DENDRO: /net/www/csela/dendro/releases/Dendro/src/test/testUtils.C Source File

00001 
00007 #include "TreeNode.h"
00008 #include "testUtils.h"
00009 #include "parUtils.h"
00010 #include "seqUtils.h"
00011 #include <cstring>
00012 
00013 namespace ot {
00014   namespace test {
00015 
00016     //Assumes nodes is sorted and unique
00017     bool isLinear(const std::vector<ot::TreeNode > &nodes) {
00018       for(int i=0; i < (nodes.size() -1); i++) {
00019         if(nodes[i].isAncestor(nodes[i+1])){
00020           return false;
00021         }
00022       }
00023       return true;       
00024     }
00025 
00026 //Assumes nodes is sorted and unique.
00027 bool isComplete(const std::vector<ot::TreeNode >& nodes) {
00028   assert(!nodes.empty());
00029   unsigned int dim = nodes[0].getDim();
00030   unsigned int maxDepth = nodes[0].getMaxDepth();
00031 
00032   std::vector<ot::TreeNode > tmp1 = nodes;
00033   for (unsigned int lev = maxDepth; lev > 0; lev--) {
00034     //1. Select all octants at lev
00035     std::vector<ot::TreeNode > tmp2;
00036     for(unsigned int i=0; i < tmp1.size(); i++) {
00037       if(tmp1[i].getLevel() == lev) {
00038         tmp2.push_back(tmp1[i]);
00039       }
00040     }//end for i
00041 
00042     if( (tmp2.size()%8) != 0) {
00043       return false;
00044     }
00045 
00046     std::vector<ot::TreeNode > tmp3;
00047     unsigned int tmp2Cnt = 0;
00048     while(tmp2Cnt < tmp2.size()) {
00049       ot::TreeNode currParent = tmp2[tmp2Cnt].getParent();
00050       for(int i = 1; i < (1 << dim); i++) {
00051         assert((tmp2Cnt + i) < tmp2.size()); 
00052         if(tmp2[tmp2Cnt + i].getParent() != currParent) {
00053           return false; 
00054         }
00055       }
00056       tmp3.push_back(currParent);
00057       tmp2Cnt +=8;
00058     }//end while
00059 
00060     tmp2.clear();
00061 
00062     for(unsigned int i=0; i < tmp1.size(); i++) {
00063       if(tmp1[i].getLevel() != lev) {
00064         tmp3.push_back(tmp1[i]);
00065       }
00066     }//end for i
00067 
00068     std::sort(tmp3.begin(),tmp3.end());
00069     tmp1 = tmp3;
00070     tmp3.clear();
00071 
00072   }//end for lev
00073   return true;
00074 }
00075 
00076 bool isBalanced(unsigned int dim, unsigned int maxDepth, char*failFileName,
00077     const std::vector<ot::TreeNode > &nodes, bool incCorn, unsigned int maxLevDiff) {
00078   TreeNode root (dim, maxDepth);
00079   return        isBalancedInternal(dim,maxDepth,failFileName,nodes,root, incCorn, maxLevDiff);
00080 }//end function
00081 
00082 bool isBalancedInternal(unsigned int dim, unsigned int maxDepth,char*failFileName,
00083     const  std::vector<ot::TreeNode > & nodes, ot::TreeNode holder,
00084     bool incCorn, unsigned int maxLevDiff) {
00085   bool yesBalanced = true;
00086   std::vector<TreeNode> failedCorners;
00087   std::vector<TreeNode> failedEdges;
00088   std::vector<TreeNode> failedFaces;
00089   TreeNode root (dim, maxDepth);
00090   unsigned int retIdx;
00091   double nxz = (double) nodes.size();
00092   for (unsigned int i=0; i<nodes.size(); i++) {
00093     /*
00094        if (!(i%100)) {
00095        printf("%4.2f\r", 100.0*((double)i)/nxz);
00096        }
00097        */
00098 
00099     // cout<<RED<<"R"<<NRM<<endl;
00100     {
00101       TreeNode it = nodes[i].getRight();
00102 
00103       if(holder.isAncestor(it)){
00104 
00105         bool found = seq::maxLowerBound(nodes,it.getDFD(), retIdx,NULL,NULL);
00106         if(found) {
00107           unsigned int retLev = nodes[retIdx].getLevel();
00108           unsigned int myLev = nodes[i].getLevel();                                     
00109           if( (it.getAnchor() != nodes[retIdx].getAnchor()) && (!(nodes[retIdx].isAncestor(it))) ) {
00110             found = false;
00111           }else if( (retLev < myLev) && ( (myLev - retLev) > maxLevDiff ) ) {
00112             //Found a very big Neighbour
00113             found = false;
00114           }                                             
00115         }
00116         if(!found) {
00117           yesBalanced = false;
00118           std::cout<<nodes[i]<<": (R) ->"<<nodes[retIdx]<<std::endl;
00119           failedFaces.push_back(nodes[i]);                                      
00120           break;
00121         }
00122       }
00123 
00124     }
00125 
00126     // cout<<RED<<"L"<<NRM<<endl;
00127     {
00128       TreeNode it = nodes[i].getLeft();
00129 
00130       if(holder.isAncestor(it)){
00131 
00132         bool found = seq::maxLowerBound(nodes,it.getDFD(), retIdx,NULL,NULL);
00133         if(found) {
00134           unsigned int retLev = nodes[retIdx].getLevel();
00135           unsigned int myLev = nodes[i].getLevel();                                     
00136           if( (it.getAnchor() != nodes[retIdx].getAnchor()) && (!(nodes[retIdx].isAncestor(it))) ) {
00137             found = false;
00138           }else if( (retLev < myLev) && ( (myLev - retLev) > maxLevDiff ) ) {
00139             //Found a very big Neighbour
00140             found = false;
00141           }                                             
00142         }
00143         if(!found) {
00144           yesBalanced = false;
00145           std::cout<<nodes[i]<<": (L) ->"<<nodes[retIdx]<<std::endl;
00146           failedFaces.push_back(nodes[i]);                                      
00147           break;
00148         }
00149       }
00150 
00151     }
00152 
00153 
00154     // cout<<RED<<"T"<<NRM<<endl;
00155     {
00156       TreeNode it = nodes[i].getTop();
00157 
00158       if(holder.isAncestor(it)){
00159 
00160         bool found = seq::maxLowerBound(nodes,it.getDFD(), retIdx,NULL,NULL);
00161         if(found) {
00162           unsigned int retLev = nodes[retIdx].getLevel();
00163           unsigned int myLev = nodes[i].getLevel();                                     
00164           if( (it.getAnchor() != nodes[retIdx].getAnchor()) && (!(nodes[retIdx].isAncestor(it))) ) {
00165             found = false;
00166           }else if( (retLev < myLev) && ( (myLev - retLev) > maxLevDiff ) ) {
00167             //Found a very big Neighbour
00168             found = false;
00169           }                                             
00170         }
00171         if(!found) {
00172           yesBalanced = false;
00173           std::cout<<nodes[i]<<": (T) ->"<<nodes[retIdx]<<std::endl;
00174           failedFaces.push_back(nodes[i]);                                      
00175           break;
00176         }
00177       }
00178     }
00179 
00180     // cout<<RED<<"Bo"<<NRM<<endl;
00181     {
00182       TreeNode it = nodes[i].getBottom();
00183 
00184 
00185       if(holder.isAncestor(it)){
00186 
00187         bool found = seq::maxLowerBound(nodes,it.getDFD(), retIdx,NULL,NULL);
00188         if(found) {
00189           unsigned int retLev = nodes[retIdx].getLevel();
00190           unsigned int myLev = nodes[i].getLevel();                                     
00191           if( (it.getAnchor() != nodes[retIdx].getAnchor()) && (!(nodes[retIdx].isAncestor(it))) ) {
00192             found = false;
00193           }else if( (retLev < myLev) && ( (myLev - retLev) > maxLevDiff ) ) {
00194             //Found a very big Neighbour
00195             found = false;
00196           }                                             
00197         }
00198         if(!found) {
00199           yesBalanced = false;
00200           std::cout<<nodes[i]<<": (Bo) ->"<<nodes[retIdx]<<std::endl;
00201           failedFaces.push_back(nodes[i]);                                      
00202           break;
00203         }
00204       }
00205 
00206     }
00207 
00208     // cout<<RED<<"F"<<NRM<<endl;
00209     {
00210       TreeNode it = nodes[i].getFront();
00211 
00212 
00213       if(holder.isAncestor(it)){
00214 
00215         bool found = seq::maxLowerBound(nodes,it.getDFD(), retIdx,NULL,NULL);
00216         if(found) {
00217           unsigned int retLev = nodes[retIdx].getLevel();
00218           unsigned int myLev = nodes[i].getLevel();                                     
00219           if( (it.getAnchor() != nodes[retIdx].getAnchor()) && (!(nodes[retIdx].isAncestor(it))) ) {
00220             found = false;
00221           }else if( (retLev < myLev) && ( (myLev - retLev) > maxLevDiff ) ) {
00222             //Found a very big Neighbour
00223             found = false;
00224           }                                             
00225         }
00226         if(!found) {
00227           yesBalanced = false;
00228           std::cout<<nodes[i]<<": (F) ->"<<nodes[retIdx]<<std::endl;
00229           failedFaces.push_back(nodes[i]);                                      
00230           break;
00231         }
00232       }
00233 
00234     }
00235 
00236     // cout<<RED<<"Bk"<<NRM<<endl;
00237     {
00238       TreeNode it = nodes[i].getBack();
00239 
00240 
00241       if(holder.isAncestor(it)){
00242 
00243         bool found = seq::maxLowerBound(nodes,it.getDFD(), retIdx,NULL,NULL);
00244         if(found) {
00245           unsigned int retLev = nodes[retIdx].getLevel();
00246           unsigned int myLev = nodes[i].getLevel();                                     
00247           if( (it.getAnchor() != nodes[retIdx].getAnchor()) && (!(nodes[retIdx].isAncestor(it))) ) {
00248             found = false;
00249           }else if( (retLev < myLev) && ( (myLev - retLev) > maxLevDiff ) ) {
00250             //Found a very big Neighbour
00251             found = false;
00252           }                                             
00253         }
00254         if(!found) {
00255           yesBalanced = false;
00256           std::cout<<nodes[i]<<": (Bk) ->"<<nodes[retIdx]<<std::endl;
00257           failedFaces.push_back(nodes[i]);                                      
00258           break;
00259         }
00260       }
00261 
00262     }
00263 
00264     if(dim == 3 || incCorn) {
00265       // cout<<RED<<"TR"<<NRM<<endl;
00266       {
00267         TreeNode it = nodes[i].getTopRight();
00268 
00269 
00270         if(holder.isAncestor(it)){
00271 
00272           bool found = seq::maxLowerBound(nodes,it.getDFD(), retIdx,NULL,NULL);
00273           if(found) {
00274             unsigned int retLev = nodes[retIdx].getLevel();
00275             unsigned int myLev = nodes[i].getLevel();                                   
00276             if( (it.getAnchor() != nodes[retIdx].getAnchor()) && (!(nodes[retIdx].isAncestor(it))) ) {
00277               found = false;
00278             }else if( (retLev < myLev) && ( (myLev - retLev) > maxLevDiff ) ) {
00279               //Found a very big Neighbour
00280               found = false;
00281             }                                           
00282           }
00283           if(!found) {
00284             yesBalanced = false;
00285             std::cout<<nodes[i]<<": (TR) ->"<<nodes[retIdx]<<std::endl;
00286             failedEdges.push_back(nodes[i]);                                    
00287             break;
00288           }
00289         }
00290 
00291       }
00292 
00293       // cout<<RED<<"TL"<<NRM<<endl;
00294       {
00295         TreeNode it = nodes[i].getTopLeft();
00296 
00297 
00298         if(holder.isAncestor(it)){
00299 
00300           bool found = seq::maxLowerBound(nodes,it.getDFD(), retIdx,NULL,NULL);
00301           if(found) {
00302             unsigned int retLev = nodes[retIdx].getLevel();
00303             unsigned int myLev = nodes[i].getLevel();                                   
00304             if( (it.getAnchor() != nodes[retIdx].getAnchor()) && (!(nodes[retIdx].isAncestor(it))) ) {
00305               found = false;
00306             }else if( (retLev < myLev) && ( (myLev - retLev) > maxLevDiff ) ) {
00307               //Found a very big Neighbour
00308               found = false;
00309             }                                           
00310           }
00311           if(!found) {
00312             yesBalanced = false;
00313             std::cout<<nodes[i]<<": (TL) ->"<<nodes[retIdx]<<std::endl;
00314             failedEdges.push_back(nodes[i]);                                    
00315             break;
00316           }
00317         }
00318 
00319       }
00320 
00321       // cout<<RED<<"BoL"<<NRM<<endl;
00322       {
00323         TreeNode it = nodes[i].getBottomLeft();
00324 
00325 
00326         if(holder.isAncestor(it)){
00327 
00328           bool found = seq::maxLowerBound(nodes,it.getDFD(), retIdx,NULL,NULL);
00329           if(found) {
00330             unsigned int retLev = nodes[retIdx].getLevel();
00331             unsigned int myLev = nodes[i].getLevel();                                   
00332             if( (it.getAnchor() != nodes[retIdx].getAnchor()) && (!(nodes[retIdx].isAncestor(it))) ) {
00333               found = false;
00334             }else if( (retLev < myLev) && ( (myLev - retLev) > maxLevDiff ) ) {
00335               //Found a very big Neighbour
00336               found = false;
00337             }                                           
00338           }
00339           if(!found) {
00340             yesBalanced = false;
00341             std::cout<<nodes[i]<<": (BoL) ->"<<nodes[retIdx]<<std::endl;
00342             failedEdges.push_back(nodes[i]);                                    
00343             break;
00344           }
00345         }
00346 
00347       }
00348 
00349       // cout<<RED<<"BoR"<<NRM<<endl;
00350       {
00351         TreeNode it = nodes[i].getBottomRight();
00352 
00353 
00354         if(holder.isAncestor(it)){
00355 
00356           bool found = seq::maxLowerBound(nodes,it.getDFD(), retIdx,NULL,NULL);
00357           if(found) {
00358             unsigned int retLev = nodes[retIdx].getLevel();
00359             unsigned int myLev = nodes[i].getLevel();                                   
00360             if( (it.getAnchor() != nodes[retIdx].getAnchor()) && (!(nodes[retIdx].isAncestor(it))) ) {
00361               found = false;
00362             }else if( (retLev < myLev) && ( (myLev - retLev) > maxLevDiff ) ) {
00363               //Found a very big Neighbour
00364               found = false;
00365             }                                           
00366           }
00367           if(!found) {
00368             yesBalanced = false;
00369             std::cout<<nodes[i]<<": (BoR) ->"<<nodes[retIdx]<<std::endl;
00370             failedEdges.push_back(nodes[i]);                                    
00371             break;
00372           }
00373         }
00374 
00375       }
00376 
00377       // cout<<RED<<"RBk"<<NRM<<endl;
00378       {
00379         TreeNode it = nodes[i].getRightBack();
00380 
00381 
00382         if(holder.isAncestor(it)){
00383 
00384           bool found = seq::maxLowerBound(nodes,it.getDFD(), retIdx,NULL,NULL);
00385           if(found) {
00386             unsigned int retLev = nodes[retIdx].getLevel();
00387             unsigned int myLev = nodes[i].getLevel();                                   
00388             if( (it.getAnchor() != nodes[retIdx].getAnchor()) && (!(nodes[retIdx].isAncestor(it))) ) {
00389               found = false;
00390             }else if( (retLev < myLev) && ( (myLev - retLev) > maxLevDiff ) ) {
00391               //Found a very big Neighbour
00392               found = false;
00393             }                                           
00394           }
00395           if(!found) {
00396             yesBalanced = false;
00397             std::cout<<nodes[i]<<": (RBk) ->"<<nodes[retIdx]<<std::endl;
00398             failedEdges.push_back(nodes[i]);                                    
00399             break;
00400           }
00401         }
00402 
00403       }
00404 
00405       // cout<<RED<<"TBk"<<NRM<<endl;
00406       {
00407         TreeNode it = nodes[i].getTopBack();
00408 
00409 
00410         if(holder.isAncestor(it)){
00411 
00412           bool found = seq::maxLowerBound(nodes,it.getDFD(), retIdx,NULL,NULL);
00413           if(found) {
00414             unsigned int retLev = nodes[retIdx].getLevel();
00415             unsigned int myLev = nodes[i].getLevel();                                   
00416             if( (it.getAnchor() != nodes[retIdx].getAnchor()) && (!(nodes[retIdx].isAncestor(it))) ) {
00417               found = false;
00418             }else if( (retLev < myLev) && ( (myLev - retLev) > maxLevDiff ) ) {
00419               //Found a very big Neighbour
00420               found = false;
00421             }                                           
00422           }
00423           if(!found) {
00424             yesBalanced = false;
00425             std::cout<<nodes[i]<<": (TBk) ->"<<nodes[retIdx]<<std::endl;
00426             failedEdges.push_back(nodes[i]);                                    
00427             break;
00428           }
00429         }
00430 
00431       }
00432 
00433       // cout<<RED<<"LF"<<NRM<<endl;
00434       {
00435         TreeNode it = nodes[i].getLeftFront();
00436 
00437 
00438         if(holder.isAncestor(it)){
00439 
00440           bool found = seq::maxLowerBound(nodes,it.getDFD(), retIdx,NULL,NULL);
00441           if(found) {
00442             unsigned int retLev = nodes[retIdx].getLevel();
00443             unsigned int myLev = nodes[i].getLevel();                                   
00444             if( (it.getAnchor() != nodes[retIdx].getAnchor()) && (!(nodes[retIdx].isAncestor(it))) ) {
00445               found = false;
00446             }else if( (retLev < myLev) && ( (myLev - retLev) > maxLevDiff ) ) {
00447               //Found a very big Neighbour
00448               found = false;
00449             }                                           
00450           }
00451           if(!found) {
00452             yesBalanced = false;
00453             std::cout<<nodes[i]<<": (LF) ->"<<nodes[retIdx]<<std::endl;
00454             failedEdges.push_back(nodes[i]);                                    
00455             break;
00456           }
00457         }
00458 
00459       }
00460 
00461       // cout<<RED<<"LBk"<<NRM<<endl;
00462       {
00463         TreeNode it = nodes[i].getLeftBack();
00464 
00465 
00466         if(holder.isAncestor(it)){
00467 
00468           bool found = seq::maxLowerBound(nodes,it.getDFD(), retIdx,NULL,NULL);
00469           if(found) {
00470             unsigned int retLev = nodes[retIdx].getLevel();
00471             unsigned int myLev = nodes[i].getLevel();                                   
00472             if( (it.getAnchor() != nodes[retIdx].getAnchor()) && (!(nodes[retIdx].isAncestor(it))) ) {
00473               found = false;
00474             }else if( (retLev < myLev) && ( (myLev - retLev) > maxLevDiff ) ) {
00475               //Found a very big Neighbour
00476               found = false;
00477             }                                           
00478           }
00479           if(!found) {
00480             yesBalanced = false;
00481             std::cout<<nodes[i]<<": (LBk) ->"<<nodes[retIdx]<<std::endl;
00482             failedEdges.push_back(nodes[i]);                                    
00483             break;
00484           }
00485         }
00486 
00487       }
00488 
00489       // cout<<RED<<"RF"<<NRM<<endl;
00490       {
00491         TreeNode it = nodes[i].getRightFront();
00492 
00493 
00494         if(holder.isAncestor(it)){
00495 
00496           bool found = seq::maxLowerBound(nodes,it.getDFD(), retIdx,NULL,NULL);
00497           if(found) {
00498             unsigned int retLev = nodes[retIdx].getLevel();
00499             unsigned int myLev = nodes[i].getLevel();                                   
00500             if( (it.getAnchor() != nodes[retIdx].getAnchor()) && (!(nodes[retIdx].isAncestor(it))) ) {
00501               found = false;
00502             }else if( (retLev < myLev) && ( (myLev - retLev) > maxLevDiff ) ) {
00503               //Found a very big Neighbour
00504               found = false;
00505             }                                           
00506           }
00507           if(!found) {
00508             yesBalanced = false;
00509             std::cout<<nodes[i]<<": (RF) ->"<<nodes[retIdx]<<std::endl;
00510             failedEdges.push_back(nodes[i]);                                    
00511             break;
00512           }
00513         }
00514 
00515       }
00516 
00517       // cout<<RED<<"TF"<<NRM<<endl;
00518       {
00519         TreeNode it = nodes[i].getTopFront();
00520 
00521 
00522         if(holder.isAncestor(it)){
00523 
00524           bool found = seq::maxLowerBound(nodes,it.getDFD(), retIdx,NULL,NULL);
00525           if(found) {
00526             unsigned int retLev = nodes[retIdx].getLevel();
00527             unsigned int myLev = nodes[i].getLevel();                                   
00528             if( (it.getAnchor() != nodes[retIdx].getAnchor()) && (!(nodes[retIdx].isAncestor(it))) ) {
00529               found = false;
00530             }else if( (retLev < myLev) && ( (myLev - retLev) > maxLevDiff ) ) {
00531               //Found a very big Neighbour
00532               found = false;
00533             }                                           
00534           }
00535           if(!found) {
00536             yesBalanced = false;
00537             std::cout<<nodes[i]<<": (TF) ->"<<nodes[retIdx]<<std::endl;
00538             failedEdges.push_back(nodes[i]);                                    
00539             break;
00540           }
00541         }
00542 
00543       }
00544 
00545       // cout<<RED<<"BoBk"<<NRM<<endl;
00546       {
00547         TreeNode it = nodes[i].getBottomBack();
00548 
00549 
00550         if(holder.isAncestor(it)){
00551 
00552           bool found = seq::maxLowerBound(nodes,it.getDFD(), retIdx,NULL,NULL);
00553           if(found) {
00554             unsigned int retLev = nodes[retIdx].getLevel();
00555             unsigned int myLev = nodes[i].getLevel();                                   
00556             if( (it.getAnchor() != nodes[retIdx].getAnchor()) && (!(nodes[retIdx].isAncestor(it))) ) {
00557               found = false;
00558             }else if( (retLev < myLev) && ( (myLev - retLev) > maxLevDiff ) ) {
00559               //Found a very big Neighbour
00560               found = false;
00561             }                                           
00562           }
00563           if(!found) {
00564             yesBalanced = false;
00565             std::cout<<nodes[i]<<": (BoBk) ->"<<nodes[retIdx]<<std::endl;
00566             failedEdges.push_back(nodes[i]);                                    
00567             break;
00568           }
00569         }
00570 
00571       }
00572 
00573       // cout<<RED<<"BoF"<<NRM<<endl;
00574       {
00575         TreeNode it = nodes[i].getBottomFront();
00576 
00577 
00578         if(holder.isAncestor(it)){
00579 
00580           bool found = seq::maxLowerBound(nodes,it.getDFD(), retIdx,NULL,NULL);
00581           if(found) {
00582             unsigned int retLev = nodes[retIdx].getLevel();
00583             unsigned int myLev = nodes[i].getLevel();                                   
00584             if( (it.getAnchor() != nodes[retIdx].getAnchor()) && (!(nodes[retIdx].isAncestor(it))) ) {
00585               found = false;
00586             }else if( (retLev < myLev) && ( (myLev - retLev) > maxLevDiff ) ) {
00587               //Found a very big Neighbour
00588               found = false;
00589             }                                           
00590           }
00591           if(!found) {
00592             yesBalanced = false;
00593             std::cout<<nodes[i]<<": (BoF) ->"<<nodes[retIdx]<<std::endl;
00594             failedEdges.push_back(nodes[i]);                                    
00595             break;
00596           }
00597         }
00598 
00599       }
00600 
00601     }//end if dim=3 or incCorn
00602 
00603     if(incCorn) {
00604       // cout<<RED<<"TRBk"<<NRM<<endl;
00605       {
00606         TreeNode it = nodes[i].getTopRightBack();
00607 
00608 
00609         if(holder.isAncestor(it)){
00610 
00611           bool found = seq::maxLowerBound(nodes,it.getDFD(), retIdx,NULL,NULL);
00612           if(found) {
00613             unsigned int retLev = nodes[retIdx].getLevel();
00614             unsigned int myLev = nodes[i].getLevel();                                   
00615             if( (it.getAnchor() != nodes[retIdx].getAnchor()) && (!(nodes[retIdx].isAncestor(it))) ) {
00616               found = false;
00617             }else if( (retLev < myLev) && ( (myLev - retLev) > maxLevDiff ) ) {
00618               //Found a very big Neighbour
00619               found = false;
00620             }                                           
00621           }
00622           if(!found) {
00623             yesBalanced = false;
00624             std::cout<<nodes[i]<<": (TRBk) ->"<<nodes[retIdx]<<std::endl;
00625             failedCorners.push_back(nodes[i]);                                  
00626             break;
00627           }
00628         }
00629 
00630       }
00631 
00632       // cout<<RED<<"TLF"<<NRM<<endl;
00633       {
00634         TreeNode it = nodes[i].getTopLeftFront();
00635 
00636 
00637         if(holder.isAncestor(it)){
00638 
00639           bool found = seq::maxLowerBound(nodes,it.getDFD(), retIdx,NULL,NULL);
00640           if(found) {
00641             unsigned int retLev = nodes[retIdx].getLevel();
00642             unsigned int myLev = nodes[i].getLevel();                                   
00643             if( (it.getAnchor() != nodes[retIdx].getAnchor()) && (!(nodes[retIdx].isAncestor(it))) ) {
00644               found = false;
00645             }else if( (retLev < myLev) && ( (myLev - retLev) > maxLevDiff ) ) {
00646               //Found a very big Neighbour
00647               found = false;
00648             }                                           
00649           }
00650           if(!found) {
00651             yesBalanced = false;
00652             std::cout<<nodes[i]<<": (TLF) ->"<<nodes[retIdx]<<std::endl;
00653             failedCorners.push_back(nodes[i]);                                  
00654             break;
00655           }
00656         }
00657 
00658       }
00659 
00660       // cout<<RED<<"BoRBk"<<NRM<<endl;
00661       {
00662         TreeNode it = nodes[i].getBottomRightBack();
00663 
00664 
00665         if(holder.isAncestor(it)){
00666 
00667           bool found = seq::maxLowerBound(nodes,it.getDFD(), retIdx,NULL,NULL);
00668           if(found) {
00669             unsigned int retLev = nodes[retIdx].getLevel();
00670             unsigned int myLev = nodes[i].getLevel();                                   
00671             if( (it.getAnchor() != nodes[retIdx].getAnchor()) && (!(nodes[retIdx].isAncestor(it))) ) {
00672               found = false;
00673             }else if( (retLev < myLev) && ( (myLev - retLev) > maxLevDiff ) ) {
00674               //Found a very big Neighbour
00675               found = false;
00676             }                                           
00677           }
00678           if(!found) {
00679             yesBalanced = false;
00680             std::cout<<nodes[i]<<": (BoRBk) ->"<<nodes[retIdx]<<std::endl;
00681             failedCorners.push_back(nodes[i]);                                  
00682             break;
00683           }
00684         }
00685 
00686       }
00687 
00688       // cout<<RED<<"TLBk"<<NRM<<endl;
00689       {
00690         TreeNode it = nodes[i].getTopLeftBack();
00691 
00692 
00693         if(holder.isAncestor(it)){
00694 
00695           bool found = seq::maxLowerBound(nodes,it.getDFD(), retIdx,NULL,NULL);
00696           if(found) {
00697             unsigned int retLev = nodes[retIdx].getLevel();
00698             unsigned int myLev = nodes[i].getLevel();                                   
00699             if( (it.getAnchor() != nodes[retIdx].getAnchor()) && (!(nodes[retIdx].isAncestor(it))) ) {
00700               found = false;
00701             }else if( (retLev < myLev) && ( (myLev - retLev) > maxLevDiff ) ) {
00702               //Found a very big Neighbour
00703               found = false;
00704             }                                           
00705           }
00706           if(!found) {
00707             yesBalanced = false;
00708             std::cout<<nodes[i]<<": (TLBk) ->"<<nodes[retIdx]<<std::endl;
00709             failedCorners.push_back(nodes[i]);                                  
00710             break;
00711           }
00712         }
00713 
00714       }
00715 
00716       // cout<<RED<<"BoRF"<<NRM<<endl;
00717       {
00718         TreeNode it = nodes[i].getBottomRightFront();
00719 
00720 
00721         if(holder.isAncestor(it)){
00722 
00723           bool found = seq::maxLowerBound(nodes,it.getDFD(), retIdx,NULL,NULL);
00724           if(found) {
00725             unsigned int retLev = nodes[retIdx].getLevel();
00726             unsigned int myLev = nodes[i].getLevel();                                   
00727             if( (it.getAnchor() != nodes[retIdx].getAnchor()) && (!(nodes[retIdx].isAncestor(it))) ) {
00728               found = false;
00729             }else if( (retLev < myLev) && ( (myLev - retLev) > maxLevDiff ) ) {
00730               //Found a very big Neighbour
00731               found = false;
00732             }                                           
00733           }
00734           if(!found) {
00735             yesBalanced = false;
00736             std::cout<<nodes[i]<<": (BoRF) ->"<<nodes[retIdx]<<std::endl;
00737             failedCorners.push_back(nodes[i]);                                  
00738             break;
00739           }
00740         }
00741 
00742       }
00743 
00744       // cout<<RED<<"TRF"<<NRM<<endl;
00745       {
00746         TreeNode it = nodes[i].getTopRightFront();
00747 
00748 
00749         if(holder.isAncestor(it)){
00750 
00751           bool found = seq::maxLowerBound(nodes,it.getDFD(), retIdx,NULL,NULL);
00752           if(found) {
00753             unsigned int retLev = nodes[retIdx].getLevel();
00754             unsigned int myLev = nodes[i].getLevel();                                   
00755             if( (it.getAnchor() != nodes[retIdx].getAnchor()) && (!(nodes[retIdx].isAncestor(it))) ) {
00756               found = false;
00757             }else if( (retLev < myLev) && ( (myLev - retLev) > maxLevDiff ) ) {
00758               //Found a very big Neighbour
00759               found = false;
00760             }                                           
00761           }
00762           if(!found) {
00763             yesBalanced = false;
00764             std::cout<<nodes[i]<<": (TRF) ->"<<nodes[retIdx]<<std::endl;
00765             failedCorners.push_back(nodes[i]);                                  
00766             break;
00767           }
00768         }
00769 
00770       }
00771 
00772 
00773       // cout<<RED<<"BoLBk"<<NRM<<endl;
00774       {
00775         TreeNode it = nodes[i].getBottomLeftBack();
00776 
00777 
00778         if(holder.isAncestor(it)){
00779 
00780           bool found = seq::maxLowerBound(nodes,it.getDFD(), retIdx,NULL,NULL);
00781           if(found) {
00782             unsigned int retLev = nodes[retIdx].getLevel();
00783             unsigned int myLev = nodes[i].getLevel();                                   
00784             if( (it.getAnchor() != nodes[retIdx].getAnchor()) && (!(nodes[retIdx].isAncestor(it))) ) {
00785               found = false;
00786             }else if( (retLev < myLev) && ( (myLev - retLev) > maxLevDiff ) ) {
00787               //Found a very big Neighbour
00788               found = false;
00789             }                                           
00790           }
00791           if(!found) {
00792             yesBalanced = false;
00793             std::cout<<nodes[i]<<": (BoLBk) ->"<<nodes[retIdx]<<std::endl;
00794             failedCorners.push_back(nodes[i]);                                  
00795             break;
00796           }
00797         }
00798 
00799 
00800       }
00801 
00802 
00803       // cout<<RED<<"BoLF"<<NRM<<endl;
00804       {
00805         TreeNode it = nodes[i].getBottomLeftFront();
00806 
00807 
00808         if(holder.isAncestor(it)){
00809 
00810 
00811           bool found = seq::maxLowerBound(nodes,it.getDFD(), retIdx,NULL,NULL);
00812           if(found) {
00813             unsigned int retLev = nodes[retIdx].getLevel();
00814             unsigned int myLev = nodes[i].getLevel();                                   
00815             if( (it.getAnchor() != nodes[retIdx].getAnchor()) && (!(nodes[retIdx].isAncestor(it))) ) {
00816               found = false;
00817             }else if( (retLev < myLev) && ( (myLev - retLev) > maxLevDiff ) ) {
00818               //Found a very big Neighbour
00819               found = false;
00820             }                                           
00821           }
00822           if(!found) {
00823             yesBalanced = false;
00824             std::cout<<nodes[i]<<": (BoLF) ->"<<nodes[retIdx]<<std::endl;
00825             failedCorners.push_back(nodes[i]);                                  
00826             break;
00827           }
00828         }
00829 
00830       }
00831 
00832     }//end if incCorn
00833 
00834   }//end for i
00835 
00836   seq::makeVectorUnique(failedFaces,false);
00837   seq::makeVectorUnique(failedEdges,false);
00838   seq::makeVectorUnique(failedCorners,false);
00839   char failCornerFileName[100];
00840   char failEdgeFileName[100];
00841   char failFaceFileName[100];
00842   strcpy(failFaceFileName,failFileName );
00843   strcpy(failEdgeFileName,failFileName);
00844   strcpy(failCornerFileName,failFileName);
00845   strcat(failFaceFileName,"_Faces.ot\0");       
00846   strcat(failEdgeFileName,"_Edges.ot\0");       
00847   strcat(failCornerFileName,"_Corners.ot\0");   
00848   writeNodesToFile(failCornerFileName,failedCorners);
00849   writeNodesToFile(failEdgeFileName,failedEdges);
00850   writeNodesToFile(failFaceFileName,failedFaces);
00851   return yesBalanced;
00852 }//end function
00853 
00854 }//end namespace
00855 }//end namespace
00856