Main Page ? Class Hierarchy ? Compound List ? File List ? Compound Members ? File Members ?

tree_node.cxx

Go to the documentation of this file.
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             //has_cycle = true;
00133             //break;
00134         }
00135 
00136       node = node->parent;
00137     }
00138 
00139   tree_node* sub_node = new tree_node (this, &p);
00140     //sub_node->set_cyclic ();
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       // Protection against cycles in the recursivity
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   // First discard all redundent client relationships at this level
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       // Check all *other* use specs at the same level
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               // for show uses 
00313               // to be checked for show clients???
00314               //tree_node* p = n.references (m);
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   // Now apply the reduction recursively to all sub-trees
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               output += ", weight=";
00443               char temp[20];
00444               sprintf (temp, "%d", level);
00445               output += temp;
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           output += ", weight=";
00472           char temp[20];
00473           sprintf (temp, "%d", level);
00474           output += temp;
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 

Generated at Fri Apr 12 16:18:12 2002 for cmtgrapher by 1.2.3 written by , ??1997-2000