flower/directed-graph.cc

   1 /*
   2   edge_out.cc -- implement Directed_graph_node
   3
   4   source file FlowerLib
   5
   6   (c) 1997 Han-Wen Nienhuys <hanwen@stack.nl>
   7 */
   8
   9 #include "directed-graph.hh"
  10
  11 #ifdef PARANOID                 // these checks eat huge amounts of time.
  12 #define PARANOID_OK() OK()
  13 #else
  14 #define PARANOID_OK()
  15 #endif
  16
  17
  18 Link_array<Directed_graph_node> const &
  19 Directed_graph_node::get_in_edge_arr() const
  20 {
  21   return edge_in_l_arr_;
  22 }
  23
  24 Link_array<Directed_graph_node> const &
  25 Directed_graph_node::get_out_edge_arr() const
  26 {
  27   return edge_out_l_arr_;
  28 }
  29
  30 /**
  31   Should not copy deps automatically
  32  */
  33 Directed_graph_node::Directed_graph_node (Directed_graph_node const&)
  34 {
  35 }
  36
  37 void
  38 Directed_graph_node::copy_edges_out (Directed_graph_node const &s)
  39 {
  40   for (int i=0; i < s.edge_out_l_arr_.size(); i++)
  41         add (s.edge_out_l_arr_[i]);
  42 }
  43
  44 void
  45 Directed_graph_node::OK() const
  46 {
  47 #ifndef NDEBUG
  48   for (int i=0; i < edge_out_l_arr_.size(); i++)
  49     {
  50         assert (edge_out_l_arr_[i]->
  51                edge_in_l_arr_.find_l (this));
  52     }
  53   for (int i=0; i < edge_in_l_arr_.size(); i++)
  54         assert (edge_in_l_arr_[i]->contains_b (this));
  55 #endif
  56 }
  57
  58 bool
  59 Directed_graph_node::contains_b (const Directed_graph_node *d) const
  60 {
  61   return edge_out_l_arr_.find_l ((Directed_graph_node*)d);
  62 }
  63
  64 void
  65 Directed_graph_node::remove_edge_out_idx (int i)
  66 {
  67   PARANOID_OK();
  68   Directed_graph_node * d_l = edge_out_l_arr_.get (i);
  69
  70   int j = d_l->edge_in_l_arr_.find_i (this);
  71   assert (j>=0);
  72   d_l->edge_in_l_arr_.unordered_del (j);
  73   PARANOID_OK();
  74 }
  75
  76 void
  77 Directed_graph_node::remove_edge_in (Directed_graph_node *d_l)
  78 {
  79   PARANOID_OK();
  80   d_l->remove_edge_out (this);
  81   PARANOID_OK();
  82 }
  83
  84 void
  85 Directed_graph_node::remove_edge_out (Directed_graph_node *d_l)
  86 {
  87   PARANOID_OK();
  88   for (int i=0; i < edge_out_l_arr_.size();)
  89     {
  90         if (edge_out_l_arr_[i]== d_l)
  91             remove_edge_out_idx (i);
  92         else
  93             i++;
  94     }
  95   PARANOID_OK();
  96 }
  97 bool
  98 Directed_graph_node::linked_b() const
  99 {
 100   return edge_out_l_arr_.size() || edge_in_l_arr_.size ();
 101 }
 102
 103 void
 104 Directed_graph_node::junk_links()
 105 {
 106   edge_in_l_arr_.set_size (0);
 107   edge_out_l_arr_.set_size (0);
 108 }
 109
 110
 111 void
 112 Directed_graph_node::unlink()
 113 {
 114 #ifdef PARANOID
 115         PARANOID_OK();
 116
 117         Link_array<Directed_graph_node> t = edge_out_l_arr_;
 118         t.concat (edge_in_l_arr_);
 119 #endif
 120
 121         while (edge_out_l_arr_.size())
 122             remove_edge_out_idx (0);
 123
 124         while (edge_in_l_arr_.size())
 125             remove_edge_in (edge_in_l_arr_[0]);
 126
 127 #ifdef PARANOID
 128         for (int i =0; i < t.size(); i++)
 129             t[i]->OK();
 130 #endif
 131 }
 132
 133 Directed_graph_node::~Directed_graph_node()
 134 {
 135   assert (!linked_b());
 136 }
 137
 138
 139 void
 140 Directed_graph_node::add (Directed_graph_node* dep_l)
 141 {
 142   PARANOID_OK();
 143   if (!dep_l)
 144         return ;
 145   dep_l->edge_in_l_arr_.push (this);
 146   edge_out_l_arr_.push (dep_l);
 147   PARANOID_OK();
 148 }
 149
 150
 151 Directed_graph_node::Directed_graph_node()
 152 {
 153 }
 154