RhodeCode

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Copyright (C) 2003-2008

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * 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

  /// \addtogroup gutils

  /// @{

  ///Creates convenience typedefs for the digraph types and iterators

  ///This \c \#define creates convenience typedefs for the following types

  ///of \c Digraph: \c Node,  \c NodeIt, \c Arc, \c ArcIt, \c InArcIt,

  ///\c OutArcIt, \c BoolNodeMap, \c IntNodeMap, \c DoubleNodeMap,

  ///\c BoolArcMap, \c IntArcMap, \c DoubleArcMap.

  ///

  ///\note If the graph type is a dependent type, ie. the graph type depend

  ///on a template parameter, then use \c TEMPLATE_DIGRAPH_TYPEDEFS()

  ///macro.

#define DIGRAPH_TYPEDEFS(Digraph)                                       \

  typedef Digraph::Node Node;                                           \

  typedef Digraph::NodeIt NodeIt;                                       \

  typedef Digraph::Arc Arc;                                             \

  typedef Digraph::ArcIt ArcIt;                                         \

  typedef Digraph::InArcIt InArcIt;                                     \

  typedef Digraph::OutArcIt OutArcIt;                                   \

  typedef Digraph::NodeMap<bool> BoolNodeMap;                           \

  typedef Digraph::NodeMap<int> IntNodeMap;                             \

  typedef Digraph::NodeMap<double> DoubleNodeMap;                       \

  /// use it the following way:

  ///\code

  /// for (ConEdgeIt<Graph> it(g, src, trg); it != INVALID; ++it) {

  ///   ...

  /// }

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

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

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

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

            } else {

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

            }

          }

          splay(s);

        } else {

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

            }

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

          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.

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

    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.