| | | 1 | | namespace Towel.DataStructures; |
| | | 2 | | |
| | | 3 | | /// <summary>Static helpers for <see cref="BTreeLinked{T, TCompare}"/>.</summary> |
| | | 4 | | public static class BTreeLinked |
| | | 5 | | { |
| | | 6 | | #region Extension Methods |
| | | 7 | | |
| | | 8 | | /// <inheritdoc cref="BTreeLinked{T, TCompare}.BTreeLinked(byte, TCompare)" /> |
| | | 9 | | /// <inheritdoc cref="BTreeLinked{T, TCompare}" /> |
| | | 10 | | /// <returns>The new constructed <see cref="BTreeLinked{T, TCompare}"/>.</returns> |
| | | 11 | | public static BTreeLinked<T, SFunc<T, T, CompareResult>> New<T>( |
| | | 12 | | byte maxDegree, |
| | | 13 | | Func<T, T, CompareResult>? compare = null) => |
| | 14 | 14 | | new(maxDegree, compare ?? Compare); |
| | | 15 | | |
| | | 16 | | #endregion |
| | | 17 | | } |
| | | 18 | | |
| | | 19 | | /// <summary>B-Tree Data structure.</summary> |
| | | 20 | | /// <typeparam name="T">The type to store</typeparam> |
| | | 21 | | /// <typeparam name="TCompare">The type that is comparing <typeparamref name="T"/> values.</typeparam> |
| | | 22 | | public class BTreeLinked<T, TCompare> : IDataStructure<T>, |
| | | 23 | | DataStructure.IAddable<T>, |
| | | 24 | | DataStructure.IRemovable<T>, |
| | | 25 | | DataStructure.ICountable, |
| | | 26 | | DataStructure.IClearable, |
| | | 27 | | DataStructure.IAuditable<T>, |
| | | 28 | | DataStructure.IComparing<T, TCompare>, |
| | | 29 | | ICloneable<BTreeLinked<T, TCompare>> |
| | | 30 | | where TCompare : struct, IFunc<T, T, CompareResult> |
| | | 31 | | { |
| | | 32 | | internal Node _root; |
| | | 33 | | internal int _count; |
| | | 34 | | internal TCompare _compare; |
| | | 35 | | internal byte _maxDegree; |
| | | 36 | | |
| | | 37 | | #region Nested Types |
| | | 38 | | |
| | | 39 | | internal class Node |
| | | 40 | | { |
| | | 41 | | internal T[] _values; |
| | | 42 | | internal Node?[] _children; |
| | | 43 | | internal Node? _parent; |
| | | 44 | | internal byte _parentIndex; |
| | | 45 | | internal byte _count; |
| | | 46 | | |
| | | 47 | | public Node(byte maxdegree) |
| | | 48 | | { |
| | | 49 | | _values = new T[maxdegree - 1]; |
| | | 50 | | _children = new Node?[maxdegree]; |
| | | 51 | | } |
| | | 52 | | |
| | | 53 | | public bool IsLeaf => _children[0] is null; |
| | | 54 | | |
| | | 55 | | public bool IsFull => _count + 1 == _children.Length; |
| | | 56 | | } |
| | | 57 | | |
| | | 58 | | #endregion |
| | | 59 | | |
| | | 60 | | #region Constructors |
| | | 61 | | |
| | | 62 | | /// <summary>Creates a B-Tree having nodes of given maximum size. Maximum size must be even</summary> |
| | | 63 | | /// <param name="maxdegree">The maximum degree/children a node can have. Must be even</param> |
| | | 64 | | /// <param name="compare">The function for comparing <typeparamref name="T"/> values.</param> |
| | | 65 | | public BTreeLinked(byte maxdegree, TCompare compare = default) |
| | | 66 | | { |
| | | 67 | | if (maxdegree < 4) throw new ArgumentException("Maximum degree should be at least 4", nameof(maxdegree)); |
| | | 68 | | if (maxdegree % 2 is not 0) throw new ArgumentException("Maximum degree should be an even number", nameof(maxdegree) |
| | | 69 | | _root = new(maxdegree); |
| | | 70 | | _count = 0; |
| | | 71 | | _maxDegree = maxdegree; |
| | | 72 | | _compare = compare; |
| | | 73 | | } |
| | | 74 | | |
| | | 75 | | #endregion |
| | | 76 | | |
| | | 77 | | #region Properties |
| | | 78 | | |
| | | 79 | | /// <inheritdoc /> |
| | | 80 | | public int Count => _count; |
| | | 81 | | |
| | | 82 | | /// <inheritdoc /> |
| | | 83 | | public TCompare Compare => _compare; |
| | | 84 | | |
| | | 85 | | /// <summary>The fixed size of a node within this tree</summary> |
| | | 86 | | public byte MaxDegree => _maxDegree; |
| | | 87 | | |
| | | 88 | | #endregion |
| | | 89 | | |
| | | 90 | | #region Methods |
| | | 91 | | |
| | | 92 | | /// <inheritdoc /> |
| | | 93 | | public void Clear() |
| | | 94 | | { |
| | | 95 | | _count = 0; |
| | | 96 | | _root._count = 0; |
| | | 97 | | for (int i = 0; i < MaxDegree; i++) |
| | | 98 | | { |
| | | 99 | | _root._children[i] = null; |
| | | 100 | | } |
| | | 101 | | } |
| | | 102 | | |
| | | 103 | | /// <summary> |
| | | 104 | | /// Searches for an value in the tree and provides the |
| | | 105 | | /// node it is contained in and its index in the array (as 'out' variables) |
| | | 106 | | /// if it exists. Otherwise provides the leaf node where the value shold be inserted |
| | | 107 | | /// </summary> |
| | | 108 | | /// <param name="value">The value to search</param> |
| | | 109 | | /// <param name="node">The node found</param> |
| | | 110 | | /// <param name="index">The index at which it is found</param> |
| | | 111 | | /// <returns>Returns true if value exists in the tree, otherwise false</returns> |
| | | 112 | | internal bool Search(T value, out Node node, out int index) |
| | | 113 | | { |
| | | 114 | | index = -1; |
| | | 115 | | Node? next = _root; |
| | | 116 | | do |
| | | 117 | | { |
| | | 118 | | node = next; |
| | | 119 | | next = node._children[node._count]; |
| | | 120 | | for (int i = 0; i < node._count; i++) |
| | | 121 | | { |
| | | 122 | | CompareResult c = Compare.Invoke(node._values[i], value); |
| | | 123 | | if (c is Equal) |
| | | 124 | | { |
| | | 125 | | index = i; |
| | | 126 | | return true; |
| | | 127 | | } |
| | | 128 | | else if (c is Greater) |
| | | 129 | | { |
| | | 130 | | next = node._children[i]; |
| | | 131 | | break; |
| | | 132 | | } |
| | | 133 | | } |
| | | 134 | | } while (next is not null); |
| | | 135 | | return false; |
| | | 136 | | } |
| | | 137 | | |
| | | 138 | | /// <inheritdoc /> |
| | | 139 | | public bool Contains(T value) |
| | | 140 | | { |
| | | 141 | | return Search(value, out _, out _); |
| | | 142 | | } |
| | | 143 | | |
| | | 144 | | /// <summary> |
| | | 145 | | /// Finds the best index at which the insertion can be done and |
| | | 146 | | /// inserts the value at the given index, displacing the values as necessary <br/> <br/> |
| | | 147 | | /// Before using this method, ensure that the node is <br/> |
| | | 148 | | /// 1. A leaf node <br/> |
| | | 149 | | /// 2. Can support adding a value in it, i.e Count is at most MaxDegree-1 after insertion |
| | | 150 | | /// </summary> |
| | | 151 | | /// <param name="value">value to add</param> |
| | | 152 | | /// <param name="node">The node in which the value is to be added</param> |
| | | 153 | | /// <returns>returns true if addition was successful. If a duplicate is found, addition fails and the method returns f |
| | | 154 | | internal (bool Success, Exception? Exception) TryAdd(T value, Node node) |
| | | 155 | | { |
| | | 156 | | int index = 0; |
| | | 157 | | if (node._count > 0) |
| | | 158 | | { |
| | | 159 | | for (; index < node._count; index++) |
| | | 160 | | { |
| | | 161 | | CompareResult c = Compare.Invoke(node._values[index], value); |
| | | 162 | | if (c is Equal) |
| | | 163 | | { |
| | | 164 | | return (false, new ArgumentException($"Adding to add a duplicate value to an {nameof(BTreeLinked<T, TCompare>) |
| | | 165 | | } |
| | | 166 | | else if (c is Greater) |
| | | 167 | | { |
| | | 168 | | break; |
| | | 169 | | } |
| | | 170 | | } |
| | | 171 | | for (int i = node._count - 1; i >= index; i--) |
| | | 172 | | { |
| | | 173 | | node._values[i + 1] = node._values[i]; |
| | | 174 | | } |
| | | 175 | | } |
| | | 176 | | node._values[index] = value; |
| | | 177 | | node._count++; |
| | | 178 | | _count++; |
| | | 179 | | return (true, default); |
| | | 180 | | } |
| | | 181 | | |
| | | 182 | | /// <summary> |
| | | 183 | | /// Splits the full node into a node having two child nodes<br/><br/> |
| | | 184 | | /// Before calling this method, ensure that <br/> |
| | | 185 | | /// 1. the node is full <br/> |
| | | 186 | | /// 2. the parent node is Not full (Not applicable for the Root node) |
| | | 187 | | /// </summary> |
| | | 188 | | /// <param name="fullNode">The node to split</param> |
| | | 189 | | internal void Split(Node fullNode) |
| | | 190 | | { |
| | | 191 | | Node right = new(MaxDegree); |
| | | 192 | | Node? parent = fullNode._parent, x; |
| | | 193 | | int l = MaxDegree - 1, MedianIndex = l >> 1; |
| | | 194 | | int i; |
| | | 195 | | int j; |
| | | 196 | | for (i = MedianIndex + 1, j = 0; i < l; i++, j++) |
| | | 197 | | { |
| | | 198 | | right._values[j] = fullNode._values[i]; |
| | | 199 | | fullNode._values[i] = default!; |
| | | 200 | | } |
| | | 201 | | right._count = (byte)j; |
| | | 202 | | if (!fullNode.IsLeaf) |
| | | 203 | | { |
| | | 204 | | for (i = MedianIndex + 1, j = 0; i <= l; i++, j++) |
| | | 205 | | { |
| | | 206 | | right._children[j] = x = fullNode._children[i]; |
| | | 207 | | if (x is not null) |
| | | 208 | | { |
| | | 209 | | x._parent = right; |
| | | 210 | | x._parentIndex = (byte)j; |
| | | 211 | | } |
| | | 212 | | fullNode._children[i] = null; |
| | | 213 | | } |
| | | 214 | | } |
| | | 215 | | fullNode._count = (byte)MedianIndex; |
| | | 216 | | if (parent is null) // 'fullnode' is Root |
| | | 217 | | { |
| | | 218 | | _root = new(MaxDegree); |
| | | 219 | | _root._values[0] = fullNode._values[MedianIndex]; |
| | | 220 | | fullNode._values[MedianIndex] = default!; |
| | | 221 | | _root._count = 1; |
| | | 222 | | _root._children[0] = fullNode; |
| | | 223 | | fullNode._parentIndex = 0; |
| | | 224 | | _root._children[1] = right; |
| | | 225 | | right._parentIndex = 1; |
| | | 226 | | fullNode._parent = right._parent = _root; |
| | | 227 | | } |
| | | 228 | | else |
| | | 229 | | { |
| | | 230 | | for (i = parent._count + 1, j = i--; i > fullNode._parentIndex; j--, i--) |
| | | 231 | | { |
| | | 232 | | parent._children[j] = x = parent._children[i]; |
| | | 233 | | if (x is not null) |
| | | 234 | | { |
| | | 235 | | x._parentIndex = (byte)j; |
| | | 236 | | } |
| | | 237 | | } |
| | | 238 | | for (i = parent._count, j = i--; i >= fullNode._parentIndex; j--, i--) |
| | | 239 | | { |
| | | 240 | | parent._values[j] = parent._values[i]; |
| | | 241 | | } |
| | | 242 | | parent._values[j] = fullNode._values[MedianIndex]; |
| | | 243 | | fullNode._values[MedianIndex] = default!; |
| | | 244 | | parent._children[j] = fullNode; |
| | | 245 | | fullNode._parentIndex = (byte)j; |
| | | 246 | | parent._children[j + 1] = right; |
| | | 247 | | right._parentIndex = (byte)(j + 1); |
| | | 248 | | right._parent = parent; |
| | | 249 | | parent._count++; |
| | | 250 | | } |
| | | 251 | | } |
| | | 252 | | |
| | | 253 | | /// <inheritdoc /> |
| | | 254 | | public (bool Success, Exception? Exception) TryAdd(T value) |
| | | 255 | | { |
| | | 256 | | if (_root.IsFull) |
| | | 257 | | { |
| | | 258 | | Split(_root); |
| | | 259 | | } |
| | | 260 | | Node node = _root; |
| | | 261 | | Node? child; |
| | | 262 | | while (!node.IsLeaf) |
| | | 263 | | { |
| | | 264 | | int i = 0; |
| | | 265 | | CompareResult c; |
| | | 266 | | while (i < node._count && (c = Compare.Invoke(node._values[i], value)) is not Greater) |
| | | 267 | | { |
| | | 268 | | if (c is Equal) |
| | | 269 | | { |
| | | 270 | | return (false, new ArgumentException($"Adding to add a duplicate value to an {nameof(BTreeLinked<T, TCompare>) |
| | | 271 | | } |
| | | 272 | | i++; |
| | | 273 | | } |
| | | 274 | | child = node._children[i]; |
| | | 275 | | if (child is not null && child.IsFull) |
| | | 276 | | { |
| | | 277 | | Split(child); |
| | | 278 | | c = Compare.Invoke(node._values[i], value); |
| | | 279 | | switch (c) |
| | | 280 | | { |
| | | 281 | | case Greater: child = node._children[i]; break; |
| | | 282 | | case Less: child = node._children[i + 1]; break; |
| | | 283 | | case Equal: return (false, new ArgumentException($"Adding to add a duplicate value to an {nameof(BTreeLinked<T |
| | | 284 | | } |
| | | 285 | | } |
| | | 286 | | if (child is null) |
| | | 287 | | { |
| | | 288 | | return (false, new CorruptedDataStructureException("Expected a non-null internal node, but found a null node")); |
| | | 289 | | } |
| | | 290 | | node = child; |
| | | 291 | | } |
| | | 292 | | return TryAdd(value, node); |
| | | 293 | | } |
| | | 294 | | |
| | | 295 | | /// <inheritdoc /> |
| | | 296 | | public (bool Success, Exception? Exception) TryRemove(T value) |
| | | 297 | | { |
| | | 298 | | if (_count is 0) |
| | | 299 | | { |
| | | 300 | | return (false, new ArgumentException($"Attempting to remove a non-existing entry: {value}.", nameof(value))); |
| | | 301 | | } |
| | | 302 | | Node? node = _root; |
| | | 303 | | Node? child; |
| | | 304 | | int t = MaxDegree >> 1; |
| | | 305 | | // All nodes (except root) must contain at least this many values |
| | | 306 | | // [value of (t) in Cormen's "Introduction to Algorithms"] |
| | | 307 | | do |
| | | 308 | | { |
| | | 309 | | int i = 0; |
| | | 310 | | CompareResult c; |
| | | 311 | | while (i < node._count && (c = Compare.Invoke(node._values[i], value)) is not Greater) |
| | | 312 | | { |
| | | 313 | | if (c is Equal) |
| | | 314 | | { |
| | | 315 | | if (node.IsLeaf) // CASE 1 |
| | | 316 | | { |
| | | 317 | | for (int j = i + 1; j < node._count; j++) |
| | | 318 | | { |
| | | 319 | | node._values[j - 1] = node._values[j]; |
| | | 320 | | } |
| | | 321 | | node._values[--node._count] = default!; |
| | | 322 | | node = null; |
| | | 323 | | } |
| | | 324 | | else |
| | | 325 | | { |
| | | 326 | | Node? lc = node._children[i]; |
| | | 327 | | Node? rc = node._children[i + 1]; |
| | | 328 | | if (lc is null || rc is null) |
| | | 329 | | { |
| | | 330 | | return (false, new CorruptedDataStructureException("Found null children of an internal node!")); |
| | | 331 | | } |
| | | 332 | | if (lc._count >= t) // CASE 2a |
| | | 333 | | { |
| | | 334 | | do |
| | | 335 | | { |
| | | 336 | | child = lc; |
| | | 337 | | lc = lc._children[lc._count]; |
| | | 338 | | } while (lc is not null); |
| | | 339 | | // At this point lc is null, child is the rightmost node of subtree preceeding 'value' |
| | | 340 | | value = node._values[i] = child._values[child._count - 1]; |
| | | 341 | | } |
| | | 342 | | else if (rc._count >= t) // Case 2b |
| | | 343 | | { |
| | | 344 | | do |
| | | 345 | | { |
| | | 346 | | child = rc; |
| | | 347 | | rc = rc._children[0]; |
| | | 348 | | } while (rc is not null); |
| | | 349 | | // At this point rc is null, child is the leftmost node of subtree following 'value' |
| | | 350 | | value = node._values[i++] = child._values[0]; |
| | | 351 | | } |
| | | 352 | | else // Case 2c |
| | | 353 | | { |
| | | 354 | | int p; |
| | | 355 | | int q; |
| | | 356 | | int r = lc._count; |
| | | 357 | | lc._values[lc._count++] = node._values[i]; |
| | | 358 | | for (p = i, q = i + 1; q < node._count; p++, q++) |
| | | 359 | | { |
| | | 360 | | node._values[p] = node._values[q]; |
| | | 361 | | } |
| | | 362 | | node._values[p] = default!; |
| | | 363 | | for (p = i + 1, q = p + 1; q <= node._count; p++, q++) |
| | | 364 | | { |
| | | 365 | | child = node._children[p] = node._children[q]; |
| | | 366 | | if (child is not null) |
| | | 367 | | { |
| | | 368 | | child._parentIndex = (byte)p; |
| | | 369 | | } |
| | | 370 | | else |
| | | 371 | | { |
| | | 372 | | return (false, new CorruptedDataStructureException("Found null children of an internal node!")); |
| | | 373 | | } |
| | | 374 | | } |
| | | 375 | | node._children[p] = null; |
| | | 376 | | node._count--; |
| | | 377 | | for (p = lc._count, q = 0; q < rc._count; p++, q++, lc._count++) |
| | | 378 | | { |
| | | 379 | | lc._values[p] = rc._values[q]; |
| | | 380 | | rc._values[q] = default!; |
| | | 381 | | } |
| | | 382 | | for (p = r + 1, q = 0; q <= rc._count; p++, q++) |
| | | 383 | | { |
| | | 384 | | child = lc._children[p] = rc._children[q]; |
| | | 385 | | if (child is not null) |
| | | 386 | | { |
| | | 387 | | child._parentIndex = (byte)p; |
| | | 388 | | child._parent = lc; |
| | | 389 | | } |
| | | 390 | | rc._children[q] = null; |
| | | 391 | | } |
| | | 392 | | rc._parent = null; // delete rc from memory ? |
| | | 393 | | if (node == _root && node._count is 0) |
| | | 394 | | { |
| | | 395 | | _root = lc; |
| | | 396 | | _root._parent = null; |
| | | 397 | | node._values = default!; |
| | | 398 | | node._children = default!; // delete node from memory ? |
| | | 399 | | node = lc; |
| | | 400 | | i = 0; |
| | | 401 | | continue; |
| | | 402 | | } |
| | | 403 | | } |
| | | 404 | | } |
| | | 405 | | break; |
| | | 406 | | } |
| | | 407 | | i++; |
| | | 408 | | } |
| | | 409 | | if (node is null) |
| | | 410 | | { |
| | | 411 | | break; // 'node' would be null after Case 1 |
| | | 412 | | } |
| | | 413 | | else |
| | | 414 | | { |
| | | 415 | | child = node._children[i]; // 'child' will be null only if 'node' is a Leaf node |
| | | 416 | | } |
| | | 417 | | if (child is null) |
| | | 418 | | { |
| | | 419 | | return (false, new ArgumentException($"Attempting to remove a non-existing entry: {value}.", nameof(value))); |
| | | 420 | | } |
| | | 421 | | else if (child._count < t) |
| | | 422 | | { |
| | | 423 | | Node? lc = i > 0 ? node._children[i - 1] : null; |
| | | 424 | | Node? rc = i < node._count ? node._children[i + 1] : null; |
| | | 425 | | int j; |
| | | 426 | | if (lc is not null && lc._count >= t) // Case 3a-Left |
| | | 427 | | { |
| | | 428 | | for (j = child._count; j > 0; j--) |
| | | 429 | | { |
| | | 430 | | child._values[j] = child._values[j - 1]; |
| | | 431 | | } |
| | | 432 | | child._count++; |
| | | 433 | | for (j = child._count; j > 0; j--) |
| | | 434 | | { |
| | | 435 | | rc = child._children[j] = child._children[j - 1]; |
| | | 436 | | if (rc is not null) |
| | | 437 | | { |
| | | 438 | | rc._parentIndex = (byte)j; |
| | | 439 | | } |
| | | 440 | | } |
| | | 441 | | rc = lc._children[lc._count]; |
| | | 442 | | if (rc is not null) |
| | | 443 | | { |
| | | 444 | | child._children[0] = rc; |
| | | 445 | | rc._parent = child; |
| | | 446 | | rc._parentIndex = 0; |
| | | 447 | | } |
| | | 448 | | child._values[0] = node._values[i - 1]; |
| | | 449 | | node._values[i - 1] = lc._values[--lc._count]; |
| | | 450 | | lc._values[lc._count] = default!; |
| | | 451 | | } |
| | | 452 | | else if (rc is not null && rc._count >= t) // Case 3a-Right |
| | | 453 | | { |
| | | 454 | | child._values[child._count++] = node._values[i]; |
| | | 455 | | node._values[i] = rc._values[0]; |
| | | 456 | | lc = rc._children[0]; |
| | | 457 | | if (lc is not null) |
| | | 458 | | { |
| | | 459 | | child._children[child._count] = lc; |
| | | 460 | | lc._parentIndex = child._count; |
| | | 461 | | lc._parent = child; |
| | | 462 | | } |
| | | 463 | | for (j = 1; j < rc._count; j++) |
| | | 464 | | { |
| | | 465 | | rc._values[j - 1] = rc._values[j]; |
| | | 466 | | } |
| | | 467 | | for (j = 1; j <= rc._count; j++) |
| | | 468 | | { |
| | | 469 | | lc = rc._children[j - 1] = rc._children[j]; |
| | | 470 | | if (lc is not null) |
| | | 471 | | { |
| | | 472 | | lc._parentIndex = (byte)(j - 1); |
| | | 473 | | } |
| | | 474 | | } |
| | | 475 | | rc._children[rc._count--] = null; |
| | | 476 | | rc._values[rc._count] = default!; |
| | | 477 | | } |
| | | 478 | | else |
| | | 479 | | { |
| | | 480 | | int k; |
| | | 481 | | if (lc is not null) // Case 3b-Left |
| | | 482 | | { |
| | | 483 | | lc._values[lc._count++] = node._values[i - 1]; |
| | | 484 | | for (j = lc._count, k = 0; k <= child._count; j++, k++) |
| | | 485 | | { |
| | | 486 | | rc = lc._children[j] = child._children[k]; |
| | | 487 | | if (rc is not null) |
| | | 488 | | { |
| | | 489 | | rc._parentIndex = (byte)j; |
| | | 490 | | rc._parent = lc; |
| | | 491 | | } |
| | | 492 | | } |
| | | 493 | | for (k = 0; k < child._count; k++) |
| | | 494 | | { |
| | | 495 | | lc._values[lc._count++] = child._values[k]; |
| | | 496 | | } |
| | | 497 | | child._values = default!; |
| | | 498 | | child._children = default!; |
| | | 499 | | child._parent = null; |
| | | 500 | | child = lc; |
| | | 501 | | } |
| | | 502 | | else if (rc is not null) // Case 3b-Right || PS: can leave it at else {...} but this avoids Null reference war |
| | | 503 | | { |
| | | 504 | | child._values[child._count++] = node._values[i]; |
| | | 505 | | for (j = child._count, k = 0; k <= rc._count; j++, k++) |
| | | 506 | | { |
| | | 507 | | lc = child._children[j] = rc._children[k]; |
| | | 508 | | if (lc is not null) |
| | | 509 | | { |
| | | 510 | | lc._parentIndex = (byte)j; |
| | | 511 | | lc._parent = child; |
| | | 512 | | } |
| | | 513 | | } |
| | | 514 | | for (k = 0; k < rc._count; k++) |
| | | 515 | | { |
| | | 516 | | child._values[child._count++] = rc._values[k]; |
| | | 517 | | } |
| | | 518 | | rc._values = default!; |
| | | 519 | | rc._children = default!; |
| | | 520 | | rc._parent = null; |
| | | 521 | | } |
| | | 522 | | else |
| | | 523 | | { |
| | | 524 | | return (false, new CorruptedDataStructureException("Found null children of an internal node!")); |
| | | 525 | | } |
| | | 526 | | for (k = child._parentIndex + 1; k < node._count; k++) |
| | | 527 | | { |
| | | 528 | | node._values[k - 1] = node._values[k]; |
| | | 529 | | lc = node._children[k] = node._children[k + 1]; |
| | | 530 | | if (lc is not null) |
| | | 531 | | { |
| | | 532 | | lc._parentIndex = (byte)k; |
| | | 533 | | } |
| | | 534 | | } |
| | | 535 | | node._children[node._count--] = null; |
| | | 536 | | node._values[node._count] = default!; |
| | | 537 | | if (node == _root && node._count is 0) |
| | | 538 | | { |
| | | 539 | | node._children = null!; |
| | | 540 | | _root = child; |
| | | 541 | | _root._parent = null; |
| | | 542 | | _root._parentIndex = 0; |
| | | 543 | | } |
| | | 544 | | } |
| | | 545 | | } |
| | | 546 | | node = child; |
| | | 547 | | } while (node is not null); |
| | | 548 | | _count--; |
| | | 549 | | return (true, default); |
| | | 550 | | } |
| | | 551 | | |
| | | 552 | | /// <inheritdoc /> |
| | | 553 | | public T[] ToArray() |
| | | 554 | | { |
| | | 555 | | if (_count is 0) |
| | | 556 | | { |
| | | 557 | | return Array.Empty<T>(); |
| | | 558 | | } |
| | | 559 | | T[] array = new T[_count]; |
| | | 560 | | this.Stepper<T, FillArray<T>>(array); |
| | | 561 | | return array; |
| | | 562 | | } |
| | | 563 | | |
| | | 564 | | internal static Node LeftmostNode(Node node) |
| | | 565 | | { |
| | | 566 | | Node? leftChild = node._children[0]; |
| | | 567 | | while (leftChild is not null) |
| | | 568 | | { |
| | | 569 | | node = leftChild; |
| | | 570 | | leftChild = node._children[0]; |
| | | 571 | | } |
| | | 572 | | return node; |
| | | 573 | | } |
| | | 574 | | |
| | | 575 | | /// <summary>Given a value's index in a node, returns the node and index of the value which is next to the given value |
| | | 576 | | /// <param name="node">The node in which the current value is contained</param> |
| | | 577 | | /// <param name="index">The index of the value within the node</param> |
| | | 578 | | /// <returns>The node and index of the next value</returns> |
| | | 579 | | internal static (Node? Node, int Index) NextNode(Node node, int index) |
| | | 580 | | { |
| | | 581 | | index++; |
| | | 582 | | Node? p = node._children[index]; |
| | | 583 | | if (index >= node._count && p is null) |
| | | 584 | | { |
| | | 585 | | index = node._parentIndex; |
| | | 586 | | p = node._parent; |
| | | 587 | | while (p is not null && index == p._count) |
| | | 588 | | { |
| | | 589 | | node = p; |
| | | 590 | | p = p._parent; |
| | | 591 | | index = node._parentIndex; |
| | | 592 | | } |
| | | 593 | | return (p, index); |
| | | 594 | | } |
| | | 595 | | else if (p is not null) |
| | | 596 | | { |
| | | 597 | | return (LeftmostNode(p), 0); |
| | | 598 | | } |
| | | 599 | | else |
| | | 600 | | { |
| | | 601 | | return (node, index); |
| | | 602 | | } |
| | | 603 | | } |
| | | 604 | | |
| | | 605 | | /// <inheritdoc /> |
| | | 606 | | public System.Collections.Generic.IEnumerator<T> GetEnumerator() |
| | | 607 | | { |
| | | 608 | | if (_count > 0) |
| | | 609 | | { |
| | | 610 | | int index = 0; |
| | | 611 | | Node node; |
| | | 612 | | Node? nextnode = LeftmostNode(_root); |
| | | 613 | | do |
| | | 614 | | { |
| | | 615 | | node = nextnode; |
| | | 616 | | yield return node._values[index]; |
| | | 617 | | (nextnode, index) = NextNode(node, index); |
| | | 618 | | } while (nextnode is not null); |
| | | 619 | | } |
| | | 620 | | yield break; |
| | | 621 | | } |
| | | 622 | | |
| | | 623 | | System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator(); |
| | | 624 | | |
| | | 625 | | /// <inheritdoc /> |
| | | 626 | | public StepStatus StepperBreak<TStep>(TStep step = default) |
| | | 627 | | where TStep : struct, IFunc<T, StepStatus> |
| | | 628 | | { |
| | | 629 | | if (_count is 0) |
| | | 630 | | { |
| | | 631 | | return Continue; |
| | | 632 | | } |
| | | 633 | | return StepperBreak(_root, step); |
| | | 634 | | } |
| | | 635 | | |
| | | 636 | | internal StepStatus StepperBreak<TStep>(Node start, TStep step = default) |
| | | 637 | | where TStep : struct, IFunc<T, StepStatus> |
| | | 638 | | { |
| | | 639 | | int index = 0; |
| | | 640 | | Node? node = LeftmostNode(start); |
| | | 641 | | do |
| | | 642 | | { |
| | | 643 | | if (step.Invoke(node._values[index]) is Break) |
| | | 644 | | { |
| | | 645 | | return Break; |
| | | 646 | | } |
| | | 647 | | (node, index) = NextNode(node!, index); |
| | | 648 | | } while (node is not null); |
| | | 649 | | return Continue; |
| | | 650 | | } |
| | | 651 | | |
| | | 652 | | /// <inheritdoc /> |
| | | 653 | | public BTreeLinked<T, TCompare> Clone() |
| | | 654 | | { |
| | | 655 | | BTreeLinked<T, TCompare> clone = new(_maxDegree, _compare); |
| | | 656 | | StackLinked<(Node original, Node copy)> stack = new(); |
| | | 657 | | stack.Push((_root, clone._root)); |
| | | 658 | | while (stack._count > 0) |
| | | 659 | | { |
| | | 660 | | (Node original, Node copy) = stack.Pop(); |
| | | 661 | | copy._parentIndex = original._parentIndex; |
| | | 662 | | copy._count = original._count; |
| | | 663 | | for (int i = 0; i < original._count; i++) |
| | | 664 | | { |
| | | 665 | | copy._values[i] = original._values[i]; |
| | | 666 | | } |
| | | 667 | | if (!original.IsLeaf) |
| | | 668 | | { |
| | | 669 | | for (int i = 0; i <= original._count; i++) |
| | | 670 | | { |
| | | 671 | | Node c = copy._children[i] = new(MaxDegree); |
| | | 672 | | c._parent = copy; |
| | | 673 | | Node? o = original._children[i]; |
| | | 674 | | if (o is null) throw new CorruptedDataStructureException("Found null children of an internal node!"); |
| | | 675 | | stack.Push((o, c)); |
| | | 676 | | } |
| | | 677 | | } |
| | | 678 | | } |
| | | 679 | | clone._count = _count; |
| | | 680 | | return clone; |
| | | 681 | | } |
| | | 682 | | |
| | | 683 | | #endregion |
| | | 684 | | } |