#include <memory>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cassert>
#include <string>
#include <type_traits>

class TreeNode;
class TreeFolderNode;

class Tree
{
public:
	typedef std::unique_ptr<TreeNode> TreeNodePtr;

	Tree();
	// copy allowed!
	Tree(const Tree& rhs);
	// copy
	Tree& operator=(const Tree& rhs);
	// move allowed
	Tree(Tree&& rhs);
	// move
	Tree& operator=(Tree&& rhs);

	// dtor not necessary because of unique_ptr

	const TreeNode& GetRootNode() const { return *rootNode; }
	TreeNode& GetRootNode() { return *rootNode; }

private:
	TreeNodePtr rootNode;
};

// 

class TreeNode
{
public:
	typedef std::unique_ptr<TreeNode> TreeNodePtr;
	typedef std::vector<TreeNodePtr> TreeNodePtrVector;

	TreeNode() : parent(nullptr) {}

	template<typename T>
	typename std::enable_if<std::is_base_of<TreeNode, T>::value, T&>::type
		Add(std::unique_ptr<T>&& ptr)
	{
		T& ref = *ptr;

		ptr->parent = this;
		children.push_back(std::move(ptr));

		return ref;
	}

	// emplaces element
	template<typename T, typename... Args>
	typename std::enable_if<std::is_base_of<TreeNode, T>::value, T&>::type
		Emplace(Args&&... args)
	{
		return Add(std::make_unique<T>(std::forward<Args>(args)...));
	}

	// removes node from current tree and returns it; memory management is no longer maintained by TreeNode
	TreeNodePtr Release()
	{
		assert(parent && "Releasing root node is not possible. If moving is wished, move whole tree instead.");

		return parent->releaseChild(this);
	}

	virtual void Foo() const {};
	virtual TreeNodePtr Clone() const
	{
		return TreeNodePtr(new TreeNode(*this));
	}

	const TreeNodePtrVector& GetChildren() const { return children; }
	const TreeNode* GetParent() const { return parent; }

	void AddChildrenFrom(const TreeNode& otherNode)
	{
		for (const TreeNodePtr& nodePtr : otherNode.children)
		{
			TreeNodePtr ptr(std::move(nodePtr->Clone()));
			Add(std::move(ptr));
		}
	}

	virtual bool IsFolder() const { return true; };

protected:
	// only for cloning
	TreeNode(const TreeNode& rhs) : parent(rhs.parent)
	{
		AddChildrenFrom(rhs);
	}

	// release child and return it
	TreeNodePtr releaseChild(const TreeNode* child)
	{
		// find child
		auto it = std::find_if(children.begin(), children.end(), [&](const TreeNodePtr& currentChild) {return &*currentChild == child; });

		TreeNodePtr releasedNode(std::move(*it));

		children.erase(it);

		return releasedNode;
	}

private:
	TreeNode* parent;
	TreeNodePtrVector children;
};

//

class TreeFolderNode : public TreeNode
{
public:
	TreeFolderNode(std::string value) : value(value) {}

	void Foo() const override { std::cout << "Folder: " << value << '\n'; }

	TreeNodePtr Clone() const override
	{
		return TreeNodePtr(new TreeFolderNode(*this));
	}

private:
	// private copy ctor for cloning
	TreeFolderNode(const TreeFolderNode& rhs) = default;

	std::string value;
};

// simple traverse algorithm for testing

void traverseOutput(const TreeNode& node, int level = 0)
{
	for (int n = 0; n < level; ++n)
		std::cout << ">";
	std::cout << " ";

	node.Foo();

	for (auto& childNode : node.GetChildren())
	{
		traverseOutput(*childNode, level + 1);
	}
}


//

//

Tree::Tree() : rootNode(new TreeNode)
{

}

// ===

Tree::Tree(const Tree& rhs)
	: rootNode(std::move(rhs.rootNode->Clone()))
{
}

// ===

Tree& Tree::operator=(const Tree& rhs)
{
	rootNode = std::move(rhs.GetRootNode().Clone());
	return *this;
}

// ===

Tree::Tree(Tree&& rhs)
	: rootNode(std::move(rhs.rootNode))
{
}

// ===

Tree& Tree::operator=(Tree&& rhs)
{
	rootNode = std::move(rhs.rootNode);
	return *this;
}


// ===	
int main()
{
	Tree tree;
	tree.GetRootNode().Emplace<TreeFolderNode>("Folder 1");
	tree.GetRootNode().Emplace<TreeFolderNode>("Folder 2");

	auto& folder3 = tree.GetRootNode().Emplace<TreeFolderNode>("Folder3");

	folder3.Emplace<TreeFolderNode>("Folder 4");
	folder3.Emplace<TreeFolderNode>("Folder 5");

	Tree copy(tree);

	std::cout << "\nTree:\n";
	traverseOutput(tree.GetRootNode());
	std::cout << "\nTree Copy:\n";
	traverseOutput(copy.GetRootNode());

	Tree moved(std::move(tree));
	std::cout << "\nMoved Tree:\n";
	traverseOutput(copy.GetRootNode());
	std::cout << "\nOld Tree (should be empty now):\n";
	traverseOutput(tree.GetRootNode());

	// space test
	auto heapTree = std::unique_ptr<Tree>(new Tree(copy));

	std::cout << "\nHeap Tree:\n";
	traverseOutput(heapTree->GetRootNode());

	Tree heapCopy(*heapTree);
	Tree heapMoved(std::move(*heapTree));

	// destroy heapTree and allocate random space
	heapTree = nullptr;
	std::unique_ptr<double[]> doubles(new double[1000]);

	// heapTree invalid now, but heapCopy and heapMoved should work
	std::cout << "\nCopied Tree:\n";
	traverseOutput(heapCopy.GetRootNode());
	std::cout << "\nMoved Tree:\n";
	traverseOutput(heapMoved.GetRootNode());

	// now copy and std::move only parts
	Tree onlyPart;
	onlyPart.GetRootNode().Add(std::move(heapCopy.GetRootNode().GetChildren()[2]->Clone()));

	std::cout << "\nCopied Tree after part copy:\n";
	traverseOutput(heapCopy.GetRootNode());
	std::cout << "\nPart Copy Tree:\n";
	traverseOutput(onlyPart.GetRootNode());

	// now std::move parts
	Tree onlyPartMoved;

	onlyPartMoved.GetRootNode().Add(std::move(heapCopy.GetRootNode().GetChildren()[2]->Release()));

	std::cout << "\nNew tree with released node of first tree:\n";
	traverseOutput(onlyPartMoved.GetRootNode());
	std::cout << "\nOld tree from which node was released:\n";
	traverseOutput(heapCopy.GetRootNode());

	return 0;
}