C++ Data Structures with Templates
Chapter 9: A Map Class
The Code
RedBlack.h#ifndef RedBlack_h
#define RedBlack_h
// std::swap is available in this context
//template <class T> inline void swap(T& a, T& b)
//{
// T c(a); a = b; b = c;
//};
template<typename T, typename K>
class RedBlack {
public:
using RBIter = bool(*)(K, T*);
RedBlack(bool = false);
~RedBlack();
bool deleteNode(K);
bool insertNode(K, T*);
int blackHeight();
int nodeCount(bool=false);
T* nodeSearch(K);
void iterate(RBIter);
void reverseIterate(RBIter);
void clear();
void allowUpdate(bool);
protected:
enum Colour { RED, BLACK };
struct rbNode {
K key;
uint8_t colour;
rbNode *left, *right, *parent;
void* data;
};
rbNode* root;
uint8_t tSize;
uint8_t nodeSize;
T* rbSearch(K, rbNode*);
rbNode* rbMinimum(rbNode*);
rbNode* rbMaximum(rbNode*);
rbNode* rbInsert(rbNode*, rbNode*);
rbNode* rbMakeNode(K key, T* data);
bool memoryError;
void rbPostInsertFix(rbNode*, rbNode*&);
rbNode* rbFind(K, rbNode*);
private:
bool updateOK;
bool rbRepeat;
int rbCount(bool, rbNode*);
int rbHeight(rbNode*);
int rbMax(int, int);
void rbDeleteTree(rbNode*);
void rbRotateRight(rbNode*, rbNode*&);
void rbRotateLeft(rbNode*, rbNode*&);
rbNode* rbPreDeleteFix(rbNode*, rbNode*&);
void rbIterate(rbNode*, RBIter);
void rbRevIterate(rbNode*, RBIter);
};
// Constructor / destructor
template<typename T, typename K>
RedBlack<T, K>::RedBlack(bool noUpdates = false) {
root = NULL;
nodeSize = sizeof(rbNode);
tSize = sizeof(T);
updateOK = !noUpdates;
}
template<typename T, typename K>
RedBlack<T, K>::~RedBlack() {
rbDeleteTree(root);
}
//Public Methods
template<typename T, typename K>
bool RedBlack<T, K>::insertNode(K key, T* data) {
memoryError = false;
rbNode* temp = rbMakeNode(key, data);
root = rbInsert(temp, root);
rbPostInsertFix(temp, root);
return !memoryError;
}
template<typename T, typename K>
bool RedBlack<T, K>::deleteNode(K key) {
rbNode* found = rbFind(key, root);
if (found) {
rbNode* del = rbPreDeleteFix(found, root);
// now zap whatever is no longer needed
free(del->data);
free(del);
return true;
}
return false;
}
template<typename T, typename K>
T* RedBlack<T, K>::nodeSearch(K key) {
return rbSearch(key, root);
}
template<typename T, typename K>
void RedBlack<T, K>::iterate(RBIter callBack) {
rbRepeat = true;
rbIterate(root, callBack);
}
template<typename T, typename K>
void RedBlack<T, K>::reverseIterate(RBIter callBack) {
rbRepeat = true;
rbRevIterate(root, callBack);
}
template<typename T, typename K>
int RedBlack<T, K>::blackHeight() {
return rbHeight(root);
}
template<typename T, typename K>
int RedBlack<T, K>::nodeCount(bool blackOnly = false) {
return rbCount(blackOnly, root);
}
template<typename T, typename K>
void RedBlack<T, K>::clear() {
rbDeleteTree(root);
root = NULL;
}
template<typename T, typename K>
void RedBlack<T, K>::allowUpdate(bool allow) {
updateOK = allow;
}
//private methods
template<typename T, typename K>
typename RedBlack<T, K>::rbNode* RedBlack<T, K>::rbMakeNode(K key, T* data) {
rbNode* temp = (rbNode*)malloc(nodeSize);
if (temp == NULL) {
memoryError = true;
}
temp->key = key;
temp->left = temp->right = temp->parent = NULL;
temp->colour = RED;
temp->data = malloc(tSize);
if (temp->data) {
if (data) {
// allows for no data presented in Map subclass
memcpy(temp->data, data, tSize);
}
else {
memset(temp->data, '\0', tSize);
}
}
else {
memoryError = true;
}
return temp;
}
template<typename T, typename K>
typename RedBlack<T, K>::rbNode* RedBlack<T, K>::rbInsert(rbNode* node, rbNode* leaf) {
if (leaf == NULL) {
return node;
}
if (node->key == leaf->key) {
if (updateOK) {
memcpy(leaf->data, node->data, tSize);
free(node->data);
free(node);
}
else {
memoryError = true; // well sort of
}
return leaf;
}
if (node->key < leaf->key) {
leaf->left = rbInsert(node, leaf->left);
leaf->left->parent = leaf;
}
else if (node->key > leaf->key) {
leaf->right = rbInsert(node, leaf->right);
leaf->right->parent = leaf;
}
return leaf;
}
template<typename T, typename K>
void RedBlack<T, K>::rbPostInsertFix(rbNode* node, rbNode*& root) {
rbNode* grandMa = NULL;
rbNode* aunty = NULL;
while (node != root && node->parent->colour == RED) {
grandMa = node->parent->parent;
if (node->parent == grandMa->left) {
aunty = grandMa->right;
if (aunty && aunty->colour == RED) {
node->parent->colour = BLACK;
aunty->colour = BLACK;
grandMa->colour = RED;
node = grandMa;
}
else {
if (node == node->parent->right) {
node = node->parent;
rbRotateLeft(node, root);
}
node->parent->colour = BLACK;
grandMa->colour = RED;
rbRotateRight(grandMa, root);
}
}
else {
aunty = grandMa->left;
if (aunty && aunty->colour == RED) {
node->parent->colour = BLACK;
aunty->colour = BLACK;
grandMa->colour = RED;
node = grandMa;
}
else {
if (node == node->parent->left) {
node = node->parent;
rbRotateRight(node, root);
}
node->parent->colour = BLACK;
grandMa->colour = RED;
rbRotateLeft(grandMa, root);
}
}
}
root->colour = BLACK;
}
template<typename T, typename K>
typename RedBlack<T, K>::rbNode* RedBlack<T, K>::rbFind(K key, rbNode* leaf) {
if (leaf) {
if (leaf->key == key) {
return leaf;
}
if (key < leaf->key) {
return rbFind(key, leaf->left);
}
return rbFind(key, leaf->right);
}
return NULL;
}
template<typename T, typename K>
typename RedBlack<T, K>::rbNode* RedBlack<T, K>::rbPreDeleteFix(rbNode* node, rbNode*& root) {
rbNode* nodeToDelete = node;
rbNode* child = NULL;
rbNode* parentNode = NULL;
if (nodeToDelete->left == NULL) { // node has one or no children
child = nodeToDelete->right; // which might be NULL
}
else {
if (nodeToDelete->right == NULL) // node has one child
child = nodeToDelete->left; // child is not NULL
else { // node has two children
nodeToDelete = rbMinimum(nodeToDelete->right);
// so we reset to the minimum key node
// from the right child (so next largest key)
child = nodeToDelete->right;
}
}
if (nodeToDelete != node) {
// if the nodeToDelete got changed above
node->left->parent = nodeToDelete;
nodeToDelete->left = node->left;
if (nodeToDelete != node->right) {
parentNode = nodeToDelete->parent;
if (child) {
child->parent = nodeToDelete->parent;
}
nodeToDelete->parent->left = child;
nodeToDelete->right = node->right;
node->right->parent = nodeToDelete;
}
else {
parentNode = nodeToDelete;
}
if (root == node) {
root = nodeToDelete;
}
else if (node->parent->left == node) {
node->parent->left = nodeToDelete;
}
else {
node->parent->right = nodeToDelete;
}
nodeToDelete->parent = node->parent;
std::swap(nodeToDelete->colour, node->colour);
nodeToDelete = node;
// nodeToDelete now deinately points to node to be deleted
}
else {
parentNode = nodeToDelete->parent;
if (child) {
child->parent = nodeToDelete->parent;
}
if (root == node) {
root = child;
}
else {
if (node->parent->left == node) {
node->parent->left = child;
}
else {
node->parent->right = child;
}
}
}
if (nodeToDelete->colour != RED) {
while (child != root && (child == NULL || child->colour == BLACK)) {
if (child == parentNode->left) {
rbNode* sisterNode = parentNode->right;
if (sisterNode->colour == RED) {
sisterNode->colour = BLACK;
parentNode->colour = RED;
rbRotateLeft(parentNode, root);
sisterNode = parentNode->right;
}
if ((sisterNode->left == NULL ||
sisterNode->left->colour == BLACK) &&
(sisterNode->right == NULL ||
sisterNode->right->colour == BLACK)) {
sisterNode->colour = RED;
child = parentNode;
parentNode = parentNode->parent;
}
else {
if (sisterNode->right == NULL ||
sisterNode->right->colour == BLACK) {
if (sisterNode->left) sisterNode->left->colour = BLACK;
sisterNode->colour = RED;
rbRotateRight(sisterNode, root);
sisterNode = parentNode->right;
}
sisterNode->colour = parentNode->colour;
parentNode->colour = BLACK;
if (sisterNode->right) {
sisterNode->right->colour = BLACK;
}
rbRotateLeft(parentNode, root);
break;
}
}
else { // same as above but the other way about
rbNode* sisterNode = parentNode->left;
if (sisterNode->colour == RED) {
sisterNode->colour = BLACK;
parentNode->colour = RED;
rbRotateRight(parentNode, root);
sisterNode = parentNode->left;
}
if ((sisterNode->right == NULL ||
sisterNode->right->colour == BLACK) &&
(sisterNode->left == NULL ||
sisterNode->left->colour == BLACK)) {
sisterNode->colour = RED;
child = parentNode;
parentNode = parentNode->parent;
}
else {
if (sisterNode->left == NULL ||
sisterNode->left->colour == BLACK) {
if (sisterNode->right) {
sisterNode->right->colour = BLACK;
}
sisterNode->colour = RED;
rbRotateLeft(sisterNode, root);
sisterNode = parentNode->left;
}
sisterNode->colour = parentNode->colour;
parentNode->colour = BLACK;
if (sisterNode->left) {
sisterNode->left->colour = BLACK;
}
rbRotateRight(parentNode, root);
break;
}
}
}
if (child) {
child->colour = BLACK;
}
}
return nodeToDelete;
}
template<typename T, typename K>
void RedBlack<T, K>::rbRotateLeft(rbNode* node, rbNode*& root) {
rbNode* child = node->right;
node->right = child->left;
if (child->left) {
child->left->parent = node;
}
child->parent = node->parent;
if (node == root) {
root = child;
}
else if (node == node->parent->left) {
node->parent->left = child;
}
else {
node->parent->right = child;
}
child->left = node;
node->parent = child;
}
template<typename T, typename K>
void RedBlack<T, K>::rbRotateRight(rbNode* node, rbNode*& root) {
rbNode* child = node->left;
node->left = child->right;
if (child->right != 0) {
child->right->parent = node;
}
child->parent = node->parent;
if (node == root) {
root = child;
}
else if (node == node->parent->right) {
node->parent->right = child;
}
else {
node->parent->left = child;
}
child->right = node;
node->parent = child;
}
template<typename T, typename K>
T* RedBlack<T, K>::rbSearch(K key, rbNode* leaf) {
if (leaf) {
if (leaf->key == key) {
return (T*)leaf->data;
}
if (key < leaf->key) {
return rbSearch(key, leaf->left);
}
return rbSearch(key, leaf->right);
}
return NULL;
}
template<typename T, typename K>
void RedBlack<T, K>::rbIterate(rbNode* leaf, RBIter callBack) {
if (leaf && rbRepeat) {
rbIterate(leaf->left, callBack);
if (rbRepeat) {
rbRepeat = callBack(leaf->key, (T*)leaf->data);
rbIterate(leaf->right, callBack);
}
}
}
template<typename T, typename K>
void RedBlack<T, K>::rbRevIterate(rbNode* leaf, RBIter callBack) {
if (leaf && rbRepeat) {
rbRevIterate(leaf->right, callBack);
if (rbRepeat) {
rbRepeat = callBack(leaf->key, (T*)leaf->data);
rbRevIterate(leaf->left, callBack);
}
}
}
template<typename T, typename K>
typename RedBlack<T, K>::rbNode* RedBlack<T, K>::rbMinimum(rbNode* node) {
while (node->left) {
node = node->left;
}
return node;
}
template<typename T, typename K>
typename RedBlack<T, K>::rbNode* RedBlack<T, K>::rbMaximum(rbNode* node) {
while (node->right) {
node = node->right;
}
return node;
}
template<typename T, typename K>
int RedBlack<T, K>::rbHeight(rbNode* leaf) {
if (leaf) {
int subMax = rbMax(rbHeight(leaf->left), rbHeight(leaf->right));
if (leaf->colour == BLACK) { subMax++; }
return subMax;
}
return 0;
}
template<typename T, typename K>
int RedBlack<T, K>::rbMax(int a, int b) {
return (a <= b) ? b : a;
}
template<typename T, typename K>
int RedBlack<T, K>::rbCount(bool blackOnly, rbNode* leaf) {
if (leaf) {
int rVal = (blackOnly && leaf->colour == RED) ? 0 : 1;
return rVal + rbCount(blackOnly, leaf->left) + rbCount(blackOnly, leaf->right);
}
return 0;
}
template<typename T, typename K>
void RedBlack<T, K>::rbDeleteTree(rbNode* leaf) {
if (leaf) {
rbDeleteTree(leaf->left);
rbDeleteTree(leaf->right);
free(leaf->data);
free(leaf);
}
}
#endif
Demodata.h
const float locations[][2] = {
{ 50.88896, -3.22276 },
{ 50.97296, -0.14434 },
{ 52.40201, -2.89624 },
{ 52.11315, -4.22539 },
{ 52.24226, -4.25925 },
{ 51.69282, -3.34593 },
{ 54.04421, -2.81772 },
{ 53.69139, -1.37831 },
{ 52.44573, -1.82716 },
{ 51.01786, 0.71719 },
{ 52.85295, -2.3481 },
{ 51.0029, -2.206 },
{ 52.86107, 1.24202 },
{ 51.24989, -0.76169 },
{ 57.2319, -2.70206 }
};
char places[][30] = {
"Abbey",
"Abbotsford",
"Abcott",
"Aber",
"Aberaeron",
"Aberfan",
"Abraham Heights",
"Ackton",
"Acocks Green",
"Acton",
"Adbaston",
"Alcester",
"Aldborough",
"Aldershot",
"Alford"
};
Town.h
class Town {
public:
char* name;
Town() {
name = (char*)malloc(4);
memset(name, '\0', 1);
}
Town(char* tname) {
size_t sLen = strlen(tname);
name = (char*)malloc((++sLen));
strncpy(name, tname, sLen);
}
bool operator==(Town& t) {
char *a = &name[0], *b = &t.name[0];
for (; *a == *b; a++, b++) {
if (*a == '\0' || *b == '\0') {
if (*a == *b) { return true; }
break;
}
}
return false;
}
bool operator<(Town& t) {
char *a = &name[0], *b = &t.name[0];
for (; *a == *b; a++, b++) {
if (*a == '\0' || *b == '\0') {
break;
}
}
return (*a < *b) ? true : false;
}
bool operator>(Town& t) {
char *a = &name[0], *b = &t.name[0];
for (; *a == *b; a++, b++) {
if (*a == '\0' || *b == '\0') {
break;
}
}
return (*a > *b) ? true : false;
}
};
class Location {
public:
float latitude;
float longitude;
Location() {
latitude = longitude = 0;
}
Location(float lat, float lng) {
latitude = lat;
longitude = lng;
}
Location(pair<float, float> p) {
latitude = p.first;
longitude = p.second;
}
};
Pair.h
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);
}
Map.h
#ifndef Map_h
#define Map_h
#include "RedBlack.h"
#include "Pair.h"
template<typename T, typename K>
class Map : public RedBlack<T, K> {
public:
typedef typename RedBlack<T, K>::rbNode tNode; // save typing
class iterator; // forward declaration
bool empty();
size_t size();
size_t erase(K); // plus erase(iterator position)
pair<iterator, bool> insert(pair<K, T>);
iterator begin();
iterator end();
iterator rbegin();
iterator rend();
iterator find(K);
void erase(iterator);
T &operator[](K k) {
T* found = this->nodeSearch(k);
if (found == NULL) {
tNode* temp = this->rbMakeNode(k, NULL);
found = (T*)temp->data;
this->root = this->rbInsert(temp, this->root);
this->rbPostInsertFix(temp, this->root);
}
return *found;
}
};
template<typename T, typename K>
class Map<T, K>::iterator : public pair<K, T> {
public:
iterator(tNode*, bool forward = true);
K getKey(); // avoids making node public
iterator &operator++() {
if (isForward) { increment(); }
else { decrement(); }
return *this;
};
iterator &operator++(int) {
if (isForward) { increment(); }
else { decrement(); }
return *this;
};
iterator &operator--() {
if (isForward) { decrement(); }
else { increment(); }
return *this;
};
iterator &operator--(int) {
if (isForward) { decrement(); }
else { increment(); }
return *this;
};
bool operator!=(const iterator a) {
return (this->node != (a.node));
};
bool operator==(const iterator a) {
return(this->node == a.node);
};
protected:
tNode* node;
private:
void increment();
void decrement();
void setPair();
bool isForward;
};
template<typename T, typename K>
Map<T, K>::iterator::iterator(tNode* iNode, bool forward = true) {
isForward = forward;
node = iNode;
if (node) {
setPair(); // node could be NULL
}
}
template<typename T, typename K>
void Map<T, K>::iterator::setPair() {
this->first = node->key;
this->second = *(T*)node->data;
}
template<typename T, typename K>
void Map<T, K>::iterator::increment() {
if (node->right) {
node = node->right;
while (node->left) {
node = node->left;
}
}
else {
if (node->parent) {
tNode* parent = node->parent;
while (parent && (node == parent->right)) {
node = parent;
parent = node->parent;
}
if (node->right != parent) {
node = parent;
}
}
else {
node = node->right; // if no right branch
}
}
if (node) {
setPair();
}
}
template<typename T, typename K>
void Map<T, K>::iterator::decrement() {
if (node->colour == RedBlack<T, K>::RED &&
node->parent->parent == node) {
node = node->right;
}
else if (node->left) {
tNode* child = node->left;
while (child->right) {
child = child->right;
}
node = child;
}
else {
if (node->parent) {
tNode* parent = node->parent;
while (parent && (node == parent->left)) {
node = parent;
parent = parent->parent;
}
node = parent;
}
else {
node = node->left;
}
}
if (node) {
setPair();
}
}
template<typename T, typename K>
K Map<T, K>::iterator::getKey() {
return node->key;
}
template<typename T, typename K>
typename Map<T, K>::iterator Map<T, K>::begin() {
iterator it(this->rbMinimum(this->root));
return it;
}
template<typename T, typename K>
typename Map<T, K>::iterator Map<T, K>::end() {
iterator it(this->rbMaximum(this->root)->right);
return it;
}
template<typename T, typename K>
typename Map<T, K>::iterator Map<T, K>::rbegin() {
iterator it(this->rbMaximum(this->root), false);
return it;
}
template<typename T, typename K>
typename Map<T, K>::iterator Map<T, K>::rend() {
iterator it(this->rbMinimum(this->root)->left);
return it;
}
template<typename T, typename K>
typename Map<T, K>::iterator Map<T, K>::find(K key) {
typename Map<T, K>::rbNode* found = this->rbFind(key, this->root);
if (found) {
iterator it(found);
return it;
}
return end();
}
template<typename T, typename K>
bool Map<T, K>::empty() {
return (this->nodeCount() == 0);
}
template<typename T, typename K>
size_t Map<T, K>::size() {
return this->nodeCount();
}
template<typename T, typename K>
size_t Map<T, K>::erase(K key) {
if (this->deleteNode(key)) {
return 1;
}
return 0;
}
template<typename T, typename K>
void Map<T, K>::erase(iterator what) {
this->deleteNode(what.getKey());
}
template<typename T, typename K>
pair<typename Map<T, K>::iterator, bool> Map<T, K>::insert(pair<K, T> newData) {
this->allowUpdate(false);
this->memoryError = false;
tNode* temp = this->rbMakeNode(newData.first, &newData.second);
this->root = this->rbInsert(temp, this->root);
this->allowUpdate(true);
bool insertOK = !this->memoryError;
if (insertOK) {
this->rbPostInsertFix(temp, this->root);
}
else {
temp = this->rbFind(newData.first, this->root);
}
iterator it(temp);
return make_pair(it, insertOK);
}
#endif
Map.cpp
#include "stdafx.h"
#include <stdint.h>
#include <stdlib.h>
#include <iostream>
#include "Map.h"
#include "Town.h"
#include "Demodata.h"
void testX();
//void test2();
int main()
{
testX();
std::cin.get();
return 0;
}
void testX() {
Map<Location, std::string> myMap;
myMap["Chester"].latitude = 53.196;
myMap["Chester"].longitude = -2.887;
for (int i = 0; i < 5; i++) {
// // we can use the underlying RB tree methods
myMap.insertNode(&places[i][0], new Location(locations[i][0], locations[i][1]));
}
std::cout << "Count: " << myMap.size() << '\n';
}
//void test2() {
// Map<Location, Town> myMap;
// for (int i = 0; i < 5; i++) {
// Town t(&places[i][0]);
// // we can use the underlying RB tree methods
// myMap.insertNode(t, new Location(locations[i][0], locations[i][1]));
// }
// // we can treat the map as an associative array
// for (int i = 5; i < 10; i++) {
// Town t(&places[i][0]);
// myMap[t].latitude = locations[i][0];
// myMap[t].longitude = locations[i][1];
// }
// // we can iterate through the map values in ascending town name order
// for (Map<Location, Town>::iterator it = myMap.begin(); it != myMap.end(); it++) {
// std::cout << it.first.name << " Lat: " << it.second.latitude << " Long: " << it.second.longitude << '\n';
// }
// std::cout << "using insert\n";
// // we can get an iterator from the map insert
// Town t(&places[10][0]);
// Location l(locations[10][0], locations[10][1]);
// pair<Town, Location> p = make_pair(t, l);
// pair<Map<Location, Town>::iterator, bool> r = myMap.insert(p);
// if (r.second) {
// // the insert was good but we could also iterate to end
// for (; r.first != myMap.end(); r.first++) {
// std::cout << r.first.first.name << " Lat: " << r.first.second.latitude << " Long: " << r.first.second.longitude << '\n';
// }
// }
// // that insert format was a bit clumsy
// // how about?
// Location s(52.7068, -2.755);
// myMap.insert(pair<Town, Location>("Shrewsbury", s));
// // or
// myMap.insert(pair<Town, Location>("Birmingham", pair<float, float>(52.484, -1.9007)));
// // or
// myMap["Chester"].latitude = 53.196;
// myMap["Chester"].longitude = -2.887;
// //
// std::cout << "now a reverse iteration\n";
// for (Map<Location, Town>::iterator it = myMap.rbegin(); it != myMap.rend(); it++) {
// std::cout << it.first.name << " Lat: " << it.second.latitude << " Long: " << it.second.longitude << '\n';
// }
// std::cout << "Count: " << myMap.size() << '\n';
// std::cout << "Erase an item from map\n";
// myMap.erase(t);
//
// std::cout << "Count now: " << myMap.size() << '\n';
// for (Map<Location, Town>::iterator it = myMap.rbegin(); it != myMap.rend(); it++) {
// std::cout << it.first.name << " Lat: " << it.second.latitude << " Long: " << it.second.longitude << '\n';
// }
// Town f(&places[4][0]);
// Map<Location, Town>::iterator it = myMap.find(f);
// if (it != myMap.end()) {
// std::cout << "Found: " << it.first.name << " Lat: " << it.second.latitude << " Long: " << it.second.longitude << '\n';
// // we can also erase using the iterator
// myMap.erase(it);
// std::cout << "But now erased, so count: " << myMap.size() << '\n';
// }
// Town g(&places[11][0]);
// float lt = myMap[g].latitude; // value not previouly created
// std::cout << "Created entry " << g.name << " Latitude: " << lt << '\n';
// myMap.clear();
// std::cout << "Clear method run so count: " << myMap.size() << '\n';
//}
Map.ino
#include "Map.h"
#include "Town.h"
#include "Demodata.h"
struct cBoard{
uint8_t player;
uint8_t piece;
};
template<class T> inline Print &operator <<(Print &obj, T arg) { obj.print(arg); return obj; }
void setup() {
Serial.begin(115200);
Map<cBoard, uint8_t> myMap;
Serial << "Is Empty is " << (myMap.empty() ? "true\n" : "false\n");
cBoard mBoard = {1,2};
myMap.insertNode(5, &mBoard);
cBoard nBoard = myMap[5];
Serial << nBoard.player << " " << nBoard.piece << '\n';
nBoard.player = 25;
myMap[5] = nBoard;
Serial << myMap[5].player << '\n';
myMap[7].player = 26; // remember 7 has not be inserted
myMap[7].piece = 8;
nBoard = myMap[7];
Serial << nBoard.player << " " << nBoard.piece << '\n';
Serial << "Size: " << myMap.size() << '\n';
mBoard.player = 2;
mBoard.piece = 4;
myMap.insertNode(2, &mBoard);
for(Map<cBoard, uint8_t>::iterator it = myMap.begin(); it != myMap.end(); ++it) {
cBoard c = it.second;
Serial << "Square: " << it.first << " Player: " << c.player << " Piece: " << c.piece << '\n';
}
for(Map<cBoard, uint8_t>::iterator it = myMap.rbegin(); it != myMap.rend(); ++it) {
cBoard c = it.second;
Serial << "Square: " << it.first << " Player: " << c.player << " Piece: " << c.piece << '\n';
}
Map<cBoard, uint8_t>::iterator it = myMap.find(5);
myMap.erase(it);
Serial << "Erased: 5\n"; // exposes a bug in the delete fix in Red-Black
for(Map<cBoard, uint8_t>::iterator it = myMap.begin(); it != myMap.end(); ++it) {
cBoard c = it.second;
Serial << "Square: " << it.first << " Player: " << c.player << " Piece: " << c.piece << '\n';
}
myMap.insert(make_pair((uint8_t)9, mBoard));
for(Map<cBoard, uint8_t>::iterator it = myMap.rbegin(); it != myMap.rend(); ++it) {
cBoard c = it.second;
Serial << "Square: " << it.first << " Player: " << c.player << " Piece: " << c.piece << '\n';
}
}
Read the chapter in my book C++ Data Structures with immediate download from Amazon