00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
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;
00052 int child_count;
00053
00054 PQ_node link_left_side, link_right_side;
00055 PQ_node left_endmost, right_endmost;
00056 gdtlist<PQ_node> full_children;
00057
00058 int label;
00059 int mark;
00060 PQ_node parent;
00061 gdtlist<PQ_node> partial_children;
00062 int pertinent_child_count;
00063 int pertinent_leaf_count;
00064 int type;
00065 T value;
00066
00067
00068
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;
00230 int max_id;
00231 int block_count;
00232 int blocked_nodes;
00233 bool off_the_top;
00234 gdtqueue<PQ_node> queue;
00235 PQ_node root;
00236 int number_of_nodes;
00237 gdtqueue<PQ_node> full_queue;
00238 gdtlist<PQ_node> blocked_list;
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;
00606 gdt::gdtlist<PQ_node_freezed> children_list;
00607 int type;
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;
00664 int number_of_nodes;
00665 gdtlist<PQ_node_freezed> frontier;
00666
00667
00668
00669
00670
00671
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();
00958 temp_n->type=LEAF;
00959 temp_n->value=temp_i;
00960 leaves.append(temp_n);
00961 map_leaves[temp_i]=temp_n;
00962
00963
00964
00965 }
00966 p_base=new(PQ_node_struct<T>);
00967 p_base->id=generate_id();
00968
00969 p_base->type=PNODE;
00970 p_base->child_count=leaves.size();
00971
00972 root=p_base;
00973 forall(temp_n,leaves)
00974 {
00975 temp_n->parent=p_base;
00976
00977
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
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
01018
01019
01020
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
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
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
01225
01226
01227
01228
01229
01230
01231
01232
01233
01234
01235
01236
01237
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
01292 (
01293 PQ_node node,
01294 int count
01295 )
01296 {
01297 PQ_node temp_node,current_parent,child;
01298
01299
01300
01301 temp_node=blocked_list.head()->link_right_side;
01302
01303
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
01389
01390
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
01404 while((queue.size()+block_count+off_the_top)>1)
01405 {
01406
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
01420
01421
01422
01423
01424
01425
01426
01427
01428
01429
01430
01431
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
01454
01455 }
01456
01457
01458 if(temp_pq->mark==UNBLOCKED)
01459 {
01460 current_parent=temp_pq->parent;
01461
01462
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
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
01501
01502 }
01503
01504
01505
01506
01507
01508
01509
01510 }
01511
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
01531
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
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
01556
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())
01572 return false;
01573
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
01582
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
01605 full_node=new(PQ_node_struct<T>);
01606 full_node->id=generate_id();
01607 full_node->type=PNODE;
01608 full_node->label=FULL;
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);
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);
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
01633
01634
01635
01636
01637
01638
01639
01640
01641
01642
01643
01644
01645
01646
01647
01648
01649
01650
01651
01652
01653
01654
01655
01656
01657
01658
01659
01660
01661
01662
01663
01664
01665
01666
01667
01668
01669
01670
01671
01672
01673
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
01696 pnode_sorting(node);
01697 if(node->child_count-node->full_children.size()>1)
01698 {
01699 empty_node=new(PQ_node_struct<T>);
01700 number_of_nodes++;
01701 empty_node->id=generate_id();
01702 empty_node->label=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
01716 empty_node=node->full_children.head()->link_right_side;
01717 if(node->full_children.size()>1)
01718 {
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
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
01754
01755
01756
01757
01758
01759
01760
01761
01762
01763
01764
01765
01766
01767
01768
01769
01770
01771
01772
01773
01774
01775
01776
01777
01778
01779
01780
01781
01782
01783
01784
01785
01786
01787
01788
01789
01790
01791
01792
01793
01794
01795
01796
01797
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
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;
01826 full_node->type=PNODE;
01827 full_queue.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
01906
01907
01908
01909
01910
01911
01912
01913
01914
01915
01916
01917
01918
01919
01920
01921
01922
01923
01924
01925
01926
01927
01928
01929
01930
01931
01932
01933
01934
01935
01936
01937
01938
01939
01940
01941
01942
01943
01944
01945
01946
01947
01948
01949
01950
01951
01952
01953
01954
01955
01956
01957
01958
01959
01960
01961
01962
01963
01964
01965
01966
01967
01968
01969
01970
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)
01988 return false;
01989
01990 partial=node->partial_children.head();
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)
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
02012
02013 partial->parent=node->parent;
02014 partial->pertinent_leaf_count=node->pertinent_leaf_count;
02015
02016 partial->parent->partial_children.append(partial);
02017 partial->remove_from_circular_link();
02018 partial->link_right_side=node->link_right_side;
02019
02020
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
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
02077
02078
02079
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
02101
02102
02103
02104 }
02105
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
02143
02144
02145
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
02153
02154
02155
02156
02157
02158
02159
02160
02161
02162
02163
02164
02165
02166
02167
02168
02169
02170
02171
02172
02173
02174
02175
02176
02177
02178
02179
02180
02181
02182
02183
02184
02185
02186
02187
02188
02189
02190
02191
02192
02193
02194
02195
02196
02197
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
02216 if(node->full_children.size()!=0)
02217 {
02218 pnode_sorting(node);
02219 }
02220 else
02221 {
02222 prec_node=node->partial_children.head();
02223
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)
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;
02261 full_node->type=PNODE;
02262 full_queue.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
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
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
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);
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
02399
02400
02401
02402
02403
02404
02405
02406
02407
02408
02409
02410
02411
02412
02413
02414
02415
02416
02417
02418
02419
02420
02421
02422
02423
02424
02425
02426
02427
02428
02429
02430
02431
02432
02433
02434
02435
02436
02437
02438
02439
02440
02441
02442
02443
02444
02445
02446
02447
02448
02449
02450
02451
02452
02453
02454
02455
02456
02457
02458
02459
02460
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
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
02486
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
02504 if(node->partial_children.size()>1)
02505 return false;
02506 if(node->full_children.size()>0)
02507 {
02508
02509
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)
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
02540 node->label=PARTIAL;
02541 if(node->parent!=NULL)
02542 node->parent->partial_children.append(node);
02543
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
02553
02554
02555
02556
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
02564
02565
02566
02567
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
02586
02587
02588
02589
02590
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
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
02616
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
02623
02624 temp_pq=node_y->left_endmost;
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 }
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
02643 }
02644 node->pertinent_child_count=0;
02645 node->pertinent_leaf_count=0;
02646 node->mark=UNMARKED;
02647 full_queue.append(node);
02648
02649
02650
02651
02652
02653
02654
02655
02656
02657
02658
02659
02660
02661
02662
02663
02664
02665
02666
02667
02668
02669
02670
02671
02672
02673
02674
02675
02676
02677
02678
02679
02680
02681
02682
02683
02684
02685
02686
02687
02688
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
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))
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
02740 return false;
02741 }
02742 else
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
02756 if(node->partial_children.size()>0)
02757 {
02758 node_y1=node->partial_children.head();
02759 temp_pq=node_y1->left_endmost;
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 }
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
02777
02778
02779
02780
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
02788
02789
02790
02791
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
02810 temp_endmost=child_full_endmost;
02811
02812
02813
02814
02815
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
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
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
02863
02864
02865
02866
02867
02868
02869
02870
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;
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 }
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
02893
02894
02895
02896
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
02904
02905
02906
02907
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
02926
02927
02928
02929
02930
02931
02932
02933
02934
02935
02936
02937
02938
02939
02940
02941
02942
02943
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
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
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
03001
03002
03003
03004
03005
03006
03007
03008
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
03036
03037
03038
03039
03040
03041
03042 node->partial_children.clear();
03043 }
03044 if(node->type!=QNODE)
03045 {
03046 assign_parent_to_draw_graph(node,count);
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
03061
03062
03063
03064
03065
03066
03067
03068
03069
03070
03071
03072
03073
03074
03075
03076
03077
03078
03079
03080
03081
03082
03083
03084
03085
03086
03087
03088
03089
03090
03091
03092
03093
03094
03095
03096
03097
03098
03099
03100
03101
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 {
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
03178
03179
03180 if(current_parent->pertinent_child_count==0)
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 {
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
03219
03220
03221
03222
03223 }
03224
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
03237
03238
03239
03240
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
03251
03252
03253
03254
03255
03256
03257
03258
03259
03260
03261
03262
03263
03264
03265
03266
03267
03268
03269
03270
03271
03272
03273
03274
03275
03276
03277
03278
03279
03280
03281
03282
03283
03284
03285
03286
03287
03288
03289
03290
03291
03292
03293
03294
03295
03296
03297
03298
03299
03300
03301
03302
03303
03304
03305
03306
03307
03308
03309
03310
03311
03312
03313
03314
03315
03316
03317
03318
03319
03320
03321
03322
03323
03324
03325
03326
03327
03328
03329
03330
03331
03332
03333
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
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;
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
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
03441 graph_node=ug.new_node();
03442 if(tree_node==root)
03443 root_node=graph_node;
03444 n=tree_node->id;
03445 if(tree_node->type==LEAF)
03446 labels[graph_node]="L"+gdt_itoa(n);
03447 else if(tree_node->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
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
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