7#include <unordered_map>
8#include <unordered_set>
30template <
class T>
class Vector :
public std::vector<T>
32 using Base = std::vector<T>;
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(); }
69 Vector mid(std::ptrdiff_t at, std::ptrdiff_t count = -1)
const
71 auto end = count < 0 ? this->
size() : std::min(this->
size(), at + count);
72 return {this->begin() + at, this->begin() + end};
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()); }
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)); }
126 T result = std::move(this->back());
138 T result = std::move(this->front());
139 this->erase(this->begin());
148 void removeAt(
int at) { this->erase(this->begin() + at); }
153 void fill(
const T &v) { std::fill(this->begin(), this->end(), v); }
167 return std::find(this->begin(), this->end(), v) != this->end();
174template <
class K>
struct Hash : std::hash<K> {
186template <
class A,
class B>
struct Hash<std::pair<A, B>> {
195 return a ^ (b + std::size_t(0x9e3779b97f4a7c15ull) + (a << 6) + (a >> 2));
210template <
class K,
class V>
class Map
212 using Base = std::unordered_map<K, V, Hash<K>>;
225 std::conditional_t<Const, typename Base::const_iterator, typename Base::iterator>;
238 decltype(
auto)
value()
const {
return (it_->second); }
240 const K &
key()
const {
return it_->first; }
242 decltype(
auto)
operator*()
const {
return (it_->second); }
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(); }
301 bool remove(
const K &k) {
return data_.erase(k) != 0; }
315 V
value(
const K &k,
const V &fallback = V{})
const
317 auto it = data_.find(k);
318 return it == data_.end() ? fallback : it->second;
358 std::unordered_map<K, Vector<V>,
Hash<K>> data_;
367 void remove(
const K &key) { data_.erase(key); }
373 void insert(
const K &key,
const V &value)
375 auto &
values = data_[key];
386 auto it = data_.find(key);
387 return it != data_.end() && it->second.contains(value);
396 auto it = data_.find(key);
397 return it == data_.end() ?
Vector<V>{} : it->second;
404template <
class K>
class Set :
public std::unordered_set<K, Hash<K>>
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(); }
451 return "cdt: non-finite input point " + std::to_string(i);
500 std::chrono::steady_clock::time_point start_;
504 void start() { start_ = std::chrono::steady_clock::now(); }
512 return std::chrono::duration_cast<std::chrono::nanoseconds>(
513 std::chrono::steady_clock::now() - start_)
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