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// SPDX-FileCopyrightText: 2008 - 2025 Kohei Yoshida
4//
5// SPDX-License-Identifier: MIT
6
7#pragma once
8
9#include <iostream>
10#include <sstream>
11#include <utility>
12#include <cassert>
13#include <type_traits>
14
15#include "./node.hpp"
16#include "./flat_segment_tree_itr.hpp"
17#include "./global.hpp"
18
19#ifdef MDDS_UNIT_TEST
20#include <cstdio>
21#include <vector>
22#endif
23
24namespace mdds {
25
26template<typename Key, typename Value>
27class flat_segment_tree
28{
29public:
30 typedef Key key_type;
31 typedef Value value_type;
32 typedef size_t size_type;
33
35 {
36 bool operator==(const nonleaf_value_type&) const noexcept
37 {
38 return true;
39 }
40 };
41
42 struct leaf_value_type
43 {
44 value_type value;
45
46 bool operator==(const leaf_value_type& r) const
47 noexcept(noexcept(std::declval<value_type>() == std::declval<value_type>()))
48 {
49 return value == r.value;
50 }
51
52 leaf_value_type() : value{}
53 {}
54 };
55
57 using node_ptr = typename node::node_ptr;
59
60private:
61 friend struct ::mdds::fst::detail::forward_itr_handler<flat_segment_tree>;
62 friend struct ::mdds::fst::detail::reverse_itr_handler<flat_segment_tree>;
63
64 static constexpr bool nothrow_move_constructible_v =
65 std::is_nothrow_move_constructible_v<std::vector<nonleaf_node>> &&
66 std::is_nothrow_move_constructible_v<value_type>;
67
68 static constexpr bool nothrow_swappable_v =
69 std::is_nothrow_swappable_v<value_type> && std::is_nothrow_swappable_v<std::vector<nonleaf_node>>;
70
71 static constexpr bool nothrow_move_assignable_v = nothrow_move_constructible_v && nothrow_swappable_v;
72
73 static constexpr bool nothrow_eq_comparable_v =
74 noexcept(std::declval<key_type>() == std::declval<key_type>()) &&
75 noexcept(std::declval<leaf_value_type>() == std::declval<leaf_value_type>());
76
77public:
79
80 class const_iterator : public ::mdds::fst::detail::const_iterator_base<
81 flat_segment_tree, ::mdds::fst::detail::forward_itr_handler<flat_segment_tree>>
82 {
85 base_type;
86 friend class flat_segment_tree;
87
88 using base_type::get_parent;
89 using base_type::get_pos;
90 using base_type::is_end_pos;
91
92 public:
93 const_iterator() : base_type(nullptr, false)
94 {}
95
100 const_segment_iterator to_segment() const;
101
102 private:
103 explicit const_iterator(const typename base_type::fst_type* _db, bool _end) : base_type(_db, _end)
104 {}
105
106 explicit const_iterator(const typename base_type::fst_type* _db, const node* p) : base_type(_db, p)
107 {}
108 };
109
110 class const_reverse_iterator : public ::mdds::fst::detail::const_iterator_base<
111 flat_segment_tree, ::mdds::fst::detail::reverse_itr_handler<flat_segment_tree>>
112 {
115 base_type;
116 friend class flat_segment_tree;
117
118 public:
119 const_reverse_iterator() : base_type(nullptr, false)
120 {}
121
122 private:
123 explicit const_reverse_iterator(const typename base_type::fst_type* _db, bool _end) : base_type(_db, _end)
124 {}
125 };
126
127 class const_segment_range_type
128 {
129 node_ptr m_left_leaf;
130 node_ptr m_right_leaf;
131
132 public:
133 const_segment_range_type(node_ptr left_leaf, node_ptr right_leaf);
134
135 const_segment_iterator begin() const;
136 const_segment_iterator end() const;
137 };
138
147 {
148 return const_iterator(this, false);
149 }
150
160 {
161 return const_iterator(this, true);
162 }
163
173 {
174 return const_reverse_iterator(this, false);
175 }
176
187 {
188 return const_reverse_iterator(this, true);
189 }
190
201 const_segment_iterator begin_segment() const;
202
214 const_segment_iterator end_segment() const;
215
220
221 flat_segment_tree() = delete;
222
234 flat_segment_tree(key_type min_val, key_type max_val, value_type init_val);
235
239 flat_segment_tree(const flat_segment_tree& r);
240
247 flat_segment_tree(flat_segment_tree&& other) noexcept(nothrow_move_constructible_v);
248
249 ~flat_segment_tree();
250
258 flat_segment_tree<Key, Value>& operator=(const flat_segment_tree& other);
259
265 flat_segment_tree<Key, Value>& operator=(flat_segment_tree&& other) noexcept(nothrow_move_assignable_v);
266
272 void swap(flat_segment_tree& other) noexcept(nothrow_swappable_v);
273
279 void clear();
280
295 std::pair<const_iterator, bool> insert_front(key_type start_key, key_type end_key, value_type val)
296 {
297 return insert_segment_impl(std::move(start_key), std::move(end_key), std::move(val), true);
298 }
299
315 std::pair<const_iterator, bool> insert_back(key_type start_key, key_type end_key, value_type val)
316 {
317 return insert_segment_impl(std::move(start_key), std::move(end_key), std::move(val), false);
318 }
319
335 std::pair<const_iterator, bool> insert(const_iterator pos, key_type start_key, key_type end_key, value_type val);
336
346 void shift_left(key_type start_key, key_type end_key);
347
360 void shift_right(key_type pos, key_type size, bool skip_start_node);
361
379 std::pair<const_iterator, bool> search(
380 key_type key, value_type& value, key_type* start_key = nullptr, key_type* end_key = nullptr) const;
381
400 std::pair<const_iterator, bool> search(
401 const_iterator pos, key_type key, value_type& value, key_type* start_key = nullptr,
402 key_type* end_key = nullptr) const;
403
413 const_iterator search(key_type key) const;
414
427 const_iterator search(const_iterator pos, key_type key) const;
428
448 std::pair<const_iterator, bool> search_tree(
449 key_type key, value_type& value, key_type* start_key = nullptr, key_type* end_key = nullptr) const;
450
461 const_iterator search_tree(key_type key) const;
462
469
474 bool valid_tree() const noexcept
475 {
476 return m_valid_tree;
477 }
478
484 bool operator==(const flat_segment_tree& other) const noexcept(nothrow_eq_comparable_v);
485
486 const key_type& min_key() const noexcept
487 {
488 return m_left_leaf->key;
489 }
490
491 const key_type& max_key() const noexcept
492 {
493 return m_right_leaf->key;
494 }
495
496 const value_type& default_value() const noexcept
497 {
498 return m_init_val;
499 }
500
506 size_type leaf_size() const
507 noexcept(noexcept(st::detail::count_leaf_nodes<size_type>(m_left_leaf.get(), m_right_leaf.get())))
508 {
509 return st::detail::count_leaf_nodes<size_type>(m_left_leaf.get(), m_right_leaf.get());
510 }
511
512#ifdef MDDS_UNIT_TEST
513 const nonleaf_node* get_root_node() const
514 {
515 return m_root_node;
516 }
517
518 struct tree_dumper_traits
519 {
520 using leaf_type = node;
521 using nonleaf_type = nonleaf_node;
522 using tree_type = flat_segment_tree;
523
524 struct to_string
525 {
526 to_string(const tree_type&)
527 {}
528
529 std::string operator()(const leaf_type& leaf) const
530 {
531 return leaf.to_string();
532 }
533
534 std::string operator()(const nonleaf_type& nonleaf) const
535 {
536 return nonleaf.to_string();
537 }
538 };
539 };
540
541 void dump_tree() const
542 {
543 using ::std::cout;
544 using ::std::endl;
545
546 if (!m_valid_tree)
547 assert(!"attempted to dump an invalid tree!");
548
549 size_t node_count = mdds::st::detail::tree_dumper<tree_dumper_traits>::dump(std::cout, *this, m_root_node);
550 size_t node_instance_count = node::get_instance_count();
551 size_t leaf_count = leaf_size();
552
553 cout << "tree node count = " << node_count << "; node instance count = " << node_instance_count
554 << "; leaf node count = " << leaf_count << endl;
555
556 assert(leaf_count == node_instance_count);
557 }
558
559 void dump_leaf_nodes() const
560 {
561 using ::std::cout;
562 using ::std::endl;
563
564 cout << "------------------------------------------" << endl;
565
566 node_ptr cur_node = m_left_leaf;
567 long node_id = 0;
568 while (cur_node)
569 {
570 cout << " node " << node_id++ << ": key = " << cur_node->key << "; value = " << cur_node->value_leaf.value
571 << endl;
572 cur_node = cur_node->next;
573 }
574 cout << endl << " node instance count = " << node::get_instance_count() << endl;
575 }
576
584 bool verify_keys(const ::std::vector<key_type>& key_values) const
585 {
586 {
587 // Start from the left-most node, and traverse right.
588 node* cur_node = m_left_leaf.get();
589 typename ::std::vector<key_type>::const_iterator itr = key_values.begin(), itr_end = key_values.end();
590 for (; itr != itr_end; ++itr)
591 {
592 if (!cur_node)
593 // Position past the right-mode node. Invalid.
594 return false;
595
596 if (cur_node->key != *itr)
597 // Key values differ.
598 return false;
599
600 cur_node = cur_node->next.get();
601 }
602
603 if (cur_node)
604 // At this point, we expect the current node to be at the position
605 // past the right-most node, which is nullptr.
606 return false;
607 }
608
609 {
610 // Start from the right-most node, and traverse left.
611 node* cur_node = m_right_leaf.get();
612 typename ::std::vector<key_type>::const_reverse_iterator itr = key_values.rbegin(),
613 itr_end = key_values.rend();
614 for (; itr != itr_end; ++itr)
615 {
616 if (!cur_node)
617 // Position past the left-mode node. Invalid.
618 return false;
619
620 if (cur_node->key != *itr)
621 // Key values differ.
622 return false;
623
624 cur_node = cur_node->prev.get();
625 }
626
627 if (cur_node)
628 // Likewise, we expect the current position to be past the
629 // left-most node, in which case the node value is nullptr.
630 return false;
631 }
632
633 return true;
634 }
635
643 bool verify_values(const ::std::vector<value_type>& values) const
644 {
645 node* cur_node = m_left_leaf.get();
646 node* end_node = m_right_leaf.get();
647 typename ::std::vector<value_type>::const_iterator itr = values.begin(), itr_end = values.end();
648 for (; itr != itr_end; ++itr)
649 {
650 if (cur_node == end_node || !cur_node)
651 return false;
652
653 if (cur_node->value_leaf.value != *itr)
654 // Key values differ.
655 return false;
656
657 cur_node = cur_node->next.get();
658 }
659
660 if (cur_node != end_node)
661 // At this point, we expect the current node to be at the end of
662 // range.
663 return false;
664
665 return true;
666 }
667#endif
668
669private:
670 const_iterator search_by_key_impl(const node* start_pos, key_type key) const;
671
672 const node* search_tree_for_leaf_node(key_type key) const;
673
674 void append_new_segment(key_type start_key)
675 {
676 if (m_right_leaf->prev->key == start_key)
677 {
678 m_right_leaf->prev->value_leaf.value = m_init_val;
679 return;
680 }
681
682#ifdef MDDS_UNIT_TEST
683 // The start position must come after the position of the last node
684 // before the right-most node.
685 assert(m_right_leaf->prev->key < start_key);
686#endif
687
688 if (m_right_leaf->prev->value_leaf.value == m_init_val)
689 // The existing segment has the same value. No need to insert a
690 // new segment.
691 return;
692
693 node_ptr new_node(new node);
694 new_node->key = start_key;
695 new_node->value_leaf.value = m_init_val;
696 new_node->prev = m_right_leaf->prev;
697 new_node->next = m_right_leaf;
698 m_right_leaf->prev->next = new_node;
699 m_right_leaf->prev = std::move(new_node);
700 m_valid_tree = false;
701 }
702
703 ::std::pair<const_iterator, bool> insert_segment_impl(
704 key_type start_key, key_type end_key, value_type val, bool forward);
705
706 ::std::pair<const_iterator, bool> insert_to_pos(
707 node_ptr start_pos, key_type start_key, key_type end_key, value_type val);
708
709 ::std::pair<const_iterator, bool> search_impl(
710 const node* pos, key_type key, value_type& value, key_type* start_key, key_type* end_key) const;
711
712 const node* get_insertion_pos_leaf_reverse(const key_type& key, const node* start_pos) const;
713
724 const node* get_insertion_pos_leaf(const key_type& key, const node* start_pos) const;
725
726 static void shift_leaf_key_left(node_ptr& begin_node, node_ptr& end_node, key_type shift_value)
727 {
728 node* cur_node_p = begin_node.get();
729 node* end_node_p = end_node.get();
730 while (cur_node_p != end_node_p)
731 {
732 cur_node_p->key -= shift_value;
733 cur_node_p = cur_node_p->next.get();
734 }
735 }
736
737 static void shift_leaf_key_right(node_ptr& cur_node, node_ptr& end_node, key_type shift_value)
738 {
739 key_type end_node_key = end_node->key;
740 while (cur_node.get() != end_node.get())
741 {
742 cur_node->key += shift_value;
743 if (cur_node->key < end_node_key)
744 {
745 // The node is still in-bound. Keep shifting.
746 cur_node = cur_node->next;
747 continue;
748 }
749
750 // This node has been pushed outside the end node position.
751 // Remove all nodes that follows, and connect the previous node
752 // with the end node.
753
754 node_ptr last_node = cur_node->prev;
755 while (cur_node.get() != end_node.get())
756 {
757 node_ptr next_node = cur_node->next;
758 disconnect_all_nodes(cur_node.get());
759 cur_node = std::move(next_node);
760 }
761 last_node->next = end_node;
762 end_node->prev = std::move(last_node);
763 return;
764 }
765 }
766
767 void destroy();
768
776 bool adjust_segment_range(key_type& start_key, key_type& end_key) const;
777
778private:
779 std::vector<nonleaf_node> m_nonleaf_node_pool;
780
781 const nonleaf_node* m_root_node;
782 node_ptr m_left_leaf;
783 node_ptr m_right_leaf;
784 value_type m_init_val;
785 bool m_valid_tree;
786};
787
788template<typename Key, typename Value>
789void swap(flat_segment_tree<Key, Value>& left, flat_segment_tree<Key, Value>& right) noexcept(
790 std::is_nothrow_swappable_v<flat_segment_tree<Key, Value>>)
791{
792 left.swap(right);
793}
794
795} // namespace mdds
796
797#include "flat_segment_tree_def.inl"
798
799/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
Definition flat_segment_tree.hpp:82
const_segment_iterator to_segment() const
Definition flat_segment_tree.hpp:112
Definition flat_segment_tree.hpp:128
Definition flat_segment_tree.hpp:28
flat_segment_tree(flat_segment_tree &&other) noexcept(nothrow_move_constructible_v)
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)
void swap(flat_segment_tree &other) noexcept(nothrow_swappable_v)
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
const_reverse_iterator rbegin() const
Definition flat_segment_tree.hpp:172
std::pair< const_iterator, bool > insert_front(key_type start_key, key_type end_key, value_type val)
Definition flat_segment_tree.hpp:295
flat_segment_tree< Key, Value > & operator=(flat_segment_tree &&other) noexcept(nothrow_move_assignable_v)
const_iterator begin() const
Definition flat_segment_tree.hpp:146
std::pair< const_iterator, bool > search(key_type key, value_type &value, key_type *start_key=nullptr, key_type *end_key=nullptr) const
size_type leaf_size() const noexcept(noexcept(st::detail::count_leaf_nodes< size_type >(m_left_leaf.get(), m_right_leaf.get())))
Definition flat_segment_tree.hpp:506
bool valid_tree() const noexcept
Definition flat_segment_tree.hpp:474
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:315
const_segment_iterator begin_segment() const
const_iterator search(key_type key) const
bool operator==(const flat_segment_tree &other) const noexcept(nothrow_eq_comparable_v)
const_iterator end() const
Definition flat_segment_tree.hpp:159
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:186
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:74
Definition flat_segment_tree_itr.hpp:166
Definition flat_segment_tree.hpp:35
Definition flat_segment_tree_itr.hpp:17
Definition flat_segment_tree_itr.hpp:47
Definition node.hpp:101
Definition node.hpp:40