diff options
Diffstat (limited to 'core/map.h')
| -rw-r--r-- | core/map.h | 708 |
1 files changed, 708 insertions, 0 deletions
diff --git a/core/map.h b/core/map.h new file mode 100644 index 0000000000..959dc58661 --- /dev/null +++ b/core/map.h @@ -0,0 +1,708 @@ +/*************************************************************************/ +/* map.h */ +/*************************************************************************/ +/* This file is part of: */ +/* GODOT ENGINE */ +/* http://www.godotengine.org */ +/*************************************************************************/ +/* Copyright (c) 2007-2014 Juan Linietsky, Ariel Manzur. */ +/* */ +/* Permission is hereby granted, free of charge, to any person obtaining */ +/* a copy of this software and associated documentation files (the */ +/* "Software"), to deal in the Software without restriction, including */ +/* without limitation the rights to use, copy, modify, merge, publish, */ +/* distribute, sublicense, and/or sell copies of the Software, and to */ +/* permit persons to whom the Software is furnished to do so, subject to */ +/* the following conditions: */ +/* */ +/* The above copyright notice and this permission notice shall be */ +/* included in all copies or substantial portions of the Software. */ +/* */ +/* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, */ +/* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF */ +/* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/ +/* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY */ +/* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, */ +/* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE */ +/* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ +/*************************************************************************/ +#ifndef MAP_H +#define MAP_H + +#include "set.h" +/** + @author Juan Linietsky <reduzio@gmail.com> +*/ + +// 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> +class Map { + + enum Color { + RED, + BLACK + }; + struct _Data; +public: + + class Element { + + private: + friend class Map<K,V,C,A>; + //Color color; + int color; + Element* right; + Element* left; + Element* parent; + Element* _next; + Element* _prev; + K _key; + V _value; + + //_Data *data; + + 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 { + return _key; + }; + V& value() { + return _value; + }; + const V& value() const { + return _value; + }; + V& get() { + return _value; + }; + const V& get() const { + return _value; + }; + Element() { + color=RED; + right=NULL; + left=NULL; + parent=NULL; + _next=NULL; + _prev=NULL; + }; + }; + + +private: + + struct _Data { + + Element* _root; + Element* _nil; + int size_cache; + + _Data() { +#ifdef GLOBALNIL_DISABLED + _nil = memnew_allocator( Element, A ); + _nil->parent=_nil->left=_nil->right=_nil; + _nil->color=BLACK; +#else + _nil=(Element*)&_GlobalNilClass::_nil; +#endif + _root=NULL; + size_cache=0; + } + + void _create_root() { + + _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; + } + } + + ~_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 ) + 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; + + } + + inline void _rotate_right(Element *p_node) { + + 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; + else + p_node->parent->left=l; + + l->right=p_node; + p_node->parent=l; + + } + + 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; + } + if (node->parent == _data._root) + return NULL; + return node->parent; + } + } + + 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; + node=node->parent; + } + return node->parent; + } + } + + + Element *_find(const K& p_key) const { + + Element *node = _data._root->left; + C less; + + while(node!=_data._nil) { + + 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; + } + + Element *_find_closest(const K& p_key) const { + + Element *node = _data._root->left; + Element *prev = NULL; + C less; + + 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; + else + break; // found + } + + if (node==_data._nil) { + if (prev==NULL) + return NULL; + if (less(p_key,prev->_key)) { + + prev=prev->_prev; + } + + return prev; + + } else + return node; + + } + + Element *_insert(const K& p_key, bool& r_exists) { + + Element *new_parent=_data._root; + Element *node = _data._root->left; + 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 { + 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) { + + 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); + _set_color(node->parent->parent,RED); + node=node->parent->parent; + } else { + if (node == node->parent->right) { + node=node->parent; + _rotate_left(node); + } + _set_color(node->parent,BLACK); + _set_color(node->parent->parent,RED); + _rotate_right(node->parent->parent); + } + } else { + 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; + } else { + if (node == node->parent->left) { + node=node->parent; + _rotate_right(node); + } + _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; + } + + 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; + if (aux->color==RED) { + _set_color(aux,BLACK); + _set_color(node->parent,RED); + _rotate_left(node->parent); + aux=node->parent->right; + } + 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); + _rotate_right(aux); + aux=node->parent->right; + } + _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 */ + } + } 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);; + _rotate_right(node->parent); + aux=node->parent->left; + } + 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); + _rotate_left(aux); + aux=node->parent->left; + } + _set_color(aux,node->parent->color); + _set_color(node->parent,BLACK); + _set_color(aux->left,BLACK); + _rotate_right(node->parent); + 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 { + if (rp == rp->parent->left) { + rp->parent->left=node; + } else { + rp->parent->right=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; + } else { + p_node->parent->right=rp; + } + } else { + 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; + } + _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) + 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()); + } + } +public: + + const Element *find(const K& p_key) const { + + if (!_data._root) + return NULL; + + const Element *res=_find(p_key); + return res; + } + + Element *find(const K& p_key) { + + if (!_data._root) + return NULL; + Element *res=_find(p_key); + return res; + } + + const Element *find_closest(const K& p_key) const { + + if (!_data._root) + return NULL; + const Element *res=_find_closest(p_key); + return res; + } + + Element *find_closest(const K& p_key) { + + if (!_data._root) + return NULL; + Element *res=_find_closest(p_key); + return res; + } + + 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); + if (_data.size_cache==0 && _data._root) + _data._free_root(); + } + + bool erase(const K& p_key) { + + if (!_data._root) + return false; + Element *e=find(p_key); + if (!e) + return false; + _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 + 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 { + // used for debug mostly + if (!_data._root) + return 0; + int max_d=0; + _calculate_depth(_data._root->left,max_d,0); + return max_d; + } + + void clear() { + + if (!_data._root) + return; + _cleanup_tree(_data._root->left); + _data._root->left=_data._nil; + _data.size_cache=0; + _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(); + } + +}; + +#endif |