offsettree.java

和YACC一样

      return false;
    }
  }

  /** (Re)compute the contours for the tree rooted at this.
   * @return			true iff the new contours differ from the
   *				previously computed one.
   */
  private boolean computeContours() {
    boolean isChanged= false;
    int nKids1= nKids();
    if (nKids1 > 0) { 
      if (!isExpand) {
	isChanged= contours[LEFT].length > 0;
	if (isChanged) contours[LEFT]= contours[RIGHT]= new int[0];
      }
      else {
	int contourN, startKidN, kidNInc;
	for (contourN= LEFT, startKidN= 0, kidNInc= 1; 
	     contourN <= RIGHT; 
	     contourN++, startKidN= (nKids1 - 1), kidNInc= -1) {
	  int h;
	  if (contourN == LEFT) {
	    //Compute max. ht. of all subtrees.
	    int kidsHMax= 0;
	    for (OffsetTree kid= (OffsetTree)kid(); 
		 kid != null; kid= (OffsetTree)kid.nextSib()) {
	      if (kid.contours[contourN].length > kidsHMax) {
		kidsHMax= kid.contours[contourN].length;
	      }
	    }
	    h= kidsHMax + 1;
	  }
	  else {
	    h= contours[LEFT].length;
	  }
	  if (contours[contourN].length != h) {
	    contours[contourN]= new int[h];
	    isChanged= true;
	  }
	  OffsetTree kid= (OffsetTree)kid(startKidN);
	  isChanged|= updateContour(contours[contourN], 0, kid.offset);
	  for (int i= 1; i < h; i++) {
	    while (i - 1 >= kid.contours[contourN].length) {
	      //Find next kid of sufficient height.	Must exist.
	      kid= (OffsetTree)kid.nextSib(kidNInc);
	    } 
	    isChanged|= updateContour(contours[contourN], i,
				      kid.offset + 
				      kid.contours[contourN][i - 1]);
	  } /* for (int i= 1; i < h; i++) */
	} /* for (contourN= LEFT, ...) */
      } /* if (nKids1 > 0 && isExpand) */
    }
    return isChanged;
  }
	
  /** Calculate minimum separation between kid and its immediate
   * left sibling to prevent any collisions.
   * @param kid		kid whose separation is to be calculated.
   * @return		returns separation.
   */
  private int leftSep(OffsetTree kid) {
    int h= kid.contours[RIGHT].length; //height of kid.
    OffsetTree left= (OffsetTree)kid.nextSib(-1); 
    OffsetTree t= left;	//will iterate thru kid's left siblings.
    int tRootOffset= 0;	//offset of current t from left.
    int sep= MIN_SEP;		//separation needed from kid and left.
    for (int i= 0; i < h; i++) {//for each level of this.
      while (t != null && t.contours[RIGHT].length <= i) {
	tRootOffset-= t.offset; t= (OffsetTree)t.nextSib(-1); 
      }
      if (t == null) break;	//kid higher than anything to its left.
      //t does have a node at level i; compute offsets at level i.
      int tOffset= tRootOffset + t.contours[RIGHT][i];
      int kidOffset= sep + kid.contours[LEFT][i];
      if (kidOffset - tOffset < MIN_SEP) { //move kid to the right.
	sep+= tOffset - kidOffset + MIN_SEP;
      }
    }
    return sep;
  }

  /** Calculate minimum separation between kid and its immediate
   * right sibling to prevent any collisions.
   * @param kid		kid whose separation is to be calculated.
   * @return		returns separation.
   */
  private int rightSep(OffsetTree kid) {
    int h= kid.contours[RIGHT].length; //height of kid.
    OffsetTree right= (OffsetTree)kid.nextSib(); 
    OffsetTree t= right;	//will iterate thru kid's right siblings.
    int tRootOffset= 0;	        //offset of current t from right.
    int sep= MIN_SEP;		//separation needed from kid and right.
  separate:
    for (int i= 0; i < h; i++) {//for each level of this.
      while (t != null && t.contours[LEFT].length <= i) {
	t= (OffsetTree)t.nextSib(); 
	if (t == null) break separate; //kid higher than anything to right.
	tRootOffset+= t.offset; 
      }
      //t does have a node at level i; compute offsets at level i.
      int tOffset= tRootOffset + t.contours[LEFT][i];
      int kidOffset= kid.contours[RIGHT][i] - sep;
      if (tOffset - kidOffset < MIN_SEP) { //move right to the right.
	sep+= kidOffset - tOffset + MIN_SEP;
      }
    }
    return sep;
  }

  /** Calculate minimum separation between kid # k and its immediate
   * siblings to prevent any collisions.  
   * @param kid		kid whose separation is to be updated..
   * @param k		the index of kid among the kids to this.
   */
  private void separation(OffsetTree kid, int k) {
    int n= nKids();
    if (k == 0) {
      kid.offset= 0;
    }
    else if (k > 0) {
      //compute separation between kid and its left sibling.
      kid.offset= leftSep(kid);
    }
    if (k < n - 1) {
      //compute separation between kid's right sibling and kid.
      ((OffsetTree)kid.nextSib()).offset= rightSep(kid);
    }
  }

  /** Calculate minimum separation between kid and its immediate
   * left sibling to prevent any collisions.
   * @param kid		kid whose separation is to be calculated.
   * @return		returns separation.
   *
   * Unlike leftSep(), this ensures no collisions between all right
   * siblings of kid and all left siblings of kid.
   *
   * Probably untested.
   */
  private int fullSep(OffsetTree kid) {
    int sep= MIN_SEP;
    OffsetTree left= (OffsetTree)kid.nextSib(-1);
    OffsetTree tLeft= left;
    int leftRootOffset= 0;
    OffsetTree tRight= kid;
    int rightRootOffset= 0;
  separate:
    for (int i= 0; true; i++) {
      while (tRight != null && tRight.contours[LEFT].length <= i) {
	tRight= (OffsetTree)tRight.nextSib();
	if (tRight == null) break separate;
	rightRootOffset+= tRight.offset;
      }
      while (tLeft != null && tLeft.contours[RIGHT].length <= i) {
	leftRootOffset-= tLeft.offset; tLeft= (OffsetTree)tLeft.nextSib(-1);
      }
      if (tRight == null || tLeft == null) break;
      int rightOffset= sep + rightRootOffset + tRight.contours[LEFT][i];
      int leftOffset= tLeft.contours[RIGHT][i] - leftRootOffset;
      if (rightOffset - leftOffset < MIN_SEP) {
	sep+= leftOffset - rightOffset + MIN_SEP;
      }
    }
    return sep;
  }

  public int height() {
    return contours[LEFT].length;
  }

  public String toString() { 
    StringBuffer b= new StringBuffer();
    b.append(super.toString() + "@" + offset);
    if (debug != 0) {
      for (int i= LEFT; i <= RIGHT; i++) {
	b.append(" [");
	for (int j= 0; j < contours[i].length; j++) {
	  b.append(contours[i][j] + " ");
	}
	b.append("]");
	if (i == LEFT) b.append(" /");
      }
    }
    return b.toString();
  }

  private static final int LEFT= 0;
  private static final int RIGHT= 1;
  private static final int MIN_SEP= 1;
  private static final int debug= 1;
  private int[][] contours= new int[2][0];
  private int[] widths= new int[2];
  private int offset= 0;	//Offset of this node from its parent.
  private boolean isExpand= true;

  /* Simple test program, basically tests addKid() and constructors. */
  static public void main(String args[]) {
    OffsetTree treeX = new OffsetTree("A",
				      new OffsetTree("0"),
				      new OffsetTree("1"),
				      new OffsetTree("2"));
    System.out.println(treeX.treeString());

    OffsetTree t000= new OffsetTree("A");
    OffsetTree t001= new OffsetTree("B");
    OffsetTree t002= new OffsetTree("C");
    OffsetTree t00= new OffsetTree("D", t000, t001, t002);
    t00.addKid(new OffsetTree("E"));
    t00.addKid(new OffsetTree("F", new OffsetTree("G")), 1);
    OffsetTree OffsetTrees[]= { t00, 
		    new OffsetTree("H", new OffsetTree("I"), 
				   new OffsetTree("J")), 
		    new OffsetTree("K"), 
		    new OffsetTree("L")
                  };
    OffsetTree t0= new OffsetTree("M", OffsetTrees);
    System.out.println(t0.treeString());

    if (false) {
    OffsetTree prg= new OffsetTree("program");
    OffsetTree stmts= new OffsetTree("stmts");
    prg.addKid(stmts);
    OffsetTree assgnStmt= new OffsetTree("assgn");
    stmts.addKid(assgnStmt);
    assgnStmt.addKid(new OffsetTree("a"));
    assgnStmt.addKid(new OffsetTree(":="));
    OffsetTree expr= new OffsetTree("expr");
    assgnStmt.addKid(expr);
    OffsetTree term= new OffsetTree("term");
    expr.addKid(term);
    OffsetTree factor= new OffsetTree("factor");
    term.addKid(factor);
    factor.addKid(new OffsetTree("1"));
    OffsetTree stmtsRest= new OffsetTree("stmtsRest");
    stmts.addKid(stmtsRest);
    stmtsRest.addKid(new OffsetTree(";"));
    System.out.println(prg.treeString());

    OffsetTree tStmts= new OffsetTree("stmts");
    OffsetTree tAssgn= new OffsetTree("assgn");
    tStmts.addKid(tAssgn);
    tAssgn.addKid(new OffsetTree("a")); tAssgn.addKid(new OffsetTree(":="));
    OffsetTree tRestStmts= new OffsetTree("restStmts");
    tStmts.addKid(tRestStmts);
    tRestStmts.addKid(new OffsetTree(";"));
    System.out.println(tStmts.treeString());
   

    OffsetTree x= 
      new OffsetTree("stmts",
        new OffsetTree("assgnStmt", 
	  new OffsetTree("a"),
          new OffsetTree(":="),
          new OffsetTree("expr",
            new OffsetTree("term",
              new OffsetTree("factor",
                new OffsetTree("1"))))),
        new OffsetTree(";"),
        new OffsetTree("stmts",
          new OffsetTree("assgnStmt",
            new OffsetTree("b"),
            new OffsetTree(":="),
	    new OffsetTree("expr",
              new OffsetTree("expr",
                new OffsetTree("term",
                  new OffsetTree("factor",
                    new OffsetTree("1")))),
              new OffsetTree("+"),
              new OffsetTree("term",
                new OffsetTree("factor",
                  new OffsetTree("2")))))));
    System.out.println(x.treeString());
    }
  }

}