/* -*- 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_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 <functional>

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

    ItemIntMap& index;

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

    // is root item and it has ~(items[it].parent) component id.  Else

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

    //

    // The \c next and \c prev provides the double-linked

    // cyclic list of one component's items.

    struct ItemT {

      int parent;

      Item item;

      int next, prev;

    };

    std::vector<ItemT> items;

    int firstFreeItem;

    struct ClassT {

      int size;

      int firstItem;

      int next, prev;

    };

    std::vector<ClassT> classes;

    int firstClass, firstFreeClass;

    int newClass() {

      if (firstFreeClass == -1) {

        int cdx = classes.size();

        classes.push_back(ClassT());

        return cdx;

      } else {

        int cdx = firstFreeClass;

        firstFreeClass = classes[firstFreeClass].next;

        return cdx;

      }

    }

    int newItem() {

      if (firstFreeItem == -1) {

        int idx = items.size();

        items.push_back(ItemT());

        return idx;

      } else {

        int idx = firstFreeItem;

        firstFreeItem = items[firstFreeItem].next;

        return idx;

      }

    }

    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;

    }

    int classIndex(int idx) const {

      return ~(items[repIndex(idx)].parent);

    }

    void singletonItem(int idx) {

      items[idx].next = idx;

      items[idx].prev = idx;

    }

    void laceItem(int idx, int rdx) {

      items[idx].prev = rdx;

      items[idx].next = items[rdx].next;

      items[items[rdx].next].prev = idx;

      items[rdx].next = idx;

    }

    void unlaceItem(int idx) {

      items[items[idx].prev].next = items[idx].next;

      items[items[idx].next].prev = items[idx].prev;

      items[idx].next = firstFreeItem;

      firstFreeItem = idx;

    }

    void spliceItems(int ak, int bk) {

      items[items[ak].prev].next = bk;

      items[items[bk].prev].next = ak;

      int tmp = items[ak].prev;

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

      items[bk].prev = tmp;

    }

    void laceClass(int cls) {

      if (firstClass != -1) {

        classes[firstClass].prev = cls;

      }

      classes[cls].next = firstClass;

      classes[cls].prev = -1;

      firstClass = cls;

    }

    void unlaceClass(int cls) {

      if (classes[cls].prev != -1) {

        classes[classes[cls].prev].next = classes[cls].next;

      } else {

        firstClass = classes[cls].next;

      }

      if (classes[cls].next != -1) {

        classes[classes[cls].next].prev = classes[cls].prev;

      }

      classes[cls].next = firstFreeClass;

      firstFreeClass = cls;

    }

  public:

    UnionFindEnum(ItemIntMap& _index)

      : index(_index), items(), firstFreeItem(-1),

        firstClass(-1), firstFreeClass(-1) {}

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

    ///

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

    /// given element.

    ///

    int insert(const Item& item) {

      int idx = newItem();

      index.set(item, idx);

      singletonItem(idx);

      items[idx].item = item;

      int cdx = newClass();

      items[idx].parent = ~cdx;

      laceClass(cdx);

      classes[cdx].size = 1;

      classes[cdx].firstItem = idx;

      firstClass = cdx;

      return cdx;

    }

    /// \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, int cls) {

      int rdx = classes[cls].firstItem;

      int idx = newItem();

      index.set(item, idx);

      laceItem(idx, rdx);

      items[idx].item = item;

      items[idx].parent = rdx;

      ++classes[~(items[rdx].parent)].size;

    }

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

    ///

    /// Erase each item from the data structure.

    void clear() {

      items.clear();

      firstClass = -1;

      firstFreeItem = -1;

    }

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

    ///

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

    int find(const Item &item) const {

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

    }

    /// \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 -1 else returns the remaining class.

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

      int ak = repIndex(index[a]);

      int bk = repIndex(index[b]);

      if (ak == bk) {

        return -1;

      }

      int acx = ~(items[ak].parent);

      int bcx = ~(items[bk].parent);

      int rcx;

      if (classes[acx].size > classes[bcx].size) {

        classes[acx].size += classes[bcx].size;

        items[bk].parent = ak;

        unlaceClass(bcx);

        rcx = acx;

      } else {

        classes[bcx].size += classes[acx].size;

        items[ak].parent = bk;

        unlaceClass(acx);

        rcx = bcx;

      }

      spliceItems(ak, bk);

      return rcx;

    }

    /// \brief Returns the size of the class.

    ///

    /// Returns the size of the class.

    int size(int cls) const {

      return classes[cls].size;

    }

    /// \brief Splits up the component.

    ///

    /// Splitting the component into singleton components (component

    /// of size one).

    void split(int cls) {

      int fdx = classes[cls].firstItem;

      int idx = items[fdx].next;

      while (idx != fdx) {

        int next = items[idx].next;

        singletonItem(idx);

        int cdx = newClass();

        items[idx].parent = ~cdx;

        laceClass(cdx);

        classes[cdx].size = 1;

        classes[cdx].firstItem = idx;

        idx = next;

      }

      items[idx].prev = idx;

      items[idx].next = idx;

      classes[~(items[idx].parent)].size = 1;

    }

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

    /// \warning This running time of this operation is proportional to the

    /// number of the items in this class.

    void erase(const Item& item) {

      int idx = index[item];

      int fdx = items[idx].next;

      int cdx = classIndex(idx);

      if (idx == fdx) {

        unlaceClass(cdx);

        items[idx].next = firstFreeItem;

        firstFreeItem = idx;

        return;

      } else {

        classes[cdx].firstItem = fdx;

        --classes[cdx].size;

        items[fdx].parent = ~cdx;

        unlaceItem(idx);

        idx = items[fdx].next;

        while (idx != fdx) {

          items[idx].parent = fdx;

          idx = items[idx].next;

        }

      }

    }

    /// \brief Gives back a representant item of the component.

    ///

    /// Gives back a representant item of the component.

    Item item(int cls) const {

      return items[classes[cls].firstItem].item;

    }

    /// \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(int cls) {

      int fdx = classes[cls].firstItem;

      unlaceClass(cls);

      items[items[fdx].prev].next = firstFreeItem;

      firstFreeItem = fdx;

    }

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

    ///

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

    /// on the ids of the classes.

    class ClassIt {

    public:

      /// \brief Constructor of the iterator

      ///

      /// Constructor of the iterator

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

        cdx = unionFind->firstClass;

      }

      /// \brief Constructor to get invalid iterator

      ///

      /// Constructor to get invalid iterator

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

      /// \brief Increment operator

      ///

      /// It steps to the next representant item.

      ClassIt& operator++() {

        cdx = unionFind->classes[cdx].next;

        return *this;

      }

      /// \brief Conversion operator

      ///

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

      operator int() const {

        return cdx;

      }

      /// \brief Equality operator

      ///

      /// Equality operator

      bool operator==(const ClassIt& i) {

        return i.cdx == cdx;

      }

      /// \brief Inequality operator

      ///

      /// Inequality operator

      bool operator!=(const ClassIt& i) {

        return i.cdx != cdx;

      }

    private:

      const UnionFindEnum* unionFind;

      int cdx;

    };

    /// \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, int cls) : unionFind(&ufe) {

        fdx = idx = unionFind->classes[cls].firstItem;

      }

      /// \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].next;

        if (idx == fdx) 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, fdx;

    };

  };

  /// \ingroup auxdat

  ///

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

  /// is able to enumerate the components.

  ///

  /// The class implements an \e Extend-Find data structure which is

  /// able to enumerate the components and the items in a

  /// component. The data structure is a simplification of the

  /// Union-Find structure, and it does not allow to merge two components.

  ///

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

  /// method.

  template <typename _ItemIntMap>

  class ExtendFindEnum {

  public:

    typedef _ItemIntMap ItemIntMap;

    typedef typename ItemIntMap::Key Item;

  private:

    ItemIntMap& index;

    struct ItemT {

      int cls;

      Item item;

      int next, prev;

    };

    std::vector<ItemT> items;

    int firstFreeItem;

    struct ClassT {

      int firstItem;

      int next, prev;

    };

    std::vector<ClassT> classes;

    int firstClass, firstFreeClass;

    int newClass() {

      if (firstFreeClass != -1) {

        int cdx = firstFreeClass;

        firstFreeClass = classes[cdx].next;

        return cdx;

      } else {

        classes.push_back(ClassT());

        return classes.size() - 1;

      }

    }

    int newItem() {

      if (firstFreeItem != -1) {

        int idx = firstFreeItem;

        firstFreeItem = items[idx].next;

        return idx;

      } else {

        items.push_back(ItemT());

        return items.size() - 1;

      }

    }

  public:

    /// \brief Constructor

    ExtendFindEnum(ItemIntMap& _index)

      : index(_index), items(), firstFreeItem(-1),

        classes(), firstClass(-1), firstFreeClass(-1) {}

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

    ///

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

    /// given element.

    int insert(const Item& item) {

      int cdx = newClass();

      classes[cdx].prev = -1;

      classes[cdx].next = firstClass;

      if (firstClass != -1) {

        classes[firstClass].prev = cdx;

      }

      firstClass = cdx;

      int idx = newItem();

      items[idx].item = item;

      items[idx].cls = cdx;

      items[idx].prev = idx;

      items[idx].next = idx;

      classes[cdx].firstItem = idx;

      index.set(item, idx);

      return cdx;

    }

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

    ///

    /// This methods inserts the element \e item a into the \e cls class.

    void insert(const Item& item, int cls) {

      int idx = newItem();

      int rdx = classes[cls].firstItem;

      items[idx].item = item;

      items[idx].cls = cls;

      items[idx].prev = rdx;

      items[idx].next = items[rdx].next;

      items[items[rdx].next].prev = idx;

      items[rdx].next = idx;

      index.set(item, idx);

    }

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

    ///

    /// Erase each item from the data structure.

    void clear() {

      items.clear();

      classes.clear;

      firstClass = firstFreeClass = firstFreeItem = -1;

    }

    /// \brief Gives back the class of the \e item.

    ///

    /// Gives back the class of the \e item.

    int find(const Item &item) const {

      return items[index[item]].cls;

    }

    /// \brief Gives back a representant item of the component.

    ///

    /// Gives back a representant item of the component.

    Item item(int cls) const {

      return items[classes[cls].firstItem].item;

    }

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

      int cdx = items[idx].cls;

      if (idx == items[idx].next) {

        if (classes[cdx].prev != -1) {

          classes[classes[cdx].prev].next = classes[cdx].next;

        } else {

          firstClass = classes[cdx].next;

        }

        if (classes[cdx].next != -1) {

          classes[classes[cdx].next].prev = classes[cdx].prev;

        }

        classes[cdx].next = firstFreeClass;

        firstFreeClass = cdx;

      } else {

        classes[cdx].firstItem = items[idx].next;

        items[items[idx].next].prev = items[idx].prev;

        items[items[idx].prev].next = items[idx].next;

      }

      items[idx].next = firstFreeItem;

      firstFreeItem = idx;

    }

    /// \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(int cdx) {

      int idx = classes[cdx].firstItem;

      items[items[idx].prev].next = firstFreeItem;

      firstFreeItem = idx;

      if (classes[cdx].prev != -1) {

        classes[classes[cdx].prev].next = classes[cdx].next;

      } else {

        firstClass = classes[cdx].next;

      }

      if (classes[cdx].next != -1) {

        classes[classes[cdx].next].prev = classes[cdx].prev;

      }

      classes[cdx].next = firstFreeClass;

      firstFreeClass = cdx;

    }

    /// \brief Lemon style iterator for the classes.

    ///

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

    /// on the ids of classes.

    class ClassIt {

    public:

      /// \brief Constructor of the iterator

      ///

      /// Constructor of the iterator

      ClassIt(const ExtendFindEnum& ufe) : extendFind(&ufe) {

        cdx = extendFind->firstClass;

      }

      /// \brief Constructor to get invalid iterator

      ///

      /// Constructor to get invalid iterator

      ClassIt(Invalid) : extendFind(0), cdx(-1) {}

      /// \brief Increment operator

      ///

      /// It steps to the next representant item.

      ClassIt& operator++() {

        cdx = extendFind->classes[cdx].next;

        return *this;

      }

      /// \brief Conversion operator

      ///

      /// It converts the iterator to the current class id.

      operator int() const {

        return cdx;

      }

      /// \brief Equality operator

      ///

      /// Equality operator

      bool operator==(const ClassIt& i) {

        return i.cdx == cdx;

      }

      /// \brief Inequality operator

      ///

      /// Inequality operator

      bool operator!=(const ClassIt& i) {

        return i.cdx != cdx;

      }

    private:

      const ExtendFindEnum* extendFind;

      int cdx;

    };

    /// \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 ExtendFindEnum& ufe, int cls) : extendFind(&ufe) {

        fdx = idx = extendFind->classes[cls].firstItem;

      }

      /// \brief Constructor to get invalid iterator

      ///

      /// Constructor to get invalid iterator

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

      /// \brief Increment operator

      ///

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

      ItemIt& operator++() {

        idx = extendFind->items[idx].next;

        if (fdx == idx) idx = -1;

        return *this;

      }

      /// \brief Conversion operator

      ///

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

      operator const Item&() const {

        return extendFind->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 ExtendFindEnum* extendFind;

      int idx, fdx;

    };

  };

  /// \ingroup auxdat

  ///

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

  /// is able to store a priority for each item and retrieve the minimum of

  /// each class.

  ///

  /// A \e Union-Find data structure implementation which is able to

  /// store a priority for each item and retrieve the minimum of each

  /// class. In addition, it supports the joining and splitting the

  /// components. If you don't need this feature then you makes

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

  ///

  /// The union-find data strcuture based on a (2, 16)-tree with a

  /// tournament minimum selection on the internal nodes. The insert

  /// operation takes O(1), the find, set, decrease and increase takes

  /// O(log(n)), where n is the number of nodes in the current

  /// component.  The complexity of join and split is O(log(n)*k),

  /// where n is the sum of the number of the nodes and k is the

  /// number of joined components or the number of the components

  /// after the split.

  ///

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

  /// method.

  ///

  template <typename _Value, typename _ItemIntMap,

            typename _Comp = std::less<_Value> >

  class HeapUnionFind {

  public:

    typedef _Value Value;

    typedef typename _ItemIntMap::Key Item;

    typedef _ItemIntMap ItemIntMap;

    typedef _Comp Comp;

  private:

    static const int cmax = 16;

    ItemIntMap& index;

    struct ClassNode {

      int parent;

      int depth;

      int left, right;

      int next, prev;

    };

    int first_class;

    int first_free_class;

    std::vector<ClassNode> classes;

    int newClass() {

      if (first_free_class < 0) {

        int id = classes.size();

        classes.push_back(ClassNode());

        return id;

      } else {

        int id = first_free_class;

        first_free_class = classes[id].next;

        return id;

      }

    }