Задача: Древовидные структуры
Исходник: Древовидный тип данных в .NET, язык: C# [code #574, hits: 10610]
автор: - [добавлен: 12.01.2009]
  1. #region Using's
  2.  
  3. using System;
  4. using System.Collections.Generic;
  5. using System.Collections.ObjectModel;
  6. using System.Diagnostics;
  7. using System.Linq;
  8.  
  9. #endregion Using's
  10.  
  11. internal static class Program
  12. {
  13. private static void Main() {
  14. var tree = Tree.New(1);
  15. tree.Add(2);
  16. tree.Add(3);
  17. tree.Children[0].Add(4);
  18. tree.Children[1].Add(5);
  19.  
  20. foreach(var item in tree.Nodes()) {
  21. Debug.Print(item.ToString());
  22. }//for
  23.  
  24. foreach(var item in tree.Values()) {
  25. Debug.Print(item.ToString());
  26. }//for
  27. }
  28. }
  29.  
  30. [DebuggerDisplay("{ToString()}")]
  31. [Serializable]
  32. public sealed class Node<T>
  33. {
  34. #region Fields
  35.  
  36. private readonly IList<Node<T>> children;
  37.  
  38. #endregion Fields
  39.  
  40. #region Constructor(s)
  41.  
  42. public Node() {
  43. children = new NodeCollection(this);
  44. }
  45.  
  46. public Node(T value) : this() {
  47. Value = value;
  48. }
  49.  
  50. #endregion Constructor(s)
  51.  
  52. #region Properties
  53.  
  54. public Node<T> Parent { get; private set; }
  55.  
  56. [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
  57. public IList<Node<T>> Children {
  58. [DebuggerStepThrough]
  59. get { return children; }
  60. }
  61.  
  62. public T Value { get; set; }
  63.  
  64. #endregion Properties
  65.  
  66. #region Methods
  67.  
  68. public Node<T> Add(T value) {
  69. var item = new Node<T>(value);
  70. Children.Add(item);
  71. return item;
  72. }
  73.  
  74. #endregion Methods
  75.  
  76. #region Overrides
  77.  
  78. public override string ToString() {
  79. return "<Node> {" + Value + "}";
  80. }
  81.  
  82. #endregion Overrides
  83.  
  84. #region class NodeCollection
  85.  
  86. [Serializable]
  87. private sealed class NodeCollection : Collection<Node<T>>
  88. {
  89. #region Fields
  90.  
  91. private readonly Node<T> owner;
  92.  
  93. #endregion Fields
  94.  
  95. #region Constructor(s)
  96.  
  97. public NodeCollection(Node<T> owner) {
  98. if(owner == null) {
  99. throw new ArgumentNullException("owner");
  100. }//if
  101.  
  102. this.owner = owner;
  103. }
  104.  
  105. #endregion Constructor(s)
  106.  
  107. #region Properties
  108.  
  109. private Node<T> Owner {
  110. [DebuggerStepThrough]
  111. get { return owner; }
  112. }
  113.  
  114. #endregion Properties
  115.  
  116. #region Methods
  117.  
  118. private void AttachItem(Node<T> item) {
  119. if(item == null) {
  120. throw new ArgumentNullException("item");
  121. }//if
  122. item.Parent = Owner;
  123. }
  124.  
  125. private void DetachItem(Node<T> item) {
  126. if(item == null) {
  127. throw new ArgumentNullException("item");
  128. }//if
  129. Debug.Assert(item.Parent == Owner, "item.Parent == Owner");
  130. item.Parent = null;
  131. }
  132.  
  133. private void ValidateItem(Node<T> item) {
  134. if(item == null) {
  135. throw new ArgumentNullException("item");
  136. } else if(item.Parent != null) {
  137. throw new InvalidOperationException("item.Parent != null");
  138. }//if
  139. }
  140.  
  141. #endregion Methods
  142.  
  143. #region Overrides
  144.  
  145. protected override void InsertItem(int index, Node<T> item) {
  146. ValidateItem(item);
  147. base.InsertItem(index, item);
  148. AttachItem(item);
  149. }
  150.  
  151. protected override void SetItem(int index, Node<T> item) {
  152. ValidateItem(item);
  153. DetachItem(this[index]);
  154. base.SetItem(index, item);
  155. AttachItem(item);
  156. }
  157.  
  158. protected override void RemoveItem(int index) {
  159. DetachItem(this[index]);
  160. base.RemoveItem(index);
  161. }
  162.  
  163. protected override void ClearItems() {
  164. foreach(var item in Items) {
  165. DetachItem(item);
  166. }//for
  167. base.ClearItems();
  168. }
  169.  
  170. #endregion Overrides
  171. }
  172.  
  173. #endregion class NodeCollection
  174. }
  175.  
  176. public static class Tree
  177. {
  178. #region Methods
  179.  
  180. public static Node<T> New<T>(T value) {
  181. return new Node<T>(value);
  182. }
  183.  
  184. public static bool IsRoot<T>(Node<T> node) {
  185. if(node == null) {
  186. throw new ArgumentNullException("node");
  187. }//if
  188.  
  189. return node.Parent == null;
  190. }
  191.  
  192. public static IEnumerable<Node<T>> Nodes<T>(this Node<T> node) {
  193. if(node == null) {
  194. throw new ArgumentNullException("node");
  195. }//if
  196.  
  197. return NodesIterator(node);
  198. }
  199.  
  200. private static IEnumerable<Node<T>> NodesIterator<T>(Node<T> node) {
  201. Debug.Assert(node != null, "node != null");
  202. yield return node;
  203. foreach(var item in NodesIterator(node.Children)) {
  204. yield return item;
  205. }//for
  206. }
  207.  
  208. private static IEnumerable<Node<T>> NodesIterator<T>(IEnumerable<Node<T>> children) {
  209. Debug.Assert(children != null, "children != null");
  210. foreach(var child in children) {
  211. foreach(var item in child.Nodes()) {
  212. yield return item;
  213. }//for
  214. }//for
  215. }
  216.  
  217. public static IEnumerable<T> Values<T>(this Node<T> root) {
  218. if(root == null) {
  219. throw new ArgumentNullException("root");
  220. }//if
  221.  
  222. return from node in root.Nodes()
  223. select node.Value;
  224. }
  225.  
  226. #endregion Methods
  227. }
  228.  
  229.  
  230. // А вот и fluent-interface с тестом
  231. using System.IO;
  232. using System.Xml.Serialization;
  233. using NUnit.Framework;
  234. using NUnit.Framework.SyntaxHelpers;
  235.  
  236. namespace Frontier.Framework.Core.Collections.Test
  237. {
  238. [TestFixture]
  239. public class TreeTest
  240. {
  241. [Test]
  242. public void CreateEmptyTreeAndCheckHasChilds()
  243. {
  244. ITree<int> root = TreeNode<int>
  245. .RootNode("root", 1000);
  246.  
  247. Assert.IsFalse(root.HasChilds, "might not has a childs");
  248. }
  249.  
  250. [Test]
  251. public void CreateFullTreeAndCheck()
  252. {
  253. ITree<int> root = TreeNode<int>
  254. .RootNode("root", 0)
  255. .Begin
  256. .Append("a1", 1)
  257. .Append("a2", 2)
  258. .Begin
  259. .Append("b1", 1)
  260. .Append("b2", 2)
  261. .End
  262. .Append("a3", 3)
  263. .End;
  264.  
  265.  
  266. Assert.That(1, Is.EqualTo(root["a1"].Value));
  267. Assert.That(2, Is.EqualTo(root["a2"].Value));
  268. Assert.That(3, Is.EqualTo(root["a3"].Value));
  269. Assert.That(1, Is.EqualTo(root["a2"]["b1"].Value));
  270. Assert.That(2, Is.EqualTo(root["a2"]["b2"].Value));
  271. }
  272.  
  273. [Test]
  274. public void CreateRoot()
  275. {
  276. TreeNode<int>
  277. .RootNode("root", 1000);
  278. }
  279.  
  280. [Test]
  281. public void CreateRootAndCheck()
  282. {
  283. ITree<int> root = TreeNode<int>
  284. .RootNode("root", 1000);
  285.  
  286. Assert.That("root", Is.EqualTo(root.Id));
  287. Assert.That(1000, Is.EqualTo(root.Value));
  288. }
  289.  
  290. [Test]
  291. public void CreateRootAndEnumChilds()
  292. {
  293. ITree<int> root = TreeNode<int>
  294. .RootNode("root", 1000)
  295. .Begin
  296. .Append("a1", 1)
  297. .Append("a2", 2)
  298. .Append("a3", 3)
  299. .End;
  300.  
  301.  
  302. int count = 0;
  303. foreach (var node in root)
  304. count++;
  305.  
  306. Assert.AreEqual(3, count);
  307. }
  308.  
  309. [Test]
  310. public void CreateRootUnnamedAndCheck()
  311. {
  312. ITree<int> root = TreeNode<int>
  313. .RootNode(1000);
  314.  
  315. Assert.That("root", Is.EqualTo(root.Id));
  316. }
  317.  
  318. [Test]
  319. public void CreateSimpleTreeAndUseIndexerToCheck()
  320. {
  321. ITree<int> tree = TreeNode<int>
  322. .RootNode("root", 0)
  323. .Append("a1", 1)
  324. .Append("a2", 2)
  325. .Append("a3", 3);
  326.  
  327.  
  328. int value;
  329. Assert.IsTrue(tree.HasChilds);
  330.  
  331. value = tree.Value;
  332. Assert.That(0, Is.EqualTo(value));
  333.  
  334. value = tree["a1"].Value;
  335. Assert.That(1, Is.EqualTo(value));
  336.  
  337. value = tree["a2"].Value;
  338. Assert.That(2, Is.EqualTo(value));
  339.  
  340. value = tree["a3"].Value;
  341. Assert.That(3, Is.EqualTo(value));
  342. }
  343.  
  344. [Test]
  345. public void CreateSimpleTreeAndUseUnnamedIndexerToCheck()
  346. {
  347. ITree<int> tree = TreeNode<int>
  348. .RootNode(0)
  349. .Append(1)
  350. .Append(2)
  351. .Append(3);
  352.  
  353.  
  354. int value;
  355. Assert.IsTrue(tree.HasChilds);
  356.  
  357. value = tree.Value;
  358. Assert.That(0, Is.EqualTo(value));
  359.  
  360. value = tree[0].Value;
  361. Assert.That(1, Is.EqualTo(value));
  362.  
  363. value = tree[1].Value;
  364. Assert.That(2, Is.EqualTo(value));
  365.  
  366. value = tree[2].Value;
  367. Assert.That(3, Is.EqualTo(value));
  368. }
  369.  
  370. [Test]
  371. public void CreateTreeAndCheckItByUseIndexer()
  372. {
  373. ITree<int> root = TreeNode<int>
  374. .RootNode("root", 1000);
  375.  
  376. int value = root["root"].Value;
  377. Assert.That(1000, Is.EqualTo(value));
  378. }
  379.  
  380. [Test]
  381. public void CreateTreeAndInvokeToString()
  382. {
  383. ITree<int> root = TreeNode<int>
  384. .RootNode("root", 1000);
  385.  
  386. var expected = "TreeNode<Int32>(\"root\")";
  387. var actual = root.ToString();
  388. Assert.AreEqual(expected, actual);
  389. }
  390.  
  391. [Test, Category("Persistence"), Ignore]
  392. public void SaveToXml()
  393. {
  394. ITree<int> root = TreeNode<int>
  395. .RootNode("root", 1000)
  396. .Begin
  397. .Append("a1", 1)
  398. .Append("a2", 2)
  399. .Append("a3", 3)
  400. .End;
  401.  
  402. string xml;
  403. using (TextWriter writer = new StringWriter())
  404. {
  405. var serializer = new XmlSerializer(root.GetType());
  406. serializer.Serialize(writer, root);
  407. xml = writer.ToString();
  408. }
  409. Assert.Fail("Нихера не реализовано");
  410. }
  411. }
  412. }
Хранение в виде "дерево", в узлах — пользовательский тип данных.

http://www.rsdn.ru/Forum/message/3215966.aspx
Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

+добавить реализацию