Loading...
Searching...
No Matches
storage.hpp
Go to the documentation of this file.
1// SPDX-License-Identifier: Apache-2.0
2#pragma once
4#include <algorithm>
5#include <chrono>
6#include <string>
7#include <unordered_map>
8#include <unordered_set>
9#include <utility>
10#include <vector>
11
12namespace meshkit::detail
13{
14// Small internal storage vocabulary: QVector-style containers behind the standard kernel
15// specialization (StandardStorage) and the plan model. The Qt specialization (QtStorage)
16// supplies QVector/QHash/QSet with the same member names instead. Public jobs own ordinary
17// standard C++ arrays. No GUI mirror or per-access conversion of the kernel's
18// multi-million-entry buffers.
30template <class T> class Vector : public std::vector<T>
31{
32 using Base = std::vector<T>;
33
34public:
35 using Base::Base;
37 Vector() = default;
42 Vector(const std::vector<T> &v) : Base(v) {};
47 Vector(std::vector<T> &&v) : Base(std::move(v)) {}
49 decltype(auto) first() { return this->front(); }
51 decltype(auto) first() const { return this->front(); }
53 decltype(auto) last() { return this->back(); }
55 decltype(auto) last() const { return this->back(); }
60 const T *constData() const { return this->data(); }
69 Vector mid(std::ptrdiff_t at, std::ptrdiff_t count = -1) const
70 {
71 auto end = count < 0 ? this->size() : std::min(this->size(), at + count);
72 return {this->begin() + at, this->begin() + end};
73 }
74
78 void prepend(const T &v) { this->insert(this->begin(), v); }
84 void append(const Vector &v) { this->insert(this->end(), v.begin(), v.end()); }
91 {
92 append(v);
93 return *this;
94 }
95
100 Vector &operator<<(const T &v)
101 {
102 append(v);
103 return *this;
104 }
105
107 std::ptrdiff_t size() const noexcept { return static_cast<std::ptrdiff_t>(Base::size()); }
109 bool isEmpty() const { return this->empty(); }
114 void append(const T &v) { this->push_back(v); }
119 void append(T &&v) { this->push_back(std::move(v)); }
125 {
126 T result = std::move(this->back());
127 this->pop_back();
128 return result;
129 }
130
137 {
138 T result = std::move(this->front());
139 this->erase(this->begin());
140 return result;
141 }
142
143 void removeLast() { this->pop_back(); }
148 void removeAt(int at) { this->erase(this->begin() + at); }
153 void fill(const T &v) { std::fill(this->begin(), this->end(), v); }
159 void fill(const T &v, std::size_t size) { this->assign(size, v); }
165 bool contains(const T &v) const
166 {
167 return std::find(this->begin(), this->end(), v) != this->end();
168 }
169};
170
174template <class K> struct Hash : std::hash<K> {
175};
176
186template <class A, class B> struct Hash<std::pair<A, B>> {
192 std::size_t operator()(const std::pair<A, B> &p) const
193 {
194 const auto a = Hash<A>{}(p.first), b = Hash<B>{}(p.second);
195 return a ^ (b + std::size_t(0x9e3779b97f4a7c15ull) + (a << 6) + (a >> 2));
196 }
197};
198
210template <class K, class V> class Map
211{
212 using Base = std::unordered_map<K, V, Hash<K>>;
213 Base data_;
214
215public:
222 template <bool Const> class Iterator
223 {
224 using It =
225 std::conditional_t<Const, typename Base::const_iterator, typename Base::iterator>;
226 It it_;
227
228 public:
233 explicit Iterator(It it) : it_(it) {}
238 decltype(auto) value() const { return (it_->second); }
240 const K &key() const { return it_->first; }
242 decltype(auto) operator*() const { return (it_->second); }
244 auto operator->() const { return &it_->second; }
250 {
251 ++it_;
252 return *this;
253 }
254
259 bool operator==(const Iterator &b) const { return it_ == b.it_; }
265 bool operator!=(const Iterator &b) const { return it_ != b.it_; }
266 };
270 void clear() { data_.clear(); }
275 void reserve(std::size_t n) { data_.reserve(n); }
277 bool isEmpty() const { return data_.empty(); }
279 std::ptrdiff_t size() const { return data_.size(); }
285 bool contains(const K &k) const { return data_.find(k) != data_.end(); }
292 MutableIterator insert(const K &k, const V &v)
293 {
294 return MutableIterator(data_.insert_or_assign(k, v).first);
295 }
296
301 bool remove(const K &k) { return data_.erase(k) != 0; }
308 V &operator[](const K &k) { return data_[k]; }
315 V value(const K &k, const V &fallback = V{}) const
316 {
317 auto it = data_.find(k);
318 return it == data_.end() ? fallback : it->second;
319 }
320
325 MutableIterator find(const K &k) { return MutableIterator(data_.find(k)); }
327 MutableIterator begin() { return MutableIterator(data_.begin()); }
329 MutableIterator end() { return MutableIterator(data_.end()); }
335 ConstIterator constFind(const K &k) const { return ConstIterator(data_.find(k)); }
337 ConstIterator constEnd() const { return ConstIterator(data_.end()); }
339 ConstIterator cbegin() const { return ConstIterator(data_.cbegin()); }
341 ConstIterator cend() const { return ConstIterator(data_.cend()); }
343 ConstIterator begin() const { return cbegin(); }
345 ConstIterator end() const { return cend(); }
346};
347
356template <class K, class V> class MultiMap
357{
358 std::unordered_map<K, Vector<V>, Hash<K>> data_;
359
360public:
362 void clear() { data_.clear(); }
367 void remove(const K &key) { data_.erase(key); }
373 void insert(const K &key, const V &value)
374 {
375 auto &values = data_[key];
376 values.insert(values.begin(), value);
377 }
378
384 bool contains(const K &key, const V &value) const
385 {
386 auto it = data_.find(key);
387 return it != data_.end() && it->second.contains(value);
388 }
389
394 Vector<V> values(const K &key) const
395 {
396 auto it = data_.find(key);
397 return it == data_.end() ? Vector<V>{} : it->second;
398 }
399};
400
404template <class K> class Set : public std::unordered_set<K, Hash<K>>
405{
406public:
412 bool remove(const K &k) { return this->erase(k) != 0; }
414 bool isEmpty() const { return this->empty(); }
420 bool contains(const K &key) const { return this->find(key) != this->end(); }
421};
422
430 using Point = Point2;
431 using Box = Box2;
432 using String = std::string;
433 using PointInput = std::vector<Point2>;
434 template <class T> using Vector = detail::Vector<T>;
435 template <class K, class V> using Hash = Map<K, V>;
436 template <class K, class V> using MultiHash = MultiMap<K, V>;
437 template <class K> using Set = detail::Set<K>;
443 static String message(const char *s) { return s; }
450 {
451 return "cdt: non-finite input point " + std::to_string(i);
452 }
453};
454
464template <class F> class ScopeExit
465{
466 F f_;
467
468public:
474 explicit ScopeExit(F f) : f_(std::move(f)) {}
476 ~ScopeExit() { f_(); }
478 ScopeExit(const ScopeExit &) = delete;
479};
480
489template <class F> ScopeExit<F> scopeExit(F f)
490{
491 return ScopeExit<F>(std::move(f));
492}
493
498class Timer
499{
500 std::chrono::steady_clock::time_point start_;
501
502public:
504 void start() { start_ = std::chrono::steady_clock::now(); }
510 std::int64_t nsecsElapsed() const
511 {
512 return std::chrono::duration_cast<std::chrono::nanoseconds>(
513 std::chrono::steady_clock::now() - start_)
514 .count();
515 }
516};
517}
Axis-aligned rectangle in the XY plane, stored as an origin corner and a signed size.
Definition geometry.hpp:167
Point or displacement vector in the horizontal (XY) plane.
Definition geometry.hpp:21
Forward iterator over a Map whose dereference yields the mapped value.
Definition storage.hpp:223
auto operator->() const
Pointer to the mapped value (not to a key/value pair).
Definition storage.hpp:244
bool operator==(const Iterator &b) const
Position equality.
Definition storage.hpp:259
const K & key() const
Key at this position; must not be called on an end iterator.
Definition storage.hpp:240
bool operator!=(const Iterator &b) const
Position inequality.
Definition storage.hpp:265
Iterator & operator++()
Advance to the next entry.
Definition storage.hpp:249
Iterator(It it)
Wrap an underlying std::unordered_map iterator.
Definition storage.hpp:233
decltype(auto) value() const
Mapped value at this position: V & for MutableIterator, const V & for ConstIterator.
Definition storage.hpp:238
Hash map with the QHash-style API the CDT kernel uses, over std::unordered_map<K, V,...
Definition storage.hpp:211
MutableIterator end()
Mutable past-the-end iterator.
Definition storage.hpp:329
ConstIterator constFind(const K &k) const
Read-only iterator to the entry for k.
Definition storage.hpp:335
V value(const K &k, const V &fallback=V{}) const
Copy of the value for k, without inserting.
Definition storage.hpp:315
V & operator[](const K &k)
Modifiable value for k, inserting a value-initialized V{} first when absent.
Definition storage.hpp:308
bool contains(const K &k) const
Key lookup.
Definition storage.hpp:285
Iterator< true > ConstIterator
Read-only iterator; value() is const V &.
Definition storage.hpp:267
Iterator< false > MutableIterator
Iterator whose value() is a modifiable V &.
Definition storage.hpp:268
bool isEmpty() const
True when the map has no entries.
Definition storage.hpp:277
bool remove(const K &k)
Erase the entry for k.
Definition storage.hpp:301
ConstIterator constEnd() const
Read-only past-the-end iterator, to compare with constFind() results.
Definition storage.hpp:337
MutableIterator find(const K &k)
Mutable iterator to the entry for k.
Definition storage.hpp:325
ConstIterator cbegin() const
Read-only iterator to the first entry (order unspecified).
Definition storage.hpp:339
ConstIterator begin() const
Read-only iterator to the first entry; same as cbegin().
Definition storage.hpp:343
void clear()
Remove all entries.
Definition storage.hpp:270
std::ptrdiff_t size() const
Number of entries, as a signed count.
Definition storage.hpp:279
void reserve(std::size_t n)
Prepare buckets for at least n entries (std::unordered_map::reserve).
Definition storage.hpp:275
ConstIterator end() const
Read-only past-the-end iterator; same as cend().
Definition storage.hpp:345
ConstIterator cend() const
Read-only past-the-end iterator.
Definition storage.hpp:341
MutableIterator insert(const K &k, const V &v)
Store v under k, overwriting any existing value (insert_or_assign).
Definition storage.hpp:292
MutableIterator begin()
Mutable iterator to the first entry (order unspecified).
Definition storage.hpp:327
Multi-valued hash map with the QMultiHash subset the CDT kernel uses.
Definition storage.hpp:357
bool contains(const K &key, const V &value) const
Key/value lookup by linear search of the key's values.
Definition storage.hpp:384
void clear()
Remove all keys and values.
Definition storage.hpp:362
void remove(const K &key)
Remove every value stored under key.
Definition storage.hpp:367
void insert(const K &key, const V &value)
Add value under key, ahead of the values already there.
Definition storage.hpp:373
Vector< V > values(const K &key) const
Copy of the values under key, most recently inserted first.
Definition storage.hpp:394
Scope guard that calls a callable when it is destroyed.
Definition storage.hpp:465
ScopeExit(F f)
Store the callable.
Definition storage.hpp:474
ScopeExit(const ScopeExit &)=delete
Not copyable (and therefore not movable).
~ScopeExit()
Invoke the stored callable.
Definition storage.hpp:476
std::unordered_set<K, Hash<K>> with the QSet-style names the CDT kernel uses.
Definition storage.hpp:405
bool isEmpty() const
True when the set has no elements.
Definition storage.hpp:414
bool contains(const K &key) const
Membership test.
Definition storage.hpp:420
bool remove(const K &k)
Erase k.
Definition storage.hpp:412
Minimal std::chrono::steady_clock stopwatch with QElapsedTimer-style names.
Definition storage.hpp:499
std::int64_t nsecsElapsed() const
Time since the last start().
Definition storage.hpp:510
void start()
Record the current steady_clock time as the reference; call again to restart.
Definition storage.hpp:504
std::vector<T> with the QVector-style member names the CDT kernel and plan model use.
Definition storage.hpp:31
decltype(auto) last() const
Read-only reference to the last element; the vector must not be empty.
Definition storage.hpp:55
void prepend(const T &v)
Insert a copy of v before the first element; linear in size().
Definition storage.hpp:78
T takeFirst()
Remove the first element and return it by move; linear in size().
Definition storage.hpp:136
void removeAt(int at)
Erase one element; the elements after it shift down by one.
Definition storage.hpp:148
void append(T &&v)
Append v by move (push_back).
Definition storage.hpp:119
void removeLast()
Remove the last element (pop_back); the vector must not be empty.
Definition storage.hpp:143
decltype(auto) first() const
Read-only reference to the first element; the vector must not be empty.
Definition storage.hpp:51
Vector(std::vector< T > &&v)
Take over the buffer of a std::vector without copying elements.
Definition storage.hpp:47
void fill(const T &v)
Assign v to every existing element; the size is unchanged.
Definition storage.hpp:153
Vector & operator<<(const T &v)
Append one element.
Definition storage.hpp:100
bool isEmpty() const
True when the vector holds no elements.
Definition storage.hpp:109
bool contains(const T &v) const
Linear search with operator==.
Definition storage.hpp:165
void fill(const T &v, std::size_t size)
Replace the contents with size copies of v (assign()).
Definition storage.hpp:159
Vector mid(std::ptrdiff_t at, std::ptrdiff_t count=-1) const
Copy of a contiguous run of elements.
Definition storage.hpp:69
void append(const Vector &v)
Append copies of all elements of v.
Definition storage.hpp:84
const T * constData() const
Read-only pointer to the contiguous elements (data()).
Definition storage.hpp:60
Vector(const std::vector< T > &v)
Copy the elements of a std::vector.
Definition storage.hpp:42
std::ptrdiff_t size() const noexcept
Number of elements as a signed std::ptrdiff_t.
Definition storage.hpp:107
T takeLast()
Remove the last element and return it by move; the vector must not be empty.
Definition storage.hpp:124
void append(const T &v)
Append a copy of v (push_back).
Definition storage.hpp:114
decltype(auto) last()
Reference to the last element (back()); the vector must not be empty.
Definition storage.hpp:53
Vector & operator+=(const Vector &v)
Append copies of all elements of v; same as append(const Vector &).
Definition storage.hpp:90
decltype(auto) first()
Reference to the first element (front()); the vector must not be empty.
Definition storage.hpp:49
Vector()=default
Empty vector.
Storage policies and containers for the constrained Delaunay kernel and the plan model: StandardStora...
ScopeExit< F > scopeExit(F f)
Make a ScopeExit guard for f.
Definition storage.hpp:489
std::size_t operator()(const std::pair< A, B > &p) const
Hash a pair.
Definition storage.hpp:192
Hash functor of Map, MultiMap and Set; the primary template is std::hash<K>.
Definition storage.hpp:174
Storage policy that instantiates BasicConstrainedDelaunay on standard C++ types.
Definition storage.hpp:429
static String message(const char *s)
Convert a fixed message to String.
Definition storage.hpp:443
MultiMap< K, V > MultiHash
Multi-valued hash map.
Definition storage.hpp:436
static String invalidPointMessage(int i)
Error text for a non-finite input point.
Definition storage.hpp:449
Map< K, V > Hash
Hash map.
Definition storage.hpp:435
Box2 Box
Axis-aligned box type.
Definition storage.hpp:431
detail::Set< K > Set
Hash set.
Definition storage.hpp:437
std::string String
Error message type (errorMsg()).
Definition storage.hpp:432
detail::Vector< T > Vector
Sequence container.
Definition storage.hpp:434
std::vector< Point2 > PointInput
Input point array type taken by build().
Definition storage.hpp:433
Point2 Point
Vertex and input point type (XY units).
Definition storage.hpp:430