fork(1) download
copy 
  1. #include <memory>
  2. #include <vector>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <cassert>
  6. #include <string>
  7. #include <type_traits>
  8.  
  9. class TreeNode;
  10. class TreeFolderNode;
  11.  
  12. class Tree
  13. {
  14. public:
  15. 	typedef std::unique_ptr<TreeNode> TreeNodePtr;
  16.  
  17. 	Tree();
  18. 	// copy allowed!
  19. 	Tree(const Tree& rhs);
  20. 	// copy
  21. 	Tree& operator=(const Tree& rhs);
  22. 	// move allowed
  23. 	Tree(Tree&& rhs);
  24. 	// move
  25. 	Tree& operator=(Tree&& rhs);
  26.  
  27. 	// dtor not necessary because of unique_ptr
  28.  
  29. 	const TreeNode& GetRootNode() const { return *rootNode; }
  30. 	TreeNode& GetRootNode() { return *rootNode; }
  31.  
  32. private:
  33. 	TreeNodePtr rootNode;
  34. };
  35.  
  36. // 
  37.  
  38. class TreeNode
  39. {
  40. public:
  41. 	typedef std::unique_ptr<TreeNode> TreeNodePtr;
  42. 	typedef std::vector<TreeNodePtr> TreeNodePtrVector;
  43.  
  44. 	TreeNode() : parent(nullptr) {}
  45.  
  46. 	template<typename T>
  47. 	typename std::enable_if<std::is_base_of<TreeNode, T>::value, T&>::type
  48. 		Add(std::unique_ptr<T>&& ptr)
  49. 	{
  50. 		T& ref = *ptr;
  51.  
  52. 		ptr->parent = this;
  53. 		children.push_back(std::move(ptr));
  54.  
  55. 		return ref;
  56. 	}
  57.  
  58. 	// emplaces element
  59. 	template<typename T, typename... Args>
  60. 	typename std::enable_if<std::is_base_of<TreeNode, T>::value, T&>::type
  61. 		Emplace(Args&&... args)
  62. 	{
  63. 		return Add(std::make_unique<T>(std::forward<Args>(args)...));
  64. 	}
  65.  
  66. 	// removes node from current tree and returns it; memory management is no longer maintained by TreeNode
  67. 	TreeNodePtr Release()
  68. 	{
  69. 		assert(parent && "Releasing root node is not possible. If moving is wished, move whole tree instead.");
  70.  
  71. 		return parent->releaseChild(this);
  72. 	}
  73.  
  74. 	virtual void Foo() const {};
  75. 	virtual TreeNodePtr Clone() const
  76. 	{
  77. 		return TreeNodePtr(new TreeNode(*this));
  78. 	}
  79.  
  80. 	const TreeNodePtrVector& GetChildren() const { return children; }
  81. 	const TreeNode* GetParent() const { return parent; }
  82.  
  83. 	void AddChildrenFrom(const TreeNode& otherNode)
  84. 	{
  85. 		for (const TreeNodePtr& nodePtr : otherNode.children)
  86. 		{
  87. 			TreeNodePtr ptr(std::move(nodePtr->Clone()));
  88. 			Add(std::move(ptr));
  89. 		}
  90. 	}
  91.  
  92. 	virtual bool IsFolder() const { return true; };
  93.  
  94. protected:
  95. 	// only for cloning
  96. 	TreeNode(const TreeNode& rhs) : parent(rhs.parent)
  97. 	{
  98. 		AddChildrenFrom(rhs);
  99. 	}
  100.  
  101. 	// release child and return it
  102. 	TreeNodePtr releaseChild(const TreeNode* child)
  103. 	{
  104. 		// find child
  105. 		auto it = std::find_if(children.begin(), children.end(), [&](const TreeNodePtr& currentChild) {return &*currentChild == child; });
  106.  
  107. 		TreeNodePtr releasedNode(std::move(*it));
  108.  
  109. 		children.erase(it);
  110.  
  111. 		return releasedNode;
  112. 	}
  113.  
  114. private:
  115. 	TreeNode* parent;
  116. 	TreeNodePtrVector children;
  117. };
  118.  
  119. //
  120.  
  121. class TreeFolderNode : public TreeNode
  122. {
  123. public:
  124. 	TreeFolderNode(std::string value) : value(value) {}
  125.  
  126. 	void Foo() const override { std::cout << "Folder: " << value << '\n'; }
  127.  
  128. 	TreeNodePtr Clone() const override
  129. 	{
  130. 		return TreeNodePtr(new TreeFolderNode(*this));
  131. 	}
  132.  
  133. private:
  134. 	// private copy ctor for cloning
  135. 	TreeFolderNode(const TreeFolderNode& rhs) = default;
  136.  
  137. 	std::string value;
  138. };
  139.  
  140. // simple traverse algorithm for testing
  141.  
  142. void traverseOutput(const TreeNode& node, int level = 0)
  143. {
  144. 	for (int n = 0; n < level; ++n)
  145. 		std::cout << ">";
  146. 	std::cout << " ";
  147.  
  148. 	node.Foo();
  149.  
  150. 	for (auto& childNode : node.GetChildren())
  151. 	{
  152. 		traverseOutput(*childNode, level + 1);
  153. 	}
  154. }
  155.  
  156.  
  157. //
  158.  
  159. //
  160.  
  161. Tree::Tree() : rootNode(new TreeNode)
  162. {
  163.  
  164. }
  165.  
  166. // ===
  167.  
  168. Tree::Tree(const Tree& rhs)
  169. 	: rootNode(std::move(rhs.rootNode->Clone()))
  170. {
  171. }
  172.  
  173. // ===
  174.  
  175. Tree& Tree::operator=(const Tree& rhs)
  176. {
  177. 	rootNode = std::move(rhs.GetRootNode().Clone());
  178. 	return *this;
  179. }
  180.  
  181. // ===
  182.  
  183. Tree::Tree(Tree&& rhs)
  184. 	: rootNode(std::move(rhs.rootNode))
  185. {
  186. }
  187.  
  188. // ===
  189.  
  190. Tree& Tree::operator=(Tree&& rhs)
  191. {
  192. 	rootNode = std::move(rhs.rootNode);
  193. 	return *this;
  194. }
  195.  
  196.  
  197. // ===	
  198. int main()
  199. {
  200. 	Tree tree;
  201. 	tree.GetRootNode().Emplace<TreeFolderNode>("Folder 1");
  202. 	tree.GetRootNode().Emplace<TreeFolderNode>("Folder 2");
  203.  
  204. 	auto& folder3 = tree.GetRootNode().Emplace<TreeFolderNode>("Folder3");
  205.  
  206. 	folder3.Emplace<TreeFolderNode>("Folder 4");
  207. 	folder3.Emplace<TreeFolderNode>("Folder 5");
  208.  
  209. 	Tree copy(tree);
  210.  
  211. 	std::cout << "\nTree:\n";
  212. 	traverseOutput(tree.GetRootNode());
  213. 	std::cout << "\nTree Copy:\n";
  214. 	traverseOutput(copy.GetRootNode());
  215.  
  216. 	Tree moved(std::move(tree));
  217. 	std::cout << "\nMoved Tree:\n";
  218. 	traverseOutput(copy.GetRootNode());
  219. 	std::cout << "\nOld Tree (should be empty now):\n";
  220. 	traverseOutput(tree.GetRootNode());
  221.  
  222. 	// space test
  223. 	auto heapTree = std::unique_ptr<Tree>(new Tree(copy));
  224.  
  225. 	std::cout << "\nHeap Tree:\n";
  226. 	traverseOutput(heapTree->GetRootNode());
  227.  
  228. 	Tree heapCopy(*heapTree);
  229. 	Tree heapMoved(std::move(*heapTree));
  230.  
  231. 	// destroy heapTree and allocate random space
  232. 	heapTree = nullptr;
  233. 	std::unique_ptr<double[]> doubles(new double[1000]);
  234.  
  235. 	// heapTree invalid now, but heapCopy and heapMoved should work
  236. 	std::cout << "\nCopied Tree:\n";
  237. 	traverseOutput(heapCopy.GetRootNode());
  238. 	std::cout << "\nMoved Tree:\n";
  239. 	traverseOutput(heapMoved.GetRootNode());
  240.  
  241. 	// now copy and std::move only parts
  242. 	Tree onlyPart;
  243. 	onlyPart.GetRootNode().Add(std::move(heapCopy.GetRootNode().GetChildren()[2]->Clone()));
  244.  
  245. 	std::cout << "\nCopied Tree after part copy:\n";
  246. 	traverseOutput(heapCopy.GetRootNode());
  247. 	std::cout << "\nPart Copy Tree:\n";
  248. 	traverseOutput(onlyPart.GetRootNode());
  249.  
  250. 	// now std::move parts
  251. 	Tree onlyPartMoved;
  252.  
  253. 	onlyPartMoved.GetRootNode().Add(std::move(heapCopy.GetRootNode().GetChildren()[2]->Release()));
  254.  
  255. 	std::cout << "\nNew tree with released node of first tree:\n";
  256. 	traverseOutput(onlyPartMoved.GetRootNode());
  257. 	std::cout << "\nOld tree from which node was released:\n";
  258. 	traverseOutput(heapCopy.GetRootNode());
  259.  
  260. 	return 0;
  261. }
Runtime error #stdin #stdout 0s 3240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/o3b8T0
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!