gtl/src/pq_tree.cpp

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //   pq_tree.cpp
0005 //
0006 //==========================================================================
0007 // $Id: pq_tree.cpp,v 1.22 2008/02/03 18:12:07 chris Exp $
0008
0009 #include <GTL/pq_tree.h>
0010 #include <GTL/debug.h>
0011
0012 #include <stack>
0013 #include <queue>
0014 #include <utility>
0015 #include <cstdio>
0016
0017 #ifdef __GTL_MSVCC
0018 #   ifdef _DEBUG
0019 #   ifndef SEARCH_MEMORY_LEAKS_ENABLED
0020 #   error SEARCH NOT ENABLED
0021 #   endif
0022 #   define new DEBUG_NEW
0023 #   undef THIS_FILE
0024     static char THIS_FILE[] = __FILE__;
0025 #   endif   // _DEBUG
0026 #endif  // __GTL_MSVCC
0027
0028 __GTL_BEGIN_NAMESPACE
0029
0030 pq_tree::pq_tree (int id, node n, const list<pq_leaf*>& li)
0031 {
0032 #ifdef _DEBUG
0033     GTL_debug::init_debug();
0034 #endif
0035     list<pq_leaf*>::const_iterator it;
0036     list<pq_leaf*>::const_iterator end = li.end();
0037     sons_list sons;
0038     pq_leaf* tmp;
0039
0040     for (it = li.begin(); it != end; ++it) {
0041     tmp = *it;
0042     tmp->pos = sons.insert (sons.end(), tmp);
0043     }
0044
0045     root = new p_node(n, id, sons);
0046     pert_root = 0;
0047     fail = 0;
0048     pseudo = 0;
0049 }
0050
0051 pq_tree::~pq_tree ()
0052 {
0053 #ifdef _DEBUG
0054     GTL_debug::close_debug();
0055 #endif
0056     reset ();
0057
0058     if (root) {
0059     delete root;
0060     }
0061 }
0062
0063
0064 bool pq_tree::bubble_up (list<pq_leaf*>& leaves)
0065 {
0066     queue<pq_node*> qu;
0067     int block_count = 0;
0068     int blocked_siblings = 0;
0069     pert_leaves_count = 0;
0070     int off_the_top = 0;
0071     pq_node* tmp;
0072
0073     assert (clear_me.empty());
0074
0075     list<pq_leaf*>::const_iterator it = leaves.begin();
0076     list<pq_leaf*>::const_iterator lend = leaves.end();
0077
0078     while (it != lend) {
0079     qu.push (*it);
0080     (*it)->lpos = clear_me.insert (clear_me.end(), *it);
0081     pert_leaves_count++;
0082     ++it;
0083     }
0084
0085     sons_iterator next, prev, end;
0086     pq_node* father;
0087     int size = pert_leaves_count;
0088
0089     while (size + block_count + off_the_top > 1) {
0090     if (size == 0) {
0091         return false;
0092     }
0093
0094     tmp = qu.front();
0095     qu.pop();
0096     size--;
0097     tmp->pert_leaves = 0;
0098
0099     if (tmp == root) {
0100         off_the_top = 1;
0101         tmp->mark = pq_node::UNBLOCKED;
0102         continue;
0103     }
0104
0105     tmp->mark = pq_node::BLOCKED;
0106
0107     if (tmp->is_endmost) {
0108         father = tmp->father;
0109         tmp->mark = pq_node::UNBLOCKED;
0110         end = father->sons.end();
0111
0112         if (father->kind() == pq_node::Q_NODE) {
0113         blocked_siblings = 0;
0114         next = tmp->pos;
0115         prev = tmp->pos;
0116         ++next;
0117         --prev;
0118
0119         if (next != end) {
0120             if ((*next)->mark == pq_node::BLOCKED) {
0121             ++blocked_siblings;
0122             }
0123         } else if (prev != end) {
0124             if ((*prev)->mark == pq_node::BLOCKED) {
0125             ++blocked_siblings;
0126             }
0127         }
0128         }
0129
0130     } else {
0131         next = tmp->pos;
0132         prev = tmp->pos;
0133         ++next;
0134         --prev;
0135         blocked_siblings = 0;
0136
0137         if ((*prev)->mark == pq_node::UNBLOCKED) {
0138         tmp->mark = pq_node::UNBLOCKED;
0139         tmp->father = (*prev)->father;
0140         father = tmp->father;
0141         end = father->sons.end();
0142         } else if ((*prev)->mark == pq_node::BLOCKED) {
0143         blocked_siblings++;
0144         }
0145
0146         if ((*next)->mark == pq_node::UNBLOCKED) {
0147         tmp->mark = pq_node::UNBLOCKED;
0148         tmp->father = (*next)->father;
0149         father = tmp->father;
0150         end = father->sons.end();
0151         } else if ((*next)->mark == pq_node::BLOCKED) {
0152         blocked_siblings++;
0153         }
0154     }
0155
0156     if (tmp->mark == pq_node::UNBLOCKED) {
0157         ++(father->pert_children);
0158
0159         if (father->mark == pq_node::UNMARKED) {
0160         qu.push (father);
0161         father->lpos = clear_me.insert (clear_me.end(), father);
0162         size++;
0163         father->mark = pq_node::QUEUED;
0164         }
0165
0166         if (father->kind() == pq_node::Q_NODE) {
0167                 pq_node* tmp;
0168
0169         while (next != end) {
0170             tmp = *next;
0171             if (tmp->mark == pq_node::BLOCKED) {
0172             tmp->father = father;
0173             tmp->mark = pq_node::UNBLOCKED;
0174
0175             if (tmp->kind () != pq_node::DIR) {
0176                 ++(father->pert_children);
0177             }
0178             } else if (tmp->kind () == pq_node::DIR &&
0179                    tmp->mark == pq_node::UNMARKED) {
0180             tmp->lpos = clear_me.insert (clear_me.end(), tmp);
0181             tmp->father = father;
0182             tmp->mark = pq_node::UNBLOCKED;
0183             } else {
0184             break;
0185             }
0186
0187             ++next;
0188         }
0189
0190         while (prev != end) {
0191             tmp = *prev;
0192             if (tmp->mark == pq_node::BLOCKED) {
0193             tmp->father = father;
0194             tmp->mark = pq_node::UNBLOCKED;
0195
0196             if (tmp->kind () != pq_node::DIR) {
0197                 ++(father->pert_children);
0198             }
0199             } else if (tmp->kind () == pq_node::DIR &&
0200                    tmp->mark == pq_node::UNMARKED) {
0201             tmp->lpos = clear_me.insert (clear_me.end(), tmp);
0202             tmp->father = father;
0203             tmp->mark = pq_node::UNBLOCKED;
0204             } else {
0205             break;
0206             }
0207
0208             --prev;
0209         }
0210
0211         block_count -= blocked_siblings;
0212         }
0213
0214     } else {
0215
0216         //
0217         // tmp is BLOCKED
0218         //
0219
0220         while ((*next)->kind() == pq_node::DIR &&
0221            (*next)->mark == pq_node::UNMARKED) {
0222         (*next)->mark = pq_node::BLOCKED;
0223         (*next)->lpos = clear_me.insert (clear_me.end(), *next);
0224         ++next;
0225         }
0226
0227         while ((*prev)->kind() == pq_node::DIR &&
0228            (*prev)->mark == pq_node::UNMARKED) {
0229         (*prev)->mark = pq_node::BLOCKED;
0230         (*prev)->lpos = clear_me.insert (clear_me.end(), *prev);
0231         --prev;
0232         }
0233
0234         block_count += 1 - blocked_siblings;
0235     }
0236     }
0237
0238     return true;
0239 }
0240
0241
0242 pq_node* pq_tree::where_bubble_up_failed (list<pq_leaf*>& leaves)
0243 {
0244
0245     //
0246     // Search the first leaf that leads to an interior block.
0247     //
0248
0249     pq_leaf* le;
0250     pq_node* blocked = 0;
0251
0252     list<pq_leaf*>::iterator l_it = leaves.begin();
0253     list<pq_leaf*>::iterator l_end = leaves.end();
0254     q_node* father = 0;
0255
0256     while (l_it != l_end ) {
0257     le = *l_it;
0258     blocked = leads_to_blocked (le);
0259
0260     if (blocked != 0) {
0261         //
0262         // Search the father of this block.
0263         //
0264
0265         sons_iterator it = blocked->pos;
0266         while (!(*it)->is_endmost) {
0267         ++it;
0268         }
0269
0270         father = (*it)->father->Q();
0271
0272         //
0273         // give all the children the right father.
0274         //
0275
0276         it = father->sons.begin();
0277         sons_iterator end = father->sons.end();
0278
0279         while (it != end) {
0280         if ((*it)->mark == pq_node::BLOCKED) {
0281             (*it)->father = father;
0282             (*it)->mark = pq_node::UNBLOCKED;
0283             if ((*it)->kind() != pq_node::DIR) {
0284             ++(father->pert_children);
0285             }
0286         }
0287
0288         ++it;
0289         }
0290
0291         //
0292         // We have to assure that there isn't any other interior block in the
0293         // subtree of father.
0294         //
0295
0296         pq_node* another = blocked_in_subtree (father);
0297
0298         if (another == 0) {
0299         break;
0300         }
0301     }
0302
0303     ++l_it;
0304     }
0305
0306     assert (father != 0);
0307
0308     //
0309     // delete all pertinent leaves that do not lead to father
0310     //
0311
0312     l_it = leaves.begin();
0313
0314     while (l_it != l_end ) {
0315     le = *l_it;
0316
0317     if (!leads_to (le, father)) {
0318         l_it = leaves.erase (l_it);
0319     } else {
0320         ++l_it;
0321     }
0322     }
0323
0324     return father;
0325 }
0326
0327
0328 pq_node* pq_tree::blocked_in_subtree (pq_node* n)
0329 {
0330     if (n->kind() == pq_node::LEAF) {
0331     return 0;
0332     }
0333
0334     if (n->mark == pq_node::BLOCKED) {
0335     return n;
0336     }
0337
0338     sons_iterator it = n->sons.begin();
0339     sons_iterator end = n->sons.end();
0340
0341     while (it != end) {
0342     pq_node* bl = blocked_in_subtree (*it);
0343
0344     if (bl) {
0345         return bl;
0346     }
0347
0348     ++it;
0349     }
0350
0351     return 0;
0352 }
0353
0354
0355 bool pq_tree::leads_to (pq_node* le, pq_node* other)
0356 {
0357     if (le == root) {
0358     return false;
0359     } else if (le->mark == pq_node::BLOCKED) {
0360     return false;
0361     } else if (le->mark == pq_node::UNMARKED) {
0362     return false;
0363     } else if (le->father == other) {
0364     return true;
0365     } else {
0366     return leads_to (le->father, other);
0367     }
0368 }
0369
0370 pq_node* pq_tree::leads_to_blocked (pq_node* le)
0371 {
0372     if (le == root) {
0373     return 0;
0374     } else if (le->mark == pq_node::BLOCKED) {
0375     return le;
0376     } else if (le->mark == pq_node::UNMARKED) {
0377     return 0;
0378     } else {
0379     return leads_to_blocked (le->father);
0380     }
0381 }
0382
0383
0384 bool pq_tree::reduce (list<pq_leaf*>& leaves)
0385 {
0386
0387     GTL_debug::debug_message ("REDUCING %d\n", leaves.front()->id);
0388     fail = 0;
0389
0390     if (!bubble_up (leaves)) {
0391
0392     //
0393     // Find the node that has an interior block.
0394     //
0395
0396     GTL_debug::debug_message ("Bubble-Up failed !!\n");
0397     fail = where_bubble_up_failed (leaves);
0398     }
0399
0400     queue<pq_node*> qu;
0401     pq_leaf* le;
0402     list<pq_leaf*>::iterator l_it = leaves.begin();
0403     list<pq_leaf*>::iterator l_end = leaves.end();
0404
0405     while (l_it != l_end ) {
0406     le = *l_it;
0407     qu.push (le);
0408     le->pert_leaves = 1;
0409     ++l_it;
0410     }
0411
0412     pq_node* tmp;
0413
0414     while (!qu.empty()) {
0415     tmp = qu.front();
0416     qu.pop();
0417     clear_me.erase (tmp->lpos);
0418
0419     if (tmp->mark == pq_node::BLOCKED) {
0420         pseudo = new q_node (node(), 0);
0421         sons_iterator past = tmp->pos;
0422
0423         //
0424         // Get maximal connected block of BLOCKED siblings right of tmp
0425         //
0426
0427         while ((*past)->mark == pq_node::BLOCKED) {
0428         (*past)->mark = pq_node::UNBLOCKED;
0429         (*past)->father = pseudo;
0430
0431         if ((*past)->kind() != pq_node::DIR) {
0432             pseudo->pert_children++;
0433         }
0434
0435         ++past;
0436         }
0437
0438
0439         //
0440         // Delete surrounding direction indicators
0441         //
0442
0443         --past;
0444
0445         while ((*past)->kind() == pq_node::DIR) {
0446         (*past)->clear();
0447         clear_me.erase ((*past)->lpos);
0448         --past;
0449         }
0450
0451         pseudo->pert_end = past;
0452
0453         //
0454         // Get maximal connected block of BLOCKED siblings left of tmp
0455         //
0456
0457         sons_iterator first = tmp->pos;
0458         --first;
0459
0460         while ((*first)->mark == pq_node::BLOCKED) {
0461         (*first)->mark = pq_node::UNBLOCKED;
0462             (*first)->father = pseudo;
0463
0464         if ((*first)->kind() != pq_node::DIR) {
0465             pseudo->pert_children++;
0466         }
0467
0468         --first;
0469         }
0470
0471
0472         //
0473         // Delete surrounding direction indicators
0474         //
0475
0476         ++first;
0477
0478         while ((*first)->kind() == pq_node::DIR) {
0479         (*first)->clear();
0480         clear_me.erase ((*first)->lpos);
0481         ++first;
0482         }
0483
0484         pseudo->pert_begin = first;
0485
0486         GTL_debug::debug_message ("creating pseudo-node as root\n");
0487         pseudo->mark = pq_node::UNBLOCKED;
0488         ++past;
0489         pseudo->sons.attach_sublist (first, past);
0490         pseudo->pert_cons = true;
0491         pseudo->lpos = clear_me.insert (clear_me.end(), pseudo);
0492     }
0493
0494     if (tmp->pert_leaves == pert_leaves_count) {
0495
0496         //
0497         // tmp is the root of the pertinent subtree
0498         //
0499
0500         if (tmp->kind() == pq_node::LEAF) {
0501         pert_root = tmp;
0502         GTL_debug::debug_message ("full leaf is root\n");
0503         } else if (tmp->kind() == pq_node::P_NODE) {
0504         if (P1 (tmp->P(), true)) {
0505             GTL_debug::debug_message ("P1 matched for root\n");
0506         } else if (P2 (tmp->P())) {
0507             GTL_debug::debug_message ("P2 matched for root\n");
0508         } else if (P4 (tmp->P())) {
0509             GTL_debug::debug_message ("P4 matched for root\n");
0510         } else if (P6 (tmp->P())) {
0511             GTL_debug::debug_message ("P6 matched for root\n");
0512         } else {
0513             GTL_debug::debug_message ("NO MATCHING FOR P-ROOT\n");
0514             fail = tmp;
0515             failed_at_root = true;
0516             return false;
0517         }
0518         } else {
0519         if (!tmp->Q()->pert_cons) {
0520             GTL_debug::debug_message ("pertinent children not consecutive\n");
0521             fail = tmp;
0522             failed_at_root = true;
0523             return false;
0524         } else if (Q1 (tmp->Q(), true)) {
0525             GTL_debug::debug_message ("Q1 matched for root\n");
0526         } else if (Q2 (tmp->Q(), true)) {
0527             GTL_debug::debug_message ("Q2 matched for root\n");
0528         } else if (Q3 (tmp->Q())) {
0529             GTL_debug::debug_message ("Q3 matched for root\n");
0530         } else {
0531             GTL_debug::debug_message ("NO MATCHING FOR Q-ROOT\n");
0532
0533             if (tmp == pseudo) {
0534
0535             //
0536             // search the real father
0537             //
0538
0539             sons_iterator it = pseudo->sons.begin();
0540             pseudo->sons.front()->is_endmost = false;
0541             pseudo->sons.back()->is_endmost = false;
0542             pseudo->sons.detach_sublist();
0543             assert (pseudo->sons.empty());
0544
0545             while (!(*it)->is_endmost) {
0546                 --it;
0547             }
0548
0549             tmp = (*it)->father;
0550             q_node* q_tmp = tmp->Q();
0551             q_tmp->pert_begin = pseudo->pert_begin;
0552             q_tmp->pert_end = pseudo->pert_end;
0553             q_tmp->partial_count = pseudo->partial_count;
0554             q_tmp->full_count = pseudo->full_count;
0555             q_tmp->pert_cons = pseudo->pert_cons;
0556
0557             for (int i = 0; i < q_tmp->partial_count; ++i) {
0558                 q_tmp->partial_pos[i] = pseudo->partial_pos[i];
0559             }
0560
0561             delete pseudo;
0562             pseudo = 0;
0563             }
0564
0565             fail = tmp;
0566             failed_at_root = true;
0567             return false;
0568         }
0569         }
0570
0571     } else {
0572
0573         //
0574         // tmp is not the root of the pertinent subtree.
0575         //
0576
0577         if (tmp == pseudo || tmp == root) {
0578
0579         //
0580         // This should not happen when bubble_up was true.
0581         //
0582
0583         assert (false);
0584
0585         } else {
0586         pq_node* father = tmp->father;
0587
0588         if (tmp->kind() == pq_node::LEAF) {
0589             father->full (tmp->pos);
0590             tmp->clear();
0591             GTL_debug::debug_message ("full leaf processed\n");
0592
0593         } else if (tmp->kind() == pq_node::P_NODE) {
0594             if (P1 (tmp->P(), false)) {
0595             GTL_debug::debug_message ("P1 matched for non-root\n");
0596             } else if (P3 (tmp->P())) {
0597             GTL_debug::debug_message ("P3 matched for non-root\n");
0598             } else if (P5 (tmp->P())) {
0599             GTL_debug::debug_message ("P5 matched for non-root\n");
0600             } else {
0601             GTL_debug::debug_message ("NO MATCHING FOR P-NON-ROOT\n");
0602             fail = tmp;
0603             failed_at_root = false;
0604             return false;
0605             }
0606
0607         } else {
0608             if (!tmp->Q()->pert_cons) {
0609             GTL_debug::debug_message ("pertinent children not consecutive\n");
0610             fail = tmp;
0611             return false;
0612             } else if (Q1 (tmp->Q(), false)) {
0613             GTL_debug::debug_message ("Q1 matched for non-root\n");
0614             } else if (Q2 (tmp->Q(), false)) {
0615             GTL_debug::debug_message ("Q2 matched for non-root\n");
0616             } else {
0617             GTL_debug::debug_message ("NO MATCHING FOR Q-NON-ROOT\n");
0618             fail = tmp;
0619             failed_at_root = false;
0620             return false;
0621             }
0622         }
0623
0624
0625         //
0626         // If all the other pertinent siblings of tmp have already been
0627         // matched father of tmp is queued.
0628         //
0629
0630         --(father->pert_children);
0631
0632         if (father->pert_children == 0) {
0633             if (father == fail) {
0634             failed_at_root = false;
0635             return false;
0636             } else {
0637             qu.push (father);
0638             }
0639         }
0640         }
0641     }
0642     }
0643
0644     return true;
0645 }
0646
0647
0648 void pq_tree::reset ()
0649 {
0650     pq_node* tmp;
0651
0652     while (!clear_me.empty()) {
0653     tmp = clear_me.front();
0654     GTL_debug::debug_message ("Clearing %d\n", tmp->id);
0655     clear_me.pop_front();
0656     tmp->clear();
0657     tmp->pert_children = 0;
0658     }
0659
0660     if (pert_root) {
0661     pert_root->clear();
0662     pert_root = 0;
0663     }
0664
0665     if (pseudo) {
0666     pseudo->sons.front()->is_endmost = false;
0667     pseudo->sons.back()->is_endmost = false;
0668     pseudo->sons.detach_sublist();
0669     assert (pseudo->sons.empty());
0670     delete pseudo;
0671     pseudo = 0;
0672     }
0673
0674     if (fail) {
0675     fail->clear();
0676     fail = 0;
0677     }
0678 }
0679
0680
0681 void pq_tree::dfs (pq_node* act, planar_embedding& em,
0682            list<direction_indicator>& dirs)
0683 {
0684     if (act->kind() == pq_node::LEAF) {
0685     em.push_back (act->n, ((pq_leaf*) act)->e);
0686     return;
0687     }
0688
0689     sons_iterator it = act->sons.begin();
0690     sons_iterator end = act->sons.end();
0691
0692     while (it != end) {
0693     if ((*it)->kind() == pq_node::DIR) {
0694         direction_indicator* dir = (*it)->D();
0695         if (dir->mark != pq_node::UNMARKED) {
0696         clear_me.erase (dir->lpos);
0697         }
0698         sons_iterator tmp = it;
0699
0700         if (++tmp == ++(dir->pos)) {
0701         dir->direction = true;
0702         } else {
0703         dir->direction = false;
0704         }
0705
0706         dirs.push_back (*dir);
0707
0708     } else {
0709         dfs (*it, em, dirs);
0710     }
0711
0712     ++it;
0713     }
0714 }
0715
0716
0717 void pq_tree::replace_pert (int id, node _n, const list<pq_leaf*>& li,
0718                 planar_embedding* em, list<direction_indicator>* dirs)
0719 {
0720     assert (pert_root);
0721     assert (!li.empty());
0722     pq_leaf* tmp = 0;
0723     list<pq_leaf*>::const_iterator it;
0724     list<pq_leaf*>::const_iterator end = li.end();
0725     sons_list sons;
0726     int size = 0;
0727
0728     for (it = li.begin(); it != end; ++it) {
0729     tmp = *it;
0730     tmp->pos = sons.insert (sons.end(), tmp);
0731     ++size;
0732     }
0733
0734     pq_node* ins;
0735
0736     if (size == 1) {
0737         sons.erase (tmp->pos);
0738         ins = tmp;
0739     } else {
0740     ins = new p_node(_n, id, sons);
0741     }
0742
0743     if (pert_root->kind() == pq_node::Q_NODE) {
0744     q_node* q_root = pert_root->Q();
0745     sons_iterator it = q_root->pert_begin;
0746     sons_iterator end = q_root->pert_end;
0747     sons_iterator tmp = it;
0748     sons_iterator sons_end = q_root->sons.end();
0749     --tmp;
0750
0751     while (tmp != sons_end) {
0752         if ((*tmp)->kind() != pq_node::DIR) {
0753         break;
0754         }
0755
0756         --tmp;
0757     }
0758
0759     it = ++tmp;
0760
0761     tmp = end;
0762     ++tmp;
0763
0764     while (tmp != sons_end) {
0765         if ((*tmp)->kind() != pq_node::DIR) {
0766         break;
0767         }
0768
0769         ++tmp;
0770     }
0771
0772     end = --tmp;
0773
0774     ins->is_endmost = (*end)->is_endmost;
0775     ++end;
0776
0777     while (it != end) {
0778         if (em && dirs) {
0779         if ((*it)->kind() == pq_node::DIR) {
0780             direction_indicator* dir = (*it)->D();
0781             clear_me.erase (dir->lpos);
0782             sons_iterator tmp = it;
0783
0784             if (++tmp == ++(dir->pos)) {
0785             dir->direction = true;
0786             } else {
0787             dir->direction = false;
0788             }
0789
0790             dirs->push_back (*dir);
0791         } else {
0792             dfs (*it, *em, *dirs);
0793         }
0794         }
0795
0796         delete *it;
0797         it = pert_root->sons.erase (it);
0798     }
0799
0800     if (pert_root->sons.empty() && pert_root != pseudo) {
0801         ins->pos = pert_root->pos;
0802         ins->father = pert_root->father;
0803         ins->is_endmost = pert_root->is_endmost;
0804         ins->up = pert_root->up;
0805         ins->up_id = pert_root->up_id;
0806
0807         if (root == pert_root) {
0808         root = ins;
0809         } else {
0810         *(pert_root->pos) = ins;
0811         }
0812
0813         delete pert_root;
0814         pert_root = 0;
0815
0816     } else {
0817         if (em && dirs) {
0818         direction_indicator* ind = new direction_indicator (_n, id);
0819         ind->is_endmost = false;
0820         ind->pos = pert_root->sons.insert (end, ind);
0821         }
0822
0823         ins->pos = pert_root->sons.insert (end, ins);
0824         ins->father = pert_root;
0825         ins->up = _n;
0826         ins->up_id = id;
0827     }
0828
0829     } else {
0830     if (em && dirs) {
0831         dfs (pert_root, *em, *dirs);
0832     }
0833
0834     ins->is_endmost = pert_root->is_endmost;
0835     ins->father = pert_root->father;
0836     ins->pos = pert_root->pos;
0837     ins->up = pert_root->up;
0838     ins->up_id = pert_root->up_id;
0839
0840     if (root == pert_root) {
0841         root = ins;
0842     } else {
0843         *(pert_root->pos) = ins;
0844     }
0845
0846     delete pert_root;
0847     pert_root = 0;
0848     }
0849 }
0850
0851 void pq_tree::get_frontier (planar_embedding& em,
0852                 list<direction_indicator>& dirs)
0853 {
0854     dfs (root, em, dirs);
0855 }
0856
0857 //------------------------------------------------------------------------ P1
0858 // Requirements:
0859 //
0860 // * x is a P-node having only full children
0861 // * wheter x is the root or not is specified by the second parameter
0862 //
0863
0864 bool pq_tree::P1 (p_node* x, bool is_root)
0865 {
0866     if (x->child_count == x->full_count) {
0867     if (!is_root) {
0868         x->father->full (x->pos);
0869     } else {
0870         pert_root = x;
0871     }
0872
0873     x->sons.splice (x->sons.end(), x->full_sons.begin(),
0874         x->full_sons.end());
0875     x->clear();
0876     return true;
0877     }
0878
0879     return false;
0880 }
0881
0882
0883 //----------------------------------------------------------------------- P2
0884 // Requirements:
0885 //
0886 // * x is a P-node having both full and empty children
0887 // * x has no partial children
0888 // * x is the root of the pertinent subtree
0889 //     ==> more than one pertinent child
0890 // * P1 didn't match
0891 //     ==> at least one non-full child
0892 //
0893 bool pq_tree::P2 (p_node* x)
0894 {
0895     if (x->partial_count != 0) {
0896     return false;
0897     }
0898
0899     p_node* ins = new p_node(x->n, x->id, x->full_sons);
0900     ins->father = x;
0901     ins->is_endmost = true;
0902     ins->pos = x->sons.insert (x->sons.end(), ins);
0903     x->child_count -= (x->full_count - 1);
0904     x->clear();
0905     pert_root = ins;
0906     return true;
0907 }
0908
0909
0910 //------------------------------------------------------------------------ P3
0911 // Requirements:
0912 //
0913 // * x is a P-node having both full and empty children.
0914 // * x isn't the root of the pertinent subtree.
0915 // * P1 didn't match.
0916 //   ==> at least one non-full child.
0917 // * x has no partial children
0918 //
0919
0920 bool pq_tree::P3 (p_node* x)
0921 {
0922     if (x->partial_count != 0) {
0923     return false;
0924     }
0925
0926     q_node* new_q = new q_node (x->n, x->id);
0927     pq_node* father = x->father;
0928     pq_node* ins;
0929
0930     *(x->pos) = new_q;
0931     new_q->pos = x->pos;
0932     new_q->up = x->up;
0933     new_q->up_id = x->up_id;
0934     new_q->is_endmost = x->is_endmost;
0935     new_q->father = father;
0936     new_q->pert_leaves = x->pert_leaves;
0937
0938     if (x->full_count > 1) {
0939     ins = new p_node (x->n, x->id, x->full_sons);
0940     } else {
0941         ins = x->full_sons.front();
0942         x->full_sons.erase (x->full_sons.begin());
0943         assert (x->full_sons.empty());
0944     }
0945
0946     ins->up = x->n;
0947     ins->up_id = x->id;
0948     ins->is_endmost = true;
0949     ins->father = new_q;
0950     ins->pos = new_q->sons.insert (new_q->sons.end(), ins);
0951     new_q->pert_cons = true;
0952     new_q->pert_begin = ins->pos;
0953     new_q->pert_end = ins->pos;
0954
0955     if (x->child_count - x->full_count > 1) {
0956     ins = x;
0957     ins->up = x->n;
0958     ins->up_id = x->id;
0959     x->child_count -= x->full_count;
0960     x->clear();
0961     } else {
0962         ins = x->sons.front();
0963     ins->up = x->n;
0964     ins->up_id = x->id;
0965         x->sons.erase (x->sons.begin());
0966         assert (x->sons.empty());
0967         delete x;
0968     }
0969
0970     ins->is_endmost = true;
0971     ins->father = new_q;
0972     ins->pos = new_q->sons.insert (new_q->pert_begin, ins);
0973     father->partial (new_q->pos);
0974
0975     return true;
0976 }
0977
0978 //------------------------------------------------------------------------ P4
0979 // Requirements:
0980 //
0981 // * x is a P-node and the root of the pertinent subtree.
0982 //   ==> more than one non-empty child, i.e. at least one full child.
0983 // * x has excactly one partial child
0984 // * P1 and P2 didn't match
0985 //   ==> at least one partial child
0986 //
0987 bool pq_tree::P4 (p_node* x)
0988 {
0989     if (x->partial_count > 1) {
0990     return false;
0991     }
0992
0993     q_node* part = x->partial_sons.front()->Q();
0994     part->n = x->n;
0995     part->id = x->id;
0996     pq_node* ins;
0997
0998     if (x->full_count > 1) {
0999     ins = new p_node (x->n, x->id, x->full_sons);
1000     } else {
1001         ins = x->full_sons.front();
1002         x->full_sons.erase (x->full_sons.begin());
1003         assert (x->full_sons.empty());
1004     }
1005
1006     part->sons.back()->is_endmost = false;
1007     ins->is_endmost = true;
1008
1009     ins->up = x->n;
1010     ins->up_id = x->id;
1011     ins->father = part;
1012     ins->pos = part->sons.insert (part->sons.end(), ins);
1013     part->pert_end = ins->pos;
1014     x->child_count -= x->full_count;
1015
1016     if (x->child_count == 1) {
1017     if (root == x) {
1018         root = part;
1019     } else {
1020         *(x->pos) = part;
1021     }
1022
1023     part->pos = x->pos;
1024     part->is_endmost = x->is_endmost;
1025     part->father = x->father;
1026     part->up = x->up;
1027     part->up_id = x->up_id;
1028     x->partial_sons.erase (x->partial_sons.begin());
1029
1030     delete x;
1031     } else {
1032     x->sons.splice (x->sons.end(), part->pos);
1033     x->clear();
1034     }
1035
1036     pert_root = part;
1037     return true;
1038 }
1039
1040
1041 //------------------------------------------------------------------------ P5
1042 // Requirements:
1043 //
1044 // * x is a P-node and not the root of the pertinent subtree
1045 // * x has exactly one partial child.
1046 // * P1 and P3 didn't match
1047 //  ==> at least one partial child
1048 //
1049 bool pq_tree::P5 (p_node* x)
1050 {
1051     if (x->partial_count > 1) {
1052     return false;
1053     }
1054
1055     pq_node* father = x->father;
1056     q_node* part = x->partial_sons.front()->Q();
1057     part->n = x->n;
1058     part->id = x->id;
1059     part->up = x->up;
1060     part->up_id = x->up_id;
1061
1062     x->partial_sons.erase (x->partial_sons.begin());
1063     part->is_endmost = x->is_endmost;
1064     part->father = father;
1065     *(x->pos) = part;
1066     part->pos = x->pos;
1067     part->pert_leaves = x->pert_leaves;
1068     pq_node* ins;
1069
1070     if (x->full_count > 1) {
1071     ins = new p_node (x->n, x->id, x->full_sons);
1072     } else if (x->full_count == 1) {
1073     ins = x->full_sons.front();
1074     x->full_sons.erase (x->full_sons.begin());
1075     assert (x->full_sons.empty());
1076     } else {
1077     ins = 0;
1078     }
1079
1080     if (ins) {
1081     ins->up = x->n;
1082     ins->up_id = x->id;
1083     part->sons.back()->is_endmost = false;
1084     ins->is_endmost = true;
1085     ins->father = part;
1086     ins->pos = part->sons.insert (part->sons.end(), ins);
1087     part->pert_end = ins->pos;
1088     }
1089
1090     x->child_count -= (x->full_count + 1);
1091
1092     if (x->child_count > 1) {
1093     ins = x;
1094     ins->up = x->n;
1095     ins->up_id = x->id;
1096     x->clear();
1097     } else if (x->child_count == 1) {
1098     ins = x->sons.front();
1099     ins->up = x->n;
1100     ins->up_id = x->id;
1101     x->sons.erase (x->sons.begin());
1102     delete x;
1103     } else {
1104     ins = 0;
1105     delete x;
1106     }
1107
1108     if (ins) {
1109     part->sons.front()->is_endmost = false;
1110     ins->is_endmost = true;
1111     ins->father = part;
1112     ins->pos = part->sons.insert (part->sons.begin(), ins);
1113     }
1114
1115     father->partial (part->pos);
1116     return true;
1117 }
1118
1119
1120 //------------------------------------------------------------------------ P6
1121 // Requirements:
1122 //
1123 // * x is the root of the pertinent subtree and has two partial children.
1124 // * P1, P2 and P4 didn't match
1125 //   ==> at least two partial children.
1126 //
1127 bool pq_tree::P6 (p_node* x)
1128 {
1129     if (x->partial_count > 2) {
1130     return false;
1131     }
1132
1133
1134     q_node* part2 = x->partial_sons.front()->Q();
1135     x->partial_sons.erase (x->partial_sons.begin());
1136     q_node* part1 = x->partial_sons.front()->Q();
1137     part1->n = x->n;
1138     part1->id = x->id;
1139     pq_node* ins;
1140
1141     if (x->full_count > 1) {
1142     ins = new p_node (x->n, x->id, x->full_sons);
1143     } else if (x->full_count == 1) {
1144     ins = x->full_sons.front();
1145     x->full_sons.erase (x->full_sons.begin());
1146     assert (x->full_sons.empty());
1147     } else {
1148     ins = 0;
1149     }
1150
1151     part1->sons.back()->is_endmost = false;
1152
1153     if (ins) {
1154     ins->up = x->n;
1155     ins->up_id = x->id;
1156     ins->is_endmost = false;
1157     ins->pos = part1->sons.insert (part1->sons.end(), ins);
1158     }
1159
1160     part2->turn ();
1161     part2->sons.front()->is_endmost = false;
1162     part2->sons.back()->father = part1;
1163     part1->sons.splice (part1->sons.end(), part2->sons.begin(),
1164     part2->sons.end());
1165     part1->pert_end = part2->pert_begin;
1166     part1->pert_end.reverse();
1167     x->child_count -= (x->full_count + 1);
1168     delete part2;
1169
1170     if (x->child_count == 1) {
1171     if (root == x) {
1172         root = part1;
1173     } else {
1174         *(x->pos) = part1;
1175     }
1176     part1->pos = x->pos;
1177     part1->is_endmost = x->is_endmost;
1178     part1->father = x->father;
1179     part1->up = x->up;
1180     part1->up_id = x->up_id;
1181     x->partial_sons.erase (x->partial_sons.begin());
1182
1183     delete x;
1184     } else {
1185     x->sons.splice (x->sons.end(), x->partial_sons.begin());
1186     x->clear();
1187     }
1188
1189     pert_root = part1;
1190     return true;
1191 }
1192
1193 //------------------------------------------------------------------------ Q1
1194 // Requirements:
1195 //
1196 // * x is a Q-node having only full children
1197 // * wheter x is the root or not is specified by the second parameter
1198 //
1199 bool pq_tree::Q1 (q_node* x, bool is_root)
1200 {
1201     if (x->partial_count > 0) return false;
1202
1203     if (*(x->pert_begin) == x->sons.front()
1204     && *(x->pert_end) == x->sons.back()) {
1205
1206     if (!is_root) {
1207         x->father->full (x->pos);
1208     } else {
1209         pert_root = x;
1210     }
1211
1212     return true;
1213     }
1214
1215     return false;
1216 }
1217
1218
1219 //------------------------------------------------------------------------ Q2
1220 // Requirements:
1221 //
1222 // * Q1 didn't match ==> x has at least one non-full child.
1223 // * wheter x is the root or not is specified by the second parameter
1224 // * x has at most one partial child
1225 // * If x has empty children, the partial child must be at pert_begin;
1226 //   if x hasn't any empty children the partial child is allowed to be at
1227 //   pert_end, since this can be transformed into the former case.
1228 //
1229 bool pq_tree::Q2 (q_node* x, bool is_root)
1230 {
1231     if (x->partial_count > 1) {
1232     return false;
1233     }
1234
1235     if (x->partial_count == 1) {
1236     if (x->partial_pos[0] == x->pert_end &&
1237         x->pert_begin == x->sons.begin() &&
1238         x->pert_begin != x->pert_end)
1239     {
1240         if (!is_root) {
1241         q_node* part = (*(x->pert_end))->Q();
1242         x->turn();
1243         sons_iterator tmp = x->pert_begin;
1244         x->pert_begin = x->pert_end;
1245         x->pert_end = tmp;
1246         x->pert_begin.reverse();
1247         x->pert_end.reverse();
1248         x->merge (x->pert_begin);
1249         x->pert_begin = part->pert_begin;
1250         delete part;
1251         } else {
1252         q_node* part = (*(x->pert_end))->Q();
1253         part->turn();
1254         x->merge (x->pert_end);
1255         x->pert_end = x->pert_begin;
1256         x->pert_begin = part->pert_begin;
1257         x->pert_end.reverse();
1258         // x->pert_begin.reverse();
1259         delete part;
1260         }
1261
1262     } else if (x->partial_pos[0] != x->pert_begin) {
1263         return false;
1264     } else {
1265         //
1266         // Partial child is at pert_begin and x has at least one
1267         // empty child (i.e. pert_begin != sons.begin())
1268         //
1269
1270         q_node* part = x->merge (x->pert_begin);
1271
1272         if (x->pert_begin == x->pert_end) {
1273         x->pert_end = part->pert_end;
1274         }
1275
1276         x->pert_begin = part->pert_begin;
1277         delete part;
1278     }
1279     }
1280
1281     if (!is_root) {
1282     x->father->partial (x->pos);
1283     } else {
1284     pert_root = x;
1285     }
1286
1287     return true;
1288 }
1289
1290
1291 //------------------------------------------------------------------------ Q3
1292 // Requirements:
1293 //
1294 // * x is the root of the pertinent subtree.
1295 // * Q1 and Q2 didn't match
1296 //   ==> at least one partial child
1297 // * if there is only one partial child it must be at pert_end, and x must
1298 //   have at least one empty and one full child.
1299 //   if there are two partial children they must be at pert_begin and
1300 //   pert_end.
1301 //
1302 bool pq_tree::Q3 (q_node* x)
1303 {
1304     if (x->partial_count > 2 || x->partial_count < 1) return false;
1305
1306     if (x->partial_count == 1) {
1307     if (x->partial_pos[0] != x->pert_end) return false;
1308
1309     //
1310     // One partial child at pert_end.
1311     //
1312
1313     } else {
1314     if (x->partial_pos[0] != x->pert_end) {
1315         if (x->partial_pos[1] != x->pert_end ||
1316         x->partial_pos[0] != x->pert_begin) return false;
1317     } else {
1318         if (x->partial_pos[1] != x->pert_begin) return false;
1319     }
1320
1321     //
1322     // One partial child at pert_begin and one at pert_end
1323     //
1324     }
1325
1326     q_node* part = (*(x->pert_end))->Q();
1327     part->turn();
1328     x->merge (x->pert_end);
1329     x->pert_end = part->pert_begin;
1330     x->pert_end.reverse();
1331     delete part;
1332
1333     if (x->partial_count == 2) {
1334     part = x->merge (x->pert_begin);
1335     x->pert_begin = part->pert_begin;
1336     delete part;
1337     }
1338
1339     pert_root = x;
1340     return true;
1341 }
1342
1343
1344
1345
1346 GTL_EXTERN ostream& operator<< (ostream& os, const pq_tree& tree)
1347 {
1348     if (!tree.root) return os;
1349
1350     int id = 0;
1351     pair<pq_node*,int> tmp;
1352     queue<pair<pq_node*,int> > qu;
1353     pq_node* act;
1354
1355     os << "graph [\n" << "directed 1" << endl;
1356     tree.root->write (os, id);
1357     tmp.first = tree.root;
1358     tmp.second = id;
1359     ++id;
1360     qu.push (tmp);
1361
1362     while (!qu.empty()) {
1363     tmp = qu.front();
1364     qu.pop();
1365
1366     if (tmp.first->kind() == pq_node::Q_NODE || tmp.first->kind() == pq_node::P_NODE) {
1367             pq_tree::sons_iterator it = tmp.first->sons.begin();
1368             pq_tree::sons_iterator end = tmp.first->sons.end();
1369
1370         for (; it != end; ++it) {
1371         act = *it;
1372         act->write (os, id);
1373
1374         os << "edge [\n" << "source " << tmp.second << endl;
1375         os << "target " << id << "\n]" << endl;
1376
1377         qu.push (pair<pq_node*,int> (act, id));
1378         ++id;
1379         }
1380         }
1381
1382         if (tmp.first->kind() == pq_node::P_NODE) {
1383             p_node* P = tmp.first->P();
1384             pq_tree::sons_iterator it = P->full_sons.begin();
1385             pq_tree::sons_iterator end = P->full_sons.end();
1386
1387             for (; it != end; ++it) {
1388                 act = *it;
1389                 act->write (os, id);
1390
1391                 os << "edge [\n" << "source " << tmp.second << endl;
1392                 os << "target " << id << "\n]" << endl;
1393
1394                 qu.push (pair<pq_node*,int> (act, id));
1395                 ++id;
1396             }
1397
1398             it = P->partial_sons.begin();
1399             end = P->partial_sons.end();
1400
1401             for (; it != end; ++it) {
1402                 act = *it;
1403                 act->write (os, id);
1404
1405                 os << "edge [\n" << "source " << tmp.second << endl;
1406                 os << "target " << id << "\n]" << endl;
1407
1408                 qu.push (pair<pq_node*,int> (act, id));
1409                 ++id;
1410             }
1411         }
1412     }
1413
1414     os << "]" << endl;
1415
1416     return os;
1417 }
1418
1419 pq_tree::sons_iterator
1420 pq_tree::remove_dir_ind(q_node* q_fail, sons_iterator s_it)
1421 {
1422     direction_indicator* dir = (*s_it)->D();
1423     sons_iterator res = q_fail->sons.erase(s_it);
1424     clear_me.erase(dir->lpos);
1425     delete dir;
1426     return res;
1427 }
1428
1429
1430 //--------------------------------------------------------------------------
1431 //   DEBUGGING
1432 //--------------------------------------------------------------------------
1433
1434 bool pq_tree::integrity_check () const
1435 {
1436     if (!root) return true;
1437
1438     queue<pq_node*> qu;
1439     qu.push (root);
1440     pq_node* tmp;
1441
1442     while (!qu.empty()) {
1443     tmp = qu.front();
1444     qu.pop();
1445
1446     if (tmp->kind() == pq_node::LEAF) continue;
1447     if (tmp->kind() == pq_node::DIR) continue;
1448
1449     sons_iterator it = tmp->sons.begin();
1450     sons_iterator end = tmp->sons.end();
1451     int count = 0;
1452     int endmost_count = 0;
1453
1454     for (; it != end; ++it) {
1455         ++count;
1456         if ((*it)->is_endmost) {
1457         ++endmost_count;
1458
1459         if ((*it)->father != tmp) {
1460             GTL_debug::debug_message ("Wrong father !!!\n");
1461             GTL_debug::close_debug();
1462             return false;
1463         }
1464         }
1465
1466         if ((*it)->pos != it) {
1467         GTL_debug::debug_message ("Wrong position !!\n");
1468         GTL_debug::close_debug();
1469         return false;
1470         }
1471
1472         qu.push (*it);
1473     }
1474
1475     if (tmp->kind() == pq_node::P_NODE
1476         && count != (tmp->P()->child_count)) {
1477         GTL_debug::debug_message ("Wrong number of children !!!\n");
1478         GTL_debug::close_debug();
1479         return false;
1480     }
1481
1482     if (tmp->kind() == pq_node::Q_NODE && count < 2) {
1483         GTL_debug::debug_message ("Q-Node with too few children !!\n");
1484         GTL_debug::close_debug();
1485         return false;
1486     }
1487
1488     if (tmp->kind() == pq_node::P_NODE && count < 2) {
1489         GTL_debug::debug_message ("P-Node with too few children !!\n");
1490         GTL_debug::close_debug();
1491         return false;
1492     }
1493
1494     if (tmp->kind() == pq_node::Q_NODE) {
1495         if (endmost_count == 2) {
1496         if (!(tmp->sons.front()->is_endmost &&
1497             tmp->sons.back()->is_endmost)) {
1498             GTL_debug::debug_message ("Q-node with inner children labeled endmost\n");
1499             GTL_debug::close_debug();
1500             return false;
1501         }
1502         } else {
1503         GTL_debug::debug_message ("Q-node with too many or too few endmost children\n");
1504         GTL_debug::close_debug();
1505         return false;
1506         }
1507     }
1508     }
1509
1510     return true;
1511 }
1512
1513 /*
1514 void pq_tree::insert (pq_node* father, pq_node* ins) {
1515     ins->father = father;
1516     ins->is_endmost = true;
1517
1518     if (father->kind() == pq_node::Q_NODE) {
1519     father->sons.back()->is_endmost = false;
1520     } else {
1521     ((p_node*)father)->child_count++;
1522     }
1523
1524     ins->pos = father->sons.insert (father->sons.end(), ins);
1525 }
1526
1527
1528 p_node* pq_tree::insert_P (pq_node* father, sons_list& sons)
1529 {
1530     p_node* p = new p_node();
1531     insert (father, p);
1532     pq_node* tmp;
1533
1534     sons_iterator it = sons.begin();
1535     sons_iterator end = sons.end();
1536
1537     for (; it != end; ++it) {
1538     p->child_count++;
1539     tmp = *it;
1540     tmp->father = p;
1541     tmp->is_endmost = true;
1542     tmp->pos  = p->sons.insert (p->sons.end(), tmp);
1543
1544     if (tmp->kind() == pq_node::LEAF) {
1545         leaves.push_back ((pq_leaf*)tmp);
1546     }
1547     }
1548
1549     return p;
1550 }
1551
1552
1553 q_node* pq_tree::insert_Q (pq_node* father, sons_list& sons)
1554 {
1555     q_node* q = new q_node();
1556     insert (father, q);
1557     pq_node* tmp;
1558     sons_iterator it = sons.begin();
1559     sons_iterator end = sons.end();
1560
1561     for (; it != end; ++it) {
1562     tmp = *it;
1563     tmp->is_endmost = false;
1564     tmp->pos = q->sons.insert (q->sons.end(), tmp);
1565
1566     if (tmp->kind() == pq_node::LEAF) {
1567         leaves.push_back (tmp->L());
1568     }
1569     }
1570
1571     q->sons.front()->father = q;
1572     q->sons.front()->is_endmost = true;
1573     q->sons.back()->father = q;
1574     q->sons.back()->is_endmost = true;
1575
1576     return q;
1577 }
1578
1579 */
1580
1581 __GTL_END_NAMESPACE
1582
1583 //--------------------------------------------------------------------------
1584 //   end of file
1585 //--------------------------------------------------------------------------