SceneGraphTest.cpp

#include "pch.h"
#include <iostream>
#include <vector>
#include <array>
#include <map>

#define LOG(x) std::cout << x << std::endl

struct Node
{
	bool alive = false;
	std::string name = "noname";
	Node* parent = nullptr;
};

const int SIZE = 64;
// Fixed size preallocated array of all nodes.
// All nodes are dead by default
// Not using vector to make sure pointers don't change
std::array<Node, SIZE> nodes;
// A multi-key map that stores parent-child relationships:
std::multimap<Node*, Node*> childrenMap;

// Adds a new node
Node* Add(std::string name, Node* parent)
{
	// Loop through node array and find a first dead one
	for (size_t i = 0; i < SIZE; i++)
	{
		if (!nodes[i].alive)
		{
			auto* n = &(nodes[i]);
			n->alive = true;
			n->name = name;
			n->parent = nullptr; // important!

			if (parent != nullptr)
			{
				n->parent = parent;
				childrenMap.insert({ parent, n });
			}

			LOG("+ Added <" << n->name.c_str() << "> to [" << i << "]");

			return &nodes[i];
		}
	}

	LOG("NOT ENOUGH SPACE!");
	return nullptr;
}

// [private] Delete all children recursively
void RecurseKill(Node* node)
{
	if (childrenMap.count(node) > 0)
	{
		auto children = childrenMap.equal_range(node);
		for (auto it = children.first; it != children.second; it++)
		{
			Node* child = it->second;
			RecurseKill(child);
		}

		// Removes all paris with key from childrenMap:
		childrenMap.erase(node);
	}

	node->alive = false;
}

// Deletes the node and all its children
void Delete(Node* node)
{
	std::cout << "- Removing <" << node->name.c_str() << ">" << std::endl;

	// remove parent-this pair from map
	if (node->parent != nullptr)
	{
		// Seems that the only way to do this is loop through the pairs with key until you find the pair
		auto parentsChildren = childrenMap.equal_range(node->parent);

		auto it = parentsChildren.first;
		for (; it != parentsChildren.second; ++it) {
			if (it->second == node) {
				childrenMap.erase(it);
				break;
			}
		}

		//std::cout << "Removed " << node->parent->name.c_str() << " - " << node->name.c_str() << std::endl;

		node->parent = nullptr; // No need to actually do this
	}

	RecurseKill(node);
}

// Outputs the graph
void RecurseLog(Node* node, int depth)
{
	auto children = childrenMap.equal_range(node);

	std::string tabs = "";
	tabs.append(depth, '\t');

	std::cout << tabs.c_str() << "+ " << node->name.c_str() << std::endl;

	for (auto it = children.first; it != children.second; it++)
	{
		Node* child = it->second;
		RecurseLog(child, depth + 1);
	}
}

int main()
{
	std::cout << "### OPERATIONS: ###" << std::endl;
	std::cout << std::endl;

	Node* root = Add("ROOT", nullptr);
	Node* child1 = Add("first", root);
	Node* child2 = Add("second", root);
	Node* child21 = Add("child of second", child2);
	Node* child4 = Add("child of first", child1);
	Add("child of child of first", child4);
	Node* baz = Add("bazinga", child4);
	Add("bazinga2", child4);

	Delete(child1);

	Add("Post remove node", root);

	// OUTPUT

	std::cout << std::endl;
	std::cout << "### HIERARCHY: ###" << std::endl;
	std::cout << std::endl;

	for (Node& node : nodes)
	{
		if (!node.alive)
			continue;

		if (node.parent)
			continue;

		RecurseLog(&node, 0);

	}

	std::cout << std::endl;

	std::cout << std::endl;
	std::cout << "All alive Nodes:" << std::endl;
	std::cout << std::endl;

	for (Node& node : nodes)
	{
		if (!node.alive)
			continue;

		std::cout << node.name.c_str() << std::endl;
	}
}