RhodeCode

      : _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.