mdds
Loading...
Searching...
No Matches
flat_segment_tree.hpp
1/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2/*************************************************************************
3 *
4 * Copyright (c) 2008-2023 Kohei Yoshida
5 *
6 * Permission is hereby granted, free of charge, to any person
7 * obtaining a copy of this software and associated documentation
8 * files (the "Software"), to deal in the Software without
9 * restriction, including without limitation the rights to use,
10 * copy, modify, merge, publish, distribute, sublicense, and/or sell
11 * copies of the Software, and to permit persons to whom the
12 * Software is furnished to do so, subject to the following
13 * conditions:
14 *
15 * The above copyright notice and this permission notice shall be
16 * included in all copies or substantial portions of the Software.
17 *
18 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
19 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
20 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
21 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
22 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
23 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
24 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
25 * OTHER DEALINGS IN THE SOFTWARE.
26 *
27 ************************************************************************/
28
29#pragma once
30
31#include <iostream>
32#include <sstream>
33#include <utility>
34#include <cassert>
35
36#include "./node.hpp"
37#include "./flat_segment_tree_itr.hpp"
38#include "./global.hpp"
39
40#ifdef MDDS_UNIT_TEST
41#include <cstdio>
42#include <vector>
43#endif
44
45namespace mdds {
46
47template<typename Key, typename Value>
49{
50public:
51 typedef Key key_type;
52 typedef Value value_type;
53 typedef size_t size_type;
54
56 {
57 };
58
60 {
61 value_type value;
62
63 bool operator==(const leaf_value_type& r) const
64 {
65 return value == r.value;
66 }
67
68 bool operator!=(const leaf_value_type& r) const
69 {
70 return !operator==(r);
71 }
72
73 leaf_value_type() : value{}
74 {}
75 };
76
78 using node_ptr = typename node::node_ptr;
80
81private:
82 friend struct ::mdds::fst::detail::forward_itr_handler<flat_segment_tree>;
83 friend struct ::mdds::fst::detail::reverse_itr_handler<flat_segment_tree>;
84
85public:
87
89 flat_segment_tree, ::mdds::fst::detail::forward_itr_handler<flat_segment_tree>>
90 {
94 friend class flat_segment_tree;
95
96 using base_type::get_parent;
97 using base_type::get_pos;
98 using base_type::is_end_pos;
99
100 public:
101 const_iterator() : base_type(nullptr, false)
102 {}
103
109
110 private:
111 explicit const_iterator(const typename base_type::fst_type* _db, bool _end) : base_type(_db, _end)
112 {}
113
114 explicit const_iterator(const typename base_type::fst_type* _db, const node* p) : base_type(_db, p)
115 {}
116 };
117
119 flat_segment_tree, ::mdds::fst::detail::reverse_itr_handler<flat_segment_tree>>
120 {
123 base_type;
124 friend class flat_segment_tree;
125
126 public:
127 const_reverse_iterator() : base_type(nullptr, false)
128 {}
129
130 private:
131 explicit const_reverse_iterator(const typename base_type::fst_type* _db, bool _end) : base_type(_db, _end)
132 {}
133 };
134
136 {
137 node_ptr m_left_leaf;
138 node_ptr m_right_leaf;
139
140 public:
141 const_segment_range_type(node_ptr left_leaf, node_ptr right_leaf);
142
143 const_segment_iterator begin() const;
144 const_segment_iterator end() const;
145 };
146
155 {
156 return const_iterator(this, false);
157 }
158
168 {
169 return const_iterator(this, true);
170 }
171
181 {
182 return const_reverse_iterator(this, false);
183 }
184
195 {
196 return const_reverse_iterator(this, true);
197 }
198
210
223
228
229 flat_segment_tree() = delete;
230
242 flat_segment_tree(key_type min_val, key_type max_val, value_type init_val);
243
248
256
258
267
274
281
287 void clear();
288
303 std::pair<const_iterator, bool> insert_front(key_type start_key, key_type end_key, value_type val)
304 {
305 return insert_segment_impl(std::move(start_key), std::move(end_key), std::move(val), true);
306 }
307
323 std::pair<const_iterator, bool> insert_back(key_type start_key, key_type end_key, value_type val)
324 {
325 return insert_segment_impl(std::move(start_key), std::move(end_key), std::move(val), false);
326 }
327
343 std::pair<const_iterator, bool> insert(const_iterator pos, key_type start_key, key_type end_key, value_type val);
344
354 void shift_left(key_type start_key, key_type end_key);
355
368 void shift_right(key_type pos, key_type size, bool skip_start_node);
369
387 std::pair<const_iterator, bool> search(
388 key_type key, value_type& value, key_type* start_key = nullptr, key_type* end_key = nullptr) const;
389
408 std::pair<const_iterator, bool> search(
409 const_iterator pos, key_type key, value_type& value, key_type* start_key = nullptr,
410 key_type* end_key = nullptr) const;
411
421 const_iterator search(key_type key) const;
422
435 const_iterator search(const_iterator pos, key_type key) const;
436
456 std::pair<const_iterator, bool> search_tree(
457 key_type key, value_type& value, key_type* start_key = nullptr, key_type* end_key = nullptr) const;
458
469 const_iterator search_tree(key_type key) const;
470
477
482 bool valid_tree() const noexcept
483 {
484 return m_valid_tree;
485 }
486
492 bool operator==(const flat_segment_tree& other) const;
493
494 bool operator!=(const flat_segment_tree& other) const
495 {
496 return !operator==(other);
497 }
498
499 key_type min_key() const
500 {
501 return m_left_leaf->key;
502 }
503
504 key_type max_key() const
505 {
506 return m_right_leaf->key;
507 }
508
509 value_type default_value() const
510 {
511 return m_init_val;
512 }
513
519 size_type leaf_size() const;
520
521#ifdef MDDS_UNIT_TEST
522 const nonleaf_node* get_root_node() const
523 {
524 return m_root_node;
525 }
526
527 struct tree_dumper_traits
528 {
529 using leaf_type = node;
530 using nonleaf_type = nonleaf_node;
531 using tree_type = flat_segment_tree;
532
533 struct to_string
534 {
535 to_string(const tree_type&)
536 {}
537
538 std::string operator()(const leaf_type& leaf) const
539 {
540 return leaf.to_string();
541 }
542
543 std::string operator()(const nonleaf_type& nonleaf) const
544 {
545 return nonleaf.to_string();
546 }
547 };
548 };
549
550 void dump_tree() const
551 {
552 using ::std::cout;
553 using ::std::endl;
554
555 if (!m_valid_tree)
556 assert(!"attempted to dump an invalid tree!");
557
558 size_t node_count = mdds::st::detail::tree_dumper<tree_dumper_traits>::dump(std::cout, *this, m_root_node);
559 size_t node_instance_count = node::get_instance_count();
560 size_t leaf_count = leaf_size();
561
562 cout << "tree node count = " << node_count << "; node instance count = " << node_instance_count
563 << "; leaf node count = " << leaf_count << endl;
564
565 assert(leaf_count == node_instance_count);
566 }
567
568 void dump_leaf_nodes() const
569 {
570 using ::std::cout;
571 using ::std::endl;
572
573 cout << "------------------------------------------" << endl;
574
575 node_ptr cur_node = m_left_leaf;
576 long node_id = 0;
577 while (cur_node)
578 {
579 cout << " node " << node_id++ << ": key = " << cur_node->key << "; value = " << cur_node->value_leaf.value
580 << endl;
581 cur_node = cur_node->next;
582 }
583 cout << endl << " node instance count = " << node::get_instance_count() << endl;
584 }
585
593 bool verify_keys(const ::std::vector<key_type>& key_values) const
594 {
595 {
596 // Start from the left-most node, and traverse right.
597 node* cur_node = m_left_leaf.get();
598 typename ::std::vector<key_type>::const_iterator itr = key_values.begin(), itr_end = key_values.end();
599 for (; itr != itr_end; ++itr)
600 {
601 if (!cur_node)
602 // Position past the right-mode node. Invalid.
603 return false;
604
605 if (cur_node->key != *itr)
606 // Key values differ.
607 return false;
608
609 cur_node = cur_node->next.get();
610 }
611
612 if (cur_node)
613 // At this point, we expect the current node to be at the position
614 // past the right-most node, which is nullptr.
615 return false;
616 }
617
618 {
619 // Start from the right-most node, and traverse left.
620 node* cur_node = m_right_leaf.get();
621 typename ::std::vector<key_type>::const_reverse_iterator itr = key_values.rbegin(),
622 itr_end = key_values.rend();
623 for (; itr != itr_end; ++itr)
624 {
625 if (!cur_node)
626 // Position past the left-mode node. Invalid.
627 return false;
628
629 if (cur_node->key != *itr)
630 // Key values differ.
631 return false;
632
633 cur_node = cur_node->prev.get();
634 }
635
636 if (cur_node)
637 // Likewise, we expect the current position to be past the
638 // left-most node, in which case the node value is nullptr.
639 return false;
640 }
641
642 return true;
643 }
644
652 bool verify_values(const ::std::vector<value_type>& values) const
653 {
654 node* cur_node = m_left_leaf.get();
655 node* end_node = m_right_leaf.get();
656 typename ::std::vector<value_type>::const_iterator itr = values.begin(), itr_end = values.end();
657 for (; itr != itr_end; ++itr)
658 {
659 if (cur_node == end_node || !cur_node)
660 return false;
661
662 if (cur_node->value_leaf.value != *itr)
663 // Key values differ.
664 return false;
665
666 cur_node = cur_node->next.get();
667 }
668
669 if (cur_node != end_node)
670 // At this point, we expect the current node to be at the end of
671 // range.
672 return false;
673
674 return true;
675 }
676#endif
677
678private:
679 const_iterator search_by_key_impl(const node* start_pos, key_type key) const;
680
681 const node* search_tree_for_leaf_node(key_type key) const;
682
683 void append_new_segment(key_type start_key)
684 {
685 if (m_right_leaf->prev->key == start_key)
686 {
687 m_right_leaf->prev->value_leaf.value = m_init_val;
688 return;
689 }
690
691#ifdef MDDS_UNIT_TEST
692 // The start position must come after the position of the last node
693 // before the right-most node.
694 assert(m_right_leaf->prev->key < start_key);
695#endif
696
697 if (m_right_leaf->prev->value_leaf.value == m_init_val)
698 // The existing segment has the same value. No need to insert a
699 // new segment.
700 return;
701
702 node_ptr new_node(new node);
703 new_node->key = start_key;
704 new_node->value_leaf.value = m_init_val;
705 new_node->prev = m_right_leaf->prev;
706 new_node->next = m_right_leaf;
707 m_right_leaf->prev->next = new_node;
708 m_right_leaf->prev = std::move(new_node);
709 m_valid_tree = false;
710 }
711
712 ::std::pair<const_iterator, bool> insert_segment_impl(
713 key_type start_key, key_type end_key, value_type val, bool forward);
714
715 ::std::pair<const_iterator, bool> insert_to_pos(
716 node_ptr start_pos, key_type start_key, key_type end_key, value_type val);
717
718 ::std::pair<const_iterator, bool> search_impl(
719 const node* pos, key_type key, value_type& value, key_type* start_key, key_type* end_key) const;
720
721 const node* get_insertion_pos_leaf_reverse(const key_type& key, const node* start_pos) const;
722
733 const node* get_insertion_pos_leaf(const key_type& key, const node* start_pos) const;
734
735 static void shift_leaf_key_left(node_ptr& begin_node, node_ptr& end_node, key_type shift_value)
736 {
737 node* cur_node_p = begin_node.get();
738 node* end_node_p = end_node.get();
739 while (cur_node_p != end_node_p)
740 {
741 cur_node_p->key -= shift_value;
742 cur_node_p = cur_node_p->next.get();
743 }
744 }
745
746 static void shift_leaf_key_right(node_ptr& cur_node, node_ptr& end_node, key_type shift_value)
747 {
748 key_type end_node_key = end_node->key;
749 while (cur_node.get() != end_node.get())
750 {
751 cur_node->key += shift_value;
752 if (cur_node->key < end_node_key)
753 {
754 // The node is still in-bound. Keep shifting.
755 cur_node = cur_node->next;
756 continue;
757 }
758
759 // This node has been pushed outside the end node position.
760 // Remove all nodes that follows, and connect the previous node
761 // with the end node.
762
763 node_ptr last_node = cur_node->prev;
764 while (cur_node.get() != end_node.get())
765 {
766 node_ptr next_node = cur_node->next;
767 disconnect_all_nodes(cur_node.get());
768 cur_node = std::move(next_node);
769 }
770 last_node->next = end_node;
771 end_node->prev = std::move(last_node);
772 return;
773 }
774 }
775
776 void destroy();
777
785 bool adjust_segment_range(key_type& start_key, key_type& end_key) const;
786
787private:
788 std::vector<nonleaf_node> m_nonleaf_node_pool;
789
790 const nonleaf_node* m_root_node;
791 node_ptr m_left_leaf;
792 node_ptr m_right_leaf;
793 value_type m_init_val;
794 bool m_valid_tree;
795};
796
797template<typename Key, typename Value>
798void swap(flat_segment_tree<Key, Value>& left, flat_segment_tree<Key, Value>& right)
799{
800 left.swap(right);
801}
802
803} // namespace mdds
804
805#include "flat_segment_tree_def.inl"
806
807/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
Definition flat_segment_tree.hpp:90
const_segment_iterator to_segment() const
Definition flat_segment_tree.hpp:120
Definition flat_segment_tree.hpp:136
Definition flat_segment_tree.hpp:49
size_type leaf_size() const
const_segment_range_type segment_range() const
flat_segment_tree< Key, Value > & operator=(const flat_segment_tree &other)
void shift_left(key_type start_key, key_type end_key)
flat_segment_tree(const flat_segment_tree &r)
flat_segment_tree(flat_segment_tree &&other)
flat_segment_tree< Key, Value > & operator=(flat_segment_tree &&other)
void shift_right(key_type pos, key_type size, bool skip_start_node)
const_segment_iterator end_segment() const
const_iterator search(const_iterator pos, key_type key) const
bool operator==(const flat_segment_tree &other) const
const_reverse_iterator rbegin() const
Definition flat_segment_tree.hpp:180
std::pair< const_iterator, bool > insert_front(key_type start_key, key_type end_key, value_type val)
Definition flat_segment_tree.hpp:303
const_iterator begin() const
Definition flat_segment_tree.hpp:154
std::pair< const_iterator, bool > search(key_type key, value_type &value, key_type *start_key=nullptr, key_type *end_key=nullptr) const
bool valid_tree() const noexcept
Definition flat_segment_tree.hpp:482
std::pair< const_iterator, bool > search_tree(key_type key, value_type &value, key_type *start_key=nullptr, key_type *end_key=nullptr) const
std::pair< const_iterator, bool > insert_back(key_type start_key, key_type end_key, value_type val)
Definition flat_segment_tree.hpp:323
const_segment_iterator begin_segment() const
const_iterator search(key_type key) const
void swap(flat_segment_tree &other)
const_iterator end() const
Definition flat_segment_tree.hpp:167
flat_segment_tree(key_type min_val, key_type max_val, value_type init_val)
std::pair< const_iterator, bool > insert(const_iterator pos, key_type start_key, key_type end_key, value_type val)
const_iterator search_tree(key_type key) const
const_reverse_iterator rend() const
Definition flat_segment_tree.hpp:194
std::pair< const_iterator, bool > search(const_iterator pos, key_type key, value_type &value, key_type *start_key=nullptr, key_type *end_key=nullptr) const
Definition flat_segment_tree_itr.hpp:97
Definition flat_segment_tree_itr.hpp:194
Definition node.hpp:427
Definition flat_segment_tree.hpp:60
Definition flat_segment_tree.hpp:56
Definition flat_segment_tree_itr.hpp:40
Definition flat_segment_tree_itr.hpp:70
Definition node.hpp:123
Definition node.hpp:64