offsettree.java

和YACC一样

/*

File:	 OffsetTree.java
Author:  zerksis d. umrigar ([e-mail])
Copyright (C) 1997 Zerksis D. Umrigar
Last Update Time-stamp: "97/07/27 09:12:05 zdu"

This code is distributed under the terms of the GNU General Public License.
See the file COPYING with this distribution, or

		http://www.fsf.org/copyleft/gpl.html

THERE IS ABSOLUTELY NO WARRANTY FOR THIS PROGRAM.

*/

package zdu.zydebug;

import zdu.zydebug.Tree;

/** Trees where each kid maintains an offset from its parent, which
 * can be used to draw the tree.
 */

/* 

This is adapted from "Tidier Drawing of Trees", by E. M. Reingold and
J. S. Tilford, IEEETSE, Vol. SE-7, Number 2, March 1981, pp. 223--228.

This algorithm needs to be incremental, so that subtrees can be
inserted at arbitrary nodes.  Hence for a straightforward adaptation,
each node would need to store information about its lowest level
leftmost and rightmost nodes (EXTREME information, in the terminology
of the paper).  Since we are also allowing general m-ary (rather than
merely binary) trees, we would also need 3 offset fields per node, if
we followed the suggestion in the paper (I could not understand how to
determine which offset field corresponded to which thread pointing to
a node).  This would be quite a lot of auxiliary storage per node.

Instead in the algorithm used here, we store the left and right
contours of each subtree at the root of the subtree.  If we use an
array for the contour, this requires additional storage of 2*h, where
h is the height of the node.  This will win over the above adaptation
when h is less than about 5; it will loose when h >= 5, but the
implementation appears simpler, without bothering about updating
threads incrementally.

If the height of a subtree is h, then left (right) contour[i] contains
the absolute displacement from the subtree root of the left (right)
contour of the tree at level (i + 1) (the root is level 0).

The main action used here is adding a kid subtree to a node.  When a
subtree is added, its contour is used to compute its separation from
its left sibling, then the separation for its right sibling is
computed.  Finally, the contours for the parent are recomputed; if
they have changed, then the its parent is recomputed, and so on.  The
worst case (which may happen often) occurs when the subtree is added
to the lowest level of the tree, in which case all nodes between the
point of addition and the root (inclusive) need their contours
recomputed.

When checking for collisions, it is not sufficient to check for
collisions only with immediate siblings.  It is necessary to check for
collisions with non-immediate siblings too, when the height of the
immediate sibling is less than the height of non-immediate siblings.

Note that the implementation distinguishes between computing the
separation of a newly added kid and existing kids.  To minimize the
computation when a new kid is added, it separates the kid from its
left siblings and its right siblings to ensure they do not collide; to
do this, it merely needs to check all the levels in the new kid versus
its left siblings and right siblings.  However, when two siblings are
brought closer together after a node is removed, it is necessary to
check all levels to the minimum of the height of the left siblings and
the right siblings.

*/

class OffsetTree extends Tree {

  /** Nullary OffsetTree constructor. 
   * @param info	Information stored in tree node being constructed.
   */
  OffsetTree(Object info) {
    super(info);
  }

  /** Unary OffsetTree constructor. 
   * @param info	Information stored in tree node being constructed.
   * @param kid0	Single child of constructed OffsetTree node.
   */
  OffsetTree(Object info, OffsetTree kid0) {
    super(info, kid0);
    kid0.offset= 0;
    sepToOffset();
    updateParent();
  }

  /** Binary OffsetTree constructor. 
   * @param info	Information stored in tree node being constructed.
   * @param kid0	Left child of constructed OffsetTree node.
   * @param kid1	Right child of constructed OffsetTree node.
   */
  OffsetTree(Object info, OffsetTree kid0, OffsetTree kid1) {
    super(info);
    addKid(kid0); addKid(kid1);
  }

  /** Ternary OffsetTree constructor.
   * @param info	Information stored in tree node being constructed.
   * @param kid0	Leftmost child of constructed OffsetTree node.
   * @param kid1	Middle child of constructed OffsetTree node.
   * @param kid2	Rightmost child of constructed OffsetTree node.
   */
  OffsetTree(Object info, OffsetTree kid0, OffsetTree kid1, OffsetTree kid2) {
    super(info);
    addKid(kid0); addKid(kid1); addKid(kid2);
  }

  /** General n-ary OffsetTree constructor.
   * @param info	Information stored in tree node being constructed.
   * @param kids	Array of OffsetTrees which will be kids 
   *			of constructed node.
   */
  OffsetTree(Object info, OffsetTree kids[]) {
    super(info);
    for (int i= 0; i < kids.length; i++) {
      addKid(kids[i]);
    }
  }

  /** Add a kid as the last kid for this OffsetTree-node.
   * @param kid		kid to be added to this OffsetTree-node.
   */
  public void addKid(OffsetTree kid) {
    addKid(kid, nKids());
  }

  /** Add a kid after the k'th current kid for this offsetTree-node.  
   * @param kid		The kid to be added.
   * @param k		The existing kid after which the new kid should be
   *			added.  If k is >= the # of existing kids, then the
   *			new kid is added as the last kid.  If k < 0, then
   *			the new kid is added as the first kid.
   */
  public void addKid(OffsetTree kid, int k) {
    offsetToSep();
    super.addKid(kid, k);
    separation(kid, k + 1);
    sepToOffset();
    updateParent();
  }

  public int getOffset() {
    return offset;
  }

  /** Remove kth kid.   No action if this does not have a kid k.
   * @return		kid if it is removed; null if not.
   */
  public Tree rmKid(int k) {
    int n= nKids();
    OffsetTree kid= null;
    if (0 <= k && k < n) {
      offsetToSep();
      OffsetTree right= (OffsetTree)kid(k + 1);
      kid= (OffsetTree)super.rmKid(k);
      kid.offset= 0;
      if (right != null) {
	right.offset= (k == 0) ? 0 : fullSep(right);
      }
      sepToOffset();
      updateParent();
    }
    return kid;
  }

  /** Remove kid.       No action if this does not have kid.
   * @return		kid if it is removed; null if not.
   */
  public Tree rmKid(OffsetTree kid) {
    int k= getKidN(kid);
    return rmKid(k);
  }

  //Instead of calculating this here, we could cache the value for each
  //node within the node (the calculation would be done just once while
  //doing computeContours().
  public int leftWidth() {
    int n= contours[LEFT].length;
    int w= 0;
    for (int i= 0; i < n; i++) {
      if (contours[LEFT][i] < w) w= contours[LEFT][i];
    }
    return -w;
  }

  //Instead of calculating this here, we could cache the value for each
  //node within the node (the calculation would be done just once while
  //doing computeContours().
  public int rightWidth() {
    int n= contours[RIGHT].length;
    int w= 0;
    for (int i= 0; i < n; i++) {
      if (contours[RIGHT][i] > w) w= contours[RIGHT][i];
    }
    return w;
  }

  public boolean getExpand() {
    return isExpand;
  }
  
  public void setExpand(boolean isExpand) {
    this.isExpand= isExpand;
    updateParent();
  }

  private void updateParent() {
    boolean isChanged= computeContours();
    if (isChanged) {
      OffsetTree p= (OffsetTree)parent();
      if (p != null && p.isExpand) {
	int k= p.getKidN(this);
	p.updateKid(this, k);
      }
    }
  }

  private void updateKid(OffsetTree kid, int k) {
    offsetToSep();
    separation(kid, k);
    sepToOffset();
    updateParent();
  }


  private void offsetToSep() {
    if (!isLeaf()) {
      //Convert offsets to separations.
      OffsetTree firstKid= (OffsetTree)kid();
      int off= firstKid.offset;
      firstKid.offset= 0;
      for (OffsetTree t= (OffsetTree)firstKid.nextSib(); t != null; 
	   t= (OffsetTree)(t.nextSib())) {
	int oldOff= t.offset;
	t.offset-= off;
	off= oldOff;
      }
    }
  }

  private void sepToOffset() {
    int nKids= nKids();
    if (nKids > 0 && isExpand) {
      OffsetTree firstKid= (OffsetTree)(kid());
      int off= 0;
      for (OffsetTree kid= (OffsetTree)firstKid.nextSib(); kid != null; 
	   kid= (OffsetTree)kid.nextSib()) {
	kid.offset+= off;
	off= kid.offset;
      }
      int rootOffset= 
	(nKids % 2 == 0) 
        ? (((OffsetTree)kid(nKids/2 - 1)).offset +
	   ((OffsetTree)kid(nKids/2)).offset)/2
        : ((OffsetTree)kid(nKids/2)).offset;
      for (OffsetTree kid= firstKid; kid != null; 
	   kid= (OffsetTree)kid.nextSib()) {
	kid.offset-= rootOffset;
      }
    }
  }

  private final boolean updateContour(int contour[], int index, int value) {
    if (contour[index] != value) {
      contour[index]= value;
      return true;
    }
    else {