summaryrefslogtreecommitdiff
path: root/Build/source/utils/asymptote/base/binarytree.asy
diff options
context:
space:
mode:
Diffstat (limited to 'Build/source/utils/asymptote/base/binarytree.asy')
-rw-r--r--Build/source/utils/asymptote/base/binarytree.asy211
1 files changed, 134 insertions, 77 deletions
diff --git a/Build/source/utils/asymptote/base/binarytree.asy b/Build/source/utils/asymptote/base/binarytree.asy
index 0a80aec4b66..31e0e3aab61 100644
--- a/Build/source/utils/asymptote/base/binarytree.asy
+++ b/Build/source/utils/asymptote/base/binarytree.asy
@@ -1,17 +1,21 @@
/* **********************************************************************
* binarytree: An Asymptote module to draw binary trees *
* *
- * Copyright (C) 2006 *
+ * Copyright(C) 2006 *
* Tobias Langner tobias[at]langner[dot]nightlabs[dot]de *
* *
* Modified by John Bowman *
* *
+ * Condensed mode: *
+ * Copyright(C) 2012 *
+ * Gerasimos Dimitriadis dimeg [at] intracom [dot] gr *
+ * *
************************************************************************
* *
* This library is free software; you can redistribute it and/or *
* modify it under the terms of the GNU Lesser General Public *
* License as published by the Free Software Foundation; either *
- * version 3 of the License, or (at your option) any later version. *
+ * version 3 of the License, or(at your option) any later version. *
* *
* This library is distributed in the hope that it will be useful, *
* but WITHOUT ANY WARRANTY; without even the implied warranty of *
@@ -25,51 +29,105 @@
* Boston, MA 02110-1301 USA *
* *
* Or get it online: *
- * http://www.gnu.org/copyleft/lesser.html *
+ * http: //www.gnu.org/copyleft/lesser.html *
* *
***********************************************************************/
-/**
- * default values
- */
+// default values
real minDistDefault=0.2cm;
real nodeMarginDefault=0.1cm;
-/**
- * structure to represent nodes in a binary tree
- */
+// structure to represent nodes in a binary tree
struct binarytreeNode {
int key;
binarytreeNode left;
binarytreeNode right;
binarytreeNode parent;
-
- /**
- * sets the left child of this node
- */
+ bool spans_calculated=false;
+ int left_span,total_left_span;
+ int right_span,total_right_span;
+ void update_spans();
+
+ // Get the horizontal span of the tree consisting of the current
+ // node plus the whole subtree that is rooted at the right child
+ // (condensed mode)
+ int getTotalRightSpan() {
+ if(spans_calculated == false) {
+ update_spans();
+ }
+
+ return total_right_span;
+ }
+
+ // Get the horizontal span of the tree consisting of the current
+ // node plus the whole subtree that is rooted at the left child
+ // (condensed mode)
+ int getTotalLeftSpan() {
+ if(spans_calculated == false) {
+ update_spans();
+ }
+ return total_left_span;
+ }
+
+ // Get the horizontal distance between this node and its right child
+ // (condensed mode)
+ int getRightSpan() {
+ if(spans_calculated == false) {
+ update_spans();
+ }
+ return right_span;
+ }
+
+ // Get the horizontal distance between this node and its left child
+ // (condensed mode)
+ int getLeftSpan() {
+ if(spans_calculated == false) {
+ update_spans();
+ }
+ return left_span;
+ }
+
+ // Update all span figures for this node.
+ // condensed mode)
+ update_spans=new void() {
+ if(spans_calculated == true)
+ return;
+
+ left_span=0;
+ total_left_span=0;
+ right_span=0;
+ total_right_span=0;
+
+ if(left != null) {
+ left_span=left.getTotalRightSpan()+1;
+ total_left_span=left_span+left.getTotalLeftSpan();
+ }
+
+ if(right != null) {
+ right_span=right.getTotalLeftSpan()+1;
+ total_right_span=right_span+right.getTotalRightSpan();
+ }
+ spans_calculated=true;
+ };
+
+ // set the left child of this node
void setLeft(binarytreeNode left) {
this.left=left;
this.left.parent=this;
}
- /**
- * sets the right child of this node
- */
+ // set the right child of this node
void setRight(binarytreeNode right) {
this.right=right;
this.right.parent=this;
}
- /**
- * returns a boolean indicating whether this node is the root
- */
+ // return a boolean indicating whether this node is the root
bool isRoot() {
return parent == null;
}
- /**
- * Returns the level of the subtree rooted at this node.
- */
+ // return the level of the subtree rooted at this node.
int getLevel() {
if(isRoot())
return 1;
@@ -77,26 +135,20 @@ struct binarytreeNode {
return parent.getLevel()+1;
}
- /**
- * sets the children of this binarytreeNode
- */
+ // set the children of this binarytreeNode
void setChildren(binarytreeNode left, binarytreeNode right) {
setLeft(left);
setRight(right);
}
- /**
- * creates a new binarytreeNode with key <key>
- */
+ // create a new binarytreeNode with key <key>
static binarytreeNode binarytreeNode(int key) {
binarytreeNode toReturn=new binarytreeNode;
toReturn.key=key;
return toReturn;
}
- /**
- * returns the height of the subtree rooted at this node.
- */
+ // returns the height of the subtree rooted at this node.
int getHeight() {
if(left == null && right == null)
return 1;
@@ -111,43 +163,46 @@ struct binarytreeNode {
binarytreeNode operator init() {return null;}
-/**
- * "constructor" for binarytreeNode
- */
+// "constructor" for binarytreeNode
binarytreeNode binarytreeNode(int key)=binarytreeNode.binarytreeNode;
-
-/**
- * draws the tree rooted at the given <node> at the given position <pos>, with
- * <height>: the height of the containing tree,
- * <minDist>: the minimal horizontal distance of two nodes at the lowest level,
- * <levelDist> the vertical distance between two levels,
- * <nodeDiameter>: the diameter of one node.
- */
+// draw the tree rooted at the given <node> at the given position <pos>, with
+// <height>=the height of the containing tree,
+// <minDist>=the minimal horizontal distance of two nodes at the lowest level,
+// <levelDist>=the vertical distance between two levels,
+// <nodeDiameter>=the diameter of one node.
object draw(picture pic=currentpicture, binarytreeNode node, pair pos,
int height, real minDist, real levelDist, real nodeDiameter,
- pen p=currentpen) {
+ pen p=currentpen, bool condensed=false) {
Label label=Label(math((string) node.key),pos);
binarytreeNode left=node.left;
binarytreeNode right=node.right;
- /**
- * returns the distance for two nodes at the given <level> when the
- * containing tree has height <height>
- * and the minimal distance between two nodes is <minDist>.
- */
+ // return the distance for two nodes at the given <level> when the
+ // containing tree has height <height>
+ // and the minimal distance between two nodes is <minDist> .
real getDistance(int level, int height, real minDist) {
return(nodeDiameter+minDist)*2^(height-level);
}
+ // return the horiontal distance between node <n> and its left child
+ // (condensed mode)
+ real getLeftDistance(binarytreeNode n) {
+ return(nodeDiameter+minDist) *(real)n.getLeftSpan() * 0.5;
+ }
+
+ // return the horiontal distance between node <n> and its right child
+ // (condensed mode)
+ real getRightDistance(binarytreeNode n) {
+ return(nodeDiameter+minDist) *(real)n.getRightSpan() * 0.5;
+ }
+
real dist=getDistance(node.getLevel(),height,minDist)/2;
- /**
- * draws the connection between the two nodes at the given positions
- * by calculating the connection points
- * and then drawing the corresponding arrow.
- */
+ // draw the connection between the two nodes at the given positions
+ // by calculating the connection points and drawing the corresponding
+ // arrow.
void deferredDrawNodeConnection(pair parentPos, pair childPos) {
pic.add(new void(frame f, transform t) {
pair start,end;
@@ -161,14 +216,26 @@ object draw(picture pic=currentpicture, binarytreeNode node, pair pos,
}
if(left != null) {
- pair childPos=pos-(0,levelDist)-(dist/2,0);
- draw(pic,left,childPos,height,minDist,levelDist,nodeDiameter,p);
+ pair childPos;
+ if(condensed == false) {
+ childPos=pos-(0,levelDist)-(dist/2,0);
+ }
+ else {
+ childPos=pos-(0,levelDist)-((real)getLeftDistance(node),0);
+ }
+ draw(pic,left,childPos,height,minDist,levelDist,nodeDiameter,p,condensed);
deferredDrawNodeConnection(pos,childPos);
}
if(right != null) {
- pair childPos=pos-(0,levelDist)+(dist/2,0);
- draw(pic,right,childPos,height,minDist,levelDist,nodeDiameter,p);
+ pair childPos;
+ if(condensed == false) {
+ childPos=pos-(0,levelDist)+(dist/2,0);
+ }
+ else {
+ childPos=pos-(0,levelDist)+((real)getRightDistance(node),0);
+ }
+ draw(pic,right,childPos,height,minDist,levelDist,nodeDiameter,p,condensed);
deferredDrawNodeConnection(pos,childPos);
}
@@ -199,16 +266,13 @@ int[] operator cast(key[] k) {
key nil=key(0,false);
-/**
- * structure to represent a binary tree.
- */
+// structure to represent a binary tree.
struct binarytree {
binarytreeNode root;
int[] keys;
- /**
- * adds the given < key > to the tree by searching for its place and inserting it there.
- */
+ // add the given <key> to the tree by searching for its place and
+ // inserting it there.
void addKey(int key) {
binarytreeNode newNode=binarytreeNode(key);
@@ -240,9 +304,7 @@ struct binarytree {
}
}
- /**
- * returns the height of the tree
- */
+ // return the height of the tree
int getHeight() {
if(root == null)
return 0;
@@ -250,9 +312,7 @@ struct binarytree {
return root.getHeight();
}
- /**
- * adds all given keys to the tree sequentially
- */
+ // add all given keys to the tree sequentially
void addSearchKeys(int[] keys) {
for(int i=0; i < keys.length; ++i) {
int key=keys[i];
@@ -283,9 +343,7 @@ struct binarytree {
}
- /**
- * returns all key in the tree
- */
+ // return all key in the tree
int[] getKeys() {
return keys;
}
@@ -305,12 +363,10 @@ binarytree binarytree(...key[] keys)
return bt;
}
-/**
- * draws the given binary tree.
- */
+// draw the given binary tree.
void draw(picture pic=currentpicture, binarytree tree,
real minDist=minDistDefault, real nodeMargin=nodeMarginDefault,
- pen p=currentpen)
+ pen p=currentpen, bool condensed=false)
{
int[] keys=tree.getKeys();
@@ -322,5 +378,6 @@ void draw(picture pic=currentpicture, binarytree tree,
real nodeDiameter=abs(max(f)-min(f))+2*nodeMargin;
real levelDist=nodeDiameter*1.8;
- draw(pic,tree.root,(0,0),tree.getHeight(),minDist,levelDist,nodeDiameter,p);
+ draw(pic,tree.root,(0,0),tree.getHeight(),minDist,levelDist,nodeDiameter,p,
+ condensed);
}