Implementation of map (associative container) based on the red-black tree structure.

rbtmap.cxx

/**
 * %file    rbtmap.cxx
 * %author  Sam Freeside (@snovvcrash)
 * %email   snovvcrash@protonmail[.]ch
 * %date    2017-03-25
 *
 * %brief Red-black tree based map (test).
 */

#include <iostream>
#include <utility>

#include "rbtmap.hxx"

using std::cout;
using std::endl;

using value_type = std::pair<int, char>;

int main() {
	rbtmap::map<int, char> rbt;

	value_type n0( 8, 'q');
	value_type n1(17, 'w');
	value_type n2( 1, 'e');
	value_type n3(11, 'r');
	value_type n4(15, 't');
	value_type n5(25, 'y');
	value_type n6(13, '1');
	value_type n7( 6, '2');
	value_type n8(22, '3');
	value_type n9(15, '4');

	rbt.insert(n0);
	rbt.insert(n1);
	rbt.insert(n2);
	rbt.insert(n3);
	rbt.insert(n4);
	rbt.insert(n5);
	rbt.insert(n6);
	rbt.insert(n7);
	rbt.insert(n8);
	rbt.insert(n9);
	
	cout << rbt.is_red_black_tree() << endl;
	cout << rbt.empty() << endl;

	rbtmap::map<int, char> rbt2;
	rbt2 = rbt;

	rbt.show_tree_levels();
	rbt2.show_tree_levels();

	for (rbtmap::map<int, char>::const_iterator it = rbt.begin(); it != rbt.end(); it++)
		cout << it->first << " " << it->second << endl;

	rbtmap::map<int, char>::iterator it = rbt.begin();
	++it; ++it; ++it;

	while (it != rbt.begin()) {
		cout << it->first << " " << it->second << endl;
		--it;
	}

	cout << rbt[22] << endl;

	it = rbt.find(11);
	cout << it->first << " " << it->second << endl;

	rbt.erase(it);
	rbt.show_tree_levels();

	rbt.erase(6);
	rbt.show_tree_levels();

	cout << rbt[25] << endl;
	cout << rbt[100] << endl;
	rbt[100] = 'x';
	cout << rbt[100] << endl;

	return 0;
}

rbtmap.hxx

/**
 * %file    rbtmap.hxx
 * %author  Sam Freeside (@snovvcrash)
 * %email   snovvcrash@protonmail[.]ch
 * %date    2017-03-25
 *
 * %brief Red-black tree based map.
 */

#pragma once
#ifndef RBTMAP_HXX
#define RBTMAP_HXX

#include <iostream>
#include <stdexcept>
#include <cstdlib>
#include <iterator>
#include <utility>
#include <queue>

namespace rbtmap {

	template<typename T>
	struct Comparator {
		bool operator()(T const& x, T const& y) {
			return x < y;
		}
	};

	template<typename T>
	struct node {
		T     value;
		bool  red;
		node* left;
		node* right;
		node* parent;

		node()         : value(T()),    red(false), left(nullptr), right(nullptr), parent(nullptr) { }
		node(T value_) : value(value_), red(true),  left(nullptr), right(nullptr), parent(nullptr) { }
		node(T value_, bool red_, node* parent_) : value(value_), red(red_), left(nullptr), right(nullptr), parent(parent_) { }
	};

	template<typename K, typename V, typename C = Comparator<K> >
	class map {
		using key_type    = K;
		using mapped_type = V;
		using value_type  = std::pair<const key_type, mapped_type>;
		using node_type   = node<value_type>;

		C cmp;

		void left_rotate(node_type* x) {
			node_type* y;

			y = x->right;

			x->right = y->left;
			if (y->left != NIL)
				y->left->parent = x;
  
			y->parent = x->parent;   
			if (x->parent == NIL)
				root = y;
			else if (x == x->parent->left)
				x->parent->left = y;
			else
				x->parent->right = y;

			y->left = x;
			x->parent = y;
		}

		void right_rotate(node_type* y) {
			node_type* x;

			x = y->left;

			y->left = x->right;
			if (x->right != NIL)
				x->right->parent = y;
  
			x->parent = y->parent;   
			if (y->parent == NIL)
				root = x;
			else if (y == y->parent->left)
				y->parent->left = x;
			else
				y->parent->right = x;

			x->right = y;
			y->parent = x;
		}

		void insert_fix_up(node_type* z) {
			while (z->parent->red == true)
				if (z->parent == z->parent->parent->left) {
					node_type* y = z->parent->parent->right;
					if (y->red == true) {
						z->parent->red = false;
						y->red = false;
						z->parent->parent->red = true;
						z = z->parent->parent;
					}
					else if (z == z->parent->right) {
						z = z->parent;
						left_rotate(z);
					}
					z->parent->red = false;
					z->parent->parent->red = true;
					right_rotate(z->parent->parent);
				}
				else {
					node_type* y = z->parent->parent->left;
					if (y->red) {
						z->parent->red = false;
						y->red = false;
						z->parent->parent->red = true;
						z = z->parent->parent;
					}
					else {
						if (z == z->parent->left) {
							z = z->parent;
							right_rotate(z);
						}
						z->parent->red = false;
						z->parent->parent->red = true;
						left_rotate(z->parent->parent);
					}
				}
			root->red = false;
		}

		node_type* insert(node_type* z) {
			node_type* x;
			node_type* y;

			x = root;
			y = NIL;

			while (x != NIL) {
				y = x;
				if (cmp(z->value.first, x->value.first))
					x = x->left;
				else if (cmp(x->value.first, z->value.first))
					x = x->right;
				else {
					delete z;
					return x;
				}
			}

			z->parent = y;

			if (y == NIL)
				root = z;
			else if (cmp(z->value.first, y->value.first))
				y->left = z;
			else if (cmp(y->value.first, z->value.first))
				y->right = z;
			else {
				delete z;
				return x;
			}

			z->left = z->right = NIL;
			z->red = true;

			insert_fix_up(z);
			return z;
		}

		void transplant(node_type* u, node_type* v) {
			if (u->parent == NIL)
				root = v;
			else if (u == u->parent->left)
				u->parent->left = v;
			else
				u->parent->right = v;

			v->parent = u->parent;
		}

		void erase_fix_up(node_type* x) {
			while (x != root && x->red == false)
				if (x == x->parent->left) {
					node_type* w = x->parent->right;
					if (w->red == true) {
						w->red = false;
						x->parent->red = true;
						left_rotate(x->parent);
						w = x->parent->right;
					}
					if (w->left->red == false && w->right->red == false) {
						w->red = true;
						x = x->parent;
					}
					else if (w->right->red == false) {
						w->left->red = false;
						w->red = true;
						right_rotate(w);
						w = x->parent->right;
					}
					w->red = x->parent->red;
					x->parent->red = false;
					w->right->red = false;
					left_rotate(x->parent);
					x = root;
				}
				else {
					node_type* w = x->parent->left;
					if (w->red == true) {
						w->red = false;
						x->parent->red = true;
						right_rotate(x->parent);
						w = x->parent->left;
					}
					if (w->right->red == false && w->left->red == false) {
						w->red = true;
						x = x->parent;
					}
					else if (w->left->red == false) {
						w->right->red = false;
						w->red = true;
						left_rotate(w);
						w = x->parent->left;
					}
					w->red = x->parent->red;
					x->parent->red = false;
					w->left->red = false;
					right_rotate(x->parent);
					x = root;
				}
			x->red = false;
		}

		void erase(node_type* z) {
			node_type* x;
			node_type* y;
			bool y_original_red;

			y = z;
			y_original_red = y->red;

			if (z->left == NIL) {
				x = z->right;
				transplant(z, z->right);
			}
			else if (z->right == NIL) {
				x = z->left;
				transplant(z, z->left);
			}
			else {
				// y = TREE-MINIMUM(z->right)
				while ((z->right)->left != NIL)
					(z->right) = (z->right)->left;
				y = z->right;

				y_original_red = y->red;
				x = y->right;
				if (y->parent == z)
					x->parent = y;
				else {
					transplant(y, y->right);
					y->right = z->right;
					y->right->parent = y;
				}
				transplant(z, y);
				y->left = z->left;
				y->left->parent = y;
				y->red = z->red;
			}
			if (y_original_red == false)
				erase_fix_up(x);
		}

		node_type* find(value_type const& value) {
			node_type* x = root;
		
			while (x != NIL) {
				if (cmp(value.first, x->value.first))
					x = x->left;
				else if (cmp(x->value.first, value.first))
					x = x->right;
				else return x;
			}
		
			return nullptr;
		}

		int get_black_height(node_type const* currNode) {
			if (currNode == NIL) return 0;

			int leftHeight  = get_black_height(currNode->left);
			int rightHeight = get_black_height(currNode->right);
			int add         = !currNode->red;

			if (leftHeight == -1 || rightHeight == -1 || leftHeight != rightHeight)
				return -1;

			return leftHeight + add;
		}

		void show_tree_items(node_type const* currNode) {
			if (currNode == NIL) return;

			show_tree_items(currNode->left);
			std::cout << "P: " << currNode->parent->value.first << std::endl;
			std::cout << "K: " << currNode->value.first << std::endl;
			std::cout << "V: " << currNode->value.second << std::endl;
			currNode->red ? std::cout << "RED" : std::cout << "BLACK";
			std::cout << std::endl << std::endl;
			show_tree_items(currNode->right);
		}

		void show_tree_levels(node_type const* currNode) {
			unsigned int level = 0;
		
			typedef std::pair<node_type const*, unsigned int> nodeLevel;
			std::queue<nodeLevel> q;
			q.push(nodeLevel(currNode, 1));
		
			while (!q.empty()) {
				nodeLevel NL = q.front();
				q.pop();
				if (NIL != (currNode = NL.first)) {
					if (level != NL.second) {
						if (1 == NL.second)
							std::cout << "Level #" << NL.second << ": [ ";
						else
							std::cout << "]  ->  Level #" << NL.second << ": [ ";
						level = NL.second;
					}
					std::cout << currNode->value.first << " ";
					q.push(nodeLevel(currNode->left, level+1));
					q.push(nodeLevel(currNode->right, level+1));
				}
			}
			std::cout << "]" << std::endl;
		}

		node_type* create_nil_node() {
			node_type* NIL = new node_type;
			NIL->left = NIL->right = NIL;
			return NIL;
		}

		void clone_map(node_type*& newNode, node_type const* sourceNode) {
			// ~ if (sourceNode == sourceNode->left || sourceNode == sourceNode->right)
			if (sourceNode == sourceNode->left) {
				newNode = NIL;
				return;
			}

			if (newNode == NIL)
				newNode = new node_type(sourceNode->value, sourceNode->red, nullptr);
			
			if (sourceNode->left != sourceNode->left->left) {
				newNode->left = new node_type(sourceNode->left->value, sourceNode->left->red, newNode);
				clone_map(newNode->left, sourceNode->left);
			}
			else newNode->left = NIL;

			if (sourceNode->right != sourceNode->right->right) {
				newNode->right = new node_type(sourceNode->right->value, sourceNode->right->red, newNode);
				clone_map(newNode->right, sourceNode->right);
			}
			else newNode->right = NIL;
		}

		void swap(map& lhs, map& rhs) noexcept {
			using std::swap;
			swap(lhs.root, rhs.root);
			swap(lhs.NIL, rhs.NIL);
		}

		void clear(node_type* currNode) {
			if (currNode == NIL) return;
			clear(currNode->left);
			clear(currNode->right);
			delete currNode;
		}

	public:
		node_type* root;
		node_type* NIL;

		map() {
			NIL = create_nil_node();
			root = NIL;
		}

		map(const map& otherMap) {
			if (otherMap.root == otherMap.NIL) return;
			NIL = create_nil_node();
			root = NIL;
			clone_map(root, otherMap.root);
		}

		map& operator=(map rhs) {
			swap(*this, rhs);
			return *this;
		}

		/* map(const map& otherMap) {
			if (otherMap.root == otherMap.NIL) return;
			NIL = create_nil_node();
			root = NIL;
			*this = otherMap;
		}

		map& operator=(const map& rhs) {
			if (this != &rhs) {
				clear();
				clone_map(root, rhs.root);
			}
			return *this;
		} */

		~map() {
			clear();
			delete NIL;
		}

		template<typename Type>
		class BidirectionalIterator : public std::iterator<
			std::bidirectional_iterator_tag,
			Type,
			std::ptrdiff_t,
			Type*,
			Type&
		> {
			using UnqualifiedType = typename std::remove_cv<Type>::type;
			node<UnqualifiedType>* itr;

			node_type* get_next(node_type* currNode) {
				if (currNode == currNode->left) return nullptr;

				if (currNode->right != currNode->right->right) {
					currNode = currNode->right;
					while (currNode->left != currNode->left->left) currNode = currNode->left;
					return currNode;
				}

				node_type* prevNode = currNode->parent;
				if (prevNode == prevNode->left) return prevNode;

				while (prevNode->right == currNode) {
					prevNode = prevNode->parent;
					currNode = currNode->parent;
					if (prevNode == prevNode->left) return nullptr;
				}
				return prevNode;
			}

			node_type* get_prev(node_type* currNode) {
				if (currNode == currNode->left) return nullptr;

				if (currNode->left != currNode->left->left) {
					currNode = currNode->left;
					while (currNode->right != currNode->right->right) currNode = currNode->right;
					return currNode;
				}

				node_type* prevNode = currNode->parent;
				if (prevNode == prevNode->left) return prevNode;

				while (prevNode->left == currNode) {
					prevNode = prevNode->parent;
					currNode = currNode->parent;
					if (prevNode == prevNode->left) return nullptr;
				}
				return prevNode;
			}

		public:
			using self_type = BidirectionalIterator;
			using reference = Type&;
			using pointer   = Type*;

			BidirectionalIterator() : itr(nullptr) { }

			// Using "explicit" to prevent using default conversion constructor
			explicit BidirectionalIterator(node<UnqualifiedType>* itr_) : itr(itr_) { }

			// One way conversion: iterator -> const_iterator
			operator BidirectionalIterator<const Type>() const {
				return BidirectionalIterator<const Type>(itr);
			}

			node<UnqualifiedType>* get_pointer() { return itr; }

			// Pre-increment
			self_type& operator++() {
				if (!itr)
					throw std::runtime_error("EXCEPTION: rbtmap::map::BidirectionalIterator::operator++: null iterator pre-increment");

				itr = get_next(itr);
				return *this;
			}

			// Post-increment
			self_type operator++(int) {
				if (!itr)
					throw std::runtime_error("EXCEPTION: rbtmap::map::BidirectionalIterator::operator++: null iterator post-increment");

				BidirectionalIterator tmpItr(*this);
				itr = get_next(itr);
				return tmpItr;
			}

			// Pre-decrement
			self_type& operator--() {
				if (!itr)
					throw std::runtime_error("EXCEPTION: rbtmap::map::BidirectionalIterator::operator--: null iterator pre-decrement");

				itr = get_prev(itr);
				return *this;
			}

			// Post-decrement
			self_type operator--(int) {
				if (!itr)
					throw std::runtime_error("EXCEPTION: rbtmap::map::BidirectionalIterator::operator--: null iterator post-decrement");

				BidirectionalIterator tmpItr(*this);
				itr = get_prev(itr);
				return tmpItr;
			}

			bool operator==(const self_type& rhs) { return itr == rhs.itr; }

			bool operator!=(const self_type& rhs) { return itr != rhs.itr; }

			reference operator*() const {
				if (!itr)
					throw std::runtime_error("EXCEPTION: rbtmap::map::BidirectionalIterator::operator*: null iterator dereference");

				return itr->value;
			}

			pointer operator->() const {
				if (!itr)
					throw std::runtime_error("EXCEPTION: rbtmap::map::BidirectionalIterator::operator->: null iterator dereference");

				return &(itr->value);
			}
		};

		using iterator       = BidirectionalIterator<value_type>;
		using const_iterator = BidirectionalIterator<const value_type>;

		iterator begin() {
			if (root == NIL) return iterator(nullptr);
			node_type* currNode = root;
			while (currNode->left != currNode->left->left) currNode = currNode->left;
			return iterator(currNode);
		}

		iterator     end()                           { return iterator(nullptr);                                }
		iterator     insert(value_type const& value) { return iterator(insert(new node_type(value)));           }
		mapped_type& operator[](key_type const& key) { return (*insert(value_type(key, mapped_type()))).second; }

		size_t erase_helper(node_type* deleting) {
			if (!deleting) return 0;
			erase(deleting);
			return 1;
		}

		size_t erase(iterator it) {
			node_type* deleting = it.get_pointer();
			return erase_helper(deleting);
		}

		size_t erase(key_type const& key) {
			node_type* deleting = find(value_type(key, mapped_type()));
			return erase_helper(deleting);
		}

		iterator find(key_type const& key) {
			node_type* seeking = find(value_type(key, mapped_type()));
			if (!seeking) return end();
			return iterator(seeking);
		}

		const_iterator find(key_type const& key) const {
			node_type* seeking = find(value_type(key, mapped_type()));
			if (!seeking) return end();
			return const_iterator(seeking);
		}

		bool empty() {
			if (root == NIL) return true;
			return false;
		}

		void clear() {
			clear(root);
			root = NIL;
		}

		void show_tree_items() {
			if (root == NIL)
				throw std::runtime_error("EXCEPTION: rbtmap::map::show_tree_items: map is empty");

			show_tree_items(root);
		}

		void show_tree_levels() {
			if (root == NIL)
				throw std::runtime_error("EXCEPTION: rbtmap::map::show_tree_levels: map is empty");

			show_tree_levels(root);
		}

		bool is_red_black_tree() { return get_black_height(root) != 1; }
	};
	
}

#endif // RBTMAP_HXX