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

class TreeNode;

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

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

	// dtor not necessary because of std::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) {}

	// adds newly created node; TreeNode owns new node now
	void Add(TreeNode* ptr)
	{
		ptr->parent = this;
		children.push_back(TreeNodePtr(ptr));
	}

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

		return parent->releaseChild(this);
	}

	virtual void Foo() const {};
	virtual TreeNode* Clone() const
	{
		return 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)
			Add(nodePtr->Clone());
	}

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

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

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

		TreeNode* releasedNode = it->release();

		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'; }

	TreeNode* Clone() const override
	{
		return 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)
	{
		if (node)
		{
			for (int n = 0; n < level; ++n)
				std::cout << ">";
			std::cout << " ";

			node->Foo();

			for (const TreeNode::TreeNodePtr& childNode : node->GetChildren())
			{
				traverseOutput(&*childNode, level + 1);
			}
		}
	}
	
	//

//

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

}

// ===

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

// ===

Tree& Tree::operator=(const Tree& rhs)
{
	this->rootNode.reset(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()->Add(new TreeFolderNode("Folder 1"));
	tree.GetRootNode()->Add(new TreeFolderNode("Folder 2"));

	auto folder3 = new TreeFolderNode("Folder 3");
	tree.GetRootNode()->Add(folder3);

	folder3->Add(new TreeFolderNode("Folder 4"));
	folder3->Add(new 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(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(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;
}