| | | 1 | | namespace Towel.DataStructures; |
| | | 2 | | |
| | | 3 | | /// <summary>A generic tree data structure.</summary> |
| | | 4 | | /// <typeparam name="T">The generic type stored in this data structure.</typeparam> |
| | | 5 | | public interface ITree<T> : IDataStructure<T>, |
| | | 6 | | DataStructure.ICountable, |
| | | 7 | | DataStructure.IRemovable<T> |
| | | 8 | | { |
| | | 9 | | #region Properties |
| | | 10 | | |
| | | 11 | | /// <summary>The head of the tree.</summary> |
| | | 12 | | T Top { get; } |
| | | 13 | | |
| | | 14 | | #endregion |
| | | 15 | | |
| | | 16 | | #region Methods |
| | | 17 | | |
| | | 18 | | /// <summary>Determines if a node is the child of another node.</summary> |
| | | 19 | | /// <param name="node">The child to check the parent of.</param> |
| | | 20 | | /// <param name="parent">The parent to check the child of.</param> |
| | | 21 | | /// <returns>True if the node is a child of the parent; False if not.</returns> |
| | | 22 | | bool IsChildOf(T node, T parent); |
| | | 23 | | |
| | | 24 | | /// <summary>Stepper function for the children of a given node.</summary> |
| | | 25 | | /// <param name="parent">The node to step through the children of.</param> |
| | | 26 | | /// <param name="step">The step function.</param> |
| | | 27 | | void Children(T parent, Action<T> step); |
| | | 28 | | |
| | | 29 | | /// <summary>Gets the parent of a given node.</summary> |
| | | 30 | | /// <param name="child">The child to get the parent of.</param> |
| | | 31 | | /// <returns>The parent of the given child.</returns> |
| | | 32 | | T Parent(T child); |
| | | 33 | | |
| | | 34 | | /// <summary>Adds a node to the tree.</summary> |
| | | 35 | | /// <param name="addition">The node to be added.</param> |
| | | 36 | | /// <param name="parent">The parent of the node to be added.</param> |
| | | 37 | | /// <returns> |
| | | 38 | | /// (<see cref="bool"/> Success, <see cref="Exception"/>? Exception)<br/> |
| | | 39 | | /// - <see cref="bool"/> Success: true if the value was added to the tree or false if not<br/> |
| | | 40 | | /// - <see cref="Exception"/>? Exception: the exception that occured if the add was not successful |
| | | 41 | | /// </returns> |
| | | 42 | | (bool Success, Exception? Exception) TryAdd(T addition, T parent); |
| | | 43 | | |
| | | 44 | | #endregion |
| | | 45 | | } |
| | | 46 | | |
| | | 47 | | /// <summary>Static members for the <see cref="TreeMap{T, TEquate, THash}"/> type.</summary> |
| | | 48 | | public static class TreeMap |
| | | 49 | | { |
| | | 50 | | #region Extension Methods |
| | | 51 | | |
| | | 52 | | /// <summary>Constructs a new <see cref="TreeMap{T, TEquate, THash}"/>.</summary> |
| | | 53 | | /// <typeparam name="T">The type of values stored in this data structure.</typeparam> |
| | | 54 | | /// <param name="top">The top of the tree.</param> |
| | | 55 | | /// <param name="equate">The function for comparing <typeparamref name="T"/> values for equality.</param> |
| | | 56 | | /// <param name="hash">The function for hashing <typeparamref name="T"/> values.</param> |
| | | 57 | | /// <returns>The new constructed <see cref="TreeMap{T, TEquate, THash}"/>.</returns> |
| | | 58 | | public static TreeMap<T, SFunc<T, T, bool>, SFunc<T, int>> New<T>( |
| | | 59 | | T top, |
| | | 60 | | Func<T, T, bool>? equate = null, |
| | | 61 | | Func<T, int>? hash = null) => |
| | 0 | 62 | | new(top, equate ?? Equate, hash ?? Hash); |
| | | 63 | | |
| | | 64 | | #endregion |
| | | 65 | | } |
| | | 66 | | |
| | | 67 | | /// <summary>A generic tree data structure using a dictionary to store node data.</summary> |
| | | 68 | | /// <typeparam name="T">The generic type stored in this data structure.</typeparam> |
| | | 69 | | /// <typeparam name="TEquate">The type of function for quality checking <typeparamref name="T"/> values.</typeparam> |
| | | 70 | | /// <typeparam name="THash">The type of function for hashing <typeparamref name="T"/> values.</typeparam> |
| | | 71 | | public class TreeMap<T, TEquate, THash> : ITree<T>, |
| | | 72 | | ICloneable<TreeMap<T, TEquate, THash>>, |
| | | 73 | | DataStructure.IHashing<T, THash>, |
| | | 74 | | DataStructure.IEquating<T, TEquate> |
| | | 75 | | where TEquate : struct, IFunc<T, T, bool> |
| | | 76 | | where THash : struct, IFunc<T, int> |
| | | 77 | | { |
| | | 78 | | internal T _top; |
| | | 79 | | internal MapHashLinked<Node, T, TEquate, THash> _map; |
| | | 80 | | |
| | | 81 | | #region Nested Types |
| | | 82 | | |
| | | 83 | | internal class Node |
| | | 84 | | { |
| | | 85 | | internal T? Parent; |
| | | 86 | | internal SetHashLinked<T, TEquate, THash> Children; |
| | | 87 | | |
| | | 88 | | public Node(T? parent, SetHashLinked<T, TEquate, THash> children) |
| | | 89 | | { |
| | | 90 | | Parent = parent; |
| | | 91 | | Children = children; |
| | | 92 | | } |
| | | 93 | | } |
| | | 94 | | |
| | | 95 | | #endregion |
| | | 96 | | |
| | | 97 | | #region Constructors |
| | | 98 | | |
| | | 99 | | /// <summary>Constructs a new tree.</summary> |
| | | 100 | | /// <param name="top">The top of the tree.</param> |
| | | 101 | | /// <param name="equate">The function for quality checking <typeparamref name="T"/> values.</param> |
| | | 102 | | /// <param name="hash">The function for hashing <typeparamref name="T"/> values.</param> |
| | | 103 | | public TreeMap(T top, TEquate equate = default, THash hash = default) |
| | | 104 | | { |
| | | 105 | | _top = top; |
| | | 106 | | _map = new(equate, hash) |
| | | 107 | | { |
| | | 108 | | { _top, new Node(default, new(equate, hash)) } |
| | | 109 | | }; |
| | | 110 | | } |
| | | 111 | | |
| | | 112 | | /// <summary>This constructor is for cloning purposes.</summary> |
| | | 113 | | /// <param name="tree">The tree to clone.</param> |
| | | 114 | | internal TreeMap(TreeMap<T, TEquate, THash> tree) |
| | | 115 | | { |
| | | 116 | | _top = tree._top; |
| | | 117 | | _map = tree._map.Clone(); |
| | | 118 | | } |
| | | 119 | | |
| | | 120 | | #endregion |
| | | 121 | | |
| | | 122 | | #region Properties |
| | | 123 | | |
| | | 124 | | /// <inheritdoc/> |
| | | 125 | | public T Top => _top; |
| | | 126 | | |
| | | 127 | | /// <inheritdoc/> |
| | | 128 | | public THash Hash => _map.Hash; |
| | | 129 | | |
| | | 130 | | /// <inheritdoc/> |
| | | 131 | | public TEquate Equate => _map.Equate; |
| | | 132 | | |
| | | 133 | | /// <inheritdoc/> |
| | | 134 | | public int Count => _map.Count + 1; |
| | | 135 | | |
| | | 136 | | #endregion |
| | | 137 | | |
| | | 138 | | #region Methods |
| | | 139 | | |
| | | 140 | | /// <inheritdoc/> |
| | | 141 | | public bool IsChildOf(T node, T parent) |
| | | 142 | | { |
| | | 143 | | if (!_map.Contains(node)) |
| | | 144 | | { |
| | | 145 | | throw new ArgumentException(paramName: nameof(node), message: "Check for a parent-child relationship of non-existi |
| | | 146 | | } |
| | | 147 | | var (success, exception, value) = _map.TryGet(parent); |
| | | 148 | | if (!success) |
| | | 149 | | { |
| | | 150 | | throw new ArgumentException(paramName: nameof(parent), message: "Check for a parent-child relationship of non-exis |
| | | 151 | | } |
| | | 152 | | return value!.Children.Contains(node); |
| | | 153 | | } |
| | | 154 | | |
| | | 155 | | /// <inheritdoc/> |
| | | 156 | | public T Parent(T child) |
| | | 157 | | { |
| | | 158 | | if (Equate.Invoke(child, _top)) |
| | | 159 | | { |
| | | 160 | | throw new InvalidOperationException("Attempting to get the parent of the top of the tree."); |
| | | 161 | | } |
| | | 162 | | var (success, exception, value) = _map.TryGet(child); |
| | | 163 | | if (!success) |
| | | 164 | | { |
| | | 165 | | throw new InvalidOperationException("Attempting to get the parent of a non-existing node.", innerException: except |
| | | 166 | | } |
| | | 167 | | return value!.Parent!; |
| | | 168 | | } |
| | | 169 | | |
| | | 170 | | /// <inheritdoc/> |
| | | 171 | | public void Children(T parent, Action<T> step) |
| | | 172 | | { |
| | | 173 | | var (success, exception, value) = _map.TryGet(parent); |
| | | 174 | | if (!success) |
| | | 175 | | { |
| | | 176 | | throw new ArgumentException(paramName: nameof(parent), message: "Attepting to step through the children of a none- |
| | | 177 | | } |
| | | 178 | | value!.Children.Stepper(step); |
| | | 179 | | } |
| | | 180 | | |
| | | 181 | | /// <inheritdoc/> |
| | | 182 | | public (bool Success, Exception? Exception) TryAdd(T node, T parent) |
| | | 183 | | { |
| | | 184 | | if (_map.Contains(node)) |
| | | 185 | | { |
| | | 186 | | return (false, new ArgumentException(paramName: nameof(node), message: "Adding an already-existing node to a tree. |
| | | 187 | | } |
| | | 188 | | var (success, exception, value) = _map.TryGet(parent); |
| | | 189 | | if (!success) |
| | | 190 | | { |
| | | 191 | | return (false, new ArgumentException(paramName: nameof(parent), message: "Adding a node to a non-existant parent i |
| | | 192 | | } |
| | | 193 | | _map.Add(node, new Node(parent, new(Equate, Hash))); |
| | | 194 | | value!.Children.Add(node); |
| | | 195 | | return (true, null); |
| | | 196 | | } |
| | | 197 | | |
| | | 198 | | /// <inheritdoc/> |
| | | 199 | | public (bool Success, Exception? Exception) TryRemove(T node) |
| | | 200 | | { |
| | | 201 | | if (Equate.Invoke(node, _top)) |
| | | 202 | | { |
| | | 203 | | return (false, new ArgumentException(paramName: nameof(node), message: "Attempting to remove the top of the tree." |
| | | 204 | | } |
| | | 205 | | |
| | | 206 | | var (success, exception, value) = _map.TryGet(node); |
| | | 207 | | if (!success) |
| | | 208 | | { |
| | | 209 | | return (false, new InvalidOperationException("Attempting to remove a non-existing node", exception)); |
| | | 210 | | } |
| | | 211 | | _map[value!.Parent!].Children.Remove(node); |
| | | 212 | | RemoveRecursive(node); |
| | | 213 | | return (true, null); |
| | | 214 | | } |
| | | 215 | | |
| | | 216 | | /// <inheritdoc/> |
| | | 217 | | public StepStatus StepperBreak<TStep>(TStep step = default) |
| | | 218 | | where TStep : struct, IFunc<T, StepStatus> => |
| | | 219 | | _map.KeysBreak(step); |
| | | 220 | | |
| | | 221 | | System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator(); |
| | | 222 | | |
| | | 223 | | /// <inheritdoc/> |
| | | 224 | | public System.Collections.Generic.IEnumerator<T> GetEnumerator() |
| | | 225 | | { |
| | | 226 | | #warning TODO: optimize |
| | | 227 | | return ((System.Collections.Generic.IEnumerable<T>)ToArray()).GetEnumerator(); |
| | | 228 | | } |
| | | 229 | | |
| | | 230 | | /// <inheritdoc/> |
| | | 231 | | public TreeMap<T, TEquate, THash> Clone() => new(this); |
| | | 232 | | |
| | | 233 | | internal void RemoveRecursive(T current) |
| | | 234 | | { |
| | | 235 | | _map[current].Children.Stepper(child => RemoveRecursive(child)); |
| | | 236 | | _map.Remove(current); |
| | | 237 | | } |
| | | 238 | | |
| | | 239 | | /// <inheritdoc/> |
| | | 240 | | public T[] ToArray() |
| | | 241 | | { |
| | | 242 | | #warning TODO: optimize |
| | | 243 | | T[] array = new T[Count]; |
| | | 244 | | int i = 0; |
| | | 245 | | this.Stepper(x => array[i++] = x); |
| | | 246 | | return array; |
| | | 247 | | } |
| | | 248 | | |
| | | 249 | | #endregion |
| | | 250 | | } |