map.h

/*************************************************************************/
/*  map.h                                                                */
/*************************************************************************/
/*                       This file is part of:                           */
/*                           GODOT ENGINE                                */
/*                    http://www.godotengine.org                         */
/*************************************************************************/
/* Copyright (c) 2007-2015 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;
		
		_FORCE_INLINE_ _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