tpl_sgraph.H

# ifndef TPL_SGRAPH_H
# define TPL_SGRAPH_H

# include <memory>
# include <htlist.H>
# include <tpl_graph.H>
# include <tpl_dynSetTree.H>

using namespace Aleph;

namespace Aleph {


    template <typename Node_Info = Empty_Class> 
class Graph_Snode
{
public:

  GRAPH_NODE_COMMON(Graph_Snode);
  
  DynList<void*> arc_list; // lista de adyacencia

  Graph_Snode() : num_arcs(0) { /* empty */ }

  Graph_Snode(const Graph_Snode &) : num_arcs(0) { /* empty */ }

  Graph_Snode(const Node_Info & info) : node_info(info), num_arcs(0)
  { 
    /* empty */ 
  }

  Graph_Snode(Graph_Snode * node) : node_info(node->get_info()), num_arcs(0)
  { 
    /* empty */ 
  }
};

    template <typename Arc_Info = Empty_Class> 
class Graph_Sarc
{
public:

  GRAPH_ARC_COMMON(Graph_Sarc);

  Graph_Sarc() : src_node(NULL), tgt_node(NULL)
  { 
    /* empty */ 
  }

  Graph_Sarc(const Arc_Info & info) 
    : arc_info(info), src_node(NULL), tgt_node(NULL)
  { 
    /* empty */ 
  }

  Graph_Sarc(void * src, void * tgt, const Arc_Info & data) 
    : arc_info(data), src_node(src), tgt_node(tgt)
  { 
    // empty
  }

  Graph_Sarc(void * src, void * tgt) : src_node(src), tgt_node(tgt)
  { 
    // empty
  }
};


template <typename __Graph_Node = Graph_Snode<int>, 
          typename __Graph_Arc  = Graph_Sarc<int>>
class List_SGraph
{
  GRAPH_ATTR_COMMON(List_SGraph);

private:

  typedef DynSetTree<Node*, Rand_Tree> DynSetNode;
  typedef DynSetTree<Arc*, Rand_Tree> DynSetArc;

  DynSetNode node_list; // lista de nodos
  DynSetArc  arc_list;  // lista de arcos

public:

  class Node_Iterator : public DynSetNode::Iterator
  {
  public:

    typedef Node * Item_Type;

    typedef List_SGraph Set_Type;

    Node_Iterator() { /* empty */ }

    Node_Iterator(List_SGraph & g) : DynSetNode::Iterator(g.node_list)
    {
      // empty
    }

    Node * get_current_node() const
    {
      return this->get_curr();
    }
  };

  class Node_Arc_Iterator : public DynList<void*>::Iterator
  {
    Node * src_node; 
    
  public:

    typedef Arc * Item_Type;

    typedef Node * Set_Type;

    Node_Arc_Iterator() { /* empty */ }

    Node_Arc_Iterator(Node * src) 
      : DynList<void*>::Iterator(src->arc_list), src_node(src)
    {
      // empty 
    }

    Arc * get_current_arc() const
    {
      return (Arc*) this->DynList<void*>::Iterator::get_curr();
    }

    Arc * get_current() const { return get_current_arc(); }

    Arc * get_curr() const { return get_current_arc(); }

    Node * get_tgt_node() const
    {
      Arc * a = get_curr();
      return (Node*) a->get_connected_node(src_node);
    }
  };

  class Arc_Iterator : public DynSetArc::Iterator
  {
  public:

    typedef Arc * Item_Type;

    typedef List_SGraph Set_Type;

    Arc_Iterator() { /* empty */ }

    Arc_Iterator(List_SGraph & _g) : DynSetArc::Iterator(_g.arc_list)
    {
      // empty
    }

    Arc * get_current_arc() const 
    {
      return this->get_curr();
    }

    Node * get_src_node() const { return (Node*) get_current_arc()->src_node; }

    Node * get_tgt_node() const { return (Node*) get_current_arc()->tgt_node; }
  };

  GRAPH_ITERATIVE_METHODS;

  GRAPH_SEARCH_METHODS; 


  virtual Node * insert_node(Node * p)
  {
    I(p->arc_list.is_empty());

    ++num_nodes;
    node_list.append(p);

    return p;
  }

private:

  Arc * insert_arc(Node * src, Node * tgt, void * a)
  {
    Arc * arc = (Arc*) a;

    arc->src_node = src;
    arc->tgt_node = tgt;

    src->arc_list.append(a);
    src->num_arcs++;
    if (not digraph and src != tgt)
      {
        tgt->arc_list.append(a);
        tgt->num_arcs++;
      }

    arc_list.append(arc);
    ++num_arcs;

    return arc;
  }

public:

  GRAPH_INSERTION_METHODS;

private:

  void disconnect_arc(Arc * arc)
  {
    Node * src = (Node*) arc->src_node;
    Node * tgt = (Node*) arc->tgt_node;

    src->arc_list.remove(arc);
    src->num_arcs--;

    if (not digraph and src != tgt)
      {
        tgt->arc_list.remove(arc);
        tgt->num_arcs--;
      }
  }

public:

  virtual void remove_arc(Arc * arc)
  {
    disconnect_arc(arc);
    arc_list.remove(arc);
    --num_arcs;
    delete arc;
  }

  virtual void remove_node(Node * p)
  {
    for (typename DynSetArc::Iterator it(arc_list); it.has_curr(); )
      {
        Arc * arc = (Arc*) it.get_curr();

        if (get_src_node(arc) == p or get_tgt_node(arc) == p)
          {
            disconnect_arc(arc);
            --num_arcs;
            delete it.del();
          }
        else
          it.next();
      }

    node_list.remove(p);
    --num_nodes;
    
    delete p;
  }

  Node * get_first_node() const
  {
    return (Node*) node_list.get_first();
  }

  Arc * get_first_arc() const
  {
    return (Arc*) arc_list.get_first();
  }

  Arc * get_first_arc(Node * p) const
  {
    return (Arc*) p->arc_list.get_first();
  }

  List_SGraph()
  {
    init();
  }

private:

  void clear()
  {
    arc_list.for_each( [/* Lambda */] (const Arc * p) { delete p; } );
    node_list.for_each( [/* Lambda */] (const Node * p) { delete p; } );
  }

public:

  ~List_SGraph()
  {
    clear();
  }

      template <class GT>
  List_SGraph(GT & g)
  {
    init();
    inter_copy_graph<GT, List_SGraph>(*this, g, false);
  }

  void swap(List_SGraph & g)
  {
    common_swap(g);
    node_list.swap(g.node_list);
    arc_list.swap(g.arc_list);
  }

  List_SGraph(List_SGraph && g) 
  {
    init();
    swap(g);
  }

  List_SGraph & operator = (const List_SGraph & g)
  {
    if (&g == this)
      return *this;

    clear();

    copy_graph(*this, const_cast<List_SGraph&>(g));

    return *this;
  }

  List_SGraph & operator = (List_SGraph && g)
  {
    swap(g);

    return *this;
  }

private:

      template <class Cmp>
  struct Cmp_Arc
  {
    Cmp & cmp;

    Cmp_Arc(Cmp && __cmp = Cmp()) : cmp(__cmp) { /* empty */ }

    Cmp_Arc(Cmp & __cmp) : cmp(__cmp) { /* empty */ }

    bool operator () (Slinknc * s1, Slinknc * s2) const
    {
      Arc * arc1 = (Arc*) s1;
      Arc * arc2 = (Arc*) s2;
      return cmp(arc1, arc2);
    }
  };

public:

      template <class Compare> 
  void sort_arcs(Compare & cmp)
  {
    Cmp_Arc<Compare> comp(cmp);
    mergesort<HTList, Cmp_Arc<Compare>>(arc_list, comp);
  }

        template <class Compare> 
  void sort_arcs(Compare && cmp = Compare())
  {
    mergesort<Cmp_Arc<Compare>>(arc_list, Cmp_Arc<Compare>(cmp)); 
  }

  GRAPH_FUNCTIONAL_METHODS(List_SGraph);
};

  template <typename __Graph_Node = Graph_Snode<int>,
            typename __Graph_Arc  = Graph_Sarc<int>>
class List_SDigraph : public List_SGraph<__Graph_Node, __Graph_Arc>
{
  typedef List_SGraph<__Graph_Node, __Graph_Arc> GT;

public:

  typedef __Graph_Node Node;

  typedef __Graph_Arc Arc;

  List_SDigraph() 
  {
    this->digraph = true; 
  }
  
  List_SDigraph(const List_SDigraph & dg) : GT()
  {
    this->digraph = true; 
    copy_graph(*this, const_cast<List_SDigraph<Node, Arc>&>(dg));
  }

  List_SDigraph & operator = (const List_SDigraph<Node, Arc> & g)
  {
    if (this == &g) 
      return *this;

    this->digraph = true;
    copy_graph(*this, const_cast<List_SDigraph<Node, Arc>&>(g));

    return *this;
  }

  List_SDigraph(List_SDigraph && dg) : GT()
  {
    this->digraph = true;
    this->swap(dg);
  }

  List_SDigraph & operator = (List_SDigraph<Node, Arc> && g)
  {
    this->digraph = true; 
    this->swap(g);

    return *this;
  }
};


GRAPH_METHODS_IMPLS(List_SGraph);


} // end namespace Aleph

# endif /* TPL_SGRAPH_H */