Mercurial > hg > orthanc-stone

annotate Framework/Toolbox/DisjointDataSet.h @ 1327:4f8db2d202c8 broker

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
OrthancSeriesProgressiveLoader now has two modes that can be selected at object creation : - progressive (will first load jpeg50, then jpeg90 then PAM) - non-progressive (will directly load PAM (uncompressed)) Please note that the slice loading order remains dynamic and depending upon the slice that the client code wishes to extract from the volume.
author Benjamin Golinvaux <bgo@osimis.io>
date Wed, 25 Mar 2020 14:34:27 +0100
parents 2d8ab34c8c91
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
1005
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
1 /**
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
2 * Stone of Orthanc
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
3 * Copyright (C) 2012-2016 Sebastien Jodogne, Medical Physics
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
4 * Department, University Hospital of Liege, Belgium
1270
2d8ab34c8c91 upgrade to year 2020
Sebastien Jodogne <s.jodogne@gmail.com>
parents: 1018
diff changeset
5 * Copyright (C) 2017-2020 Osimis S.A., Belgium
1005
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
6 *
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
7 * This program is free software: you can redistribute it and/or
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
8 * modify it under the terms of the GNU Affero General Public License
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
9 * as published by the Free Software Foundation, either version 3 of
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
10 * the License, or (at your option) any later version.
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
11 *
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
12 * This program is distributed in the hope that it will be useful, but
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
13 * WITHOUT ANY WARRANTY; without even the implied warranty of
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
15 * Affero General Public License for more details.
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
16 *
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
17 * You should have received a copy of the GNU Affero General Public License
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
18 * along with this program. If not, see <http://www.gnu.org/licenses/>.
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
19 **/
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
20
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
21 #pragma once
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
22
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
23 #include <vector>
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
24
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
25 #include "../StoneException.h"
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
26
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
27 namespace OrthancStone
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
28 {
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
29 class DisjointDataSet
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
30 {
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
31 public:
1018
58eed6bbcabb fix warnings
Sebastien Jodogne <s.jodogne@gmail.com>
parents: 1005
diff changeset
32 DisjointDataSet(size_t itemCount) :
58eed6bbcabb fix warnings
Sebastien Jodogne <s.jodogne@gmail.com>
parents: 1005
diff changeset
33 parents_(itemCount),
58eed6bbcabb fix warnings
Sebastien Jodogne <s.jodogne@gmail.com>
parents: 1005
diff changeset
34 ranks_(itemCount)
1005
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
35 {
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
36 for (size_t index = 0; index < parents_.size(); index++)
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
37 {
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
38 SetParent(index,index);
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
39 ranks_[index] = 1;
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
40 }
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
41 }
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
42
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
43 size_t Find(size_t item)
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
44 {
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
45 /*
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
46 If parents_[i] == i, it means i is representative of a set.
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
47 Otherwise, we go up the tree...
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
48 */
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
49 if (GetParent(item) != item)
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
50 {
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
51 // if item is not a top item (representative of its set),
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
52 // we use path compression to improve future lookups
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
53 // see: https://en.wikipedia.org/wiki/Disjoint-set_data_structure#Path_compression
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
54 SetParent(item, Find(parents_[item]));
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
55 }
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
56
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
57 // now that paths have been compressed, we are positively certain
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
58 // that item's parent is a set ("X is a set" means that X is the
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
59 // representative of a set)
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
60 return GetParent(item);
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
61 }
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
62
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
63 /*
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
64 This merge the two sets that contains itemA and itemB
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
65 */
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
66 void Union(size_t itemA, size_t itemB)
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
67 {
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
68 // Find current sets of x and y
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
69 size_t setA = Find(itemA);
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
70 size_t setB = Find(itemB);
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
71
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
72 // if setA == setB, it means they are already in the same set and
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
73 // do not need to be merged!
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
74 if (setA != setB)
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
75 {
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
76 // we need to merge the sets, which means that the trees representing
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
77 // the sets needs to be merged (there must be a single top parent to
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
78 // all the items originally belonging to setA and setB must be the same)
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
79
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
80 // since the algorithm speed is inversely proportional to the tree
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
81 // height (the rank), we need to combine trees in a way that
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
82 // minimizes this rank. See "Union by rank" at
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
83 // https://en.wikipedia.org/wiki/Disjoint-set_data_structure#by_rank
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
84 if (GetRank(setA) < GetRank(setB))
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
85 {
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
86 SetParent(setA, setB);
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
87 }
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
88 else if (GetRank(setA) > GetRank(setB))
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
89 {
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
90 SetParent(setB, setA);
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
91 }
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
92 else
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
93 {
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
94 SetParent(setB, setA);
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
95 BumpRank(setA);
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
96 // the trees had the same height but we attached the whole of setB
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
97 // under setA (under its parent), so the resulting tree is now
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
98 // 1 higher. setB is NOT representative of a set anymore.
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
99 }
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
100 }
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
101 }
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
102
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
103 private:
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
104 size_t GetRank(size_t i) const
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
105 {
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
106 ORTHANC_ASSERT(i < ranks_.size());
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
107 ORTHANC_ASSERT(ranks_.size() == parents_.size());
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
108 return ranks_[i];
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
109 }
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
110
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
111 size_t GetParent(size_t i) const
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
112 {
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
113 ORTHANC_ASSERT(i < parents_.size());
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
114 ORTHANC_ASSERT(ranks_.size() == parents_.size());
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
115 return parents_[i];
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
116 }
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
117
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
118 void SetParent(size_t i, size_t parent)
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
119 {
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
120 ORTHANC_ASSERT(i < parents_.size());
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
121 ORTHANC_ASSERT(ranks_.size() == parents_.size());
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
122 parents_[i] = parent;
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
123 }
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
124
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
125 void BumpRank(size_t i)
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
126 {
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
127 ORTHANC_ASSERT(i < ranks_.size());
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
128 ORTHANC_ASSERT(ranks_.size() == parents_.size());
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
129 ranks_[i] = ranks_[i] + 1u;
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
130 }
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
131
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
132 /*
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
133 This vector contains the direct parent of each item
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
134 */
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
135 std::vector<size_t> parents_;
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
136
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
137 /*
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
138 This vector contains the tree height of each set. The values in the
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
139 vector for non-representative items is UNDEFINED!
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
140 */
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
141 std::vector<size_t> ranks_;
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
142 };
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
143
7e861cfd142d Added a union find class (on integers) called DisjointDataSet
Benjamin Golinvaux <bgo@osimis.io>
parents:
diff changeset
144 }