lemon-0.x: comparison lemon/unionfind.h

equal deleted inserted replaced

-:7840492798a5
+:99776a617e72
 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 size.  Else
+// is root item and it has ~(items[it].parent) component id.  Else
 // the items[it].parent contains the index of the parent.
 //
-// The \c nextItem and \c prevItem provides the double-linked
+// The \c next and \c prev provides the double-linked
-// cyclic list of one component's items. The \c prevClass and
+// cyclic list of one component's items.
-// \c nextClass gives the double linked list of the representant
-// items.
 struct ItemT {
 int parent;
 Item item;
-int nextItem, prevItem;
+int next, prev;
-int nextClass, prevClass;
 };
 std::vector<ItemT> items;
-ItemIntMap& index;
+int firstFreeItem;
-int firstClass;
+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;
 }
 idx = next;
 }
 return k;
 }
-void unlaceClass(int k) {
+int classIndex(int idx) const {
-if (items[k].prevClass != -1) {
+return ~(items[repIndex(idx)].parent);
-items[items[k].prevClass].nextClass = items[k].nextClass;
+}
+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 = items[k].nextClass;
+firstClass = classes[cls].next;
 }
-if (items[k].nextClass != -1) {
+if (classes[cls].next != -1) {
-items[items[k].nextClass].prevClass = items[k].prevClass;
+classes[classes[cls].next].prev = classes[cls].prev;
 }
+classes[cls].next = firstFreeClass;
+firstFreeClass = cls;
 }
-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) {}
+: 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.
 ///
-void insert(const Item& item) {
+int insert(const Item& item) {
-ItemT t;
+int idx = newItem();
-int idx = items.size();
 index.set(item, idx);
-t.nextItem = idx;
+singletonItem(idx);
-t.prevItem = idx;
+items[idx].item = item;
-t.item = item;
-t.parent = -1;
+int cdx = newClass();
-t.nextClass = firstClass;
+items[idx].parent = ~cdx;
-if (firstClass != -1) {
-items[firstClass].prevClass = idx;
+laceClass(cdx);
-}
+classes[cdx].size = 1;
-t.prevClass = -1;
+classes[cdx].firstItem = idx;
-firstClass = idx;
+firstClass = cdx;
-items.push_back(t);
+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, const Item& comp) {
+void insert(const Item& item, int cls) {
-int k = repIndex(index[comp]);
+int rdx = classes[cls].firstItem;
-ItemT t;
+int idx = newItem();
-int idx = items.size();
 index.set(item, idx);
-t.prevItem = k;
+laceItem(idx, rdx);
-t.nextItem = items[k].nextItem;
-items[items[k].nextItem].prevItem = idx;
+items[idx].item = item;
-items[k].nextItem = idx;
+items[idx].parent = rdx;
-t.item = item;
+++classes[~(items[rdx].parent)].size;
-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;
-}
+firstFreeItem = -1;
+}
-/// \brief Finds the leader of the component of the given element.
-///
+/// \brief Finds 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 {
+/// The method returns the component id of the given element.
-return items[repIndex(index[item])].item;
+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 false else returns true.
+/// returns -1 else returns the remaining class.
-bool join(const Item& a, const Item& b) {
+int join(const Item& a, const Item& b) {
 int ak = repIndex(index[a]);
 int bk = repIndex(index[b]);
 if (ak == bk) {
-	return false;
+	return -1;
 }
-if ( items[ak].parent < items[bk].parent ) {
+int acx = ~(items[ak].parent);
-unlaceClass(bk);
+int bcx = ~(items[bk].parent);
-items[ak].parent += 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 {
-unlaceClass(ak);
+	classes[bcx].size += classes[acx].size;
-items[bk].parent += items[ak].parent;
 	items[ak].parent = bk;
+unlaceClass(acx);
+	rcx = bcx;
 }
 spliceItems(ak, bk);
-return true;
+return rcx;
 }
-/// \brief Returns the size of the component of element \e a.
+/// \brief Returns the size of the class.
 ///
-/// Returns the size of the component of element \e a.
+/// Returns the size of the class.
-int size(const Item &item) const {
+int size(int cls) const {
-return - items[repIndex(index[item])].parent;
+return classes[cls].size;
 }
-/// \brief Splits up the component of the element.
+/// \brief Splits up the component.
 ///
-/// Splitting the component of the element into sigleton
+/// Splitting the component into singleton components (component
-/// components (component of size one).
+/// of size one).
-void split(const Item &item) {
+void split(int cls) {
-int k = repIndex(index[item]);
+int fdx = classes[cls].firstItem;
-int idx = items[k].nextItem;
+int idx = items[fdx].next;
-while (idx != k) {
+while (idx != fdx) {
-int next = items[idx].nextItem;
+int next = items[idx].next;
+	singletonItem(idx);
+	int cdx = newClass();
+items[idx].parent = ~cdx;
+	laceClass(cdx);
+	classes[cdx].size = 1;
+	classes[cdx].firstItem = idx;
-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].prev = idx;
-items[idx].prevItem = idx;
+items[idx].next = idx;
-items[idx].nextItem = idx;
+classes[~(items[idx].parent)].size = 1;
-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) {
+/// \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];
-if (rep(idx)) {
+int fdx = items[idx].next;
-int k = idx;
-if (items[k].parent == -1) {
+int cdx = classIndex(idx);
-unlaceClass(idx);
+if (idx == fdx) {
-return;
+	unlaceClass(cdx);
-} else {
+	items[idx].next = firstFreeItem;
-int nk = items[k].nextItem;
+	firstFreeItem = idx;
-if (items[k].prevClass != -1) {
+	return;
-items[items[k].prevClass].nextClass = nk;
+} else {
-} else {
+	classes[cdx].firstItem = fdx;
-firstClass = nk;
+	--classes[cdx].size;
-}
+	items[fdx].parent = ~cdx;
-if (items[k].nextClass != -1) {
-items[items[k].nextClass].prevClass = nk;
+	unlaceItem(idx);
-}
+	idx = items[fdx].next;
+	while (idx != fdx) {
-int l = items[k].nextItem;
+	  items[idx].parent = fdx;
-while (l != k) {
+	  idx = items[idx].next;
-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) {
+void eraseClass(int cls) {
-unlaceClass(repIndex(index[item]));
+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 representant items of the classes.
+/// on the ids of the classes.
 class ClassIt {
 public:
 /// \brief Constructor of the iterator
 ///
 /// Constructor of the iterator
 ClassIt(const UnionFindEnum& ufe) : unionFind(&ufe) {
-idx = unionFind->firstClass;
+cdx = unionFind->firstClass;
 }
 /// \brief Constructor to get invalid iterator
 ///
 /// Constructor to get invalid iterator
-ClassIt(Invalid) : unionFind(0), idx(-1) {}
+ClassIt(Invalid) : unionFind(0), cdx(-1) {}
 /// \brief Increment operator
 ///
 /// It steps to the next representant item.
 ClassIt& operator++() {
-idx = unionFind->items[idx].nextClass;
+cdx = unionFind->classes[cdx].next;
 return *this;
 }
 /// \brief Conversion operator
 ///
 /// It converts the iterator to the current representant item.
-operator const Item&() const {
+operator int() const {
-return unionFind->items[idx].item;
+return cdx;
 }
 /// \brief Equality operator
 ///
 /// Equality operator
 bool operator==(const ClassIt& i) {
-return i.idx == idx;
+return i.cdx == cdx;
 }
 /// \brief Inequality operator
 ///
 /// Inequality operator
 bool operator!=(const ClassIt& i) {
-return i.idx != idx;
+return i.cdx != cdx;
 }
 private:
 const UnionFindEnum* unionFind;
-int idx;
+int cdx;
 };
 /// \brief Lemon style iterator for the items of a component.
 ///
 /// ClassIt is a lemon style iterator for the components. It iterates
 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) {
+ItemIt(const UnionFindEnum& ufe, int cls) : unionFind(&ufe) {
-idx = unionFind->repIndex(unionFind->index[item]);
+fdx = idx = unionFind->classes[cls].firstItem;
 }
 /// \brief Constructor to get invalid iterator
 ///
 /// Constructor to get invalid iterator
 /// \brief Increment operator
 ///
 /// It steps to the next item in the class.
 ItemIt& operator++() {
-idx = unionFind->items[idx].nextItem;
+idx = unionFind->items[idx].next;
-if (unionFind->rep(idx)) idx = -1;
+if (idx == fdx) idx = -1;
 return *this;
 }
 /// \brief Conversion operator
 ///
 return i.idx != idx;
 }
 private:
 const UnionFindEnum* unionFind;
-int idx;
+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;
+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 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;
+};
+};
 //! @}
 } //namespace lemon

changeset 2505	1bb471764ab8
parent 2427	d40c31b08d6f
child 2506	216c6bd5c18c