//

//=======================================================================

// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.

// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek

//

// Distributed under the Boost Software License, Version 1.0. (See

// accompanying file LICENSE_1_0.txt or copy at

// http://www.boost.org/LICENSE_1_0.txt)

//=======================================================================

//

#ifndef BOOST_DISJOINT_SETS_HPP

#define BOOST_DISJOINT_SETS_HPP

#include <vector>

#include <boost/graph/properties.hpp>

#include <boost/pending/detail/disjoint_sets.hpp>

namespace boost {

  struct find_with_path_halving {

    template <class ParentPA, class Vertex>

    Vertex operator()(ParentPA p, Vertex v) { 

      return detail::find_representative_with_path_halving(p, v);

    }

  };

  struct find_with_full_path_compression {

    template <class ParentPA, class Vertex>

    Vertex operator()(ParentPA p, Vertex v){

      return detail::find_representative_with_full_compression(p, v);

    }

  };

  // This is a generalized functor to provide disjoint sets operations

  // with "union by rank" and "path compression".  A disjoint-set data

  // structure maintains a collection S={S1, S2, ..., Sk} of disjoint

  // sets. Each set is identified by a representative, which is some

  // member of of the set. Sets are represented by rooted trees. Two

  // heuristics: "union by rank" and "path compression" are used to

  // speed up the operations.

  // Disjoint Set requires two vertex properties for internal use.  A

  // RankPA and a ParentPA. The RankPA must map Vertex to some Integral type

  // (preferably the size_type associated with Vertex). The ParentPA

  // must map Vertex to Vertex.

  template <class RankPA, class ParentPA,

    class FindCompress = find_with_full_path_compression

    >

  class disjoint_sets {

    typedef disjoint_sets self;

    inline disjoint_sets() {}

  public:

    inline disjoint_sets(RankPA r, ParentPA p) 

      : rank(r), parent(p) {}

    inline disjoint_sets(const self& c) 

      : rank(c.rank), parent(c.parent) {}

    // Make Set -- Create a singleton set containing vertex x

    template <class Element>

    inline void make_set(Element x)

    {

      put(parent, x, x);

      typedef typename property_traits<RankPA>::value_type R;

      put(rank, x, R());

    }

    // Link - union the two sets represented by vertex x and y

    template <class Element>

    inline void link(Element x, Element y)

    {

      detail::link_sets(parent, rank, x, y, rep);

    }

    // Union-Set - union the two sets containing vertex x and y 

    template <class Element>

    inline void union_set(Element x, Element y)

    {

      link(find_set(x), find_set(y));

    }

    // Find-Set - returns the Element representative of the set

    // containing Element x and applies path compression.

    template <class Element>

    inline Element find_set(Element x)

    {

      return rep(parent, x);

    }

    template <class ElementIterator>

    inline std::size_t count_sets(ElementIterator first, ElementIterator last)

    {

      std::size_t count = 0;  

      for ( ; first != last; ++first)

      if (get(parent, *first) == *first)

        ++count;

      return count;

    }

    template <class ElementIterator>

    inline void normalize_sets(ElementIterator first, ElementIterator last)

    {

      for (; first != last; ++first) 

        detail::normalize_node(parent, *first);

    }    

    template <class ElementIterator>

    inline void compress_sets(ElementIterator first, ElementIterator last)

    {

      for (; first != last; ++first) 

        detail::find_representative_with_full_compression(parent, *first);

    }    

  protected:

    RankPA rank;

    ParentPA parent;

    FindCompress rep;

  };

  template <class ID = identity_property_map,

            class InverseID = identity_property_map,

            class FindCompress = find_with_full_path_compression

            >

  class disjoint_sets_with_storage

  {

    typedef typename property_traits<ID>::value_type Index;

    typedef std::vector<Index> ParentContainer;

    typedef std::vector<unsigned char> RankContainer;

  public:

    typedef typename ParentContainer::size_type size_type;

    disjoint_sets_with_storage(size_type n = 0,

                               ID id_ = ID(),

                               InverseID inv = InverseID())

      : id(id_), id_to_vertex(inv), rank(n, 0), parent(n)

    {

      for (Index i = 0; i < n; ++i)

        parent[i] = i;

    }

    // note this is not normally needed

    template <class Element>

    inline void 

    make_set(Element x) {

      parent[x] = x;

      rank[x]   = 0;

    }

    template <class Element>

    inline void 

    link(Element x, Element y)

    {

      extend_sets(x,y);

      detail::link_sets(&parent[0], &rank[0], 

                        get(id,x), get(id,y), rep);

    }

    template <class Element>

    inline void 

    union_set(Element x, Element y) {

      Element rx = find_set(x);

      Element ry = find_set(y);

      link(rx, ry);

    }

    template <class Element>

    inline Element find_set(Element x) {

      return id_to_vertex[rep(&parent[0], get(id,x))];

    }

    template <class ElementIterator>

    inline std::size_t count_sets(ElementIterator first, ElementIterator last)

    {

      std::size_t count = 0;  

      for ( ; first != last; ++first)

      if (parent[*first] == *first)

        ++count;

      return count;

    }

    template <class ElementIterator>

    inline void normalize_sets(ElementIterator first, ElementIterator last)

    {

      for (; first != last; ++first) 

        detail::normalize_node(&parent[0], *first);

    }    

    template <class ElementIterator>

    inline void compress_sets(ElementIterator first, ElementIterator last)

    {

      for (; first != last; ++first) 

        detail::find_representative_with_full_compression(&parent[0],

                                                          *first);

    }    

    const ParentContainer& parents() { return parent; }

  protected:

    template <class Element>

    inline void 

    extend_sets(Element x, Element y)

    {

      Index needed = get(id,x) > get(id,y) ? get(id,x) + 1 : get(id,y) + 1;

      if (needed > parent.size()) {

        rank.insert(rank.end(), needed - rank.size(), 0);

        for (Index k = parent.size(); k < needed; ++k)

        parent.push_back(k);

      } 

    }

    ID id;

    InverseID id_to_vertex;

    RankContainer rank;

    ParentContainer parent;

    FindCompress rep;

  };

} // namespace boost

#endif // BOOST_DISJOINT_SETS_HPP