Abstract data types library in C++

data_structures.h

/* My personal project of a library that includes different types of template container structures.
 * 
 * A work in progress with the objective of implementing the most useful data structures in C++ for later reuse in real projects and also studying data structures themselves.
 *
 * Implemented and tested structures until latest revision:
 * Node
 * Stack
 * Queue
 * List
 * KeyNode
 * BinSearchTree
 * 
 * Untested structures:
 * AVLTree
 * PriorityQueue
 * BNode
 * 
 * To-do list:
 * Heap
 * BTree
 * HashTable
 * Graph
 * RedBlackTree
 *
 * Gabriel Alves, São Carlos - SP, 2017.
 */

#ifndef DATA_STRUCTURES_H
#define DATA_STRUCTURES_H

#include <iostream>
using std::cout;

template<class T>
class Node {
public:
	T value;
	Node* next;
	Node* previous;

	Node() :next(this), previous(this) {};
	Node(const T val) : value(val), next(this), previous(next) {};
	~Node() { next = nullptr; previous = nullptr; }
};

template<class T>
class Stack {
private:
	Node<T> header;
	int size;

public:
	Stack() :size(0) {};
	~Stack() { this->clear(); };

	void push(const T);
	bool pop(T&);

	bool isEmpty() const { return (this->header.next == &this->header) ? true : false; };
	int getSize() const { return this->size; };
	Node<T>* peek() const { return this->header.next; };

	void clear();

};

template<class T>
void Stack<T>::push(const T element) {
	Node<T>* newNode = new Node<T>;
	newNode->value = element;
	newNode->next = &this->header;
	newNode->previous = this->header.previous;
	this->header.previous->next = newNode;
	this->header.previous = newNode;
	size++;
}

template<class T>
bool Stack<T>::pop(T& element) {
	if (!this->isEmpty()) {
		element = this->header.previous->value;
		Node<T> *aux = this->header.previous;
		this->header.previous = aux->previous;
		aux->previous = &this->header;
		delete(aux);
		size--;
		return true;
	}
	return false;
}

template<class T>
inline void Stack<T>::clear() {
	T temp;
	while (this->pop(temp));
}

template<class T>
class Queue {
private:
	Node<T> header;
	int size;

public:
	Queue() :size(0) {};
	~Queue() { this->clear(); };

	void enque(const T);
	bool deque(T&);

	bool isEmpty() const { bool check = (this->header.next == &this->header) ? true : false; return check; };
	int getSize() const { return this->size; };
	Node<T>* getFront() const { return this->header.next; };
	Node<T>* getBack() const { return this->header.previous; };

	void clear();

};

template<class T>
void Queue<T>::enque(const T element) {
	Node<T> *newNode = new Node<T>;
	newNode->value = element;
	newNode->next = &this->header;
	newNode->previous = this->header.previous;
	this->header.previous->next = newNode;
	this->header.previous = newNode;
	size++;
}


template<class T>
bool Queue<T>::deque(T& element) {
	if (!this->isEmpty()) {
		element = this->header.next->value;
		Node<T>* aux = this->header.next;
		this->header.next = aux->next;
		aux->next->previous = &this->header;
		delete aux;
		size--;
		return true;
	}
	return false;
}

template<class T>
void Queue<T>::clear() {
	T temp;
	while (this->deque(temp));
}

template<class T>
class List {
private:
	Node<T> header;
	Node<T>* current;
	int size;

public:
	List() : current(&this->header), size(0) {};
	~List() { this->clear(); }

	bool toFirst(); // retorna verdadeiro se a lista estiver vazia.
	bool toNext(); // retorna verdadeiro se passar para o último elemento da lista.

	bool isEmpty() const { return (this->header.next == &this->header) ? true : false; };

	void insert(T);
	bool find(T);
	bool remove(T);
	void getCurrent(T& element) { element = this->current->value; };
	void removeCurrent();
	int getSize() const { return this->size; };

	void clear();

	T operator[](int) const;

};

template<class T>
bool List<T>::toFirst() {
	this->current = this->header.next;
	return this->current == &this->header;
}

template<class T>
bool List<T>::toNext() {
	if (!this->isEmpty()) {
		this->current = this->current->next;
		if (this->current == &this->header)
			this->current = this->current->next;
	}
	return this->current->next == &this->header;
}

template<class T>
void List<T>::insert(T element) {
	Node<T>* newNode = new Node<T>;
	newNode->value = element;
	newNode->next = this->current->next;
	newNode->previous = this->current;
	newNode->next->previous = newNode;
	this->current->next = newNode;
	this->toNext();
	this->size++;
}

template<class T>
void List<T>::removeCurrent() {
	if (!this->isEmpty()) {
		Node<T>* aux = this->current;
		aux->previous->next = aux->next;
		aux->next->previous = aux->previous;
		this->current = aux->previous;
		delete aux;
		this->size--;
	}
}

template<class T>
bool List<T>::find(T element) {
	this->toFirst();
	while (this->current->value != element) this->toNext();
	if (this->current->value == element)
		return true;
	return false;
}

template<class T>
bool List<T>::remove(T element) {
  Node<T>* temp = this->current;
		if(this->find(element)){
			this->removeCurrent();
			this->current = temp;
			return true;
		}
	return false;
}

template<class T>
void List<T>::clear() {
	this->toFirst();
	while (!this->toNext())
		this->removeCurrent();
}

template<class T>
T List<T>::operator[](int index) const {
	this->toFirst();
	while (index > 0 && !this->toNext())
		index--;
	return this->current.value;
}

template<class T>
class KeyNode {
public:
	int key;
	T data;
	KeyNode* right;
	KeyNode* left;

	KeyNode() :right(this), left(this) {};
	KeyNode(const T val, int keyVal) : data(val), key(keyVal), right(this), left(right) {};
	KeyNode(const KeyNode<T>&);
	~KeyNode() { right = nullptr; left = nullptr; }
};

template<class T>
KeyNode<T>::KeyNode(const KeyNode<T>& copyNode) {
	this->key = copyNode->key;
	this->data = copyNode->data;
	this->right = copyNode->right;
	this->left = copyNode->left;
}

template<class T>
class BinSearchTree {
private:
	KeyNode<T>* root;

	void insert(KeyNode<T>*, int, T);
	KeyNode<T>* find(KeyNode<T>*, int) const;
	void remove(KeyNode<T>*, int);

public:
	BinSearchTree() : root(nullptr) {};
	~BinSearchTree() { this->purge(root); };

	void insert(int, T);
	KeyNode<T>* find(int) const;
	void remove(int);

	bool isEmpty() const { return (this->root == nullptr) ? true : false; };
	KeyNode<T>* getMax(KeyNode<T>*) const;
	KeyNode<T>* getMin(KeyNode<T>*) const;

	void purge(KeyNode<T>*);

};

template<class T>
void BinSearchTree<T>::insert(int key, T data) {
	insert(this->root, key, data);
}

template<class T>
void BinSearchTree<T>::insert(KeyNode<T>* leaf, int key, T data) {
	if (leaf == nullptr) {
		leaf = new KeyNode<T>;
		leaf->key = key;
		leaf->data = data;
		leaf->right = nullptr;
		leaf->left = nullptr;
	}
	else if (key > leaf->key)
		insert(leaf->right, key, data);
	else if (key < leaf->key)
		insert(leaf->left, key, data);
}

template<class T>
KeyNode<T>* BinSearchTree<T>::find(int key) const {
	return find(this->root, key);
}

template<class T>
KeyNode<T>* BinSearchTree<T>::find(KeyNode<T>* leaf, int key) const {
	if (leaf == nullptr)
		return nullptr;
	else if (key == leaf->key)
		return leaf;
	else if (key < leaf->key)
		return find(leaf->left, key);
	else if (key > leaf->key)
		return find(leaf->right, key);
}

template<class T>
KeyNode<T>* BinSearchTree<T>::getMax(KeyNode<T>* leaf) const {
	if (leaf->right == nullptr)
		return leaf;
	else
		return getMax(leaf->right);
}

template<class T>
KeyNode<T>* BinSearchTree<T>::getMin(KeyNode<T>* leaf) const {
	if (leaf->left == nullptr)
		return leaf;
	else
		return getMin(leaf->left);
}

template<class T>
void BinSearchTree<T>::remove(int key) {
	if(!this->isEmpty())
		this->remove(this->root, key);
}

template<class T>
void BinSearchTree<T>::remove(KeyNode<T>* leaf, int key) {
	//Case 0: tree is empty
	if (leaf != nullptr) {
		//Case 1: found node to be removed
		if (key == leaf->key) {
			//Case 1.1: leaf node
			if (leaf->right == nullptr && leaf->left == nullptr)
				delete leaf;
			//Case 1.2: branch node with 1 leaf node
			else if (leaf->right == nullptr) {
				KeyNode<T>* aux = leaf;
				leaf = leaf->left;
				delete aux;
			}
			else if (leaf->left == nullptr) {
				KeyNode<T>* aux = leaf;
				leaf = leaf->right;
				delete aux;
			}
			//Case 1.3: branch node with 2 leaf nodes
			else {
				KeyNode<T>* aux = getMax(leaf->left);
				leaf->key = aux->key;
				leaf->data = aux->data;
				this->remove(aux, aux->key);
			}
		}
		//Case 2: the key value we're looking for is smaller than leaf's key value, go left
		else if (key < leaf->key)
			this->remove(leaf->left, key);
		//Case 3: the key value we're looking for is greater than leaf's key value, go right
		else if (key > leaf->key)
			this->remove(leaf->right, key);
	}
}

template<class T>
void BinSearchTree<T>::purge(KeyNode<T>* leaf) {
	if(!this->isEmpty()){
		if (leaf->left != nullptr)
			purge(leaf->left);
		if (leaf->right != nullptr)
			purge(leaf->right);
		delete leaf;
	}
}

template<class T>
class AVLTree {
private:
	KeyNode<T>* root;

	void rebalance_ins(KeyNode<T>*);
	void rebalance_rem(KeyNode<T>*);

	void rotateLL(KeyNode<T>*);
	void rotateRR(KeyNode<T>*);
	void rotateRL(KeyNode<T>*);
	void rotateLR(KeyNode<T>*);

	KeyNode<T>* find(KeyNode<T>*, int) const;
	void insert(KeyNode<T>*, int, T, bool&);
	void remove(KeyNode<T>*, int,bool&);

public:
	AVLTree() : root(nullptr) {};
	~AVLTree() { this->purge(root); };

	int getHeight(KeyNode<T>*) const;
	int getBF(KeyNode<T>* subtree) const { return getHeight(subtree->right) - getHeight(subtree->left); }

	KeyNode<T>* getParentNode(KeyNode<T>*, int) const;
	KeyNode<T>* getMax(KeyNode<T>*) const;
	KeyNode<T>* getMin(KeyNode<T>*) const;

	bool isBalanced(KeyNode<T>*) const;
	bool isEmpty() const { return (this->root == nullptr) ? true : false; };

	KeyNode<T>* find(int) const;
	void insert(int, T, bool&);
	void remove(int, bool&);

	void purge(KeyNode<T>*);

	void preorder(KeyNode<T>*);

};

template<class T>
int AVLTree<T>::getHeight(KeyNode<T>* subtree) const {
	// Case 1: empty subtree
	if (subtree == nullptr)
		return 0;
	//Case 2: height equals to 1 + greatest value between left and right branches
	int maxHeight = (getHeight(subtree->left) >= getHeight(subtree->right)) ? getHeight(subtree->left) : getHeight(subtree->right);
	return 1 + maxHeight;
}

template<class T>
KeyNode<T>* AVLTree<T>::getParentNode(KeyNode<T>* leaf, int childkey) const{
	//Searches for leaf node's parent, considering the leaf node is already in the tree

	if (childkey != this->root->key) {
		if (childkey == leaf->left->key || childkey == leaf->right->key)
			return leaf;
		else{
			if (childkey > leaf->key)
				return getParentNode(leaf->right, childkey);

			else if (childkey < leaf->key)
				return getParentNode(leaf->left, childkey);
		}
	}
	return nullptr;
}

template<class T>
KeyNode<T>* AVLTree<T>::getMax(KeyNode<T>* leaf) const {
	if (leaf->right == nullptr)
		return leaf;
	else
		return getMax(leaf->right);
}

template<class T>
KeyNode<T>* AVLTree<T>::getMin(KeyNode<T>* leaf) const {
	if (leaf->left == nullptr)
		return leaf;
	else
		return getMin(leaf->left);
}

template<class T>
bool AVLTree<T>::isBalanced(KeyNode<T>* subtree) const{
	if (subtree == nullptr)
		return true;
	else{
		if (getBF(subtree) < -1 || getBF(subtree) > 1)
			return false;
		return isBalanced(subtree->right) && isBalanced(subtree->left);
	}
}

template<class T>
void AVLTree<T>::rotateLL(KeyNode<T>* leaf) {
	KeyNode<T>* child;
	child = leaf->left;
	leaf->left = child->right;
	child->right = leaf;
	leaf = child;
}

template<class T>
void AVLTree<T>::rotateRR(KeyNode<T>* leaf) {
	KeyNode<T>* child;
	child = leaf->right;
	leaf->right = child->left;
	child->left = leaf;
	leaf = child;
}

template<class T>
void AVLTree<T>::rotateLR(KeyNode<T>* leaf) {
	KeyNode<T>* child, grandchild;
	child = leaf->left;
	grandchild = child->right;
	//RotateRR child and grandchild nodes
	child->right = grandchild->left;
	grandchild->left = child;
	//RotateLL root and grandchild nodes
	leaf->left = grandchild->right;
	grandchild->right = leaf;
	//Make grandchild node the new root
	leaf = grandchild;
}

template<class T>
void AVLTree<T>::rotateRL(KeyNode<T>* leaf) {
	KeyNode<T>* child, grandchild;
	child = leaf->right;
	grandchild = child->left;
	//RotateLL child and grandchild nodes
	child->left = grandchild->right;
	grandchild->right = child;
	//RotateRR root and grandchild nodes
	leaf->right = grandchild->left;
	grandchild->left = leaf;
	//Make grandchild node the new root
	leaf = grandchild;
}

template<class T>
void AVLTree<T>::rebalance_ins(KeyNode<T>* leaf) {
	//Proceed to check if the tree has been unbalanced
	if (!isBalanced(this->root)) {
		//If it is, search for the first unbalanced node from the bottom node "leaf"
		KeyNode<T>* BalNode = getParentNode(this->root, leaf->key);
		KeyNode<T>* tempX = leaf;
		KeyNode<T>* tempY;

		//The other 2 temp nodes will be used in the coming rotation cases
		while (isBalanced(BalNode) && getParentNode(this->root, BalNode->key) != nullptr) {
			tempY = tempX;
			tempX = BalNode;
			BalNode = getParentNode(this->root, BalNode->key);
		}
		//Check which of the rotation cases will be needed and rotate the nodes
			//Case 1: Left-Left Rotation
			if (BalNode->left == tempX && tempX->left == tempY)
				this->rotateLL(BalNode);

			//Case 2: Right-Right Rotation
			else if (BalNode->right == tempX && tempX->right == tempY)
				this->rotateRR(BalNode);

			//Case 3: Left-Right Rotation
			else if (BalNode->left == tempX && tempX->right == tempY)
				this->rotateLR(BalNode);

			//Case 4: Right-Left Rotation
			else if (BalNode->right == tempX && tempX->left == tempY)
				this->rotateRL(BalNode);
	}
}

template<class T>
void AVLTree<T>::rebalance_rem(KeyNode<T>* BalNode){
	//Check if the tree is unbalanced
	if (!isBalanced(this->root)) {
		//If it is, search for the first unbalanced node from the parent of the one that was removed
		while (isBalanced(BalNode) && getParentNode(this->root, BalNode->key) != nullptr)
			BalNode = getParentNode(this->root, BalNode->key);
		//Now find another 2 nodes from the tallest subtree
		KeyNode<T>* tempX = (getHeight(BalNode->left) > getHeight(BalNode->right)) ? BalNode->left : BalNode->right;
		KeyNode<T>* tempY = (getHeight(tempX->left) > getHeight(tempX->right)) ? tempX->left : tempX->right;
		//Check which of the rotation cases will be needed and rotate the nodes
			//Case 1: Left-Left Rotation
			if (BalNode->left == tempX && tempX->left == tempY)
				this->rotateLL(BalNode);

			//Case 2: Right-Right Rotation
			else if (BalNode->right == tempX && tempX->right == tempY)
				this->rotateRR(BalNode);

			//Case 3: Left-Right Rotation
			else if (BalNode->left == tempX && tempX->right == tempY)
				this->rotateLR(BalNode);

			//Case 4: Right-Left Rotation
			else if (BalNode->right == tempX && tempX->left == tempY)
				this->rotateRL(BalNode);

	}
}

template<class T>
KeyNode<T>* AVLTree<T>::find(int key) const {
	return find(this->root, key);
}

template<class T>
KeyNode<T>* AVLTree<T>::find(KeyNode<T>* leaf, int key) const {
	if (leaf == nullptr)
		return nullptr;
	else if (key == leaf->key)
		return leaf;
	else if (key < leaf->key)
		return find(leaf->left, key);
	else if (key > leaf->key)
		return find(leaf->right, key);
}

template<class T>
void AVLTree<T>::insert(int key, T data, bool& need_rebalance) {
	insert(this->root, key, data, need_rebalance);
}

template<class T>
void AVLTree<T>::insert(KeyNode<T>* leaf, int key, T data, bool& need_rebalance){
	//Same insertion procedure as the unbalanced version
	if (leaf == nullptr) {
		leaf = new KeyNode<T>;
		leaf->key = key;
		leaf->data = data;
		leaf->right = nullptr;
		leaf->left = nullptr;
		need_rebalance = true;
	}
	else if (key == leaf->key)
		need_rebalance = false;
	else if (key > leaf->key)
		insert(leaf->right, key, data, need_rebalance);
	else if (key < leaf->key)
		insert(leaf->left, key, data, need_rebalance);

	//If insertion is successful, check if tree needs balancing
	if (need_rebalance)
		this->rebalance_ins(leaf);
}

template<class T>
void AVLTree<T>::remove(int key, bool& need_rebalance) {
	need_rebalance = false;
	if(!this->isEmpty())
		this->remove(this->root, key, need_rebalance);
}

template<class T>
void AVLTree<T>::remove(KeyNode<T>* leaf, int key,bool& need_rebalance) {
	KeyNode<T>* pNode;
	//Case 0: tree is empty
	if (leaf != nullptr) {
		//Case 1: found node to be removed
		if (key == leaf->key) {
			//Case 1.1: leaf node
			if (leaf->right == nullptr && leaf->left == nullptr) {
				pNode = getParentNode(this->root, leaf->key);
				delete leaf;
				need_rebalance = true;
			}
			//Case 1.2: branch node with 1 leaf node
			else if (leaf->right == nullptr) {
				KeyNode<T>* aux = leaf;
				leaf = leaf->left;
				pNode = getParentNode(this->root, aux->key);
				delete aux;
				need_rebalance = true;
			}
			else if (leaf->left == nullptr) {
				KeyNode<T>* aux = leaf;
				leaf = leaf->right;
				pNode = getParentNode(this->root, aux->key);
				delete aux;
				need_rebalance = true;
			}
			//Case 1.3: branch node with 2 leaf nodes
			else {
				KeyNode<T>* aux = getMax(leaf->left);
				leaf->key = aux->key;
				leaf->data = aux->data;
				this->remove(aux, aux->key, need_rebalance);
			}
		}
		//Case 2: the key value we're looking for is smaller than leaf's key value, go left
		else if (key < leaf->key)
			this->remove(leaf->left, key, need_rebalance);
		//Case 3: the key value we're looking for is greater than leaf's key value, go right
		else if (key > leaf->key)
			this->remove(leaf->right, key, need_rebalance);
	}
	//After removal, rebalance the tree if needed using the removed node's parent reference
	if (need_rebalance)
		if (!this->isEmpty() && pNode != nullptr){
			while (!isBalanced(this->root)){
				this->rebalance_rem(pNode);
				pNode = getParentNode(pNode);
			}
		}
}

template<class T>
void AVLTree<T>::purge(KeyNode<T>* leaf) {
	if (!this->isEmpty()) {
		if (leaf->left != nullptr)
			purge(leaf->left);

		if (leaf->right != nullptr)
			purge(leaf->right);

		delete leaf;
	}
}

template<class T>
void AVLTree<T>::preorder(KeyNode<T>* leaf) {
	if (leaf != nullptr) {
		preorder(leaf->left);
		preorder(leaf->right);
		cout << leaf->key;
	}
}

template<class T>
class PriorityQueue{
private:
	Node<T> header;
	int size;

public:
	PriorityQueue() :size(0) {};
	~PriorityQueue() { this->clear(); };

	void enque(const T);
	bool deque(T&);

	bool isEmpty() const { bool check = (this->header.next == &this->header) ? true : false; return check; };
	int getSize() const { return this->size; };
	Node<T>* getFront() const { return this->header.next; };
	Node<T>* getBack() const { return this->header.previous; };

	void clear();

};

template<class T>
void PriorityQueue<T>::enque(const T element) {
	Node<T>* newNode = new Node<T>;
	if(this->isEmpty()){
		newNode->value = element;
		newNode->next = &this->header;
		newNode->previous = this->header.previous;
		this->header.previous->next = newNode;
		this->header.previous = newNode;
		size++;
	}
	else{
		Node<T>* iter = this->header.next;
		if (element > iter->value){
			newNode->value = element;
			newNode->next = iter;
			newNode->previous = this->header;
			iter->previous = newNode;
			size++;
		}
		else{
			while((iter->value > element) && (iter->next != this->header)) iter = iter->next;
			newNode->value = element;
			newNode->next = iter->next;
			newNode->previous = iter;
			iter->next = newNode;
			size++;
		}
	}
}


template<class T>
bool PriorityQueue<T>::deque(T& element) {
	if (!this->isEmpty()) {
		element = this->header.next->value;
		Node<T>* aux = this->header.next;
		this->header.next = aux->next;
		aux->next->previous = &this->header;
		delete aux;
		size--;
		return true;
	}
	return false;
}

template<class T>
void PriorityQueue<T>::clear() {
	T temp;
	while (this->deque(temp));
}

template<class T>
class Heap {};

template<class T, int M>
class BNode {
public:
	bool leaf;
	int keyTally;
	T keys[M-1];
	BNode* pointers[M];

	BNode();
	BNode(const T&);
};

template<class T>
class BTree {};

template<class T>
class HashTable {};

template<class T>
class Graph {};
#endif