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