map.h
1 /*************************************************************************/
2 /* map.h */
3 /*************************************************************************/
4 /* This file is part of: */
5 /* GODOT ENGINE */
6 /* http://www.godotengine.org */
7 /*************************************************************************/
8 /* Copyright (c) 2007-2016 Juan Linietsky, Ariel Manzur. */
9 /* */
10 /* Permission is hereby granted, free of charge, to any person obtaining */
11 /* a copy of this software and associated documentation files (the */
12 /* "Software"), to deal in the Software without restriction, including */
13 /* without limitation the rights to use, copy, modify, merge, publish, */
14 /* distribute, sublicense, and/or sell copies of the Software, and to */
15 /* permit persons to whom the Software is furnished to do so, subject to */
16 /* the following conditions: */
17 /* */
18 /* The above copyright notice and this permission notice shall be */
19 /* included in all copies or substantial portions of the Software. */
20 /* */
21 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */
22 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */
23 /* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/
24 /* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */
25 /* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */
26 /* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */
27 /* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */
28 /*************************************************************************/
29 #ifndef MAP_H
30 #define MAP_H
31 
32 #include "set.h"
37 // based on the very nice implementation of rb-trees by:
38 // http://web.mit.edu/~emin/www/source_code/red_black_tree/index.html
39 
40 template <class K,class V,class C=Comparator<K>,class A=DefaultAllocator>
41 class Map {
42 
43  enum Color {
44  RED,
45  BLACK
46  };
47  struct _Data;
48 public:
49 
50  class Element {
51 
52  private:
53  friend class Map<K,V,C,A>;
54  //Color color;
55  int color;
56  Element* right;
57  Element* left;
58  Element* parent;
59  Element* _next;
60  Element* _prev;
61  K _key;
62  V _value;
63 
64  //_Data *data;
65 
66  public:
67 
68  const Element *next() const {
69 
70  return _next;
71  }
72  Element *next() {
73 
74  return _next;
75  }
76  const Element *prev() const {
77 
78  return _prev;
79  }
80  Element *prev() {
81 
82  return _prev;
83  }
84  const K& key() const {
85  return _key;
86  };
87  V& value() {
88  return _value;
89  };
90  const V& value() const {
91  return _value;
92  };
93  V& get() {
94  return _value;
95  };
96  const V& get() const {
97  return _value;
98  };
99  Element() {
100  color=RED;
101  right=NULL;
102  left=NULL;
103  parent=NULL;
104  _next=NULL;
105  _prev=NULL;
106  };
107  };
108 
109 
110 private:
111 
112  struct _Data {
113 
114  Element* _root;
115  Element* _nil;
116  int size_cache;
117 
118  _FORCE_INLINE_ _Data() {
119 #ifdef GLOBALNIL_DISABLED
120  _nil = memnew_allocator( Element, A );
121  _nil->parent=_nil->left=_nil->right=_nil;
122  _nil->color=BLACK;
123 #else
124  _nil=(Element*)&_GlobalNilClass::_nil;
125 #endif
126  _root=NULL;
127  size_cache=0;
128  }
129 
130  void _create_root() {
131 
132  _root = memnew_allocator( Element,A );
133  _root->parent=_root->left=_root->right=_nil;
134  _root->color=BLACK;
135  }
136 
137  void _free_root() {
138 
139  if (_root) {
140  memdelete_allocator<Element,A>(_root);
141  _root=NULL;
142  }
143  }
144 
145  ~_Data() {
146 
147  _free_root();
148 
149 #ifdef GLOBALNIL_DISABLED
150  memdelete_allocator<Element,A>(_nil);
151 #endif
152 // memdelete_allocator<Element,A>(_root);
153  }
154  };
155 
156  _Data _data;
157 
158  inline void _set_color(Element *p_node, int p_color) {
159 
160  ERR_FAIL_COND( p_node == _data._nil && p_color == RED );
161  p_node->color=p_color;
162  }
163  inline void _rotate_left(Element *p_node) {
164 
165  Element *r=p_node->right;
166  p_node->right=r->left;
167  if (r->left != _data._nil )
168  r->left->parent=p_node;
169  r->parent=p_node->parent;
170  if (p_node==p_node->parent->left)
171  p_node->parent->left=r;
172  else
173  p_node->parent->right=r;
174 
175  r->left=p_node;
176  p_node->parent=r;
177 
178  }
179 
180  inline void _rotate_right(Element *p_node) {
181 
182  Element *l=p_node->left;
183  p_node->left=l->right;
184  if (l->right != _data._nil)
185  l->right->parent=p_node;
186  l->parent=p_node->parent;
187  if (p_node==p_node->parent->right)
188  p_node->parent->right=l;
189  else
190  p_node->parent->left=l;
191 
192  l->right=p_node;
193  p_node->parent=l;
194 
195  }
196 
197  inline Element* _successor(Element *p_node) const {
198 
199  Element *node=p_node;
200 
201  if (node->right != _data._nil) {
202 
203  node=node->right;
204  while(node->left != _data._nil) { /* returns the minium of the right subtree of node */
205  node=node->left;
206  }
207  return node;
208  } else {
209 
210  while(node == node->parent->right) {
211  node=node->parent;
212  }
213  if (node->parent == _data._root)
214  return NULL;
215  return node->parent;
216  }
217  }
218 
219  inline Element* _predecessor(Element *p_node) const {
220  Element *node=p_node;
221 
222  if (node->left != _data._nil) {
223 
224  node=node->left;
225  while(node->right != _data._nil) { /* returns the minium of the left subtree of node */
226  node=node->right;
227  }
228  return node;
229  } else {
230 
231  while(node == node->parent->left) {
232  if (node->parent == _data._root)
233  return NULL;
234  node=node->parent;
235  }
236  return node->parent;
237  }
238  }
239 
240 
241  Element *_find(const K& p_key) const {
242 
243  Element *node = _data._root->left;
244  C less;
245 
246  while(node!=_data._nil) {
247 
248  if (less(p_key,node->_key))
249  node=node->left;
250  else if (less(node->_key,p_key))
251  node=node->right;
252  else
253  break; // found
254  }
255 
256  return (node!=_data._nil)?node:NULL;
257  }
258 
259  Element *_find_closest(const K& p_key) const {
260 
261  Element *node = _data._root->left;
262  Element *prev = NULL;
263  C less;
264 
265  while(node!=_data._nil) {
266  prev=node;
267 
268  if (less(p_key,node->_key))
269  node=node->left;
270  else if (less(node->_key,p_key))
271  node=node->right;
272  else
273  break; // found
274  }
275 
276  if (node==_data._nil) {
277  if (prev==NULL)
278  return NULL;
279  if (less(p_key,prev->_key)) {
280 
281  prev=prev->_prev;
282  }
283 
284  return prev;
285 
286  } else
287  return node;
288 
289  }
290 
291  Element *_insert(const K& p_key, bool& r_exists) {
292 
293  Element *new_parent=_data._root;
294  Element *node = _data._root->left;
295  C less;
296 
297  while (node!=_data._nil) {
298 
299  new_parent=node;
300 
301  if (less(p_key,node->_key))
302  node=node->left;
303  else if (less(node->_key,p_key))
304  node=node->right;
305  else {
306  r_exists=true;
307  return node;
308  }
309  }
310 
311  Element *new_node = memnew_allocator( Element, A );
312 
313 
314  new_node->parent=new_parent;
315  new_node->right=_data._nil;
316  new_node->left=_data._nil;
317  new_node->_key=p_key;
318  //new_node->data=_data;
319  if (new_parent==_data._root || less(p_key,new_parent->_key)) {
320 
321  new_parent->left=new_node;
322  } else {
323  new_parent->right=new_node;
324  }
325 
326  r_exists=false;
327 
328  new_node->_next=_successor(new_node);
329  new_node->_prev=_predecessor(new_node);
330  if (new_node->_next)
331  new_node->_next->_prev=new_node;
332  if (new_node->_prev)
333  new_node->_prev->_next=new_node;
334 
335 
336  return new_node;
337  }
338 
339  Element * _insert_rb(const K& p_key, const V& p_value) {
340 
341  bool exists=false;
342  Element *new_node = _insert(p_key,exists);
343 
344  if (new_node) {
345  new_node->_value=p_value;
346  }
347  if (exists)
348  return new_node;
349 
350  Element *node=new_node;
351  _data.size_cache++;
352 
353  while(node->parent->color==RED) {
354 
355  if (node->parent == node->parent->parent->left) {
356 
357  Element *aux=node->parent->parent->right;
358 
359  if (aux->color==RED) {
360  _set_color(node->parent,BLACK);
361  _set_color(aux,BLACK);
362  _set_color(node->parent->parent,RED);
363  node=node->parent->parent;
364  } else {
365  if (node == node->parent->right) {
366  node=node->parent;
367  _rotate_left(node);
368  }
369  _set_color(node->parent,BLACK);
370  _set_color(node->parent->parent,RED);
371  _rotate_right(node->parent->parent);
372  }
373  } else {
374  Element *aux=node->parent->parent->left;
375 
376  if (aux->color==RED) {
377  _set_color(node->parent,BLACK);
378  _set_color(aux,BLACK);
379  _set_color(node->parent->parent,RED);
380  node=node->parent->parent;
381  } else {
382  if (node == node->parent->left) {
383  node=node->parent;
384  _rotate_right(node);
385  }
386  _set_color(node->parent,BLACK);
387  _set_color(node->parent->parent,RED);
388  _rotate_left(node->parent->parent);
389  }
390  }
391  }
392  _set_color(_data._root->left,BLACK);
393  return new_node;
394  }
395 
396  void _erase_fix(Element *p_node) {
397 
398  Element *root = _data._root->left;
399  Element *node=p_node;
400 
401 
402  while( (node->color==BLACK) && (root != node)) {
403  if (node == node->parent->left) {
404  Element *aux=node->parent->right;
405  if (aux->color==RED) {
406  _set_color(aux,BLACK);
407  _set_color(node->parent,RED);
408  _rotate_left(node->parent);
409  aux=node->parent->right;
410  }
411  if ( (aux->right->color==BLACK) && (aux->left->color==BLACK) ) {
412  _set_color(aux,RED);
413  node=node->parent;
414  } else {
415  if (aux->right->color==BLACK) {
416  _set_color(aux->left,BLACK);
417  _set_color(aux,RED);
418  _rotate_right(aux);
419  aux=node->parent->right;
420  }
421  _set_color(aux,node->parent->color);
422  _set_color(node->parent,BLACK);
423  _set_color(aux->right,BLACK);
424  _rotate_left(node->parent);
425  node=root; /* this is to exit while loop */
426  }
427  } else { /* the code below is has left and right switched from above */
428  Element *aux=node->parent->left;
429  if (aux->color==RED) {
430  _set_color(aux,BLACK);
431  _set_color(node->parent,RED);;
432  _rotate_right(node->parent);
433  aux=node->parent->left;
434  }
435  if ( (aux->right->color==BLACK) && (aux->left->color==BLACK) ) {
436  _set_color(aux,RED);
437  node=node->parent;
438  } else {
439  if (aux->left->color==BLACK) {
440  _set_color(aux->right,BLACK);
441  _set_color(aux,RED);
442  _rotate_left(aux);
443  aux=node->parent->left;
444  }
445  _set_color(aux,node->parent->color);
446  _set_color(node->parent,BLACK);
447  _set_color(aux->left,BLACK);
448  _rotate_right(node->parent);
449  node=root;
450  }
451  }
452  }
453 
454  _set_color(node,BLACK);
455 
456  ERR_FAIL_COND(_data._nil->color!=BLACK);
457  }
458 
459  void _erase(Element *p_node) {
460 
461 
462  Element *rp= ((p_node->left == _data._nil) || (p_node->right == _data._nil)) ? p_node : _successor(p_node);
463  if (!rp)
464  rp=_data._nil;
465  Element *node= (rp->left == _data._nil) ? rp->right : rp->left;
466 
467  if (_data._root == (node->parent=rp->parent) ) {
468  _data._root->left=node;
469  } else {
470  if (rp == rp->parent->left) {
471  rp->parent->left=node;
472  } else {
473  rp->parent->right=node;
474  }
475  }
476 
477  if (rp != p_node) {
478 
479  ERR_FAIL_COND( rp == _data._nil );
480 
481  if (rp->color==BLACK)
482  _erase_fix(node);
483 
484 
485  rp->left=p_node->left;
486  rp->right=p_node->right;
487  rp->parent=p_node->parent;
488  rp->color=p_node->color;
489  p_node->left->parent=rp;
490  p_node->right->parent=rp;
491 
492  if (p_node == p_node->parent->left) {
493  p_node->parent->left=rp;
494  } else {
495  p_node->parent->right=rp;
496  }
497  } else {
498  if (p_node->color==BLACK)
499  _erase_fix(node);
500 
501  }
502 
503 
504  if (p_node->_next)
505  p_node->_next->_prev=p_node->_prev;
506  if (p_node->_prev)
507  p_node->_prev->_next=p_node->_next;
508 
509  memdelete_allocator<Element,A>(p_node);
510  _data.size_cache--;
511  ERR_FAIL_COND( _data._nil->color==RED );
512  }
513 
514 
515  void _calculate_depth(Element *p_element,int &max_d,int d) const {
516 
517  if (p_element==_data._nil) {
518  return;
519  }
520  _calculate_depth(p_element->left,max_d,d+1);
521  _calculate_depth(p_element->right,max_d,d+1);
522  if (d>max_d)
523  max_d=d;
524  }
525 
526  void _cleanup_tree(Element *p_element) {
527 
528  if (p_element==_data._nil)
529  return;
530 
531  _cleanup_tree(p_element->left);
532  _cleanup_tree(p_element->right);
533  memdelete_allocator<Element,A>( p_element );
534  }
535 
536  void _copy_from( const Map& p_map) {
537 
538  clear();
539  // not the fastest way, but safeset to write.
540  for(Element *I=p_map.front();I;I=I->next()) {
541 
542  insert(I->key(),I->value());
543  }
544  }
545 public:
546 
547  const Element *find(const K& p_key) const {
548 
549  if (!_data._root)
550  return NULL;
551 
552  const Element *res=_find(p_key);
553  return res;
554  }
555 
556  Element *find(const K& p_key) {
557 
558  if (!_data._root)
559  return NULL;
560  Element *res=_find(p_key);
561  return res;
562  }
563 
564  const Element *find_closest(const K& p_key) const {
565 
566  if (!_data._root)
567  return NULL;
568  const Element *res=_find_closest(p_key);
569  return res;
570  }
571 
572  Element *find_closest(const K& p_key) {
573 
574  if (!_data._root)
575  return NULL;
576  Element *res=_find_closest(p_key);
577  return res;
578  }
579 
580  Element *insert(const K& p_key,const V& p_value) {
581 
582  if (!_data._root)
583  _data._create_root();
584  return _insert_rb(p_key,p_value);
585 
586  }
587 
588  void erase(Element* p_element) {
589 
590  if (!_data._root)
591  return;
592  _erase(p_element);
593  if (_data.size_cache==0 && _data._root)
594  _data._free_root();
595  }
596 
597  bool erase(const K& p_key) {
598 
599  if (!_data._root)
600  return false;
601  Element *e=find(p_key);
602  if (!e)
603  return false;
604  _erase(e);
605  return true;
606  }
607 
608  bool has(const K& p_key) const {
609 
610  if (!_data._root)
611  return false;
612  return find(p_key) != NULL;
613  }
614 
615  const V& operator[](const K& p_key) const {
616 
617  ERR_FAIL_COND_V(!_data._root, *(V*)NULL); // crash on purpose
618  const Element *e=find(p_key);
619  ERR_FAIL_COND_V(!e, *(V*)NULL); // crash on purpose
620  return e->_value;
621  }
622  V& operator[](const K& p_key) {
623 
624  if (!_data._root)
625  _data._create_root();
626 
627  Element *e=find(p_key);
628  if (!e)
629  e=insert(p_key,V());
630 
631  ERR_FAIL_COND_V(!e, *(V*)NULL); // crash on purpose
632  return e->_value;
633  }
634 
635  Element *front() const {
636 
637  if (!_data._root)
638  return NULL;
639 
640  Element *e=_data._root->left;
641  if (e==_data._nil)
642  return NULL;
643 
644  while(e->left!=_data._nil)
645  e=e->left;
646 
647  return e;
648  }
649 
650  Element *back() const {
651 
652  if (!_data._root)
653  return NULL;
654  Element *e=_data._root->left;
655  if (e==_data._nil)
656  return NULL;
657 
658  while(e->right!=_data._nil)
659  e=e->right;
660 
661  return e;
662  }
663 
664  inline bool empty() const { return _data.size_cache==0; }
665  inline int size() const { return _data.size_cache; }
666  int calculate_depth() const {
667  // used for debug mostly
668  if (!_data._root)
669  return 0;
670  int max_d=0;
671  _calculate_depth(_data._root->left,max_d,0);
672  return max_d;
673  }
674 
675  void clear() {
676 
677  if (!_data._root)
678  return;
679  _cleanup_tree(_data._root->left);
680  _data._root->left=_data._nil;
681  _data.size_cache=0;
682  _data._nil->parent=_data._nil;
683  _data._free_root();
684  }
685 
686  void operator=(const Map& p_map) {
687 
688  _copy_from( p_map );
689  }
690 
691  Map(const Map& p_map) {
692 
693  _copy_from( p_map );
694  }
695 
696  _FORCE_INLINE_ Map() {
697 
698  }
699 
700 
701  ~Map() {
702 
703  clear();
704  }
705 
706 };
707 
708 #endif
Color
Definition: color.h:37
Map::Element
Definition: map.h:50
back
Definition: tween_interpolaters.cpp:356
Map
Definition: map.h:41
Generated on Wed Jul 13 2016 13:20:59 by   doxygen 1.8.11