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

tree_node Class Reference

This represents the client tree. More...

#include <tree_node.h>

Collaboration diagram for tree_node:

[legend]
List of all members.

Public Methods

? tree_node ()
? Default constructor. More...

? tree_node (tree_node* node, Package* p)
? A complete constructor. More...

void? set (tree_node* node, Package* p)
Package*? get_package () const
const cmt_string&? get_name () const
const cmt_string&? get_dot_name () const
const cmt_string&? get_cluster_name () const
const cmt_string&? get_dot_label () const
int? operator== (const tree_node& other) const
int? operator== (const Package& p) const
int? operator!= (const tree_node& other) const
tree_node*? get_last_sub_node () const
void? install_as_reference_node ()
void? set_cyclic ()
bool? is_cyclic () const
tree_node&? append (Package& p)
? Create a sub-node entry for this client package. More...

bool? hold_package (const Package& p) const
? Check whether the specified tree_node holds the specified package. More...

bool? check_cycle (const Package& p) const
? First look backward in this tree whether the package we are adding is already there, which would sign a cyclic dependency. More...

tree_node*? references (const tree_node& other) const
? Check whether the specified tree_node is recursively refered to in the local sub-tree. More...

void? reduce ()
? A use tree may contain redundent use specifications (ie. More...

int? show_node (cmt_string& output, const cmt_string& direction, bool collapsed = false) const
? Produce the dot format for this node only. More...

int? show_tree (cmt_string& output, const cmt_string& direction, bool collapsed = false) const
? Produce the dot format for the reduced tree. More...


Static Public Methods

tree_node&? null ()

Private Attributes

cmt_vector? sub_nodes
cmt_vector? cyclic_nodes
tree_node*? parent
Package*? package
bool? cyclic
bool? discarded

Detailed Description

This represents the client tree.

Each node refers to one Package entry. The complete tree represents the redundent client tree (with duplicated client relationships)

Definition at line 17 of file tree_node.h.


Constructor & Destructor Documentation

tree_node::tree_node ( )
?

Default constructor.

Definition at line 19 of file tree_node.cxx.

Referenced by append().

00020 {
00021   discarded = false;
00022   parent = 0;
00023   package = 0;
00024   cyclic = false;
00025 }

tree_node::tree_node ( tree_node * node,
Package * p?)
?

A complete constructor.

Definition at line 28 of file tree_node.cxx.

00029 {
00030   discarded = false;
00031   parent = node;
00032   package = p;
00033   cyclic = false;
00034 }

Member Function Documentation

tree_node & tree_node::append ( Package & p?)
?

Create a sub-node entry for this client package.

Definition at line 115 of file tree_node.cxx.

Referenced by UseScanner::filter(), and UsesGraphBuilder::filter().

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 }

bool tree_node::check_cycle ( const Package & p?) const
?

First look backward in this tree whether the package we are adding is already there, which would sign a cyclic dependency.

Definition at line 146 of file tree_node.cxx.

Referenced by UsesGraphBuilder::filter().

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 }

const cmt_string & tree_node::get_cluster_name ( ) const
?

Definition at line 62 of file tree_node.cxx.

Referenced by show_node().

00063 {
00064   static const cmt_string null = "";
00065   if (package == 0) return (null);
00066   return (package->get_cluster_name ());
00067 }

const cmt_string & tree_node::get_dot_label ( ) const
?

Definition at line 69 of file tree_node.cxx.

00070 {
00071   static const cmt_string null = "";
00072   if (package == 0) return (null);
00073   return (package->get_dot_label ());
00074 }

const cmt_string & tree_node::get_dot_name ( ) const
?

Definition at line 55 of file tree_node.cxx.

Referenced by show_node().

00056 {
00057   static const cmt_string null = "";
00058   if (package == 0) return (null);
00059   return (package->get_dot_name ());
00060 }

tree_node * tree_node::get_last_sub_node ( ) const
?

Definition at line 94 of file tree_node.cxx.

Referenced by UsesGraphBuilder::filter().

00095 {
00096   if (sub_nodes.size () == 0) return (0);
00097   return (sub_nodes.back ());
00098 }

const cmt_string & tree_node::get_name ( ) const
?

Definition at line 48 of file tree_node.cxx.

Referenced by check_cycle(), UsesGraphBuilder::filter(), and DotGenerator::run().

00049 {
00050   static const cmt_string null = "";
00051   if (package == 0) return (null);
00052   return (package->get_name ());
00053 }

Package * tree_node::get_package ( ) const
?

Definition at line 43 of file tree_node.cxx.

Referenced by UsesGraphBuilder::start().

00044 {
00045   return (package);
00046 }

bool tree_node::hold_package ( const Package & p?) const
?

Check whether the specified tree_node holds the specified package.

void tree_node::install_as_reference_node ( )
?

Definition at line 100 of file tree_node.cxx.

Referenced by UsesGraphBuilder::filter().

00101 {
00102   package->set_node (this);
00103 }

bool tree_node::is_cyclic ( ) const
?

Definition at line 110 of file tree_node.cxx.

00111 {
00112   return (cyclic);
00113 }

tree_node & tree_node::null ( ) [static]
?

Definition at line 12 of file tree_node.cxx.

00013 {
00014   static tree_node null_node;
00015 
00016   return (null_node);
00017 }

int tree_node::operator!= ( const tree_node & other?) const
?

Definition at line 88 of file tree_node.cxx.

00089 {
00090   const tree_node& me = *this;
00091   return (!(me == other));
00092 }

int tree_node::operator== ( const Package & p?) const
?

Definition at line 76 of file tree_node.cxx.

00077 {
00078   if ((*package) == p) return (1);
00079   return (0);
00080 }

int tree_node::operator== ( const tree_node & other?) const
?

Definition at line 82 of file tree_node.cxx.

00083 {
00084   if (package == other.package) return (1);
00085   return (0);
00086 }

void tree_node::reduce ( )
?

A use tree may contain redundent use specifications (ie.

when there is a direct reference to a package at a given tree_node, while this package is also referenced in the local sub-tree, or when two identical refs are specified)

Definition at line 273 of file tree_node.cxx.

Referenced by DotGenerator::run().

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 }

tree_node * tree_node::references ( const tree_node & other?) const
?

Check whether the specified tree_node is recursively refered to in the local sub-tree.

Definition at line 203 of file tree_node.cxx.

Referenced by reduce().

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 }

void tree_node::set ( tree_node * node,
Package * p?)
?

Definition at line 36 of file tree_node.cxx.

Referenced by UsesGraphBuilder::UsesGraphBuilder().

00037 {
00038   discarded = false;
00039   parent = node;
00040   package = p;
00041 }

void tree_node::set_cyclic ( )
?

Definition at line 105 of file tree_node.cxx.

00106 {
00107   cyclic = true;
00108 }

int tree_node::show_node ( cmt_string & output,
const cmt_string & direction,
bool collapsed = false?) const
?

Produce the dot format for this node only.

We have to transfer the sub-nodes from the discarded one to the reference one

Definition at line 351 of file tree_node.cxx.

Referenced by show_tree().

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 }

int tree_node::show_tree ( cmt_string & output,
const cmt_string & direction,
bool collapsed = false?) const
?

Produce the dot format for the reduced tree.

Definition at line 490 of file tree_node.cxx.

Referenced by DotGenerator::run().

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 }

Member Data Documentation

bool tree_node::cyclic [private]
?

Definition at line 83 of file tree_node.h.

cmt_vector< tree_node *> tree_node::cyclic_nodes [private]
?

Definition at line 80 of file tree_node.h.

bool tree_node::discarded [private]
?

Definition at line 84 of file tree_node.h.

Package * tree_node::package [private]
?

Definition at line 82 of file tree_node.h.

tree_node * tree_node::parent [private]
?

Definition at line 81 of file tree_node.h.

cmt_vector< tree_node *> tree_node::sub_nodes [private]
?

Definition at line 79 of file tree_node.h.


The documentation for this class was generated from the following files:
Generated at Fri Apr 12 16:18:17 2002 for cmtgrapher by 1.2.3 written by , ??1997-2000