/* -*- C++ -*-

 *

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

 *

 * Copyright (C) 2003-2007

 * 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_UNION_FIND_H

#define LEMON_UNION_FIND_H

//!\ingroup auxdat

//!\file

//!\brief Union-Find data structures.

//!

#include <vector>

#include <list>

#include <utility>

#include <algorithm>

#include <lemon/bits/invalid.h>

namespace lemon {

  /// \ingroup auxdat

  ///

  /// \brief A \e Union-Find data structure implementation

  ///

  /// The class implements the \e Union-Find data structure. 

  /// The union operation uses rank heuristic, while

  /// the find operation uses path compression.

  /// This is a very simple but efficient implementation, providing 

  /// only four methods: join (union), find, insert and size.

  /// For more features see the \ref UnionFindEnum class.

  ///

  /// It is primarily used in Kruskal algorithm for finding minimal

  /// cost spanning tree in a graph.

  /// \sa kruskal()

  ///

  /// \pre You need to add all the elements by the \ref insert()

  /// method.  

  template <typename _ItemIntMap>

  class UnionFind {

  public:

    typedef _ItemIntMap ItemIntMap;

    typedef typename ItemIntMap::Key Item;

  private:

    // If the items vector stores negative value for an item then

    // that item is root item and it has -items[it] component size.

    // Else the items[it] contains the index of the parent.

    std::vector<int> items;

    ItemIntMap& index;

    bool rep(int idx) const {

      return items[idx] < 0;

    }

    int repIndex(int idx) const {

      int k = idx;

      while (!rep(k)) {

        k = items[k] ;

      }

      while (idx != k) {

        int next = items[idx];

        const_cast<int&>(items[idx]) = k;

        idx = next;

      }

      return k;

    }

  public:

    /// \brief Constructor

    ///

    /// Constructor of the UnionFind class. You should give an item to

    /// integer map which will be used from the data structure. If you

    /// modify directly this map that may cause segmentation fault,

    /// invalid data structure, or infinite loop when you use again

    /// the union-find.

    UnionFind(ItemIntMap& m) : index(m) {}

    /// \brief Returns the index of the element's component.

    ///

    /// The method returns the index of the element's component.

    /// This is an integer between zero and the number of inserted elements.

    ///

    int find(const Item& a) {

      return repIndex(index[a]);

    }

    /// \brief Clears the union-find data structure

    ///

    /// Erase each item from the data structure.

    void clear() {

      items.clear();

    }

    /// \brief Inserts a new element into the structure.

    ///

    /// This method inserts a new element into the data structure. 

    ///

    /// The method returns the index of the new component.

    int insert(const Item& a) {

      int n = items.size();

      items.push_back(-1);

      index.set(a,n);

      return n;

    }

    /// \brief Joining the components of element \e a and element \e b.

    ///

    /// This is the \e union operation of the Union-Find structure. 

    /// Joins the component of element \e a and component of

    /// element \e b. If \e a and \e b are in the same component then

    /// it returns false otherwise it returns true.

    bool join(const Item& a, const Item& b) {

      int ka = repIndex(index[a]);

      int kb = repIndex(index[b]);

      if ( ka == kb ) 

	return false;

      if (items[ka] < items[kb]) {

	items[ka] += items[kb];

	items[kb] = ka;

      } else {

	items[kb] += items[ka];

	items[ka] = kb;

      }

      return true;

    }

    /// \brief Returns the size of the component of element \e a.

    ///

    /// Returns the size of the component of element \e a.

    int size(const Item& a) {

      int k = repIndex(index[a]);

      return - items[k];

    }

  };

  /// \ingroup auxdat

  ///

  /// \brief A \e Union-Find data structure implementation which

  /// is able to enumerate the components.

  ///

  /// The class implements a \e Union-Find data structure

  /// which is able to enumerate the components and the items in

  /// a component. If you don't need this feature then perhaps it's

  /// better to use the \ref UnionFind class which is more efficient.

  ///

  /// The union operation uses rank heuristic, while

  /// the find operation uses path compression.

  ///

  /// \pre You need to add all the elements by the \ref insert()

  /// method.

  ///

  template <typename _ItemIntMap>

  class UnionFindEnum {

  public:

    typedef _ItemIntMap ItemIntMap;

    typedef typename ItemIntMap::Key Item;

  private:

    // If the parent stores negative value for an item then that item

    // is root item and it has -items[it].parent component size.  Else

    // the items[it].parent contains the index of the parent.

    //

    // The \c nextItem and \c prevItem provides the double-linked

    // cyclic list of one component's items. The \c prevClass and

    // \c nextClass gives the double linked list of the representant

    // items. 

    struct ItemT {

      int parent;

      Item item;

      int nextItem, prevItem;

      int nextClass, prevClass;

    };

    std::vector<ItemT> items;

    ItemIntMap& index;

    int firstClass;

    bool rep(int idx) const {

      return items[idx].parent < 0;

    }

    int repIndex(int idx) const {

      int k = idx;

      while (!rep(k)) {

        k = items[k].parent;

      }

      while (idx != k) {

        int next = items[idx].parent;

        const_cast<int&>(items[idx].parent) = k;

        idx = next;

      }

      return k;

    }

    void unlaceClass(int k) {

      if (items[k].prevClass != -1) {

        items[items[k].prevClass].nextClass = items[k].nextClass;

      } else {

        firstClass = items[k].nextClass;

      }

      if (items[k].nextClass != -1) {

        items[items[k].nextClass].prevClass = items[k].prevClass;

      }

    } 

    void spliceItems(int ak, int bk) {

      items[items[ak].prevItem].nextItem = bk;

      items[items[bk].prevItem].nextItem = ak;

      int tmp = items[ak].prevItem;

      items[ak].prevItem = items[bk].prevItem;

      items[bk].prevItem = tmp;

    }

  public:

    UnionFindEnum(ItemIntMap& _index) 

      : items(), index(_index), firstClass(-1) {}

    /// \brief Inserts the given element into a new component.

    ///

    /// This method creates a new component consisting only of the

    /// given element.

    ///

    void insert(const Item& item) {

      ItemT t;

      int idx = items.size();

      index.set(item, idx);

      t.nextItem = idx;

      t.prevItem = idx;

      t.item = item;

      t.parent = -1;

      t.nextClass = firstClass;

      if (firstClass != -1) {

        items[firstClass].prevClass = idx;

      }

      t.prevClass = -1;

      firstClass = idx;

      items.push_back(t);

    }

    /// \brief Inserts the given element into the component of the others.

    ///

    /// This methods inserts the element \e a into the component of the

    /// element \e comp. 

    void insert(const Item& item, const Item& comp) {

      int k = repIndex(index[comp]);

      ItemT t;

      int idx = items.size();

      index.set(item, idx);

      t.prevItem = k;

      t.nextItem = items[k].nextItem;

      items[items[k].nextItem].prevItem = idx;

      items[k].nextItem = idx;

      t.item = item;

      t.parent = k;

      --items[k].parent;

      items.push_back(t);

    }

    /// \brief Clears the union-find data structure

    ///

    /// Erase each item from the data structure.

    void clear() {

      items.clear();

      firstClass = -1;

    }

    /// \brief Finds the leader of the component of the given element.

    ///

    /// The method returns the leader of the component of the given element.

    const Item& find(const Item &item) const {

      return items[repIndex(index[item])].item;

    }

    /// \brief Joining the component of element \e a and element \e b.

    ///

    /// This is the \e union operation of the Union-Find structure. 

    /// Joins the component of element \e a and component of

    /// element \e b. If \e a and \e b are in the same component then

    /// returns false else returns true.

    bool join(const Item& a, const Item& b) {

      int ak = repIndex(index[a]);

      int bk = repIndex(index[b]);

      if (ak == bk) {

	return false;

      }

      if ( items[ak].parent < items[bk].parent ) {

        unlaceClass(bk);

        items[ak].parent += items[bk].parent;

	items[bk].parent = ak;

      } else {

        unlaceClass(ak);

        items[bk].parent += items[ak].parent;

	items[ak].parent = bk;

      }

      spliceItems(ak, bk);

      return true;

    }

    /// \brief Returns the size of the component of element \e a.

    ///

    /// Returns the size of the component of element \e a.

    int size(const Item &item) const {

      return - items[repIndex(index[item])].parent;

    }

    /// \brief Splits up the component of the element. 

    ///

    /// Splitting the component of the element into sigleton

    /// components (component of size one).

    void split(const Item &item) {

      int k = repIndex(index[item]);

      int idx = items[k].nextItem;

      while (idx != k) {

        int next = items[idx].nextItem;

        items[idx].parent = -1;

        items[idx].prevItem = idx;

        items[idx].nextItem = idx;

        items[idx].nextClass = firstClass;

        items[firstClass].prevClass = idx;

        firstClass = idx;

        idx = next;

      }

      items[idx].parent = -1;

      items[idx].prevItem = idx;

      items[idx].nextItem = idx;

      items[firstClass].prevClass = -1;

    }

    /// \brief Sets the given element to the leader element of its component.

    ///

    /// Sets the given element to the leader element of its component.

    void makeRep(const Item &item) {

      int nk = index[item];

      int k = repIndex(nk);

      if (nk == k) return;

      if (items[k].prevClass != -1) {

        items[items[k].prevClass].nextClass = nk;

      } else {

        firstClass = nk;

      }

      if (items[k].nextClass != -1) {

        items[items[k].nextClass].prevClass = nk;

      }

      int idx = items[k].nextItem;

      while (idx != k) {

        items[idx].parent = nk;

        idx = items[idx].nextItem;

      }

      items[nk].parent = items[k].parent;

      items[k].parent = nk;

    }

    /// \brief Removes the given element from the structure.

    ///

    /// Removes the element from its component and if the component becomes

    /// empty then removes that component from the component list.

    ///

    /// \warning It is an error to remove an element which is not in

    /// the structure.

    void erase(const Item &item) {

      int idx = index[item];

      if (rep(idx)) {

        int k = idx;

        if (items[k].parent == -1) {

          unlaceClass(idx);

          return;

        } else {

          int nk = items[k].nextItem;

          if (items[k].prevClass != -1) {

            items[items[k].prevClass].nextClass = nk;

          } else {

            firstClass = nk;

          }

          if (items[k].nextClass != -1) {

            items[items[k].nextClass].prevClass = nk;

          }

          int l = items[k].nextItem;

          while (l != k) {

            items[l].parent = nk;

            l = items[l].nextItem;

          }

          items[nk].parent = items[k].parent + 1;

        }

      } else {

        int k = repIndex(idx);

        idx = items[k].nextItem;

        while (idx != k) {

          items[idx].parent = k;

          idx = items[idx].nextItem;

        }

        ++items[k].parent;

      }

      idx = index[item];      

      items[items[idx].prevItem].nextItem = items[idx].nextItem;

      items[items[idx].nextItem].prevItem = items[idx].prevItem;

    }    

    /// \brief Moves the given element to another component.

    ///

    /// This method moves the element \e a from its component

    /// to the component of \e comp.

    /// If \e a and \e comp are in the same component then

    /// it returns false otherwise it returns true.

    bool move(const Item &item, const Item &comp) {

      if (repIndex(index[item]) == repIndex(index[comp])) return false;

      erase(item);

      insert(item, comp);

      return true;

    }

    /// \brief Removes the component of the given element from the structure.

    ///

    /// Removes the component of the given element from the structure.

    ///

    /// \warning It is an error to give an element which is not in the

    /// structure.

    void eraseClass(const Item &item) {

      unlaceClass(repIndex(index[item]));

    }

    /// \brief Lemon style iterator for the representant items.

    ///

    /// ClassIt is a lemon style iterator for the components. It iterates

    /// on the representant items of the classes.

    class ClassIt {

    public:

      /// \brief Constructor of the iterator

      ///

      /// Constructor of the iterator

      ClassIt(const UnionFindEnum& ufe) : unionFind(&ufe) {

        idx = unionFind->firstClass;

      }

      /// \brief Constructor to get invalid iterator

      ///

      /// Constructor to get invalid iterator

      ClassIt(Invalid) : unionFind(0), idx(-1) {}

      /// \brief Increment operator

      ///

      /// It steps to the next representant item.

      ClassIt& operator++() {

        idx = unionFind->items[idx].nextClass;

        return *this;

      }

      /// \brief Conversion operator

      ///

      /// It converts the iterator to the current representant item.

      operator const Item&() const {

        return unionFind->items[idx].item;

      }

      /// \brief Equality operator

      ///

      /// Equality operator

      bool operator==(const ClassIt& i) { 

        return i.idx == idx;

      }

      /// \brief Inequality operator

      ///

      /// Inequality operator

      bool operator!=(const ClassIt& i) { 

        return i.idx != idx;

      }

    private:

      const UnionFindEnum* unionFind;

      int idx;

    };

    /// \brief Lemon style iterator for the items of a component.

    ///

    /// ClassIt is a lemon style iterator for the components. It iterates

    /// on the items of a class. By example if you want to iterate on

    /// each items of each classes then you may write the next code.

    ///\code

    /// for (ClassIt cit(ufe); cit != INVALID; ++cit) {

    ///   std::cout << "Class: ";

    ///   for (ItemIt iit(ufe, cit); iit != INVALID; ++iit) {

    ///     std::cout << toString(iit) << ' ' << std::endl;

    ///   }

    ///   std::cout << std::endl;

    /// }

    ///\endcode

    class ItemIt {

    public:

      /// \brief Constructor of the iterator

      ///

      /// Constructor of the iterator. The iterator iterates

      /// on the class of the \c item.

      ItemIt(const UnionFindEnum& ufe, const Item& item) : unionFind(&ufe) {

        idx = unionFind->repIndex(unionFind->index[item]);

      }

      /// \brief Constructor to get invalid iterator

      ///

      /// Constructor to get invalid iterator

      ItemIt(Invalid) : unionFind(0), idx(-1) {}

      /// \brief Increment operator

      ///

      /// It steps to the next item in the class.

      ItemIt& operator++() {

        idx = unionFind->items[idx].nextItem;

        if (unionFind->rep(idx)) idx = -1;

        return *this;

      }

      /// \brief Conversion operator

      ///

      /// It converts the iterator to the current item.

      operator const Item&() const {

        return unionFind->items[idx].item;

      }

      /// \brief Equality operator

      ///

      /// Equality operator

      bool operator==(const ItemIt& i) { 

        return i.idx == idx;

      }

      /// \brief Inequality operator

      ///

      /// Inequality operator

      bool operator!=(const ItemIt& i) { 

        return i.idx != idx;

      }

    private:

      const UnionFindEnum* unionFind;

      int idx;

    };

  };

  //! @}

} //namespace lemon

#endif //LEMON_UNION_FIND_H