C++ Data Structures with Templates

The Code

template <class T1, class T2>
struct pair {
	T1 first;
	T2 second;
	pair() : first(T1()), second(T2()) {}
	pair(const T1& a, const T2& b) : first(a), second(b) {}
};
template <class T1, class T2>
inline pair<T1, T2> make_pair(const T1& k, const T2& t)
{
	return pair<T1, T2>(k, t);
}

#include "Pair.h"
template<typename T>
class Set {
public:
	class iterator;
	using Comparator = bool(*)(T*, T*);
	Set();
	Set(Comparator c);
	~Set();
	pair<iterator, bool> insert(T);
	void clear();
	iterator find(T);
	size_t size();
	bool empty();
	iterator begin();
	iterator end();
	iterator rbegin();
	iterator rend();
	void erase(T);
	void erase(iterator);
private:
	struct btNode {
		T data;
		btNode* left;
		btNode* right;
		btNode* parent;
	};
	btNode* root = NULL;
	size_t sSize, nSize;
	Comparator comp;
	bool insertOK;
	btNode* rightRotate(btNode**);
	btNode* leftRotate(btNode**);
	btNode* getMinimum(btNode*);
	btNode* getMaximum(btNode*);
	btNode* itemInsert(T, btNode*, btNode**);
	btNode* postInsert(T, btNode*);
	btNode* findNode(T, btNode*);
	btNode* deleteNode(btNode*);
	void deleteTree(btNode*);
	static bool defComp(T*, T*); // static so a pointer to it matches Comparator spec
	size_t btMax(size_t, size_t);
	int16_t btHeight(btNode*);
};
template<typename T>
class Set<T>::iterator {
public:
	iterator(typename Set<T>::btNode* pos, bool forward) {
		this->pos = pos;
		this->forward = forward;
	}
	typename Set<T>::btNode* getPos() {
		return pos;
	}
	T operator*() const { return pos->data; }
	iterator &operator++() {
		if (forward) {
			increment();
		}
		else {
			decrement();
		}
		return *this;
	}
	iterator &operator++(int) {
		if (forward) {
			increment();
		}
		else {
			decrement();
		}
		return *this;
	}
	iterator &operator--() {
		if (forward) {
			decrement;
		}
		else {
			increment;
		}
		return *this;
	}
	iterator &operator--(int) {
		if (forward) {
			decrement;
		}
		else {
			increment;
		}
		return *this;
	}
	bool operator!=(const iterator a) {
		return (this->pos != (a.pos));
	};
	typename Set<T>::btNode* pos;
private:
	bool forward;
	void increment();
	void decrement();
};
template<typename T>
Set<T>::Set() {
	sSize = 0;
	nSize = sizeof(btNode);
	comp = &Set<T>::defComp; // T has a < operator
}
template<typename T>
Set<T>::Set(Comparator c) {
	sSize = 0;
	nSize = sizeof(btNode);
	comp = c; // use the supplied < comparitor
}
template<typename T>
Set<T>::~Set() {
	deleteTree(root);
}
//public methods
template<typename T>
void Set<T>::clear() {
	deleteTree(root);
	root = NULL;
}
template<typename T>
size_t Set<T>::size() {
	return sSize;
}
template<typename T>
bool Set<T>::empty() {
	return (sSize == 0);
}
template<typename T>
pair<typename Set<T>::iterator, bool> Set<T>::insert(T t) {
	insertOK = false;
	btNode *n = NULL;
	root =  itemInsert(t, root, &n);
	if (insertOK) { sSize++; }
	iterator it(n, true);
	pair<typename Set<T>::iterator, bool> p(it, insertOK);
	return p;
	// build a pair out of iterator and insertOK
}
template<typename T>
typename Set<T>::iterator Set<T>::find(T value) {
	btNode* n = findNode(value, root);
	iterator it(n, true);
	return it;
}
template<typename T>
typename Set<T>::iterator Set<T>::begin() {
	btNode* is = NULL;
	if (root) {
		is = getMinimum(root);
	}
	iterator it(is, true);
	return it;
}
template<typename T>
typename Set<T>::iterator Set<T>::end() {
	iterator it(NULL, true);
	return it;
}
template<typename T>
typename Set<T>::iterator Set<T>::rbegin() {
	btNode* is = NULL;
	if (root) {
		is = getMaximum(root);
	}
	iterator it(is, false);
	return it;
}
template<typename T>
typename Set<T>::iterator Set<T>::rend() {
	iterator it(NULL, false);
	return it;
}
template<typename T>
void Set<T>::erase(T data) {
	btNode* f = findNode(data, root);
	if (f) {
		deleteNode(f);
		int a = 1;
	}
}
template<typename T>
void Set<T>::erase(typename Set<T>::iterator it) {
	btNode* pos = it.getPos();
	if (pos) {
		deleteNode(pos);
	}
}
//private methods
template<typename T>
typename Set<T>::btNode* Set<T>::itemInsert(T data, btNode* leaf, btNode** node) {
	if (leaf == NULL) {
		leaf = (btNode*)malloc(nSize);
		if (leaf == NULL) { return NULL; }
		leaf->data = data;
		leaf->parent = leaf->left = leaf->right = NULL;
		insertOK = true; // but we might yet need to balance the tree
		*node = leaf;
		return postInsert(data, leaf);
	}
	else {
		if (!comp(&data, &(leaf)->data) && !comp(&(leaf)->data, &data)) {
			// but we do not insert duplicates
			*node = leaf; // for the iterator
			return leaf;
		}
		if (comp(&data, &(leaf)->data)) {
			leaf->left = itemInsert(data, leaf->left, node);
			leaf->left->parent = leaf;
			return leaf;
		}
		else {
			leaf->right = itemInsert(data, leaf->right, node);
			leaf->right->parent = leaf;
			return leaf;
		}
	}
}
template<typename T>
typename Set<T>::btNode* Set<T>::postInsert(T data, btNode* leaf) {
	int16_t diff = btHeight((leaf)->left) - btHeight((leaf)->right);
	if (diff > 1) {
		//left branch is too hight compared to right branch
		if(comp(&data, &leaf->left->data)) {
			return rightRotate(&leaf);
		}
		else if (comp(&leaf->left->data, &data)) {
			leaf->left = leftRotate(&((leaf)->left));
			return rightRotate(&leaf);
		}
	}
	if (diff < -1) {
		//right branch is too high compared to left branch
		if (comp(&leaf->right->data, &data)) {
			return leftRotate(&leaf);
		}
		else if (comp(&data, &leaf->right->data)) {
			(leaf)->right = rightRotate(&(leaf)->right);
			return leftRotate(&leaf);
		}
	}
	return leaf;
}
template<typename T>
typename Set<T>::btNode* Set<T>::rightRotate(btNode** root) {
	btNode *oldRight, *oldRightLeft;
	oldRight = (*root)->right;
	oldRightLeft = oldRight->left;
	oldRight->left = *root;
	oldRight->left->right = oldRightLeft;
	// testing
	(*root)->parent = oldRight;
	oldRight->left->right->parent = oldRight->left;
	return oldRight;
}
template<typename T>
typename Set<T>::btNode* Set<T>::leftRotate(btNode** root) {
	btNode *oldLeft, *oldLeftRight;
	oldLeft = (*root)->left;
	oldLeftRight = oldLeft->right;
	oldLeft->right = *root;
	(*root)->left = oldLeftRight;
	// testing
	(*root)->parent = oldLeft;
	(*root)->left->parent = *root;
	return oldLeft;
}
template<typename T>
void Set<T>::deleteTree(btNode* leaf) {
	if (leaf) {
		deleteTree(leaf->left);
		deleteTree(leaf->right);
		free(leaf);
	}
}
template<typename T>
bool Set<T>::defComp(T* a, T* b) {
	return *a < *b;
}
template<typename T>
typename Set<T>::btNode* Set<T>::getMinimum(btNode* leaf) {
	btNode* temp = leaf;
	while (temp->left != NULL) {
		temp = temp->left;
	}
	return temp;
}
template<typename T>
typename Set<T>::btNode* Set<T>::getMaximum(btNode* leaf) {
	btNode* temp = leaf;
	while (temp->right != NULL) {
		temp = temp->right;
	}
	return temp;
}
template<typename T>
typename Set<T>::btNode* Set<T>::findNode(T data, btNode* leaf) {
	if (leaf) {
		if (!comp(&data, &(leaf)->data) && !comp(&(leaf)->data, &data)) {
			// remember only comparison operator we are certain to have is <
			return leaf;
		}
		if (comp(&data, &(leaf)->data)) {
			return findNode(data, leaf->left);
		}
		return findNode(data, leaf->right);
	}
	else {
		return NULL;
	}
}
template<typename T>
size_t Set<T>::btMax(size_t a, size_t b) {
	return (a <= b) ? b : a;
}
template<typename T>
int16_t Set<T>::btHeight(btNode* leaf) {
	if (leaf) {
		return 1 + btMax(btHeight(leaf->left), btHeight(leaf->right));
	}
	return 0;
}
template<typename T>
typename Set<T>::btNode* Set<T>::deleteNode(btNode* leaf) {
	btNode* temp;
	if (leaf->left == NULL || leaf->right == NULL) {
		// one or both child nodes might be NULL
		temp = leaf->left ? leaf->left : leaf->right;
		if (temp == NULL) {
			// no children
			temp = leaf;
			if (leaf->parent) {
				if (leaf == leaf->parent->left) {
					leaf->parent->left = NULL;
				}
				else {
					leaf->parent->right = NULL;
				}
			}
			leaf = NULL;
		}
		else {
			// one child so copy child to this node
			leaf->data = temp->data;
			leaf->left = temp->left;
			leaf->right = temp->right;
			//leaf = *temp;
		}
		// free the node (or copied child) memory allocations
		free(temp);
		sSize--;
	}
	else {
		temp = getMinimum(leaf->right);
		// copy the lowest node on the right path to this node
		//leaf)->key = temp->key;
		leaf->data = temp->data;
		//leaf->left = temp->left; // NULL of course
		// and then zap that node instead
		deleteNode(temp); // leaf->right);
	}
	if (leaf == NULL) {
		return leaf;
	}
	int16_t diff = btHeight(leaf->left) - btHeight(leaf->right);
	if (diff > 1) {
		// get the height difference on the left path
		diff = btHeight(leaf->left->left) - btHeight(leaf->left->right);
		if (diff < 0) {
			leaf->left = leftRotate(&leaf->left);
			return rightRotate(&leaf);
		}
		else {
			return rightRotate(&leaf);
		}
	}
	if (diff < -1) {
		// calc the height difference on the right path
		diff = btHeight(leaf->right->left) - btHeight(leaf->right->right);
		if (diff <= 0) {
			return leftRotate(&leaf);
		}
		else {
			leaf->right = rightRotate(&leaf->right);
			return leftRotate(&leaf);
		}
	}
	return leaf;
}
// iterator increment and decrement
template<typename T>
void Set<T>::iterator::increment() {
	if (pos->right) {
		pos = pos->right;
		while (pos->left) {
			pos = pos->left;
		}
	}
	else {
		if (pos->parent) {
			btNode* parent = pos->parent;
			while (parent && (pos == parent->right)) {
				pos = parent;
				parent = pos->parent;
			}
			if (pos->right != parent) {
				pos = parent;
			}
		}
		else {
			pos = pos->right; // if no right branch
		}
	}
}
template<typename T>
void Set<T>::iterator::decrement() {
	if (pos->left) {
		btNode* child = pos->left;
		while (child->right) {
			child = child->right;
		}
		pos = child;
	}
	else {
		if (pos->parent) {
			btNode* parent = pos->parent;
			while (parent && (pos == parent->left)) {
				pos = parent;
				parent = parent->parent;
			}
			pos = parent;
		}
		else {
			pos = pos->left;
		}
	}
}

#include "stdafx.h"
#include <stdint.h>
#include <stdlib.h>
#include "Set.h"
#include <iostream>
//using namespace std;
struct MyData {
	int valueC;
	int valueD;
};
void test1();
void test2();
bool compMyData(MyData*, MyData*);
int main()
{
	test1();
	//test2();
	std::cin.get();
    return 0;
}
void test1() {
	Set<int> set;
	int ints[] = { 2, 7, 4, 9, 5, 1, 8 };
	for (int i = 0; i < 7; i++) {
		set.insert(ints[i]); // ignoring the return value
	}
	for (Set<int>::iterator it = set.begin(); it != set.end(); it++) {
		std::cout << *it << '\n';
	}
	// 
	pair<Set<int>::iterator, bool> p = set.insert(21);
	if (p.second) {
		std::cout << "Value 21 inserted\n"; // reading returned Pair
	}
	std::cout << "List in reverse\n";
	for (Set<int>::iterator it = set.rbegin(); it != set.rend(); it++) {
		std::cout << *it << '\n';
	}
	// trying find()
	Set<int>::iterator is = set.find(7);
	if (is != set.end()) {
		std::cout << "Found " << *is << '\n';
	}
	// erase() by value
	std::cout << "Erasing 7\n";
	set.erase(7);
	std::cout << "Now using the iterator to erase 4\n";
	for (Set<int>::iterator it = set.begin(); it != set.end(); it++) {
		if (*it == 4) {
			set.erase(it);
			break;
		}
	}
	// list of final state
	for (Set<int>::iterator it = set.begin(); it != set.end(); it++) {
		std::cout << *it << '\n';
	}
}
void test2() {
	Set<MyData> set(compMyData);
	MyData myData;
	for (int i = 0; i < 20; i++) {
		myData.valueC = rand() % 49;
		myData.valueD = rand() % 11;
		set.insert(myData);
	}
	for (Set<MyData>::iterator it = set.begin(); it != set.end(); it++) {
		std::cout << "valueC: " <<  (*it).valueC << " ValueD: " << (*it).valueD << '\n';
	}
}
bool compMyData(MyData* a, MyData* b) {
	if (a->valueC < b->valueC) { return true; }
	if (b->valueC < a->valueC) { return false; }
	if (a->valueD < b->valueD) { return true; }
	return false;
}

#include "Set.h"
template<class T> inline Print &operator <<(Print &obj, T arg) { obj.print(arg); return obj; }
struct MyData {
  int valueC;
  int valueD;
};
void setup() {
  Serial.begin(115200);
  test1();
}
void test1(){
  Set<int> set;
  int ints[] = { 2, 7, 4, 9, 5, 1, 8 };
  for (int i = 0; i < 7; i++) {
    set.insert(ints[i]); // ignoring the return value
  }
  Serial << "Size: " << set.size() << '\n';
  for (Set<int>::iterator it = set.begin(); it != set.end(); it++) {
    Serial << *it << '\n';
  }
  // 
  pair<Set<int>::iterator, bool> p = set.insert(21);
  if (p.second) {
    Serial << "Value 21 inserted\n"; // reading returned Pair
  }
  Serial << "List in reverse\n";
  for (Set<int>::iterator it = set.rbegin(); it != set.rend(); it++) {
    Serial << *it << '\n';
  }
  // trying find()
  Set<int>::iterator is = set.find(7);
  if (is != set.end()) {
    Serial << "Found " << *is << '\n';
  }
  // erase() by value
  Serial << "Erasing 7\n";
  set.erase(7);
  Serial << "Now using the iterator to erase 4\n";
  for (Set<int>::iterator it = set.begin(); it != set.end(); it++) {
    if (*it == 4) {
      set.erase(it);
      break;
    }
  }
  // list of final state
  for (Set<int>::iterator it = set.begin(); it != set.end(); it++) {
    Serial << *it << '\n';
  }
}
void test2() {
  Set<MyData> set(compMyData);
  MyData myData;
  for (int i = 0; i < 20; i++) {
    myData.valueC = rand() % 49;
    myData.valueD = rand() % 11;
    set.insert(myData);
  }
  for (Set<MyData>::iterator it = set.begin(); it != set.end(); it++) {
    Serial << "valueC: " <<  (*it).valueC << " ValueD: " << (*it).valueD << '\n';
  }
}
bool compMyData(struct MyData* a, struct MyData* b) {
  if (a->valueC < b->valueC) { return true; }
  if (b->valueC < a->valueC) { return false; }
  if (a->valueD < b->valueD) { return true; }
  return false;
}

Read the chapter in my book C++ Data Structures with immediate download from Amazon