RhodeCode

  ///\endcode

  ///

  ///\sa findEdge()

  template <typename _Graph>

  class ConEdgeIt : public _Graph::Edge {

  public:

    typedef _Graph Graph;

    typedef typename Graph::Edge Parent;

    typedef typename Graph::Edge Edge;

    typedef typename Graph::Node Node;

    /// \brief Constructor.

    ///

    /// Construct a new ConEdgeIt iterating on the edges which

    /// connects the \c u and \c v node.

    ConEdgeIt(const Graph& g, Node u, Node v) : _graph(g) {

      Parent::operator=(findEdge(_graph, u, v));

    }

    /// \brief Constructor.

    ///

    /// Construct a new ConEdgeIt which continues the iterating from

    /// the \c e edge.

    ConEdgeIt(const Graph& g, Edge e) : Parent(e), _graph(g) {}

    /// \brief Increment operator.

    ///

    /// It increments the iterator and gives back the next edge.

    ConEdgeIt& operator++() {

      Parent::operator=(findEdge(_graph, _graph.u(*this),

                                 _graph.v(*this), *this));

      return *this;

    }

  private:

    const Graph& _graph;

  };

  ///Dynamic arc look up between given endpoints.

  ///Using this class, you can find an arc in a digraph from a given

  ///source to a given target in amortized time <em>O(log d)</em>,

  ///where <em>d</em> is the out-degree of the source node.

  ///

  ///It is possible to find \e all parallel arcs between two nodes with

  ///the \c findFirst() and \c findNext() members.

  ///

  ///See the \ref ArcLookUp and \ref AllArcLookUp classes if your

  ///digraph is not changed so frequently.

  ///

  ///This class uses a self-adjusting binary search tree, Sleator's

  ///and Tarjan's Splay tree for guarantee the logarithmic amortized

  ///time bound for arc lookups. This class also guarantees the

  ///optimal time bound in a constant factor for any distribution of

  ///queries.

  ///

  ///\tparam G The type of the underlying digraph.

  ///

  ///\sa ArcLookUp

  ///\sa AllArcLookUp

  template<class G>

  class DynArcLookUp

    : protected ItemSetTraits<G, typename G::Arc>::ItemNotifier::ObserverBase

  {

  public:

    typedef typename ItemSetTraits<G, typename G::Arc>

    ::ItemNotifier::ObserverBase Parent;

    TEMPLATE_DIGRAPH_TYPEDEFS(G);

    typedef G Digraph;

  protected:

    class AutoNodeMap : public ItemSetTraits<G, Node>::template Map<Arc>::Type {

    public:

      typedef typename ItemSetTraits<G, Node>::template Map<Arc>::Type Parent;

      AutoNodeMap(const G& digraph) : Parent(digraph, INVALID) {}

      virtual void add(const Node& node) {

        Parent::add(node);

        Parent::set(node, INVALID);

      }

      virtual void add(const std::vector<Node>& nodes) {

        Parent::add(nodes);

        for (int i = 0; i < int(nodes.size()); ++i) {

          Parent::set(nodes[i], INVALID);

        }

      }

      virtual void build() {

        Parent::build();

        Node it;

        typename Parent::Notifier* nf = Parent::notifier();

        for (nf->first(it); it != INVALID; nf->next(it)) {

          Parent::set(it, INVALID);

        }

      }

    };

    const Digraph &_g;

    AutoNodeMap _head;

    typename Digraph::template ArcMap<Arc> _parent;

    typename Digraph::template ArcMap<Arc> _left;

    typename Digraph::template ArcMap<Arc> _right;

    class ArcLess {

      const Digraph &g;

    public:

      ArcLess(const Digraph &_g) : g(_g) {}

      bool operator()(Arc a,Arc b) const

      {

        return g.target(a)<g.target(b);

      }

    };

  public:

    ///Constructor

    ///Constructor.

    ///

    ///It builds up the search database.

    DynArcLookUp(const Digraph &g)

      : _g(g),_head(g),_parent(g),_left(g),_right(g)

    {

      Parent::attach(_g.notifier(typename Digraph::Arc()));

      refresh();

    }

  protected:

    virtual void add(const Arc& arc) {

      insert(arc);

    }

    virtual void add(const std::vector<Arc>& arcs) {

      for (int i = 0; i < int(arcs.size()); ++i) {

        insert(arcs[i]);

      }

    }

    virtual void erase(const Arc& arc) {

      remove(arc);

    }

    virtual void erase(const std::vector<Arc>& arcs) {

      for (int i = 0; i < int(arcs.size()); ++i) {

        remove(arcs[i]);

      }

    }

    virtual void build() {

      refresh();

    }

    virtual void clear() {

      for(NodeIt n(_g);n!=INVALID;++n) {

        _head.set(n, INVALID);

      }

    }

    void insert(Arc arc) {

      Node s = _g.source(arc);

      Node t = _g.target(arc);

      _left.set(arc, INVALID);

      _right.set(arc, INVALID);

      Arc e = _head[s];

      if (e == INVALID) {

        _head.set(s, arc);

        _parent.set(arc, INVALID);

        return;

      }

      while (true) {

        if (t < _g.target(e)) {

          if (_left[e] == INVALID) {

            _left.set(e, arc);

            _parent.set(arc, e);

            splay(arc);

            return;

          } else {

            e = _left[e];

          }

        } else {

          if (_right[e] == INVALID) {

            _right.set(e, arc);

            _parent.set(arc, e);

            splay(arc);

            return;

          } else {

            e = _right[e];

          }

        }

      }

    }

    void remove(Arc arc) {

      if (_left[arc] == INVALID) {

        if (_right[arc] != INVALID) {

          _parent.set(_right[arc], _parent[arc]);

        }

        if (_parent[arc] != INVALID) {

          if (_left[_parent[arc]] == arc) {

            _left.set(_parent[arc], _right[arc]);

          } else {

            _right.set(_parent[arc], _right[arc]);

          }

        } else {

          _head.set(_g.source(arc), _right[arc]);

        }

      } else if (_right[arc] == INVALID) {

        _parent.set(_left[arc], _parent[arc]);

        if (_parent[arc] != INVALID) {

          if (_left[_parent[arc]] == arc) {

            _left.set(_parent[arc], _left[arc]);

          } else {

            _right.set(_parent[arc], _left[arc]);

          }

        } else {

          _head.set(_g.source(arc), _left[arc]);

        }

      } else {

        Arc e = _left[arc];

        if (_right[e] != INVALID) {

          e = _right[e];

          while (_right[e] != INVALID) {

            e = _right[e];

          }

          Arc s = _parent[e];

          _right.set(_parent[e], _left[e]);

          if (_left[e] != INVALID) {

            _parent.set(_left[e], _parent[e]);

          }

          _left.set(e, _left[arc]);

          _parent.set(_left[arc], e);

          _right.set(e, _right[arc]);

          _parent.set(_right[arc], e);

          _parent.set(e, _parent[arc]);

          if (_parent[arc] != INVALID) {

            if (_left[_parent[arc]] == arc) {

              _left.set(_parent[arc], e);

            } else {

              _right.set(_parent[arc], e);

            }

          }

          splay(s);

        } else {

          _right.set(e, _right[arc]);

          _parent.set(_right[arc], e);

          if (_parent[arc] != INVALID) {

            if (_left[_parent[arc]] == arc) {

              _left.set(_parent[arc], e);

            } else {

              _right.set(_parent[arc], e);

            }

          } else {

            _head.set(_g.source(arc), e);

          }

        }

      }

    }

    Arc refreshRec(std::vector<Arc> &v,int a,int b)

    {

      int m=(a+b)/2;

      Arc me=v[m];

      if (a < m) {

        Arc left = refreshRec(v,a,m-1);

        _left.set(me, left);

        _parent.set(left, me);

      } else {

        _left.set(me, INVALID);

      }

      if (m < b) {

        Arc right = refreshRec(v,m+1,b);

        _right.set(me, right);

        _parent.set(right, me);

      } else {

        _right.set(me, INVALID);

      }

      return me;

    }

    void refresh() {

      for(NodeIt n(_g);n!=INVALID;++n) {

        std::vector<Arc> v;

        for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);

        if(v.size()) {

          std::sort(v.begin(),v.end(),ArcLess(_g));

          Arc head = refreshRec(v,0,v.size()-1);

          _head.set(n, head);

          _parent.set(head, INVALID);

        }

        else _head.set(n, INVALID);

      }

    }

    void zig(Arc v) {

      Arc w = _parent[v];

      _parent.set(v, _parent[w]);

      _parent.set(w, v);

      _left.set(w, _right[v]);

      _right.set(v, w);

      if (_parent[v] != INVALID) {

        if (_right[_parent[v]] == w) {

          _right.set(_parent[v], v);

        } else {

          _left.set(_parent[v], v);

        }

      }

      if (_left[w] != INVALID){

        _parent.set(_left[w], w);

      }

    }

    void zag(Arc v) {

      Arc w = _parent[v];

      _parent.set(v, _parent[w]);

      _parent.set(w, v);

      _right.set(w, _left[v]);

      _left.set(v, w);

      if (_parent[v] != INVALID){

        if (_left[_parent[v]] == w) {

          _left.set(_parent[v], v);

        } else {

          _right.set(_parent[v], v);

        }

      }

      if (_right[w] != INVALID){

        _parent.set(_right[w], w);

      }

    }

    void splay(Arc v) {

      while (_parent[v] != INVALID) {

        if (v == _left[_parent[v]]) {

          if (_parent[_parent[v]] == INVALID) {

            zig(v);

          } else {

            if (_parent[v] == _left[_parent[_parent[v]]]) {

              zig(_parent[v]);

              zig(v);

            } else {

              zig(v);

              zag(v);

            }

          }

        } else {

          if (_parent[_parent[v]] == INVALID) {

            zag(v);

          } else {

            if (_parent[v] == _left[_parent[_parent[v]]]) {

              zag(v);

              zig(v);

            } else {

              zag(_parent[v]);

              zag(v);

            }

          }

        }

      }

      _head[_g.source(v)] = v;

    }

  public:

    ///Find an arc between two nodes.

    ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where

    /// <em>d</em> is the number of outgoing arcs of \c s.

    ///\param s The source node

    ///\param t The target node

    ///\return An arc from \c s to \c t if there exists,

    ///\ref INVALID otherwise.

    Arc operator()(Node s, Node t) const

    {

      Arc a = _head[s];

      while (true) {

        if (_g.target(a) == t) {

          const_cast<DynArcLookUp&>(*this).splay(a);

          return a;

        } else if (t < _g.target(a)) {

          if (_left[a] == INVALID) {

            const_cast<DynArcLookUp&>(*this).splay(a);

            return INVALID;

          } else {

            a = _left[a];

          }

        } else  {

          if (_right[a] == INVALID) {

            const_cast<DynArcLookUp&>(*this).splay(a);

            return INVALID;

          } else {

            a = _right[a];

          }

        }

      }

    }

    ///Find the first arc between two nodes.

    ///Find the first arc between two nodes in time

    /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of

    /// outgoing arcs of \c s.

    ///\param s The source node

    ///\param t The target node

    ///\return An arc from \c s to \c t if there exists, \ref INVALID

    /// otherwise.

    Arc findFirst(Node s, Node t) const

    {

      Arc a = _head[s];

      Arc r = INVALID;

      while (true) {

        if (_g.target(a) < t) {

          if (_right[a] == INVALID) {

            const_cast<DynArcLookUp&>(*this).splay(a);

            return r;

          } else {

            a = _right[a];

          }

        } else {

          if (_g.target(a) == t) {

            r = a;

          }

          if (_left[a] == INVALID) {

            const_cast<DynArcLookUp&>(*this).splay(a);

            return r;

          } else {

            a = _left[a];

          }

        }

      }

    }

    ///Find the next arc between two nodes.

    ///Find the next arc between two nodes in time

    /// <em>O(</em>log<em>d)</em>, where <em>d</em> is the number of

    /// outgoing arcs of \c s.

    ///\param s The source node

    ///\param t The target node

    ///\return An arc from \c s to \c t if there exists, \ref INVALID

    /// otherwise.

    ///\note If \c e is not the result of the previous \c findFirst()

    ///operation then the amorized time bound can not be guaranteed.

#ifdef DOXYGEN

    Arc findNext(Node s, Node t, Arc a) const

#else

    Arc findNext(Node, Node t, Arc a) const

#endif

    {

      if (_right[a] != INVALID) {

        a = _right[a];

        while (_left[a] != INVALID) {

          a = _left[a];

        }

        const_cast<DynArcLookUp&>(*this).splay(a);

      } else {

        while (_parent[a] != INVALID && _right[_parent[a]] ==  a) {

          a = _parent[a];

        }

        if (_parent[a] == INVALID) {

          return INVALID;

        } else {

          a = _parent[a];

          const_cast<DynArcLookUp&>(*this).splay(a);

        }

      }

      if (_g.target(a) == t) return a;

      else return INVALID;

    }

  };

  ///Fast arc look up between given endpoints.

  ///Using this class, you can find an arc in a digraph from a given

  ///source to a given target in time <em>O(log d)</em>,

  ///where <em>d</em> is the out-degree of the source node.

  ///

  ///It is not possible to find \e all parallel arcs between two nodes.

  ///Use \ref AllArcLookUp for this purpose.

  ///

  ///\warning This class is static, so you should refresh() (or at least

  ///refresh(Node)) this data structure

  ///whenever the digraph changes. This is a time consuming (superlinearly

  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).

  ///

  ///\tparam G The type of the underlying digraph.

  ///

  ///\sa DynArcLookUp

  ///\sa AllArcLookUp

  template<class G>

  class ArcLookUp

  {

  public:

    TEMPLATE_DIGRAPH_TYPEDEFS(G);

    typedef G Digraph;

  protected:

    const Digraph &_g;

    typename Digraph::template NodeMap<Arc> _head;

    typename Digraph::template ArcMap<Arc> _left;

    typename Digraph::template ArcMap<Arc> _right;

    class ArcLess {

      const Digraph &g;

    public:

      ArcLess(const Digraph &_g) : g(_g) {}

      bool operator()(Arc a,Arc b) const

      {

        return g.target(a)<g.target(b);

      }

    };

  public:

    ///Constructor

    ///Constructor.

    ///

    ///It builds up the search database, which remains valid until the digraph

    ///changes.

    ArcLookUp(const Digraph &g) :_g(g),_head(g),_left(g),_right(g) {refresh();}

  private:

    Arc refreshRec(std::vector<Arc> &v,int a,int b)

    {

      int m=(a+b)/2;

      Arc me=v[m];

      _left[me] = a<m?refreshRec(v,a,m-1):INVALID;

      _right[me] = m<b?refreshRec(v,m+1,b):INVALID;

      return me;

    }

  public:

    ///Refresh the data structure at a node.

    ///Build up the search database of node \c n.

    ///

    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is

    ///the number of the outgoing arcs of \c n.

    void refresh(Node n)

    {

      std::vector<Arc> v;

      for(OutArcIt e(_g,n);e!=INVALID;++e) v.push_back(e);

      if(v.size()) {

        std::sort(v.begin(),v.end(),ArcLess(_g));

        _head[n]=refreshRec(v,0,v.size()-1);

      }

      else _head[n]=INVALID;

    }

    ///Refresh the full data structure.

    ///Build up the full search database. In fact, it simply calls

    ///\ref refresh(Node) "refresh(n)" for each node \c n.

    ///

    ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is

    ///the number of the arcs of \c n and <em>D</em> is the maximum

    ///out-degree of the digraph.

    void refresh()

    {

      for(NodeIt n(_g);n!=INVALID;++n) refresh(n);

    }

    ///Find an arc between two nodes.

    ///Find an arc between two nodes in time <em>O(</em>log<em>d)</em>, where

    /// <em>d</em> is the number of outgoing arcs of \c s.

    ///\param s The source node

    ///\param t The target node

    ///\return An arc from \c s to \c t if there exists,

    ///\ref INVALID otherwise.

    ///

    ///\warning If you change the digraph, refresh() must be called before using

    ///this operator. If you change the outgoing arcs of

    ///a single node \c n, then

    ///\ref refresh(Node) "refresh(n)" is enough.

    ///

    Arc operator()(Node s, Node t) const

    {

      Arc e;

      for(e=_head[s];

          e!=INVALID&&_g.target(e)!=t;

          e = t < _g.target(e)?_left[e]:_right[e]) ;

      return e;

    }

  };

  ///Fast look up of all arcs between given endpoints.

  ///This class is the same as \ref ArcLookUp, with the addition

  ///that it makes it possible to find all arcs between given endpoints.

  ///

  ///\warning This class is static, so you should refresh() (or at least

  ///refresh(Node)) this data structure

  ///whenever the digraph changes. This is a time consuming (superlinearly

  ///proportional (<em>O(m</em>log<em>m)</em>) to the number of arcs).

  ///

  ///\tparam G The type of the underlying digraph.

  ///

  ///\sa DynArcLookUp

  ///\sa ArcLookUp

  template<class G>

  class AllArcLookUp : public ArcLookUp<G>

  {

    using ArcLookUp<G>::_g;

    using ArcLookUp<G>::_right;

    using ArcLookUp<G>::_left;

    using ArcLookUp<G>::_head;

    TEMPLATE_DIGRAPH_TYPEDEFS(G);

    typedef G Digraph;

    typename Digraph::template ArcMap<Arc> _next;

    Arc refreshNext(Arc head,Arc next=INVALID)

    {

      if(head==INVALID) return next;

      else {

        next=refreshNext(_right[head],next);

//         _next[head]=next;

        _next[head]=( next!=INVALID && _g.target(next)==_g.target(head))

          ? next : INVALID;

        return refreshNext(_left[head],head);

      }

    }

    void refreshNext()

    {

      for(NodeIt n(_g);n!=INVALID;++n) refreshNext(_head[n]);

    }

  public:

    ///Constructor

    ///Constructor.

    ///

    ///It builds up the search database, which remains valid until the digraph

    ///changes.

    AllArcLookUp(const Digraph &g) : ArcLookUp<G>(g), _next(g) {refreshNext();}

    ///Refresh the data structure at a node.

    ///Build up the search database of node \c n.

    ///

    ///It runs in time <em>O(d</em>log<em>d)</em>, where <em>d</em> is

    ///the number of the outgoing arcs of \c n.

    void refresh(Node n)

    {

      ArcLookUp<G>::refresh(n);

      refreshNext(_head[n]);

    }

    ///Refresh the full data structure.

    ///Build up the full search database. In fact, it simply calls

    ///\ref refresh(Node) "refresh(n)" for each node \c n.

    ///

    ///It runs in time <em>O(m</em>log<em>D)</em>, where <em>m</em> is

    ///the number of the arcs of \c n and <em>D</em> is the maximum

    ///out-degree of the digraph.

    void refresh()