Molassembler  3.0.0
Molecule graph and conformer library
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Pages
Poset.h
Go to the documentation of this file.
1 
9 #ifndef INCLUDE_TEMPLE_POSET_H
10 #define INCLUDE_TEMPLE_POSET_H
11 
12 #include "boost/logic/tribool.hpp"
13 #include <vector>
14 #include <string>
15 #include <algorithm>
16 #include <stdexcept>
17 
18 namespace Scine {
19 namespace Molassembler {
20 namespace Temple {
21 
43 template<typename T>
44 class Poset {
45 public:
49  struct Subset {
50  using const_iterator = typename std::vector<T>::const_iterator;
51 
52  std::vector<T> values;
53  bool ordered = false;
54 
56  Subset(T value) {
57  values.push_back(std::move(value));
58  }
59 
61  Subset(std::vector<T> passValues) : values(std::move(passValues)) {}
62 
64  template<typename Iter>
65  Subset(Iter begin, Iter end) : values(begin, end) {}
66 
67  const_iterator begin() const {
68  return std::begin(values);
69  }
70 
71  const_iterator end() const {
72  return std::end(values);
73  }
74  };
75 
76  using const_iterator = typename std::vector<Subset>::const_iterator;
77 
82  template<typename Container>
83  Poset(const Container& container) {
85  std::begin(container),
86  std::end(container)
87  );
88  }
89 
94  template<typename Iter>
95  Poset(Iter&& begin, Iter&& end) {
97  std::forward<Iter>(begin),
98  std::forward<Iter>(end)
99  );
100  }
101 
110  template<typename Iter>
111  void setUnorderedValues(Iter&& begin, Iter&& end) {
112  subsets.clear();
113  subsets.emplace_back(std::forward<Iter>(begin), std::forward<Iter>(end));
114  }
115 
127  template<typename Comparator>
128  void orderUnordered(Comparator&& comparator) {
129  auto lowerBoundComparator = [&comparator](const Subset& set, const T& t) -> bool {
130  return comparator(set.values.front(), t);
131  };
132 
133  std::vector<Subset> newSubsets;
134  newSubsets.reserve(subsets.size());
135  for(Subset& subset : subsets) {
136  // If the subset is already ordered, move it to the newSubsets
137  if(subset.ordered) {
138  newSubsets.push_back(std::move(subset));
139  continue;
140  }
141 
142  // Unordered Subsets may split into multiple Subsets
143  std::vector<Subset> splat;
144  for(auto& value : subset) {
145  // Find which Subset this element belongs to using binary search
146  auto findIter = std::lower_bound(
147  std::begin(splat),
148  std::end(splat),
149  value,
150  lowerBoundComparator
151  );
152 
153  if(findIter == std::end(splat)) {
154  // This element does not belong to any existing Subset, so we create one
155  splat.emplace_back(std::move(value));
156  continue;
157  }
158 
159  if(!comparator(value, findIter->values.front())) {
160  // This element belongs to the set pointed to by findIter
161  findIter->values.push_back(std::move(value));
162  continue;
163  }
164 
165  /* Last possibility: This element is part of a new set that should be
166  * inserted before the set pointed to by findIter
167  */
168  splat.emplace(
169  findIter,
170  std::move(value)
171  );
172  }
173 
174  // Finalize single-element sets
175  for(auto& splatSet : splat) {
176  if(splatSet.values.size() == 1) {
177  splatSet.ordered = true;
178  }
179  }
180 
181  // Move the split up sets into the new subsets
182  std::move(
183  std::begin(splat),
184  std::end(splat),
185  std::back_inserter(newSubsets)
186  );
187  }
188 
189  // Overwrite subsets with the new ones
190  subsets = std::move(newSubsets);
191  }
192 
202  void finalize() {
203  for(Subset& subset : subsets) {
204  subset.ordered = true;
205  }
206  }
207 
208  const_iterator begin() const {
209  return std::begin(subsets);
210  }
211 
212  const_iterator end() const {
213  return std::end(subsets);
214  }
215 
220  std::string toString() const {
221  std::string str = "{";
222  for(const Subset& subset : subsets) {
223  auto it = std::begin(subset);
224  while(true) {
225  str += std::to_string(*it);
226  if(++it != std::end(subset)) {
227  str += ", ";
228  } else {
229  str += " | ";
230  break;
231  }
232  }
233  }
234  str += "}";
235 
236  return str;
237  }
238 
250  const_iterator find(const T& a) const {
251  return std::find_if(
252  std::begin(subsets),
253  std::end(subsets),
254  [&a](const Subset& subset) -> bool {
255  return std::find(
256  std::begin(subset),
257  std::end(subset),
258  a
259  ) != std::end(subset);
260  }
261  );
262  }
263 
279  boost::tribool compare(const T& a, const T& b) const {
280  const auto subsetEnd = std::end(subsets);
281  auto aIter = find(a);
282 
283  if(aIter == subsetEnd) {
284  throw std::invalid_argument("The first argument to compare is not in the poset");
285  }
286 
287  auto bIter = find(b);
288 
289  if(bIter == subsetEnd) {
290  throw std::invalid_argument("The second argument to compare is not in the poset");
291  }
292 
293  /* If both elements are not in the same Subset, then they are ordered by
294  * their position in the list of Subsets.
295  */
296  if(aIter != bIter) {
297  return aIter < bIter;
298  }
299 
300  /* So now we know both outer iterators point to the same subset and that
301  * neither of those outer iterators is the end iterator. So we can safely
302  * look at the Subset pointed to by the (matching) outer iterators.
303  *
304  * If the subset is ordered, then the elements are equal. Otherwise, the
305  * order is indeterminate.
306  */
307  if(aIter.first->ordered) {
308  return false;
309  }
310 
311  return boost::indeterminate;
312  }
313 
318  std::vector<
319  std::vector<T>
320  > extract() {
321  const unsigned N = subsets.size();
322  std::vector<
323  std::vector<T>
324  > extracted(N);
325 
326  for(unsigned i = 0; i < N; ++i) {
327  extracted[i] = std::move(subsets[i].values);
328  }
329 
330  subsets.clear();
331  return extracted;
332  }
333 
334 private:
335  std::vector<Subset> subsets;
336 };
337 
338 } // namespace Temple
339 } // namespace Molassembler
340 } // namespace Scine
341 
342 #endif
void orderUnordered(Comparator &&comparator)
Adds order to unordered Subsets.
Definition: Poset.h:128
auto find_if(const Container &container, UnaryPredicate &&predicate)
std::find_if shorthand
Definition: Functional.h:356
Poset(Iter &&begin, Iter &&end)
Range constructor.
Definition: Poset.h:95
Subset(std::vector< T > passValues)
Vector constructor.
Definition: Poset.h:61
void setUnorderedValues(Iter &&begin, Iter &&end)
Sets the values in the specified range as the only unordered Subset.
Definition: Poset.h:111
Poset(const Container &container)
Container constructor.
Definition: Poset.h:83
std::string toString() const
Convert the Poset to a string representation for debug purposes.
Definition: Poset.h:220
Data structure for partially ordered sets with support for gradual ordering discovery.
Definition: Poset.h:44
Subset of T values.
Definition: Poset.h:49
const_iterator find(const T &a) const
Find an element.
Definition: Poset.h:250
Subset(Iter begin, Iter end)
Range constructor.
Definition: Poset.h:65
std::vector< std::vector< T > > extract()
Extracts the contained order, moving from each contained subset and clearing the Poset.
Definition: Poset.h:320
Subset(T value)
Single-value constructor.
Definition: Poset.h:56
void finalize()
Sets all subsets as ordered.
Definition: Poset.h:202
boost::tribool compare(const T &a, const T &b) const
Less-than compare two elements in the poset.
Definition: Poset.h:279
auto find(const Container &container, const T &needle)
std::find shorthand
Definition: Functional.h:346