equal
deleted
inserted
replaced
49 /// cost spanning tree in a graph. |
49 /// cost spanning tree in a graph. |
50 /// \sa kruskal() |
50 /// \sa kruskal() |
51 /// |
51 /// |
52 /// \pre You need to add all the elements by the \ref insert() |
52 /// \pre You need to add all the elements by the \ref insert() |
53 /// method. |
53 /// method. |
54 template <typename _ItemIntMap> |
54 template <typename IM> |
55 class UnionFind { |
55 class UnionFind { |
56 public: |
56 public: |
57 |
57 |
58 typedef _ItemIntMap ItemIntMap; |
58 ///\e |
|
59 typedef IM ItemIntMap; |
|
60 ///\e |
59 typedef typename ItemIntMap::Key Item; |
61 typedef typename ItemIntMap::Key Item; |
60 |
62 |
61 private: |
63 private: |
62 // If the items vector stores negative value for an item then |
64 // If the items vector stores negative value for an item then |
63 // that item is root item and it has -items[it] component size. |
65 // that item is root item and it has -items[it] component size. |
168 /// the find operation uses path compression. |
170 /// the find operation uses path compression. |
169 /// |
171 /// |
170 /// \pre You need to add all the elements by the \ref insert() |
172 /// \pre You need to add all the elements by the \ref insert() |
171 /// method. |
173 /// method. |
172 /// |
174 /// |
173 template <typename _ItemIntMap> |
175 template <typename IM> |
174 class UnionFindEnum { |
176 class UnionFindEnum { |
175 public: |
177 public: |
176 |
178 |
177 typedef _ItemIntMap ItemIntMap; |
179 ///\e |
|
180 typedef IM ItemIntMap; |
|
181 ///\e |
178 typedef typename ItemIntMap::Key Item; |
182 typedef typename ItemIntMap::Key Item; |
179 |
183 |
180 private: |
184 private: |
181 |
185 |
182 ItemIntMap& index; |
186 ItemIntMap& index; |
625 /// component. The data structure is a simplification of the |
629 /// component. The data structure is a simplification of the |
626 /// Union-Find structure, and it does not allow to merge two components. |
630 /// Union-Find structure, and it does not allow to merge two components. |
627 /// |
631 /// |
628 /// \pre You need to add all the elements by the \ref insert() |
632 /// \pre You need to add all the elements by the \ref insert() |
629 /// method. |
633 /// method. |
630 template <typename _ItemIntMap> |
634 template <typename IM> |
631 class ExtendFindEnum { |
635 class ExtendFindEnum { |
632 public: |
636 public: |
633 |
637 |
634 typedef _ItemIntMap ItemIntMap; |
638 ///\e |
|
639 typedef IM ItemIntMap; |
|
640 ///\e |
635 typedef typename ItemIntMap::Key Item; |
641 typedef typename ItemIntMap::Key Item; |
636 |
642 |
637 private: |
643 private: |
638 |
644 |
639 ItemIntMap& index; |
645 ItemIntMap& index; |
946 /// number of joined components or the number of the components |
952 /// number of joined components or the number of the components |
947 /// after the split. |
953 /// after the split. |
948 /// |
954 /// |
949 /// \pre You need to add all the elements by the \ref insert() |
955 /// \pre You need to add all the elements by the \ref insert() |
950 /// method. |
956 /// method. |
951 /// |
957 template <typename V, typename IM, typename Comp = std::less<V> > |
952 template <typename _Value, typename _ItemIntMap, |
|
953 typename _Comp = std::less<_Value> > |
|
954 class HeapUnionFind { |
958 class HeapUnionFind { |
955 public: |
959 public: |
956 |
960 |
957 typedef _Value Value; |
961 ///\e |
958 typedef typename _ItemIntMap::Key Item; |
962 typedef V Value; |
959 |
963 ///\e |
960 typedef _ItemIntMap ItemIntMap; |
964 typedef typename IM::Key Item; |
961 |
965 ///\e |
962 typedef _Comp Comp; |
966 typedef IM ItemIntMap; |
|
967 ///\e |
|
968 typedef Comp Compare; |
963 |
969 |
964 private: |
970 private: |
965 |
971 |
966 static const int cmax = 16; |
972 static const int cmax = 16; |
967 |
973 |
1599 } |
1605 } |
1600 } |
1606 } |
1601 |
1607 |
1602 /// \brief Gives back the priority of the current item. |
1608 /// \brief Gives back the priority of the current item. |
1603 /// |
1609 /// |
1604 /// \return Gives back the priority of the current item. |
1610 /// Gives back the priority of the current item. |
1605 const Value& operator[](const Item& item) const { |
1611 const Value& operator[](const Item& item) const { |
1606 return nodes[index[item]].prio; |
1612 return nodes[index[item]].prio; |
1607 } |
1613 } |
1608 |
1614 |
1609 /// \brief Sets the priority of the current item. |
1615 /// \brief Sets the priority of the current item. |
1644 } |
1650 } |
1645 } |
1651 } |
1646 |
1652 |
1647 /// \brief Gives back the minimum priority of the class. |
1653 /// \brief Gives back the minimum priority of the class. |
1648 /// |
1654 /// |
1649 /// \return Gives back the minimum priority of the class. |
1655 /// Gives back the minimum priority of the class. |
1650 const Value& classPrio(int cls) const { |
1656 const Value& classPrio(int cls) const { |
1651 return nodes[~(classes[cls].parent)].prio; |
1657 return nodes[~(classes[cls].parent)].prio; |
1652 } |
1658 } |
1653 |
1659 |
1654 /// \brief Gives back the minimum priority item of the class. |
1660 /// \brief Gives back the minimum priority item of the class. |
1658 return nodes[~(classes[cls].parent)].item; |
1664 return nodes[~(classes[cls].parent)].item; |
1659 } |
1665 } |
1660 |
1666 |
1661 /// \brief Gives back a representant item of the class. |
1667 /// \brief Gives back a representant item of the class. |
1662 /// |
1668 /// |
|
1669 /// Gives back a representant item of the class. |
1663 /// The representant is indpendent from the priorities of the |
1670 /// The representant is indpendent from the priorities of the |
1664 /// items. |
1671 /// items. |
1665 /// \return Gives back a representant item of the class. |
|
1666 const Item& classRep(int id) const { |
1672 const Item& classRep(int id) const { |
1667 int parent = classes[id].parent; |
1673 int parent = classes[id].parent; |
1668 return nodes[parent >= 0 ? classes[id].depth : leftNode(id)].item; |
1674 return nodes[parent >= 0 ? classes[id].depth : leftNode(id)].item; |
1669 } |
1675 } |
1670 |
1676 |