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

Tree Copy:
 > Folder: Folder 1
> Folder: Folder 2
> Folder: Folder 3
>> Folder: Folder 4
>> Folder: Folder 5

Moved Tree:
 > Folder: Folder 1
> Folder: Folder 2
> Folder: Folder 3
>> Folder: Folder 4
>> Folder: Folder 5

Old Tree (should be empty now):

Heap Tree:
 > Folder: Folder 1
> Folder: Folder 2
> Folder: Folder 3
>> Folder: Folder 4
>> Folder: Folder 5

Copied Tree:
 > Folder: Folder 1
> Folder: Folder 2
> Folder: Folder 3
>> Folder: Folder 4
>> Folder: Folder 5

Moved Tree:
 > Folder: Folder 1
> Folder: Folder 2
> Folder: Folder 3
>> Folder: Folder 4
>> Folder: Folder 5

Copied Tree after part copy:
 > Folder: Folder 1
> Folder: Folder 2
> Folder: Folder 3
>> Folder: Folder 4
>> Folder: Folder 5

Part Copy Tree:
 > Folder: Folder 3
>> Folder: Folder 4
>> Folder: Folder 5

New tree with released node of first tree:
 > Folder: Folder 3
>> Folder: Folder 4
>> Folder: Folder 5

Old tree from which node was released:
 > Folder: Folder 1
> Folder: Folder 2
https://ideone.com/70P3o4
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!