sysrap/tests/tree.h

0001 #pragma once
0002
0003 #include "scanvas.h"
0004
0005
0006 enum {
0007   IN,
0008   RIN,
0009   PRE,
0010   RPRE,
0011   POST,
0012   RPOST
0013 };
0014
0015 struct u
0016 {
0017     static const char* IN_ ;
0018     static const char* RIN_ ;
0019     static const char* PRE_ ;
0020     static const char* RPRE_ ;
0021     static const char* POST_ ;
0022     static const char* RPOST_ ;
0023     static const char* OrderName(int order);
0024 };
0025
0026 const char* u::IN_ = "IN" ;
0027 const char* u::RIN_ = "RIN" ;
0028 const char* u::PRE_ = "PRE" ;
0029 const char* u::RPRE_ = "RPRE" ;
0030 const char* u::POST_ = "POST" ;
0031 const char* u::RPOST_ = "RPOST" ;
0032
0033 const char* u::OrderName(int order) // static
0034 {
0035     const char* s = nullptr ;
0036     switch(order)
0037     {
0038         case IN:    s = IN_    ; break ;
0039         case RIN:   s = RIN_   ; break ;
0040         case PRE:   s = PRE_   ; break ;
0041         case RPRE:  s = RPRE_  ; break ;
0042         case POST:  s = POST_  ; break ;
0043         case RPOST: s = RPOST_ ; break ;
0044     }
0045     return s ;
0046 }
0047
0048
0049
0050 enum {
0051   UNDEFINED = 0,
0052   INCLUDE   = 1<<0 ,
0053   EXCLUDE   = 1<<1 ,
0054   MIXED     = INCLUDE | EXCLUDE
0055 };
0056
0057 char pcls( int cls ) // static
0058 {
0059     char pcl = '_' ;
0060     switch( cls )
0061     {
0062         case UNDEFINED: pcl = 'U' ; break ;
0063         case INCLUDE:   pcl = 'I' ; break ;
0064         case EXCLUDE:   pcl = 'E' ; break ;
0065         case MIXED:     pcl = 'X' ; break ;
0066         default:        pcl = '?' ; break ;
0067     }
0068     return pcl ;
0069 }
0070
0071 struct nd
0072 {
0073     int value ;
0074     nd* left ;
0075     nd* right ;
0076
0077     nd( int value, nd* left=nullptr, nd* right=nullptr );
0078
0079     const char* desc() const ;
0080     bool is_prim() const ;
0081     bool is_boolean() const ;
0082     bool is_bileaf() const ;
0083     bool is_mixed() const ;
0084     bool is_cut_right() const ;
0085     bool is_cut_left() const ;
0086     bool is_crux() const ;
0087
0088     int cls ;
0089     int depth ;
0090
0091     int in ;
0092     int rin ;
0093     int pre ;
0094     int rpre ;
0095     int post ;
0096     int rpost ;
0097
0098     int index(int order) const ;
0099
0100     char mkr ;
0101
0102 };
0103
0104
0105 int nd::index(int order) const
0106 {
0107     int idx = -1 ;
0108     switch(order)
0109     {
0110        case IN:    idx=in   ; break ;
0111        case RIN:   idx=rin  ; break ;
0112        case PRE:   idx=pre  ; break ;
0113        case RPRE:  idx=rpre ; break ;
0114        case POST:  idx=post  ; break ;
0115        case RPOST: idx=rpost ; break ;
0116     }
0117     return idx ;
0118 }
0119
0120
0121 nd::nd(int value_, nd* left_, nd* right_)
0122     :
0123     value(value_),
0124     left(left_),
0125     right(right_),
0126     cls(UNDEFINED),
0127     depth(UNDEFINED),
0128     in(UNDEFINED),
0129     rin(UNDEFINED),
0130     pre(UNDEFINED),
0131     rpre(UNDEFINED),
0132     post(UNDEFINED),
0133     rpost(UNDEFINED),
0134     mkr('_')
0135 {
0136 }
0137
0138 const char* nd::desc() const
0139 {
0140     char tmp[30] ;
0141     snprintf(tmp, 30, "%d:%c:%c", value, pcls(cls), mkr );
0142     return strdup(tmp);
0143 }
0144
0145 bool nd::is_prim()   const {  return left == nullptr && right == nullptr ; }
0146 bool nd::is_boolean() const { return left != nullptr && right != nullptr ; }
0147 bool nd::is_bileaf() const {  return is_boolean() && left->is_prim() && right->is_prim() ; }
0148 bool nd::is_mixed() const {   return cls == MIXED ; }
0149 bool nd::is_cut_right() const {   return is_boolean() && left->cls == INCLUDE && right->cls == EXCLUDE ; }
0150 bool nd::is_cut_left()  const {   return is_boolean() && left->cls == EXCLUDE && right->cls == INCLUDE ; }
0151 bool nd::is_crux() const {        return is_cut_right() ^ is_cut_left() ; }  // XOR : is_cut_right OR is_cut_left BUT not both
0152
0153
0154 /**
0155
0156 NTreeAnalyse height 7 count 15::
0157
0158                                                      [un]
0159
0160                                               un         [cy]
0161
0162                                       un          cy
0163
0164                               un          zs
0165
0166                       un          cy
0167
0168               un          co
0169
0170       un          zs
0171
0172   zs      cy
0173
0174
0175 Could kludge cut unbalanced trees like the above simply by changing the root.
0176 But how to cut more generally such as with a balanced tree.
0177
0178 When left and right child are EXCLUDED that exclusion
0179 needs to spread upwards to the parent.
0180
0181 When the right child of a union gets EXCLUDED [cy] need to
0182 pullup the left child to replace the parent node.::
0183
0184
0185            un                              un
0186
0187                     un                              cy
0188                                  -->               /
0189                cy      [cy]                    ..         ..
0190
0191
0192 More generally when the right subtree of a union *un*
0193 is all excluded need to pullup the left subtree ^un^ to replace the *un*::
0194
0195
0196                              (un)
0197
0198               un                             *un*
0199                                            ^
0200       un              un             ^un^            [un]
0201
0202   zs      cy      zs      co      cy      zs     [cy]    [cy]
0203
0204
0205 How to do that exactly ?
0206
0207 * get parent of *un* -> (un)
0208 * change right child of (un) from *un* to ^un^
0209
0210 * j/PMTSim/ZSolid.cc
0211 * BUT there is no G4BooleanSolid::SetConstituentSolid so ZSolid::SetRight ZSolid::SetLeft using placement new
0212
0213
0214 When the right subtree of root is all excluded need to
0215 do the same in principal : pullup the left subtree to replace root *un*.
0216 In practice this is simpler because can just change the root pointer::
0217
0218
0219                              *un*
0220
0221              ^un^                            [un]
0222
0223       un              un             [un]            [un]
0224
0225   zs      cy      zs      co     [cy]    [zs]    [cy]    [cy]
0226
0227
0228
0229 How to detect can just shift the root pointer ?
0230
0231
0232 Hmm if exclusions were scattered all over would be easier to
0233 just rebuild.
0234
0235 **/
0236
0237 struct tree
0238 {
0239     static const int ORDER1 ;
0240     static const int ORDER2 ;
0241
0242     static int NumNode(int height);
0243     static tree* make_complete(int height);
0244     static tree* make_unbalanced(int numprim);
0245     static nd* build_r(int h, int& count );
0246     static void initvalue_r( nd* n, int order );
0247
0248     bool verbose ;
0249     nd* root ;
0250     int width ;
0251     int height ;
0252     int xscale ;
0253     int yscale ;
0254
0255     scanvas* canvas ;
0256     int value_order ;
0257
0258     std::vector<nd*> inorder ;
0259     std::vector<nd*> rinorder ;
0260     std::vector<nd*> preorder ;
0261     std::vector<nd*> rpreorder ;
0262     std::vector<nd*> postorder ;
0263     std::vector<nd*> rpostorder ;
0264
0265     std::vector<nd*> crux ;
0266     std::map<nd*, nd*> parentmap ;
0267
0268     tree( nd* root );
0269
0270     void instrument();
0271     void initvalue(int order) ;
0272
0273     void inorder_r( nd* n );
0274     void rinorder_r( nd* n );
0275     void preorder_r( nd* n );
0276     void rpreorder_r( nd* n );
0277     void postorder_r( nd* n );
0278     void rpostorder_r( nd* n );
0279
0280     void parent_r( nd* n, int depth );
0281     void depth_r( nd* n, int depth );
0282     void clear_mkr();
0283     void clear_mkr_r( nd* n );
0284
0285     int num_prim() const ;
0286     int num_prim_r( nd* n ) const ;
0287
0288     int num_node(int qcls) const ;
0289     static int num_node_r( nd* n, int qcls);
0290     int num_node() const ;
0291     static int num_node_r( nd* n) ;
0292
0293     const char* desc() const ;
0294
0295     nd* parent( nd* n ) const ;
0296
0297     void dump(const char* msg) const ;
0298     void dump_r( nd* n ) const ;
0299
0300     int maxdepth_r(nd* n, int depth) const ;
0301     int maxdepth() const  ;
0302
0303     void draw(const char* msg=nullptr, int meta=-1);
0304     void draw_r( nd* n );
0305
0306     void apply_cut(int cut);
0307
0308     void classify( int cut );
0309     int classify_r( nd* n, int cut );
0310
0311     void prune( bool act, int pass );
0312     void prune_crux( nd* n, bool act, int pass );
0313 };
0314
0315
0316 int tree::NumNode(int height){ return (1 << (height+1)) - 1  ; } // static
0317
0318
0319 nd* tree::build_r(int h, int& count)  // static
0320 {
0321     nd* l = h > 0 ? build_r( h-1, count) : nullptr ;
0322     nd* r = h > 0 ? build_r( h-1, count ) : nullptr ;
0323     return new nd( count++, l, r) ;
0324 }
0325
0326 tree* tree::make_complete(int height) // static
0327 {
0328     int count = 0 ;
0329     nd* root = build_r(height, count );
0330     tree* t = new tree(root);
0331     return t ;
0332 }
0333
0334 tree* tree::make_unbalanced(int numprim) // static
0335 {
0336     nd* root = new nd(0) ;
0337     for(unsigned i=1 ; i < numprim ; i++)
0338     {
0339         nd* right = new nd(i) ;
0340         root = new nd(i, root, right) ;
0341     }
0342     tree* t = new tree(root);
0343     return t ;
0344 }
0345
0346
0347
0348 tree::tree(nd* root_)
0349     :
0350     verbose(getenv("VERBOSE")!=nullptr),
0351     root(root_),
0352     width(num_node_r(root)),
0353     height(maxdepth_r(root,0)),
0354     xscale(5),
0355     yscale(4),
0356     canvas(new scanvas(width,height+1,xscale,yscale)),  // +1 as a height 0 tree is still 1 node
0357     value_order(-1)
0358 {
0359     instrument();
0360     initvalue_r(root, PRE);   // must be after instrument, as uses n.pre
0361 }
0362
0363 void tree::instrument()
0364 {
0365     if(!root) return ;
0366     clear_mkr();
0367
0368
0369     inorder.clear();
0370     inorder_r(root);
0371
0372     rinorder.clear();
0373     rinorder_r(root);
0374
0375     preorder.clear();
0376     preorder_r(root);
0377
0378     rpreorder.clear();
0379     rpreorder_r(root);
0380
0381     postorder.clear();
0382     postorder_r(root);
0383
0384     rpostorder.clear();
0385     rpostorder_r(root);
0386
0387
0388     parentmap.clear();
0389     parentmap[root] = nullptr ;
0390     parent_r(root, 0 );
0391
0392     depth_r(root, 0);
0393
0394     width = num_node_r(root) ;
0395     height = maxdepth_r(root,0) ;
0396     canvas->resize(width, height+1);   // +1 as a height 0 tree is still 1 node
0397 }
0398
0399
0400 /**
0401 tree::initvalue
0402 ----------------
0403
0404 Invokes postorder recursive traverse that sets
0405 nd::value of all nodes in the tree to the result of nd::index
0406 for the order type.
0407
0408 **/
0409
0410 void tree::initvalue(int order_ )
0411 {
0412    value_order = order_ ;
0413    initvalue_r(root, value_order);
0414 }
0415 void tree::initvalue_r( nd* n, int order ) // static
0416 {
0417     if( n == nullptr ) return ;
0418     initvalue_r( n->left, order );
0419     initvalue_r( n->right, order );
0420     n->value = n->index(order);
0421 }
0422
0423 int tree::maxdepth_r(nd* n, int depth) const
0424 {
0425     return n->left && n->right ? std::max( maxdepth_r( n->left, depth+1), maxdepth_r(n->right, depth+1)) : depth ;
0426 }
0427 int tree::maxdepth() const
0428 {
0429     return maxdepth_r( root, 0 );
0430 }
0431
0432 int tree::num_prim_r(nd* n) const
0433 {
0434     if(!n) return 0 ;
0435     return ( n->left && n->right ) ? num_prim_r( n->left) + num_prim_r(n->right) : 1 ;
0436 }
0437 int tree::num_prim() const
0438 {
0439     return num_prim_r(root);
0440 }
0441 int tree::num_node() const
0442 {
0443     return num_node_r(root) ;
0444 }
0445 int tree::num_node_r(nd* n) // static
0446 {
0447     int num = n ? 1 : 0 ;
0448     if( n && n->left && n->right )
0449     {
0450         num += num_node_r( n->left );
0451         num += num_node_r( n->right );
0452     }
0453     return num ;
0454 }
0455 int tree::num_node_r(nd* n, int qcls) // static
0456 {
0457     int num = ( n && n->cls == qcls ) ? 1 : 0 ;
0458     if( n && n->left && n->right )
0459     {
0460         num += num_node_r( n->left,  qcls );
0461         num += num_node_r( n->right, qcls );
0462     }
0463     return num ;
0464 }
0465 int tree::num_node(int cls) const
0466 {
0467     return num_node_r(root, cls);
0468 }
0469
0470 const char* tree::desc() const
0471 {
0472     char tmp[100];
0473     int num_undefined = num_node(UNDEFINED);
0474     int num_exclude   = num_node(EXCLUDE);
0475     int num_include   = num_node(INCLUDE);
0476     int num_mixed     = num_node(MIXED);
0477     int num_prim_     = num_prim();
0478
0479     snprintf(tmp, 100, "UN:%d EX:%d IN:%d MX:%d prim:%d",num_undefined, num_exclude, num_include, num_mixed, num_prim_ );
0480     return strdup(tmp);
0481 }
0482
0483 nd* tree::parent( nd* n ) const
0484 {
0485     return parentmap.count(n) == 1 ? parentmap.at(n) : nullptr ;
0486 }
0487
0488 void tree::depth_r( nd* n, int d )
0489 {
0490     if( n == nullptr ) return ;
0491     depth_r( n->left , d+1 );
0492     depth_r( n->right, d+1 );
0493     n->depth = d ;
0494 }
0495
0496 void tree::clear_mkr()
0497 {
0498     clear_mkr_r(root);
0499 }
0500
0501 void tree::clear_mkr_r( nd* n )
0502 {
0503     if( n == nullptr ) return ;
0504     clear_mkr_r( n->left  );
0505     clear_mkr_r( n->right );
0506     n->mkr = '_' ;
0507 }
0508
0509 void tree::parent_r( nd* n, int depth )
0510 {
0511     if( n->is_boolean() )
0512     {
0513         parent_r( n->left, depth+1 );
0514         parent_r( n->right, depth+1 );
0515
0516         parentmap[n->left] = n ;
0517         parentmap[n->right] = n ;
0518     }
0519 }
0520
0521
0522 /**
0523
0524 This is taking too many passes dealing with excluded parents...
0525 In an unbalanced tree, should be able to directly find the new root
0526 avoiding reconnections to excluded parent nodes.
0527
0528 **/
0529
0530 void tree::apply_cut(int cut)
0531 {
0532     if(verbose)
0533     printf("tree::apply_cut %d \n", cut );
0534
0535     unsigned pass = 0 ;
0536     unsigned maxpass = 10 ;
0537
0538     while( root != nullptr && root->cls != INCLUDE && pass < maxpass )
0539     {
0540         classify(cut);   // set n.cls n.mkr
0541         prune(false, pass);
0542
0543         if(verbose)
0544         draw("tree::apply_cut before prune", pass );
0545
0546         prune(true, pass );
0547
0548         classify(cut);
0549         instrument();
0550
0551         if(verbose)
0552         draw("tree::apply_cut after prune and re-classify", pass );
0553
0554         pass++ ;
0555     }
0556
0557     printf("tree::apply_cut pass %d \n", pass);
0558 }
0559
0560
0561 /**
0562 tree::classify
0563 ---------------
0564
0565 1. for all tree nodes sets n.cls according to the cut
0566 2. for crux nodes sets n.mkr and collects nodes into crux vector
0567 3. invokes prune(false) that sets prune n.mkr without proceeding with the prune
0568
0569 **/
0570
0571 void tree::classify( int cut )
0572 {
0573     crux.clear();
0574     classify_r( root, cut );
0575     //printf("crux %lu \n", crux.size() ) ;
0576 }
0577
0578 /**
0579 tree::classify_r
0580 -------------------
0581
0582 NB classification is based on the node value set by initvalue_r
0583 it is not using other node props like pre/in etc..
0584 that get changed by instrument as the tree changes.
0585
0586 bitwise-OR up the tree is not so convenient for
0587 identification of the crucial MIXED nodes where
0588 **/
0589
0590 int tree::classify_r( nd* n, int cut )
0591 {
0592     if(!n) return UNDEFINED ;
0593     n->cls = UNDEFINED ;
0594     if( n->left && n->right )
0595     {
0596         n->cls |= classify_r( n->left , cut ) ;
0597         n->cls |= classify_r( n->right, cut ) ;
0598
0599         if( n->is_crux() )
0600         {
0601             n->mkr = '*' ;
0602             crux.push_back(n) ;
0603
0604             if(verbose)
0605             printf("tree::classify_r set crux %s \n", n->desc() );
0606         }
0607     }
0608     else
0609     {
0610         n->cls = n->value >= cut ? EXCLUDE : INCLUDE ;
0611     }
0612     return n->cls ;
0613 }
0614
0615
0616 /**
0617 tree::prune
0618 ------------
0619
0620 Crux nodes by definition have mixed INCLUDE/EXCLUDE child status.
0621 Tree pruning is done in the context of a crux node, eg 3X below
0622 in a tree of 4 prim::
0623
0624
0625                    1
0626                    I
0627                    P
0628          2           \       3
0629          I            \      X
0630                        \
0631     4         5         6          7
0632     I         I         I          E
0633
0634
0635 Gets pruned to a tree of 3 prim::
0636
0637                    1
0638                    I
0639
0640          2                   6
0641          I                   I
0642
0643     4         5
0644     I         I
0645
0646 **/
0647
0648 void tree::prune(bool act, int pass)
0649 {
0650     int num_include = num_node(INCLUDE) ;
0651
0652     if(verbose)
0653     printf("tree::prune num_include %d \n", num_include);
0654
0655     if( num_include == 0)
0656     {
0657         if(verbose)
0658         printf("tree::prune find zero remaining nodes : num_include %d, will set root to nullptr \n", num_include);
0659
0660         if(act)
0661         {
0662             if(verbose)
0663             printf("tree::prune setting root to nullptr \n");
0664
0665             root = nullptr ;
0666         }
0667     }
0668
0669     if(crux.size() == 0 ) return ;
0670     assert(crux.size() == 1) ;  // more than one crux node not expected
0671
0672     nd* x = crux[0] ;
0673     prune_crux(x, act, pass);
0674 }
0675
0676 /**
0677 tree::prune_crux
0678 ----------------------
0679
0680 For *act:false* no tree surgery actions are taken, this is convenient for
0681 seeing the classification of the tree immediately prior to taking action.
0682
0683 Mechanics of non-root prune:
0684
0685 * find parent of crux node (if no parent it is root so see below)
0686 * find left/right child status of crux node
0687 * change the child slot occupied by the crux node in its parent
0688   with the surviving child node or subtree
0689
0690 Mechanics of root prune:
0691
0692 * find surviving side of the crux and promote it to root
0693
0694 ISSUE : are ignoring the exclude status of parent causing
0695 many pointless passes before get to all include
0696
0697 Following tree changes need to update tree instrumentation.
0698
0699
0700
0701
0702                 p
0703                  .
0704           o       .    x
0705                    .
0706       o       o     I      E
0707                     s
0708
0709
0710 **/
0711
0712 void tree::prune_crux( nd* x, bool act, int pass )
0713 {
0714     assert( x && x->is_crux() );
0715     bool cut_left = x->is_cut_left() ;
0716     bool cut_right = x->is_cut_right() ;
0717     assert( cut_left ^ cut_right );  // XOR definition of crux node : both cannot be cut
0718
0719     nd* survivor = cut_right ? x->left : x->right ;
0720     assert( survivor );
0721     survivor->mkr = 'S' ;
0722     nd* p = parent(x);
0723
0724     if( p->cls != INCLUDE )
0725     {
0726         printf("tree::prune_crux act:%d pass:%d parent disqualified as not INCLUDE : handle as root(of the new tree) prune \n", act, pass);
0727         p = nullptr ;
0728     }
0729
0730     if( p != nullptr )   // non-root prune
0731     {
0732         p->mkr = 'P' ;
0733
0734         if( x == p->left )
0735         {
0736             if(act)
0737             {
0738                 if(verbose)
0739                 printf("tree::prune_crux act:%d pass:%d setting p->left %s to survivor %s \n", act, pass, p->left->desc(), survivor->desc() );
0740                 p->left = survivor ;
0741             }
0742         }
0743         else if( x == p->right )
0744         {
0745             if(act)
0746             {
0747                 if(verbose)
0748                 printf("tree::prune_crux act:%d pass:%d setting p->right %s to survivor %s \n", act, pass, p->right->desc(), survivor->desc() );
0749                 p->right = survivor ;
0750             }
0751         }
0752     }
0753     else           // root prune
0754     {
0755         if( act )
0756         {
0757             if(verbose)
0758             printf("tree::prune_crux act:%d pass:%d changing root to survivor\n", act, pass);
0759             root = survivor ;
0760         }
0761     }
0762     if(act)
0763     {
0764         instrument();
0765     }
0766 }
0767
0768
0769 void tree::inorder_r( nd* n )
0770 {
0771     if( n == nullptr ) return ;
0772
0773     inorder_r(n->left) ;
0774
0775     n->in = inorder.size() ; inorder.push_back(n);
0776
0777     inorder_r(n->right) ;
0778 }
0779 void tree::rinorder_r( nd* n )
0780 {
0781     if( n == nullptr ) return ;
0782
0783     rinorder_r(n->right) ;
0784
0785     n->rin = rinorder.size() ; rinorder.push_back(n);
0786
0787     rinorder_r(n->left) ;
0788 }
0789
0790
0791 void tree::preorder_r( nd* n )
0792 {
0793     if( n == nullptr ) return ;
0794     n->pre = preorder.size() ; preorder.push_back(n);
0795
0796     preorder_r(n->left) ;
0797     preorder_r(n->right) ;
0798 }
0799 void tree::rpreorder_r( nd* n )
0800 {
0801     if( n == nullptr ) return ;
0802     n->rpre = rpreorder.size() ; rpreorder.push_back(n);
0803
0804     rpreorder_r(n->right) ;
0805     rpreorder_r(n->left) ;
0806 }
0807
0808
0809 void tree::postorder_r( nd* n )
0810 {
0811     if( n == nullptr ) return ;
0812
0813     postorder_r(n->left) ;
0814     postorder_r(n->right) ;
0815
0816     n->post = postorder.size() ; postorder.push_back(n);
0817 }
0818 void tree::rpostorder_r( nd* n )
0819 {
0820     if( n == nullptr ) return ;
0821
0822     rpostorder_r(n->right) ;
0823     rpostorder_r(n->left) ;
0824
0825     n->rpost = rpostorder.size() ; rpostorder.push_back(n);
0826 }
0827
0828 void tree::dump( const char* msg ) const
0829 {
0830     printf("%s\n",msg);
0831     dump_r(root);
0832 }
0833
0834 void tree::dump_r( nd* n ) const
0835 {
0836     if( n == nullptr ) return ;
0837     dump_r( n->left );
0838     dump_r( n->right );
0839     printf(" value %2d depth %2d mkr %c cls %c\n", n->value, n->depth, n->mkr, pcls(n->cls) ) ;
0840 }
0841
0842
0843 const int tree::ORDER1 = RPRE ;
0844 const int tree::ORDER2 = POST ;
0845
0846 void tree::draw(const char* msg, int meta)
0847 {
0848     if(!root) return ;
0849     if(msg) printf("%s [%d] \n", msg, meta );
0850     canvas->clear();
0851
0852     printf("vorder : %s \n", u::OrderName(value_order) );
0853     printf("order1 : %s \n", u::OrderName(ORDER1) );
0854     //printf("order2 : %s \n", u::OrderName(ORDER2) );
0855
0856     draw_r(root);
0857     canvas->print();
0858 }
0859
0860 void tree::draw_r( nd* n )
0861 {
0862     if( n == nullptr ) return ;
0863     draw_r( n->left );
0864     draw_r( n->right );
0865
0866     int x = n->in ;
0867     int y = n->depth  ;
0868
0869     canvas->draw(     x, y, 0,0, n->value );
0870     canvas->draw(     x, y, 0,1, n->index(ORDER1));
0871     //canvas->draw(     x, y, 0,2, n->index(ORDER2));
0872     canvas->drawch(   x, y, 0,2, pcls(n->cls) );
0873     canvas->drawch(   x, y, 0,3, n->mkr );
0874 }
0875
0876