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