25 #include "../../macros.h"
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)) {}
35 std::pair<const K, V> pair;
37 bool is_black =
false;
41 int32_t equal_index_ = -1;
42 int32_t last_equal_index_ = -1;
44 int32_t parent_index_ = -1;
45 int32_t left_index_ = -1;
46 int32_t right_index_ = -1;
55 enum Result : int8_t {
61 Result operator()(
const T& a,
const T& b)
const {
62 return (a < b) ? RESULT_LESS : (b < a) ? RESULT_GREATER : RESULT_EQUAL;
67 template<
typename K,
typename V,
typename Compare=ThreeWayCompare<K>>
72 typedef _contiguous_map::NodeMeta<K, V> node_type;
80 current_node_ = map->leftmost_index_;
87 current_node_ = index;
90 auto current = _node(current_node_);
91 if(current->left_index_ > -1) {
92 previous_node_index_ = current->left_index_;
95 previous_node_index_ = -1;
101 inline typename ContiguousMultiMap::node_type* _node(int32_t index)
const {
103 return &map_->nodes_[index];
107 if(current_node_ < 0)
return;
109 auto current = _node(current_node_);
112 if(current->equal_index_ > -1 && list_head_index_ == -1) {
113 list_head_index_ = current_node_;
114 current_node_ = current->equal_index_;
116 }
else if(list_head_index_ > -1) {
118 current_node_ = current->equal_index_;
119 if(current_node_ == -1) {
121 current_node_ = list_head_index_;
122 list_head_index_ = -1;
123 current = _node(current_node_);
130 auto previous = current_node_;
132 if(current->right_index_ == -1) {
136 current_node_ = current->parent_index_;
137 while(current_node_ > -1) {
138 current = _node(current_node_);
139 if(previous == current->left_index_) {
143 previous = current_node_;
144 current_node_ = current->parent_index_;
149 current_node_ = current->right_index_;
150 if(current_node_ > -1) {
152 current = _node(current_node_);
153 while(current->left_index_ > -1) {
154 current_node_ = current->left_index_;
155 current = _node(current_node_);
160 previous_node_index_ = previous;
165 map_ == other.map_ &&
166 current_node_ == other.current_node_
170 int32_t current_node_ = -1;
175 int32_t list_head_index_ = -1;
176 int32_t previous_node_index_ = -1;
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>&;
205 bool operator==(
const iterator& other)
const {
206 return this->is_equal(other);
209 bool operator!=(
const iterator& other)
const {
210 return !this->is_equal(other);
213 reference operator*()
const {
214 return this->_node(this->current_node_)->pair;
217 pointer operator->()
const {
218 return &this->_node(this->current_node_)->pair;
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>&;
250 return this->is_equal(other);
254 return !this->is_equal(other);
257 reference operator*()
const {
258 return this->_node(this->current_node_)->pair;
261 pointer operator->()
const {
262 return &this->_node(this->current_node_)->pair;
270 leftmost_index_(-1) {
271 nodes_.reserve(reserve_count);
276 for(
auto& it: other) {
277 insert(it.first, it.second);
281 ContiguousMultiMap& operator=(
const ContiguousMultiMap& other) {
287 for(
auto& it: other) {
288 insert(it.first, it.second);
294 bool insert(
const K& key, V&& element) {
296 return _insert(std::move(k), std::move(element));
299 bool insert(
const K& key,
const V& element) {
302 return _insert(std::move(k), std::move(v));
308 leftmost_index_ = -1;
311 std::size_t count(
const K& key)
const {
312 return find(key) != end() ? 1 : 0;
315 void shrink_to_fit() {
316 nodes_.shrink_to_fit();
319 std::size_t size()
const {
320 return nodes_.size();
323 void reserve(std::size_t size) {
324 nodes_.reserve(size);
328 return nodes_.empty();
331 iterator find(
const K& key) {
332 int32_t index = _find(key);
336 return iterator(
this, index);
339 const_iterator find(
const K &key)
const {
340 int32_t index = _find(key);
345 return const_iterator(
346 const_cast<ContiguousMultiMap*
>(
this),
351 const_iterator upper_bound(
const K& key)
const {
354 while(it != end() && it->first == key) {
362 return iterator(
this);
369 const_iterator begin()
const {
370 return const_iterator(
371 const_cast<ContiguousMultiMap*
>(
this)
375 const_iterator end()
const {
383 const K& path_key(
const std::string& path)
const {
384 const node_type* node = &nodes_[root_index_];
388 if(node->left_index_ == -1) {
389 throw std::logic_error(
"Hit end of branch");
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");
396 node = &nodes_[node->right_index_];
398 throw std::logic_error(
"Invalid path");
403 return node->pair.first;
406 friend class iterator_base;
408 iterator end_ = iterator(
this, -1);
409 const_iterator cend_ = const_iterator(
410 const_cast<ContiguousMultiMap*
>(
this), -1
413 int32_t _find(
const K& key)
const {
414 if(root_index_ == -1)
return -1;
416 int32_t current_index = root_index_;
417 const node_type* current = &nodes_[current_index];
420 auto order = compare_(key, current->pair.first);
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];
432 if(current->right_index_ != -1) {
433 current_index = current->right_index_;
434 current = &nodes_[current_index];
441 return current_index;
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);
449 int32_t parent_index = node->parent_index_;
450 parent = (parent) ? parent : (parent_index == -1) ? nullptr : &nodes_[parent_index];
452 node_type* nnew = &nodes_[nnew_index];
454 node->right_index_ = nnew->left_index_;
455 nnew->left_index_ = node_index;
456 node->parent_index_ = nnew_index;
458 if(node->right_index_ != -1) {
459 nodes_[node->right_index_].parent_index_ = node_index;
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;
470 nnew->parent_index_ = parent_index;
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);
478 int32_t parent_index = node->parent_index_;
479 parent = (parent) ? parent : (parent_index == -1) ? nullptr : &nodes_[parent_index];
481 node_type* nnew = &nodes_[nnew_index];
483 node->left_index_ = nnew->right_index_;
484 nnew->right_index_ = node_index;
485 node->parent_index_ = nnew_index;
487 if(node->left_index_ != -1) {
488 nodes_[node->left_index_].parent_index_ = node_index;
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;
499 nnew->parent_index_ = parent_index;
502 void _insert_repair_tree(node_type* node, int32_t node_index) {
505 if(node->parent_index_ == -1) {
506 node->is_black =
true;
510 assert(node->parent_index_ != -1);
511 node_type* parent = &nodes_[node->parent_index_];
514 if(parent->is_black) {
518 node_type* grandparent = (parent->parent_index_ == -1) ?
519 nullptr : &nodes_[parent->parent_index_];
521 int32_t parent_sibling_index = (!grandparent) ? -1 :
522 (grandparent->left_index_ == node->parent_index_) ?
523 grandparent->right_index_ : grandparent->left_index_;
525 node_type* parent_sibling = (parent_sibling_index == -1) ? nullptr : &nodes_[parent_sibling_index];
528 if(parent_sibling && !parent_sibling->is_black) {
530 parent->is_black =
true;
531 parent_sibling->is_black =
true;
532 grandparent->is_black =
false;
535 _insert_repair_tree(grandparent, parent->parent_index_);
538 if(node_index == parent->right_index_ && node->parent_index_ == grandparent->left_index_) {
539 _rotate_left(parent, node->parent_index_, grandparent);
541 node_index = node->left_index_;
542 node = &nodes_[node->left_index_];
544 assert(node->parent_index_ != -1);
545 parent = &nodes_[node->parent_index_];
547 assert(parent->parent_index_ != -1);
548 grandparent = &nodes_[parent->parent_index_];
550 }
else if(node_index == parent->left_index_ && node->parent_index_ == grandparent->right_index_) {
551 _rotate_right(parent, node->parent_index_, grandparent);
553 node_index = node->right_index_;
554 node = &nodes_[node->right_index_];
556 assert(node->parent_index_ != -1);
557 parent = &nodes_[node->parent_index_];
559 assert(parent->parent_index_ != -1);
560 grandparent = &nodes_[parent->parent_index_];
563 if(node_index == parent->left_index_) {
564 _rotate_right(grandparent, parent->parent_index_);
566 _rotate_left(grandparent, parent->parent_index_);
572 parent->is_black =
true;
573 grandparent->is_black =
false;
577 bool _insert(K&& key, V&& value) {
578 if(root_index_ == -1) {
580 leftmost_index_ = root_index_ = new_node(-1, std::move(key), std::move(value));
581 nodes_.back().is_black =
true;
587 bool is_black = _insert_recurse(
588 root_index_, std::move(key), std::move(value), &new_index
591 node_type* inserted = (new_index > -1) ? &nodes_[new_index] :
nullptr;
593 auto ret = new_index > 1;
594 if(new_index > -1 && !is_black) {
596 _insert_repair_tree(inserted, new_index);
599 if(inserted->parent_index_ == -1) {
600 root_index_ = new_index;
602 node_type* parent = inserted;
603 while(parent->parent_index_ != -1) {
604 node_type* next_parent = &nodes_[parent->parent_index_];
606 if(next_parent->parent_index_ == -1) {
607 root_index_ = parent->parent_index_;
611 parent = next_parent;
618 assert(leftmost_index_ > -1);
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;
633 inline int32_t new_node(int32_t parent_index, K&& key, V&& value) {
634 auto ret = (int32_t) nodes_.size();
636 node_type n(key, value);
637 n.parent_index_ = parent_index;
638 nodes_.push_back(std::move(n));
643 bool _insert_recurse(int32_t root_index, K&& key, V&& value, int32_t* new_index) {
644 assert(root_index > -1);
646 node_type* root = &nodes_[root_index];
648 auto order = compare_(key, root->pair.first);
649 if(order == ThreeWayCompare<K>::RESULT_EQUAL) {
653 auto new_idx = new_node(-1, std::move(key), std::move(value));
654 root = &nodes_[root_index];
662 if(root->last_equal_index_ > -1) {
663 left = &nodes_[left->last_equal_index_];
666 left->equal_index_ = new_idx;
667 root->last_equal_index_ = new_idx;
674 *new_index = new_idx;
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));
682 root = &nodes_[root_index];
683 root->left_index_ = new_idx;
686 *new_index = new_idx;
689 return root->is_black;
691 return _insert_recurse(
692 root->left_index_, std::move(key), std::move(value), new_index
696 if(root->right_index_ == -1) {
697 auto new_idx = new_node(root_index, std::move(key), std::move(value));
699 root = &nodes_[root_index];
700 root->right_index_ = new_idx;
703 *new_index = new_idx;
706 return root->is_black;
708 return _insert_recurse(
709 root->right_index_, std::move(key), std::move(value), new_index
715 std::vector<node_type> nodes_;
717 int32_t root_index_ = -1;
718 int32_t leftmost_index_ = -1;
724 template<
typename K,
typename V,
typename Compare=ThreeWayCompare<K>>
738 std::size_t size()
const {
742 std::size_t count(
const K& key)
const {
743 return find(key) != end() ? 1 : 0;
746 bool insert(
const std::pair<K, V>& pair) {
747 return insert(pair.first, pair.second);
750 bool insert(
const K& key, V&& element) {
751 if(map_.find(key) == map_.end()) {
752 map_.insert(key, std::move(element));
759 V& at(
const K& key) {
760 auto it = map_.find(key);
762 if(it == map_.end()) {
763 throw std::out_of_range(
"Key not found");
769 const V& at(
const K& key)
const {
770 auto it = map_.find(key);
772 if(it == map_.end()) {
773 throw std::out_of_range(
"Key not found");
779 bool insert(
const K& key,
const V& element) {
780 if(map_.find(key) == map_.end()) {
781 map_.insert(key, element);
788 void shrink_to_fit() {
789 map_.shrink_to_fit();
797 return map_.find(key);
801 return map_.find(key);