Graph Drawing Toolkit
00001 /******************************************************************************* 00002 + 00003 + rm3_PQ_tree.h 00004 + 00005 + This file is part of GDToolkit. It can be 00006 + used free of charge in academic research and teaching. 00007 + Any direct or indirect commercial use of this software is illegal 00008 + without a written authorization of 00009 + the Dipartimento di Informatica e Automazione 00010 + Universita' di Roma Tre, Roma, ITALIA 00011 + 00012 + 00013 *******************************************************************************/ 00017 #include <string> 00018 #include <GDT/gdtlist.h> 00019 #include <GDT/gdtmap.h> 00020 #include <GDT/gdtqueue.h> 00021 #include <GDT/gdt_error.h> 00022 #include <GDT/rm3_undi_graph.h> 00023 #include<GDT/rm3_draw_undi_graph.h> 00024 #include <GDT/stopwatch.h> 00025 00026 #ifndef RM3_PQ_TREE_H 00027 #define RM3_PQ_TREE_H 00028 00029 00030 namespace gdt { 00031 00032 template <class T> class PQ_tree; 00033 template <class T> class PQ_node_struct_freezed; 00034 template <class T> class PQ_tree_freezed; 00035 00036 template <class T> class 00037 00044 PQ_node_struct 00045 { 00046 00047 friend class PQ_tree<T>; 00048 typedef PQ_node_struct<T>* PQ_node; 00049 00050 public: 00051 int id; //id del nodo 00052 int child_count; // number of children possessed by the node (only for P-node) 00053 //gdt::gdtlist<PQ_node> circular_link; // doubly-linked circular list of chidren of a P-node ?? 00054 PQ_node link_left_side, link_right_side; //two link to two siblings ?? 00055 PQ_node left_endmost, right_endmost; // two endmost children (only for Q_nodes) 00056 gdtlist<PQ_node> full_children; // list containing all of full children 00057 //gdt::gdtlist<PQ_node> immediate_siblings; //list containig 0 (children of a P_node),1 (endmost children of a Q-node) or 2 (interior children of a Q_node) immediate siblings non c'č pių 00058 int label; // "empty", "full" or "partial" 00059 int mark; // initially "unmarked", during bubbling up "queued", during processing "blocked" or "unblocked" 00060 PQ_node parent; //immediate ancestor 00061 gdtlist<PQ_node> partial_children; // list containing all of partial children 00062 int pertinent_child_count; // number of pertinent children 00063 int pertinent_leaf_count; // number of pertinent leaves which are descendants 00064 int type; // "leaf", "P-node" or "Q-node" 00065 T value; 00066 00067 00068 //public: 00072 PQ_node_struct 00073 ( 00074 ); 00075 00076 00077 00081 ~PQ_node_struct 00082 ( 00083 ); 00084 00085 00086 00090 void 00091 set_id 00092 ( 00093 int id 00094 ); 00095 00096 00097 00101 void 00102 set_type 00103 ( 00104 int type 00105 ); 00106 00107 00108 00112 void 00113 set_value 00114 ( 00115 T value 00116 ); 00117 00118 00119 00123 void 00124 set_child_count 00125 ( 00126 int child_count 00127 ); 00128 00129 00130 00134 void 00135 set_parent 00136 ( 00137 PQ_node parent 00138 ); 00139 00140 00144 PQ_node 00145 get_parent 00146 ( 00147 ); 00148 00149 00150 00154 int 00155 get_id 00156 ( 00157 ); 00158 00159 00160 00164 int 00165 get_type 00166 ( 00167 ); 00168 00169 00170 00174 T 00175 get_value 00176 ( 00177 ); 00178 00179 00180 00184 void 00185 reset_node 00186 ( 00187 ); 00188 00189 00190 00194 bool 00195 is_endmost 00196 ( 00197 ); 00198 00199 00200 00204 void 00205 remove_from_circular_link 00206 ( 00207 ); 00208 00209 }; 00210 00211 00212 00220 template <class T> class 00221 PQ_tree 00222 { 00223 00224 00225 typedef PQ_node_struct<T>* PQ_node; 00226 typedef PQ_node_struct_freezed<T>* PQ_node_freezed; 00227 00228 private: 00229 gdtlist<PQ_node> leaves; //list of the leaves 00230 int max_id; //max id of the nodes 00231 int block_count; //number of blocks of blocked nodes 00232 int blocked_nodes; //number of the blocked nodes 00233 bool off_the_top; //if the root has been processed 00234 gdtqueue<PQ_node> queue; //queue for sequencing the order in which nodes are processed 00235 PQ_node root; //radice 00236 int number_of_nodes; //the number of nodes of tree 00237 gdtqueue<PQ_node> full_queue; //queue for full nodes 00238 gdtlist<PQ_node> blocked_list; //list of blocked nodes qui per disegnare grafi da mettere in bubble 00239 gdtmap<T,PQ_node> map_leaves; 00240 00241 00242 00243 protected: 00244 int 00245 generate_id 00246 ( 00247 ); 00248 00249 00250 public: 00254 PQ_tree 00255 ( 00256 ); 00257 00258 00262 PQ_tree 00263 ( 00264 gdtlist<T> &input_leaves 00265 ); 00266 00267 00268 00272 ~PQ_tree 00273 ( 00274 ); 00275 00276 00277 00282 PQ_tree<T>& 00283 operator= 00284 ( 00285 const PQ_tree<T>& t 00286 ); 00287 00288 00289 00293 PQ_node 00294 get_root 00295 ( 00296 ); 00297 00298 00299 00303 int 00304 get_max_id 00305 ( 00306 ); 00307 00308 00309 00313 int 00314 get_number_of_nodes 00315 ( 00316 ); 00317 00318 00322 void 00323 set_leaves 00324 ( 00325 gdt::gdtlist<gdt::PQ_node_struct<T>*> list_leaves 00326 ); 00327 00328 00329 00333 gdtlist<PQ_node> 00334 get_leaves 00335 ( 00336 ); 00337 00338 00339 00343 PQ_node 00344 find_leaf 00345 ( 00346 T value 00347 ); 00348 00349 00350 00354 void 00355 reset_tree 00356 ( 00357 ); 00358 00359 00360 00364 bool 00365 is_root 00366 ( 00367 PQ_node node 00368 ); 00369 00370 00371 00375 bool 00376 pnode_sorting 00377 ( 00378 PQ_node node 00379 ); 00380 00381 00382 00386 bool 00387 qnode_reversing 00388 ( 00389 PQ_node node 00390 ); 00391 00392 00393 00397 bool 00398 assign_parent_to_draw_graph 00399 ( 00400 PQ_node node, 00401 int count 00402 ); 00403 00404 00405 00409 void 00410 add_leaf 00411 ( 00412 T value 00413 ); 00414 00415 00416 00421 bool 00422 bubble 00423 ( 00424 gdtlist<T> &S 00425 ); 00426 00427 00428 00433 bool 00434 template_L1 00435 ( 00436 PQ_node node 00437 ); 00438 00439 00440 00445 bool 00446 template_P1 00447 ( 00448 PQ_node node 00449 ); 00450 00451 00452 00457 bool 00458 template_P2 00459 ( 00460 PQ_node node 00461 ); 00462 00463 00464 00469 bool 00470 template_P3 00471 ( 00472 PQ_node node 00473 ); 00474 00475 00476 00481 bool 00482 template_P4 00483 ( 00484 PQ_node node 00485 ); 00486 00487 00488 00492 bool 00493 template_P5 00494 ( 00495 PQ_node node 00496 ); 00497 00498 00499 00504 bool 00505 template_P6 00506 ( 00507 PQ_node node 00508 ); 00509 00510 00511 00516 bool 00517 template_Q1 00518 ( 00519 PQ_node node 00520 ); 00521 00522 00523 00527 bool 00528 template_Q2 00529 ( 00530 PQ_node node 00531 ); 00532 00533 00534 00538 bool 00539 template_Q3 00540 ( 00541 PQ_node node 00542 ); 00543 00544 00545 00550 bool 00551 make_empty 00552 ( 00553 ); 00554 00555 00556 00561 bool 00562 reduce 00563 ( 00564 gdtlist<T> &S 00565 ); 00566 00567 00568 00572 void 00573 freeze 00574 ( 00575 PQ_tree_freezed<T> &freezed_tree 00576 ); 00577 00578 00579 00584 undi_graph 00585 PQ_tree_into_undi_graph 00586 ( 00587 std::string title 00588 ); 00589 00590 }; 00591 00592 00593 00594 template <class T> class PQ_tree_freezed; 00595 00596 template <class T> class 00597 PQ_node_struct_freezed 00598 { 00599 00600 friend class PQ_tree<T>; 00601 friend class PQ_tree_freezed<T>; 00602 typedef PQ_node_struct_freezed<T>* PQ_node_freezed; 00603 00604 private: 00605 int id; //id del nodo 00606 gdt::gdtlist<PQ_node_freezed> children_list; // list of the chidren 00607 int type; // "leaf", "P-node" or "Q-node" 00608 T value; 00609 00610 00611 00612 public: 00616 PQ_node_struct_freezed 00617 ( 00618 ); 00619 00620 00621 00625 ~PQ_node_struct_freezed 00626 ( 00627 ); 00628 00629 00630 00634 int 00635 get_id 00636 ( 00637 ); 00638 00639 00640 00644 T 00645 get_value 00646 ( 00647 ); 00648 00649 }; 00650 00651 00652 00653 template <class T> class 00654 PQ_tree_freezed 00655 { 00656 00657 00658 friend class PQ_tree<T>; 00659 typedef PQ_node_struct<T>* PQ_node; 00660 typedef PQ_node_struct_freezed<T>* PQ_node_freezed; 00661 00662 private: 00663 PQ_node_freezed root; //radice 00664 int number_of_nodes; //the number of nodes of tree 00665 gdtlist<PQ_node_freezed> frontier; //tree frontier 00666 00667 00668 00669 /*protected: 00670 int 00671 generate_id 00672 ( 00673 );*/ 00674 00675 00676 public: 00677 00681 PQ_tree_freezed 00682 ( 00683 ); 00684 00685 00686 00690 ~PQ_tree_freezed 00691 ( 00692 ); 00693 00694 00695 00699 gdtlist<T> 00700 tree_search 00701 ( 00702 ); 00703 00704 00705 00709 void 00710 sorted_leaves_list 00711 ( 00712 gdtlist<PQ_node_struct_freezed<T>*> 00713 ); 00714 00715 00716 00720 void 00721 tree_frontier 00722 (); 00723 00724 00725 00729 gdtlist<PQ_node_struct_freezed<T>*> 00730 get_frontier 00731 (); 00732 }; 00733 00734 }; 00735 00736 00737 00738 enum 00739 { 00740 NON_VALID=0, 00741 LEAF=1, 00742 PNODE=2, 00743 QNODE=3, 00744 PSEUDONODE=4, 00745 00746 EMPTY=5, 00747 PARTIAL=6, 00748 FULL=7, 00749 00750 UNMARKED=8, 00751 QUEUED=9, 00752 MARKED=10, 00753 BLOCKED=11, 00754 UNBLOCKED=12 00755 }; 00756 00757 00758 00759 00760 template<class T> 00761 gdt::PQ_node_struct<T>:: 00762 PQ_node_struct 00763 () 00764 { 00765 id=0; 00766 child_count=0; 00767 link_left_side=NULL; 00768 link_right_side=NULL; 00769 left_endmost=NULL; 00770 right_endmost=NULL; 00771 parent=NULL; 00772 type=NON_VALID; 00773 reset_node(); 00774 } 00775 00776 00777 00778 template<class T> 00779 gdt::PQ_node_struct<T>:: 00780 ~PQ_node_struct 00781 () 00782 { 00783 full_children.clear(); 00784 partial_children.clear(); 00785 } 00786 00787 00788 00789 template<class T> 00790 void 00791 gdt::PQ_node_struct<T>:: 00792 set_id 00793 ( 00794 int id 00795 ) 00796 { 00797 this->id=id; 00798 } 00799 00800 00801 00802 template<class T> 00803 void 00804 gdt::PQ_node_struct<T>:: 00805 set_child_count 00806 ( 00807 int child_count 00808 ) 00809 { 00810 this->child_count=child_count; 00811 } 00812 00813 00814 template<class T> 00815 void 00816 gdt::PQ_node_struct<T>:: 00817 set_parent 00818 ( 00819 PQ_node parent 00820 ) 00821 { 00822 this->parent=parent; 00823 } 00824 00825 00826 template<class T> 00827 gdt::PQ_node_struct<T>* 00828 gdt::PQ_node_struct<T>:: 00829 get_parent 00830 ( 00831 ) 00832 { 00833 return parent; 00834 } 00835 00836 00837 template<class T> 00838 void 00839 gdt::PQ_node_struct<T>:: 00840 set_type 00841 ( 00842 int type 00843 ) 00844 { 00845 this->type=type; 00846 } 00847 00848 00849 template<class T> 00850 void 00851 gdt::PQ_node_struct<T>:: 00852 set_value 00853 ( 00854 T value 00855 ) 00856 { 00857 this->value=value; 00858 } 00859 00860 00861 template<class T> 00862 int 00863 gdt::PQ_node_struct<T>:: 00864 get_id 00865 () 00866 { 00867 return id; 00868 } 00869 00870 00871 template<class T> 00872 int 00873 gdt::PQ_node_struct<T>:: 00874 get_type 00875 () 00876 { 00877 return type; 00878 } 00879 00880 00881 00882 template<class T> 00883 T 00884 gdt::PQ_node_struct<T>:: 00885 get_value 00886 () 00887 { 00888 return value; 00889 } 00890 00891 00892 template<class T> 00893 void 00894 gdt::PQ_node_struct<T>:: 00895 reset_node 00896 () 00897 { 00898 label=EMPTY; 00899 mark=UNMARKED; 00900 pertinent_child_count=0; 00901 pertinent_leaf_count=0; 00902 full_children.clear(); 00903 partial_children.clear(); 00904 } 00905 00906 00907 template<class T> 00908 bool 00909 gdt::PQ_node_struct<T>:: 00910 is_endmost 00911 () 00912 { 00913 return((this->link_left_side==NULL)||(this->link_right_side==NULL)); 00914 } 00915 00916 00917 template<class T> 00918 void 00919 gdt::PQ_node_struct<T>:: 00920 remove_from_circular_link 00921 () 00922 { 00923 this->link_right_side->link_left_side=this->link_left_side; 00924 this->link_left_side->link_right_side=this->link_right_side; 00925 } 00926 00927 00928 00929 template <class T> 00930 gdt::PQ_tree<T>:: 00931 PQ_tree 00932 () 00933 { 00934 root=NULL; 00935 number_of_nodes=0; 00936 max_id=-1; 00937 block_count=0; 00938 blocked_nodes=0; 00939 off_the_top=false; 00940 } 00941 00942 00943 00944 template <class T> 00945 gdt::PQ_tree<T>:: 00946 PQ_tree 00947 ( 00948 gdt::gdtlist<T> &input_leaves 00949 ) 00950 { 00951 T temp_i; 00952 PQ_node temp_n,p_base; 00953 max_id=-1; 00954 forall(temp_i,input_leaves) 00955 { 00956 temp_n=new(PQ_node_struct<T>); 00957 temp_n->id=generate_id(); //temp_n->set_id(generate_id()); 00958 temp_n->type=LEAF; //temp_n->set_type(LEAF); 00959 temp_n->value=temp_i; 00960 leaves.append(temp_n); 00961 map_leaves[temp_i]=temp_n; 00962 //if(temp_i>max_id) 00963 // max_id=temp_i; 00964 00965 } 00966 p_base=new(PQ_node_struct<T>); 00967 p_base->id=generate_id(); //p_base->set_id(generate_id()); 00968 //max_id=p_base->id; //max_id=p_base->get_id(); 00969 p_base->type=PNODE; //p_base->set_type(PNODE); 00970 p_base->child_count=leaves.size(); //p_base->set_child_count(leaves.size()); 00971 //p_base->circular_link=leaves; //p_base->set_circular_link(leaves); 00972 root=p_base; 00973 forall(temp_n,leaves) 00974 { 00975 temp_n->parent=p_base; //temp_n->set_parent(p_base); 00976 //temp_n->link_left_side=leaves.contents(leaves.cyclic_pred(temp_n));//segmentation fault 00977 //temp_n->link_right_side=leaves.contents(leaves.cyclic_succ(temp_n)); 00978 } 00979 for(int i=0;i<leaves.size();i++) 00980 { 00981 leaves.contents(leaves.get_item(i))->link_left_side=leaves.contents(leaves.cyclic_pred(leaves.get_item(i))); 00982 leaves.contents(leaves.get_item(i)) ->link_right_side=leaves.contents(leaves.cyclic_succ(leaves.get_item(i))); 00983 } 00984 number_of_nodes=leaves.size()+1; 00985 reset_tree(); 00986 } 00987 00988 00989 00990 template <class T> 00991 gdt::PQ_tree<T>:: 00992 ~PQ_tree 00993 () 00994 { 00995 make_empty(); 00996 if(root!=NULL) 00997 { 00998 delete(root); 00999 } 01000 //cout<<"OK"<<endl; 01001 } 01002 01003 01004 01005 template <class T> 01006 gdt::PQ_tree<T>& 01007 gdt::PQ_tree<T>:: 01008 operator= 01009 ( 01010 const gdt::PQ_tree<T>& t 01011 ) 01012 { 01013 PQ_node temp_node,temp_pq,temp_child,current_node; 01014 gdt::gdtmap<PQ_node,PQ_node> map_PQ; 01015 gdt::gdtmap<PQ_node,int> node_visited_1(0); 01016 gdt::gdtmap<PQ_node,int> node_visited_2(0); 01017 /*forall(temp_node,t.leaves) 01018 cout<<temp_node->id<<endl;*/ 01019 //this->leaves.clear(); 01020 //this->map_leaves.clear(); 01021 this->make_empty(); 01022 forall(temp_node,t.leaves) 01023 { 01024 temp_pq=temp_node; 01025 while((temp_pq!=NULL)&&(node_visited_1[temp_pq]==0)) 01026 { 01027 current_node=new(PQ_node_struct<T>); 01028 current_node->id=temp_pq->id; 01029 current_node->type=temp_pq->type; 01030 current_node->value=temp_pq->value; 01031 current_node->child_count=temp_pq->child_count; 01032 map_PQ[temp_pq]=current_node; 01033 node_visited_1[temp_pq]=1; 01034 temp_pq=temp_pq->parent; 01035 } 01036 } 01037 forall(temp_node,t.leaves) 01038 { 01039 temp_pq=temp_node; 01040 while((temp_pq!=NULL)&&(node_visited_2[temp_pq]==0)) 01041 { 01042 current_node=map_PQ[temp_pq]; 01043 forall(temp_child,temp_pq->full_children) 01044 current_node->full_children.append(map_PQ[temp_child]); 01045 forall(temp_child,temp_pq->partial_children) 01046 current_node->partial_children.append(map_PQ[temp_child]); 01047 current_node->parent=map_PQ[temp_pq->parent]; 01048 current_node->link_left_side=map_PQ[temp_pq->link_left_side]; 01049 current_node->link_right_side=map_PQ[temp_pq->link_right_side]; 01050 if(current_node->type==LEAF) 01051 { 01052 this->leaves.append(current_node); 01053 map_leaves[current_node->value]=current_node; 01054 } 01055 else 01056 { 01057 if(temp_pq->left_endmost!=NULL) 01058 current_node->left_endmost=map_PQ[temp_pq->left_endmost]; 01059 if(temp_pq->right_endmost!=NULL) 01060 current_node->right_endmost=map_PQ[temp_pq->right_endmost]; 01061 } 01062 node_visited_2[temp_pq]=1; 01063 temp_pq=temp_pq->parent; 01064 } 01065 } 01066 this->max_id=t.max_id; 01067 this->root=map_PQ[t.root]; 01068 this->root->parent=NULL; 01069 this->number_of_nodes=t.number_of_nodes; 01070 this->reset_tree(); 01071 return *this; 01072 } 01073 01074 01075 template<class T> 01076 int 01077 gdt::PQ_tree<T>:: 01078 generate_id 01079 () 01080 { 01081 return ++max_id; 01082 } 01083 01084 01085 template<class T> 01086 void 01087 gdt::PQ_tree<T>:: 01088 reset_tree 01089 () 01090 { 01091 block_count=0; 01092 blocked_nodes=0; 01093 off_the_top=false; 01094 queue.clear(); 01095 } 01096 01097 01098 template<class T> 01099 gdt::PQ_node_struct<T>* 01100 gdt::PQ_tree<T>:: 01101 get_root 01102 () 01103 { 01104 return root; 01105 } 01106 01107 01108 template<class T> 01109 int 01110 gdt::PQ_tree<T>:: 01111 get_max_id 01112 () 01113 { 01114 return max_id; 01115 } 01116 01117 01118 template<class T> 01119 int 01120 gdt::PQ_tree<T>:: 01121 get_number_of_nodes 01122 () 01123 { 01124 return number_of_nodes; 01125 } 01126 01127 01128 01129 template<class T> 01130 void 01131 gdt::PQ_tree<T>:: 01132 set_leaves 01133 ( 01134 gdt::gdtlist<gdt::PQ_node_struct<T>*> list_leaves 01135 ) 01136 { 01137 leaves=list_leaves; 01138 } 01139 01140 01141 template<class T> 01142 gdt::gdtlist<gdt::PQ_node_struct<T>*> 01143 gdt::PQ_tree<T>:: 01144 get_leaves 01145 () 01146 { 01147 return leaves; 01148 } 01149 01150 01151 template<class T> 01152 gdt::PQ_node_struct<T>* 01153 gdt::PQ_tree<T>:: 01154 find_leaf 01155 ( 01156 T value 01157 ) 01158 { 01159 return map_leaves[value]; 01160 } 01161 01162 01163 template<class T> 01164 bool 01165 gdt::PQ_tree<T>:: 01166 is_root 01167 ( 01168 PQ_node node 01169 ) 01170 { 01171 return (root==node); 01172 } 01173 01174 01175 template<class T> 01176 bool 01177 gdt::PQ_tree<T>:: 01178 pnode_sorting 01179 ( 01180 PQ_node node 01181 ) 01182 { 01183 PQ_node prec_node,temp_node,partial_node; 01184 if(node->type!=PNODE) 01185 return false; 01186 prec_node=node->full_children.head(); 01187 //temp_node=node->full_children.head()->link_right_side; 01188 temp_node=prec_node->link_right_side;// 01189 while(temp_node!=node->full_children.head()) 01190 { 01191 if(temp_node->label==EMPTY) 01192 { 01193 prec_node->link_right_side=temp_node; 01194 temp_node->link_left_side=prec_node; 01195 prec_node=temp_node; 01196 } 01197 temp_node=temp_node->link_right_side; 01198 } 01199 01200 //PQ_node nodes_array[node->full_children.size()];// 01201 PQ_node* nodes_array; 01202 nodes_array=new PQ_node[node->full_children.size()]; 01203 int l=0; 01204 forall(temp_node,node->full_children) 01205 { 01206 nodes_array[l]=temp_node; 01207 l++; 01208 } 01209 for(int i=1; i<node->full_children.size(); i++) 01210 { 01211 temp_node=nodes_array[i]; 01212 temp_node->link_right_side=nodes_array[i-1]; 01213 if(i==node->full_children.size()-1) 01214 temp_node->link_left_side=prec_node; 01215 else 01216 temp_node->link_left_side=nodes_array[i+1]; 01217 } 01218 if(node->full_children.size()==1) 01219 node->full_children.head()->link_left_side=prec_node; 01220 else 01221 node->full_children.head()->link_left_side=nodes_array[1];// 01222 prec_node->link_right_side=node->full_children.tail(); 01223 /* 01224 for(int i=1;i<node->full_children.size();i++) 01225 { 01226 temp_node=node->full_children.contents(node->full_children.get_item(i)); // 01227 temp_node -> link_right_side=node->full_children.contents(node->full_children.get_item(i-1)); 01228 if(i==node->full_children.size()-1) 01229 temp_node->link_left_side=prec_node; 01230 else 01231 temp_node ->link_left_side=node->full_children.contents(node->full_children.get_item(i+1)); 01232 } 01233 if(node->full_children.size()==1) 01234 node->full_children.head()->link_left_side=prec_node; 01235 else 01236 node->full_children.head()->link_left_side=node->full_children.contents(node->full_children.get_item(1)); 01237 prec_node->link_right_side=node->full_children.tail();*/ 01238 if(node->partial_children.size()>0) 01239 { 01240 partial_node=node->partial_children.head(); 01241 temp_node=node->full_children.head();// 01242 partial_node->link_right_side=temp_node->link_right_side; 01243 temp_node->link_right_side->link_left_side=partial_node; 01244 partial_node->link_left_side=temp_node; 01245 temp_node->link_right_side=partial_node; 01246 if(node->partial_children.size()==2) 01247 { 01248 temp_node=node->full_children.tail();// 01249 partial_node=node->partial_children.tail(); 01250 partial_node->link_left_side=temp_node->link_left_side; 01251 temp_node->link_left_side->link_right_side=partial_node; 01252 partial_node->link_right_side=temp_node; 01253 temp_node->link_left_side=partial_node; 01254 } 01255 } 01256 return true; 01257 } 01258 01259 01260 01261 template<class T> 01262 bool 01263 gdt::PQ_tree<T>:: 01264 qnode_reversing 01265 ( 01266 PQ_node node 01267 ) 01268 { 01269 PQ_node temp_pq,temp_node; 01270 if(node->type!=QNODE) 01271 return false; 01272 temp_pq=node->left_endmost; 01273 while(temp_pq!=NULL) 01274 { 01275 temp_node=temp_pq->link_right_side; 01276 temp_pq->link_right_side=temp_pq->link_left_side; 01277 temp_pq->link_left_side=temp_node; 01278 temp_pq=temp_node; 01279 } 01280 temp_pq=node->left_endmost; 01281 node->left_endmost=node->right_endmost; 01282 node->right_endmost=temp_pq; 01283 return true; 01284 } 01285 01286 01287 01288 template<class T> 01289 bool 01290 gdt::PQ_tree<T>:: 01291 assign_parent_to_draw_graph //da togliere serve per disegnare il grafo 01292 ( 01293 PQ_node node, 01294 int count 01295 ) 01296 { 01297 PQ_node temp_node,current_parent,child; 01298 /*forall(temp_node,blocked_list) 01299 cout<<temp_node->id<<" "; 01300 cout<<endl;*/ 01301 temp_node=blocked_list.head()->link_right_side; 01302 /*while(!(temp_node->is_endmost())) 01303 temp_node=temp_node->link_right_side;*/ 01304 01305 while(temp_node->link_right_side!=NULL)// 01306 temp_node=temp_node->link_right_side;// 01307 01308 child=temp_node; 01309 current_parent=child->parent; 01310 forall(temp_node,blocked_list) 01311 { 01312 temp_node->parent=current_parent; 01313 if(temp_node->label==FULL) 01314 current_parent->full_children.append(temp_node); 01315 } 01316 current_parent->label=PARTIAL; 01317 full_queue.append(current_parent); 01318 if(current_parent->parent!=NULL) 01319 current_parent->parent->partial_children.append(current_parent); 01320 current_parent->child_count=current_parent->child_count+count; 01321 return true; 01322 } 01323 01324 01325 01326 template<class T> 01327 void 01328 gdt::PQ_tree<T>:: 01329 add_leaf 01330 ( 01331 T value 01332 ) 01333 { 01334 PQ_node node,right_node,left_node,leaf; 01335 leaf=new(PQ_node_struct<T>); 01336 leaf->id=generate_id(); 01337 leaf->type=LEAF; 01338 leaf->value=value; 01339 if(number_of_nodes>1) 01340 { 01341 leaf->parent=root; 01342 right_node=leaves.head(); 01343 while(right_node->parent!=root) 01344 right_node=right_node->parent; 01345 left_node=right_node->link_left_side; 01346 leaf->link_right_side=right_node; 01347 leaf->link_left_side=left_node; 01348 right_node->link_left_side=leaf; 01349 if(left_node!=NULL) 01350 left_node->link_right_side=leaf; 01351 } 01352 else if (number_of_nodes==1) 01353 { 01354 leaf->link_right_side=root; 01355 leaf->link_left_side=root; 01356 root->link_right_side=leaf; 01357 root->link_left_side=leaf; 01358 node=new(PQ_node_struct<T>); 01359 node->id=generate_id(); 01360 node->type=PNODE; 01361 node->parent=NULL; 01362 node->child_count=2; 01363 number_of_nodes++; 01364 root->parent=node; 01365 leaf->parent=node; 01366 root=node; 01367 } 01368 else 01369 { 01370 leaf->parent=NULL; 01371 root=leaf; 01372 } 01373 number_of_nodes++; 01374 leaves.append(leaf); 01375 map_leaves[value]=leaf; 01376 } 01377 01378 01379 01380 template <class T> 01381 bool 01382 gdt::PQ_tree<T>:: 01383 bubble 01384 ( 01385 gdt::gdtlist<T> &S 01386 ) 01387 { 01388 //gdt::gdtlist<PQ_node> blocked_siblings, unblocked_siblings; non ci sono pių utilizzo link 01389 //stop5.start(); 01390 //stop1.start(); 01391 gdt::gdtlist<PQ_node> blocked_consecutive_siblings; 01392 T temp_i; 01393 int blocked_siblings; 01394 PQ_node temp_pq,current_parent,temp_node,pseudo_node; 01395 reset_tree(); 01396 forall(temp_i,S) 01397 { 01398 temp_pq=find_leaf(temp_i); 01399 if(temp_pq==NULL) 01400 gdt_error("A leaf doesn't exist"); 01401 queue.append(temp_pq); 01402 } 01403 //stop1.pause(); 01404 while((queue.size()+block_count+off_the_top)>1) 01405 { 01406 //stop2.start(); 01407 if(queue.empty()) 01408 { 01409 make_empty(); 01410 std::cout<<"Could not reduce {"; 01411 forall(temp_i,S) 01412 if(temp_i!=S.tail()) 01413 std::cout<<find_leaf(temp_i)->id<<","; 01414 std::cout<<S.tail()<<"}"<<std::endl; 01415 return false; 01416 } 01417 temp_pq=queue.pop(); 01418 blocked_siblings=0; 01419 //forall(temp_sibling,temp_pq->immediate_siblings)//TOLTO perchč non uso immediate_siblings 01420 // if(temp_sibling->mark==BLOCKED) 01421 // blocked_siblings.append(temp_sibling); 01422 // else if(temp_sibling->mark==UNBLOCKED) 01423 // unblocked_siblings.append(temp_sibling); 01424 //if (unblocked_siblings.size()>0) 01425 // { 01426 // temp_sibling=(PQ_node)unblocked_siblings.first(); 01427 // temp_pq->parent=temp_sibling->parent; 01428 // temp_pq->mark=UNBLOCKED; 01429 // } 01430 //else if(temp_pq->immediate_siblings.size()<2) 01431 // temp_pq->mark=UNBLOCKED; 01432 if((is_root(temp_pq))||(temp_pq->parent->type==PNODE)||(temp_pq->is_endmost())) 01433 temp_pq->mark=UNBLOCKED; 01434 else if((temp_pq->link_right_side->is_endmost())||(temp_pq->link_right_side->mark==UNBLOCKED)) 01435 { 01436 temp_pq->parent=temp_pq->link_right_side->parent; 01437 temp_pq->mark=UNBLOCKED; 01438 } 01439 else if((temp_pq->link_left_side->is_endmost())||(temp_pq->link_left_side->mark==UNBLOCKED)) 01440 { 01441 temp_pq->parent=temp_pq->link_left_side->parent; 01442 temp_pq->mark=UNBLOCKED; 01443 } 01444 else 01445 { 01446 temp_pq->mark=BLOCKED; 01447 blocked_nodes++; 01448 if((temp_pq->link_right_side->mark==BLOCKED) &&(temp_pq->link_left_side->mark==BLOCKED)) 01449 block_count--; 01450 else if((temp_pq->link_right_side->mark!=BLOCKED) &&(temp_pq->link_left_side->mark!=BLOCKED)) 01451 block_count++; 01452 blocked_list.append(temp_pq); 01453 //blocked_siblings=2; 01454 //block_count=2; 01455 } 01456 //stop2.pause(); 01457 //stop3.start(); 01458 if(temp_pq->mark==UNBLOCKED) 01459 { 01460 current_parent=temp_pq->parent; 01461 /*if(current_parent!=NULL) 01462 cout<<current_parent->id<<" "<<current_parent->pertinent_child_count<<endl;*/ 01463 if(((temp_pq->link_left_side!=NULL)&&(temp_pq->link_left_side->mark==BLOCKED)) || ((temp_pq->link_right_side!=NULL)&&(temp_pq->link_right_side->mark==BLOCKED))) 01464 { 01465 //blocked_siblings=1; 01466 temp_node=temp_pq; 01467 while(temp_node->link_left_side->mark==BLOCKED) 01468 { 01469 blocked_consecutive_siblings.append(temp_node->link_left_side); 01470 temp_node=temp_node->link_left_side; 01471 } 01472 temp_node=temp_pq; 01473 while(temp_node->link_right_side->mark==BLOCKED) 01474 { 01475 blocked_consecutive_siblings.append(temp_node->link_right_side); 01476 temp_node=temp_node->link_right_side; 01477 } 01478 forall(temp_node,blocked_consecutive_siblings) 01479 { 01480 temp_node->mark=UNBLOCKED; 01481 temp_node->parent=current_parent; 01482 blocked_list.remove(temp_node); 01483 current_parent->pertinent_child_count=current_parent->pertinent_child_count+1; 01484 } 01485 block_count--; 01486 blocked_nodes=blocked_nodes-blocked_consecutive_siblings.size(); 01487 blocked_consecutive_siblings.clear(); 01488 } 01489 if(current_parent==NULL) 01490 off_the_top=1; 01491 else 01492 { 01493 current_parent->pertinent_child_count=current_parent->pertinent_child_count+1; 01494 if(current_parent->mark==UNMARKED) 01495 { 01496 queue.append(current_parent); 01497 current_parent->mark=QUEUED; 01498 } 01499 } 01500 //block_count=block_count - blocked_siblings; 01501 //blocked_nodes=blocked_nodes-blocked_consecutive_siblings.size(); 01502 } 01503 //stop3.pause(); 01504 /*else 01505 { 01506 block_count=block_count + 1 - blocked_siblings; 01507 blocked_list.append(temp_pq); 01508 blocked_nodes=blocked_nodes + 1; 01509 }*/ 01510 } 01511 //stop4.start(); 01512 if(blocked_list.size()>1) 01513 { 01514 pseudo_node=new(PQ_node_struct<T>); 01515 pseudo_node->id=generate_id(); 01516 pseudo_node->type=PSEUDONODE; 01517 forall(temp_node,blocked_list) 01518 { 01519 temp_node->parent=pseudo_node; 01520 if(temp_node->link_right_side->mark==UNMARKED) 01521 pseudo_node->right_endmost=temp_node; 01522 else if(temp_node->link_left_side->mark==UNMARKED) 01523 pseudo_node->left_endmost=temp_node; 01524 } 01525 pseudo_node->child_count=blocked_list.size(); 01526 pseudo_node->pertinent_child_count=blocked_list.size(); 01527 } 01528 else if(blocked_list.size()==1) 01529 blocked_list.clear(); 01530 //stop4.pause(); 01531 //stop5.pause(); 01532 return true; 01533 } 01534 01535 01536 01537 template<class T> 01538 bool 01539 gdt::PQ_tree<T>:: 01540 template_L1 01541 ( 01542 PQ_node node 01543 ) 01544 { 01545 if(node->type!=LEAF) 01546 return false; 01547 //stop1.start(); 01548 node->label=FULL; 01549 if(!is_root(node)) 01550 node->parent->full_children.append(node); 01551 full_queue.append(node); 01552 node->pertinent_child_count=0;//?? 01553 node->pertinent_leaf_count=0;//?? 01554 node->mark=UNMARKED; 01555 //l1++; 01556 //stop1.pause(); 01557 return true; 01558 } 01559 01560 01561 template<class T> 01562 bool 01563 gdt::PQ_tree<T>:: 01564 template_P1 01565 ( 01566 PQ_node node 01567 ) 01568 { 01569 if(node->type!=PNODE) 01570 return false; 01571 if(node->child_count!=node->full_children.size())//basta per controllare se non ci sono partial o empty 01572 return false; 01573 //stop2.start(); 01574 node->label=FULL; 01575 if(!is_root(node)) 01576 node->parent->full_children.append(node); 01577 full_queue.append(node); 01578 node->pertinent_child_count=0;//?? 01579 node->pertinent_leaf_count=0;//?? 01580 node->mark=UNMARKED; 01581 //p1++; 01582 //stop2.pause(); 01583 return true; 01584 } 01585 01586 01587 template<class T> 01588 bool 01589 gdt::PQ_tree<T>:: 01590 template_P2 01591 ( 01592 PQ_node node 01593 ) 01594 { 01595 PQ_node full_node,temp_node; 01596 if(node->type!=PNODE) 01597 return false; 01598 if(node->full_children.size()==0) 01599 return false; 01600 if(node->partial_children.size()!=0) 01601 return false; 01602 if(node->full_children.size()==node->child_count) 01603 return false; 01604 //stop3.start(); 01605 full_node=new(PQ_node_struct<T>); 01606 full_node->id=generate_id(); 01607 full_node->type=PNODE; 01608 full_node->label=FULL;//tolgo 01609 full_queue.append(full_node); 01610 full_node->parent=node; 01611 pnode_sorting(node); 01612 forall(temp_node,node->full_children) 01613 { 01614 temp_node->parent=full_node; 01615 full_node->full_children.append(temp_node);//togliere chissā 01616 full_node->child_count++; 01617 } 01618 full_node->link_right_side=node->full_children.head()->link_right_side; 01619 full_node->link_left_side=node->full_children.tail()->link_left_side; 01620 full_node->link_right_side->link_left_side=full_node; 01621 full_node->link_left_side->link_right_side=full_node; 01622 node->full_children.head()->link_right_side=node->full_children.tail(); 01623 node->full_children.tail()->link_left_side=node->full_children.head(); 01624 node->child_count=node->child_count-node->full_children.size()+1; 01625 node->full_children.clear(); 01626 node->full_children.append(full_node);//tolgo 01627 number_of_nodes++; 01628 node->pertinent_child_count=0;//?? 01629 node->pertinent_leaf_count=0;//?? 01630 node->mark=UNMARKED; 01631 full_queue.append(node);// 01632 //p2++; 01633 //stop3.pause(); 01634 /*cout<<root->id<<endl; 01635 cout<<root->child_count<<endl; 01636 forall(temp_node,root->full_children) 01637 cout<<temp_node->id<<" "; 01638 cout<<endl; 01639 forall(temp_node,root->partial_children) 01640 cout<<temp_node->id<<" "; 01641 cout<<endl; 01642 temp_node=root->full_children.head()->link_right_side; 01643 while(temp_node!=root->full_children.head()) 01644 { 01645 cout<<temp_node->id<<" "; 01646 temp_node=temp_node->link_right_side; 01647 } 01648 cout<<endl; 01649 temp_node=root->full_children.head()->link_left_side; 01650 while(temp_node!=root->full_children.head()) 01651 { 01652 cout<<temp_node->id<<" "; 01653 temp_node=temp_node->link_left_side; 01654 } 01655 cout<<endl; 01656 forall(temp_node,root->full_children.head()->full_children) 01657 cout<<temp_node->id<<" "; 01658 cout<<endl; 01659 cout<<root->full_children.head()->child_count<<endl; 01660 temp_node=root->full_children.head()->full_children.head()->link_right_side; 01661 while(temp_node!=root->full_children.head()->full_children.head()) 01662 { 01663 cout<<temp_node->id<<" "; 01664 temp_node=temp_node->link_right_side; 01665 } 01666 cout<<endl; 01667 temp_node=root->full_children.head()->full_children.head()->link_left_side; 01668 while(temp_node!=root->full_children.head()->full_children.head()) 01669 { 01670 cout<<temp_node->id<<" "; 01671 temp_node=temp_node->link_left_side; 01672 } 01673 cout<<endl;*/ 01674 return true; 01675 } 01676 01677 01678 template<class T> 01679 bool 01680 gdt::PQ_tree<T>:: 01681 template_P3 01682 ( 01683 PQ_node node 01684 ) 01685 { 01686 PQ_node empty_node,full_node,temp_n; 01687 if(node->type!=PNODE) 01688 return false; 01689 if(node->full_children.size()==0) 01690 return false; 01691 if(node->partial_children.size()!=0) 01692 return false; 01693 if(node->full_children.size()==node->child_count) 01694 return false; 01695 //stop4.start(); 01696 pnode_sorting(node); 01697 if(node->child_count-node->full_children.size()>1) 01698 {//more than one empty child 01699 empty_node=new(PQ_node_struct<T>); 01700 number_of_nodes++; 01701 empty_node->id=generate_id(); 01702 empty_node->label=EMPTY;// togliere č automaticamente empty 01703 empty_node->parent=node; 01704 empty_node->type=PNODE; 01705 temp_n=node->full_children.head()->link_right_side; 01706 while(temp_n->label==EMPTY) 01707 { 01708 temp_n->parent=empty_node; 01709 empty_node->child_count++; 01710 temp_n=temp_n->link_right_side; 01711 } 01712 node->full_children.head()->link_right_side->link_left_side=node->full_children.tail()->link_left_side; 01713 node->full_children.tail()->link_left_side->link_right_side=node->full_children.head()->link_right_side; 01714 } 01715 else//one empty child 01716 empty_node=node->full_children.head()->link_right_side; 01717 if(node->full_children.size()>1) 01718 {//more than one full children 01719 full_node=new(PQ_node_struct<T>); 01720 number_of_nodes++; 01721 full_node->id=generate_id(); 01722 full_node->label=FULL; 01723 full_queue.append(full_node); 01724 full_node->parent=node; 01725 full_node->type=PNODE; 01726 node->full_children.head()->link_right_side=node->full_children.tail(); 01727 node->full_children.tail()->link_left_side=node->full_children.head(); 01728 forall(temp_n,node->full_children) 01729 { 01730 temp_n->parent=full_node; 01731 full_node->child_count++; 01732 full_node->full_children.append(temp_n); 01733 } 01734 } 01735 else//one full child 01736 full_node=node->full_children.head(); 01737 empty_node->link_right_side=full_node; 01738 empty_node->link_left_side=NULL; 01739 full_node->link_right_side=NULL; 01740 full_node->link_left_side=empty_node; 01741 node->child_count=2; 01742 node->type=QNODE; 01743 node->label=PARTIAL; 01744 full_queue.append(node); 01745 node->full_children.clear(); 01746 node->full_children.append(full_node); 01747 node->left_endmost=empty_node; 01748 node->right_endmost=full_node; 01749 node->parent->partial_children.append(node); 01750 node->pertinent_child_count=0;//?? 01751 node->pertinent_leaf_count=0;//?? 01752 node->mark=UNMARKED; 01753 //p3++; 01754 //stop4.pause(); 01755 /*cout<<root->id<<endl; 01756 cout<<root->child_count<<endl; 01757 forall(temp_n,root->full_children) 01758 cout<<temp_n->id<<" "; 01759 cout<<endl; 01760 forall(temp_n,root->partial_children) 01761 cout<<temp_n->id<<" "; 01762 cout<<endl; 01763 temp_n=root->full_children.head()->link_right_side; 01764 while(temp_n!=root->full_children.head()) 01765 { 01766 cout<<temp_n->id<<" "; 01767 temp_n=temp_n->link_right_side; 01768 } 01769 cout<<endl; 01770 temp_n=root->full_children.head()->link_left_side; 01771 while(temp_n!=root->full_children.head()) 01772 { 01773 cout<<temp_n->id<<" "; 01774 temp_n=temp_n->link_left_side; 01775 } 01776 cout<<endl; 01777 forall(temp_n,root->full_children.head()->link_right_side->link_right_side->full_children) 01778 cout<<temp_n->id<<" "; 01779 cout<<endl; 01780 cout<<root->full_children.head()->link_right_side->link_right_side->child_count<<endl; 01781 temp_n=root->full_children.head()->link_right_side->link_right_side->full_children.head()->link_right_side; 01782 while(temp_n!=root->full_children.head()->link_right_side->link_right_side->full_children.head()) 01783 { 01784 cout<<temp_n->id<<" "; 01785 temp_n=temp_n->link_right_side; 01786 } 01787 cout<<endl; 01788 temp_n=root->full_children.head()->link_right_side->link_right_side->full_children.head()->link_left_side; 01789 while(temp_n!=root->full_children.head()->link_right_side->link_right_side->full_children.head()) 01790 { 01791 cout<<temp_n->id<<" "; 01792 temp_n=temp_n->link_left_side; 01793 } 01794 cout<<endl; 01795 forall(temp_n,root->full_children.head()->link_right_side->link_right_side->partial_children) 01796 cout<<temp_n->id<<" "; 01797 cout<<endl;*/ 01798 return true; 01799 } 01800 01801 01802 template<class T> 01803 bool 01804 gdt::PQ_tree<T>:: 01805 template_P4 01806 ( 01807 PQ_node node 01808 ) 01809 { 01810 PQ_node partial_node,temp_n,full_node,current_parent; 01811 if(node->type!=PNODE) 01812 return false; 01813 if(node->partial_children.size()!=1) 01814 return false; 01815 //stop5.start(); 01816 partial_node=node->partial_children.head(); 01817 if(node->full_children.size()!=0) 01818 { 01819 pnode_sorting(node); 01820 if(node->full_children.size()>1) 01821 { 01822 full_node=new(PQ_node_struct<T>); 01823 number_of_nodes++; 01824 full_node->id=generate_id(); 01825 full_node->label=FULL;//tolgo 01826 full_node->type=PNODE; 01827 full_queue.append(full_node);//tolgo ATTENZIONE partial_node->full_children.append(full_node); 01828 partial_node->link_left_side=node->full_children.tail()->link_left_side; 01829 node->full_children.tail()->link_left_side->link_right_side=partial_node; 01830 node->full_children.head()->link_right_side=node->full_children.tail(); 01831 node->full_children.tail()->link_left_side=node->full_children.head(); 01832 forall(temp_n,node->full_children) 01833 { 01834 temp_n->parent=full_node; 01835 full_node->child_count++; 01836 full_node->full_children.append(temp_n); 01837 } 01838 } 01839 else if(node->full_children.size()==1) 01840 { 01841 full_node=node->full_children.head(); 01842 if(node->child_count-node->full_children.size()-node->partial_children.size()!=0) 01843 { 01844 partial_node->link_left_side=full_node->link_left_side; 01845 full_node->link_left_side->link_right_side=partial_node; 01846 } 01847 else 01848 { 01849 partial_node->link_right_side=NULL; 01850 partial_node->link_left_side=NULL; 01851 } 01852 full_node->link_right_side=NULL; 01853 full_node->link_left_side=NULL; 01854 } 01855 full_node->parent=partial_node; 01856 partial_node->child_count++; 01857 partial_node->full_children.append(full_node); 01858 if(partial_node->left_endmost->label==FULL) 01859 { 01860 partial_node->left_endmost->link_left_side=full_node; 01861 full_node->link_right_side=partial_node->left_endmost; 01862 partial_node->left_endmost=full_node; 01863 } 01864 else 01865 { 01866 partial_node->right_endmost->link_right_side=full_node; 01867 full_node->link_left_side=partial_node->right_endmost; 01868 partial_node->right_endmost=full_node; 01869 } 01870 node->child_count=node->child_count-node->full_children.size(); 01871 node->full_children.clear(); 01872 } 01873 node->pertinent_child_count=0;//?? 01874 node->pertinent_leaf_count=0;//?? 01875 node->mark=UNMARKED; 01876 if(node->child_count==1) 01877 { 01878 if(!is_root(node)) 01879 { 01880 current_parent=node->parent; 01881 partial_node->parent=current_parent; 01882 current_parent->partial_children.append(partial_node); 01883 if(current_parent->right_endmost==node) 01884 current_parent->right_endmost=partial_node; 01885 else if(current_parent->left_endmost==node) 01886 current_parent->left_endmost=partial_node; 01887 partial_node->link_right_side=node->link_right_side; 01888 if(node->link_right_side!=NULL) 01889 node->link_right_side->link_left_side=partial_node; 01890 partial_node->link_left_side=node->link_left_side; 01891 if(node->link_left_side!=NULL) 01892 node->link_left_side->link_right_side=partial_node; 01893 full_queue.append(current_parent);// 01894 } 01895 else 01896 { 01897 root=partial_node; 01898 partial_node->parent=NULL; 01899 } 01900 delete(node); 01901 number_of_nodes--; 01902 } 01903 else// 01904 full_queue.append(node);// 01905 //p4++; 01906 //stop5.pause(); 01907 /*cout<<root->id<<endl; 01908 cout<<root->child_count<<endl; 01909 forall(temp_n,root->full_children) 01910 cout<<temp_n->id<<" "; 01911 cout<<endl; 01912 forall(temp_n,root->partial_children) 01913 cout<<temp_n->id<<" "; 01914 cout<<endl; 01915 if(root->partial_children.size()>0) 01916 { 01917 temp_n=root->partial_children.head()->link_right_side; 01918 while(temp_n!=root->partial_children.head()) 01919 { 01920 cout<<temp_n->id<<" "; 01921 temp_n=temp_n->link_right_side; 01922 } 01923 cout<<endl; 01924 temp_n=root->partial_children.head()->link_left_side; 01925 while(temp_n!=root->partial_children.head()) 01926 { 01927 cout<<temp_n->id<<" "; 01928 temp_n=temp_n->link_left_side; 01929 } 01930 cout<<endl; 01931 cout<<root->partial_children.head()->child_count<<endl; 01932 forall(temp_n,root->partial_children.head()->full_children) 01933 cout<<temp_n->id<<" "; 01934 cout<<endl; 01935 forall(temp_n,root->partial_children.head()->partial_children) 01936 cout<<temp_n->id<<" "; 01937 cout<<endl; 01938 temp_n=root->partial_children.head()->full_children.head()->link_right_side; 01939 while(temp_n!=NULL) 01940 { 01941 cout<<temp_n->id<<" "; 01942 temp_n=temp_n->link_right_side; 01943 } 01944 cout<<endl; 01945 temp_n=root->partial_children.head()->full_children.head()->link_left_side; 01946 while(temp_n!=NULL) 01947 { 01948 cout<<temp_n->id<<" "; 01949 temp_n=temp_n->link_left_side; 01950 } 01951 cout<<endl; 01952 }*/ 01953 /*forall(temp_pq,root->partial_children.head()->full_children) 01954 cout<<temp_pq->id<<" "; 01955 cout<<endl; 01956 temp_pq=root->partial_children.head()->full_children.head()->link_right_side; 01957 while(temp_pq!=NULL) 01958 { 01959 cout<<temp_pq->id<<" "; 01960 temp_pq=temp_pq->link_right_side; 01961 } 01962 cout<<endl; 01963 temp_pq=root->partial_children.head()->full_children.head()->link_left_side; 01964 while(temp_pq!=NULL) 01965 { 01966 cout<<temp_pq->id<<" "; 01967 temp_pq=temp_pq->link_left_side; 01968 } 01969 cout<<endl; 01970 cout<<find_leaf(1)->parent->id<<endl;*/ 01971 return true; 01972 } 01973 01974 01975 template<class T> 01976 bool 01977 gdt::PQ_tree<T>:: 01978 template_P5 01979 ( 01980 PQ_node node 01981 ) 01982 { 01983 int empty_count=0; 01984 PQ_node partial,empty_endmost,full_endmost,temp_pq,empty_sibling,full,empty; 01985 if(node->type!=PNODE) 01986 return false; 01987 if(node->partial_children.size()!=1)//qua conviene lista e non due partial children 01988 return false; 01989 //stop6.start(); 01990 partial=node->partial_children.head();//the unique element in partial_children 01991 if(partial->left_endmost->label==FULL) 01992 { 01993 full_endmost=partial->left_endmost; 01994 empty_endmost=partial->right_endmost; 01995 } 01996 else 01997 { 01998 full_endmost=partial->right_endmost; 01999 empty_endmost=partial->left_endmost; 02000 } 02001 temp_pq=partial->link_right_side; 02002 while(temp_pq!=partial) //conto gli empty e se uno lo memorizzo 02003 { 02004 if(temp_pq->label==EMPTY) 02005 { 02006 empty_count++; 02007 empty_sibling=temp_pq; 02008 } 02009 temp_pq=temp_pq->link_right_side; 02010 } 02011 /*if(empty_count!=1) 02012 empty_sibling=NULL;*/ 02013 partial->parent=node->parent; 02014 partial->pertinent_leaf_count=node->pertinent_leaf_count; 02015 //partial->label=PARTIAL; 02016 partial->parent->partial_children.append(partial);//qua va bene la lista non so due elementi 02017 partial->remove_from_circular_link(); 02018 partial->link_right_side=node->link_right_side; 02019 /*if(blocked_list.del(node)!=NULL) 02020 blocked_list.append(partial);*/ //?? 02021 if(blocked_list.search(node)!=NULL) 02022 { 02023 blocked_list.remove(node); 02024 blocked_list.append(partial); 02025 } 02026 if(partial->link_right_side!=NULL) 02027 partial->link_right_side->link_left_side=partial; 02028 partial->link_left_side=node->link_left_side; 02029 if(partial->link_left_side!=NULL) 02030 partial->link_left_side->link_right_side=partial; 02031 if(partial->parent->left_endmost==node) 02032 partial->parent->left_endmost=partial; 02033 else if(partial->parent->right_endmost==node) 02034 partial->parent->right_endmost=partial; 02035 if(node->full_children.size()>0) 02036 { 02037 if(node->full_children.size()==1) 02038 { 02039 full=node->full_children.head(); 02040 full->remove_from_circular_link(); 02041 } 02042 else 02043 { 02044 full=new(PQ_node_struct<T>); 02045 number_of_nodes++; 02046 full->id=generate_id(); 02047 full->type=PNODE; 02048 full->label=FULL; 02049 full_queue.append(full); 02050 forall(temp_pq,node->full_children) 02051 { 02052 temp_pq->remove_from_circular_link(); 02053 temp_pq->parent=full; 02054 full->full_children.append(temp_pq); 02055 } 02056 02057 //PQ_node nodes_array[node->full_children.size()];// 02058 PQ_node* nodes_array; 02059 nodes_array=new PQ_node[node->full_children.size()]; 02060 int l=0; 02061 forall(temp_pq,node->full_children) 02062 { 02063 nodes_array[l]=temp_pq; 02064 l++; 02065 } 02066 for(int i=1;i<node->full_children.size()-1;i++) 02067 { 02068 nodes_array[i]->link_left_side=nodes_array[i-1]; 02069 nodes_array[i]->link_right_side=nodes_array[i+1]; 02070 } 02071 nodes_array[0]->link_left_side=nodes_array[node->full_children.size()-1]; 02072 nodes_array[0]->link_right_side=nodes_array[1]; 02073 nodes_array[node->full_children.size()-1] -> link_left_side=nodes_array[node->full_children.size()-2]; 02074 nodes_array[node->full_children.size()-1]->link_right_side=nodes_array[0];// 02075 /* 02076 for(int i=0;i<node->full_children.size();i++) 02077 { 02078 node->full_children.contents(node->full_children.get_item(i))->link_left_side=node->full_children.contents(node->full_children.cyclic_pred(node->full_children.get_item(i))); 02079 node->full_children.contents(node->full_children.get_item(i))->link_right_side=node->full_children.contents(node->full_children.cyclic_succ(node->full_children.get_item(i))); 02080 }*/ 02081 full->child_count=node->full_children.size(); 02082 } 02083 full->parent=partial; 02084 partial->full_children.append(full); 02085 partial->child_count++; 02086 if(full_endmost->link_left_side==NULL) 02087 { 02088 full_endmost->link_left_side=full; 02089 full->link_right_side=full_endmost; 02090 full->link_left_side=NULL; 02091 partial->left_endmost=full; 02092 } 02093 else 02094 { 02095 full_endmost->link_right_side=full; 02096 full->link_left_side=full_endmost; 02097 full->link_right_side=NULL; 02098 partial->right_endmost=full; 02099 } 02100 /*if(partial->left_endmost==full_endmost) 02101 partial->left_endmost=full; 02102 else 02103 partial->right_endmost=full;*/ 02104 } 02105 //number_empty=node->child_count-node->full_children.size()-node->partial_children.size(); 02106 if(empty_count>0) 02107 { 02108 if(empty_count==1) 02109 empty=empty_sibling; 02110 else 02111 { 02112 empty=new(PQ_node_struct<T>); 02113 number_of_nodes++; 02114 empty->id=generate_id(); 02115 empty->type=PNODE; 02116 empty->label=EMPTY; 02117 temp_pq=empty_sibling->link_right_side; 02118 while(temp_pq!=empty_sibling) 02119 { 02120 temp_pq->parent=empty; 02121 temp_pq=temp_pq->link_right_side; 02122 } 02123 empty_sibling->parent=empty; 02124 empty->child_count=empty_count; 02125 } 02126 empty->parent=partial; 02127 partial->child_count++; 02128 if(empty_endmost->link_left_side==NULL) 02129 { 02130 empty_endmost->link_left_side=empty; 02131 empty->link_right_side=empty_endmost; 02132 empty->link_left_side=NULL; 02133 partial->left_endmost=empty; 02134 } 02135 else 02136 { 02137 empty_endmost->link_right_side=empty; 02138 empty->link_left_side=empty_endmost; 02139 empty->link_right_side=NULL; 02140 partial->right_endmost=empty; 02141 } 02142 /*if(partial->left_endmost==empty_endmost) 02143 partial->left_endmost=empty; 02144 else 02145 partial->right_endmost=empty;*/ 02146 } 02147 delete(node); 02148 number_of_nodes--; 02149 partial->pertinent_child_count=0;//?? 02150 partial->pertinent_leaf_count=0;//?? 02151 partial->mark=UNMARKED; 02152 //p5++; 02153 //stop6.pause(); 02154 /*cout<<root->id<<endl; 02155 cout<<root->child_count<<endl; 02156 forall(temp_pq,root->full_children) 02157 cout<<temp_pq->id<<" "; 02158 cout<<endl; 02159 forall(temp_pq,root->partial_children) 02160 cout<<temp_pq->id<<" "; 02161 cout<<endl; 02162 cout<<root->partial_children.head()->link_right_side->link_right_side->id<<endl;*/ 02163 /*temp_pq=root->partial_children.head()->link_right_side; 02164 while(temp_pq!=root->partial_children.head()) 02165 { 02166 cout<<temp_pq->id<<" "; 02167 temp_pq=temp_pq->link_right_side; 02168 } 02169 cout<<endl; 02170 temp_pq=root->partial_children.head()->link_left_side; 02171 while(temp_pq!=root->partial_children.head()) 02172 { 02173 cout<<temp_pq->id<<" "; 02174 temp_pq=temp_pq->link_left_side; 02175 } 02176 cout<<endl; 02177 cout<<root->partial_children.head()->child_count<<endl; 02178 forall(temp_pq,root->partial_children.head()->full_children) 02179 cout<<temp_pq->id<<" "; 02180 cout<<endl; 02181 forall(temp_pq,root->partial_children.head()->partial_children) 02182 cout<<temp_pq->id<<" "; 02183 cout<<endl; 02184 temp_pq=root->partial_children.head()->full_children.head()->link_right_side; 02185 while(temp_pq!=NULL) 02186 { 02187 cout<<temp_pq->id<<" "; 02188 temp_pq=temp_pq->link_right_side; 02189 } 02190 cout<<endl; 02191 temp_pq=root->partial_children.head()->full_children.head()->link_left_side; 02192 while(temp_pq!=NULL) 02193 { 02194 cout<<temp_pq->id<<" "; 02195 temp_pq=temp_pq->link_left_side; 02196 } 02197 cout<<endl;*/ 02198 return true; 02199 } 02200 02201 02202 template<class T> 02203 bool 02204 gdt::PQ_tree<T>:: 02205 template_P6 02206 ( 02207 PQ_node node 02208 ) 02209 { 02210 if(node->type!=PNODE) 02211 return false; 02212 if(node->partial_children.size()!=2) 02213 return false; 02214 PQ_node full_node,partial_node,q_partial_node,temp_node,temp_n,prec_node,current_parent; 02215 //stop7.start(); 02216 if(node->full_children.size()!=0) 02217 { 02218 pnode_sorting(node); 02219 } 02220 else //vedere 02221 { 02222 prec_node=node->partial_children.head(); 02223 //temp_n=node->partial_children.head()->link_right_side; 02224 temp_n=prec_node->link_right_side;// 02225 while(temp_n!=node->partial_children.head()) 02226 { 02227 if(temp_n->label==EMPTY) 02228 { 02229 prec_node->link_right_side=temp_n; 02230 temp_n->link_left_side=prec_node; 02231 prec_node=temp_n; 02232 } 02233 temp_n=temp_n->link_right_side; 02234 } 02235 prec_node->link_right_side=node->partial_children.tail(); 02236 node->partial_children.tail()->link_left_side=prec_node; 02237 node->partial_children.tail()->link_right_side=node->partial_children.head(); 02238 node->partial_children.head()->link_left_side=node->partial_children.tail(); 02239 } 02240 q_partial_node=new(PQ_node_struct<T>); 02241 number_of_nodes++; 02242 q_partial_node->id=generate_id(); 02243 q_partial_node->label=PARTIAL; 02244 q_partial_node->type=QNODE; 02245 full_queue.append(q_partial_node); 02246 if(node->child_count-node->full_children.size()-2>0) //there are empty children 02247 { 02248 q_partial_node->link_right_side=node->partial_children.head()->link_right_side; 02249 node->partial_children.head()->link_right_side->link_left_side=q_partial_node; 02250 q_partial_node->link_left_side=node->partial_children.tail()->link_left_side; 02251 node->partial_children.tail()->link_left_side->link_right_side=q_partial_node; 02252 } 02253 if(node->full_children.size()>0) 02254 { 02255 if(node->full_children.size()>1) 02256 { 02257 full_node=new(PQ_node_struct<T>); 02258 number_of_nodes++; 02259 full_node->id=generate_id(); 02260 full_node->label=FULL;//tolgo 02261 full_node->type=PNODE; 02262 full_queue.append(full_node);//tolgo ATTENZIONE partial_node->full_children.append(full_node); 02263 node->full_children.head()->link_right_side=node->full_children.tail(); 02264 node->full_children.tail()->link_left_side=node->full_children.head(); 02265 forall(temp_n,node->full_children) 02266 { 02267 temp_n->parent=full_node; 02268 full_node->child_count++; 02269 full_node->full_children.append(temp_n); 02270 } 02271 } 02272 else //if(node->full_children==1) 02273 full_node=node->full_children.head(); 02274 full_node->parent=q_partial_node; 02275 q_partial_node->child_count++; 02276 q_partial_node->full_children.append(full_node); 02277 } 02278 partial_node=node->partial_children.pop(); 02279 if(partial_node->left_endmost->label==EMPTY) 02280 { 02281 q_partial_node->left_endmost=partial_node->left_endmost; 02282 temp_node=partial_node->left_endmost; 02283 while(temp_node!=NULL) 02284 { 02285 temp_node->parent=q_partial_node; 02286 prec_node=temp_node; 02287 temp_node=temp_node->link_right_side; 02288 } 02289 } 02290 else //if(partial_node->right_endmost->label==EMPTY) 02291 { 02292 q_partial_node->left_endmost=partial_node->right_endmost; 02293 temp_node=partial_node->right_endmost; 02294 while(temp_node!=NULL) 02295 { 02296 temp_node->parent=q_partial_node; 02297 temp_n=temp_node->link_left_side; 02298 temp_node->link_left_side=temp_node->link_right_side; 02299 temp_node->link_right_side=temp_n; 02300 prec_node=temp_node; 02301 temp_node=temp_n; 02302 } 02303 } 02304 if(node->full_children.size()>0) 02305 { 02306 prec_node->link_right_side=full_node; 02307 full_node->link_left_side=prec_node; 02308 q_partial_node->right_endmost=full_node; 02309 } 02310 else 02311 q_partial_node->right_endmost=prec_node; 02312 q_partial_node->child_count=q_partial_node->child_count+partial_node->child_count; 02313 forall(temp_n,partial_node->full_children) 02314 q_partial_node->full_children.append(temp_n); 02315 temp_n=full_queue.pop(); 02316 while(temp_n!=partial_node) 02317 { 02318 full_queue.append(temp_n); 02319 temp_n=full_queue.pop(); 02320 } 02321 delete(partial_node); 02322 number_of_nodes--; 02323 partial_node=node->partial_children.pop(); 02324 if(partial_node->left_endmost->label==FULL) 02325 { 02326 q_partial_node->right_endmost->link_right_side=partial_node->left_endmost; 02327 partial_node->left_endmost->link_left_side=q_partial_node->right_endmost; 02328 q_partial_node->right_endmost=partial_node->right_endmost; 02329 temp_node=partial_node->left_endmost; 02330 while(temp_node!=NULL) 02331 { 02332 temp_node->parent=q_partial_node; 02333 temp_node=temp_node->link_right_side; 02334 } 02335 } 02336 else //if(partial_node->right_endmost->label==FULL) 02337 { 02338 q_partial_node->right_endmost->link_right_side=partial_node->right_endmost; 02339 partial_node->right_endmost->link_right_side=q_partial_node->right_endmost; 02340 q_partial_node->right_endmost=partial_node->left_endmost; 02341 temp_node=partial_node->right_endmost; 02342 while(temp_node!=NULL) 02343 { 02344 temp_node->parent=q_partial_node; 02345 temp_n=temp_node->link_left_side; 02346 temp_node->link_left_side=temp_node->link_right_side; 02347 temp_node->link_right_side=temp_n; 02348 temp_node=temp_n; 02349 } 02350 } 02351 q_partial_node->child_count=q_partial_node->child_count+partial_node->child_count; 02352 forall(temp_n,partial_node->full_children) 02353 q_partial_node->full_children.append(temp_n); 02354 temp_n=full_queue.pop(); 02355 while(temp_n!=partial_node) 02356 { 02357 full_queue.append(temp_n); 02358 temp_n=full_queue.pop(); 02359 } 02360 delete(partial_node); 02361 number_of_nodes--; 02362 q_partial_node->parent=node; 02363 node->child_count=node->child_count-node->full_children.size()-2+1; 02364 node->full_children.clear(); 02365 node->partial_children.append(q_partial_node); //lo posso togliere 02366 node->pertinent_child_count=0;//?? 02367 node->pertinent_leaf_count=0;//?? 02368 node->mark=UNMARKED; 02369 if(node->child_count==1) 02370 { 02371 if(!is_root(node)) 02372 { 02373 current_parent=node->parent; 02374 q_partial_node->parent=current_parent; 02375 current_parent->partial_children.append(q_partial_node); 02376 if(current_parent->right_endmost==node) 02377 current_parent->right_endmost=q_partial_node; 02378 else if(current_parent->left_endmost==node) 02379 current_parent->left_endmost=q_partial_node; 02380 q_partial_node->link_right_side=node->link_right_side; 02381 if(node->link_right_side!=NULL) 02382 node->link_right_side->link_left_side=q_partial_node; 02383 q_partial_node->link_left_side=node->link_left_side; 02384 if(node->link_left_side!=NULL) 02385 node->link_left_side->link_right_side=q_partial_node; 02386 full_queue.append(current_parent);// 02387 } 02388 else 02389 { 02390 root=q_partial_node; 02391 q_partial_node->parent=NULL; 02392 } 02393 delete(node); 02394 number_of_nodes--; 02395 } 02396 else 02397 full_queue.append(node);// 02398 //p6++; 02399 //stop7.pause(); 02400 /*cout<<root->id<<endl; 02401 cout<<root->child_count<<endl; 02402 forall(temp_n,root->full_children) 02403 cout<<temp_n->id<<" "; 02404 cout<<endl; 02405 forall(temp_n,root->partial_children) 02406 cout<<temp_n->id<<" "; 02407 cout<<endl; 02408 temp_n=root->partial_children.head()->link_right_side; 02409 while(temp_n!=root->partial_children.head()) 02410 { 02411 cout<<temp_n->id<<" "; 02412 temp_n=temp_n->link_right_side; 02413 } 02414 cout<<endl; 02415 temp_n=root->partial_children.head()->link_left_side; 02416 while(temp_n!=root->partial_children.head()) 02417 { 02418 cout<<temp_n->id<<" "; 02419 temp_n=temp_n->link_left_side; 02420 } 02421 cout<<endl; 02422 cout<<root->partial_children.head()->child_count<<endl; 02423 forall(temp_n,root->partial_children.head()->full_children) 02424 cout<<temp_n->id<<" "; 02425 cout<<endl; 02426 forall(temp_n,root->partial_children.head()->partial_children) 02427 cout<<temp_n->id<<" "; 02428 cout<<endl; 02429 temp_n=root->partial_children.head()->full_children.head()->link_right_side; 02430 while(temp_n!=NULL) 02431 { 02432 cout<<temp_n->id<<" "; 02433 temp_n=temp_n->link_right_side; 02434 } 02435 cout<<endl; 02436 temp_n=root->partial_children.head()->full_children.head()->link_left_side; 02437 while(temp_n!=NULL) 02438 { 02439 cout<<temp_n->id<<" "; 02440 temp_n=temp_n->link_left_side; 02441 } 02442 cout<<endl;*/ 02443 /*forall(temp_pq,root->partial_children.head()->full_children) 02444 cout<<temp_pq->id<<" "; 02445 cout<<endl; 02446 temp_pq=root->partial_children.head()->full_children.head()->link_right_side; 02447 while(temp_pq!=NULL) 02448 { 02449 cout<<temp_pq->id<<" "; 02450 temp_pq=temp_pq->link_right_side; 02451 } 02452 cout<<endl; 02453 temp_pq=root->partial_children.head()->full_children.head()->link_left_side; 02454 while(temp_pq!=NULL) 02455 { 02456 cout<<temp_pq->id<<" "; 02457 temp_pq=temp_pq->link_left_side; 02458 } 02459 cout<<endl; 02460 cout<<find_leaf(1)->parent->id<<endl;*/ 02461 return true; 02462 } 02463 02464 02465 template<class T> 02466 bool 02467 gdt::PQ_tree<T>:: 02468 template_Q1 02469 ( 02470 PQ_node node 02471 ) 02472 { 02473 if(node->type!=QNODE) 02474 return false; 02475 if(node->child_count!=node->full_children.size()) 02476 return false; 02477 //stop8.start(); 02478 node->label=FULL; 02479 if(!is_root(node)) 02480 node->parent->full_children.append(node); 02481 full_queue.append(node); 02482 node->pertinent_child_count=0;//?? 02483 node->pertinent_leaf_count=0;//?? 02484 node->mark=UNMARKED; 02485 //q1++; 02486 //stop8.pause(); 02487 return true; 02488 } 02489 02490 02491 template<class T> 02492 bool 02493 gdt::PQ_tree<T>:: 02494 template_Q2 02495 ( 02496 PQ_node node 02497 ) 02498 { 02499 int full_count=0; 02500 PQ_node temp_pq,node_y,child_full_endmost,full_sibling,child_empty_endmost,empty_sibling; 02501 if(node->type!=QNODE) 02502 return false; 02503 //if node č uno pseudonode return false 02504 if(node->partial_children.size()>1) 02505 return false; 02506 if(node->full_children.size()>0) 02507 { 02508 //if(((node->endmost1->label==FULL)&&(node->endmost2->label==FULL))||((node->endmost1->label==EMPTY) &&(node->endmost2->label==EMPTY))) 02509 // return false; //vedere 02510 forall(temp_pq,node->full_children) 02511 if((temp_pq==node->left_endmost)||(temp_pq==node->right_endmost)) 02512 { 02513 full_count++; 02514 node_y=temp_pq; 02515 } 02516 if(full_count!=1) 02517 return false; 02518 temp_pq=node_y; 02519 if(node_y->link_left_side==NULL) //controlla che non ci sono alternanze full ed empty 02520 for(int i=0;i<node->full_children.size();i++) 02521 { 02522 if(temp_pq->label!=FULL) 02523 return false; 02524 temp_pq=temp_pq->link_right_side; 02525 } 02526 else 02527 for(int i=0;i<node->full_children.size();i++) 02528 { 02529 if(temp_pq->label!=FULL) 02530 return false; 02531 temp_pq=temp_pq->link_left_side; 02532 } 02533 if(node->partial_children.size()==1) 02534 if(temp_pq->label!=PARTIAL) 02535 return false; 02536 } 02537 else if((node->left_endmost->label==EMPTY)&&(node->right_endmost->label==EMPTY)) 02538 return false; 02539 //stop9.start(); 02540 node->label=PARTIAL; 02541 if(node->parent!=NULL) 02542 node->parent->partial_children.append(node); 02543 //full_queue.append(node); 02544 if(node->partial_children.size()>0) 02545 { 02546 node_y=node->partial_children.pop(); 02547 if(node_y->left_endmost->label==FULL) 02548 { 02549 child_full_endmost=node_y->left_endmost; 02550 child_empty_endmost=node_y->right_endmost; 02551 temp_pq=child_full_endmost; 02552 /*while(temp_pq->label==FULL) 02553 { 02554 node->full_children.append(temp_pq); 02555 temp_pq=temp_pq->link_right_side; 02556 }*/ //giā messo sotto per disegnare il grafo 02557 } 02558 else if(node_y->right_endmost->label==FULL) 02559 { 02560 child_full_endmost=node_y->right_endmost; 02561 child_empty_endmost=node_y->left_endmost; 02562 temp_pq=child_full_endmost; 02563 /*while(temp_pq->label==FULL) 02564 { 02565 node->full_children.append(temp_pq); 02566 temp_pq=temp_pq->link_left_side; 02567 }*/ //giā messo sotto per disegnare il grafo 02568 } 02569 if((node->left_endmost!=node_y)&&(node_y->link_left_side->label==FULL)) 02570 { 02571 if(node_y->left_endmost->label==EMPTY) 02572 qnode_reversing(node_y); 02573 full_sibling=node_y->link_left_side; 02574 full_sibling->link_right_side=child_full_endmost; 02575 child_full_endmost->link_left_side=full_sibling; 02576 } 02577 else if((node->right_endmost!=node_y)&&(node_y->link_right_side->label==FULL)) 02578 { 02579 if(node_y->right_endmost->label==EMPTY) 02580 qnode_reversing(node_y); 02581 full_sibling=node_y->link_right_side; 02582 full_sibling->link_left_side=child_full_endmost; 02583 child_full_endmost->link_right_side=full_sibling; 02584 } 02585 /*else //node_y non ha sibling con label full 02586 { 02587 if(node->left_endmost==node_y) 02588 node->left_endmost=child_full_endmost; 02589 else 02590 node->right_endmost=child_full_endmost; 02591 }*/ 02592 if((node->left_endmost!=node_y)&&(node_y->link_left_side->label==EMPTY)) 02593 { 02594 if(node_y->left_endmost->label==FULL) 02595 qnode_reversing(node_y); 02596 empty_sibling=node_y->link_left_side; 02597 empty_sibling->link_right_side=child_empty_endmost; 02598 child_empty_endmost->link_left_side=empty_sibling; 02599 } 02600 else if((node->right_endmost!=node_y)&&(node_y->link_right_side->label==EMPTY)) 02601 { 02602 if(node_y->right_endmost->label==FULL) 02603 qnode_reversing(node_y); 02604 empty_sibling=node_y->link_right_side; 02605 empty_sibling->link_left_side=child_empty_endmost; 02606 child_empty_endmost->link_right_side=empty_sibling; 02607 } 02608 else //node_y non ha sibling con label empty 02609 { 02610 if(node->left_endmost==node_y) 02611 node->left_endmost=child_empty_endmost; 02612 else 02613 node->right_endmost=child_empty_endmost; 02614 } 02615 //child_empty_endmost->parent=node; giā messo sotto per disegnare il grafo 02616 //node->child_count++; 02617 if(node->full_children.size()==0) 02618 if(node->left_endmost==node_y) 02619 node->left_endmost=child_full_endmost; 02620 else 02621 node->right_endmost=child_full_endmost; 02622 //child_full_endmost->parent=node; giā messo sotto per disegnare il grafo 02623 //node->child_count++; 02624 temp_pq=node_y->left_endmost; //questo č per disegnare il grafo da qui... 02625 while(temp_pq!=NULL) 02626 { 02627 temp_pq->parent=node; 02628 if(temp_pq->label==FULL) 02629 node->full_children.append(temp_pq); 02630 temp_pq=temp_pq->link_right_side; 02631 } //...a qui 02632 node->child_count=node->child_count+node_y->child_count; 02633 temp_pq=full_queue.pop(); 02634 while(temp_pq!=node_y) 02635 { 02636 full_queue.append(temp_pq); 02637 temp_pq=full_queue.pop(); 02638 } 02639 delete(node_y); 02640 node->child_count--; 02641 number_of_nodes--; 02642 //node->partial_children.clear(); 02643 } 02644 node->pertinent_child_count=0;//?? 02645 node->pertinent_leaf_count=0;//?? 02646 node->mark=UNMARKED; 02647 full_queue.append(node);// 02648 //q2++; 02649 //stop9.pause(); 02650 /*cout<<root->id<<endl; 02651 forall(temp_pq,root->full_children) 02652 cout<<temp_pq->id<<" "; 02653 cout<<endl; 02654 forall(temp_pq,root->partial_children) 02655 cout<<temp_pq->id<<" "; 02656 cout<<endl; 02657 temp_pq=root->full_children.head()->link_right_side; 02658 while(temp_pq!=root->full_children.head()) 02659 { 02660 cout<<temp_pq->id<<" "; 02661 temp_pq=temp_pq->link_right_side; 02662 } 02663 cout<<endl; 02664 temp_pq=root->full_children.head()->link_left_side; 02665 while(temp_pq!=root->full_children.head()) 02666 { 02667 cout<<temp_pq->id<<" "; 02668 temp_pq=temp_pq->link_left_side; 02669 } 02670 cout<<endl; 02671 forall(temp_pq,root->partial_children.head()->full_children) 02672 cout<<temp_pq->id<<" "; 02673 cout<<endl; 02674 temp_pq=root->partial_children.head()->full_children.head()->link_right_side; 02675 while(temp_pq!=NULL) 02676 { 02677 cout<<temp_pq->id<<" "; 02678 temp_pq=temp_pq->link_right_side; 02679 } 02680 cout<<endl; 02681 temp_pq=root->partial_children.head()->full_children.head()->link_left_side; 02682 while(temp_pq!=NULL) 02683 { 02684 cout<<temp_pq->id<<" "; 02685 temp_pq=temp_pq->link_left_side; 02686 } 02687 cout<<endl; 02688 cout<<find_leaf(1)->parent->id<<endl;*/ 02689 return true; 02690 } 02691 02692 template<class T> 02693 bool 02694 gdt::PQ_tree<T>:: 02695 template_Q3 02696 ( 02697 PQ_node node 02698 ) 02699 { 02700 if((node->type!=PSEUDONODE)&&(node->type!=QNODE)) 02701 return false; 02702 if(node->partial_children.size()>2) 02703 return false; 02704 if(((node->right_endmost->label==FULL)||(node->left_endmost->label==FULL))&&(node->type==QNODE)) 02705 return false; 02706 PQ_node temp_pq,node_y1,node_y2,child_full_endmost,child_empty_endmost,full_sibling,empty_sibling,temp_endmost; 02707 int count=0; 02708 int l=0; 02709 if(node->full_children.size()==0) 02710 { 02711 if((node->partial_children.head()->link_right_side!=node->partial_children.tail())&& (node->partial_children.head()->link_left_side!=node->partial_children.tail())) 02712 return false; 02713 } 02714 else //if(node->full_children.size()>0) 02715 { 02716 if(node->partial_children.size()>0) 02717 { 02718 temp_pq=node->partial_children.head(); 02719 if((node->partial_children.head()->link_right_side!=NULL)&& (node->partial_children.head()->link_right_side->label==FULL)) //controlla che non ci sono alternanze 02720 { 02721 temp_pq=node->partial_children.head()->link_right_side; 02722 for(int i=0;i<node->full_children.size();i++) 02723 { 02724 if(temp_pq->label!=FULL) 02725 return false; 02726 temp_pq=temp_pq->link_right_side; 02727 } 02728 } 02729 else if((node->partial_children.head()->link_left_side!=NULL)&& (node->partial_children.head()->link_left_side->label==FULL)) 02730 { 02731 temp_pq=node->partial_children.head()->link_left_side; 02732 for(int i=0;i<node->full_children.size();i++) 02733 { 02734 if(temp_pq->label!=FULL) 02735 return false; 02736 temp_pq=temp_pq->link_left_side; 02737 } 02738 } 02739 else //il partial_children.head() non ha sibling con label full vicini 02740 return false; 02741 } 02742 else //if(node->partial_children.size()==0) 02743 { 02744 temp_pq=node->left_endmost; 02745 while(temp_pq->label!=FULL) 02746 temp_pq=temp_pq->link_right_side; 02747 for(int i=0;i<node->full_children.size();i++) 02748 { 02749 if(temp_pq->label!=FULL) 02750 return false; 02751 temp_pq=temp_pq->link_right_side; 02752 } 02753 } 02754 } 02755 //stop10.start(); 02756 if(node->partial_children.size()>0) 02757 { 02758 node_y1=node->partial_children.head(); 02759 temp_pq=node_y1->left_endmost; //questo č per disegnare il grafo da qui... 02760 blocked_list.remove(node_y1); 02761 count--; 02762 while(temp_pq!=NULL) 02763 { 02764 temp_pq->parent=node; 02765 if(temp_pq->label==FULL) 02766 node->full_children.append(temp_pq); 02767 blocked_list.append(temp_pq); 02768 count++; 02769 temp_pq=temp_pq->link_right_side; 02770 } //...a qui 02771 if(node_y1->left_endmost->label==FULL) 02772 { 02773 child_full_endmost=node_y1->left_endmost; 02774 child_empty_endmost=node_y1->right_endmost; 02775 temp_pq=child_full_endmost; 02776 /*while(temp_pq->label==FULL) //controllare 02777 { 02778 node->full_children.append(temp_pq); 02779 temp_pq=temp_pq->link_right_side; 02780 }*/ //giā messo sopra per disegnare il grafo 02781 } 02782 else if(node_y1->right_endmost->label==FULL) 02783 { 02784 child_full_endmost=node_y1->right_endmost; 02785 child_empty_endmost=node_y1->left_endmost; 02786 temp_pq=child_full_endmost; 02787 /*while(temp_pq->label==FULL) 02788 { 02789 node->full_children.append(temp_pq); 02790 temp_pq=temp_pq->link_left_side; 02791 }*/ //giā messo sopra per disegnare il grafo 02792 } 02793 if((node->left_endmost!=node_y1)&&(node_y1->link_left_side->label==FULL)) 02794 { 02795 if(node_y1->left_endmost->label==EMPTY) 02796 qnode_reversing(node_y1); 02797 full_sibling=node_y1->link_left_side; 02798 full_sibling->link_right_side=child_full_endmost; 02799 child_full_endmost->link_left_side=full_sibling; 02800 } 02801 else if((node->right_endmost!=node_y1)&&(node_y1->link_right_side->label==FULL)) 02802 { 02803 if(node_y1->right_endmost->label==EMPTY) 02804 qnode_reversing(node_y1); 02805 full_sibling=node_y1->link_right_side; 02806 full_sibling->link_left_side=child_full_endmost; 02807 child_full_endmost->link_right_side=full_sibling; 02808 } 02809 else //node_y1 non ha sibling con label full 02810 temp_endmost=child_full_endmost; 02811 /*{ 02812 if(node->left_endmost==node_y1) 02813 node->left_endmost=child_full_endmost; 02814 else 02815 node->right_endmost=child_full_endmost; 02816 }*/ 02817 if((node->left_endmost!=node_y1)&&(node_y1->link_left_side->label==EMPTY)) 02818 { 02819 if(node_y1->left_endmost->label==FULL) 02820 qnode_reversing(node_y1); 02821 empty_sibling=node_y1->link_left_side; 02822 empty_sibling->link_right_side=child_empty_endmost; 02823 child_empty_endmost->link_left_side=empty_sibling; 02824 } 02825 else if((node->right_endmost!=node_y1)&&(node_y1->link_right_side->label==EMPTY)) 02826 { 02827 if(node_y1->right_endmost->label==FULL) 02828 qnode_reversing(node_y1); 02829 empty_sibling=node_y1->link_right_side; 02830 empty_sibling->link_left_side=child_empty_endmost; 02831 child_empty_endmost->link_right_side=empty_sibling; 02832 } 02833 else //node_y1 non ha sibling con label empty 02834 { 02835 if((node->left_endmost!=node_y1)&&(node_y1->link_left_side->label==PARTIAL)) 02836 { 02837 if(node_y1->left_endmost->label==EMPTY) 02838 qnode_reversing(node_y1); 02839 } 02840 else if((node->right_endmost!=node_y1)&&(node_y1->link_right_side->label==PARTIAL)) 02841 { 02842 if(node_y1->right_endmost->label==EMPTY) 02843 qnode_reversing(node_y1); 02844 } 02845 if(node->type==QNODE) 02846 if(node->left_endmost==node_y1) 02847 node->left_endmost=child_empty_endmost; 02848 else 02849 node->right_endmost=child_empty_endmost; 02850 else //if(node->type!=QNODE) 02851 if(node->left_endmost==node_y1) 02852 { 02853 child_empty_endmost->link_left_side=node_y1->link_left_side; 02854 node_y1->link_left_side->link_right_side=child_empty_endmost; 02855 } 02856 else 02857 { 02858 child_empty_endmost->link_right_side=node_y1->link_right_side; 02859 node_y1->link_right_side->link_left_side=child_empty_endmost; 02860 } 02861 } 02862 //child_empty_endmost->parent=node; //giā messo sopra per disegnare il grafo 02863 //node->child_count++; 02864 /*if(node->full_children.size()==0) 02865 if(node->left_endmost==node_y1) 02866 node->left_endmost=child_full_endmost; 02867 else 02868 node->right_endmost=child_full_endmost;*/ 02869 //child_full_endmost->parent=node; //giā messo sopra per disegnare il grafo 02870 //node->child_count++; 02871 node->child_count=node->child_count+node_y1->child_count; 02872 if((node->partial_children.size()==2)) 02873 { 02874 node_y2=node->partial_children.tail(); 02875 temp_pq=node_y2->left_endmost; //questo č per disegnare il grafo da qui... 02876 blocked_list.remove(node_y2); 02877 count--; 02878 while(temp_pq!=NULL) 02879 { 02880 temp_pq->parent=node; 02881 if(temp_pq->label==FULL) 02882 node->full_children.append(temp_pq); 02883 blocked_list.append(temp_pq); 02884 count++; 02885 temp_pq=temp_pq->link_right_side; 02886 } //...a qui 02887 if(node_y2->left_endmost->label==FULL) 02888 { 02889 child_full_endmost=node_y2->left_endmost; 02890 child_empty_endmost=node_y2->right_endmost; 02891 temp_pq=child_full_endmost; 02892 /*while(temp_pq->label==FULL) //controllare 02893 { 02894 node->full_children.append(temp_pq); 02895 temp_pq=temp_pq->link_right_side; 02896 }*/ //giā messo sopra per disegnare il grafo 02897 } 02898 else if(node_y2->right_endmost->label==FULL) 02899 { 02900 child_full_endmost=node_y2->right_endmost; 02901 child_empty_endmost=node_y2->left_endmost; 02902 temp_pq=child_full_endmost; 02903 /*while(temp_pq->label==FULL) 02904 { 02905 node->full_children.append(temp_pq); 02906 temp_pq=temp_pq->link_left_side; 02907 }*/ //giā messo sopra per disegnare il grafo 02908 } 02909 if((node->left_endmost!=node_y2)&&(node_y2->link_left_side->label==FULL)) 02910 { 02911 if(node_y2->left_endmost->label==EMPTY) 02912 qnode_reversing(node_y2); 02913 full_sibling=node_y2->link_left_side; 02914 full_sibling->link_right_side=child_full_endmost; 02915 child_full_endmost->link_left_side=full_sibling; 02916 } 02917 else if((node->right_endmost!=node_y2)&&(node_y2->link_right_side->label==FULL)) 02918 { 02919 if(node_y2->right_endmost->label==EMPTY) 02920 qnode_reversing(node_y2); 02921 full_sibling=node_y2->link_right_side; 02922 full_sibling->link_left_side=child_full_endmost; 02923 child_full_endmost->link_right_side=full_sibling; 02924 } 02925 //else //node_y2 non ha sibling con label full 02926 //{ 02927 //temp_endmost2=child_full_endmost; 02928 /*if((node->right_endmost!=node_y2)&&(node_y2->link_right_side->label==PARTIAL)) 02929 { 02930 temp_endmost->link_left_side=child_full_endmost; 02931 child_full_endmost->link_right_side=temp_endmost; 02932 } 02933 else 02934 { 02935 temp_endmost->link_right_side=child_full_endmost; 02936 child_full_endmost->link_left_side=temp_endmost; 02937 }*/ 02938 //} 02939 /*{ 02940 if(node->left_endmost==node_y2) 02941 node->left_endmost=child_full_endmost; 02942 else 02943 node->right_endmost=child_full_endmost; 02944 }*/ 02945 if((node->left_endmost!=node_y2)&&(node_y2->link_left_side->label==EMPTY)) 02946 { 02947 if(node_y2->left_endmost->label==FULL) 02948 qnode_reversing(node_y2); 02949 empty_sibling=node_y2->link_left_side; 02950 empty_sibling->link_right_side=child_empty_endmost; 02951 child_empty_endmost->link_left_side=empty_sibling; 02952 } 02953 else if((node->right_endmost!=node_y2)&&(node_y2->link_right_side->label==EMPTY)) 02954 { 02955 if(node_y2->right_endmost->label==FULL) 02956 qnode_reversing(node_y2); 02957 empty_sibling=node_y2->link_right_side; 02958 empty_sibling->link_left_side=child_empty_endmost; 02959 child_empty_endmost->link_right_side=empty_sibling; 02960 } 02961 else //node_y2 non ha sibling con label empty 02962 { 02963 if((node->left_endmost!=node_y2)&&(node_y2->link_left_side->label==PARTIAL)) 02964 { 02965 if(node_y2->left_endmost->label==EMPTY) 02966 qnode_reversing(node_y2); 02967 } 02968 else if((node->right_endmost!=node_y2)&&(node_y2->link_right_side->label==PARTIAL)) 02969 { 02970 if(node_y2->right_endmost->label==EMPTY) 02971 qnode_reversing(node_y2); 02972 } 02973 if(node->type==QNODE) 02974 if(node->left_endmost==node_y2) 02975 node->left_endmost=child_empty_endmost; 02976 else 02977 node->right_endmost=child_empty_endmost; 02978 else //if(node->type!=QNODE) 02979 if(node->left_endmost==node_y2) 02980 { 02981 child_empty_endmost->link_left_side=node_y2->link_left_side; 02982 node_y2->link_left_side->link_right_side=child_empty_endmost; 02983 } 02984 else 02985 { 02986 child_empty_endmost->link_right_side=node_y2->link_right_side; 02987 node_y2->link_right_side->link_left_side=child_empty_endmost; 02988 } 02989 } 02990 if((node->right_endmost!=node_y2)&&(node->right_endmost!=child_empty_endmost) &&(node_y2->link_right_side->label==PARTIAL)) 02991 { 02992 temp_endmost->link_left_side=child_full_endmost; 02993 child_full_endmost->link_right_side=temp_endmost; 02994 } 02995 else if((node->left_endmost!=node_y2)&&(node->left_endmost!=child_empty_endmost) &&(node_y2->link_left_side->label==PARTIAL)) 02996 { 02997 temp_endmost->link_right_side=child_full_endmost; 02998 child_full_endmost->link_left_side=temp_endmost; 02999 } 03000 //child_empty_endmost->parent=node; //giā messo sopra per disegnare il grafo 03001 //node->child_count++; 03002 /*if(node->full_children.size()==0) 03003 if(node->left_endmost==node_y2) 03004 node->left_endmost=child_full_endmost; 03005 else 03006 node->right_endmost=child_full_endmost;*/ 03007 //child_full_endmost->parent=node; //giā messo sopra per disegnare il grafo 03008 //node->child_count++; 03009 node->child_count=node->child_count+node_y2->child_count; 03010 while(l!=2) 03011 { 03012 temp_pq=full_queue.pop(); 03013 if((temp_pq==node_y1)||(temp_pq==node_y2)) 03014 l++; 03015 else 03016 full_queue.append(temp_pq); 03017 } 03018 l=0; 03019 delete(node_y2); 03020 node->child_count--; 03021 number_of_nodes--; 03022 } 03023 if(node->partial_children.size()==1) //?? 03024 { 03025 temp_pq=full_queue.pop(); 03026 while(temp_pq!=node_y1) 03027 { 03028 full_queue.append(temp_pq); 03029 temp_pq=full_queue.pop(); 03030 } 03031 } 03032 delete(node_y1); 03033 node->child_count--; 03034 number_of_nodes--; 03035 /*if(node->type==QNODE) //di questo secondo me non c'č bisogno perchč č il template_Q3 03036 { 03037 node->label=PARTIAL; 03038 if(!is_root(node)) 03039 node->parent->partial_children.append(node); 03040 full_queue.append(node); 03041 }*/ 03042 node->partial_children.clear(); 03043 } 03044 if(node->type!=QNODE) 03045 { 03046 assign_parent_to_draw_graph(node,count); //da togliere serve per disegnare il grafo 03047 delete(node); 03048 } 03049 else 03050 { 03051 node->label=PARTIAL;// 03052 if(!is_root(node))// 03053 node->parent->partial_children.append(node);// 03054 full_queue.append(node);// 03055 node->pertinent_child_count=0;//?? 03056 node->pertinent_leaf_count=0;//?? 03057 node->mark=UNMARKED; 03058 } 03059 blocked_list.clear(); 03060 //q3++; 03061 //stop10.pause(); 03062 /*cout<<root->id<<endl; 03063 forall(temp_pq,root->full_children) 03064 cout<<temp_pq->id<<" "; 03065 cout<<endl; 03066 forall(temp_pq,root->partial_children) 03067 cout<<temp_pq->id<<" "; 03068 cout<<endl; 03069 temp_pq=root->partial_children.head()->link_right_side; 03070 while(temp_pq!=root->partial_children.head()) 03071 { 03072 cout<<temp_pq->id<<" "; 03073 temp_pq=temp_pq->link_right_side; 03074 } 03075 cout<<endl; 03076 temp_pq=root->partial_children.head()->link_left_side; 03077 while(temp_pq!=root->partial_children.head()) 03078 { 03079 cout<<temp_pq->id<<" "; 03080 temp_pq=temp_pq->link_left_side; 03081 } 03082 cout<<endl; 03083 forall(temp_pq,root->partial_children.head()->full_children) 03084 cout<<temp_pq->id<<" "; 03085 cout<<endl; 03086 temp_pq=root->partial_children.head()->left_endmost; 03087 while(temp_pq!=NULL) 03088 { 03089 cout<<temp_pq->id<<" "; 03090 temp_pq=temp_pq->link_right_side; 03091 } 03092 cout<<endl; 03093 temp_pq=root->partial_children.head()->right_endmost; 03094 while(temp_pq!=NULL) 03095 { 03096 cout<<temp_pq->id<<" "; 03097 temp_pq=temp_pq->link_left_side; 03098 } 03099 cout<<endl; 03100 cout<<root->child_count<<endl; 03101 cout<<root->partial_children.head()->child_count<<endl;*/ 03102 return true; 03103 } 03104 03105 03106 03107 template <class T> 03108 bool 03109 gdt::PQ_tree<T>:: 03110 make_empty 03111 () 03112 { 03113 PQ_node temp_node,current_parent; 03114 gdt::gdtqueue<PQ_node> queue_to_make_empty; 03115 gdt::gdtmap<int,int> queued_for_delete(0); 03116 forall(temp_node,leaves) 03117 queue_to_make_empty.append(temp_node); 03118 while(!(queue_to_make_empty.empty())) 03119 { 03120 temp_node=queue_to_make_empty.pop(); 03121 current_parent=temp_node->parent; 03122 if(current_parent!=root) 03123 { 03124 if(temp_node->type!=PSEUDONODE) 03125 { 03126 queued_for_delete[current_parent->id]++; 03127 if(queued_for_delete[current_parent->id]==current_parent->child_count) 03128 queue_to_make_empty.append(current_parent); 03129 } 03130 } 03131 delete(temp_node); 03132 } 03133 leaves.clear(); 03134 queue.clear(); 03135 full_queue.clear(); 03136 if(root!=NULL) 03137 { 03138 max_id=root->id; 03139 number_of_nodes=1; 03140 } 03141 else 03142 { 03143 max_id=-1; 03144 number_of_nodes=0; 03145 } 03146 return true; 03147 } 03148 03149 03150 template <class T> 03151 bool 03152 gdt::PQ_tree<T>:: 03153 reduce 03154 ( 03155 gdt::gdtlist<T> &S 03156 ) 03157 { 03158 T temp_i; 03159 PQ_node temp_pq,current_parent,temp_n; 03160 queue.clear();//?? 03161 forall(temp_i,S) 03162 { 03163 temp_pq=find_leaf(temp_i); 03164 if(temp_pq==NULL) 03165 gdt_error("A leaf doesn't exist"); 03166 queue.append(temp_pq); 03167 temp_pq->pertinent_leaf_count=1; 03168 } 03169 while(queue.size()>0) 03170 { 03171 temp_pq=queue.pop(); 03172 if(temp_pq->pertinent_leaf_count<S.size()) 03173 {//temp_pq is not root of the pertinent subtree 03174 current_parent=temp_pq->parent; 03175 current_parent->pertinent_leaf_count=current_parent->pertinent_leaf_count + temp_pq->pertinent_leaf_count; 03176 current_parent->pertinent_child_count=current_parent->pertinent_child_count-1; 03177 /*cout<<current_parent->id<<" "<<current_parent->pertinent_leaf_count<<" "<<current_parent->pertinent_child_count<<endl;*/ 03178 //cout<<current_parent->id<<endl; 03179 //cout<<current_parent->pertinent_leaf_count<<" "<<current_parent->pertinent_child_count<<endl; 03180 if(current_parent->pertinent_child_count==0)//all children of current parent have been computed 03181 queue.append(current_parent); 03182 if(!template_L1(temp_pq)) 03183 if(!template_P1(temp_pq)) 03184 if(!template_P3(temp_pq)) 03185 if(!template_P5(temp_pq)) 03186 if(!template_Q1(temp_pq)) 03187 if(!template_Q2(temp_pq)) 03188 { 03189 make_empty(); 03190 std::cout<<"Could not reduce {"; 03191 forall(temp_i,S) 03192 if(temp_i!=S.tail()) 03193 std::cout<<find_leaf(temp_i)->id<<","; 03194 std::cout<<S.tail()<<"}"<<std::endl; 03195 return false; 03196 } 03197 } 03198 else 03199 {//temp_pq is root of the pertinent subtree 03200 if(!template_L1(temp_pq)) 03201 if(!template_P1(temp_pq)) 03202 if(!template_P2(temp_pq)) 03203 if(!template_P4(temp_pq)) 03204 if(!template_P6(temp_pq)) 03205 if(!template_Q1(temp_pq)) 03206 if(!template_Q2(temp_pq)) 03207 if(!template_Q3(temp_pq)) 03208 { 03209 make_empty(); 03210 std::cout<<"Could not reduce {"; 03211 forall(temp_i,S) 03212 if(temp_i!=S.tail()) 03213 std::cout<<find_leaf (temp_i)->id<<","; 03214 std::cout<<S.tail()<<"}"<<std::endl; 03215 return false; 03216 } 03217 } 03218 //temp_pq->pertinent_child_count=0;//?? 03219 //temp_pq->pertinent_leaf_count=0;//?? 03220 //temp_pq->mark=UNMARKED; 03221 /*if(temp_pq->parent!=NULL) 03222 cout<<temp_pq->parent->id<<" "<<temp_pq->parent->pertinent_child_count<<endl;*/ 03223 } 03224 //cout<<endl; 03225 temp_pq=temp_pq->parent; 03226 while((temp_pq!=NULL)&&(temp_pq->mark!=UNMARKED)) 03227 { 03228 temp_pq->mark=UNMARKED; 03229 temp_pq->pertinent_child_count=0;//?? 03230 temp_pq->pertinent_leaf_count=0; 03231 temp_pq=temp_pq->parent; 03232 } 03233 while(!full_queue.empty()) 03234 { 03235 temp_n=full_queue.pop(); 03236 /*if(!is_root(temp_n)) 03237 if(temp_n->label==FULL) 03238 temp_n->parent->full_children.remove(temp_n); 03239 else if(temp_n->label==PARTIAL)//ovviamente quindi togliere questo 03240 temp_n->parent->partial_children.remove(temp_n);*/ 03241 temp_n->label=EMPTY; 03242 temp_n->full_children.clear(); 03243 temp_n->partial_children.clear(); 03244 } 03245 if(!is_root(temp_n)) 03246 { 03247 temp_n->parent->full_children.clear(); 03248 temp_n->parent->partial_children.clear(); 03249 } 03250 /*PQ_node temp_n,temp_n1; 03251 cout<<"numero di nodi "<<number_of_nodes<<endl; 03252 cout<<"queue "; 03253 while(!queue.empty()) 03254 cout<<queue.pop()->id<<" "; 03255 cout<<endl; 03256 cout<<"max_id "<<max_id<<endl; 03257 cout<<"leaves "; 03258 forall(temp_pq,leaves) 03259 cout<<temp_pq->id<<" "; 03260 cout<<endl; 03261 cout<<"radice "<<root->id<<endl; 03262 cout<<" child_count "<<root->child_count<<endl; 03263 cout<<" full_children "; 03264 forall(temp_pq,root->full_children) 03265 cout<<temp_pq->id<<" "; 03266 cout<<endl; 03267 cout<<" label "<<root->label<<endl; 03268 cout<<" pertinent_child_count "<<root->pertinent_child_count<<endl; 03269 cout<<" pertinent_leaf_count "<<root->pertinent_leaf_count<<endl; 03270 cout<<" type "<<root->type<<endl; 03271 cout<<endl; 03272 temp_n=root->full_children.head(); 03273 cout<<"full_children "<<temp_n->id<<endl; 03274 cout<<" child_count "<<temp_n->child_count<<endl; 03275 cout<<" link_left_side "<<temp_n->link_left_side->id<<endl; 03276 cout<<" link_right_side "<<temp_n->link_right_side->id<<endl; 03277 cout<<" circular_link right "; 03278 temp_pq=temp_n->link_right_side; 03279 while(temp_pq!=temp_n) 03280 { 03281 cout<<temp_pq->id<<" "; 03282 temp_pq=temp_pq->link_right_side; 03283 } 03284 cout<<endl; 03285 cout<<" circular_link left "; 03286 temp_pq=temp_n->link_left_side; 03287 while(temp_pq!=temp_n) 03288 { 03289 cout<<temp_pq->id<<" "; 03290 temp_pq=temp_pq->link_left_side; 03291 } 03292 cout<<endl; 03293 cout<<" full_children "; 03294 forall(temp_pq,temp_n->full_children) 03295 cout<<temp_pq->id<<" "; 03296 cout<<endl; 03297 cout<<" label "<<temp_n->label<<endl; 03298 cout<<" parent "<<temp_n->parent->id<<endl; 03299 cout<<" pertinent_child_count "<<temp_n->pertinent_child_count<<endl; 03300 cout<<" pertinent_leaf_count "<<temp_n->pertinent_leaf_count<<endl; 03301 cout<<" type "<<temp_n->type<<endl; 03302 cout<<endl; 03303 temp_n1=temp_n->full_children.head(); 03304 cout<<"full_children1 "<<temp_n1->id<<endl; 03305 cout<<" child_count "<<temp_n1->child_count<<endl; 03306 cout<<" link_left_side "<<temp_n1->link_left_side->id<<endl; 03307 cout<<" link_right_side "<<temp_n1->link_right_side->id<<endl; 03308 cout<<" circular_link right "; 03309 temp_pq=temp_n1->link_right_side; 03310 while(temp_pq!=temp_n1) 03311 { 03312 cout<<temp_pq->id<<" "; 03313 temp_pq=temp_pq->link_right_side; 03314 } 03315 cout<<endl; 03316 cout<<" circular_link left "; 03317 temp_pq=temp_n1->link_left_side; 03318 while(temp_pq!=temp_n1) 03319 { 03320 cout<<temp_pq->id<<" "; 03321 temp_pq=temp_pq->link_left_side; 03322 } 03323 cout<<endl; 03324 cout<<" full_children "; 03325 forall(temp_pq,temp_n1->full_children) 03326 cout<<temp_pq->id<<" "; 03327 cout<<endl; 03328 cout<<" label "<<temp_n1->label<<endl; 03329 cout<<" parent "<<temp_n1->parent->id<<endl; 03330 cout<<" pertinent_child_count "<<temp_n1->pertinent_child_count<<endl; 03331 cout<<" pertinent_leaf_count "<<temp_n1->pertinent_leaf_count<<endl; 03332 cout<<" type "<<temp_n1->type<<endl; 03333 cout<<endl;*/ 03334 return true; 03335 } 03336 03337 03338 03339 template<class T> 03340 void 03341 gdt::PQ_tree<T>:: 03342 freeze 03343 ( 03344 PQ_tree_freezed<T>& freezed_tree 03345 ) 03346 { 03347 PQ_node temp_pq,current_node,prec_child,current_child; 03348 PQ_node_freezed freezed_child,freezed_node,temp_freezed; 03349 gdt::gdtmap<PQ_node,int> node_visited(0); 03350 gdt::gdtmap<PQ_node,PQ_node_struct_freezed<T>*> map_PQ; 03351 gdt::gdtmap<PQ_node_struct_freezed<T>*,PQ_node> map_PQfreezed; 03352 gdt::gdtqueue<PQ_node_freezed> freezed_queue; 03353 //All of the nodes have mark UNMARKED 03354 forall(temp_pq,leaves) 03355 { 03356 current_node=temp_pq; 03357 while((current_node!=NULL)&&(node_visited[current_node]==0)) 03358 { 03359 freezed_node=new PQ_node_struct_freezed<T>; 03360 freezed_node->id=current_node->id; 03361 if(current_node->type!=LEAF) 03362 freezed_node->children_list.append(map_PQ[prec_child]); 03363 freezed_node->type=current_node->type; 03364 map_PQ[current_node]=freezed_node; 03365 map_PQfreezed[freezed_node]=current_node; 03366 if((current_node->parent!=NULL)&&(node_visited[current_node->parent]==1)) 03367 map_PQ[current_node->parent]->children_list.append(freezed_node); 03368 freezed_tree.number_of_nodes++; 03369 if(freezed_node->type==LEAF) 03370 freezed_node->value=current_node->value; 03371 if(current_node==root) 03372 { 03373 freezed_tree.root=freezed_node; 03374 } 03375 node_visited[current_node]=1; 03376 prec_child=current_node; 03377 current_node=current_node->parent; 03378 } 03379 } 03380 freezed_queue.append(freezed_tree.root); 03381 while(freezed_queue.size()!=0) 03382 { 03383 freezed_node=freezed_queue.pop(); 03384 forall(temp_freezed,freezed_node->children_list) 03385 { 03386 if(temp_freezed->type!=LEAF) 03387 freezed_queue.append(temp_freezed); 03388 } 03389 if(freezed_node->type==QNODE) 03390 { 03391 freezed_child=freezed_node->children_list.head(); 03392 freezed_node->children_list.clear(); 03393 current_child=map_PQfreezed[freezed_child]; 03394 current_node=map_PQfreezed[freezed_node]; 03395 while(!(current_child->is_endmost())) 03396 { 03397 current_child=current_child->link_left_side;//link_right_side anche va bene 03398 } 03399 if(current_child==current_node->right_endmost) 03400 while(current_child!=NULL) 03401 { 03402 freezed_node->children_list.append(map_PQ[current_child]); 03403 current_child=current_child->link_left_side; 03404 } 03405 else if(current_child==current_node->left_endmost) 03406 while(current_child!=NULL) 03407 { 03408 freezed_node->children_list.append(map_PQ[current_child]); 03409 current_child=current_child->link_right_side; 03410 } 03411 } 03412 } 03413 } 03414 03415 03416 template<class T> 03417 undi_graph 03418 gdt::PQ_tree<T>:: 03419 PQ_tree_into_undi_graph 03420 ( 03421 std::string title 03422 ) 03423 { 03424 int n; 03425 gdt::gdtqueue<PQ_node> pq_queue; 03426 undi_graph ug; 03427 gdtnode graph_node,temp_node,root_node; 03428 PQ_node temp,tree_node; 03429 //int queued_for_graph[this->number_of_nodes]; 03430 gdt::gdtmap<int,int> queued_for_graph(0); 03431 gdt::gdtnode_map<std::string> labels(ug); 03432 gdt::gdtnode_map<PQ_node> parents(ug); 03433 03434 forall(temp,this->leaves) 03435 pq_queue.append(temp); 03436 if(number_of_nodes!=1) 03437 while(!pq_queue.empty()) 03438 { 03439 tree_node=pq_queue.pop(); 03440 //cout<<tree_node->id<<" "<<tree_node->child_count<<endl; 03441 graph_node=ug.new_node(); 03442 if(tree_node==root) 03443 root_node=graph_node; 03444 n=tree_node->id; //n=tree_node->get_id(); 03445 if(tree_node->type==LEAF) //(tree_node->get_type()==LEAF) 03446 labels[graph_node]="L"+gdt_itoa(n); 03447 else if(tree_node->type==PNODE) //(tree_node->get_type()==PNODE) 03448 labels[graph_node]="P"+gdt_itoa(n); 03449 else labels[graph_node]="Q"+gdt_itoa(n); 03450 parents[graph_node]=tree_node->parent; 03451 if(tree_node->parent!=NULL) 03452 queued_for_graph[tree_node->parent->id]++; 03453 if((tree_node->parent!=NULL)&&(queued_for_graph[tree_node->parent->id]==tree_node->parent->child_count)) 03454 pq_queue.append(tree_node->parent); 03455 if(tree_node->child_count!=0) 03456 forall_nodes(temp_node,ug) 03457 if(parents[temp_node]!=NULL) 03458 if(parents[temp_node]->id==tree_node->id) 03459 ug.new_edge(temp_node,graph_node); 03460 } 03461 else 03462 { 03463 graph_node=ug.new_node(); 03464 n=root->id; 03465 labels[graph_node]="P"+gdt_itoa(n); 03466 temp_node=ug.new_node(); 03467 labels[temp_node]="0"; 03468 ug.new_edge(temp_node,graph_node); 03469 } 03470 tree albero(ug,root_node); 03471 draw_undi_graph dug(ug); 03472 forall_nodes(temp_node,dug) 03473 { 03474 graph_node=ug.find_node(dug.id(temp_node)); 03475 dug.set_label(temp_node,labels[graph_node]); 03476 } 03477 dug.write(title+".gdt"); 03478 draw_undi_graph dug_tree(albero); 03479 forall_nodes(temp_node,dug_tree) 03480 { 03481 graph_node=ug.find_node(dug_tree.id(temp_node)); 03482 dug_tree.set_label(temp_node,labels[graph_node]); 03483 } 03484 title=title+"_tree.gdt"; 03485 dug_tree.write(title); 03486 return ug; 03487 } 03488 03489 03490 03491 03492 03493 03494 template<class T> 03495 gdt::PQ_node_struct_freezed<T>:: 03496 PQ_node_struct_freezed 03497 () 03498 { 03499 id=0; 03500 type=NON_VALID; 03501 //punt_value=NULL; 03502 } 03503 03504 03505 template<class T> 03506 gdt::PQ_node_struct_freezed<T>:: 03507 ~PQ_node_struct_freezed 03508 () 03509 { 03510 children_list.clear(); 03511 } 03512 03513 03514 03515 template<class T> 03516 int 03517 gdt::PQ_node_struct_freezed<T>:: 03518 get_id 03519 () 03520 { 03521 return id; 03522 } 03523 03524 03525 03526 template<class T> 03527 T 03528 gdt::PQ_node_struct_freezed<T>:: 03529 get_value 03530 () 03531 { 03532 return value; 03533 } 03534 03535 03536 03537 03538 03539 03540 template<class T> 03541 gdt::PQ_tree_freezed<T>:: 03542 PQ_tree_freezed 03543 () 03544 { 03545 root=NULL; 03546 //max_id=-1; 03547 number_of_nodes=0; 03548 } 03549 03550 03551 03552 template<class T> 03553 gdt::PQ_tree_freezed<T>:: 03554 ~PQ_tree_freezed 03555 () 03556 { 03557 delete(root); 03558 frontier.clear(); 03559 } 03560 03561 03562 03563 template<class T> 03564 gdt::gdtlist<T> 03565 gdt::PQ_tree_freezed<T>:: 03566 tree_search 03567 () 03568 { 03569 PQ_node_freezed freezed_node,freezed_child; 03570 gdt::gdtqueue<PQ_node_freezed> search_queue; 03571 gdt::gdtlist<T> search_list; 03572 search_queue.append(root); 03573 while(search_queue.size()!=0) 03574 { 03575 freezed_node=search_queue.pop(); 03576 forall(freezed_child,freezed_node->children_list) 03577 search_queue.append(freezed_child); 03578 search_list.append(freezed_node->id); 03579 } 03580 return search_list; 03581 } 03582 03583 03584 03585 template<class T> 03586 void 03587 gdt::PQ_tree_freezed<T>:: 03588 sorted_leaves_list 03589 ( 03590 gdt::gdtlist<gdt::PQ_node_struct_freezed<T>*> node_list 03591 ) 03592 { 03593 PQ_node_freezed temp_node; 03594 forall(temp_node,node_list) 03595 if(temp_node->type==LEAF) 03596 frontier.append(temp_node); 03597 else 03598 sorted_leaves_list(temp_node->children_list); 03599 } 03600 03601 03602 03603 template<class T> 03604 void 03605 gdt::PQ_tree_freezed<T>:: 03606 tree_frontier 03607 () 03608 { 03609 gdt::gdtlist<gdt::PQ_node_struct_freezed<T>*> node_list; 03610 node_list.append(root); 03611 sorted_leaves_list(node_list); 03612 } 03613 03614 03615 03616 template<class T> 03617 gdt::gdtlist<gdt::PQ_node_struct_freezed<T>*> 03618 gdt::PQ_tree_freezed<T>:: 03619 get_frontier 03620 () 03621 { 03622 return frontier; 03623 } 03624 03625 03626 #endif
1.5.3