mdds
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 #ifndef INCLUDED_MDDS_FLAT_SEGMENT_TREE_HPP
30 #define INCLUDED_MDDS_FLAT_SEGMENT_TREE_HPP
31 
32 #include <iostream>
33 #include <sstream>
34 #include <utility>
35 #include <cassert>
36 
37 #include "mdds/node.hpp"
38 #include "mdds/flat_segment_tree_itr.hpp"
39 #include "mdds/global.hpp"
40 
41 #ifdef MDDS_UNIT_TEST
42 #include <cstdio>
43 #include <vector>
44 #endif
45 
46 namespace mdds {
47 
48 template<typename Key, typename Value>
50 {
51 public:
52  typedef Key key_type;
53  typedef Value value_type;
54  typedef size_t size_type;
55 
57  {
58  key_type low;
59  key_type high;
60 
61  bool operator==(const nonleaf_value_type& r) const
62  {
63  return low == r.low && high == r.high;
64  }
65 
66  nonleaf_value_type() : low{}, high{}
67  {}
68  };
69 
71  {
72  key_type key;
73  value_type value;
74 
75  bool operator==(const leaf_value_type& r) const
76  {
77  return key == r.key && value == r.value;
78  }
79 
80  leaf_value_type() : key{}, value{}
81  {}
82  };
83 
84  // Handlers required by the node template class.
86  struct init_handler;
87  struct dispose_handler;
88 #ifdef MDDS_UNIT_TEST
89  struct to_string_handler;
90 #endif
91 
93  typedef typename node::node_ptr node_ptr;
94 
96 
98  {
99  void operator()(
101  const __st::node_base* right_node)
102  {
103  // Parent node should carry the range of all of its child nodes.
104  if (left_node)
105  {
106  _self.value_nonleaf.low = left_node->is_leaf
107  ? static_cast<const node*>(left_node)->value_leaf.key
108  : static_cast<const nonleaf_node*>(left_node)->value_nonleaf.low;
109  }
110  else
111  {
112  // Having a left node is prerequisite.
113  throw general_error(
114  "flat_segment_tree::fill_nonleaf_value_handler: Having a left node is prerequisite.");
115  }
116 
117  if (right_node)
118  {
119  if (right_node->is_leaf)
120  {
121  // When the child nodes are leaf nodes, the upper bound
122  // must be the value of the node that comes after the
123  // right leaf node (if such node exists).
124  const node* p = static_cast<const node*>(right_node);
125  if (p->next)
126  _self.value_nonleaf.high = p->next->value_leaf.key;
127  else
128  _self.value_nonleaf.high = p->value_leaf.key;
129  }
130  else
131  {
132  _self.value_nonleaf.high = static_cast<const nonleaf_node*>(right_node)->value_nonleaf.high;
133  }
134  }
135  else
136  {
137  _self.value_nonleaf.high = left_node->is_leaf
138  ? static_cast<const node*>(left_node)->value_leaf.key
139  : static_cast<const nonleaf_node*>(left_node)->value_nonleaf.high;
140  }
141  }
142  };
143 
144 #ifdef MDDS_UNIT_TEST
145  struct to_string_handler
146  {
147  std::string operator()(const node& _self) const
148  {
149  std::ostringstream os;
150  os << "(" << _self.value_leaf.key << ") ";
151  return os.str();
152  }
153 
154  std::string operator()(const mdds::__st::nonleaf_node<flat_segment_tree>& _self) const
155  {
156  std::ostringstream os;
157  os << "(" << _self.value_nonleaf.low << "-" << _self.value_nonleaf.high << ") ";
158  return os.str();
159  }
160  };
161 #endif
162 
164  {
165  void operator()(node& /*_self*/)
166  {}
167  void operator()(__st::nonleaf_node<flat_segment_tree>& /*_self*/)
168  {}
169  };
170 
172  {
173  void operator()(node& /*_self*/)
174  {}
175  void operator()(__st::nonleaf_node<flat_segment_tree>& /*_self*/)
176  {}
177  };
178 
179 private:
180  friend struct ::mdds::fst::detail::forward_itr_handler<flat_segment_tree>;
181  friend struct ::mdds::fst::detail::reverse_itr_handler<flat_segment_tree>;
182 
183 public:
185 
187  flat_segment_tree, ::mdds::fst::detail::forward_itr_handler<flat_segment_tree>>
188  {
189  typedef ::mdds::fst::detail::const_iterator_base<
191  base_type;
192  friend class flat_segment_tree;
193 
194  using base_type::get_parent;
195  using base_type::get_pos;
196  using base_type::is_end_pos;
197 
198  public:
199  const_iterator() : base_type(nullptr, false)
200  {}
201 
207 
208  private:
209  explicit const_iterator(const typename base_type::fst_type* _db, bool _end) : base_type(_db, _end)
210  {}
211 
212  explicit const_iterator(const typename base_type::fst_type* _db, const node* p) : base_type(_db, p)
213  {}
214  };
215 
217  flat_segment_tree, ::mdds::fst::detail::reverse_itr_handler<flat_segment_tree>>
218  {
219  typedef ::mdds::fst::detail::const_iterator_base<
221  base_type;
222  friend class flat_segment_tree;
223 
224  public:
225  const_reverse_iterator() : base_type(nullptr, false)
226  {}
227 
228  private:
229  explicit const_reverse_iterator(const typename base_type::fst_type* _db, bool _end) : base_type(_db, _end)
230  {}
231  };
232 
234  {
235  node_ptr m_left_leaf;
236  node_ptr m_right_leaf;
237 
238  public:
239  const_segment_range_type(node_ptr left_leaf, node_ptr right_leaf);
240 
241  const_segment_iterator begin() const;
242  const_segment_iterator end() const;
243  };
244 
253  {
254  return const_iterator(this, false);
255  }
256 
266  {
267  return const_iterator(this, true);
268  }
269 
279  {
280  return const_reverse_iterator(this, false);
281  }
282 
293  {
294  return const_reverse_iterator(this, true);
295  }
296 
307  const_segment_iterator begin_segment() const;
308 
320  const_segment_iterator end_segment() const;
321 
325  const_segment_range_type segment_range() const;
326 
327  flat_segment_tree() = delete;
328 
340  flat_segment_tree(key_type min_val, key_type max_val, value_type init_val);
341 
346 
354 
356 
365 
372 
378  void swap(flat_segment_tree& other);
379 
385  void clear();
386 
401  std::pair<const_iterator, bool> insert_front(key_type start_key, key_type end_key, value_type val)
402  {
403  return insert_segment_impl(std::move(start_key), std::move(end_key), std::move(val), true);
404  }
405 
421  std::pair<const_iterator, bool> insert_back(key_type start_key, key_type end_key, value_type val)
422  {
423  return insert_segment_impl(std::move(start_key), std::move(end_key), std::move(val), false);
424  }
425 
441  std::pair<const_iterator, bool> insert(
442  const const_iterator& pos, key_type start_key, key_type end_key, value_type val);
443 
453  void shift_left(key_type start_key, key_type end_key);
454 
467  void shift_right(key_type pos, key_type size, bool skip_start_node);
468 
486  std::pair<const_iterator, bool> search(
487  key_type key, value_type& value, key_type* start_key = nullptr, key_type* end_key = nullptr) const;
488 
507  std::pair<const_iterator, bool> search(
508  const const_iterator& pos, key_type key, value_type& value, key_type* start_key = nullptr,
509  key_type* end_key = nullptr) const;
510 
520  const_iterator search(key_type key) const;
521 
534  const_iterator search(const const_iterator& pos, key_type key) const;
535 
555  std::pair<const_iterator, bool> search_tree(
556  key_type key, value_type& value, key_type* start_key = nullptr, key_type* end_key = nullptr) const;
557 
568  const_iterator search_tree(key_type key) const;
569 
575  void build_tree();
576 
581  bool is_tree_valid() const
582  {
583  return m_valid_tree;
584  }
585 
591  bool operator==(const flat_segment_tree& other) const;
592 
593  bool operator!=(const flat_segment_tree& other) const
594  {
595  return !operator==(other);
596  }
597 
598  key_type min_key() const
599  {
600  return m_left_leaf->value_leaf.key;
601  }
602 
603  key_type max_key() const
604  {
605  return m_right_leaf->value_leaf.key;
606  }
607 
608  value_type default_value() const
609  {
610  return m_init_val;
611  }
612 
618  size_type leaf_size() const;
619 
620 #ifdef MDDS_UNIT_TEST
621  const nonleaf_node* get_root_node() const
622  {
623  return m_root_node;
624  }
625 
626  void dump_tree() const
627  {
628  using ::std::cout;
629  using ::std::endl;
630 
631  if (!m_valid_tree)
632  assert(!"attempted to dump an invalid tree!");
633 
634  size_t node_count = mdds::__st::tree_dumper<node, nonleaf_node>::dump(m_root_node);
635  size_t node_instance_count = node::get_instance_count();
636  size_t leaf_count = leaf_size();
637 
638  cout << "tree node count = " << node_count << "; node instance count = " << node_instance_count
639  << "; leaf node count = " << leaf_count << endl;
640 
641  assert(leaf_count == node_instance_count);
642  }
643 
644  void dump_leaf_nodes() const
645  {
646  using ::std::cout;
647  using ::std::endl;
648 
649  cout << "------------------------------------------" << endl;
650 
651  node_ptr cur_node = m_left_leaf;
652  long node_id = 0;
653  while (cur_node)
654  {
655  cout << " node " << node_id++ << ": key = " << cur_node->value_leaf.key
656  << "; value = " << cur_node->value_leaf.value << endl;
657  cur_node = cur_node->next;
658  }
659  cout << endl << " node instance count = " << node::get_instance_count() << endl;
660  }
661 
669  bool verify_keys(const ::std::vector<key_type>& key_values) const
670  {
671  {
672  // Start from the left-most node, and traverse right.
673  node* cur_node = m_left_leaf.get();
674  typename ::std::vector<key_type>::const_iterator itr = key_values.begin(), itr_end = key_values.end();
675  for (; itr != itr_end; ++itr)
676  {
677  if (!cur_node)
678  // Position past the right-mode node. Invalid.
679  return false;
680 
681  if (cur_node->value_leaf.key != *itr)
682  // Key values differ.
683  return false;
684 
685  cur_node = cur_node->next.get();
686  }
687 
688  if (cur_node)
689  // At this point, we expect the current node to be at the position
690  // past the right-most node, which is nullptr.
691  return false;
692  }
693 
694  {
695  // Start from the right-most node, and traverse left.
696  node* cur_node = m_right_leaf.get();
697  typename ::std::vector<key_type>::const_reverse_iterator itr = key_values.rbegin(),
698  itr_end = key_values.rend();
699  for (; itr != itr_end; ++itr)
700  {
701  if (!cur_node)
702  // Position past the left-mode node. Invalid.
703  return false;
704 
705  if (cur_node->value_leaf.key != *itr)
706  // Key values differ.
707  return false;
708 
709  cur_node = cur_node->prev.get();
710  }
711 
712  if (cur_node)
713  // Likewise, we expect the current position to be past the
714  // left-most node, in which case the node value is nullptr.
715  return false;
716  }
717 
718  return true;
719  }
720 
728  bool verify_values(const ::std::vector<value_type>& values) const
729  {
730  node* cur_node = m_left_leaf.get();
731  node* end_node = m_right_leaf.get();
732  typename ::std::vector<value_type>::const_iterator itr = values.begin(), itr_end = values.end();
733  for (; itr != itr_end; ++itr)
734  {
735  if (cur_node == end_node || !cur_node)
736  return false;
737 
738  if (cur_node->value_leaf.value != *itr)
739  // Key values differ.
740  return false;
741 
742  cur_node = cur_node->next.get();
743  }
744 
745  if (cur_node != end_node)
746  // At this point, we expect the current node to be at the end of
747  // range.
748  return false;
749 
750  return true;
751  }
752 #endif
753 
754 private:
755  const_iterator search_by_key_impl(const node* start_pos, key_type key) const;
756 
757  const node* search_tree_for_leaf_node(key_type key) const;
758 
759  void append_new_segment(key_type start_key)
760  {
761  if (m_right_leaf->prev->value_leaf.key == start_key)
762  {
763  m_right_leaf->prev->value_leaf.value = m_init_val;
764  return;
765  }
766 
767 #ifdef MDDS_UNIT_TEST
768  // The start position must come after the position of the last node
769  // before the right-most node.
770  assert(m_right_leaf->prev->value_leaf.key < start_key);
771 #endif
772 
773  if (m_right_leaf->prev->value_leaf.value == m_init_val)
774  // The existing segment has the same value. No need to insert a
775  // new segment.
776  return;
777 
778  node_ptr new_node(new node);
779  new_node->value_leaf.key = start_key;
780  new_node->value_leaf.value = m_init_val;
781  new_node->prev = m_right_leaf->prev;
782  new_node->next = m_right_leaf;
783  m_right_leaf->prev->next = new_node;
784  m_right_leaf->prev = new_node;
785  m_valid_tree = false;
786  }
787 
788  ::std::pair<const_iterator, bool> insert_segment_impl(
789  key_type start_key, key_type end_key, value_type val, bool forward);
790 
791  ::std::pair<const_iterator, bool> insert_to_pos(
792  node_ptr start_pos, key_type start_key, key_type end_key, value_type val);
793 
794  ::std::pair<const_iterator, bool> search_impl(
795  const node* pos, key_type key, value_type& value, key_type* start_key, key_type* end_key) const;
796 
797  const node* get_insertion_pos_leaf_reverse(const key_type& key, const node* start_pos) const;
798 
809  const node* get_insertion_pos_leaf(const key_type& key, const node* start_pos) const;
810 
811  static void shift_leaf_key_left(node_ptr& begin_node, node_ptr& end_node, key_type shift_value)
812  {
813  node* cur_node_p = begin_node.get();
814  node* end_node_p = end_node.get();
815  while (cur_node_p != end_node_p)
816  {
817  cur_node_p->value_leaf.key -= shift_value;
818  cur_node_p = cur_node_p->next.get();
819  }
820  }
821 
822  static void shift_leaf_key_right(node_ptr& cur_node, node_ptr& end_node, key_type shift_value)
823  {
824  key_type end_node_key = end_node->value_leaf.key;
825  while (cur_node.get() != end_node.get())
826  {
827  cur_node->value_leaf.key += shift_value;
828  if (cur_node->value_leaf.key < end_node_key)
829  {
830  // The node is still in-bound. Keep shifting.
831  cur_node = cur_node->next;
832  continue;
833  }
834 
835  // This node has been pushed outside the end node position.
836  // Remove all nodes that follows, and connect the previous node
837  // with the end node.
838 
839  node_ptr last_node = cur_node->prev;
840  while (cur_node.get() != end_node.get())
841  {
842  node_ptr next_node = cur_node->next;
843  disconnect_all_nodes(cur_node.get());
844  cur_node = next_node;
845  }
846  last_node->next = end_node;
847  end_node->prev = last_node;
848  return;
849  }
850  }
851 
852  void destroy();
853 
861  bool adjust_segment_range(key_type& start_key, key_type& end_key) const;
862 
863 private:
864  std::vector<nonleaf_node> m_nonleaf_node_pool;
865 
866  const nonleaf_node* m_root_node;
867  node_ptr m_left_leaf;
868  node_ptr m_right_leaf;
869  value_type m_init_val;
870  bool m_valid_tree;
871 };
872 
873 template<typename Key, typename Value>
874 void swap(flat_segment_tree<Key, Value>& left, flat_segment_tree<Key, Value>& right)
875 {
876  left.swap(right);
877 }
878 
879 } // namespace mdds
880 
881 #include "flat_segment_tree_def.inl"
882 
883 #endif
884 
885 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
Definition: flat_segment_tree.hpp:233
Definition: flat_segment_tree_itr.hpp:67
Definition: flat_segment_tree.hpp:216
key_type high
low range value (inclusive)
Definition: flat_segment_tree.hpp:59
bool is_leaf
parent nonleaf_node
Definition: node.hpp:46
bool is_tree_valid() const
Definition: flat_segment_tree.hpp:581
const_reverse_iterator rbegin() const
Definition: flat_segment_tree.hpp:278
size_type leaf_size() const
const_segment_range_type segment_range() const
Definition: flat_segment_tree.hpp:70
const_segment_iterator end_segment() const
std::pair< const_iterator, bool > insert(const const_iterator &pos, key_type start_key, key_type end_key, value_type val)
bool operator==(const flat_segment_tree &other) const
const_reverse_iterator rend() const
Definition: flat_segment_tree.hpp:292
Definition: node.hpp:43
const_iterator end() const
Definition: flat_segment_tree.hpp:265
std::pair< const_iterator, bool > insert_front(key_type start_key, key_type end_key, value_type val)
Definition: flat_segment_tree.hpp:401
std::pair< const_iterator, bool > search_tree(key_type key, value_type &value, key_type *start_key=nullptr, key_type *end_key=nullptr) const
Definition: flat_segment_tree_itr.hpp:94
Definition: node.hpp:55
Definition: flat_segment_tree_itr.hpp:37
const_segment_iterator begin_segment() const
Definition: global.hpp:83
Definition: flat_segment_tree_itr.hpp:198
void shift_right(key_type pos, key_type size, bool skip_start_node)
bool operator==(const nonleaf_value_type &r) const
high range value (non-inclusive)
Definition: flat_segment_tree.hpp:61
Definition: flat_segment_tree.hpp:49
Definition: flat_segment_tree.hpp:46
Definition: flat_segment_tree.hpp:56
flat_segment_tree< Key, Value > & operator=(const flat_segment_tree &other)
std::pair< const_iterator, bool > insert_back(key_type start_key, key_type end_key, value_type val)
Definition: flat_segment_tree.hpp:421
Definition: node.hpp:139
std::pair< const_iterator, bool > search(key_type key, value_type &value, key_type *start_key=nullptr, key_type *end_key=nullptr) const
void shift_left(key_type start_key, key_type end_key)
Definition: flat_segment_tree.hpp:186
void swap(flat_segment_tree &other)
Definition: flat_segment_tree.hpp:97
const_segment_iterator to_segment() const
Definition: flat_segment_tree.hpp:171
node_ptr next
previous sibling leaf node.
Definition: node.hpp:162
const_iterator begin() const
Definition: flat_segment_tree.hpp:252
Definition: flat_segment_tree.hpp:163