libutil++  1.9.3
 All Classes Functions Variables
radix_tree.h
1 /*
2 ** libutil++
3 ** $Id: radix_tree.h 1653 2016-02-28 19:54:59Z sella $
4 ** Copyright (c) 2011-2016 Digital Genesis, LLC. All Rights Reserved.
5 ** Released under the LGPL Version 2.1 License.
6 ** http://www.digitalgenesis.com
7 */
8 
9 #ifndef __libutilxx__sella__container__radix_tree_H__
10 #define __libutilxx__sella__container__radix_tree_H__
11 
12 #include <cassert>
13 #include <string>
14 #include <utility>
15 #include <vector>
16 #include <stdexcept>
17 
18 #include "radix_tree_it.h"
19 #include "radix_tree_node.h"
20 
21 #include "ContainerException.h"
22 
23 namespace sella {
24  namespace container {
25  template<typename K>
26  K radix_substr(const K &key, int begin, int num);
27 
28  template<>
29  inline std::string radix_substr<std::string>(const std::string &key, int begin, int num) {
30  return key.substr(begin, num);
31  }
32 
33  template<typename K>
34  K radix_join(const K &key1, const K &key2);
35 
36  template<>
37  inline std::string radix_join<std::string>(const std::string &key1, const std::string &key2) {
38  return key1 + key2;
39  }
40 
41  template<typename K>
42  int radix_length(const K &key);
43 
44  template<>
45  inline int radix_length<std::string>(const std::string &key) {
46  return key.size();
47  }
48 
49  template <typename K, typename T>
50  class radix_tree {
51  public:
52  typedef K key_type;
53  typedef T mapped_type;
54  typedef std::pair<const K, T> value_type;
55  typedef radix_tree_it<K, T> iterator;
56  typedef std::size_t size_type;
57 
58  radix_tree() : m_size(0), m_root(NULL) { }
59  ~radix_tree() {
60  if (m_root != NULL) delete m_root;
61  }
62 
63  size_type size() const {
64  return m_size;
65  }
66  bool empty() const {
67  return m_size == 0;
68  }
69  void clear() {
70  delete m_root;
71  m_root = NULL;
72  m_size = 0;
73  }
74 
75  iterator find(const K &key);
76  iterator begin();
77  iterator end();
78 
79  std::pair<iterator, bool> insert(const value_type &val);
80  bool erase(const K &key);
81  void erase(iterator it);
82  void prefix_match(const K &key, std::vector<iterator> &vec);
83  void greedy_match(const K &key, std::vector<iterator> &vec);
84  iterator longest_match(const K &key);
85 
86  bool contains(const K &key) {
87  return (find(key) != end());
88  }
89 
90  T& operator[] (const K &lhs);
91  T& at(const K &lhs) throw (ContainerException);
92 
93  private:
94  size_type m_size;
95  radix_tree_node<K, T>* m_root;
96 
97  radix_tree_node<K, T>* begin(radix_tree_node<K, T> *node);
98  radix_tree_node<K, T>* find_node(const K &key, radix_tree_node<K, T> *node, int depth);
99  radix_tree_node<K, T>* append(radix_tree_node<K, T> *parent, const value_type &val);
100  radix_tree_node<K, T>* prepend(radix_tree_node<K, T> *node, const value_type &val);
101  void greedy_match(radix_tree_node<K, T> *node, std::vector<iterator> &vec);
102  };
103 
104  template <typename K, typename T>
105  void radix_tree<K, T>::prefix_match(const K &key, std::vector<iterator> &vec) {
106  vec.clear();
107 
108  if (m_root == NULL)
109  return;
110 
111  radix_tree_node<K, T> *node;
112  K key_sub1, key_sub2;
113 
114  node = find_node(key, m_root, 0);
115 
116  if (node->m_is_leaf)
117  node = node->m_parent;
118 
119  int len = radix_length(key) - node->m_depth;
120  key_sub1 = radix_substr(key, node->m_depth, len);
121  key_sub2 = radix_substr(node->m_key, 0, len);
122 
123  if (key_sub1 != key_sub2)
124  return;
125 
126  greedy_match(node, vec);
127  }
128 
129  template <typename K, typename T>
130  typename radix_tree<K, T>::iterator radix_tree<K, T>::longest_match(const K &key) {
131  if (m_root == NULL)
132  return iterator(NULL);
133 
134  radix_tree_node<K, T> *node;
135  K key_sub;
136 
137  node = find_node(key, m_root, 0);
138 
139  if (node->m_is_leaf)
140  return iterator(node);
141 
142  key_sub = radix_substr(key, node->m_depth, radix_length(node->m_key));
143 
144  if (! (key_sub == node->m_key))
145  node = node->m_parent;
146 
147  K nul = radix_substr(key, 0, 0);
148 
149  while (node != NULL) {
150  typename radix_tree_node<K, T>::it_child it;
151  it = node->m_children.find(nul);
152  if (it != node->m_children.end() && it->second->m_is_leaf)
153  return iterator(it->second);
154 
155  node = node->m_parent;
156  }
157 
158  return iterator(NULL);
159  }
160 
161  template <typename K, typename T>
162  typename radix_tree<K, T>::iterator radix_tree<K, T>::end() {
163  return iterator(NULL);
164  }
165 
166  template <typename K, typename T>
167  typename radix_tree<K, T>::iterator radix_tree<K, T>::begin() {
168  radix_tree_node<K, T> *node;
169 
170  if (m_root == NULL)
171  node = NULL;
172  else
173  node = begin(m_root);
174 
175  return iterator(node);
176  }
177 
178  template <typename K, typename T>
179  radix_tree_node<K, T>* radix_tree<K, T>::begin(radix_tree_node<K, T> *node) {
180  if (node->m_is_leaf)
181  return node;
182 
183  assert(!node->m_children.empty());
184 
185  return begin(node->m_children.begin()->second);
186  }
187 
188  template <typename K, typename T>
189  T& radix_tree<K, T>::operator[] (const K &lhs) {
190  iterator it = find(lhs);
191 
192  if (it == end()) {
193  std::pair<K, T> val;
194  val.first = lhs;
195 
196  std::pair<iterator, bool> ret;
197  ret = insert(val);
198 
199  assert(ret.second == true);
200 
201  it = ret.first;
202  }
203 
204  return it->second;
205  }
206 
207  template <typename K, typename T>
208  T& radix_tree<K, T>::at(const K &lhs) throw (ContainerException) {
209  iterator it = find(lhs);
210 
211  if (it == end()) {
212  THROW(ContainerException, "index is out of range");
213  }
214 
215  return it->second;
216  }
217 
218  template <typename K, typename T>
219  void radix_tree<K, T>::greedy_match(const K &key, std::vector<iterator> &vec) {
220  radix_tree_node<K, T> *node;
221 
222  vec.clear();
223 
224  if (m_root == NULL)
225  return;
226 
227  node = find_node(key, m_root, 0);
228 
229  if (node->m_is_leaf)
230  node = node->m_parent;
231 
232  greedy_match(node, vec);
233  }
234 
235  template <typename K, typename T>
236  void radix_tree<K, T>::greedy_match(radix_tree_node<K, T> *node, std::vector<iterator> &vec) {
237  if (node->m_is_leaf) {
238  vec.push_back(iterator(node));
239  return;
240  }
241 
242  typename std::map<K, radix_tree_node<K, T>*>::iterator it;
243 
244  for (it = node->m_children.begin(); it != node->m_children.end(); ++it) {
245  greedy_match(it->second, vec);
246  }
247  }
248 
249  template <typename K, typename T>
250  void radix_tree<K, T>::erase(iterator it) {
251  erase(it->first);
252  }
253 
254  template <typename K, typename T>
255  bool radix_tree<K, T>::erase(const K &key) {
256  if (m_root == NULL)
257  return 0;
258 
259  radix_tree_node<K, T> *child;
260  radix_tree_node<K, T> *parent;
261  radix_tree_node<K, T> *grandparent;
262  K nul = radix_substr(key, 0, 0);
263 
264  child = find_node(key, m_root, 0);
265 
266  if (! child->m_is_leaf)
267  return 0;
268 
269  parent = child->m_parent;
270  parent->m_children.erase(nul);
271 
272  delete child;
273 
274  m_size--;
275 
276  if (parent == m_root)
277  return 1;
278 
279  if (parent->m_children.size() > 1)
280  return 1;
281 
282  if (parent->m_children.empty()) {
283  grandparent = parent->m_parent;
284  grandparent->m_children.erase(parent->m_key);
285  delete parent;
286  } else {
287  grandparent = parent;
288  }
289 
290  if (grandparent == m_root) {
291  return 1;
292  }
293 
294  if (grandparent->m_children.size() == 1) {
295  // merge grandparent with the uncle
296  typename std::map<K, radix_tree_node<K, T>*>::iterator it;
297  it = grandparent->m_children.begin();
298 
299  radix_tree_node<K, T> *uncle = it->second;
300 
301  if (uncle->m_is_leaf)
302  return 1;
303 
304  uncle->m_depth = grandparent->m_depth;
305  uncle->m_key = radix_join(grandparent->m_key, uncle->m_key);
306  uncle->m_parent = grandparent->m_parent;
307 
308  grandparent->m_children.erase(it);
309 
310  grandparent->m_parent->m_children.erase(grandparent->m_key);
311  grandparent->m_parent->m_children[uncle->m_key] = uncle;
312 
313  delete grandparent;
314  }
315 
316  return 1;
317  }
318 
319  template <typename K, typename T>
320  radix_tree_node<K, T>* radix_tree<K, T>::append(radix_tree_node<K, T> *parent, const value_type &val) {
321  int depth;
322  int len;
323  K nul = radix_substr(val.first, 0, 0);
324  radix_tree_node<K, T> *node_c, *node_cc;
325 
326  depth = parent->m_depth + radix_length(parent->m_key);
327  len = radix_length(val.first) - depth;
328 
329  if (len == 0) {
330  node_c = new radix_tree_node<K, T>(val);
331 
332  node_c->m_depth = depth;
333  node_c->m_parent = parent;
334  node_c->m_key = nul;
335  node_c->m_is_leaf = true;
336 
337  parent->m_children[nul] = node_c;
338 
339  return node_c;
340  } else {
341  node_c = new radix_tree_node<K, T>(val);
342 
343  K key_sub = radix_substr(val.first, depth, len);
344 
345  parent->m_children[key_sub] = node_c;
346 
347  node_c->m_depth = depth;
348  node_c->m_parent = parent;
349  node_c->m_key = key_sub;
350 
351 
352  node_cc = new radix_tree_node<K, T>(val);
353  node_c->m_children[nul] = node_cc;
354 
355  node_cc->m_depth = depth + len;
356  node_cc->m_parent = node_c;
357  node_cc->m_key = nul;
358  node_cc->m_is_leaf = true;
359 
360  return node_cc;
361  }
362  }
363 
364  template <typename K, typename T>
365  radix_tree_node<K, T>* radix_tree<K, T>::prepend(radix_tree_node<K, T> *node, const value_type &val) {
366  int count;
367  int len1, len2;
368 
369  len1 = radix_length(node->m_key);
370  len2 = radix_length(val.first) - node->m_depth;
371 
372  for (count = 0; count < len1 && count < len2; count++) {
373  if (! (node->m_key[count] == val.first[count + node->m_depth]) )
374  break;
375  }
376 
377  assert(count != 0);
378 
379  node->m_parent->m_children.erase(node->m_key);
380 
381  radix_tree_node<K, T> *node_a = new radix_tree_node<K, T>;
382 
383  node_a->m_parent = node->m_parent;
384  node_a->m_key = radix_substr(node->m_key, 0, count);
385  node_a->m_depth = node->m_depth;
386  node_a->m_parent->m_children[node_a->m_key] = node_a;
387 
388 
389  node->m_depth += count;
390  node->m_parent = node_a;
391  node->m_key = radix_substr(node->m_key, count, len1 - count);
392  node->m_parent->m_children[node->m_key] = node;
393 
394  K nul = radix_substr(val.first, 0, 0);
395  if (count == len2) {
396  radix_tree_node<K, T> *node_b;
397 
398  node_b = new radix_tree_node<K, T>(val);
399 
400  node_b->m_parent = node_a;
401  node_b->m_key = nul;
402  node_b->m_depth = node_a->m_depth + count;
403  node_b->m_is_leaf = true;
404  node_b->m_parent->m_children[nul] = node_b;
405 
406  return node_b;
407  } else {
408  radix_tree_node<K, T> *node_b, *node_c;
409 
410  node_b = new radix_tree_node<K, T>;
411 
412  node_b->m_parent = node_a;
413  node_b->m_depth = node->m_depth;
414  node_b->m_key = radix_substr(val.first, node_b->m_depth, len2 - count);
415  node_b->m_parent->m_children[node_b->m_key] = node_b;
416 
417  node_c = new radix_tree_node<K, T>(val);
418 
419  node_c->m_parent = node_b;
420  node_c->m_depth = radix_length(val.first);
421  node_c->m_key = nul;
422  node_c->m_is_leaf = true;
423  node_c->m_parent->m_children[nul] = node_c;
424 
425  return node_c;
426  }
427  }
428 
429  template <typename K, typename T>
430  std::pair<typename radix_tree<K, T>::iterator, bool> radix_tree<K, T>::insert(const value_type &val) {
431  if (m_root == NULL) {
432  K nul = radix_substr(val.first, 0, 0);
433 
434  m_root = new radix_tree_node<K, T>;
435  m_root->m_key = nul;
436  }
437 
438 
439  radix_tree_node<K, T> *node = find_node(val.first, m_root, 0);
440 
441  if (node->m_is_leaf) {
442  return std::pair<iterator, bool>(node, false);
443  } else if (node == m_root) {
444  m_size++;
445  return std::pair<iterator, bool>(append(m_root, val), true);
446  } else {
447  m_size++;
448  int len = radix_length(node->m_key);
449  K key_sub = radix_substr(val.first, node->m_depth, len);
450 
451  if (key_sub == node->m_key) {
452  return std::pair<iterator, bool>(append(node, val), true);
453  } else {
454  return std::pair<iterator, bool>(prepend(node, val), true);
455  }
456  }
457  }
458 
459  template <typename K, typename T>
460  typename radix_tree<K, T>::iterator radix_tree<K, T>::find(const K &key) {
461  if (m_root == NULL)
462  return iterator(NULL);
463 
464  radix_tree_node<K, T> *node = find_node(key, m_root, 0);
465 
466  // if the node is a internal node, return NULL
467  if (! node->m_is_leaf)
468  return iterator(NULL);
469 
470  return iterator(node);
471  }
472 
473  template <typename K, typename T>
474  radix_tree_node<K, T>* radix_tree<K, T>::find_node(const K &key, radix_tree_node<K, T> *node, int depth) {
475  for (;;) {
476 cont:
477  if (node->m_children.empty())
478  return node;
479 
480  typename radix_tree_node<K, T>::it_child it;
481  int len_key = radix_length(key) - depth;
482 
483  for (it = node->m_children.begin(); it != node->m_children.end(); ++it) {
484  if (len_key == 0) {
485  if (it->second->m_is_leaf)
486  return it->second;
487  else
488  continue;
489  }
490 
491  if (! it->second->m_is_leaf && key[depth] == it->first[0] ) {
492  int len_node = radix_length(it->first);
493  K key_sub = radix_substr(key, depth, len_node);
494 
495  if (key_sub == it->first) {
496  node = it->second;
497  depth += len_node;
498  goto cont;
499  } else {
500  return it->second;
501  }
502  }
503  }
504 
505  return node;
506  }
507  }
508  }
509 }
510 
511 /*
512 
513 (root)
514 |
515 |---------------
516 | | |
517 abcde bcdef c
518 | | | |------
519 | | $3 | | |
520 f ge d e $6
521 | | | |
522 $1 $2 $4 $5
523 
524 find_node():
525  bcdef -> $3
526  bcdefa -> bcdef
527  c -> $6
528  cf -> c
529  abch -> abcde
530  abc -> abcde
531  abcde -> abcde
532  abcdef -> $1
533  abcdeh -> abcde
534  de -> (root)
535 
536 
537 (root)
538 |
539 abcd
540 |
541 $
542 
543 (root)
544 |
545 $
546 
547 */
548 
549 #endif
550 
551 /*
552 ** vim: noet ts=3 sw=3
553 */
sella::container::radix_tree_it
Definition: radix_tree_it.h:21
sella::container::radix_tree
Definition: radix_tree.h:50
sella::container::radix_tree_node
Definition: radix_tree_it.h:18
Generated on Sat Sep 2 2017 11:44:21 for libutil++ by   doxygen 1.8.5