Skip to content

Instantly share code, notes, and snippets.

@snovvcrash snovvcrash/rbtmap.cxx
Last active Nov 22, 2018

Embed
What would you like to do?
Implementation of map (associative container) based on the red-black tree structure.
/**
* %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;
}
/**
* %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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.