sysrap/tests/tree_test.cc

0001 // ./tree_test.sh
0002
0003 #include <cassert>
0004 #include <cstring>
0005 #include <cstdlib>
0006 #include <cstdio>
0007 #include <vector>
0008 #include <map>
0009
0010 #include "tree.h"
0011
0012 void test_flip( nd* n )
0013 {
0014     n->value = -n->value ;  // easy way to flip the nodes value
0015 }
0016
0017 void test_placement_new( nd* n )
0018 {
0019     nd* p = new (n) nd( -n->value, n->left, n->right) ;
0020     assert( p == n );
0021     // placement new creation of new object to replace the nd at same location
0022 }
0023
0024
0025 void test_cuts(int height0)
0026 {
0027     int count0 = tree::NumNode(height0) ;
0028
0029     for( int cut=count0 ; cut > 0 ; cut-- )
0030     {
0031         tree* t = tree::make_complete(height0) ;
0032         t->initvalue(PRE);
0033
0034         int count0 = t->num_node() ;
0035         t->apply_cut(cut);
0036         printf("count0 %d cut %d t.desc %s\n", count0, cut, t->desc() );
0037         t->draw();
0038     }
0039 }
0040
0041 void test_unbalanced(int numprim0, int order, const char* msg=nullptr)
0042 {
0043     tree* t = tree::make_unbalanced(numprim0) ;
0044     t->initvalue(order);
0045     t->draw(msg);
0046 }
0047 void test_unbalanced(int numprim)
0048 {
0049     test_unbalanced(numprim, POST);
0050     test_unbalanced(numprim, RPRE,  "RPRE is opposite order to POST" );
0051
0052     test_unbalanced(numprim, PRE);
0053     test_unbalanced(numprim, RPOST, "RPOST is opposite order to PRE");
0054
0055     test_unbalanced(numprim, IN);
0056     test_unbalanced(numprim, RIN,   "RIN is opposite order to IN");
0057 }
0058
0059 void test_complete(int numprim0, int order, const char* msg=nullptr)
0060 {
0061     tree* t = tree::make_complete(numprim0) ;
0062     t->initvalue(order);
0063     t->draw(msg);
0064 }
0065 void test_complete(int numprim)
0066 {
0067     test_complete(numprim, POST);
0068     test_complete(numprim, RPRE,  "RPRE is opposite order to POST" );
0069
0070     test_complete(numprim, PRE);
0071     test_complete(numprim, RPOST, "RPOST is opposite order to PRE");
0072
0073     test_complete(numprim, IN);
0074     test_complete(numprim, RIN,   "RIN is opposite order to IN");
0075 }
0076
0077
0078 void test_cuts_unbalanced(int numprim0)
0079 {
0080     for(int i=0 ; i < 20 ; i++)
0081     {
0082         tree* t = tree::make_unbalanced(numprim0) ;
0083         t->initvalue(POST);
0084         //t->draw();
0085
0086         int count0 = t->num_node() ;
0087         int cut = count0 - i ;
0088         if( cut < 1 ) break ;
0089         t->apply_cut(cut);
0090         printf("count0 %d cut %d t.desc %s\n", count0, cut, t->desc() );
0091
0092         t->draw();
0093     }
0094 }
0095
0096 void test_cut_unbalanced(int numprim0, int cut)
0097 {
0098     printf("test_cut_unbalanced numprim0 %d cut %d \n", numprim0, cut );
0099
0100     tree* t = tree::make_unbalanced(numprim0) ;
0101     t->initvalue(POST);
0102     t->draw("before cut");
0103     t->apply_cut(cut);
0104     t->draw("after cut");
0105 }
0106
0107 void test_no_remaining_nodes()
0108 {
0109     int height0 = 3 ;
0110     tree* t = tree::make_complete(height0) ;
0111     t->initvalue(PRE);
0112     t->draw();
0113     t->verbose = true ;
0114
0115     printf("t.desc %s \n", t->desc() );
0116
0117     int count0 = t->num_node() ;
0118     int cut = 3 ;
0119     t->apply_cut(cut);
0120     printf("count0 %d cut %d t.desc %s\n", count0, cut, t->desc() );
0121     t->draw();
0122 }
0123
0124 void test_unbalanced_cut()
0125 {
0126     tree* t = tree::make_unbalanced(8) ;
0127     t->initvalue(POST);
0128     t->draw("before cut");
0129
0130     t->apply_cut(8);
0131     t->draw("after cut");
0132 }
0133
0134 void test_complete_initvalue()
0135 {
0136     tree* t = tree::make_complete(4) ;
0137     t->initvalue(POST);
0138     t->draw();
0139 }
0140
0141
0142
0143 int main(int argc, char**argv )
0144 {
0145     /*
0146     test_unbalanced(8);
0147     test_complete(4);
0148
0149     test_cuts(4);
0150     test_cuts(3);
0151     test_no_remaining_nodes();
0152
0153     test_cut_unbalanced(8, 8);
0154     test_cuts_unbalanced(8);
0155
0156     test_unbalanced_cut();
0157     test_complete_initvalue();
0158     */
0159
0160     test_unbalanced(8);
0161
0162
0163     return 0 ;
0164 }