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 
67  : low(0)
68  , high(0)
69  {
70  }
71  };
72 
74  {
75  key_type key;
76  value_type value;
77 
78  bool operator== (const leaf_value_type& r) const
79  {
80  return key == r.key && value == r.value;
81  }
82 
84  : key(0)
85  , value()
86  {
87  }
88  };
89 
90  // Handlers required by the node template class.
92  struct init_handler;
93  struct dispose_handler;
94 #ifdef MDDS_UNIT_TEST
95  struct to_string_handler;
96 #endif
97 
99  typedef typename node::node_ptr node_ptr;
100 
102 
104  {
105  void operator() (__st::nonleaf_node<flat_segment_tree>& _self, const __st::node_base* left_node, const __st::node_base* right_node)
106  {
107  // Parent node should carry the range of all of its child nodes.
108  if (left_node)
109  {
110  _self.value_nonleaf.low =
111  left_node->is_leaf ?
112  static_cast<const node*>(left_node)->value_leaf.key :
113  static_cast<const nonleaf_node*>(left_node)->value_nonleaf.low;
114  }
115  else
116  {
117  // Having a left node is prerequisite.
118  throw general_error("flat_segment_tree::fill_nonleaf_value_handler: Having a left node is prerequisite.");
119  }
120 
121  if (right_node)
122  {
123  if (right_node->is_leaf)
124  {
125  // When the child nodes are leaf nodes, the upper bound
126  // must be the value of the node that comes after the
127  // right leaf node (if such node exists).
128  const node* p = static_cast<const node*>(right_node);
129  if (p->next)
130  _self.value_nonleaf.high = p->next->value_leaf.key;
131  else
132  _self.value_nonleaf.high = p->value_leaf.key;
133  }
134  else
135  {
136  _self.value_nonleaf.high = static_cast<const nonleaf_node*>(right_node)->value_nonleaf.high;
137  }
138  }
139  else
140  {
141  _self.value_nonleaf.high =
142  left_node->is_leaf ?
143  static_cast<const node*>(left_node)->value_leaf.key :
144  static_cast<const nonleaf_node*>(left_node)->value_nonleaf.high;
145  }
146  }
147  };
148 
149 #ifdef MDDS_UNIT_TEST
150  struct to_string_handler
151  {
152  std::string operator() (const node& _self) const
153  {
154  std::ostringstream os;
155  os << "(" << _self.value_leaf.key << ") ";
156  return os.str();
157  }
158 
159  std::string operator() (const mdds::__st::nonleaf_node<flat_segment_tree>& _self) const
160  {
161  std::ostringstream os;
162  os << "(" << _self.value_nonleaf.low << "-" << _self.value_nonleaf.high << ") ";
163  return os.str();
164  }
165  };
166 #endif
167 
169  {
170  void operator() (node& /*_self*/) {}
171  void operator() (__st::nonleaf_node<flat_segment_tree>& /*_self*/) {}
172  };
173 
175  {
176  void operator() (node& /*_self*/) {}
177  void operator() (__st::nonleaf_node<flat_segment_tree>& /*_self*/) {}
178  };
179 
180 private:
181 
182  friend struct ::mdds::__fst::itr_forward_handler<flat_segment_tree>;
183  friend struct ::mdds::__fst::itr_reverse_handler<flat_segment_tree>;
184 
185 public:
187  flat_segment_tree, ::mdds::__fst::itr_forward_handler<flat_segment_tree> >
188  {
189  typedef ::mdds::__fst::const_iterator_base<
191  base_type;
192  friend class flat_segment_tree;
193  public:
194  const_iterator() :
195  base_type(nullptr, false) {}
196 
197  private:
198  explicit const_iterator(const typename base_type::fst_type* _db, bool _end) :
199  base_type(_db, _end) {}
200 
201  explicit const_iterator(const typename base_type::fst_type* _db, const node* p) :
202  base_type(_db, p) {}
203  };
204 
206  flat_segment_tree, ::mdds::__fst::itr_reverse_handler<flat_segment_tree> >
207  {
208  typedef ::mdds::__fst::const_iterator_base<
210  base_type;
211  friend class flat_segment_tree;
212  public:
214  base_type(nullptr, false) {}
215  private:
216  explicit const_reverse_iterator(const typename base_type::fst_type* _db, bool _end) :
217  base_type(_db, _end) {}
218  };
219 
221 
222  const_iterator begin() const
223  {
224  return const_iterator(this, false);
225  }
226 
227  const_iterator end() const
228  {
229  return const_iterator(this, true);
230  }
231 
232  const_reverse_iterator rbegin() const
233  {
234  return const_reverse_iterator(this, false);
235  }
236 
237  const_reverse_iterator rend() const
238  {
239  return const_reverse_iterator(this, true);
240  }
241 
242  const_segment_iterator begin_segment() const;
243 
244  const_segment_iterator end_segment() const;
245 
246  flat_segment_tree(key_type min_val, key_type max_val, value_type init_val);
247 
252 
254 
260 
261  void swap(flat_segment_tree<key_type, value_type>& other);
262 
263  void clear();
264 
279  std::pair<const_iterator, bool>
280  insert_front(key_type start_key, key_type end_key, value_type val)
281  {
282  return insert_segment_impl(start_key, end_key, val, true);
283  }
284 
300  std::pair<const_iterator, bool>
301  insert_back(key_type start_key, key_type end_key, value_type val)
302  {
303  return insert_segment_impl(start_key, end_key, val, false);
304  }
305 
321  std::pair<const_iterator, bool>
322  insert(const const_iterator& pos, key_type start_key, key_type end_key, value_type val);
323 
333  void shift_left(key_type start_key, key_type end_key);
334 
347  void shift_right(key_type pos, key_type size, bool skip_start_node);
348 
366  std::pair<const_iterator, bool>
367  search(key_type key, value_type& value, key_type* start_key = nullptr, key_type* end_key = nullptr) const;
368 
387  std::pair<const_iterator, bool>
388  search(const const_iterator& pos, key_type key, value_type& value, key_type* start_key = nullptr, key_type* end_key = nullptr) const;
389 
409  std::pair<const_iterator, bool>
410  search_tree(key_type key, value_type& value, key_type* start_key = nullptr, key_type* end_key = nullptr) const;
411 
417  void build_tree();
418 
423  bool is_tree_valid() const
424  {
425  return m_valid_tree;
426  }
427 
434 
435  bool operator !=(const flat_segment_tree<key_type, value_type>& r) const
436  {
437  return !operator==(r);
438  }
439 
440  key_type min_key() const
441  {
442  return m_left_leaf->value_leaf.key;
443  }
444 
445  key_type max_key() const
446  {
447  return m_right_leaf->value_leaf.key;
448  }
449 
450  value_type default_value() const
451  {
452  return m_init_val;
453  }
454 
460  size_type leaf_size() const;
461 
462 #ifdef MDDS_UNIT_TEST
463  nonleaf_node* get_root_node() const
464  {
465  return m_root_node;
466  }
467 
468  void dump_tree() const
469  {
470  using ::std::cout;
471  using ::std::endl;
472 
473  if (!m_valid_tree)
474  assert(!"attempted to dump an invalid tree!");
475 
476  size_t node_count = mdds::__st::tree_dumper<node, nonleaf_node>::dump(m_root_node);
477  size_t node_instance_count = node::get_instance_count();
478  size_t leaf_count = leaf_size();
479 
480  cout << "tree node count = " << node_count << "; node instance count = "
481  << node_instance_count << "; leaf node count = " << leaf_count << endl;
482 
483  assert(leaf_count == node_instance_count);
484  }
485 
486  void dump_leaf_nodes() const
487  {
488  using ::std::cout;
489  using ::std::endl;
490 
491  cout << "------------------------------------------" << endl;
492 
493  node_ptr cur_node = m_left_leaf;
494  long node_id = 0;
495  while (cur_node)
496  {
497  cout << " node " << node_id++ << ": key = " << cur_node->value_leaf.key
498  << "; value = " << cur_node->value_leaf.value
499  << endl;
500  cur_node = cur_node->next;
501  }
502  cout << endl << " node instance count = " << node::get_instance_count() << endl;
503  }
504 
512  bool verify_keys(const ::std::vector<key_type>& key_values) const
513  {
514  {
515  // Start from the left-most node, and traverse right.
516  node* cur_node = m_left_leaf.get();
517  typename ::std::vector<key_type>::const_iterator itr = key_values.begin(), itr_end = key_values.end();
518  for (; itr != itr_end; ++itr)
519  {
520  if (!cur_node)
521  // Position past the right-mode node. Invalid.
522  return false;
523 
524  if (cur_node->value_leaf.key != *itr)
525  // Key values differ.
526  return false;
527 
528  cur_node = cur_node->next.get();
529  }
530 
531  if (cur_node)
532  // At this point, we expect the current node to be at the position
533  // past the right-most node, which is nullptr.
534  return false;
535  }
536 
537  {
538  // Start from the right-most node, and traverse left.
539  node* cur_node = m_right_leaf.get();
540  typename ::std::vector<key_type>::const_reverse_iterator itr = key_values.rbegin(), itr_end = key_values.rend();
541  for (; itr != itr_end; ++itr)
542  {
543  if (!cur_node)
544  // Position past the left-mode node. Invalid.
545  return false;
546 
547  if (cur_node->value_leaf.key != *itr)
548  // Key values differ.
549  return false;
550 
551  cur_node = cur_node->prev.get();
552  }
553 
554  if (cur_node)
555  // Likewise, we expect the current position to be past the
556  // left-most node, in which case the node value is nullptr.
557  return false;
558  }
559 
560  return true;
561  }
562 
570  bool verify_values(const ::std::vector<value_type>& values) const
571  {
572  node* cur_node = m_left_leaf.get();
573  node* end_node = m_right_leaf.get();
574  typename ::std::vector<value_type>::const_iterator itr = values.begin(), itr_end = values.end();
575  for (; itr != itr_end; ++itr)
576  {
577  if (cur_node == end_node || !cur_node)
578  return false;
579 
580  if (cur_node->value_leaf.value != *itr)
581  // Key values differ.
582  return false;
583 
584  cur_node = cur_node->next.get();
585  }
586 
587  if (cur_node != end_node)
588  // At this point, we expect the current node to be at the end of
589  // range.
590  return false;
591 
592  return true;
593  }
594 #endif
595 
596 private:
597  flat_segment_tree(); // default constructor is not allowed.
598 
599  void append_new_segment(key_type start_key)
600  {
601  if (m_right_leaf->prev->value_leaf.key == start_key)
602  {
603  m_right_leaf->prev->value_leaf.value = m_init_val;
604  return;
605  }
606 
607 #ifdef MDDS_UNIT_TEST
608  // The start position must come after the position of the last node
609  // before the right-most node.
610  assert(m_right_leaf->prev->value_leaf.key < start_key);
611 #endif
612 
613  if (m_right_leaf->prev->value_leaf.value == m_init_val)
614  // The existing segment has the same value. No need to insert a
615  // new segment.
616  return;
617 
618  node_ptr new_node(new node);
619  new_node->value_leaf.key = start_key;
620  new_node->value_leaf.value = m_init_val;
621  new_node->prev = m_right_leaf->prev;
622  new_node->next = m_right_leaf;
623  m_right_leaf->prev->next = new_node;
624  m_right_leaf->prev = new_node;
625  m_valid_tree = false;
626  }
627 
628  ::std::pair<const_iterator, bool>
629  insert_segment_impl(key_type start_key, key_type end_key, value_type val, bool forward);
630 
631  ::std::pair<const_iterator, bool>
632  insert_to_pos(node_ptr& start_pos, key_type start_key, key_type end_key, value_type val);
633 
634  ::std::pair<const_iterator, bool>
635  search_impl(const node* pos, key_type key, value_type& value, key_type* start_key, key_type* end_key) const;
636 
637  const node* get_insertion_pos_leaf_reverse(key_type key, const node* start_pos) const;
638 
639  const node* get_insertion_pos_leaf(key_type key, const node* start_pos) const;
640 
641  static void shift_leaf_key_left(node_ptr& begin_node, node_ptr& end_node, key_type shift_value)
642  {
643  node* cur_node_p = begin_node.get();
644  node* end_node_p = end_node.get();
645  while (cur_node_p != end_node_p)
646  {
647  cur_node_p->value_leaf.key -= shift_value;
648  cur_node_p = cur_node_p->next.get();
649  }
650  }
651 
652  static void shift_leaf_key_right(node_ptr& cur_node, node_ptr& end_node, key_type shift_value)
653  {
654  key_type end_node_key = end_node->value_leaf.key;
655  while (cur_node.get() != end_node.get())
656  {
657  cur_node->value_leaf.key += shift_value;
658  if (cur_node->value_leaf.key < end_node_key)
659  {
660  // The node is still in-bound. Keep shifting.
661  cur_node = cur_node->next;
662  continue;
663  }
664 
665  // This node has been pushed outside the end node position.
666  // Remove all nodes that follows, and connect the previous node
667  // with the end node.
668 
669  node_ptr last_node = cur_node->prev;
670  while (cur_node.get() != end_node.get())
671  {
672  node_ptr next_node = cur_node->next;
673  disconnect_all_nodes(cur_node.get());
674  cur_node = next_node;
675  }
676  last_node->next = end_node;
677  end_node->prev = last_node;
678  return;
679  }
680  }
681 
682  void destroy();
683 
691  bool adjust_segment_range(key_type& start_key, key_type& end_key) const;
692 
693 private:
694  std::vector<nonleaf_node> m_nonleaf_node_pool;
695 
696  nonleaf_node* m_root_node;
697  node_ptr m_left_leaf;
698  node_ptr m_right_leaf;
699  value_type m_init_val;
700  bool m_valid_tree;
701 };
702 
703 template<typename _Key, typename _Value>
704 void
706 {
707  left.swap(right);
708 }
709 
710 } // namespace mdds
711 
712 #include "flat_segment_tree_def.inl"
713 
714 #endif
715 
716 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
std::pair< const_iterator, bool > insert_front(key_type start_key, key_type end_key, value_type val)
Definition: flat_segment_tree.hpp:280
void shift_left(key_type start_key, key_type end_key)
Definition: flat_segment_tree.hpp:205
bool is_leaf
parent nonleaf_node
Definition: node.hpp:46
bool operator==(const nonleaf_value_type &r) const
high range value (non-inclusive)
Definition: flat_segment_tree.hpp:61
bool is_tree_valid() const
Definition: flat_segment_tree.hpp:423
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(const const_iterator &pos, key_type start_key, key_type end_key, value_type val)
Definition: flat_segment_tree_itr.hpp:37
Definition: flat_segment_tree.hpp:73
Definition: node.hpp:43
Definition: node.hpp:53
Definition: global.hpp:58
std::pair< const_iterator, bool > search(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:301
Definition: flat_segment_tree.hpp:49
Definition: default_deleter.hpp:33
key_type high
low range value (inclusive)
Definition: flat_segment_tree.hpp:59
Definition: flat_segment_tree.hpp:56
flat_segment_tree< key_type, value_type > & operator=(const flat_segment_tree< key_type, value_type > &other)
Definition: flat_segment_tree_itr.hpp:67
Definition: flat_segment_tree_itr.hpp:94
size_type leaf_size() const
Definition: node.hpp:143
void shift_right(key_type pos, key_type size, bool skip_start_node)
Definition: flat_segment_tree.hpp:186
Definition: flat_segment_tree.hpp:103
Definition: flat_segment_tree.hpp:174
node_ptr next
previous sibling leaf node.
Definition: node.hpp:166
Definition: flat_segment_tree_itr.hpp:185
Definition: flat_segment_tree.hpp:168