eic-opticks/sysrap/sndtree.h

0001 #pragma once
0002 /**
0003 sndtree.h
0004 ===========
0005
0006 Used from snd::UnionTree which is for example used by U4Polycone
0007 This brings some of the functionality of the old NTreeBuilder for use with snd node trees
0008
0009 This is a workaround combining the inherently persistable but not very flexible
0010 snd.hh with the more flexible pointer based sn.h
0011
0012 Once sn.h persisting using s_pool.h s_csg.h becomes fully featured
0013 this sndtree.h SHOULD BE REMOVED.
0014
0015 AS ITS AN UNHEALTHY MIX OF TWO NODE TYPES THAT ARE DOING
0016 ESSENTIALLY THE SAME THING
0017
0018 **/
0019
0020 #include <cassert>
0021 #include <vector>
0022 #include "snd.hh"
0023 #include "sn.h"
0024
0025 struct sndtree
0026 {
0027     static int CommonTree_PlaceLeaves( const std::vector<int>& leaves, int op ) ;
0028     static int Build_r(sn* n, int& num_leaves_placed, const std::vector<int>& leaves, int d );
0029 };
0030
0031
0032 /**
0033 sndtree::CommonTree_PlaceLeaves
0034 ---------------------------------
0035
0036 The *leaves* are snd indices, so can snd::Get(idx) to access the snd
0037
0038 Creates *snd* binary tree sufficient to hold the
0039 leaves and places the leaf references into the tree.
0040
0041 Internally this uses the pointer based *sn* tree as a guide,
0042 assisting with the dirty work of creating the complete binary tree
0043 and then pruning it down to hold the leaves provided.
0044 The *sn* nodes are used for this as they can easily be deleted (or leaked)
0045 unlike the *snd* nodes.
0046
0047 Constructing the *snd* tree requires calling snd::Boolean with 3 int args
0048 in a postorder traverse to cover children before parents.
0049 The snd::Boolean call does the n-ary setup for the 2-ary boolean nodes.
0050
0051 **/
0052
0053 inline int sndtree::CommonTree_PlaceLeaves( const std::vector<int>& leaves, int op ) // static
0054 {
0055     int num_leaves = leaves.size() ;
0056     std::vector<int> leaftypes ;
0057     snd::GetTypes(leaftypes, leaves);
0058
0059     sn* n = sn::CommonOperatorTypeTree( leaftypes, op );
0060
0061     int num_leaves_placed = 0 ;
0062     int root = Build_r(n, num_leaves_placed, leaves, 0 );
0063
0064     bool expect_leaves = num_leaves_placed == num_leaves ;
0065     if(!expect_leaves) std::cerr << "sndtree::CommonTree_PlaceLeaves UNEXPECTED LEAVES " << std::endl;
0066     assert( expect_leaves );
0067
0068     delete n ;
0069
0070     snd* r = snd::Get_(root);
0071     r->sibdex = 0 ;
0072
0073     return root ;
0074 }
0075
0076
0077 /**
0078 sndtree::Build_r
0079 ------------------
0080
0081 Builds snd tree based on the "skeleton" provided by the sn tree.
0082
0083 Postorder visit after recursive call : so children reached before parents
0084
0085 **/
0086
0087 inline int sndtree::Build_r(sn* n, int& num_leaves_placed, const std::vector<int>& leaves, int d )
0088 {
0089     int N = -1 ;
0090     if( n->is_operator() )
0091     {
0092         int op = n->typecode ;
0093         int nc = n->num_child();
0094         bool nc_expect = nc == 2 ;
0095         if(!nc_expect) std::cerr << "sndtree::Build_r nc_expect " << std::endl ;
0096         assert( nc_expect );
0097         sn* l = n->get_child(0);
0098         sn* r = n->get_child(1);
0099         int L = Build_r(l, num_leaves_placed, leaves, d+1) ;
0100         int R = Build_r(r, num_leaves_placed, leaves, d+1) ;
0101         N = snd::Boolean( op, L, R );
0102     }
0103     else
0104     {
0105         N = leaves[num_leaves_placed] ;
0106         num_leaves_placed += 1 ;
0107     }
0108     return N ;
0109 }
0110
0111