summaryrefslogtreecommitdiff
path: root/core/map.h
diff options
context:
space:
mode:
Diffstat (limited to 'core/map.h')
-rw-r--r--core/map.h507
1 files changed, 244 insertions, 263 deletions
diff --git a/core/map.h b/core/map.h
index d1a4c209ad..e9700ff371 100644
--- a/core/map.h
+++ b/core/map.h
@@ -37,7 +37,7 @@
// based on the very nice implementation of rb-trees by:
// http://web.mit.edu/~emin/www/source_code/red_black_tree/index.html
-template <class K,class V,class C=Comparator<K>,class A=DefaultAllocator>
+template <class K, class V, class C = Comparator<K>, class A = DefaultAllocator>
class Map {
enum Color {
@@ -45,26 +45,25 @@ class Map {
BLACK
};
struct _Data;
-public:
+public:
class Element {
private:
- friend class Map<K,V,C,A>;
+ friend class Map<K, V, C, A>;
//Color color;
int color;
- Element* right;
- Element* left;
- Element* parent;
- Element* _next;
- Element* _prev;
+ Element *right;
+ Element *left;
+ Element *parent;
+ Element *_next;
+ Element *_prev;
K _key;
V _value;
//_Data *data;
public:
-
const Element *next() const {
return _next;
@@ -81,64 +80,62 @@ public:
return _prev;
}
- const K& key() const {
+ const K &key() const {
return _key;
};
- V& value() {
+ V &value() {
return _value;
};
- const V& value() const {
+ const V &value() const {
return _value;
};
- V& get() {
+ V &get() {
return _value;
};
- const V& get() const {
+ const V &get() const {
return _value;
};
Element() {
- color=RED;
- right=NULL;
- left=NULL;
- parent=NULL;
- _next=NULL;
- _prev=NULL;
+ color = RED;
+ right = NULL;
+ left = NULL;
+ parent = NULL;
+ _next = NULL;
+ _prev = NULL;
};
};
-
private:
-
struct _Data {
- Element* _root;
- Element* _nil;
+ Element *_root;
+ Element *_nil;
int size_cache;
_FORCE_INLINE_ _Data() {
#ifdef GLOBALNIL_DISABLED
- _nil = memnew_allocator( Element, A );
- _nil->parent=_nil->left=_nil->right=_nil;
- _nil->color=BLACK;
+ _nil = memnew_allocator(Element, A);
+ _nil->parent = _nil->left = _nil->right = _nil;
+ _nil->color = BLACK;
#else
- _nil=(Element*)&_GlobalNilClass::_nil;
+ _nil = (Element *)&_GlobalNilClass::_nil;
#endif
- _root=NULL;
- size_cache=0;
+ _root = NULL;
+ size_cache = 0;
}
void _create_root() {
- _root = memnew_allocator( Element,A );
- _root->parent=_root->left=_root->right=_nil;
- _root->color=BLACK;
+ _root = memnew_allocator(Element, A);
+ _root->parent = _root->left = _root->right = _nil;
+ _root->color = BLACK;
}
void _free_root() {
if (_root) {
- memdelete_allocator<Element,A>(_root);
- _root=NULL;
+ memdelete_allocator<Element, A>(_root);
+ _root = NULL;
}
}
@@ -147,7 +144,7 @@ private:
_free_root();
#ifdef GLOBALNIL_DISABLED
- memdelete_allocator<Element,A>(_nil);
+ memdelete_allocator<Element, A>(_nil);
#endif
//memdelete_allocator<Element,A>(_root);
}
@@ -157,58 +154,56 @@ private:
inline void _set_color(Element *p_node, int p_color) {
- ERR_FAIL_COND( p_node == _data._nil && p_color == RED );
- p_node->color=p_color;
+ ERR_FAIL_COND(p_node == _data._nil && p_color == RED);
+ p_node->color = p_color;
}
inline void _rotate_left(Element *p_node) {
- Element *r=p_node->right;
- p_node->right=r->left;
- if (r->left != _data._nil )
- r->left->parent=p_node;
- r->parent=p_node->parent;
- if (p_node==p_node->parent->left)
- p_node->parent->left=r;
+ Element *r = p_node->right;
+ p_node->right = r->left;
+ if (r->left != _data._nil)
+ r->left->parent = p_node;
+ r->parent = p_node->parent;
+ if (p_node == p_node->parent->left)
+ p_node->parent->left = r;
else
- p_node->parent->right=r;
-
- r->left=p_node;
- p_node->parent=r;
+ p_node->parent->right = r;
+ r->left = p_node;
+ p_node->parent = r;
}
inline void _rotate_right(Element *p_node) {
- Element *l=p_node->left;
- p_node->left=l->right;
+ Element *l = p_node->left;
+ p_node->left = l->right;
if (l->right != _data._nil)
- l->right->parent=p_node;
- l->parent=p_node->parent;
- if (p_node==p_node->parent->right)
- p_node->parent->right=l;
+ l->right->parent = p_node;
+ l->parent = p_node->parent;
+ if (p_node == p_node->parent->right)
+ p_node->parent->right = l;
else
- p_node->parent->left=l;
-
- l->right=p_node;
- p_node->parent=l;
+ p_node->parent->left = l;
+ l->right = p_node;
+ p_node->parent = l;
}
- inline Element* _successor(Element *p_node) const {
+ inline Element *_successor(Element *p_node) const {
- Element *node=p_node;
+ Element *node = p_node;
if (node->right != _data._nil) {
- node=node->right;
- while(node->left != _data._nil) { /* returns the minium of the right subtree of node */
- node=node->left;
+ node = node->right;
+ while (node->left != _data._nil) { /* returns the minium of the right subtree of node */
+ node = node->left;
}
return node;
} else {
- while(node == node->parent->right) {
- node=node->parent;
+ while (node == node->parent->right) {
+ node = node->parent;
}
if (node->parent == _data._root)
return NULL;
@@ -216,419 +211,408 @@ private:
}
}
- inline Element* _predecessor(Element *p_node) const {
- Element *node=p_node;
+ inline Element *_predecessor(Element *p_node) const {
+ Element *node = p_node;
if (node->left != _data._nil) {
- node=node->left;
- while(node->right != _data._nil) { /* returns the minium of the left subtree of node */
- node=node->right;
+ node = node->left;
+ while (node->right != _data._nil) { /* returns the minium of the left subtree of node */
+ node = node->right;
}
return node;
} else {
- while(node == node->parent->left) {
+ while (node == node->parent->left) {
if (node->parent == _data._root)
return NULL;
- node=node->parent;
+ node = node->parent;
}
return node->parent;
}
}
-
- Element *_find(const K& p_key) const {
+ Element *_find(const K &p_key) const {
Element *node = _data._root->left;
C less;
- while(node!=_data._nil) {
+ while (node != _data._nil) {
- if (less(p_key,node->_key))
- node=node->left;
- else if (less(node->_key,p_key))
- node=node->right;
+ if (less(p_key, node->_key))
+ node = node->left;
+ else if (less(node->_key, p_key))
+ node = node->right;
else
break; // found
}
- return (node!=_data._nil)?node:NULL;
+ return (node != _data._nil) ? node : NULL;
}
- Element *_find_closest(const K& p_key) const {
+ Element *_find_closest(const K &p_key) const {
Element *node = _data._root->left;
Element *prev = NULL;
C less;
- while(node!=_data._nil) {
- prev=node;
+ while (node != _data._nil) {
+ prev = node;
- if (less(p_key,node->_key))
- node=node->left;
- else if (less(node->_key,p_key))
- node=node->right;
+ if (less(p_key, node->_key))
+ node = node->left;
+ else if (less(node->_key, p_key))
+ node = node->right;
else
break; // found
}
- if (node==_data._nil) {
- if (prev==NULL)
+ if (node == _data._nil) {
+ if (prev == NULL)
return NULL;
- if (less(p_key,prev->_key)) {
+ if (less(p_key, prev->_key)) {
- prev=prev->_prev;
+ prev = prev->_prev;
}
return prev;
} else
return node;
-
}
- Element *_insert(const K& p_key, bool& r_exists) {
+ Element *_insert(const K &p_key, bool &r_exists) {
- Element *new_parent=_data._root;
+ Element *new_parent = _data._root;
Element *node = _data._root->left;
C less;
- while (node!=_data._nil) {
+ while (node != _data._nil) {
- new_parent=node;
+ new_parent = node;
- if (less(p_key,node->_key))
- node=node->left;
- else if (less(node->_key,p_key))
- node=node->right;
+ if (less(p_key, node->_key))
+ node = node->left;
+ else if (less(node->_key, p_key))
+ node = node->right;
else {
- r_exists=true;
+ r_exists = true;
return node;
}
}
- Element *new_node = memnew_allocator( Element, A );
+ Element *new_node = memnew_allocator(Element, A);
-
- new_node->parent=new_parent;
- new_node->right=_data._nil;
- new_node->left=_data._nil;
- new_node->_key=p_key;
+ new_node->parent = new_parent;
+ new_node->right = _data._nil;
+ new_node->left = _data._nil;
+ new_node->_key = p_key;
//new_node->data=_data;
- if (new_parent==_data._root || less(p_key,new_parent->_key)) {
+ if (new_parent == _data._root || less(p_key, new_parent->_key)) {
- new_parent->left=new_node;
+ new_parent->left = new_node;
} else {
- new_parent->right=new_node;
+ new_parent->right = new_node;
}
- r_exists=false;
+ r_exists = false;
- new_node->_next=_successor(new_node);
- new_node->_prev=_predecessor(new_node);
+ new_node->_next = _successor(new_node);
+ new_node->_prev = _predecessor(new_node);
if (new_node->_next)
- new_node->_next->_prev=new_node;
+ new_node->_next->_prev = new_node;
if (new_node->_prev)
- new_node->_prev->_next=new_node;
-
+ new_node->_prev->_next = new_node;
return new_node;
}
- Element * _insert_rb(const K& p_key, const V& p_value) {
+ Element *_insert_rb(const K &p_key, const V &p_value) {
- bool exists=false;
- Element *new_node = _insert(p_key,exists);
+ bool exists = false;
+ Element *new_node = _insert(p_key, exists);
if (new_node) {
- new_node->_value=p_value;
+ new_node->_value = p_value;
}
if (exists)
return new_node;
- Element *node=new_node;
+ Element *node = new_node;
_data.size_cache++;
- while(node->parent->color==RED) {
+ while (node->parent->color == RED) {
if (node->parent == node->parent->parent->left) {
- Element *aux=node->parent->parent->right;
+ Element *aux = node->parent->parent->right;
- if (aux->color==RED) {
- _set_color(node->parent,BLACK);
- _set_color(aux,BLACK);
- _set_color(node->parent->parent,RED);
- node=node->parent->parent;
+ if (aux->color == RED) {
+ _set_color(node->parent, BLACK);
+ _set_color(aux, BLACK);
+ _set_color(node->parent->parent, RED);
+ node = node->parent->parent;
} else {
if (node == node->parent->right) {
- node=node->parent;
+ node = node->parent;
_rotate_left(node);
}
- _set_color(node->parent,BLACK);
- _set_color(node->parent->parent,RED);
+ _set_color(node->parent, BLACK);
+ _set_color(node->parent->parent, RED);
_rotate_right(node->parent->parent);
}
} else {
- Element *aux=node->parent->parent->left;
+ Element *aux = node->parent->parent->left;
- if (aux->color==RED) {
- _set_color(node->parent,BLACK);
- _set_color(aux,BLACK);
- _set_color(node->parent->parent,RED);
- node=node->parent->parent;
+ if (aux->color == RED) {
+ _set_color(node->parent, BLACK);
+ _set_color(aux, BLACK);
+ _set_color(node->parent->parent, RED);
+ node = node->parent->parent;
} else {
if (node == node->parent->left) {
- node=node->parent;
+ node = node->parent;
_rotate_right(node);
}
- _set_color(node->parent,BLACK);
- _set_color(node->parent->parent,RED);
+ _set_color(node->parent, BLACK);
+ _set_color(node->parent->parent, RED);
_rotate_left(node->parent->parent);
}
}
}
- _set_color(_data._root->left,BLACK);
+ _set_color(_data._root->left, BLACK);
return new_node;
}
void _erase_fix(Element *p_node) {
Element *root = _data._root->left;
- Element *node=p_node;
-
+ Element *node = p_node;
- while( (node->color==BLACK) && (root != node)) {
+ while ((node->color == BLACK) && (root != node)) {
if (node == node->parent->left) {
- Element *aux=node->parent->right;
- if (aux->color==RED) {
- _set_color(aux,BLACK);
- _set_color(node->parent,RED);
+ Element *aux = node->parent->right;
+ if (aux->color == RED) {
+ _set_color(aux, BLACK);
+ _set_color(node->parent, RED);
_rotate_left(node->parent);
- aux=node->parent->right;
+ aux = node->parent->right;
}
- if ( (aux->right->color==BLACK) && (aux->left->color==BLACK) ) {
- _set_color(aux,RED);
- node=node->parent;
+ if ((aux->right->color == BLACK) && (aux->left->color == BLACK)) {
+ _set_color(aux, RED);
+ node = node->parent;
} else {
- if (aux->right->color==BLACK) {
- _set_color(aux->left,BLACK);
- _set_color(aux,RED);
+ if (aux->right->color == BLACK) {
+ _set_color(aux->left, BLACK);
+ _set_color(aux, RED);
_rotate_right(aux);
- aux=node->parent->right;
+ aux = node->parent->right;
}
- _set_color(aux,node->parent->color);
- _set_color(node->parent,BLACK);
- _set_color(aux->right,BLACK);
+ _set_color(aux, node->parent->color);
+ _set_color(node->parent, BLACK);
+ _set_color(aux->right, BLACK);
_rotate_left(node->parent);
- node=root; /* this is to exit while loop */
+ node = root; /* this is to exit while loop */
}
} else { /* the code below is has left and right switched from above */
- Element *aux=node->parent->left;
- if (aux->color==RED) {
- _set_color(aux,BLACK);
- _set_color(node->parent,RED);
+ Element *aux = node->parent->left;
+ if (aux->color == RED) {
+ _set_color(aux, BLACK);
+ _set_color(node->parent, RED);
_rotate_right(node->parent);
- aux=node->parent->left;
+ aux = node->parent->left;
}
- if ( (aux->right->color==BLACK) && (aux->left->color==BLACK) ) {
- _set_color(aux,RED);
- node=node->parent;
+ if ((aux->right->color == BLACK) && (aux->left->color == BLACK)) {
+ _set_color(aux, RED);
+ node = node->parent;
} else {
- if (aux->left->color==BLACK) {
- _set_color(aux->right,BLACK);
- _set_color(aux,RED);
+ if (aux->left->color == BLACK) {
+ _set_color(aux->right, BLACK);
+ _set_color(aux, RED);
_rotate_left(aux);
- aux=node->parent->left;
+ aux = node->parent->left;
}
- _set_color(aux,node->parent->color);
- _set_color(node->parent,BLACK);
- _set_color(aux->left,BLACK);
+ _set_color(aux, node->parent->color);
+ _set_color(node->parent, BLACK);
+ _set_color(aux->left, BLACK);
_rotate_right(node->parent);
- node=root;
+ node = root;
}
}
}
- _set_color(node,BLACK);
+ _set_color(node, BLACK);
- ERR_FAIL_COND(_data._nil->color!=BLACK);
+ ERR_FAIL_COND(_data._nil->color != BLACK);
}
void _erase(Element *p_node) {
-
- Element *rp= ((p_node->left == _data._nil) || (p_node->right == _data._nil)) ? p_node : _successor(p_node);
+ Element *rp = ((p_node->left == _data._nil) || (p_node->right == _data._nil)) ? p_node : _successor(p_node);
if (!rp)
- rp=_data._nil;
- Element *node= (rp->left == _data._nil) ? rp->right : rp->left;
+ rp = _data._nil;
+ Element *node = (rp->left == _data._nil) ? rp->right : rp->left;
- if (_data._root == (node->parent=rp->parent) ) {
- _data._root->left=node;
+ if (_data._root == (node->parent = rp->parent)) {
+ _data._root->left = node;
} else {
if (rp == rp->parent->left) {
- rp->parent->left=node;
+ rp->parent->left = node;
} else {
- rp->parent->right=node;
+ rp->parent->right = node;
}
}
if (rp != p_node) {
- ERR_FAIL_COND( rp == _data._nil );
+ ERR_FAIL_COND(rp == _data._nil);
- if (rp->color==BLACK)
+ if (rp->color == BLACK)
_erase_fix(node);
-
- rp->left=p_node->left;
- rp->right=p_node->right;
- rp->parent=p_node->parent;
- rp->color=p_node->color;
- p_node->left->parent=rp;
- p_node->right->parent=rp;
+ rp->left = p_node->left;
+ rp->right = p_node->right;
+ rp->parent = p_node->parent;
+ rp->color = p_node->color;
+ p_node->left->parent = rp;
+ p_node->right->parent = rp;
if (p_node == p_node->parent->left) {
- p_node->parent->left=rp;
+ p_node->parent->left = rp;
} else {
- p_node->parent->right=rp;
+ p_node->parent->right = rp;
}
} else {
- if (p_node->color==BLACK)
+ if (p_node->color == BLACK)
_erase_fix(node);
-
}
-
if (p_node->_next)
- p_node->_next->_prev=p_node->_prev;
+ p_node->_next->_prev = p_node->_prev;
if (p_node->_prev)
- p_node->_prev->_next=p_node->_next;
+ p_node->_prev->_next = p_node->_next;
- memdelete_allocator<Element,A>(p_node);
+ memdelete_allocator<Element, A>(p_node);
_data.size_cache--;
- ERR_FAIL_COND( _data._nil->color==RED );
+ ERR_FAIL_COND(_data._nil->color == RED);
}
+ void _calculate_depth(Element *p_element, int &max_d, int d) const {
- void _calculate_depth(Element *p_element,int &max_d,int d) const {
-
- if (p_element==_data._nil) {
+ if (p_element == _data._nil) {
return;
}
- _calculate_depth(p_element->left,max_d,d+1);
- _calculate_depth(p_element->right,max_d,d+1);
- if (d>max_d)
- max_d=d;
+ _calculate_depth(p_element->left, max_d, d + 1);
+ _calculate_depth(p_element->right, max_d, d + 1);
+ if (d > max_d)
+ max_d = d;
}
void _cleanup_tree(Element *p_element) {
- if (p_element==_data._nil)
+ if (p_element == _data._nil)
return;
_cleanup_tree(p_element->left);
_cleanup_tree(p_element->right);
- memdelete_allocator<Element,A>( p_element );
+ memdelete_allocator<Element, A>(p_element);
}
- void _copy_from( const Map& p_map) {
+ void _copy_from(const Map &p_map) {
clear();
// not the fastest way, but safeset to write.
- for(Element *I=p_map.front();I;I=I->next()) {
+ for (Element *I = p_map.front(); I; I = I->next()) {
- insert(I->key(),I->value());
+ insert(I->key(), I->value());
}
}
-public:
- const Element *find(const K& p_key) const {
+public:
+ const Element *find(const K &p_key) const {
if (!_data._root)
return NULL;
- const Element *res=_find(p_key);
+ const Element *res = _find(p_key);
return res;
}
- Element *find(const K& p_key) {
+ Element *find(const K &p_key) {
if (!_data._root)
return NULL;
- Element *res=_find(p_key);
+ Element *res = _find(p_key);
return res;
}
- const Element *find_closest(const K& p_key) const {
+ const Element *find_closest(const K &p_key) const {
if (!_data._root)
return NULL;
- const Element *res=_find_closest(p_key);
+ const Element *res = _find_closest(p_key);
return res;
}
- Element *find_closest(const K& p_key) {
+ Element *find_closest(const K &p_key) {
if (!_data._root)
return NULL;
- Element *res=_find_closest(p_key);
+ Element *res = _find_closest(p_key);
return res;
}
- Element *insert(const K& p_key,const V& p_value) {
+ Element *insert(const K &p_key, const V &p_value) {
if (!_data._root)
_data._create_root();
- return _insert_rb(p_key,p_value);
-
+ return _insert_rb(p_key, p_value);
}
- void erase(Element* p_element) {
+ void erase(Element *p_element) {
if (!_data._root)
return;
_erase(p_element);
- if (_data.size_cache==0 && _data._root)
+ if (_data.size_cache == 0 && _data._root)
_data._free_root();
}
- bool erase(const K& p_key) {
+ bool erase(const K &p_key) {
if (!_data._root)
return false;
- Element *e=find(p_key);
+ Element *e = find(p_key);
if (!e)
return false;
_erase(e);
return true;
}
- bool has(const K& p_key) const {
+ bool has(const K &p_key) const {
if (!_data._root)
return false;
return find(p_key) != NULL;
}
- const V& operator[](const K& p_key) const {
+ const V &operator[](const K &p_key) const {
- ERR_FAIL_COND_V(!_data._root, *(V*)NULL); // crash on purpose
- const Element *e=find(p_key);
- ERR_FAIL_COND_V(!e, *(V*)NULL); // crash on purpose
+ ERR_FAIL_COND_V(!_data._root, *(V *)NULL); // crash on purpose
+ const Element *e = find(p_key);
+ ERR_FAIL_COND_V(!e, *(V *)NULL); // crash on purpose
return e->_value;
}
- V& operator[](const K& p_key) {
+ V &operator[](const K &p_key) {
if (!_data._root)
_data._create_root();
- Element *e=find(p_key);
+ Element *e = find(p_key);
if (!e)
- e=insert(p_key,V());
+ e = insert(p_key, V());
- ERR_FAIL_COND_V(!e, *(V*)NULL); // crash on purpose
+ ERR_FAIL_COND_V(!e, *(V *)NULL); // crash on purpose
return e->_value;
}
@@ -637,12 +621,12 @@ public:
if (!_data._root)
return NULL;
- Element *e=_data._root->left;
- if (e==_data._nil)
+ Element *e = _data._root->left;
+ if (e == _data._nil)
return NULL;
- while(e->left!=_data._nil)
- e=e->left;
+ while (e->left != _data._nil)
+ e = e->left;
return e;
}
@@ -651,24 +635,24 @@ public:
if (!_data._root)
return NULL;
- Element *e=_data._root->left;
- if (e==_data._nil)
+ Element *e = _data._root->left;
+ if (e == _data._nil)
return NULL;
- while(e->right!=_data._nil)
- e=e->right;
+ while (e->right != _data._nil)
+ e = e->right;
return e;
}
- inline bool empty() const { return _data.size_cache==0; }
+ inline bool empty() const { return _data.size_cache == 0; }
inline int size() const { return _data.size_cache; }
int calculate_depth() const {
// used for debug mostly
if (!_data._root)
return 0;
- int max_d=0;
- _calculate_depth(_data._root->left,max_d,0);
+ int max_d = 0;
+ _calculate_depth(_data._root->left, max_d, 0);
return max_d;
}
@@ -677,32 +661,29 @@ public:
if (!_data._root)
return;
_cleanup_tree(_data._root->left);
- _data._root->left=_data._nil;
- _data.size_cache=0;
- _data._nil->parent=_data._nil;
+ _data._root->left = _data._nil;
+ _data.size_cache = 0;
+ _data._nil->parent = _data._nil;
_data._free_root();
}
- void operator=(const Map& p_map) {
+ void operator=(const Map &p_map) {
- _copy_from( p_map );
+ _copy_from(p_map);
}
- Map(const Map& p_map) {
+ Map(const Map &p_map) {
- _copy_from( p_map );
+ _copy_from(p_map);
}
_FORCE_INLINE_ Map() {
-
}
-
~Map() {
clear();
}
-
};
#endif
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-25 04:09:18 +0000