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-2017 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(0), high(0)
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(0), 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::itr_forward_handler<flat_segment_tree>;
181  friend struct ::mdds::__fst::itr_reverse_handler<flat_segment_tree>;
182 
183 public:
185  flat_segment_tree, ::mdds::__fst::itr_forward_handler<flat_segment_tree>>
186  {
187  typedef ::mdds::__fst::const_iterator_base<
189  base_type;
190  friend class flat_segment_tree;
191 
192  public:
193  const_iterator() : base_type(nullptr, false)
194  {}
195 
196  private:
197  explicit const_iterator(const typename base_type::fst_type* _db, bool _end) : base_type(_db, _end)
198  {}
199 
200  explicit const_iterator(const typename base_type::fst_type* _db, const node* p) : base_type(_db, p)
201  {}
202  };
203 
205  flat_segment_tree, ::mdds::__fst::itr_reverse_handler<flat_segment_tree>>
206  {
207  typedef ::mdds::__fst::const_iterator_base<
209  base_type;
210  friend class flat_segment_tree;
211 
212  public:
213  const_reverse_iterator() : base_type(nullptr, false)
214  {}
215 
216  private:
217  explicit const_reverse_iterator(const typename base_type::fst_type* _db, bool _end) : base_type(_db, _end)
218  {}
219  };
220 
222 
231  {
232  return const_iterator(this, false);
233  }
234 
244  {
245  return const_iterator(this, true);
246  }
247 
257  {
258  return const_reverse_iterator(this, false);
259  }
260 
271  {
272  return const_reverse_iterator(this, true);
273  }
274 
285  const_segment_iterator begin_segment() const;
286 
298  const_segment_iterator end_segment() const;
299 
311  flat_segment_tree(key_type min_val, key_type max_val, value_type init_val);
312 
317 
319 
324 
331 
337  void clear();
338 
353  std::pair<const_iterator, bool> insert_front(key_type start_key, key_type end_key, value_type val)
354  {
355  return insert_segment_impl(start_key, end_key, val, true);
356  }
357 
373  std::pair<const_iterator, bool> insert_back(key_type start_key, key_type end_key, value_type val)
374  {
375  return insert_segment_impl(start_key, end_key, val, false);
376  }
377 
393  std::pair<const_iterator, bool> insert(
394  const const_iterator& pos, key_type start_key, key_type end_key, value_type val);
395 
405  void shift_left(key_type start_key, key_type end_key);
406 
419  void shift_right(key_type pos, key_type size, bool skip_start_node);
420 
438  std::pair<const_iterator, bool> search(
439  key_type key, value_type& value, key_type* start_key = nullptr, key_type* end_key = nullptr) const;
440 
459  std::pair<const_iterator, bool> search(
460  const const_iterator& pos, key_type key, value_type& value, key_type* start_key = nullptr,
461  key_type* end_key = nullptr) const;
462 
482  std::pair<const_iterator, bool> search_tree(
483  key_type key, value_type& value, key_type* start_key = nullptr, key_type* end_key = nullptr) const;
484 
490  void build_tree();
491 
496  bool is_tree_valid() const
497  {
498  return m_valid_tree;
499  }
500 
507 
508  bool operator!=(const flat_segment_tree<key_type, value_type>& r) const
509  {
510  return !operator==(r);
511  }
512 
513  key_type min_key() const
514  {
515  return m_left_leaf->value_leaf.key;
516  }
517 
518  key_type max_key() const
519  {
520  return m_right_leaf->value_leaf.key;
521  }
522 
523  value_type default_value() const
524  {
525  return m_init_val;
526  }
527 
533  size_type leaf_size() const;
534 
535 #ifdef MDDS_UNIT_TEST
536  nonleaf_node* get_root_node() const
537  {
538  return m_root_node;
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::tree_dumper<node, nonleaf_node>::dump(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->value_leaf.key
571  << "; value = " << cur_node->value_leaf.value << 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->value_leaf.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->value_leaf.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 
669 private:
670  flat_segment_tree(); // default constructor is not allowed.
671 
672  void append_new_segment(key_type start_key)
673  {
674  if (m_right_leaf->prev->value_leaf.key == start_key)
675  {
676  m_right_leaf->prev->value_leaf.value = m_init_val;
677  return;
678  }
679 
680 #ifdef MDDS_UNIT_TEST
681  // The start position must come after the position of the last node
682  // before the right-most node.
683  assert(m_right_leaf->prev->value_leaf.key < start_key);
684 #endif
685 
686  if (m_right_leaf->prev->value_leaf.value == m_init_val)
687  // The existing segment has the same value. No need to insert a
688  // new segment.
689  return;
690 
691  node_ptr new_node(new node);
692  new_node->value_leaf.key = start_key;
693  new_node->value_leaf.value = m_init_val;
694  new_node->prev = m_right_leaf->prev;
695  new_node->next = m_right_leaf;
696  m_right_leaf->prev->next = new_node;
697  m_right_leaf->prev = new_node;
698  m_valid_tree = false;
699  }
700 
701  ::std::pair<const_iterator, bool> insert_segment_impl(
702  key_type start_key, key_type end_key, value_type val, bool forward);
703 
704  ::std::pair<const_iterator, bool> insert_to_pos(
705  node_ptr& start_pos, key_type start_key, key_type end_key, value_type val);
706 
707  ::std::pair<const_iterator, bool> search_impl(
708  const node* pos, key_type key, value_type& value, key_type* start_key, key_type* end_key) const;
709 
710  const node* get_insertion_pos_leaf_reverse(key_type key, const node* start_pos) const;
711 
712  const node* get_insertion_pos_leaf(key_type key, const node* start_pos) const;
713 
714  static void shift_leaf_key_left(node_ptr& begin_node, node_ptr& end_node, key_type shift_value)
715  {
716  node* cur_node_p = begin_node.get();
717  node* end_node_p = end_node.get();
718  while (cur_node_p != end_node_p)
719  {
720  cur_node_p->value_leaf.key -= shift_value;
721  cur_node_p = cur_node_p->next.get();
722  }
723  }
724 
725  static void shift_leaf_key_right(node_ptr& cur_node, node_ptr& end_node, key_type shift_value)
726  {
727  key_type end_node_key = end_node->value_leaf.key;
728  while (cur_node.get() != end_node.get())
729  {
730  cur_node->value_leaf.key += shift_value;
731  if (cur_node->value_leaf.key < end_node_key)
732  {
733  // The node is still in-bound. Keep shifting.
734  cur_node = cur_node->next;
735  continue;
736  }
737 
738  // This node has been pushed outside the end node position.
739  // Remove all nodes that follows, and connect the previous node
740  // with the end node.
741 
742  node_ptr last_node = cur_node->prev;
743  while (cur_node.get() != end_node.get())
744  {
745  node_ptr next_node = cur_node->next;
746  disconnect_all_nodes(cur_node.get());
747  cur_node = next_node;
748  }
749  last_node->next = end_node;
750  end_node->prev = last_node;
751  return;
752  }
753  }
754 
755  void destroy();
756 
764  bool adjust_segment_range(key_type& start_key, key_type& end_key) const;
765 
766 private:
767  std::vector<nonleaf_node> m_nonleaf_node_pool;
768 
769  nonleaf_node* m_root_node;
770  node_ptr m_left_leaf;
771  node_ptr m_right_leaf;
772  value_type m_init_val;
773  bool m_valid_tree;
774 };
775 
776 template<typename Key, typename Value>
777 void swap(flat_segment_tree<Key, Value>& left, flat_segment_tree<Key, Value>& right)
778 {
779  left.swap(right);
780 }
781 
782 } // namespace mdds
783 
784 #include "flat_segment_tree_def.inl"
785 
786 #endif
787 
788 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
Definition: flat_segment_tree.hpp:204
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:496
Definition: flat_segment_tree_itr.hpp:37
const_reverse_iterator rbegin() const
Definition: flat_segment_tree.hpp:256
size_type leaf_size() 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)
const_reverse_iterator rend() const
Definition: flat_segment_tree.hpp:270
Definition: node.hpp:43
flat_segment_tree< key_type, value_type > & operator=(const flat_segment_tree< key_type, value_type > &other)
const_iterator end() const
Definition: flat_segment_tree.hpp:243
std::pair< const_iterator, bool > insert_front(key_type start_key, key_type end_key, value_type val)
Definition: flat_segment_tree.hpp:353
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: node.hpp:55
const_segment_iterator begin_segment() const
Definition: global.hpp:83
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
flat_segment_tree(key_type min_val, key_type max_val, value_type init_val)
Definition: flat_segment_tree.hpp:46
void swap(flat_segment_tree< key_type, value_type > &other)
Definition: flat_segment_tree.hpp:56
Definition: flat_segment_tree_itr.hpp:67
Definition: flat_segment_tree_itr.hpp:94
std::pair< const_iterator, bool > insert_back(key_type start_key, key_type end_key, value_type val)
Definition: flat_segment_tree.hpp:373
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:184
bool operator==(const flat_segment_tree< key_type, value_type > &r) const
Definition: flat_segment_tree.hpp:97
Definition: flat_segment_tree.hpp:171
node_ptr next
previous sibling leaf node.
Definition: node.hpp:162
Definition: flat_segment_tree_itr.hpp:192
const_iterator begin() const
Definition: flat_segment_tree.hpp:230
Definition: flat_segment_tree.hpp:163