Mercury library 1.0 Translation of CFG grammars into an object model (Bachelor's thesis).

- Main Page
- Packages
- Classes
- Files

- File List

All Classes Namespaces Files Functions Variables Enumerations Enumerator Properties
Tree.cs
Go to the documentation of this file.
1 using System;
2 using System.Collections;
3 using System.Collections.Generic;
4 using System.Collections.ObjectModel;
5 using System.Linq;
6 using System.Text;
7
8 namespace Mercury.Nucleus.Trees
9 {
10 //=============================================================================
11 // Tree
12 //=============================================================================
13
30 public class Tree<T> : IEquatable<Tree<T>>, IComparable<Tree<T>>,
31 IEnumerable<T>, IEnumerable
32 {
33 //--[ Private fields ]-----------------------------------------------
34
35 private string strhash = null; // used for caching
36 private int? memhash = null; // memoized hash
37 private string memstr = null; // memoized ToString
38
39 internal string CacheKey
40 { get { return strhash ?? (strhash = memhash.ToString()); } }
41
42 //--[ Constructors ]-------------------------------------------------
43
49 public Tree(T value)
50 : this(value, new List<Tree<T>>())
51 { }
52
56 public Tree(Tree<T> other, IEnumerable<Tree<T>> children)
57 : this(other.Value, other.Children.Concat(children))
58 { }
59
66 public Tree(T value, IEnumerable<Tree<T>> children)
67 {
68 Value = value;
69 Depth = 0;
70 LeavesCount = 0;
71 NodesCount = 1;
72
73 List<Tree<T>> cld = new List<Tree<T>>();
74 foreach (var tree in children)
75 {
76 cld.Add(tree);
77 Depth = Math.Max(Depth, tree.Depth + 1);
78 LeavesCount += tree.IsLeaf ? 1 : tree.LeavesCount;
79 NodesCount += tree.NodesCount;
80 }
81
82 Children = cld;
83 }
84
85 //--[ Properties ]---------------------------------------------------
86
88 public int Depth { get; private set; }
89
91 public int LeavesCount { get; private set; }
92
94 public int NodesCount { get; private set; }
95
97 public T Value { get; private set; }
98
100 public bool IsLeaf { get { return Children.Count == 0; } }
101
104 public IReadOnlyList<Tree<T>> Children { get; private set; }
105
107 public DFSTreeEnumerator<T> DepthFirstEnumerator
108 { get { return new DFSTreeEnumerator<T>(this); } }
109
111 public BFSTreeEnumerator<T> BreadthFirstEnumerator
112 { get { return new BFSTreeEnumerator<T>(this); } }
113
114 //--[ Indexer ]------------------------------------------------------
115
119 public Tree<T> this[int ix] { get { return Children[ix]; } }
120
121 //--[ Overriden methods ]--------------------------------------------
122
123 #region [ Object ]
124
125 public override bool Equals(object obj)
126 {
127 Tree<T> tree = obj as Tree<T>;
128 return tree == null ? false : Equals(tree);
129 }
130
131 public override int GetHashCode()
132 {
133 if (memhash.HasValue) return memhash.Value;
134
135 int count = Children.Count;
136 memhash = Value.GetHashCode() * (13 * count + 7);
137
138 int px = 7;
139 for (int ix = 0; ix < count; ++ix)
140 {
141 memhash += (px * (ix + 1)) * Children[ix].GetHashCode();
142 px *= 7;
143 }
144
145 return memhash.Value;
146 }
147
148 public string ToString(int maxdepth)
149 {
150 if ((maxdepth >= Depth) && (memstr != null)) return memstr;
151 if (IsLeaf) return Value.ToString();
152 if (maxdepth == 0) return Value.ToString() + "{" + LeavesCount.ToString() + "}";
153
154 StringBuilder sb = new StringBuilder();
155 sb.Append('[').Append(Value.ToString());
156
157 for (int ix = 0; ix < Children.Count; ++ix)
158 {
159 var c = (maxdepth < 0) || (maxdepth >= Children[ix].Depth);
160 sb.Append(' ').Append(Children[ix].ToString(c ? -1 : maxdepth - 1));
161 }
162
163 sb.Append(']');
164
165 if (maxdepth >= Depth) return (memstr = sb.ToString());
166 return sb.ToString();
167 }
168
169 public override string ToString()
170 { return memstr ?? (memstr = this.ToString(-1)); }
171
172 #endregion
173
174 //--[ Interface implementation ]-------------------------------------
175
176 #region [ IEquatable ]
177
178 public bool Equals(Tree<T> other)
179 {
180 if (other == null) return false;
181 if (object.ReferenceEquals(this, other)) return true; // performance hack
182 if (this.GetHashCode() != other.GetHashCode()) return false;
183
184 bool temp = Value.Equals(other.Value)
185 && Children.Count == other.Children.Count;
186
187 for (int ix = 0; temp && (ix < Children.Count); ++ix)
188 temp = Children[ix].Equals(other.Children[ix]);
189
190 return temp;
191 }
192
193 #endregion
194
195 #region [ IComparable ]
196
197 public int CompareTo(Tree<T> other)
198 {
199 int temp = Comparer<T>.Default.Compare(Value, other.Value);
200
201 if (temp == 0) temp = Children.Count - other.Children.Count;
202
203 for (int ix = 0; (temp == 0) && (ix < Children.Count); ++ix)
204 temp = Children[ix].CompareTo(other.Children[ix]);
205
206 return temp;
207 }
208
209 #endregion
210
211 #region [ IEnumerable ]
212
213 public IEnumerator<T> GetEnumerator() { return DepthFirstEnumerator; }
214
215 IEnumerator IEnumerable.GetEnumerator() { return DepthFirstEnumerator; }
216
217 #endregion
218
219 }
220 }
Mercury.Nucleus.Trees.Tree< T >.GetEnumerator
IEnumerator< T > GetEnumerator()
Definition: Tree.cs:213
Mercury.Nucleus.Trees.Tree< T >.Tree
Tree(Tree< T > other, IEnumerable< Tree< T >> children)
"Copy" constructor
Definition: Tree.cs:56
Mercury.Nucleus.Trees.BFSTreeEnumerator< T >
Breadth-First Search tree enumerator
Definition: TreeEnumerators.cs:90
Mercury.Nucleus.Trees.Tree< T >.Equals
override bool Equals(object obj)
Definition: Tree.cs:125
Mercury.Nucleus.Trees.DFSTreeEnumerator< T >
Depth-First Search tree enumerator
Definition: TreeEnumerators.cs:13
Mercury.Nucleus.Trees.Tree< T >.Tree
Tree(T value)
Initializes a new instance of the Tree{T} class with no child nodes (Leaf)
Definition: Tree.cs:49
Mercury.Nucleus.Trees.Tree< T >.Equals
bool Equals(Tree< T > other)
Definition: Tree.cs:178
Mercury.Nucleus.Trees.Tree< T >.ToString
override string ToString()
Definition: Tree.cs:169
Mercury.Nucleus.Trees.Tree< T >.CompareTo
int CompareTo(Tree< T > other)
Definition: Tree.cs:197
Mercury.Nucleus.Trees.Tree< T >
A non-balanced tree implementation that can be referenced from many other trees. Because of that...
Definition: Tree.cs:30
Mercury.Nucleus.Trees.Tree< T >.ToString
string ToString(int maxdepth)
Definition: Tree.cs:148
Mercury.Nucleus.Trees.Tree< T >.GetHashCode
override int GetHashCode()
Definition: Tree.cs:131
Mercury.Nucleus.Trees.Tree< T >.Children
IReadOnlyList< Tree< T > > Children
Tree's children
Definition: Tree.cs:104
Mercury.Nucleus.Trees.Tree< T >.Tree
Tree(T value, IEnumerable< Tree< T >> children)
Initializes a new instance of the Tree{T} class with the given parent and children ...
Definition: Tree.cs:66