src/edu/berkeley/sbp/Tree.java

   1 // Copyright 2006-2007 all rights reserved; see LICENSE file for BSD-style license
   2
   3 package edu.berkeley.sbp;
   4 import edu.berkeley.sbp.*;
   5 import edu.berkeley.sbp.util.*;
   6 import java.io.*;
   7 import java.util.*;
   8 import java.lang.reflect.*;
   9
  10 /** <font color=blue>a tree (or node in a tree); see jargon.txt for details</font> */
  11 public class Tree<NodeType>
  12     extends PrintableTree<Tree<NodeType>>
  13     implements Iterable<Tree<NodeType>> {
  14
  15     private static final Tree[] emptyTree = new Tree[0];
  16
  17     private final Input.Region     location;
  18     private final NodeType         ihead;
  19     private final Tree<NodeType>[] children;
  20
  21     /** the number of children the tree has */
  22     public int               size() { return children.length; }
  23
  24     /** the element at the head of the tree */
  25     public NodeType                 head()        { return ihead; }
  26     public NodeType              getHead()        { return ihead; }
  27
  28     /** the tree's children */
  29     public Iterable<Tree<NodeType>> children()    { return this; }
  30
  31     /** the tree's children */
  32     public Iterator<Tree<NodeType>> iterator()    { return new ArrayIterator(children); }
  33
  34     /** get the <tt>i</t>th child */
  35     public Tree<NodeType> child(int i)            { return children[i]; }
  36
  37     /** get the input region that this tree was parsed from */
  38     public Input.Region    getRegion() { return location; }
  39
  40     public Tree(Input.Region loc, NodeType head) {
  41         location = loc;
  42         ihead = head;
  43         children = emptyTree;
  44     }
  45     public Tree(Input.Region loc, NodeType head, List<Tree<NodeType>> kids){
  46         location = loc;
  47         ihead = head;
  48         if (kids.size() == 0)
  49             children = emptyTree;
  50         else {
  51             children = new Tree[kids.size()];
  52             kids.toArray(children);
  53         }
  54     }
  55     public Tree(Input.Region loc, NodeType head, Tree<NodeType>[] kids) {
  56         location = loc;
  57         ihead = head;
  58         children = (kids == null ? emptyTree : kids.clone());
  59     }
  60
  61     // FIXME: fairly inefficient because we keep copying arrays
  62     /** package-private constructor, allows setting the "lift" bit */
  63     Tree(Input.Region loc, NodeType head, Tree<NodeType>[] children, boolean[] lifts) {
  64         this.location = loc;
  65         this.ihead = head;
  66
  67         int count = 0;
  68         for(int i=0; i<children.length; i++)
  69             count += lifts[i] ? children[i].size() : 1;
  70
  71         this.children = new Tree[count];
  72         int j = 0;
  73         for(int i=0; i<children.length; i++) {
  74             if (!lifts[i])
  75                 this.children[j++] = children[i];
  76             else
  77                 for(int k=0; k<children[i].size(); k++)
  78                     this.children[j++] = children[i].child(k);
  79         }
  80     }
  81
  82
  83     // PrintableTree /////////////////////////////////////////////////////////////////////////////
  84
  85     protected String headToString() { return head()==null?null:head().toString(); }
  86     protected String headToJava()   {
  87       // FIXME
  88         if (head()==null) return null;
  89         if (head() instanceof ToJava) {
  90             StringBuffer sb = new StringBuffer();
  91             ((ToJava)head()).toJava(sb);
  92             return sb.toString();
  93         }
  94         return (head()==null?"null":("\""+StringUtil.toJavaString(head().toString())+"\""));
  95     }
  96     protected String left()   { return "{"; }
  97     protected String right()  { return "}"; }
  98     protected boolean ignoreSingleton() { return false; }
  99
 100
 101 }