|
|
Space-efficient geometric algorithms and data structuresBy Ilya Katz and Hervé Brönnimann |
00001 //TODO: remove unneeded functions 00002 //TODO: most of the work in remove_top, should be done in remove 00003 //TODO: insert(line) should return pointer to the node just created 00004 //TODO: DataNode() should be private 00005 00006 /* 00007 * Copyright © Ilya Katz and Hervé Brönnimann, 2005. 00008 */ 00019 #ifndef EXCPLICIT_TREE_HEAP_HPP 00020 #define EXCPLICIT_TREE_HEAP_HPP 00021 00022 00023 #include "tree_heap.hpp" 00024 #include "cgl.hpp" 00025 #include "data_node.hpp" 00026 00027 #include <boost/array.hpp> 00028 #include <vector> 00029 #include <algorithm> 00030 //#include <iostream> 00031 00032 00033 namespace inplaceds 00034 { 00035 template<typename Geometry> 00036 class explicit_tree_node: public TreeNode<Geometry> 00037 { 00038 public: 00039 00040 typedef typename Geometry::point_type point_type; 00041 typedef typename Geometry::line_type line_type; 00042 typedef DataNode<Geometry> Data; 00043 typedef explicit_tree_node<Geometry>* nodePtr; 00044 00045 explicit_tree_node(): 00046 //data(NULL), 00047 leftBST(NULL),rightBST(NULL),parentBST(NULL), 00048 leftPQ(NULL),rightPQ(NULL),parentPQ(NULL) 00049 {} 00050 explicit_tree_node(const line_type& l): 00051 data(Data(l)), 00052 leftBST(NULL),rightBST(NULL),parentBST(NULL), 00053 leftPQ(NULL),rightPQ(NULL),parentPQ(NULL) 00054 {} 00055 explicit_tree_node(const Data& d): 00056 data(d), 00057 leftBST(NULL),rightBST(NULL),parentBST(NULL), 00058 leftPQ(NULL),rightPQ(NULL),parentPQ(NULL) 00059 {} 00060 00061 00062 ~explicit_tree_node(){/*delete data;*/} 00063 00064 public: 00065 00066 nodePtr leftBST; 00067 nodePtr rightBST; 00068 nodePtr parentBST; 00069 00070 nodePtr leftPQ; 00071 nodePtr rightPQ; 00072 nodePtr parentPQ; 00073 00074 Data data; 00075 00076 }; 00077 00078 00079 template<typename Geometry, typename BSTCompare, typename PQCompare> 00080 class explicit_tree_heap: public tree_heap<Geometry> 00081 { 00082 00083 public: 00084 typedef typename Geometry::coord_type coord_type; 00085 typedef explicit_tree_node<Geometry> TNode; 00086 typedef typename TNode::point_type point_type; 00087 typedef typename TNode::nodePtr nodePtr; 00088 typedef typename TNode::Data Data; 00089 typedef typename Data::line_type line_type; 00090 00091 private: 00092 00094 #define DEFINE_POINTER_MAP( name, m_pointer ) \ 00095 struct name { \ 00096 nodePtr& operator[](nodePtr t) const { return (*t).m_pointer; } \ 00097 }; 00098 00099 00100 DEFINE_POINTER_MAP(PQ_leftPointer, leftPQ) 00101 DEFINE_POINTER_MAP(PQ_rightPointer, rightPQ) 00102 DEFINE_POINTER_MAP(PQ_parentPointer, parentPQ) 00103 00104 DEFINE_POINTER_MAP(BST_leftPointer, leftBST) 00105 DEFINE_POINTER_MAP(BST_rightPointer, rightBST) 00106 DEFINE_POINTER_MAP(BST_parentPointer, parentBST) 00107 00108 #undef DEFINE_POINTER_MAP 00110 00111 00112 struct BST_Data 00113 { 00114 Data& operator[](nodePtr t) const { return (*t).data; } 00115 }; 00116 00117 typedef BST_leftPointer leftBSTptr; 00118 typedef BST_rightPointer rightBSTptr; 00119 typedef BST_parentPointer parentBSTptr; 00120 00121 typedef PQ_leftPointer leftPQptr; 00122 typedef PQ_rightPointer rightPQptr; 00123 typedef PQ_parentPointer parentPQptr; 00124 00125 00126 typedef BST_Data BST_Data; 00127 00128 private: 00129 nodePtr rootBST; 00130 nodePtr rootPQ; 00131 00132 BSTCompare BSTcomp; 00133 PQCompare PQcomp; 00134 00135 rightBSTptr right; 00136 leftBSTptr left; 00137 parentBSTptr parent; 00138 00139 rightPQptr rightPQ; 00140 leftPQptr leftPQ; 00141 parentPQptr parentPQ; 00142 00143 BST_Data data; 00144 00145 public: 00146 00150 explicit_tree_heap(); 00151 00159 explicit_tree_heap(BSTCompare& b, PQCompare& p); 00160 ~explicit_tree_heap(){} 00161 00166 bool 00167 empty() 00168 { 00169 return rootPQ==NULL; 00170 } 00171 00176 inline void 00177 print() 00178 { 00179 00180 if(rootPQ!=NULL){ 00181 std::cerr<<"Priority Queue:"<<std::endl; 00182 preOrderPQ(rootPQ); 00183 } 00184 00185 if(rootBST!=NULL){ 00186 std::cerr<<std::endl<<"BST"<<std::endl; 00187 preOrder(rootBST); 00188 } 00189 } 00190 00195 void 00196 remove_top(); 00197 00202 inline nodePtr 00203 remove_node(nodePtr node) 00204 { 00205 nodePtr tmp = m_remove_node_PQ(node); 00206 tmp =m_remove_BST(tmp); 00207 } 00208 00212 inline void insert(const line_type& l) ; 00213 00217 nodePtr get_top(); 00218 00219 /* 00220 * @copydoc tree_heap::remove 00221 */ 00222 bool remove(const line_type& l) 00223 {} 00224 00229 inline nodePtr 00230 successor(nodePtr x){ 00231 m_successor(x, parent, left, right); 00232 } 00233 00238 inline nodePtr 00239 predecessor(nodePtr x){ 00240 return m_successor(x, parent, right, left); 00241 } 00242 00256 void 00257 swap_nodes(nodePtr a, nodePtr b); 00264 inline void 00265 adjust_PQ(nodePtr node) 00266 { 00267 percolate_down(node); 00268 percolate_up(node); 00269 } 00270 00275 inline void insert_BST(nodePtr t) 00276 { 00277 nodePtr result; 00278 rootBST= insert_without_balance(t, rootBST, result); 00279 } 00280 00285 void segment_right_event(nodePtr it) 00286 { 00287 it->data.right_event(); 00288 adjust_PQ(it); 00289 } 00290 00295 void segment_intersection_event(nodePtr it, point_type point, Data* intersecting) 00296 { 00297 it->data.intersection_event(point, intersecting); 00298 adjust_PQ(it); 00299 } 00300 00301 private: 00302 00303 template<class Parent, class Left, class Right> 00304 inline nodePtr 00305 m_successor(nodePtr x, Parent parent, Left left, Right right){ 00306 00307 if (right[x] != NULL) { 00308 x = right[x]; 00309 while (left[x] != NULL) 00310 x = left[x]; 00311 } 00312 else { 00313 nodePtr y = parent[x]; 00314 while (y!=NULL &&x == right[y]) { 00315 x = y; 00316 y = parent[y]; 00317 } 00318 x = y; 00319 00320 } 00321 return x; 00322 } 00323 00324 nodePtr 00325 insert_without_balance(nodePtr newLine, nodePtr t, nodePtr& result = NULL) 00326 { 00327 if(t==NULL) 00328 { 00329 t=newLine; 00330 result=t; 00331 00332 } 00333 else 00334 { 00335 if(BSTcomp(data[newLine], data[t])) 00336 { 00337 left[t]=( insert_without_balance(newLine, left[t], result)); 00338 parent[left[t]]=(t); 00339 } 00340 else //(BSTcomp(data[t],data[newLine])) 00341 { 00342 right[t]=( insert_without_balance(newLine, right[t], result)); 00343 parent[right[t]]=(t); 00344 } 00345 } 00346 00347 return t; 00348 00349 } 00350 00356 void 00357 percolate_up(nodePtr node); 00358 00364 void 00365 percolate_down(nodePtr node); 00366 00372 void 00373 update_node(nodePtr hole, nodePtr newNode); 00378 nodePtr 00379 m_remove_node_PQ(nodePtr root) 00380 { 00381 nodePtr hole=root; 00382 00383 while(hole!=NULL) 00384 { 00385 if(leftPQ[hole]!=NULL) 00386 { 00387 if(rightPQ[hole]!=NULL) 00388 { 00389 //if(!PQcomp(data[leftPQ[hole]], data[rightPQ[hole]])) 00390 if(PQcomp(data[leftPQ[hole]], data[rightPQ[hole]])) 00391 { 00392 update_node(hole, leftPQ[hole]); 00393 //hole=leftPQ[hole]; 00394 } 00395 else 00396 { 00397 update_node(hole, rightPQ[hole]); 00398 //hole=rightPQ[hole]; 00399 } 00400 } 00401 else 00402 {//only left child present 00403 update_node(hole, leftPQ[hole]); 00404 //hole=leftPQ[hole]; 00405 } 00406 } 00407 else if(rightPQ[hole]!=NULL) 00408 //only right child present 00409 { 00410 update_node(hole, rightPQ[hole]); 00411 //hole=rightPQ[hole]; 00412 } 00413 else{ 00414 //no children, stop 00415 return hole; 00416 } 00417 } 00418 } 00419 00420 00428 nodePtr 00429 m_remove_BST(nodePtr z) 00430 { 00431 nodePtr y,x; 00432 if(left[z] == NULL || right[z] == NULL) 00433 { 00434 y = z; 00435 } 00436 else 00437 { 00438 y = successor(z); 00439 } 00440 00441 if(left[y] != NULL) 00442 { 00443 x = left[y]; 00444 } 00445 else 00446 { 00447 x = right[y]; 00448 } 00449 00450 if(x != NULL) 00451 { 00452 parent[x] = parent[y]; 00453 } 00454 00455 if(parent[y] == NULL) 00456 { 00457 rootBST= x; 00458 } 00459 else if (y == left [parent[y]]) 00460 { 00461 left[parent[y]]=x; 00462 } 00463 else 00464 { 00465 right[parent[y]]=x; 00466 } 00467 00468 if(y != z) 00469 { 00470 //y is the successor of z, hence doesn't have a left child 00471 left[y]=left[z]; 00472 right[y]=right[z]; 00473 parent[y]=parent[z]; 00474 00475 if(parent[y]==NULL) 00476 { 00477 rootBST=y; 00478 } 00479 else 00480 { 00481 if(left[parent[y]]==z) 00482 { 00483 left[parent[y]]=y; 00484 } 00485 else 00486 { 00487 right[parent[y]]=y; 00488 } 00489 } 00490 00491 if(left[y]!=NULL) 00492 { 00493 parent[left[y]]=y; 00494 } 00495 00496 if(right[y]!=NULL) 00497 { 00498 parent[right[y]]=y; 00499 } 00500 00501 left[z]=right[z]=parent[z]=NULL; 00502 00503 return z; 00504 } 00505 00506 left[y]=right[y]=parent[y]=NULL; 00507 return y; 00508 } 00509 00510 void preOrder(nodePtr root) 00511 { 00512 00513 std::cerr<<*root<<" "; 00514 if(left[root]!=NULL) 00515 preOrder(left[root]); 00516 if(right[root]!=NULL) 00517 preOrder(right[root]); 00518 } 00519 00520 void preOrderPQ(nodePtr root) 00521 { 00522 std::cerr<<*root<<" "; 00523 if(leftPQ[root]!=NULL) 00524 preOrderPQ(leftPQ[root]); 00525 if(rightPQ[root]!=NULL) 00526 preOrderPQ(rightPQ[root]); 00527 00528 } 00529 00537 nodePtr BST_insert(const line_type& l, nodePtr t, nodePtr& result = NULL); 00538 00539 nodePtr PQ_insert(nodePtr); 00540 /* 00541 * Function that allocates a new node 00542 * Returns pointer to the node just allocated 00543 */ 00544 nodePtr allocateNode(const line_type&); 00545 nodePtr allocateNode(Data&); 00546 00547 void swap(nodePtr, nodePtr); 00548 00549 //disallow copies 00550 explicit_tree_heap(const explicit_tree_heap& p){}; 00551 explicit_tree_heap operator =(const explicit_tree_heap& p){}; 00552 00553 }; 00554 00555 template<typename Geometry, typename BSTCompare, typename PQCompare> 00556 typename explicit_tree_heap<Geometry, BSTCompare, PQCompare>::nodePtr 00557 explicit_tree_heap<Geometry, BSTCompare, PQCompare>::get_top() 00558 { 00559 return rootPQ; 00560 } 00561 00562 template<typename Geometry, typename BSTCompare, typename PQCompare> 00563 explicit_tree_heap<Geometry, BSTCompare, PQCompare>::explicit_tree_heap(): 00564 rootBST(NULL), rootPQ(NULL) 00565 00566 {} 00567 template<typename Geometry, typename BSTCompare, typename PQCompare> 00568 explicit_tree_heap<Geometry, BSTCompare, PQCompare>::explicit_tree_heap(BSTCompare& b, PQCompare& p): 00569 BSTcomp(b),PQcomp(p),rootBST(NULL), rootPQ(NULL) 00570 {} 00571 00573 template<typename Geometry, typename BSTCompare, typename PQCompare> 00574 typename explicit_tree_heap<Geometry, BSTCompare, PQCompare>::nodePtr 00575 explicit_tree_heap<Geometry, BSTCompare, PQCompare>::PQ_insert( nodePtr newNode) 00576 { 00577 00578 if(rootPQ == NULL){ 00579 rootPQ = newNode; 00580 return newNode; 00581 } 00582 00583 nodePtr hole = rootPQ; 00584 00585 //dont need hole!=null 00586 while(hole!=NULL && PQcomp(data[hole], data[newNode])/*PQcomp(data[newNode], data[hole])*/){ 00587 00588 if(hole->leftPQ == NULL){ 00589 leftPQ[hole]= newNode; 00590 parentPQ[newNode] = hole; 00591 return leftPQ[hole]; 00592 } 00593 if(hole->rightPQ == NULL){ 00594 rightPQ[hole] = newNode; 00595 parentPQ[newNode] = hole; 00596 return rightPQ[hole]; 00597 } 00598 hole = PQcomp(data[rightPQ[hole]], data[leftPQ[hole]])? /*PQcomp(data[leftPQ[hole]], data[rightPQ[hole]])?*/ 00599 leftPQ[hole]: 00600 rightPQ[hole]; 00601 } 00602 00603 if(hole==rootPQ){ 00604 rootPQ=newNode; 00605 leftPQ[newNode]=hole; 00606 //if hole!=null 00607 parentPQ[hole]=newNode; 00608 return newNode; 00609 } 00610 if(leftPQ[parentPQ[hole]] == hole){ 00611 leftPQ[parentPQ[hole]]=newNode; 00612 } 00613 else{ 00614 rightPQ[parentPQ[hole]]=newNode; 00615 } 00616 00617 parentPQ[newNode]=parentPQ[hole]; 00618 parentPQ[hole]=newNode; 00619 leftPQ[newNode]=hole; 00620 rightPQ[newNode]=NULL; 00621 return newNode; 00622 } 00623 00624 template<typename Geometry, typename BSTCompare, typename PQCompare> 00625 void explicit_tree_heap<Geometry, BSTCompare, PQCompare>::swap(nodePtr a, nodePtr b) 00626 { 00627 std::swap(*a,*b); 00628 } 00629 00630 template<typename Geometry, typename BSTCompare, typename PQCompare> 00631 void explicit_tree_heap<Geometry, BSTCompare, PQCompare>::insert(const line_type& l) 00632 { 00633 nodePtr result=NULL; 00634 //rootBST=BST_insert(l, rootBST, result); 00635 nodePtr t=allocateNode(l); 00636 00637 // rootBST= insert_without_balance(t, rootBST, result); 00638 00639 PQ_insert(t); 00640 00641 00642 } 00643 00644 00645 template<typename Geometry> 00646 std::ostream& operator<<(std::ostream& os, inplaceds::explicit_tree_node<Geometry>& node) 00647 { 00648 os<<"("<<node.data.line[0][0]<<","<<node.data.line[0][1]<<")-(" 00649 <<node.data.line[1][0]<<","<<node.data.line[1][1] 00650 // <<" h:"<<node.height 00651 <<",\t r: "<<(node.rightBST!=NULL?node.rightBST->data.line[0][1]:0) 00652 <<",l: "<<(node.leftBST!=NULL?node.leftBST->data.line[0][1]:0)<<"\t" 00653 <<",p: ("<<(node.parentBST!=NULL?node.parentBST->data.line[0][0]:0)<<"" 00654 <<",: "<<(node.parentBST!=NULL?node.parentBST->data.line[0][1]:0)<<")\t" 00655 // <<" "<<&node 00656 <<" "<<int(node.data.myEvent)<<" "<<node.data.point[0] 00657 <<" )"<<std::endl; 00658 00659 // <<node.height//<<" left "<<node.leftBST<<" pare"<<node.parentBST 00660 // <<")";//<<" L:"<<node.leftBST 00661 // <<" R:"<<node.rightBST<<" )";//<<","<<node.data.line[0][1]<<")"; 00662 } 00663 00664 00665 00666 00667 template<typename Geometry, typename BSTCompare, typename PQCompare> 00668 typename explicit_tree_heap<Geometry, BSTCompare, PQCompare>::nodePtr 00669 explicit_tree_heap<Geometry, BSTCompare, PQCompare>::allocateNode(const line_type& l) 00670 { 00671 return new TNode(l); 00672 } 00673 00674 template<typename Geometry, typename BSTCompare, typename PQCompare> 00675 typename explicit_tree_heap<Geometry, BSTCompare, PQCompare>::nodePtr 00676 explicit_tree_heap<Geometry, BSTCompare, PQCompare>::allocateNode(Data& d) 00677 { 00678 return new TNode(d); 00679 } 00680 00681 template<typename Geometry, typename BSTCompare, typename PQCompare> 00682 void 00683 explicit_tree_heap<Geometry, BSTCompare, PQCompare>::swap_nodes( 00684 typename explicit_tree_heap<Geometry, BSTCompare, PQCompare>::nodePtr a, 00685 typename explicit_tree_heap<Geometry, BSTCompare, PQCompare>::nodePtr b) 00686 { 00687 std::swap(left[a],left[b]); 00688 std::swap(right[a],right[b]); 00689 std::swap(parent[a],parent[b]); 00690 00691 if(parent[b]!=NULL) 00692 { 00693 if(parent[b]==b) 00694 { 00695 parent[b]=a; 00696 } 00697 if(left[parent[b]]==a) 00698 { 00699 left[parent[b]]=b; 00700 } 00701 else 00702 { 00703 right[parent[b]]=b; 00704 } 00705 } 00706 else 00707 { 00708 rootBST=b; 00709 } 00710 00711 if(parent[a]!=NULL) 00712 { 00713 if(parent[a]==a) 00714 { 00715 parent[a]=b; 00716 } 00717 if(left[parent[a]]==b) 00718 { 00719 left[parent[a]]=a; 00720 } 00721 else 00722 { 00723 right[parent[a]]=a; 00724 } 00725 00726 } 00727 else 00728 { 00729 rootBST=a; 00730 } 00731 00732 00733 if(left[a]!=NULL) 00734 { 00735 if(left[a]==a) 00736 { 00737 left[a]=b; 00738 } 00739 parent[left[a]]=a; 00740 } 00741 00742 00743 if(right[a]!=NULL) 00744 { 00745 if(right[a]==a) 00746 { 00747 right[a]=b; 00748 } 00749 parent[right[a]]=a; 00750 } 00751 00752 00753 00754 if(left[b]!=NULL) 00755 { 00756 if(left[b]==b) 00757 { 00758 left[b]=a; 00759 } 00760 parent[left[b]]=b; 00761 } 00762 if(right[b]!=NULL) 00763 { 00764 if(right[b]==b) 00765 { 00766 right[b]=a; 00767 } 00768 parent[right[b]]=b; 00769 } 00770 } 00771 00772 template<typename Geometry, typename BSTCompare, typename PQCompare> 00773 void 00774 explicit_tree_heap<Geometry, BSTCompare, PQCompare>::percolate_up( 00775 typename explicit_tree_heap<Geometry, BSTCompare, PQCompare>::nodePtr node) 00776 { 00777 nodePtr hole = node; 00778 while(parentPQ[hole]!=NULL) 00779 { 00780 /*if(!PQcomp(data[hole],data[parentPQ[hole]]))*/ 00781 if(PQcomp(data[hole],data[parentPQ[hole]])) 00782 { 00783 update_node(parentPQ[hole],hole); 00784 } 00785 else 00786 { 00787 break; 00788 } 00789 } 00790 } 00791 00792 template<typename Geometry, typename BSTCompare, typename PQCompare> 00793 void 00794 explicit_tree_heap<Geometry, BSTCompare, PQCompare>::percolate_down( 00795 typename explicit_tree_heap<Geometry, BSTCompare, PQCompare>::nodePtr node) 00796 { 00797 nodePtr hole=node; 00798 00799 while(true) 00800 { 00801 if(leftPQ[hole]==NULL) 00802 { 00803 if(rightPQ[hole]!=NULL)//only right child 00804 { 00805 if(PQcomp(data[rightPQ[hole]],data[hole])) 00806 { 00807 update_node(hole, rightPQ[hole]); 00808 } 00809 else break; 00810 } 00811 else break; //no children 00812 } 00813 else if(rightPQ[hole]==NULL) 00814 { 00815 if(leftPQ[hole]!=NULL)//only left child 00816 { 00817 if(PQcomp(data[leftPQ[hole]],data[hole])) 00818 { 00819 update_node(hole, leftPQ[hole]); 00820 } 00821 else break; 00822 } 00823 } 00824 else //both children 00825 { 00826 //choose the smaller one 00827 if(PQcomp(data[leftPQ[hole]], data[rightPQ[hole]])) 00828 { 00829 if(PQcomp(data[leftPQ[hole]],data[hole])) 00830 { 00831 update_node(hole, leftPQ[hole]); 00832 } 00833 else break; 00834 } 00835 else 00836 { 00837 if(PQcomp(data[rightPQ[hole]],data[hole])) 00838 { 00839 update_node(hole, rightPQ[hole]); 00840 } 00841 else break; 00842 00843 } 00844 00845 } 00846 } 00847 00848 } 00849 00850 template<typename Geometry, typename BSTCompare, typename PQCompare> 00851 void 00852 explicit_tree_heap<Geometry, BSTCompare, PQCompare>::update_node( 00853 typename explicit_tree_heap<Geometry, BSTCompare, PQCompare>::nodePtr hole, 00854 typename explicit_tree_heap<Geometry, BSTCompare, PQCompare>::nodePtr newNode) 00855 { 00856 if(parentPQ[hole]==NULL) 00857 { 00858 parentPQ[newNode]=NULL; 00859 rootPQ=newNode; 00860 } 00861 else 00862 { 00863 std::swap(parentPQ[newNode], parentPQ[hole]); 00864 00865 if(leftPQ[parentPQ[newNode]]==hole) 00866 { 00867 leftPQ[parentPQ[newNode]]=newNode; 00868 } 00869 else 00870 { 00871 rightPQ[parentPQ[newNode]]=newNode; 00872 } 00873 } 00874 00875 std::swap(leftPQ[hole],leftPQ[newNode]); 00876 if(leftPQ[hole]!=NULL) 00877 { 00878 parentPQ[leftPQ[hole]]=hole; 00879 } 00880 if(leftPQ[newNode]==newNode) 00881 { 00882 leftPQ[newNode]=hole; 00883 } 00884 if(leftPQ[newNode]!=NULL) 00885 { 00886 parentPQ[leftPQ[newNode]]=newNode; 00887 } 00888 00889 std::swap(rightPQ[hole],rightPQ[newNode]); 00890 if(rightPQ[hole]!=NULL) 00891 { 00892 parentPQ[rightPQ[hole]]=hole; 00893 } 00894 if(rightPQ[newNode]==newNode) 00895 { 00896 rightPQ[newNode]=hole; 00897 } 00898 if(rightPQ[newNode]!=NULL) 00899 { 00900 parentPQ[rightPQ[newNode]]=newNode; 00901 } 00902 00903 } 00904 00905 00906 template<typename Geometry, typename BSTCompare, typename PQCompare> 00907 void 00908 explicit_tree_heap<Geometry, BSTCompare, PQCompare>::remove_top() 00909 { 00910 if(leftPQ[rootPQ]!=NULL || rightPQ[rootPQ]!=NULL) 00911 { 00912 nodePtr tmp = m_remove_node_PQ(rootPQ); 00913 tmp = m_remove_BST(tmp); 00914 00915 if(parentPQ[tmp]!=NULL){ 00916 if(leftPQ[parentPQ[tmp]]==tmp) 00917 { 00918 leftPQ[parentPQ[tmp]]=NULL; 00919 } 00920 else if(rightPQ[parentPQ[tmp]]==tmp) 00921 { 00922 rightPQ[parentPQ[tmp]]=NULL; 00923 } 00924 } 00925 tmp->data.line[0][0]=-99; 00926 tmp->data.line[0][1]=-99; 00927 delete tmp; 00928 } 00929 else 00930 { 00931 delete rootPQ; 00932 rootBST=NULL; 00933 rootPQ=NULL; 00934 } 00935 00936 } 00937 00938 } //namespace 00939 #endif 00940 00941 00942 00943
Code Documentation generated Using Doxygen
Copyright © Ilya Katz and Hervé Brönnimann, 2005, 2006.