"Fossies" - the Fresh Open Source Software Archive

Member "asymptote-2.60/base/binarytree.asy" (6 Nov 2019, 11482 Bytes) of package /linux/misc/asymptote-2.60.src.tgz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file.

    1 /* **********************************************************************
    2  * binarytree: An Asymptote module to draw binary trees                 *
    3  *                                                                      *
    4  * Copyright(C) 2006                                                    *
    5  * Tobias Langner tobias[at]langner[dot]nightlabs[dot]de                *
    6  *                                                                      *
    7  * Modified by John Bowman                                              *
    8  *                                                                      *
    9  * Condensed mode:                                                      *
   10  * Copyright(C) 2012                                                    *
   11  * Gerasimos Dimitriadis dimeg [at] intracom [dot] gr                   *
   12  *                                                                      *
   13  ************************************************************************
   14  *                                                                      *
   15  * This library is free software; you can redistribute it and/or        *
   16  * modify it under the terms of the GNU Lesser General Public           *
   17  * License as published by the Free Software Foundation; either         *
   18  * version 3 of the License, or(at your option) any later version.      *
   19  *                                                                      *
   20  * This library is distributed in the hope that it will be useful,      *
   21  * but WITHOUT ANY WARRANTY; without even the implied warranty of       *
   22  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU    *
   23  * Lesser General Public License for more details.                      *
   24  *                                                                      *
   25  * You should have received a copy of the GNU Lesser General Public     *
   26  * License along with this library; if not, write to the                *
   27  *     Free Software Foundation, Inc.,                                  *
   28  *     51 Franklin St, Fifth Floor,                                     *
   29  *     Boston, MA  02110-1301  USA                                      *
   30  *                                                                      *
   31  * Or get it online:                                                    *
   32  *     http: //www.gnu.org/copyleft/lesser.html                         *
   33  *                                                                      *
   34  ***********************************************************************/
   35 
   36 // default values
   37 real minDistDefault=0.2cm;
   38 real nodeMarginDefault=0.1cm;
   39 
   40 // structure to represent nodes in a binary tree
   41 struct binarytreeNode {
   42   int key;
   43   binarytreeNode left;
   44   binarytreeNode right;
   45   binarytreeNode parent;
   46   bool spans_calculated=false;
   47   int left_span,total_left_span;
   48   int right_span,total_right_span;
   49   void update_spans();
   50 
   51   // Get the horizontal span of the tree consisting of the current 
   52   // node plus the whole subtree that is rooted at the right child 
   53   // (condensed mode)
   54   int getTotalRightSpan() {
   55     if(spans_calculated == false) {
   56       update_spans();
   57     }
   58 
   59     return total_right_span;
   60   }
   61 
   62   // Get the horizontal span of the tree consisting of the current 
   63   // node plus the whole subtree that is rooted at the left child 
   64   // (condensed mode)
   65   int getTotalLeftSpan() {
   66     if(spans_calculated == false) {
   67       update_spans();
   68     }
   69     return total_left_span;
   70   }
   71 
   72   // Get the horizontal distance between this node and its right child
   73   // (condensed mode)
   74   int getRightSpan() {
   75     if(spans_calculated == false) {
   76       update_spans();
   77     }
   78     return right_span;
   79   }
   80 
   81   // Get the horizontal distance between this node and its left child
   82   // (condensed mode)
   83   int getLeftSpan() {
   84     if(spans_calculated == false) {
   85       update_spans();
   86     }
   87     return left_span;
   88   }
   89 
   90   // Update all span figures for this node. 
   91   // condensed mode)
   92   update_spans=new void() {
   93     if(spans_calculated == true)
   94       return;
   95 
   96     left_span=0;
   97     total_left_span=0;
   98     right_span=0;
   99     total_right_span=0;
  100 
  101     if(left != null) {
  102       left_span=left.getTotalRightSpan()+1;
  103       total_left_span=left_span+left.getTotalLeftSpan();
  104     }
  105 
  106     if(right != null) {
  107       right_span=right.getTotalLeftSpan()+1;
  108       total_right_span=right_span+right.getTotalRightSpan();
  109     }
  110     spans_calculated=true;
  111   };
  112 
  113   // set the left child of this node
  114   void setLeft(binarytreeNode left) {
  115     this.left=left;
  116     this.left.parent=this;
  117   }
  118 
  119   // set the right child of this node
  120   void setRight(binarytreeNode right) {
  121     this.right=right;
  122     this.right.parent=this;
  123   }
  124 
  125   // return a boolean indicating whether this node is the root
  126   bool isRoot() {
  127     return parent == null;
  128   }
  129 
  130   // return the level of the subtree rooted at this node.
  131   int getLevel() {
  132     if(isRoot())
  133       return 1;
  134     else
  135       return parent.getLevel()+1;
  136   }
  137         
  138   // set the children of this binarytreeNode
  139   void setChildren(binarytreeNode left, binarytreeNode right) {
  140     setLeft(left);
  141     setRight(right);
  142   }
  143         
  144   // create a new binarytreeNode with key <key> 
  145   static binarytreeNode binarytreeNode(int key) {
  146     binarytreeNode toReturn=new binarytreeNode;
  147     toReturn.key=key;
  148     return toReturn;
  149   }
  150         
  151   // returns the height of the subtree rooted at this node.
  152   int getHeight() {
  153     if(left == null && right == null)
  154       return 1;
  155     if(left == null)
  156       return right.getHeight()+1;
  157     if(right == null)
  158       return left.getHeight()+1;
  159                 
  160     return max(left.getHeight(),right.getHeight())+1;
  161   }
  162 }
  163 
  164 binarytreeNode operator init() {return null;}
  165 
  166 // "constructor" for binarytreeNode
  167 binarytreeNode binarytreeNode(int key)=binarytreeNode.binarytreeNode;
  168 
  169 // draw the tree rooted at the given <node> at the given position <pos>, with
  170 // <height>=the height of the containing tree,
  171 // <minDist>=the minimal horizontal distance of two nodes at the lowest level,
  172 // <levelDist>=the vertical distance between two levels,
  173 // <nodeDiameter>=the diameter of one node.
  174 object draw(picture pic=currentpicture, binarytreeNode node, pair pos,
  175             int height, real minDist, real levelDist, real nodeDiameter,
  176             pen p=currentpen, bool condensed=false) {
  177   Label label=Label(math((string) node.key),pos);
  178         
  179   binarytreeNode left=node.left;        
  180   binarytreeNode right=node.right;
  181 
  182   // return the distance for two nodes at the given <level> when the
  183   // containing tree has height <height> 
  184   // and the minimal distance between two nodes is <minDist> .
  185   real getDistance(int level, int height, real minDist) {
  186     return(nodeDiameter+minDist)*2^(height-level);
  187   }
  188 
  189   // return the horiontal distance between node <n> and its left child
  190   // (condensed mode)
  191   real getLeftDistance(binarytreeNode n) {
  192     return(nodeDiameter+minDist) *(real)n.getLeftSpan() * 0.5;
  193   }
  194 
  195   // return the horiontal distance between node <n> and its right child
  196   // (condensed mode)
  197   real getRightDistance(binarytreeNode n) {
  198     return(nodeDiameter+minDist) *(real)n.getRightSpan() * 0.5;
  199   }
  200 
  201   real dist=getDistance(node.getLevel(),height,minDist)/2;
  202 
  203   // draw the connection between the two nodes at the given positions
  204   // by calculating the connection points and drawing the corresponding
  205   // arrow.
  206   void deferredDrawNodeConnection(pair parentPos, pair childPos) {
  207     pic.add(new void(frame f, transform t) {
  208         pair start,end; 
  209         // calculate connection path 
  210         transform T=shift(nodeDiameter/2*unit(t*childPos-t*parentPos));  
  211         path arr=(T*t*parentPos)--(inverse(T)*t*childPos);  
  212         draw(f,PenMargin(arr,p).g,p,Arrow(5));  
  213       }); 
  214     pic.addPoint(parentPos);
  215     pic.addPoint(childPos);
  216   } 
  217 
  218   if(left != null) {
  219     pair childPos;
  220     if(condensed == false) {
  221       childPos=pos-(0,levelDist)-(dist/2,0);
  222     }
  223     else {
  224       childPos=pos-(0,levelDist)-((real)getLeftDistance(node),0);
  225     }
  226     draw(pic,left,childPos,height,minDist,levelDist,nodeDiameter,p,condensed);
  227     deferredDrawNodeConnection(pos,childPos);
  228   }
  229 
  230   if(right != null) {
  231     pair childPos;
  232     if(condensed == false) {
  233       childPos=pos-(0,levelDist)+(dist/2,0);
  234     }
  235     else {
  236       childPos=pos-(0,levelDist)+((real)getRightDistance(node),0);
  237     }
  238     draw(pic,right,childPos,height,minDist,levelDist,nodeDiameter,p,condensed);
  239     deferredDrawNodeConnection(pos,childPos);
  240   }
  241         
  242   picture obj;
  243   draw(obj,circle((0,0),nodeDiameter/2),p);
  244   label(obj,label,(0,0),p);
  245         
  246   add(pic,obj,pos);
  247         
  248   return label;
  249 }
  250 
  251 struct key {
  252   int n;
  253   bool active;
  254 }
  255 
  256 key key(int n, bool active=true) {key k; k.n=n; k.active=active; return k;}
  257 
  258 key operator cast(int n) {return key(n);}
  259 int operator cast(key k) {return k.n;}
  260 int[] operator cast(key[] k) {
  261   int[] I;
  262   for(int i=0; i < k.length; ++i)
  263     I[i]=k[i].n;
  264   return I;
  265 }
  266 
  267 key nil=key(0,false);
  268 
  269 // structure to represent a binary tree.
  270 struct binarytree {
  271   binarytreeNode root;
  272   int[] keys;
  273         
  274   // add the given <key> to the tree by searching for its place and
  275   // inserting it there.
  276   void addKey(int key) {
  277     binarytreeNode newNode=binarytreeNode(key);
  278                 
  279     if(root == null) {
  280       root=newNode;
  281       keys.push(key);
  282       return; 
  283     }
  284                 
  285     binarytreeNode n=root;
  286     while(n != null) {
  287       if(key < n.key) {
  288         if(n.left != null)
  289           n=n.left;
  290         else {
  291           n.setLeft(newNode);
  292           keys.push(key);
  293           return;
  294         }
  295       } else if(key > n.key) {
  296         if(n.right != null)
  297           n=n.right;
  298         else {
  299           n.setRight(newNode);
  300           keys.push(key);
  301           return;
  302         }
  303       }
  304     }
  305   }
  306         
  307   // return the height of the tree
  308   int getHeight() {
  309     if(root == null)
  310       return 0;
  311     else
  312       return root.getHeight();
  313   }
  314         
  315   // add all given keys to the tree sequentially
  316   void addSearchKeys(int[] keys) {
  317     for(int i=0; i < keys.length; ++i) {
  318       int key=keys[i];
  319       // Ignore duplicate keys
  320       if(find(this.keys == key) == -1)
  321         addKey(key);
  322     }
  323   }
  324         
  325   binarytreeNode build(key[] keys, int[] ind) {
  326     if(ind[0] >= keys.length) return null;
  327     key k=keys[ind[0]];
  328     ++ind[0];
  329     if(!k.active) return null;
  330     binarytreeNode bt=binarytreeNode(k);
  331     binarytreeNode left=build(keys,ind);
  332     binarytreeNode right=build(keys,ind);
  333     bt.left=left; bt.right=right;
  334     if(left != null) left.parent=bt;
  335     if(right != null) right.parent=bt;
  336     return bt;
  337   }
  338 
  339   void addKeys(key[] keys) {
  340     int[] ind={0};
  341     root=build(keys,ind);
  342     this.keys=keys;
  343   }
  344 
  345 
  346   // return all key in the tree
  347   int[] getKeys() {
  348     return keys;
  349   }
  350 }
  351 
  352 binarytree searchtree(...int[] keys)
  353 {
  354   binarytree bt;
  355   bt.addSearchKeys(keys);
  356   return bt;
  357 }
  358 
  359 binarytree binarytree(...key[] keys)
  360 {
  361   binarytree bt;
  362   bt.addKeys(keys);
  363   return bt;
  364 }
  365 
  366 // draw the given binary tree.
  367 void draw(picture pic=currentpicture, binarytree tree,
  368           real minDist=minDistDefault, real nodeMargin=nodeMarginDefault,
  369           pen p=currentpen, bool condensed=false)
  370 {
  371   int[] keys=tree.getKeys();
  372         
  373   // calculate the node diameter so that all keys fit into it
  374   frame f; 
  375   for(int i=0; i < keys.length; ++i)
  376     label(f,math(string(keys[i])),p);
  377 
  378   real nodeDiameter=abs(max(f)-min(f))+2*nodeMargin;
  379   real levelDist=nodeDiameter*1.8;
  380 
  381   draw(pic,tree.root,(0,0),tree.getHeight(),minDist,levelDist,nodeDiameter,p,
  382        condensed);
  383 }