RhodeCode

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_CORE_H

#define LEMON_CORE_H

#include <vector>

#include <algorithm>

#include <lemon/bits/enable_if.h>

#include <lemon/bits/traits.h>

///\file

///\brief LEMON core utilities.

///

///This header file contains core utilities for LEMON.

///do not have to be included directly.

namespace lemon {

  /// \brief Dummy type to make it easier to create invalid iterators.

  ///

  /// Dummy type to make it easier to create invalid iterators.

  /// See \ref INVALID for the usage.

  struct Invalid {

  public:

    bool operator==(Invalid) { return true;  }

    bool operator!=(Invalid) { return false; }

    bool operator< (Invalid) { return false; }

  };

  /// \brief Invalid iterators.

  ///

  /// \ref Invalid is a global type that converts to each iterator

  /// in such a way that the value of the target iterator will be invalid.

#ifdef LEMON_ONLY_TEMPLATES

  const Invalid INVALID = Invalid();

#else

  extern const Invalid INVALID;

#endif

    }

    /// \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

  ///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

  ///

  ///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;

    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;

          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);

            }

          }

        } 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.

    ///\param s The source node

    ///\param t The target node

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

            return INVALID;

          } else {

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

          }

        }

      }

    }

  };

  ///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: