Simulant  21.09-46
A portable game engine for Windows, OSX, Linux, Dreamcast, and PSP
contiguous_map.h
1 #pragma once
2 
3 /*
4  * ContiguousMap<T> is a container with the following properties:
5  *
6  * - Sorted on insertion
7  * - Clears without dealloc
8  * - Nodes stored in contiguous memory
9  *
10  * Internally it's a simple binary search tree that's stored
11  * in a vector. Ideally it would be a red-black tree to
12  * balance it. FUTURE IMPROVEMENT IF ANYONE WANTS TO PICK IT UP!
13  */
14 
15 
16 #include <vector>
17 #include <utility>
18 #include <cstdint>
19 #include <cassert>
20 #include <stdexcept>
21 
22 namespace smlt {
23 
24 namespace _contiguous_map {
25 
26 template<typename K, typename V>
27 struct NodeMeta {
28  NodeMeta(const K& key, const V& value):
29  pair(std::make_pair(key, value)) {}
30 
31  std::pair<const K, V> pair;
32 
33  bool is_black = false;
34 
35  /* If this is not -1, then this is the start
36  * of a linked list of equal values */
37  int32_t equal_index_ = -1;
38  int32_t last_equal_index_ = -1;
39 
40  int32_t parent_index_ = -1;
41  int32_t left_index_ = -1;
42  int32_t right_index_ = -1;
43 } __attribute__((aligned(8)));
44 
45 }
46 
47 template<typename T>
49 public:
50  enum Result : int8_t {
51  RESULT_LESS = -1,
52  RESULT_EQUAL = 0,
53  RESULT_GREATER = 1
54  };
55 
56  Result operator()(const T& a, const T& b) const {
57  return (a < b) ? RESULT_LESS : (b < a) ? RESULT_GREATER : RESULT_EQUAL;
58  }
59 };
60 
61 
62 template<typename K, typename V, typename Compare=ThreeWayCompare<K>>
64 public:
65  typedef K key_type;
66  typedef V value_type;
68 
69  class iterator_base {
70  protected:
71  /* This is the equivalent of begin */
73  map_(map) {
74 
75  current_node_ = map->root_index_;
76 
77  while(current_node_ > -1 && _node(current_node_)->left_index_ > -1) {
78  current_node_ = _node(current_node_)->left_index_;
79  }
80  }
81 
82  /* Passing -1 means end(), anything else points to the specified node */
83  iterator_base(ContiguousMultiMap* map, int32_t index):
84  map_(map) {
85 
86  current_node_ = index;
87 
88  if(index > -1) {
89  auto current = _node(current_node_);
90  if(current->left_index_ > -1) {
91  previous_node_index_ = current->left_index_;
92  }
93  } else {
94  previous_node_index_ = -1;
95  }
96  }
97 
98  iterator_base(const iterator_base& other) = default;
99 
100  inline typename ContiguousMultiMap::node_type* _node(int32_t index) const {
101  assert(index > -1);
102  return &map_->nodes_[index];
103  }
104 
105  void increment() {
106  if(current_node_ < 0) return; // Do nothing
107 
108  auto current = _node(current_node_);
109 
110  /* We have a pointer to an equal value node, but we haven't started iterating */
111  if(current->equal_index_ > -1 && list_head_index_ == -1) {
112  list_head_index_ = current_node_;
113  current_node_ = current->equal_index_;
114  return;
115  } else if(list_head_index_ > -1) {
116  /* We're iterating equal value nodes */
117  current_node_ = current->equal_index_;
118  if(current_node_ == -1) {
119  /* We've finished iterating the list, now back to recursing */
120  current_node_ = list_head_index_; // Restore back to the head node
121  list_head_index_ = -1; // We're no longer iterating the list
122  current = _node(current_node_); // Set current so we can continue normally
123  } else {
124  /* We've updated the current node */
125  return;
126  }
127  }
128 
129  auto previous = current_node_;
130 
131  if(current->right_index_ == -1) {
132  /* We've reached the end, now we go up until we come from
133  * the left branch */
134 
135  current_node_ = current->parent_index_;
136  while(current_node_ > -1) {
137  current = _node(current_node_);
138  if(previous == current->left_index_) {
139  /* We came from the left, so break */
140  break;
141  } else {
142  previous = current_node_;
143  current_node_ = current->parent_index_;
144  }
145  }
146 
147  } else {
148  current_node_ = current->right_index_;
149  if(current_node_ > -1) {
150  /* Go down the left branch to start iterating this one */
151  current = _node(current_node_);
152  while(current->left_index_ > -1) {
153  current_node_ = current->left_index_;
154  current = _node(current_node_);
155  }
156  }
157  }
158 
159  previous_node_index_ = previous;
160  }
161 
162  bool is_equal(const iterator_base& other) const {
163  return (
164  map_ == other.map_ &&
165  current_node_ == other.current_node_
166  );
167  }
168 
169  int32_t current_node_ = -1;
170 
171  private:
172  ContiguousMultiMap* map_ = nullptr;
173 
174  int32_t list_head_index_ = -1;
175  int32_t previous_node_index_ = -1;
176  };
177 
178  class iterator : private iterator_base {
179  private:
181  iterator_base(map) {}
182 
183  iterator(ContiguousMultiMap* map, int32_t index):
184  iterator_base(map, index) {}
185 
186  public:
187  friend class ContiguousMultiMap;
188 
189  using iterator_category = std::forward_iterator_tag;
190  using value_type = std::pair<const K, V>;
191  using difference_type = uint32_t;
192  using pointer = std::pair<const K, V>*;
193  using reference = std::pair<const K, V>&;
194 
195  iterator(const iterator& other) = default;
196  iterator& operator=(const iterator&) = default;
197  iterator& operator=(iterator&&) = default;
198 
199  iterator& operator++() {
200  this->increment();
201  return *this;
202  }
203 
204  bool operator==(const iterator& other) const {
205  return this->is_equal(other);
206  }
207 
208  bool operator!=(const iterator& other) const {
209  return !this->is_equal(other);
210  }
211 
212  reference operator*() const {
213  return this->_node(this->current_node_)->pair;
214  }
215 
216  pointer operator->() const {
217  return &this->_node(this->current_node_)->pair;
218  }
219  };
220 
221  class const_iterator : private iterator_base {
222  private:
223  friend class ContiguousMultiMap;
224 
226  iterator_base(map) {}
227 
228  const_iterator(ContiguousMultiMap* map, int32_t index):
229  iterator_base(map, index) {}
230 
231  public:
232 
233  using iterator_category = std::forward_iterator_tag;
234  using value_type = std::pair<const K, V>;
235  using difference_type = uint32_t;
236  using pointer = const std::pair<const K, V>*;
237  using reference = const std::pair<const K, V>&;
238 
239  const_iterator(const const_iterator& other) = default;
240  const_iterator& operator=(const const_iterator&) = default;
241  const_iterator& operator=(const_iterator&&) = default;
242 
243  const_iterator& operator++() {
244  this->increment();
245  return *this;
246  }
247 
248  bool operator==(const const_iterator& other) const {
249  return this->is_equal(other);
250  }
251 
252  bool operator!=(const const_iterator& other) const {
253  return !this->is_equal(other);
254  }
255 
256  reference operator*() const {
257  return this->_node(this->current_node_)->pair;
258  }
259 
260  pointer operator->() const {
261  return &this->_node(this->current_node_)->pair;
262  }
263  };
264 
265  ContiguousMultiMap() = default;
266 
267  ContiguousMultiMap(std::size_t reserve_count):
268  root_index_(-1) {
269  nodes_.reserve(reserve_count);
270  }
271 
272  ContiguousMultiMap(const ContiguousMultiMap&) = delete; // Avoid copies for now, slow!
273  ContiguousMultiMap& operator=(const ContiguousMultiMap&) = delete;
274 
275  bool insert(const K& key, V&& element) {
276  K k = key; // Copy K to leverage the move of _insert
277  return _insert(std::move(k), std::move(element));
278  }
279 
280  bool insert(const K& key, const V& element) {
281  K k = key;
282  V v = element;
283  return _insert(std::move(k), std::move(v));
284  }
285 
286  void clear() {
287  nodes_.clear();
288  root_index_ = -1;
289  }
290 
291  void shrink_to_fit() {
292  nodes_.shrink_to_fit();
293  }
294 
295  std::size_t size() const {
296  return nodes_.size();
297  }
298 
299  void reserve(std::size_t size) {
300  nodes_.reserve(size);
301  }
302 
303  bool empty() const {
304  return nodes_.empty();
305  }
306 
307  iterator find(const K& key) {
308  int32_t index = _find(key);
309  if(index == -1) {
310  return end();
311  }
312  return iterator(this, index);
313  }
314 
315  const_iterator find(const K &key) const {
316  int32_t index = _find(key);
317  if(index == -1) {
318  return end();
319  }
320 
321  return const_iterator(
322  const_cast<ContiguousMultiMap*>(this),
323  index
324  );
325  }
326 
327  const_iterator upper_bound(const K& key) const {
328  auto it = find(key);
329 
330  while(it != end() && it->first == key) {
331  ++it;
332  }
333 
334  return it;
335  }
336 
337  iterator begin() {
338  return iterator(this);
339  }
340 
341  iterator end() {
342  return end_;
343  }
344 
345  const_iterator begin() const {
346  return const_iterator(
347  const_cast<ContiguousMultiMap*>(this)
348  );
349  }
350 
351  const_iterator end() const {
352  return cend_;
353  }
354 
355  /* This is a helper function for debugging the contiguousmap.
356  * Given a path of L or R characters, returns the key at that path
357  * or throws an error if the path is invalid */
358 
359  const K& path_key(const std::string& path) const {
360  const node_type* node = &nodes_[root_index_];
361 
362  for(auto c: path) {
363  if(c == 'L') {
364  if(node->left_index_ == -1) {
365  throw std::logic_error("Hit end of branch");
366  }
367  node = &nodes_[node->left_index_];
368  } else if(c == 'R') {
369  if(node->right_index_ == -1) {
370  throw std::logic_error("Hit end of branch");
371  }
372  node = &nodes_[node->right_index_];
373  } else {
374  throw std::logic_error("Invalid path");
375  }
376  }
377 
378  /* Return the key */
379  return node->pair.first;
380  }
381 private:
382  friend class iterator_base;
383 
384  iterator end_ = iterator(this, -1);
385  const_iterator cend_ = const_iterator(
386  const_cast<ContiguousMultiMap*>(this), -1
387  );
388 
389  int32_t _find(const K& key) const {
390  if(root_index_ == -1) return -1;
391 
392  int32_t current_index = root_index_;
393  const node_type* current = &nodes_[current_index];
394 
395  while(current) {
396  auto order = compare_(key, current->pair.first);
397 
398  if(order == ThreeWayCompare<K>::RESULT_EQUAL) {
399  return current_index;
400  } else if(order == ThreeWayCompare<K>::RESULT_LESS) {
401  if(current->left_index_ != -1) {
402  current_index = current->left_index_;
403  current = &nodes_[current_index];
404  } else {
405  return -1;
406  }
407  } else {
408  if(current->right_index_ != -1) {
409  current_index = current->right_index_;
410  current = &nodes_[current_index];
411  } else {
412  return -1;
413  }
414  }
415  }
416 
417  return current_index;
418  }
419 
420  void _rotate_left(node_type* node, int32_t node_index, node_type* parent=nullptr) {
421  int32_t nnew_index = node->right_index_;
422  assert(nnew_index != -1);
423 
424  /* Fetch the parent if it wasn't passed */
425  int32_t parent_index = node->parent_index_;
426  parent = (parent) ? parent : (parent_index == -1) ? nullptr : &nodes_[parent_index];
427 
428  node_type* nnew = &nodes_[nnew_index];
429 
430  node->right_index_ = nnew->left_index_;
431  nnew->left_index_ = node_index;
432  node->parent_index_ = nnew_index;
433 
434  if(node->right_index_ != -1) {
435  nodes_[node->right_index_].parent_index_ = node_index;
436  }
437 
438  if(parent) {
439  if(node_index == parent->left_index_) {
440  parent->left_index_ = nnew_index;
441  } else if(node_index == parent->right_index_) {
442  parent->right_index_ = nnew_index;
443  }
444  }
445 
446  nnew->parent_index_ = parent_index;
447  }
448 
449  void _rotate_right(node_type* node, int32_t node_index, node_type* parent=nullptr) {
450  int32_t nnew_index = node->left_index_;
451  assert(nnew_index != -1);
452 
453  /* Fetch the parent if it wasn't passed */
454  int32_t parent_index = node->parent_index_;
455  parent = (parent) ? parent : (parent_index == -1) ? nullptr : &nodes_[parent_index];
456 
457  node_type* nnew = &nodes_[nnew_index];
458 
459  node->left_index_ = nnew->right_index_;
460  nnew->right_index_ = node_index;
461  node->parent_index_ = nnew_index;
462 
463  if(node->left_index_ != -1) {
464  nodes_[node->left_index_].parent_index_ = node_index;
465  }
466 
467  if(parent) {
468  if(node_index == parent->left_index_) {
469  parent->left_index_ = nnew_index;
470  } else if(node_index == parent->right_index_) {
471  parent->right_index_ = nnew_index;
472  }
473  }
474 
475  nnew->parent_index_ = parent_index;
476  }
477 
478  void _insert_repair_tree(node_type* node, int32_t node_index) {
479 
480  /* Case 1: Parent is the root, so just mark the parent as black */
481  if(node->parent_index_ == -1) {
482  node->is_black = true;
483  return;
484  }
485 
486  assert(node->parent_index_ != -1);
487  node_type* parent = &nodes_[node->parent_index_];
488 
489  /* Case 2: Parent is black, we're all good */
490  if(parent->is_black) {
491  return;
492  }
493 
494  node_type* grandparent = (parent->parent_index_ == -1) ?
495  nullptr : &nodes_[parent->parent_index_];
496 
497  int32_t parent_sibling_index = (!grandparent) ? -1 :
498  (grandparent->left_index_ == node->parent_index_) ?
499  grandparent->right_index_ : grandparent->left_index_;
500 
501  node_type* parent_sibling = (parent_sibling_index == -1) ? nullptr : &nodes_[parent_sibling_index];
502 
503  /* Case 3: parent has a sibling, and it's red */
504  if(parent_sibling && !parent_sibling->is_black) {
505  /* Recolor and recurse upwards */
506  parent->is_black = true;
507  parent_sibling->is_black = true;
508  grandparent->is_black = false;
509 
510  /* Recurse up! */
511  _insert_repair_tree(grandparent, parent->parent_index_);
512  } else {
513  /* Case 4: Parent is red, but the parent sibling doesn't exist, or is black */
514  if(node_index == parent->right_index_ && node->parent_index_ == grandparent->left_index_) {
515  _rotate_left(parent, node->parent_index_, grandparent);
516 
517  node_index = node->left_index_;
518  node = &nodes_[node->left_index_];
519 
520  assert(node->parent_index_ != -1);
521  parent = &nodes_[node->parent_index_];
522 
523  assert(parent->parent_index_ != -1);
524  grandparent = &nodes_[parent->parent_index_];
525 
526  } else if(node_index == parent->left_index_ && node->parent_index_ == grandparent->right_index_) {
527  _rotate_right(parent, node->parent_index_, grandparent);
528 
529  node_index = node->right_index_;
530  node = &nodes_[node->right_index_];
531 
532  assert(node->parent_index_ != -1);
533  parent = &nodes_[node->parent_index_];
534 
535  assert(parent->parent_index_ != -1);
536  grandparent = &nodes_[parent->parent_index_];
537  }
538 
539  if(node_index == parent->left_index_) {
540  _rotate_right(grandparent, parent->parent_index_);
541  } else {
542  _rotate_left(grandparent, parent->parent_index_);
543  }
544 
545  assert(parent);
546  assert(grandparent);
547 
548  parent->is_black = true;
549  grandparent->is_black = false;
550  }
551  }
552 
553  bool _insert(K&& key, V&& value) {
554  if(root_index_ == -1) {
555  /* Root case, just set to black */
556  root_index_ = new_node(-1, std::move(key), std::move(value));
557  nodes_.back().is_black = true;
558  return true;
559  } else {
560  /* Returns new index, and whether or not the
561  * parent is a black node */
562  int32_t new_index;
563  bool is_black = _insert_recurse(
564  root_index_, std::move(key), std::move(value), &new_index
565  );
566 
567  if(new_index > -1 && !is_black) {
568  /* Parent was red! rebalance! */
569  node_type* inserted = &nodes_[new_index];
570  _insert_repair_tree(inserted, new_index);
571 
572  /* Reset root index */
573  if(inserted->parent_index_ == -1) {
574  root_index_ = new_index;
575  } else {
576  node_type* parent = inserted;
577  while(parent->parent_index_ != -1) {
578  node_type* next_parent = &nodes_[parent->parent_index_];
579 
580  if(next_parent->parent_index_ == -1) {
581  root_index_ = parent->parent_index_;
582  break;
583  }
584 
585  parent = next_parent;
586  }
587  }
588 
589  return true;
590  }
591 
592  /* p.first is the new index, it will be -1 on insert failure */
593  return new_index > -1;
594  }
595  }
596 
597  inline int32_t new_node(int32_t parent_index, K&& key, V&& value) {
598  auto ret = (int32_t) nodes_.size();
599  nodes_.push_back(node_type(key, value));
600  nodes_.back().parent_index_ = parent_index;
601  return ret;
602  }
603 
604  /* Returns inserted, parent_is_black */
605  bool _insert_recurse(int32_t root_index, K&& key, V&& value, int32_t* new_index) {
606  assert(root_index > -1);
607 
608  node_type* root = &nodes_[root_index];
609 
610  auto order = compare_(key, root->pair.first);
611  if(order == ThreeWayCompare<K>::RESULT_EQUAL) {
612 
613  /* We're inserting a duplicate, so we use the equal_index_ */
614 
615  auto new_idx = new_node(-1, std::move(key), std::move(value));
616  root = &nodes_[root_index]; // new_node could realloc
617 
618  /* We could insert immediately after the root, but, this
619  * makes insertion unstable; iteration won't iterate in the
620  * inserted order so instead we go through to the last
621  * equal index before inserting */
622 
623  auto left = root;
624  if(root->last_equal_index_ > -1) {
625  left = &nodes_[left->last_equal_index_];
626  }
627 
628  left->equal_index_ = new_idx;
629  root->last_equal_index_ = new_idx;
630 
631  /* We return the new node index, and we say the parent
632  * is black (because this node was added to a linked list
633  * not the tree itself and we don't want any recursive fixing
634  * of the red-black tree) */
635  if(new_index) {
636  *new_index = new_idx;
637  }
638 
639  return true;
640  } else if(order == ThreeWayCompare<K>::RESULT_LESS) {
641  if(root->left_index_ == -1) {
642  auto new_idx = new_node(root_index, std::move(key), std::move(value));
643  /* The insert could have invalidated the root pointer */
644  root = &nodes_[root_index];
645  root->left_index_ = new_idx;
646 
647  if(new_index) {
648  *new_index = new_idx;
649  }
650 
651  return root->is_black;
652  } else {
653  return _insert_recurse(
654  root->left_index_, std::move(key), std::move(value), new_index
655  );
656  }
657  } else {
658  if(root->right_index_ == -1) {
659  auto new_idx = new_node(root_index, std::move(key), std::move(value));
660  /* The insert could have invalidated the root pointer */
661  root = &nodes_[root_index];
662  root->right_index_ = new_idx;
663 
664  if(new_index) {
665  *new_index = new_idx;
666  }
667 
668  return root->is_black;
669  } else {
670  return _insert_recurse(
671  root->right_index_, std::move(key), std::move(value), new_index
672  );
673  }
674  }
675  }
676 
677  std::vector<node_type> nodes_;
678 
679  int32_t root_index_ = -1;
680  Compare compare_;
681 };
682 
683 
684 template<typename K, typename V, typename Compare=ThreeWayCompare<K>>
686 public:
689 
690  ContiguousMap() = default;
691  ContiguousMap(std::size_t reserve):
692  map_(reserve) {}
693 
694  bool empty() const {
695  return map_.empty();
696  }
697 
698  std::size_t size() const {
699  return map_.size();
700  }
701 
702  bool insert(const K& key, V&& element) {
703  if(map_.find(key) == map_.end()) {
704  map_.insert(key, std::move(element));
705  return true;
706  } else {
707  return false;
708  }
709  }
710 
711  const V& at(const K& key) const {
712  auto it = map_.find(key);
713 
714  if(it == map_.end()) {
715  throw std::out_of_range("Key not found");
716  }
717 
718  return (*it).second;
719  }
720 
721  bool insert(const K& key, const V& element) {
722  if(map_.find(key) == map_.end()) {
723  map_.insert(key, element);
724  return true;
725  } else {
726  return false;
727  }
728  }
729 
730  void shrink_to_fit() {
731  map_.shrink_to_fit();
732  }
733 
734  void clear() {
735  map_.clear();
736  }
737 
738  iterator find(const K& key) {
739  return map_.find(key);
740  }
741 
742  const_iterator find(const K &key) const {
743  return map_.find(key);
744  }
745 
746  iterator begin() {
747  return map_.begin();
748  }
749 
750  iterator end() {
751  return map_.end();
752  }
753 
754  const_iterator begin() const {
755  return map_.begin();
756  }
757 
758  const_iterator end() const {
759  return map_.end();
760  }
761 private:
763 };
764 
765 
766 }
smlt::ContiguousMultiMap::const_iterator
Definition: contiguous_map.h:221
smlt::ThreeWayCompare
Definition: contiguous_map.h:48
smlt
Definition: animation.cpp:25
smlt::ContiguousMap
Definition: contiguous_map.h:685
smlt::_contiguous_map::NodeMeta
Definition: contiguous_map.h:27
smlt::ContiguousMultiMap::iterator_base
Definition: contiguous_map.h:69
smlt::ContiguousMultiMap::iterator
Definition: contiguous_map.h:178
smlt::ContiguousMultiMap
Definition: contiguous_map.h:63