c525ffad81d2229a9ed0162d16980191d9df3609
[sbp.git] / src / edu / berkeley / sbp / Tree.java
1 package edu.berkeley.sbp;
2 import edu.berkeley.sbp.*;
3 import edu.berkeley.sbp.util.*;
4 import edu.berkeley.sbp.bind.*;
5 import java.io.*;
6 import java.util.*;
7 import java.lang.reflect.*;
8
9 /** a tree (or node in a tree); see jargon.txt for details */
10 public class Tree<T>
11     extends PrintableTree<Tree<T>>
12     implements Iterable<Tree<T>>,
13                GraphViz.ToGraphViz {
14
15     private final T            head;
16     private final Tree<T>[]    children;
17     private final Input.Region location;
18     private final boolean      lift;
19
20     public T                 head()        { return head; }
21
22     private Tree<T> lifted() { return children[children.length-1]; }
23
24     public int               numChildren() {
25         if (lift && children.length > 0)
26             return (children.length-1)+lifted().numChildren();
27         return children.length;
28     }
29     public Iterable<Tree<T>> children()    { return this; }
30     public Iterator<Tree<T>> iterator()    {
31         if (lift)
32             return new ConcatenateIterator(new ArrayIterator(children, 0, children.length-1),
33                                            children[children.length-1].iterator());
34         return new ArrayIterator(children);
35     }
36     public Tree<T>           child(int i)  {
37         if (lift && i >= children.length-1)
38             return children[children.length-1].child(i-(children.length-1));
39         return children[i];
40     }
41
42     public Input.Region    getRegion() { return location; }
43
44     public Tree(Input.Region loc, T head)                   { this(loc, head, null); }
45     public Tree(Input.Region loc, T head, Tree<T>[] children) { this(loc, head, children, false); }
46     public Tree(Input.Region loc, T head, Tree<T>[] children, boolean lift) {
47         this.location = loc;
48         this.head = head;
49         this.lift = lift;
50
51         Tree<T>[] children2 = children==null ? new Tree[0] : new Tree[children.length];
52         if (children != null) System.arraycopy(children, 0, children2, 0, children.length);
53         this.children = children2;
54     }
55
56     protected String headToString() { return head()==null?null:head().toString(); }
57     protected String headToJava()   {
58       // FIXME
59         if (head()==null) return null;
60         if (head() instanceof ToJava) {
61             StringBuffer sb = new StringBuffer();
62             ((ToJava)head()).toJava(sb);
63             return sb.toString();
64         }
65         return (head()==null?"null":("\""+StringUtil.toJavaString(head().toString())+"\""));
66     }
67     protected String left()   { return "{"; }
68     protected String right()  { return "}"; }
69     protected boolean ignoreSingleton() { return false; }
70
71     public GraphViz.Node toGraphViz(GraphViz gv) {
72         if (gv.hasNode(this)) return gv.createNode(this);
73         GraphViz.Node n = gv.createNode(this);
74         n.label = head()==null ? "" : head().toString();
75         //n.color = "red";
76         for(Tree t : this) n.edge(t, null);
77         return n;
78     }
79     public boolean isTransparent() { return false; }
80     public boolean isHidden() { return false; }
81
82     public static interface TreeFunctor<T,R> extends Functor<Iterable<Tree<T>>, R> {
83     }
84
85     public static class ArrayBuildingTreeFunctor<T> implements TreeFunctor<T,T[]>, ToJava {
86
87         public void toJava(StringBuffer sb) { sb.append("new Tree.ArrayBuildingTreeFunctor()"); }
88         public String toString() { return ""; }
89         
90         public T[] invoke(Iterable<Tree<T>> t) {
91             ArrayList ret = new ArrayList();
92             for(Tree tc : t) {
93                 if (tc.head() != null && tc.head() instanceof Functor)
94                     ret.add(((Functor<Iterable<Tree>,Object>)tc.head()).invoke(tc.children()));
95                 else if (tc.numChildren() == 0)
96                     ret.add(tc.head());
97                 else {
98                     System.err.println("FIXME: don't know what to do about " + tc);
99                     ret.add(null);
100                 }
101             }
102             return (T[])ret.toArray(new Object[0]);
103         }
104     }
105
106     public static class RawBindingFunctor<T> implements TreeFunctor<T,Object>, ToJava {
107         private Binding _binding;
108         public void toJava(StringBuffer sb) {
109             sb.append("new Tree.RawBindingFunctor(");
110             _binding.toJava(sb);
111             sb.append(")");
112         }
113         public RawBindingFunctor(Binding binding) {
114             this._binding = binding;
115         }
116         public Object invoke(Iterable<Tree<T>> t) {
117             return _binding.invoke(new Object[] { t });           
118         }
119     }
120
121     public static class BindingFunctor<T> implements TreeFunctor<T,Object>, ToJava {
122         private Binding _binding;
123         public BindingFunctor(Binding binding) {
124             this._binding = binding;
125         }
126         public void toJava(StringBuffer sb) {
127             sb.append("new Tree.BindingFunctor(");
128             _binding.toJava(sb);
129             sb.append(")");
130         }
131         public Object invoke(Iterable<Tree<T>> t) {
132             ArrayList ret = new ArrayList();
133             for(Tree tc : t) {
134                 if (tc.head() != null && tc.head() instanceof Functor)
135                     ret.add(((Tree.TreeFunctor<Object,Object>)tc.head()).invoke(tc.children()));
136                 else if (tc.numChildren() == 0)
137                     ret.add(tc.head());
138                 else {
139                     System.err.println("FIXME: don't know what to do about " + tc);
140                     ret.add(null);
141                 }
142             }
143             Object[] o = (Object[])ret.toArray(new Object[0]);
144             return _binding.invoke(o);
145         }
146     }
147
148 }