title
Graph Drawing Toolkit

An object-oriented C++ library for handling and drawing graphs

rm3_PQ_tree.h

Go to the documentation of this file.
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  

Generated on Thu Jan 10 14:48:02 2008 for GDToolkit GAPI by  doxygen 1.5.3