gtl/src/pq_node.cpp

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //   pq_node.cpp
0005 //
0006 //==========================================================================
0007 // $Id: pq_node.cpp,v 1.12 2002/10/04 08:07:36 chris Exp $
0008
0009 #include <GTL/pq_node.h>
0010
0011 #ifdef __GTL_MSVCC
0012 #   ifdef _DEBUG
0013 #   ifndef SEARCH_MEMORY_LEAKS_ENABLED
0014 #   error SEARCH NOT ENABLED
0015 #   endif
0016 #   define new DEBUG_NEW
0017 #   undef THIS_FILE
0018     static char THIS_FILE[] = __FILE__;
0019 #   endif   // _DEBUG
0020 #endif  // __GTL_MSVCC
0021
0022 __GTL_BEGIN_NAMESPACE
0023
0024 pq_node::~pq_node ()
0025 {
0026     while (!sons.empty()) {
0027     pq_node* tmp = sons.front();
0028     sons.erase (sons.begin());
0029     delete tmp;
0030     }
0031 }
0032
0033
0034 //--------------------------------------------------------------------------
0035 //   P-NODE
0036 //--------------------------------------------------------------------------
0037
0038 p_node::p_node (node n_, int id_) : pq_node (n_, id_), partial_count (0), full_count (0)
0039 {
0040 }
0041
0042 p_node::p_node (node n_, int id_, symlist<pq_node*>& s) :
0043     pq_node (n_, id_), child_count (0), partial_count (0), full_count (0)
0044 {
0045     sons.splice (sons.end(), s.begin(), s.end());
0046
0047     iterator it = sons.begin();
0048     iterator end = sons.end();
0049
0050     for (; it != end; ++it) {
0051     ++child_count;
0052     (*it)->is_endmost = true;
0053     (*it)->father = this;
0054     }
0055 }
0056
0057 void p_node::clear ()
0058 {
0059     pq_node::clear();
0060     partial_count = full_count = 0;
0061     if (!full_sons.empty())
0062     sons.splice (sons.end(), full_sons.begin(), full_sons.end());
0063
0064     if (!partial_sons.empty())
0065     sons.splice (sons.end(), partial_sons.begin(), partial_sons.end());
0066 }
0067
0068 inline void p_node::partial (iterator it)
0069 {
0070     ++partial_count;
0071     pert_leaves += (*it)->pert_leaves;
0072     partial_sons.splice (partial_sons.end(), it);
0073 }
0074
0075 inline void p_node::full (iterator it)
0076 {
0077     ++full_count;
0078     pert_leaves += (*it)->pert_leaves;
0079     full_sons.splice (full_sons.end(), it);
0080 }
0081
0082
0083 inline void p_node::write (ostream& os, int _id)
0084 {
0085     os << "node [\n" << "id " << _id << endl;
0086     os << "label \"" << id << "\nP" << "\"\n";
0087     os << "graphics [\n" << "x 100\n" << "y 100\n";
0088     if (mark == UNBLOCKED) {
0089     os << "outline \"#0000ff\"\n";
0090     } else if (mark == BLOCKED) {
0091     os << "outline \"#ff0000\"\n";
0092     }
0093     os << "type \"oval\"\n" << "]" << endl;
0094     os << "LabelGraphics [\n";
0095     os << "type \"text\"\n]\n]" << endl;
0096 }
0097
0098 //--------------------------------------------------------------------------
0099 //   Q-NODE
0100 //--------------------------------------------------------------------------
0101
0102 q_node::q_node (node n_, int id_) : pq_node (n_, id_), partial_count (0), full_count (0)
0103 {
0104 }
0105
0106 inline void q_node::partial (iterator it)
0107 {
0108     if (partial_count < 3) {
0109     partial_pos[partial_count] = it;
0110     }
0111
0112     pert_leaves += (*it)->pert_leaves;
0113     ++partial_count;
0114
0115     if (pert_begin == iterator()) {
0116     pertinent (it);
0117     }
0118 }
0119
0120
0121 inline void q_node::full (iterator it)
0122 {
0123     ++full_count;
0124     pert_leaves += (*it)->pert_leaves;
0125
0126
0127     if (pert_begin == iterator()) {
0128     pertinent (it);
0129     }
0130 }
0131
0132
0133 void q_node::pertinent (iterator it)
0134 {
0135     iterator end = sons.end();
0136     iterator tmp = it;
0137     pq_node* first;
0138     pq_node* last;
0139     pert_end = it;
0140     ++tmp;
0141     int pert_block_count = 1;
0142
0143     while (tmp != end) {
0144     if ((*tmp)->mark != UNBLOCKED) {
0145         break;
0146     }
0147
0148     if ((*tmp)->kind () != DIR) {
0149         ++pert_block_count;
0150         pert_end = tmp;
0151     }
0152
0153     ++tmp;
0154     }
0155
0156     last = *pert_end;
0157
0158     pert_begin = tmp = it;
0159     --tmp;
0160
0161     while (tmp != end) {
0162     if ((*tmp)->mark != UNBLOCKED) {
0163         break;
0164     }
0165
0166     if ((*tmp)->kind () != DIR) {
0167         ++pert_block_count;
0168         pert_begin = tmp;
0169     }
0170
0171     --tmp;
0172     }
0173
0174     first = *pert_begin;
0175     pert_cons = (pert_block_count == pert_children);
0176
0177     //
0178     // it must be true, that either first or last is in
0179     // {sons.front(), sons.back()} (or both). Thus we are able to achive
0180     // the following normalization: pert_end is *always* sons.last() and
0181     // pert_begin is some other child, such that ++pert_begin leads towards
0182     // pert_end.
0183     //
0184
0185     if (pert_cons) {
0186     if (last == sons.front()) {
0187         turn();
0188     } else if (last != sons.back()) {
0189         tmp = pert_begin;
0190         pert_begin = pert_end;
0191         pert_end = tmp;
0192         pert_end.reverse();
0193         pert_begin.reverse();
0194
0195         if (first == sons.front()) {
0196         turn();
0197         } else if (first != sons.back()) {
0198
0199         //
0200         // This should not happen. In this case the pertinent children are
0201         // BLOCKED and thus this method would�t be called.
0202         //
0203         // 17.3. Now this can happen.
0204         //
0205
0206         // pert_cons = false;
0207
0208         // assert (false);
0209         }
0210     }
0211
0212     } else {
0213
0214     //
0215     // In case that there are more than one block of pertinent children although
0216     // bubble up didn�t fail (e.g. pp...pe...ep...pp or ee...ep...pe...ep...pp)
0217     // we need some element of the second block in order to find K5 or K33. So we
0218     // leave pert_begin as it is, but assign pert_end to something in the second
0219     // block
0220     //
0221
0222     tmp = pert_begin;
0223     --tmp;
0224
0225     while (tmp != sons.end()) {
0226         if ((*tmp)->mark == UNBLOCKED && (*tmp)->kind () != DIR) {
0227         break;
0228         }
0229
0230         --tmp;
0231     }
0232
0233
0234     //
0235     // We need an empty child. So we always keep the invariant that --pert_end
0236     // leads to an empty child. Please note that --pert_end might be a DI.
0237     //
0238
0239     tmp.reverse();
0240
0241     if (tmp == sons.end()) {
0242         tmp = pert_end;
0243         ++tmp;
0244
0245         while (tmp != sons.end()) {
0246         if ((*tmp)->mark == UNBLOCKED && (*tmp)->kind () != DIR) {
0247             break;
0248         }
0249
0250         ++tmp;
0251         }
0252
0253         assert (tmp != sons.end());
0254     }
0255
0256     pert_end = tmp;
0257     }
0258
0259     //
0260     // In the case that there is in fact only one pertinent child we so far
0261     // only assured that it is the last child, but it is still possible
0262     // that pert_begin (and pert_end, too) is headed the wrong way.
0263     //
0264
0265     if (pert_begin == pert_end && pert_cons && pert_end == --(sons.end())) {
0266     pert_begin = pert_end = --(sons.end());
0267     }
0268 }
0269
0270 inline void q_node::clear ()
0271 {
0272     pq_node::clear();
0273     partial_count = full_count = 0;
0274     pert_begin = symlist<pq_node*>::iterator();
0275     pert_end = symlist<pq_node*>::iterator();
0276 }
0277
0278 inline void q_node::write (ostream& os, int _id)
0279 {
0280     os << "node [\n" << "id " << _id << endl;
0281     os << "label \"" << id << "\n" << "Q" << "\"\n";
0282     os << "graphics [\n" << "x 100\n" << "y 100 \n";
0283     if (mark == UNBLOCKED) {
0284     os << "outline \"#0000ff\"\n";
0285     } else if (mark == BLOCKED) {
0286     os << "outline \"#ff0000\"\n";
0287     }
0288     os << "]\n";
0289     os << "LabelGraphics [\n";
0290     os << "type \"text\"\n]\n]" << endl;
0291 }
0292
0293 q_node* q_node::merge (iterator it)
0294 {
0295     assert ((*it)->kind() == pq_node::Q_NODE);
0296     q_node* part = (q_node*) *it;
0297
0298     if (part == sons.front()) {
0299     part->sons.front()->father = this;
0300     part->sons.back()->is_endmost = false;
0301     } else if (part == sons.back()){
0302     part->sons.back()->father = this;
0303     part->sons.front()->is_endmost = false;
0304     } else {
0305     part->sons.front()->is_endmost = false;
0306     part->sons.back()->is_endmost = false;
0307     }
0308
0309     sons.splice (it, part->sons.begin(), part->sons.end());
0310     sons.erase (it);
0311
0312     return part;
0313 }
0314
0315
0316 void q_node::turn ()
0317 {
0318     sons.reverse();
0319 }
0320
0321
0322 //--------------------------------------------------------------------------
0323 //   LEAF
0324 //--------------------------------------------------------------------------
0325
0326
0327 pq_leaf::pq_leaf (int id_, int other_, edge e_, node n_) : pq_node (n_, id_)
0328 {
0329     up_id = other_;
0330     up = n_.opposite (e_);
0331     other_id = other_;
0332     e = e_;
0333 }
0334
0335 inline void pq_leaf::write (ostream& os, int _id)
0336 {
0337     os << "node [\n" << "id " << _id << endl;
0338     os << "label \"" << other_id << "\n" << id << "\"\n";
0339     os << "graphics [\n" << "x 100\n" << "y 100 \n";
0340     if (mark == UNBLOCKED) {
0341     os << "outline \"#0000ff\"\n";
0342     } else if (mark == BLOCKED) {
0343     os << "outline \"#ff0000\"\n";
0344     }
0345     os << "]\n";
0346     os << "LabelGraphics [\n";
0347     os << "type \"text\"\n]\n]" << endl;
0348 }
0349
0350
0351 void direction_indicator::write (ostream& os, int _id)
0352 {
0353     os << "node [\n" << "id " << _id << endl;
0354     os << "label \"DIR\n" << id << "\"\n";
0355     os << "graphics [\n" << "x 100\n" << "y 100 \n";
0356     if (mark == UNBLOCKED) {
0357     os << "outline \"#0000ff\"\n";
0358     } else if (mark == BLOCKED) {
0359     os << "outline \"#ff0000\"\n";
0360     }
0361     os << "]\n";
0362     os << "LabelGraphics [\n";
0363     os << "type \"text\"\n]\n]" << endl;
0364 }
0365
0366 __GTL_END_NAMESPACE
0367
0368 //--------------------------------------------------------------------------
0369 //   end of file
0370 //--------------------------------------------------------------------------