00001
00002 #include "Package.h"
00003 #include "tree_node.h"
00004
00005 static bool debug ()
00006 {
00007 static bool state = ::getenv ("CMTGRAPHERDEBUG");
00008
00009 return (state);
00010 }
00011
00012 tree_node& tree_node::null ()
00013 {
00014 static tree_node null_node;
00015
00016 return (null_node);
00017 }
00018
00019 tree_node::tree_node ()
00020 {
00021 discarded = false;
00022 parent = 0;
00023 package = 0;
00024 cyclic = false;
00025 }
00026
00028 tree_node::tree_node (tree_node* node, Package* p)
00029 {
00030 discarded = false;
00031 parent = node;
00032 package = p;
00033 cyclic = false;
00034 }
00035
00036 void tree_node::set (tree_node* node, Package* p)
00037 {
00038 discarded = false;
00039 parent = node;
00040 package = p;
00041 }
00042
00043 Package* tree_node::get_package () const
00044 {
00045 return (package);
00046 }
00047
00048 const cmt_string& tree_node::get_name () const
00049 {
00050 static const cmt_string null = "";
00051 if (package == 0) return (null);
00052 return (package->get_name ());
00053 }
00054
00055 const cmt_string& tree_node::get_dot_name () const
00056 {
00057 static const cmt_string null = "";
00058 if (package == 0) return (null);
00059 return (package->get_dot_name ());
00060 }
00061
00062 const cmt_string& tree_node::get_cluster_name () const
00063 {
00064 static const cmt_string null = "";
00065 if (package == 0) return (null);
00066 return (package->get_cluster_name ());
00067 }
00068
00069 const cmt_string& tree_node::get_dot_label () const
00070 {
00071 static const cmt_string null = "";
00072 if (package == 0) return (null);
00073 return (package->get_dot_label ());
00074 }
00075
00076 int tree_node::operator == (const Package& p) const
00077 {
00078 if ((*package) == p) return (1);
00079 return (0);
00080 }
00081
00082 int tree_node::operator == (const tree_node& other) const
00083 {
00084 if (package == other.package) return (1);
00085 return (0);
00086 }
00087
00088 int tree_node::operator != (const tree_node& other) const
00089 {
00090 const tree_node& me = *this;
00091 return (!(me == other));
00092 }
00093
00094 tree_node* tree_node::get_last_sub_node () const
00095 {
00096 if (sub_nodes.size () == 0) return (0);
00097 return (sub_nodes.back ());
00098 }
00099
00100 void tree_node::install_as_reference_node ()
00101 {
00102 package->set_node (this);
00103 }
00104
00105 void tree_node::set_cyclic ()
00106 {
00107 cyclic = true;
00108 }
00109
00110 bool tree_node::is_cyclic () const
00111 {
00112 return (cyclic);
00113 }
00114
00115 tree_node& tree_node::append (Package& p)
00116 {
00122 bool has_cycle = false;
00123
00124 tree_node* node = parent;
00125 while (node != 0)
00126 {
00127 if ((*node) == p)
00128 {
00129 tree_node* sub_node = new tree_node (this, &p);
00130 cyclic_nodes.push_back (sub_node);
00131 return (*sub_node);
00132
00133
00134 }
00135
00136 node = node->parent;
00137 }
00138
00139 tree_node* sub_node = new tree_node (this, &p);
00140
00141
00142 sub_nodes.push_back (sub_node);
00143 return (*sub_node);
00144 }
00145
00146 bool tree_node::check_cycle (const Package& p) const
00147 {
00148 static int level = 0;
00149
00150 if (debug ())
00151 {
00152 for (int i = 0; i < level; i++) cout << " ";
00153
00154 cout << "tree_node::check_cycle>";
00155 if (package == 0) cout << "[null]";
00156 else cout << "[" << package->get_name () << "]";
00157
00158 cout << " (" << p.get_name () << ")";
00159
00160 if (parent == 0) cout << " no parent";
00161 else cout << " parent=" << parent->package->get_name ();
00162
00163 cout << endl;
00164 }
00165
00166 bool result = false;
00167
00168 if ((package != 0) && ((*package) == p))
00169 {
00170 result = true;
00171 }
00172 else if (parent == 0)
00173 {
00174 result = false;
00175 }
00176 else
00177 {
00178 level++;
00179 result = parent->check_cycle (p);
00180 level--;
00181 }
00182
00183 if (debug ())
00184 {
00185 for (int i = 0; i < level; i++) cout << " ";
00186
00187 cout << "tree_node::check_cycle>";
00188 if (package == 0) cout << "[null]";
00189 else cout << "[" << package->get_name () << "]";
00190
00191 cout << " (" << p.get_name () << ")";
00192
00193 if (parent == 0) cout << " no parent";
00194 else cout << " parent=" << parent->package->get_name ();
00195
00196 cout << " -> " << result;
00197 cout << endl;
00198 }
00199
00200 return (result);
00201 }
00202
00203 tree_node* tree_node::references (const tree_node& other) const
00204 {
00205 static int level = 0;
00206 static cmt_vector stack;
00207
00208 {
00209
00210
00211
00212
00213 if (level == 0)
00214 {
00215 stack.clear ();
00216 }
00217
00218 for (int k = 0; k < stack.size (); k++)
00219 {
00220 const tree_node* t = stack[k];
00221 if (t == this) return (0);
00222 }
00223
00224 if (stack.size () <= level)
00225 {
00226 stack.push_back (this);
00227 }
00228 else
00229 {
00230 stack[level] = this;
00231 }
00232 }
00233
00234 int i;
00235
00236 if (sub_nodes.size () > 0)
00237 {
00241 for (i = 0; i < sub_nodes.size (); i++)
00242 {
00243 tree_node& n = *(sub_nodes[i]);
00244 if (n == other) return (&n);
00245 level++;
00246 tree_node* p = n.references (other);
00247 level--;
00248 if (p != 0) return (p);
00249 }
00250 }
00251 else
00252 {
00260 tree_node* ref_node = package->get_node ();
00261 if ((ref_node != 0) && (ref_node != this))
00262 {
00263 level++;
00264 tree_node* p = ref_node->references (other);
00265 level--;
00266 return (p);
00267 }
00268 }
00269
00270 return (0);
00271 }
00272
00273 void tree_node::reduce ()
00274 {
00275 int i;
00276
00277
00278
00279
00280 for (i = 0; i < sub_nodes.size (); i++)
00281 {
00282 tree_node& n = *(sub_nodes[i]);
00283
00284 if (n.discarded) continue;
00285
00286
00287 for (int j = 0; j < sub_nodes.size (); j++)
00288 {
00289 if (j == i) continue;
00290 tree_node& m = *(sub_nodes[j]);
00291 if (m.discarded) continue;
00292
00293 if (n == m)
00294 {
00296 m.discarded = true;
00297 if ((m.sub_nodes.size () != 0) &&
00298 (n.sub_nodes.size () == 0))
00299 {
00305 n.sub_nodes = m.sub_nodes;
00306 }
00307 }
00308 else
00309 {
00310 tree_node* p = m.references (n);
00311
00312
00313
00314
00315
00316 if (p != 0)
00317 {
00319 n.discarded = true;
00320
00321 if ((n.sub_nodes.size () != 0) &&
00322 (p->sub_nodes.size () == 0))
00323 {
00329 p->sub_nodes = n.sub_nodes;
00330 }
00331
00332 break;
00333 }
00334 else
00335 {
00337 }
00338 }
00339 }
00340 }
00341
00342
00343 for (i = 0; i < sub_nodes.size (); i++)
00344 {
00345 tree_node& n = *(sub_nodes[i]);
00346 if (n.discarded) continue;
00347 n.reduce ();
00348 }
00349 }
00350
00351 int tree_node::show_node (cmt_string& output,
00352 const cmt_string& direction,
00353 bool collapsed) const
00354 {
00355 static int level = 0;
00356 static const char* colors[] = {
00357 "black",
00358 "red1",
00359 "red2",
00360 "red3",
00361 "red4",
00362 "brown1",
00363 "brown2",
00364 "brown3",
00365 "brown4",
00366 "orange1",
00367 "orange2",
00368 "orange3",
00369 "orange4",
00370 "yellow1",
00371 "yellow2",
00372 "yellow3",
00373 "yellow4",
00374 "green1",
00375 "green2",
00376 "green3",
00377 "green4",
00378 "cyan1",
00379 "cyan2",
00380 "cyan3",
00381 "cyan4",
00382 "blue1",
00383 "blue2",
00384 "blue3",
00385 "blue4",
00386 "magenta1",
00387 "magenta2",
00388 "magenta3",
00389 "magenta4"
00390 };
00391
00392 static int max_color = sizeof (colors) / sizeof (char*);
00393 static int color = 0;
00394
00395 if (package->is_unreachable ())
00396 {
00397 output += " ";
00398 output += package->get_dot_name ();
00399 output += " [label = \"";
00400 output += package->get_dot_label ();
00401 output += "\" color=red ];\n";
00402 return (0);
00403 }
00404
00405 int result = 0;
00406
00407 if (parent != 0)
00408 {
00409 int j;
00410
00411 for (j = 0; j < level; j++) output += " ";
00412
00413 if (collapsed)
00414 {
00415 cmt_string my_cluster = get_cluster_name ();
00416 cmt_string parent_cluster = parent->get_cluster_name ();
00417
00418 output += " ";
00419 if (parent_cluster == "")
00420 {
00421 output += parent->get_dot_name ();
00422 }
00423 else
00424 {
00425 output += parent_cluster;
00426 }
00427
00428 output += " -> ";
00429
00430 if (my_cluster == "")
00431 {
00432 output += get_dot_name ();
00433 }
00434 else
00435 {
00436 output += my_cluster;
00437 }
00438
00439 output += " [dir=";
00440 output += direction;
00441
00442
00443
00444
00445
00446
00447 output += ", color=";
00448 if (discarded)
00449 {
00450 output += "gray20";
00451 }
00452 else
00453 {
00454 output += colors[color];
00455 }
00456 color++;
00457 if (color >= max_color) color = 0;
00458 output += "]";
00459 output += ";\n";
00460
00461 }
00462 else
00463 {
00464 output += " ";
00465 output += parent->get_dot_name ();
00466 output += " -> ";
00467 output += get_dot_name ();
00468 output += " [dir=";
00469 output += direction;
00470
00471
00472
00473
00474
00475
00476 output += ", color=";
00477 output += colors[color];
00478 color++;
00479 if (color >= max_color) color = 0;
00480 output += "]";
00481 output += ";\n";
00482 }
00483
00484 result++;
00485 }
00486
00487 return (result);
00488 }
00489
00490 int tree_node::show_tree (cmt_string& output,
00491 const cmt_string& direction,
00492 bool collapsed) const
00493 {
00494 static int level = 0;
00495
00496 int result = show_node (output, direction, collapsed);
00497
00498 if (package->is_unreachable ()) return (0);
00499
00500 int i;
00501
00503 for (i = 0; i < sub_nodes.size (); i++)
00504 {
00505 const tree_node& n = *(sub_nodes[i]);
00506 if (n.discarded) continue;
00507 level++;
00508 result += n.show_tree (output, direction, collapsed);
00509 level--;
00510 }
00511
00513 for (i = 0; i < cyclic_nodes.size (); i++)
00514 {
00515 const tree_node& n = *(cyclic_nodes[i]);
00516 if (n.discarded) continue;
00517 level++;
00518 result += n.show_node (output, direction, collapsed);
00519 level--;
00520 }
00521
00522 return (result);
00523 }
00524