source: lemon-0.x/src/include/graph.h @ 21:181b37336b29

// -*-mode: c++; -*-
#ifndef __GRAPH_H_
#define __GRAPH_H_

//inline void *operator new(size_t s, void *p) { return p; }
#include <new>
#include <vector>

namespace NEGRO 
{
  using namespace std;
  
#include "oldgraph.h"
  
  template <class N, class E> class Graph : protected OldGraph<N,E>
  {
  public:
    typedef E EdgeType;
    typedef N NodeType;
    
    class EdgePoint
    {
    public:
      NEGRO::EdgePoint e;
      bool isValid() { return e; }
    };
    
    class InEdgePoint : public EdgePoint {};
    class OutEdgePoint : public EdgePoint {};
    class BiEdgePoint : public EdgePoint {};
    class SymEdgePoint : public EdgePoint {};
    
    typedef int NodePoint;
    
    class NodeIterator;
    
    class EdgeIterator;
    class InEdgeIterator;
    class OutEdgeIterator;
    class BiEdgeIterator;
    class SymEdgeIterator;
    class AllEdgeIterator;
    
    class FirstAnythingTypeNode; //Required by the unified First() function.

    friend class NodeIterator;
    friend class EdgeIterator;
    friend class InEdgeIterator;
    friend class OutEdgeIterator;
    friend class BiEdgeIterator;
    friend class SymEdgeIterator;
    friend class AllEdgeIterator;
    
    class NodeIterator
    {
      Graph<N,E> *G;  //operator*() miatt kell!!!
      int n;     //nem kellene, ha itt mutato lenne!!
    public:    
      
      NodeIterator() {;} 
      NodeIterator(Graph<N,E> &Gr)//'const Graph<N,E> &G' would be wrong.
      {G=&Gr;n=Gr.OldGraph<N,E>::FirstNode();} 
      NodeIterator(const NodeIterator &i) {G=i.G;n=i.n;}
      
      NodeIterator &GoNext() { n=G->NextNode(n); return *this;}
      NodeIterator Next() const { return NodeIterator(*this).GoNext();}
      NodeIterator &operator++() { return GoNext();} 
      NodeIterator operator++(int)
      {NodeIterator tmp(*this); GoNext(); return tmp;}
      bool isValid() { return n!=INVALID; }
      
      N &operator*() const { return G->Data(n); }
      N *operator->() const { return &G->Data(n); }
      
      bool operator==(const NodeIterator &i) const {return n==i.n;}
      bool operator!=(const NodeIterator &i) const {return n!=i.n;}
      
      int Index() const { return n; } //If the nodes are indexable 
      friend class Graph;
      friend class EdgeIterator;
      friend class InEdgeIterator;
      friend class OutEdgeIterator;
      friend class BiEdgeIterator;
      friend class SymEdgeIterator;
      friend class AllEdgeIterator;
      friend class FirstAnythingTypeNode;

      //Nem kellene egy:
      //      static NodeIterator &GetInvalid();  ?
    };
    
    class EdgeIterator
    {
      
      Graph<N,E> *G; //Itt baj van!!!!! operator*() miatt kell!
      //Ez csak kicsit baj, de:
      // Meg a From() es To() miatt!!!!!!!!!!
      
      NEGRO::EdgePoint e;
      
    public:
      EdgeIterator() {;} //Kell inicializalni? (Nem)
      EdgeIterator(const EdgeIterator &i) {G=i.G;e=i.e;}
      
      // Lehet, hogy ez a ketto nem kell!!!
      
      NodeIterator From() const {NodeIterator i;i.G=G;i.n=e->From();return i;}
      NodeIterator To() const {NodeIterator i;i.G=G;i.n=e->To();return i;}
      
      bool isValid() {return e;}
      E &operator*() const { return G->Data(e); }
      E *operator->() const { return &G->Data(e); }
      
      //operator const OutEdgeIterator ();
      //operator const InEdgeIterator ();
      //operator const BiEdgeIterator ();
      //operator const SymEdgeIterator(); //Ez kerdeses, mit csinal
      
      bool operator==(const EdgeIterator &i) const {return e==i.e;}
      bool operator!=(const EdgeIterator &i) const {return e!=i.e;}
       
      int Index() const { return e.index.block*EDGE_BLOCK_SIZE+e.index.index; }
      //If the edges are indexable 

      friend class Graph;
      friend class InEdgeIterator;
      friend class OutEdgeIterator;
      friend class BiEdgeIterator;
      friend class SymEdgeIterator;
      friend class AllEdgeIterator;
    };
    
    class BiEdgeIterator : public EdgeIterator
    {
    public:
      BiEdgeIterator &GoNextIn()  { e=e->NextIn(); return *this;}
      BiEdgeIterator &GoNextOut() { e=e->NextOut(); return *this;}
      BiEdgeIterator NextIn() const  {return BiEdgeIterator(*this).GoNextIn();}
      BiEdgeIterator NextOut() const {return BiEdgeIterator(*this).GoNextOut();}
      
      operator InEdgeIterator ()
      {InEdgeIterator i; i.G=G;i.e=e;return i;}
      operator OutEdgeIterator ()
      {OutEdgeIterator i; i.G=G;i.e=e;return i;}
      //operator const SymEdgeIterator ()
      
      friend class Graph;
    };
    
    class InEdgeIterator : public EdgeIterator
    //Ne a BiEdgeIterator-bol szarmazzon?
    {
    public:
      InEdgeIterator() {}
      InEdgeIterator(const Graph<N,E> &Gr,const NodeIterator &n)
      { G=&Gr; e=Gr.OldGraph<N,E>::FirstIn(n.n);}

      InEdgeIterator &GoNext() { e=e->NextIn(); return *this;}
      InEdgeIterator Next() const {return InEdgeIterator(*this).GoNext();}
      InEdgeIterator &operator++() { return GoNext();}
      InEdgeIterator operator++(int)
      {InEdgeIterator tmp(*this); GoNext(); return tmp;}
      
      operator const OutEdgeIterator ()
      {OutEdgeIterator i; i.G=G;i.e=e;return i;}
      operator const BiEdgeIterator ()
      {EdgeIterator i; i.G=G;i.e=e;return i;}
      //      operator const SymEdgeIterator ();
      
      NodeIterator Anode() const {return To();}
      NodeIterator Bnode() const {return From();}
      
      friend class Graph;
    };
    
    class OutEdgeIterator : public EdgeIterator
    {
    public:
      OutEdgeIterator() {}
      OutEdgeIterator(Graph<N,E> &Gr,const NodeIterator &n)
      { G=&Gr; e=Gr.OldGraph<N,E>::FirstOut(n.n);}

      OutEdgeIterator &GoNext() { e=e->NextOut(); return *this;}
      OutEdgeIterator Next() const {return OutEdgeIterator(*this).GoNext();}
      OutEdgeIterator &operator++() { return GoNext();}
      OutEdgeIterator operator++(int)
      {OutEdgeIterator tmp(*this); GoNext(); return tmp;}
      
      NodeIterator Anode() const {return From();}
      NodeIterator Bnode() const {return To();}
      
      operator const InEdgeIterator ()
      {InEdgeIterator i; i.G=G;i.e=e;return i;}
      operator const BiEdgeIterator ()
      {BiEdgeIterator i; i.G=G;i.e=e;return i;}
      //operator const SymEdgeIterator(); 
      
      friend class Graph;
    };
    
    class SymEdgeIterator : public EdgeIterator
    {
      NodeIterator n;  // Itt ketszer van a G
      
    public:
      SymEdgeIterator() {}
      SymEdgeIterator(const Graph<N,E> &Gr,const NodeIterator &nn)
      { G=&Gr; n=nn; e=Gr.FirstSym(nn.n); }

      SymEdgeIterator &GoNext() { e=e->NextEdge(n.n); return *this;}
      SymEdgeIterator Next() const {return SymEdgeIterator(*this).GoNext();}
      SymEdgeIterator &operator++() { return GoNext();}
      SymEdgeIterator operator++(int)
      {SymEdgeIterator tmp(*this); GoNext(); return tmp;}
      
      NodeIterator Anode() const {return n;}
      NodeIterator Bnode() const {return n.n==From().n?To():From();}
      
      operator const InEdgeIterator ()
      {InEdgeIterator i; i.G=G;i.e=e;return i;}
      operator const OutEdgeIterator ()
      {OutEdgeIterator i; i.G=G;i.e=e;return i;}
      operator const BiEdgeIterator ()
      {BiEdgeIterator i; i.G=G;i.e=e;return i;}
      
      friend class Graph;
    };
    
    class AllEdgeIterator : public EdgeIterator
    {
      NodeIterator n;  // Itt ketszer van a G
      
    public:
      AllEdgeIterator() {}
      AllEdgeIterator(Graph<N,E> &Gr) : n(Gr)
      {
        e=n.isValid()?Gr.OldGraph<N,E>::FirstOut(n.n):NULL;
      }  

      AllEdgeIterator &GoNext()
      {
        e=e->NextOut();
        if(!e && (++n).isValid()) e=G->OldGraph<N,E>::FirstOut(n.n);
        return *this;
      }
      AllEdgeIterator Next() const {return AllEdgeIterator(*this).GoNext();}
      AllEdgeIterator &operator++() { return GoNext();}
      AllEdgeIterator operator++(int)
        {AllEdgeIterator tmp(*this); GoNext(); return tmp;}
      
      
      NodeIterator Anode() const {return n;}
      NodeIterator Bnode() const {return n.n==From().n?To():From();}
      
      operator const InEdgeIterator ()
      {InEdgeIterator i; i.G=G;i.e=e;return i;}
      operator const OutEdgeIterator ()
      {OutEdgeIterator i; i.G=G;i.e=e;return i;}
      operator const BiEdgeIterator ()
      {BiEdgeIterator i; i.G=G;i.e=e;return i;}
      
      friend class Graph;
    };
    
    typedef NodeIterator DeletingNodeIterator;
    typedef EdgeIterator DeletingEdgeIterator;
    typedef BiEdgeIterator DeletingBiEdgeIterator;
    typedef OutEdgeIterator DeletingOutEdgeIterator;
    typedef InEdgeIterator DeletingInEdgeIterator;
    typedef SymEdgeIterator DeletingSymEdgeIterator;
    
    const NodeIterator FirstNode()
    {
      NodeIterator i;
      i.G=this;i.n=OldGraph<N,E>::FirstNode();
      return i;
    }
    
    void GetFirst(NodePoint &p)   { p=OldGraph<N,E>::FirstNode(); }
    
    void GetFirst(InEdgePoint &p,const NodePoint &n)
    { p=OldGraph<N,E>::FirstIn(n); }
    void GetFirst(OutEdgePoint &p,const NodePoint &n)
    { p=OldGraph<N,E>::FirstOut(n); }
    void GetFirst(SymEdgePoint &p,const NodePoint &n)
    { p=OldGraph<N,E>::FirstEdge(n); }
    void GetFirst(EdgePoint &p) //Vegigmegy mindenen
    { p.e=NodeNum()?OldGraph<N,E>::FirstOut(OldGraph<N,E>::FirstNode()):NULL;}

    void GetFirst(NodeIterator &i) { i.G=this;i.n=OldGraph<N,E>::FirstNode();}
    
    void GetFirst(InEdgeIterator &i,const NodeIterator &n)
    { i.G=this;i.e=OldGraph<N,E>::FirstIn(n.n); }
    void GetFirst(OutEdgeIterator &i,const NodeIterator &n)
    { i.G=this;i.e=OldGraph<N,E>::FirstOut(n.n); }
    void GetFirst(SymEdgeIterator &i,const NodeIterator &n)
    { i.G=this;i.e=OldGraph<N,E>::FirstSym(n.n); }
    void GetFirst(AllEdgeIterator &i) //Vegigmegy mindenen
    {
      i.G=this;
      GetFirst(i.n);
      i.e=OldGraph<N,E>::NodeNum()?OldGraph<N,E>::FirstOut(i.n.n):NULL;
    }  
    
    
    
    //Vagy beginnode()?
    const DeletingEdgeIterator FirstOut(const NodeIterator &n)
    {
      EdgeIterator i;
      i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstOut(n.n);
      return i;
    }
    const DeletingEdgeIterator FirstIn(const NodeIterator &n)
    {
      EdgeIterator i;
      i.G=n.G;i.edge=n.G->OldGraph<N,E>::FirstIn(n.n);
      return i;
    }
    const DeletingSymEdgeIterator FirstSym(const NodeIterator &n)
    {
      EdgeIterator i;
      i.G=n.G;i.n=n.n;
      i.edge=n.G->OldGraph<N,E>::FirstEdge(n.n);
      return i;
    }
    
    //    class FirstAnythingType;
    //    friend class FirstAnythingType;

    class FirstAnythingTypeNode
    {
      NodeIterator n;
    public:
      FirstAnythingTypeNode(NodeIterator i) : n(i) {}

      operator const InEdgeIterator () const
      {InEdgeIterator i; n.G->GetFirst(i,n);return i;}
      operator const OutEdgeIterator () const
      {OutEdgeIterator i; n.G->GetFirst(i,n);return i;}
      operator const SymEdgeIterator () const
      {SymEdgeIterator i; n.G->GetFirst(i,n);return i;}
  
      operator const InEdgePoint () const
      {InEdgePoint i; n.G->GetFirst(i,n);return i;}
      operator const OutEdgePoint () const
      {OutEdgePoint i; n.G->GetFirst(i,n);return i;}
      operator const SymEdgePoint () const
      {SymEdgePoint i; n.G->GetFirst(i,n);return i;}
    };
    
    class FirstAnythingType
    {
      Graph<N,E> *G;
    public:
      FirstAnythingType(Graph<N,E> *gg) : G(gg) {}

      operator const AllEdgeIterator () const
      {AllEdgeIterator i; G->GetFirst(i);return i;}  
      operator const EdgePoint () const
      {EdgePoint i; G->GetFirst(i);return i;}
      operator const NodeIterator () const
      {NodeIterator i; G->GetFirst(i);return i;}  
      operator const NodePoint () const
      {NodePoint i; G->GetFirst(i);return i;}
    } _FST;
    
    //    const NodeIterator First() {NodeIterator i;GetFirst(i); return i;}
    FirstAnythingTypeNode First(NodeIterator &i)
    {FirstAnythingTypeNode t(i); return t;}
    const FirstAnythingType &First() {return _FST;}
    
    // LastNode() vagy endnode() stb. Nem kell?
    
    DeletingNodeIterator AddNode()
    {
      DeletingNodeIterator i;
      i.G=this; i.n=OldGraph<N,E>::AddNode();
      return i;
    }
    DeletingEdgeIterator
    AddEdge(const NodeIterator from,const NodeIterator to)
    {
      DeletingEdgeIterator i;
      i.G=this;i.e=OldGraph<N,E>::AddEdge(from.n,to.n);return i;
    }
    
    void Delete(DeletingNodeIterator n) {n.G->OldGraph<N,E>::Delete(n.n);}
    void Delete(DeletingEdgeIterator e) {e.G->OldGraph<N,E>::Delete(e.e);}
    
    int NodeNum() { OldGraph<N,E>::NodeNum(); }
    void Clean() { OldGraph<N,E>::Clean(); }

    Graph() : _FST(this) {}

    // MAPS:
    template<class T> class NodeMap
    {
      Graph<N,E> *G;
      vector<T> map;

    public:
      typedef T value_type;
      void Put(const NodeIterator i, const T &t) {map[i.Index()]=t;}
      T Get(const NodeIterator i) const {return map[i.Index()];}
      T operator[](NodeIterator i) {return map[i.Index()];}

      void update() { map.resize(G->MaxNode());}

      NodeMap() {}
      void SetG(Graph<N,E> &Gr) { G=&Gr; update();}      
    };

    template<class T> class EdgeMap
    {
      Graph<N,E> *G;
      vector<T> map;

    public:
      typedef T value_type;
      void Put(const NodeIterator i, const T &t) {map[i.Index()]=t;}
      T &Get(const NodeIterator i) {return map[i.Index()];}
      T &operator[](NodeIterator i) {return map[i.Index()];}
      
      void update()
        { map.resize(G->MaxEdge());}
      
      EdgeMap() {}
      void SetG(Graph<N,E> &Gr) 
      { G=&Gr ;update();}
      
    };
    

    int MaxNode() { return OldGraph<N,E>::MaxNode();}
    int MaxEdge() { return ::edge_block_num*EDGE_BLOCK_SIZE;}
    
  };
  
  /*   Ez itt a fiam kommentje:
       <v n  nnnnnnnnnnnnnncncccccccccccccccccvvvvvv
       vvnvnvnvnvnvvnnvnvnvnnvnbbbvfffffvvffffffffffffffffffffz
       <<  < < <  < <  <   .cx..x.c.cc.c          
       mcmn   
  */
  
}

#endif