lemon-1.1: comparison lemon/unionfind.h

equal deleted inserted replaced

-:a2fb3411c97d
+:fff4cfc1bb80
-/* -*- C++ -*-
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
-* This file is a part of LEMON, a generic C++ optimization library
+* 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).
 *
 /// \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;
 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);
 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;
+return false;
 if (items[ka] < items[kb]) {
-	items[ka] += items[kb];
+items[ka] += items[kb];
-	items[kb] = ka;
+items[kb] = ka;
 } else {
-	items[kb] += items[ka];
+items[kb] += items[ka];
-	items[ka] = kb;
+items[ka] = kb;
 }
 return true;
 }
 /// \brief Returns the size of the component of element \e a.
 /// 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.
 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();
+int cdx = classes.size();
-	classes.push_back(ClassT());
+classes.push_back(ClassT());
-	return cdx;
+return cdx;
 } else {
-	int cdx = firstFreeClass;
+int cdx = firstFreeClass;
-	firstFreeClass = classes[firstFreeClass].next;
+firstFreeClass = classes[firstFreeClass].next;
-	return cdx;
+return cdx;
 }
 }
 int newItem() {
 if (firstFreeItem == -1) {
-	int idx = items.size();
+int idx = items.size();
-	items.push_back(ItemT());
+items.push_back(ItemT());
-	return idx;
+return idx;
 } else {
-	int idx = firstFreeItem;
+int idx = firstFreeItem;
-	firstFreeItem = items[firstFreeItem].next;
+firstFreeItem = items[firstFreeItem].next;
-	return idx;
+return idx;
 }
 }
 bool rep(int idx) const {
 }
 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) {}
+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.
 ///
 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);
 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;
+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;
+classes[acx].size += classes[bcx].size;
-	items[bk].parent = ak;
+items[bk].parent = ak;
 unlaceClass(bcx);
-	rcx = acx;
+rcx = acx;
 } else {
-	classes[bcx].size += classes[acx].size;
+classes[bcx].size += classes[acx].size;
-	items[ak].parent = bk;
+items[ak].parent = bk;
 unlaceClass(acx);
-	rcx = bcx;
+rcx = bcx;
 }
 spliceItems(ak, bk);
 return rcx;
 }
 /// 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);
+singletonItem(idx);
-	int cdx = newClass();
+int cdx = newClass();
 items[idx].parent = ~cdx;
-	laceClass(cdx);
+laceClass(cdx);
-	classes[cdx].size = 1;
+classes[cdx].size = 1;
-	classes[cdx].firstItem = idx;
+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
 int idx = index[item];
 int fdx = items[idx].next;
 int cdx = classIndex(idx);
 if (idx == fdx) {
-	unlaceClass(cdx);
+unlaceClass(cdx);
-	items[idx].next = firstFreeItem;
+items[idx].next = firstFreeItem;
-	firstFreeItem = idx;
+firstFreeItem = idx;
-	return;
+return;
 } else {
-	classes[cdx].firstItem = fdx;
+classes[cdx].firstItem = fdx;
-	--classes[cdx].size;
+--classes[cdx].size;
-	items[fdx].parent = ~cdx;
+items[fdx].parent = ~cdx;
-	unlaceItem(idx);
+unlaceItem(idx);
-	idx = items[fdx].next;
+idx = items[fdx].next;
-	while (idx != fdx) {
+while (idx != fdx) {
-	  items[idx].parent = fdx;
+items[idx].parent = fdx;
-	  idx = items[idx].next;
+idx = items[idx].next;
-	}
+}
 }
 }
 /// \brief Gives back a representant item of the component.
 /// \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 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;
 };
 /// \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 firstClass, firstFreeClass;
 int newClass() {
 if (firstFreeClass != -1) {
-	int cdx = firstFreeClass;
+int cdx = firstFreeClass;
-	firstFreeClass = classes[cdx].next;
+firstFreeClass = classes[cdx].next;
-	return cdx;
+return cdx;
 } else {
-	classes.push_back(ClassT());
+classes.push_back(ClassT());
-	return classes.size() - 1;
+return classes.size() - 1;
 }
 }
 int newItem() {
 if (firstFreeItem != -1) {
-	int idx = firstFreeItem;
+int idx = firstFreeItem;
-	firstFreeItem = items[idx].next;
+firstFreeItem = items[idx].next;
-	return idx;
+return idx;
 } else {
-	items.push_back(ItemT());
+items.push_back(ItemT());
-	return items.size() - 1;
+return items.size() - 1;
 }
 }
 public:
 /// \brief Constructor
 ExtendFindEnum(ItemIntMap& _index)
 : index(_index), items(), firstFreeItem(-1),
-	classes(), firstClass(-1), firstFreeClass(-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;
+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.
 ///
 ///
 /// 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) {
+if (classes[cdx].prev != -1) {
-	  classes[classes[cdx].prev].next = classes[cdx].next;
+classes[classes[cdx].prev].next = classes[cdx].next;
-	} else {
+} else {
-	  firstClass = classes[cdx].next;
+firstClass = classes[cdx].next;
-	}
+}
-	if (classes[cdx].next != -1) {
+if (classes[cdx].next != -1) {
-	  classes[classes[cdx].next].prev = classes[cdx].prev;
+classes[classes[cdx].next].prev = classes[cdx].prev;
-	}
+}
-	classes[cdx].next = firstFreeClass;
+classes[cdx].next = firstFreeClass;
-	firstFreeClass = cdx;
+firstFreeClass = cdx;
 } else {
-	classes[cdx].firstItem = items[idx].next;
+classes[cdx].firstItem = items[idx].next;
-	items[items[idx].next].prev = items[idx].prev;
+items[items[idx].next].prev = items[idx].prev;
-	items[items[idx].prev].next = items[idx].next;
+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
 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;
+classes[classes[cdx].prev].next = classes[cdx].next;
 } else {
-	firstClass = classes[cdx].next;
+firstClass = classes[cdx].next;
 }
 if (classes[cdx].next != -1) {
-	classes[classes[cdx].next].prev = classes[cdx].prev;
+classes[classes[cdx].next].prev = classes[cdx].prev;
 }
 classes[cdx].next = firstFreeClass;
 firstFreeClass = cdx;
 }
 /// \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 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;
+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;
 };
 /// 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;
 if (id < 0) {
 return -1;
 }
 id = nodes[id].next;
 while (depth--) {
 id = nodes[id].left;
 }
 return id;
 }
 void split(int id, int jd) {
 int kd = nodes[id].parent;
 nodes[kd].right = nodes[id].prev;
 nodes[nodes[id].prev].next = -1;
 nodes[jd].left = id;
 nodes[id].prev = -1;
 int num = 0;
 while (id != -1) {
 nodes[id].parent = jd;
 nodes[jd].right = id;
 id = nodes[id].next;
 ++num;
 }
 nodes[kd].size -= num;
 nodes[jd].size = num;
 }
 void pushLeft(int id, int jd) {
 }
 void repairLeft(int id) {
 int jd = ~(classes[id].parent);
 while (nodes[jd].left != -1) {
-	int kd = nodes[jd].left;
+int kd = nodes[jd].left;
-	if (nodes[jd].size == 1) {
+if (nodes[jd].size == 1) {
-	  if (nodes[jd].parent < 0) {
+if (nodes[jd].parent < 0) {
-	    classes[id].parent = ~kd;
+classes[id].parent = ~kd;
-	    classes[id].depth -= 1;
+classes[id].depth -= 1;
-	    nodes[kd].parent = ~id;
+nodes[kd].parent = ~id;
-	    deleteNode(jd);
+deleteNode(jd);
-	    jd = kd;
+jd = kd;
-	  } else {
+} else {
-	    int pd = nodes[jd].parent;
+int pd = nodes[jd].parent;
-	    if (nodes[nodes[jd].next].size < cmax) {
+if (nodes[nodes[jd].next].size < cmax) {
-	      pushLeft(nodes[jd].next, nodes[jd].left);
+pushLeft(nodes[jd].next, nodes[jd].left);
-	      if (less(nodes[jd].left, nodes[jd].next)) {
+if (less(nodes[jd].left, nodes[jd].next)) {
-		nodes[nodes[jd].next].prio = nodes[nodes[jd].left].prio;
+nodes[nodes[jd].next].prio = nodes[nodes[jd].left].prio;
-		nodes[nodes[jd].next].item = nodes[nodes[jd].left].item;
+nodes[nodes[jd].next].item = nodes[nodes[jd].left].item;
-	      }
+}
-	      popLeft(pd);
+popLeft(pd);
-	      deleteNode(jd);
+deleteNode(jd);
-	      jd = pd;
+jd = pd;
-	    } else {
+} else {
-	      int ld = nodes[nodes[jd].next].left;
+int ld = nodes[nodes[jd].next].left;
-	      popLeft(nodes[jd].next);
+popLeft(nodes[jd].next);
-	      pushRight(jd, ld);
+pushRight(jd, ld);
-	      if (less(ld, nodes[jd].left)) {
+if (less(ld, nodes[jd].left)) {
-		nodes[jd].item = nodes[ld].item;
+nodes[jd].item = nodes[ld].item;
-		nodes[jd].prio = nodes[jd].prio;
+nodes[jd].prio = nodes[jd].prio;
-	      }
+}
-	      if (nodes[nodes[jd].next].item == nodes[ld].item) {
+if (nodes[nodes[jd].next].item == nodes[ld].item) {
-		setPrio(nodes[jd].next);
+setPrio(nodes[jd].next);
-	      }
+}
-	      jd = nodes[jd].left;
+jd = nodes[jd].left;
-	    }
+}
-	  }
+}
-	} else {
+} else {
-	  jd = nodes[jd].left;
+jd = nodes[jd].left;
-	}
+}
 }
 }
 void repairRight(int id) {
 int jd = ~(classes[id].parent);
 while (nodes[jd].right != -1) {
-	int kd = nodes[jd].right;
+int kd = nodes[jd].right;
-	if (nodes[jd].size == 1) {
+if (nodes[jd].size == 1) {
-	  if (nodes[jd].parent < 0) {
+if (nodes[jd].parent < 0) {
-	    classes[id].parent = ~kd;
+classes[id].parent = ~kd;
-	    classes[id].depth -= 1;
+classes[id].depth -= 1;
-	    nodes[kd].parent = ~id;
+nodes[kd].parent = ~id;
-	    deleteNode(jd);
+deleteNode(jd);
-	    jd = kd;
+jd = kd;
-	  } else {
+} else {
-	    int pd = nodes[jd].parent;
+int pd = nodes[jd].parent;
-	    if (nodes[nodes[jd].prev].size < cmax) {
+if (nodes[nodes[jd].prev].size < cmax) {
-	      pushRight(nodes[jd].prev, nodes[jd].right);
+pushRight(nodes[jd].prev, nodes[jd].right);
-	      if (less(nodes[jd].right, nodes[jd].prev)) {
+if (less(nodes[jd].right, nodes[jd].prev)) {
-		nodes[nodes[jd].prev].prio = nodes[nodes[jd].right].prio;
+nodes[nodes[jd].prev].prio = nodes[nodes[jd].right].prio;
-		nodes[nodes[jd].prev].item = nodes[nodes[jd].right].item;
+nodes[nodes[jd].prev].item = nodes[nodes[jd].right].item;
-	      }
+}
-	      popRight(pd);
+popRight(pd);
-	      deleteNode(jd);
+deleteNode(jd);
-	      jd = pd;
+jd = pd;
-	    } else {
+} else {
-	      int ld = nodes[nodes[jd].prev].right;
+int ld = nodes[nodes[jd].prev].right;
-	      popRight(nodes[jd].prev);
+popRight(nodes[jd].prev);
-	      pushLeft(jd, ld);
+pushLeft(jd, ld);
-	      if (less(ld, nodes[jd].right)) {
+if (less(ld, nodes[jd].right)) {
-		nodes[jd].item = nodes[ld].item;
+nodes[jd].item = nodes[ld].item;
-		nodes[jd].prio = nodes[jd].prio;
+nodes[jd].prio = nodes[jd].prio;
-	      }
+}
-	      if (nodes[nodes[jd].prev].item == nodes[ld].item) {
+if (nodes[nodes[jd].prev].item == nodes[ld].item) {
-		setPrio(nodes[jd].prev);
+setPrio(nodes[jd].prev);
-	      }
+}
-	      jd = nodes[jd].right;
+jd = nodes[jd].right;
-	    }
+}
-	  }
+}
-	} else {
+} else {
-	  jd = nodes[jd].right;
+jd = nodes[jd].right;
-	}
+}
 }
 }
 bool less(int id, int jd) const {
 return classes[cls].left == -1;
 }
 /// \brief Constructs the union-find.
 ///
 /// Constructs the union-find.
 /// \brief _index The index map of the union-find. The data
 /// structure uses internally for store references.
 HeapUnionFind(ItemIntMap& _index)
 : index(_index), first_class(-1),
-	first_free_class(-1), first_free_node(-1) {}
+first_free_class(-1), first_free_node(-1) {}
 /// \brief Insert a new node into a new component.
 ///
 /// Insert a new node into a new component.
 /// \param item The item of the new node.
 nodes[id].left = -1;
 nodes[id].right = -1;
 nodes[id].item = item;
 index[item] = id;
 int class_id = newClass();
 classes[class_id].parent = ~id;
 classes[class_id].depth = 0;
 classes[class_id].left = -1;
 classes[class_id].right = -1;
 if (first_class != -1) {
 classes[first_class].prev = class_id;
 }
 classes[class_id].next = first_class;
 classes[class_id].prev = -1;
 first_class = class_id;
 nodes[id].parent = ~class_id;
 return class_id;
 }
 /// \brief The class of the item.
 ///
 ///
 /// The time complexity is O(log(n)).
 int find(const Item& item) const {
 return findClass(index[item]);
 }
 /// \brief Joins the classes.
 ///
 /// The current function joins the given classes. The parameter is
 /// an STL range which should be contains valid class ids. The
 /// time complexity is O(log(n)*k) where n is the overall number
 if (classes[l].next != -1) {
 classes[classes[l].next].prev = classes[l].prev;
 }
 classes[classes[l].prev].next = classes[l].next;
 classes[l].prev = -1;
 classes[l].next = -1;
 classes[l].depth = leftNode(l);
 classes[l].parent = class_id;
 }
 { // merging of heap
 int l = class_id;
 for (int ci = 1; ci < int(cs.size()); ++ci) {
 nodes[new_parent].parent = ~l;
 push(new_parent, ~(classes[r].parent));
 pushLeft(new_parent, ~(classes[l].parent));
 setPrio(new_parent);
 classes[r].parent = ~new_parent;
 classes[r].depth += 1;
 } else {
 pushLeft(id, ~(classes[l].parent));
 while (id >= 0 && less(~(classes[l].parent), id)) {
 }
 nodes[~(classes[r].parent)].parent = ~l;
 classes[l].parent = classes[r].parent;
 classes[l].depth = classes[r].depth;
 } else {
 if (classes[l].depth != 0 &&
 nodes[~(classes[l].parent)].size +
 nodes[~(classes[r].parent)].size <= cmax) {
 splice(~(classes[l].parent), ~(classes[r].parent));
 deleteNode(~(classes[r].parent));
 if (less(~(classes[r].parent), ~(classes[l].parent))) {
 nodes[~(classes[l].parent)].prio =
 nodes[~(classes[r].parent)].prio;
 nodes[~(classes[l].parent)].item =
 nodes[~(classes[r].parent)].item;
 }
 } else {
 int new_parent = newNode();
 nodes[new_parent].next = nodes[new_parent].prev = -1;
 push(new_parent, ~(classes[l].parent));
 pushRight(new_parent, ~(classes[r].parent));
 setPrio(new_parent);
 classes[l].parent = ~new_parent;
 classes[l].depth += 1;
 nodes[new_parent].parent = ~l;
 }
 }
 }
 classes[classes[id].right].next = first_class;
 classes[first_class].prev = classes[id].right;
 first_class = classes[id].left;
 if (classes[id].next != -1) {
 classes[classes[id].next].prev = classes[id].prev;
 }
 classes[classes[id].prev].next = classes[id].next;
 deleteClass(id);
 }
 {
 for (int i = 1; i < int(cs.size()); ++i) {
 int l = classes[cs[i]].depth;
 while (nodes[nodes[l].parent].left == l) {
 l = nodes[l].parent;
 }
 int r = l;
 while (nodes[l].parent >= 0) {
 l = nodes[l].parent;
 int new_node = newNode();
 nodes[new_node].prev = -1;
 nodes[l].next = -1;
 nodes[r].prev = -1;
 repairRight(~(nodes[l].parent));
 repairLeft(cs[i]);
 *out++ = cs[i];
 }
 }
 }
 decrease(item, prio);
 } else if (!comp(prio, nodes[index[item]].prio)) {
 increase(item, prio);
 }
 }
 /// \brief Increase the priority of the current item.
 ///
 /// Increase the priority of the current item.
 void increase(const Item& item, const Value& prio) {
 int id = index[item];
 nodes[kd].prio = prio;
 nodes[kd].item = item;
 kd = nodes[kd].parent;
 }
 }
 /// \brief Gives back the minimum priority of the class.
 ///
 /// \return Gives back the minimum priority of the class.
 const Value& classPrio(int cls) const {
 return nodes[~(classes[cls].parent)].prio;
 const Item& classTop(int cls) const {
 return nodes[~(classes[cls].parent)].item;
 }
 /// \brief Gives back a representant item of the class.
 ///
 /// The representant is indpendent from the priorities of the
 /// items.
 /// \return Gives back a representant item of the class.
 const Item& classRep(int id) const {
 int parent = classes[id].parent;
 return nodes[parent >= 0 ? classes[id].depth : leftNode(id)].item;
 }
 class ItemIt {
 private:
 const HeapUnionFind* _huf;
 int _id, _lid;
 public:
 /// \brief Default constructor
 ///
 /// Default constructor
 ItemIt() {}
 ItemIt(const HeapUnionFind& huf, int cls) : _huf(&huf) {
 int id = cls;
 int parent = _huf->classes[id].parent;
 _lid = -1;
 }
 } else {
 _id = _huf->leftNode(id);
 _lid = -1;
 }
 }
 /// \brief Increment operator
 ///
 /// It steps to the next item in the class.
 ItemIt& operator++() {
 _id = _huf->nextNode(_id);
 ///
 /// It converts the iterator to the current item.
 operator const Item&() const {
 return _huf->nodes[_id].item;
 }
 /// \brief Equality operator
 ///
 /// Equality operator
 bool operator==(const ItemIt& i) {
 return i._id == _id;
 }
 /// \brief Inequality operator
 ///
 /// Inequality operator
 bool operator!=(const ItemIt& i) {
 return i._id != _id;
 }
 /// \brief Equality operator
 ///
 /// Equality operator
 bool operator==(Invalid) {
 return _id == _lid;
 }
 /// \brief Inequality operator
 ///
 /// Inequality operator
 bool operator!=(Invalid) {
 return _id != _lid;
 }
 };
 /// \brief Class iterator
 ///
 /// The iterator stores
 class ClassIt {
 private:
 const HeapUnionFind* _huf;
 int _id;
 public:
 ClassIt(const HeapUnionFind& huf)
 : _huf(&huf), _id(huf.first_class) {}
 ClassIt(const HeapUnionFind& huf, int cls)
 : _huf(&huf), _id(huf.classes[cls].left) {}
 ClassIt(Invalid) : _huf(0), _id(-1) {}
 const ClassIt& operator++() {
 _id = _huf->classes[_id].next;
-	return *this;
+return *this;
 }
 /// \brief Equality operator
 ///
 /// Equality operator
 bool operator==(const ClassIt& i) {
 return i._id == _id;
 }
 /// \brief Inequality operator
 ///
 /// Inequality operator
 bool operator!=(const ClassIt& i) {
 return i._id != _id;
 }
 operator int() const {
-	return _id;
+return _id;
 }
 };
 };
 //! @}

changeset 244	c30731a37f91
parent 103	b68a7e348e00
child 220	a5d8c039f218