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-2015 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 
220  const_iterator begin() const
221  {
222  return const_iterator(this, false);
223  }
224 
225  const_iterator end() const
226  {
227  return const_iterator(this, true);
228  }
229 
230  const_reverse_iterator rbegin() const
231  {
232  return const_reverse_iterator(this, false);
233  }
234 
235  const_reverse_iterator rend() const
236  {
237  return const_reverse_iterator(this, true);
238  }
239 
240  flat_segment_tree(key_type min_val, key_type max_val, value_type init_val);
241 
246 
248 
254 
255  void swap(flat_segment_tree<key_type, value_type>& other);
256 
257  void clear();
258 
273  std::pair<const_iterator, bool>
274  insert_front(key_type start_key, key_type end_key, value_type val)
275  {
276  return insert_segment_impl(start_key, end_key, val, true);
277  }
278 
294  std::pair<const_iterator, bool>
295  insert_back(key_type start_key, key_type end_key, value_type val)
296  {
297  return insert_segment_impl(start_key, end_key, val, false);
298  }
299 
315  std::pair<const_iterator, bool>
316  insert(const const_iterator& pos, key_type start_key, key_type end_key, value_type val);
317 
327  void shift_left(key_type start_key, key_type end_key);
328 
341  void shift_right(key_type pos, key_type size, bool skip_start_node);
342 
360  std::pair<const_iterator, bool>
361  search(key_type key, value_type& value, key_type* start_key = nullptr, key_type* end_key = nullptr) const;
362 
381  std::pair<const_iterator, bool>
382  search(const const_iterator& pos, key_type key, value_type& value, key_type* start_key = nullptr, key_type* end_key = nullptr) const;
383 
403  std::pair<const_iterator, bool>
404  search_tree(key_type key, value_type& value, key_type* start_key = nullptr, key_type* end_key = nullptr) const;
405 
411  void build_tree();
412 
417  bool is_tree_valid() const
418  {
419  return m_valid_tree;
420  }
421 
428 
429  bool operator !=(const flat_segment_tree<key_type, value_type>& r) const
430  {
431  return !operator==(r);
432  }
433 
434  key_type min_key() const
435  {
436  return m_left_leaf->value_leaf.key;
437  }
438 
439  key_type max_key() const
440  {
441  return m_right_leaf->value_leaf.key;
442  }
443 
444  value_type default_value() const
445  {
446  return m_init_val;
447  }
448 
454  size_type leaf_size() const;
455 
456 #ifdef MDDS_UNIT_TEST
457  nonleaf_node* get_root_node() const
458  {
459  return m_root_node;
460  }
461 
462  void dump_tree() const
463  {
464  using ::std::cout;
465  using ::std::endl;
466 
467  if (!m_valid_tree)
468  assert(!"attempted to dump an invalid tree!");
469 
470  size_t node_count = mdds::__st::tree_dumper<node, nonleaf_node>::dump(m_root_node);
471  size_t node_instance_count = node::get_instance_count();
472  size_t leaf_count = leaf_size();
473 
474  cout << "tree node count = " << node_count << "; node instance count = "
475  << node_instance_count << "; leaf node count = " << leaf_count << endl;
476 
477  assert(leaf_count == node_instance_count);
478  }
479 
480  void dump_leaf_nodes() const
481  {
482  using ::std::cout;
483  using ::std::endl;
484 
485  cout << "------------------------------------------" << endl;
486 
487  node_ptr cur_node = m_left_leaf;
488  long node_id = 0;
489  while (cur_node)
490  {
491  cout << " node " << node_id++ << ": key = " << cur_node->value_leaf.key
492  << "; value = " << cur_node->value_leaf.value
493  << endl;
494  cur_node = cur_node->next;
495  }
496  cout << endl << " node instance count = " << node::get_instance_count() << endl;
497  }
498 
506  bool verify_keys(const ::std::vector<key_type>& key_values) const
507  {
508  {
509  // Start from the left-most node, and traverse right.
510  node* cur_node = m_left_leaf.get();
511  typename ::std::vector<key_type>::const_iterator itr = key_values.begin(), itr_end = key_values.end();
512  for (; itr != itr_end; ++itr)
513  {
514  if (!cur_node)
515  // Position past the right-mode node. Invalid.
516  return false;
517 
518  if (cur_node->value_leaf.key != *itr)
519  // Key values differ.
520  return false;
521 
522  cur_node = cur_node->next.get();
523  }
524 
525  if (cur_node)
526  // At this point, we expect the current node to be at the position
527  // past the right-most node, which is nullptr.
528  return false;
529  }
530 
531  {
532  // Start from the right-most node, and traverse left.
533  node* cur_node = m_right_leaf.get();
534  typename ::std::vector<key_type>::const_reverse_iterator itr = key_values.rbegin(), itr_end = key_values.rend();
535  for (; itr != itr_end; ++itr)
536  {
537  if (!cur_node)
538  // Position past the left-mode node. Invalid.
539  return false;
540 
541  if (cur_node->value_leaf.key != *itr)
542  // Key values differ.
543  return false;
544 
545  cur_node = cur_node->prev.get();
546  }
547 
548  if (cur_node)
549  // Likewise, we expect the current position to be past the
550  // left-most node, in which case the node value is nullptr.
551  return false;
552  }
553 
554  return true;
555  }
556 
564  bool verify_values(const ::std::vector<value_type>& values) const
565  {
566  node* cur_node = m_left_leaf.get();
567  node* end_node = m_right_leaf.get();
568  typename ::std::vector<value_type>::const_iterator itr = values.begin(), itr_end = values.end();
569  for (; itr != itr_end; ++itr)
570  {
571  if (cur_node == end_node || !cur_node)
572  return false;
573 
574  if (cur_node->value_leaf.value != *itr)
575  // Key values differ.
576  return false;
577 
578  cur_node = cur_node->next.get();
579  }
580 
581  if (cur_node != end_node)
582  // At this point, we expect the current node to be at the end of
583  // range.
584  return false;
585 
586  return true;
587  }
588 #endif
589 
590 private:
591  flat_segment_tree(); // default constructor is not allowed.
592 
593  void append_new_segment(key_type start_key)
594  {
595  if (m_right_leaf->prev->value_leaf.key == start_key)
596  {
597  m_right_leaf->prev->value_leaf.value = m_init_val;
598  return;
599  }
600 
601 #ifdef MDDS_UNIT_TEST
602  // The start position must come after the position of the last node
603  // before the right-most node.
604  assert(m_right_leaf->prev->value_leaf.key < start_key);
605 #endif
606 
607  if (m_right_leaf->prev->value_leaf.value == m_init_val)
608  // The existing segment has the same value. No need to insert a
609  // new segment.
610  return;
611 
612  node_ptr new_node(new node);
613  new_node->value_leaf.key = start_key;
614  new_node->value_leaf.value = m_init_val;
615  new_node->prev = m_right_leaf->prev;
616  new_node->next = m_right_leaf;
617  m_right_leaf->prev->next = new_node;
618  m_right_leaf->prev = new_node;
619  m_valid_tree = false;
620  }
621 
622  ::std::pair<const_iterator, bool>
623  insert_segment_impl(key_type start_key, key_type end_key, value_type val, bool forward);
624 
625  ::std::pair<const_iterator, bool>
626  insert_to_pos(node_ptr& start_pos, key_type start_key, key_type end_key, value_type val);
627 
628  ::std::pair<const_iterator, bool>
629  search_impl(const node* pos, key_type key, value_type& value, key_type* start_key, key_type* end_key) const;
630 
631  const node* get_insertion_pos_leaf_reverse(key_type key, const node* start_pos) const;
632 
633  const node* get_insertion_pos_leaf(key_type key, const node* start_pos) const;
634 
635  static void shift_leaf_key_left(node_ptr& begin_node, node_ptr& end_node, key_type shift_value)
636  {
637  node* cur_node_p = begin_node.get();
638  node* end_node_p = end_node.get();
639  while (cur_node_p != end_node_p)
640  {
641  cur_node_p->value_leaf.key -= shift_value;
642  cur_node_p = cur_node_p->next.get();
643  }
644  }
645 
646  static void shift_leaf_key_right(node_ptr& cur_node, node_ptr& end_node, key_type shift_value)
647  {
648  key_type end_node_key = end_node->value_leaf.key;
649  while (cur_node.get() != end_node.get())
650  {
651  cur_node->value_leaf.key += shift_value;
652  if (cur_node->value_leaf.key < end_node_key)
653  {
654  // The node is still in-bound. Keep shifting.
655  cur_node = cur_node->next;
656  continue;
657  }
658 
659  // This node has been pushed outside the end node position.
660  // Remove all nodes that follows, and connect the previous node
661  // with the end node.
662 
663  node_ptr last_node = cur_node->prev;
664  while (cur_node.get() != end_node.get())
665  {
666  node_ptr next_node = cur_node->next;
667  disconnect_all_nodes(cur_node.get());
668  cur_node = next_node;
669  }
670  last_node->next = end_node;
671  end_node->prev = last_node;
672  return;
673  }
674  }
675 
676  void destroy();
677 
685  bool adjust_segment_range(key_type& start_key, key_type& end_key) const;
686 
687 private:
688  std::vector<nonleaf_node> m_nonleaf_node_pool;
689 
690  nonleaf_node* m_root_node;
691  node_ptr m_left_leaf;
692  node_ptr m_right_leaf;
693  value_type m_init_val;
694  bool m_valid_tree;
695 };
696 
697 template<typename _Key, typename _Value>
698 void
700 {
701  left.swap(right);
702 }
703 
704 } // namespace mdds
705 
706 #include "flat_segment_tree_def.inl"
707 
708 #endif
709 
710 /* 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:274
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
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
std::pair< const_iterator, bool > search(key_type key, value_type &value, key_type *start_key=nullptr, key_type *end_key=nullptr) const
Definition: node.hpp:43
Definition: node.hpp:53
Definition: global.hpp:58
std::pair< const_iterator, bool > insert_back(key_type start_key, key_type end_key, value_type val)
Definition: flat_segment_tree.hpp:295
Definition: flat_segment_tree.hpp:49
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: default_deleter.hpp:33
bool is_tree_valid() const
Definition: flat_segment_tree.hpp:417
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
size_type leaf_size() const
Definition: flat_segment_tree_itr.hpp:94
Definition: node.hpp:143
void shift_right(key_type pos, key_type size, bool skip_start_node)
Definition: flat_segment_tree.hpp:186
bool operator==(const nonleaf_value_type &r) const
high range value (non-inclusive)
Definition: flat_segment_tree.hpp:61
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.hpp:168