summaryrefslogtreecommitdiff
path: root/core/map.h
diff options
context:
space:
mode:
Diffstat (limited to 'core/map.h')
-rw-r--r--core/map.h284
1 files changed, 142 insertions, 142 deletions
diff --git a/core/map.h b/core/map.h
index 35dc73df48..81cda1ece2 100644
--- a/core/map.h
+++ b/core/map.h
@@ -39,12 +39,12 @@
template <class K,class V,class C=Comparator<K>,class A=DefaultAllocator>
class Map {
-
- enum Color {
+
+ enum Color {
RED,
BLACK
};
- struct _Data;
+ struct _Data;
public:
class Element {
@@ -66,34 +66,34 @@ public:
public:
const Element *next() const {
-
+
return _next;
}
Element *next() {
-
+
return _next;
}
const Element *prev() const {
-
+
return _prev;
}
Element *prev() {
-
+
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() {
@@ -106,15 +106,15 @@ public:
};
};
-
+
private:
struct _Data {
-
+
Element* _root;
Element* _nil;
int size_cache;
-
+
_FORCE_INLINE_ _Data() {
#ifdef GLOBALNIL_DISABLED
_nil = memnew_allocator( Element, A );
@@ -126,7 +126,7 @@ private:
_root=NULL;
size_cache=0;
}
-
+
void _create_root() {
_root = memnew_allocator( Element,A );
@@ -145,23 +145,23 @@ private:
~_Data() {
_free_root();
-
+
#ifdef GLOBALNIL_DISABLED
memdelete_allocator<Element,A>(_nil);
#endif
// memdelete_allocator<Element,A>(_root);
}
};
-
+
_Data _data;
-
+
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;
}
inline void _rotate_left(Element *p_node) {
-
+
Element *r=p_node->right;
p_node->right=r->left;
if (r->left != _data._nil )
@@ -171,14 +171,14 @@ private:
p_node->parent->left=r;
else
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;
if (l->right != _data._nil)
@@ -188,25 +188,25 @@ private:
p_node->parent->right=l;
else
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;
-
+
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;
}
return node;
} else {
-
+
while(node == node->parent->right) {
node=node->parent;
}
@@ -215,44 +215,44 @@ private:
return node->parent;
}
}
-
- inline Element* _predecessor(Element *p_node) const {
+
+ 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;
}
return node;
} else {
-
+
while(node == node->parent->left) {
if (node->parent == _data._root)
- return NULL;
+ return NULL;
node=node->parent;
}
return node->parent;
}
}
-
-
+
+
Element *_find(const K& p_key) const {
-
+
Element *node = _data._root->left;
- C less;
-
+ C less;
+
while(node!=_data._nil) {
-
- if (less(p_key,node->_key))
+
+ 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;
}
@@ -289,73 +289,73 @@ private:
}
Element *_insert(const K& p_key, bool& r_exists) {
-
+
Element *new_parent=_data._root;
Element *node = _data._root->left;
- C less;
-
+ C less;
+
while (node!=_data._nil) {
-
+
new_parent=node;
-
+
if (less(p_key,node->_key))
node=node->left;
else if (less(node->_key,p_key))
node=node->right;
- else {
+ else {
r_exists=true;
return node;
- }
+ }
}
-
+
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->data=_data;
if (new_parent==_data._root || less(p_key,new_parent->_key)) {
-
+
new_parent->left=new_node;
} else {
new_parent->right=new_node;
}
-
+
r_exists=false;
-
+
new_node->_next=_successor(new_node);
new_node->_prev=_predecessor(new_node);
if (new_node->_next)
new_node->_next->_prev=new_node;
if (new_node->_prev)
new_node->_prev->_next=new_node;
-
+
return new_node;
}
-
+
Element * _insert_rb(const K& p_key, const V& p_value) {
-
+
bool exists=false;
Element *new_node = _insert(p_key,exists);
-
+
if (new_node) {
new_node->_value=p_value;
}
if (exists)
return 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;
-
+
if (aux->color==RED) {
_set_color(node->parent,BLACK);
_set_color(aux,BLACK);
@@ -369,10 +369,10 @@ private:
_set_color(node->parent,BLACK);
_set_color(node->parent->parent,RED);
_rotate_right(node->parent->parent);
- }
- } else {
+ }
+ } else {
Element *aux=node->parent->parent->left;
-
+
if (aux->color==RED) {
_set_color(node->parent,BLACK);
_set_color(aux,BLACK);
@@ -386,19 +386,19 @@ private:
_set_color(node->parent,BLACK);
_set_color(node->parent->parent,RED);
_rotate_left(node->parent->parent);
- }
+ }
}
}
_set_color(_data._root->left,BLACK);
- return new_node;
- }
+ return new_node;
+ }
void _erase_fix(Element *p_node) {
-
+
Element *root = _data._root->left;
Element *node=p_node;
-
-
+
+
while( (node->color==BLACK) && (root != node)) {
if (node == node->parent->left) {
Element *aux=node->parent->right;
@@ -408,7 +408,7 @@ private:
_rotate_left(node->parent);
aux=node->parent->right;
}
- if ( (aux->right->color==BLACK) && (aux->left->color==BLACK) ) {
+ if ( (aux->right->color==BLACK) && (aux->left->color==BLACK) ) {
_set_color(aux,RED);
node=node->parent;
} else {
@@ -432,7 +432,7 @@ private:
_rotate_right(node->parent);
aux=node->parent->left;
}
- if ( (aux->right->color==BLACK) && (aux->left->color==BLACK) ) {
+ if ( (aux->right->color==BLACK) && (aux->left->color==BLACK) ) {
_set_color(aux,RED);
node=node->parent;
} else {
@@ -446,24 +446,24 @@ private:
_set_color(node->parent,BLACK);
_set_color(aux->left,BLACK);
_rotate_right(node->parent);
- node=root;
+ node=root;
}
}
}
-
+
_set_color(node,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);
if (!rp)
rp=_data._nil;
Element *node= (rp->left == _data._nil) ? rp->right : rp->left;
-
+
if (_data._root == (node->parent=rp->parent) ) {
_data._root->left=node;
} else {
@@ -473,47 +473,47 @@ private:
rp->parent->right=node;
}
}
-
- if (rp != p_node) {
-
+
+ if (rp != p_node) {
+
ERR_FAIL_COND( rp == _data._nil );
-
+
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;
-
+
if (p_node == p_node->parent->left) {
- p_node->parent->left=rp;
+ p_node->parent->left=rp;
} else {
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;
if (p_node->_prev)
p_node->_prev->_next=p_node->_next;
-
+
memdelete_allocator<Element,A>(p_node);
_data.size_cache--;
ERR_FAIL_COND( _data._nil->color==RED );
}
-
-
+
+
void _calculate_depth(Element *p_element,int &max_d,int d) const {
-
+
if (p_element==_data._nil) {
return;
}
@@ -522,23 +522,23 @@ private:
if (d>max_d)
max_d=d;
}
-
+
void _cleanup_tree(Element *p_element) {
-
+
if (p_element==_data._nil)
return;
-
+
_cleanup_tree(p_element->left);
_cleanup_tree(p_element->right);
memdelete_allocator<Element,A>( p_element );
}
-
+
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()) {
-
+
insert(I->key(),I->value());
}
}
@@ -554,7 +554,7 @@ public:
}
Element *find(const K& p_key) {
-
+
if (!_data._root)
return NULL;
Element *res=_find(p_key);
@@ -578,15 +578,15 @@ public:
}
Element *insert(const K& p_key,const V& p_value) {
-
+
if (!_data._root)
_data._create_root();
return _insert_rb(p_key,p_value);
-
+
}
-
+
void erase(Element* p_element) {
-
+
if (!_data._root)
return;
_erase(p_element);
@@ -595,72 +595,72 @@ public:
}
bool erase(const K& p_key) {
-
+
if (!_data._root)
return false;
Element *e=find(p_key);
if (!e)
return false;
- _erase(e);
+ _erase(e);
return true;
}
-
+
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 {
-
+
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) {
-
+
if (!_data._root)
_data._create_root();
Element *e=find(p_key);
if (!e)
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;
}
-
+
Element *front() const {
-
+
if (!_data._root)
return NULL;
Element *e=_data._root->left;
if (e==_data._nil)
return NULL;
-
+
while(e->left!=_data._nil)
e=e->left;
-
+
return e;
}
-
+
Element *back() const {
-
+
if (!_data._root)
return NULL;
Element *e=_data._root->left;
if (e==_data._nil)
return NULL;
-
+
while(e->right!=_data._nil)
e=e->right;
-
+
return e;
}
-
+
inline bool empty() const { return _data.size_cache==0; }
inline int size() const { return _data.size_cache; }
int calculate_depth() const {
@@ -671,9 +671,9 @@ public:
_calculate_depth(_data._root->left,max_d,0);
return max_d;
}
-
+
void clear() {
-
+
if (!_data._root)
return;
_cleanup_tree(_data._root->left);
@@ -682,25 +682,25 @@ public:
_data._nil->parent=_data._nil;
_data._free_root();
}
-
+
void operator=(const Map& p_map) {
-
+
_copy_from( p_map );
}
-
+
Map(const Map& p_map) {
-
+
_copy_from( p_map );
}
_FORCE_INLINE_ Map() {
-
+
}
-
-
+
+
~Map() {
-
- clear();
+
+ clear();
}
};
generated by cgit v1.2.3 (git 2.25.1) at 2025-03-31 13:02:57 +0000