diff options
author | Karl Berry <karl@freefriends.org> | 2013-04-08 18:41:28 +0000 |
---|---|---|
committer | Karl Berry <karl@freefriends.org> | 2013-04-08 18:41:28 +0000 |
commit | a3358f7394e3adabeff44a4858bab8f13cbe1180 (patch) | |
tree | 014354d566c06a47c483b7231af921247180f770 /Master/texmf-dist/asymptote/binarytree.asy | |
parent | 11bcd1a52098dab6ac5baa790409a2261a31755f (diff) |
asymptote 2.21
git-svn-id: svn://tug.org/texlive/trunk@29753 c570f23f-e606-0410-a88d-b1316a301751
Diffstat (limited to 'Master/texmf-dist/asymptote/binarytree.asy')
-rw-r--r-- | Master/texmf-dist/asymptote/binarytree.asy | 211 |
1 files changed, 134 insertions, 77 deletions
diff --git a/Master/texmf-dist/asymptote/binarytree.asy b/Master/texmf-dist/asymptote/binarytree.asy index 0a80aec4b66..31e0e3aab61 100644 --- a/Master/texmf-dist/asymptote/binarytree.asy +++ b/Master/texmf-dist/asymptote/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); } |