? ? ? ? ? ?

---

tree_node.cxx

Go to the documentation of this file.

#include "Package.h"
#include "tree_node.h"

static bool debug ()
{
  static bool state = ::getenv ("CMTGRAPHERDEBUG");

  return (state);
}

tree_node& tree_node::null ()
{
  static tree_node null_node;

  return (null_node);
}

tree_node::tree_node ()
{
  discarded = false;
  parent = 0;
  package = 0;
  cyclic = false;
}

tree_node::tree_node (tree_node* node, Package* p)
{
  discarded = false;
  parent = node;
  package = p;
  cyclic = false;
}
  
void tree_node::set (tree_node* node, Package* p)
{
  discarded = false;
  parent = node;
  package = p;
}
  
Package* tree_node::get_package () const
{
  return (package);
}
  
const cmt_string& tree_node::get_name () const
{
  static const cmt_string null = "";
  if (package == 0) return (null);
  return (package->get_name ());
}
  
const cmt_string& tree_node::get_dot_name () const
{
  static const cmt_string null = "";
  if (package == 0) return (null);
  return (package->get_dot_name ());
}
  
const cmt_string& tree_node::get_cluster_name () const
{
  static const cmt_string null = "";
  if (package == 0) return (null);
  return (package->get_cluster_name ());
}
  
const cmt_string& tree_node::get_dot_label () const
{
  static const cmt_string null = "";
  if (package == 0) return (null);
  return (package->get_dot_label ());
}
  
int tree_node::operator == (const Package& p) const
{
  if ((*package) == p) return (1);
  return (0);
}
  
int tree_node::operator == (const tree_node& other) const
{
  if (package == other.package) return (1);
  return (0);
}
  
int tree_node::operator != (const tree_node& other) const
{
  const tree_node& me = *this;
  return (!(me == other));
}

tree_node* tree_node::get_last_sub_node () const
{
  if (sub_nodes.size () == 0) return (0);
  return (sub_nodes.back ());
}

void tree_node::install_as_reference_node ()
{
  package->set_node (this);
}

void tree_node::set_cyclic ()
{
  cyclic = true;
}

bool tree_node::is_cyclic () const
{
  return (cyclic);
}

tree_node& tree_node::append (Package& p)
{
  bool has_cycle = false;

  tree_node* node = parent;
  while (node != 0)
    {
      if ((*node) == p) 
        {
          tree_node* sub_node = new tree_node (this, &p);
          cyclic_nodes.push_back (sub_node);
          return (*sub_node);
            //has_cycle = true;
            //break;
        }

      node = node->parent;
    }

  tree_node* sub_node = new tree_node (this, &p);
    //sub_node->set_cyclic ();

  sub_nodes.push_back (sub_node);
  return (*sub_node);
}

bool tree_node::check_cycle (const Package& p) const
{
  static int level = 0;

  if (debug ())
    {
      for (int i = 0; i < level; i++) cout << "  ";
 
      cout << "tree_node::check_cycle>";
      if (package == 0) cout << "[null]";
      else cout << "[" << package->get_name () << "]";

      cout << " (" << p.get_name () << ")";

      if (parent == 0) cout << " no parent";
      else cout << " parent=" << parent->package->get_name ();

      cout << endl;
    }

  bool result = false;

  if ((package != 0) && ((*package) == p)) 
    {
      result = true;
    }
  else if (parent == 0) 
    {
      result = false;
    }
  else
    {
      level++;
      result = parent->check_cycle (p);
      level--;
    }

  if (debug ())
    {
      for (int i = 0; i < level; i++) cout << "  ";
 
      cout << "tree_node::check_cycle>";
      if (package == 0) cout << "[null]";
      else cout << "[" << package->get_name () << "]";

      cout << " (" << p.get_name () << ")";

      if (parent == 0) cout << " no parent";
      else cout << " parent=" << parent->package->get_name ();

      cout << " -> " << result;
      cout << endl;
    }

  return (result);
}

tree_node* tree_node::references (const tree_node& other) const
{
  static int level = 0;
  static cmt_vector stack;

  {
      //
      // Protection against cycles in the recursivity
      //

    if (level == 0)
      {
        stack.clear ();
      }
    
    for (int k = 0; k < stack.size (); k++)
      {
        const tree_node* t = stack[k];
        if (t == this) return (0);
      }
    
    if (stack.size () <= level)
      {
        stack.push_back (this);
      }
    else
      {
        stack[level] = this;
      }
  }

  int i;

  if (sub_nodes.size () > 0)
    {
      for (i = 0; i < sub_nodes.size (); i++)
        {
          tree_node& n = *(sub_nodes[i]);
          if (n == other) return (&n);
          level++;
          tree_node* p = n.references (other);
          level--;
          if (p != 0) return (p);
        }
    }
  else
    {
      tree_node* ref_node = package->get_node ();
      if ((ref_node != 0) && (ref_node != this))
        {
          level++;
          tree_node* p = ref_node->references (other);
          level--;
          return (p);
        }
    }

  return (0);
}

void tree_node::reduce ()
{
  int i;

  //
  // First discard all redundent client relationships at this level
  //
  for (i = 0; i < sub_nodes.size (); i++)
    {
      tree_node& n = *(sub_nodes[i]);
      
      if (n.discarded) continue;
      
      // Check all *other* use specs at the same level
      for (int j = 0; j < sub_nodes.size (); j++)
        {
          if (j == i) continue;
          tree_node& m = *(sub_nodes[j]);
          if (m.discarded) continue;
          
          if (n == m)
            {
              m.discarded = true;
              if ((m.sub_nodes.size () != 0) &&
                  (n.sub_nodes.size () == 0))
                {
                  n.sub_nodes = m.sub_nodes;
                }
            }
          else
            {
              tree_node* p = m.references (n);

              // for show uses 
              // to be checked for show clients???
              //tree_node* p = n.references (m);

              if (p != 0)
                {
                  n.discarded = true;
                  
                  if ((n.sub_nodes.size () != 0) &&
                      (p->sub_nodes.size () == 0))
                    {
                      p->sub_nodes = n.sub_nodes;
                    }
                  
                  break;
                }
              else
                {
                }
            }
        }
    }
    
  // Now apply the reduction recursively to all sub-trees
  for (i = 0; i < sub_nodes.size (); i++)
    {
      tree_node& n = *(sub_nodes[i]);
      if (n.discarded) continue;
      n.reduce ();
    }
}

int tree_node::show_node (cmt_string& output, 
                          const cmt_string& direction,
                          bool collapsed) const
{
  static int level = 0;
  static const char* colors[] = {
    "black",
    "red1",
    "red2",
    "red3",
    "red4",
    "brown1",
    "brown2",
    "brown3",
    "brown4",
    "orange1",
    "orange2",
    "orange3",
    "orange4",
    "yellow1",
    "yellow2",
    "yellow3",
    "yellow4",
    "green1",
    "green2",
    "green3",
    "green4",
    "cyan1",
    "cyan2",
    "cyan3",
    "cyan4",
    "blue1",
    "blue2",
    "blue3",
    "blue4",
    "magenta1",
    "magenta2",
    "magenta3",
    "magenta4"
  };

  static int max_color = sizeof (colors) / sizeof (char*);
  static int color = 0;

  if (package->is_unreachable ())
    {
      output += "  ";
      output += package->get_dot_name ();
      output += " [label = \"";
      output += package->get_dot_label ();
      output += "\" color=red ];\n";
      return (0);
    }

  int result = 0;

  if (parent != 0)
    {
      int j;

      for (j = 0; j < level; j++) output += "  ";

      if (collapsed)
        {
          cmt_string my_cluster = get_cluster_name ();
          cmt_string parent_cluster = parent->get_cluster_name ();

          output += "  ";
          if (parent_cluster == "")
            {
              output += parent->get_dot_name ();
            }
          else
            {
              output += parent_cluster;
            }

          output += " -> ";

          if (my_cluster == "")
            {
              output += get_dot_name ();
            }
          else
            {
              output += my_cluster;
            }

          output += " [dir=";
          output += direction;
            /*
              output += ", weight=";
              char temp[20];
              sprintf (temp, "%d", level);
              output += temp;
            */
          output += ", color=";
          if (discarded) 
            {
              output += "gray20";
            }
          else
            {
              output += colors[color];
            }
          color++;
          if (color >= max_color) color = 0;
          output += "]";
          output += ";\n";

        }
      else
        {
          output += "  ";
          output += parent->get_dot_name ();
          output += " -> ";
          output += get_dot_name ();
          output += " [dir=";
          output += direction;
            /*
          output += ", weight=";
          char temp[20];
          sprintf (temp, "%d", level);
          output += temp;
            */
          output += ", color=";
          output += colors[color];
          color++;
          if (color >= max_color) color = 0;
          output += "]";
          output += ";\n";
        }

      result++;
    }
  
  return (result);
}

int tree_node::show_tree (cmt_string& output, 
                          const cmt_string& direction,
                          bool collapsed) const
{
  static int level = 0;

  int result = show_node (output, direction, collapsed);

  if (package->is_unreachable ()) return (0);

  int i;

  for (i = 0; i < sub_nodes.size (); i++)
    {
      const tree_node& n = *(sub_nodes[i]);
      if (n.discarded) continue;
      level++;
      result += n.show_tree (output, direction, collapsed);
      level--;
    }

  for (i = 0; i < cyclic_nodes.size (); i++)
    {
      const tree_node& n = *(cyclic_nodes[i]);
      if (n.discarded) continue;
      level++;
      result += n.show_node (output, direction, collapsed);
      level--;
    }
  
  return (result);
}

---