1 // Licensed to the .NET Foundation under one or more agreements. 2 // The .NET Foundation licenses this file to you under the MIT license. 3 // See the LICENSE file in the project root for more information. 4 5 using System.Collections.Generic; 6 using System.Diagnostics; 7 using System.Diagnostics.CodeAnalysis; 8 using System.Diagnostics.Contracts; 9 using System.Runtime.CompilerServices; 10 11 namespace System.Collections.Immutable 12 { 13 public sealed partial class ImmutableList<T> 14 { 15 /// <summary> 16 /// A node in the AVL tree storing this set. 17 /// </summary> 18 [DebuggerDisplay("{_key}")] 19 internal sealed class Node : IBinaryTree<T>, IEnumerable<T> 20 { 21 /// <summary> 22 /// The default empty node. 23 /// </summary> 24 internal static readonly Node EmptyNode = new Node(); 25 26 /// <summary> 27 /// The key associated with this node. 28 /// </summary> 29 private T _key; 30 31 /// <summary> 32 /// A value indicating whether this node has been frozen (made immutable). 33 /// </summary> 34 /// <remarks> 35 /// Nodes must be frozen before ever being observed by a wrapping collection type 36 /// to protect collections from further mutations. 37 /// </remarks> 38 private bool _frozen; 39 40 /// <summary> 41 /// The depth of the tree beneath this node. 42 /// </summary> 43 private byte _height; // AVL tree max height <= ~1.44 * log2(maxNodes + 2) 44 45 /// <summary> 46 /// The number of elements contained by this subtree starting at this node. 47 /// </summary> 48 /// <remarks> 49 /// If this node would benefit from saving 4 bytes, we could have only a few nodes 50 /// scattered throughout the graph actually record the count of nodes beneath them. 51 /// Those without the count could query their descendants, which would often short-circuit 52 /// when they hit a node that *does* include a count field. 53 /// </remarks> 54 private int _count; 55 56 /// <summary> 57 /// The left tree. 58 /// </summary> 59 private Node _left; 60 61 /// <summary> 62 /// The right tree. 63 /// </summary> 64 private Node _right; 65 66 /// <summary> 67 /// Initializes a new instance of the <see cref="ImmutableList{T}.Node"/> class 68 /// that is pre-frozen. 69 /// </summary> Node()70 private Node() 71 { 72 Contract.Ensures(this.IsEmpty); 73 _frozen = true; // the empty node is *always* frozen. 74 } 75 76 /// <summary> 77 /// Initializes a new instance of the <see cref="ImmutableList{T}.Node"/> class 78 /// that is not yet frozen. 79 /// </summary> 80 /// <param name="key">The value stored by this node.</param> 81 /// <param name="left">The left branch.</param> 82 /// <param name="right">The right branch.</param> 83 /// <param name="frozen">Whether this node is prefrozen.</param> Node(T key, Node left, Node right, bool frozen = false)84 private Node(T key, Node left, Node right, bool frozen = false) 85 { 86 Requires.NotNull(left, nameof(left)); 87 Requires.NotNull(right, nameof(right)); 88 Debug.Assert(!frozen || (left._frozen && right._frozen)); 89 Contract.Ensures(!this.IsEmpty); 90 91 _key = key; 92 _left = left; 93 _right = right; 94 _height = ParentHeight(left, right); 95 _count = ParentCount(left, right); 96 _frozen = frozen; 97 } 98 99 /// <summary> 100 /// Gets a value indicating whether this instance is empty. 101 /// </summary> 102 /// <value> 103 /// <c>true</c> if this instance is empty; otherwise, <c>false</c>. 104 /// </value> 105 public bool IsEmpty 106 { 107 get 108 { 109 Contract.Ensures(Contract.Result<bool>() == (_left == null)); 110 Debug.Assert(!(_left == null ^ _right == null)); 111 return _left == null; 112 } 113 } 114 115 /// <summary> 116 /// Gets the height of the tree beneath this node. 117 /// </summary> 118 public int Height => _height; 119 120 /// <summary> 121 /// Gets the left branch of this node. 122 /// </summary> 123 public Node Left => _left; 124 125 /// <summary> 126 /// Gets the left branch of this node. 127 /// </summary> 128 IBinaryTree IBinaryTree.Left => _left; 129 130 /// <summary> 131 /// Gets the right branch of this node. 132 /// </summary> 133 public Node Right => _right; 134 135 /// <summary> 136 /// Gets the right branch of this node. 137 /// </summary> 138 IBinaryTree IBinaryTree.Right => _right; 139 140 /// <summary> 141 /// Gets the left branch of this node. 142 /// </summary> 143 IBinaryTree<T> IBinaryTree<T>.Left => _left; 144 145 /// <summary> 146 /// Gets the right branch of this node. 147 /// </summary> 148 IBinaryTree<T> IBinaryTree<T>.Right => _right; 149 150 /// <summary> 151 /// Gets the value represented by the current node. 152 /// </summary> 153 public T Value => _key; 154 155 /// <summary> 156 /// Gets the number of elements contained by this subtree starting at this node. 157 /// </summary> 158 public int Count => _count; 159 160 /// <summary> 161 /// Gets the key. 162 /// </summary> 163 internal T Key => _key; 164 165 /// <summary> 166 /// Gets the element of the set at the given index. 167 /// </summary> 168 /// <param name="index">The 0-based index of the element in the set to return.</param> 169 /// <returns>The element at the given position.</returns> 170 internal T this[int index] 171 { 172 get 173 { 174 Requires.Range(index >= 0 && index < this.Count, nameof(index)); 175 176 if (index < _left._count) 177 { 178 return _left[index]; 179 } 180 181 if (index > _left._count) 182 { 183 return _right[index - _left._count - 1]; 184 } 185 186 return _key; 187 } 188 } 189 190 #if FEATURE_ITEMREFAPI 191 /// <summary> 192 /// Gets a read-only reference to the element of the set at the given index. 193 /// </summary> 194 /// <param name="index">The 0-based index of the element in the set to return.</param> 195 /// <returns>A read-only reference to the element at the given position.</returns> ItemRef(int index)196 internal ref readonly T ItemRef(int index) 197 { 198 Requires.Range(index >= 0 && index < this.Count, nameof(index)); 199 200 if (index < _left._count) 201 { 202 return ref _left.ItemRef(index); 203 } 204 205 if (index > _left._count) 206 { 207 return ref _right.ItemRef(index - _left._count - 1); 208 } 209 210 return ref _key; 211 } 212 #endif 213 214 #region IEnumerable<T> Members 215 216 /// <summary> 217 /// Returns an enumerator that iterates through the collection. 218 /// </summary> 219 /// <returns> 220 /// A <see cref="IEnumerator{T}"/> that can be used to iterate through the collection. 221 /// </returns> GetEnumerator()222 public Enumerator GetEnumerator() => new Enumerator(this); 223 224 /// <summary> 225 /// Returns an enumerator that iterates through the collection. 226 /// </summary> 227 /// <returns> 228 /// A <see cref="IEnumerator{T}"/> that can be used to iterate through the collection. 229 /// </returns> 230 [ExcludeFromCodeCoverage] // internal, never called, but here for interface implementation GetEnumerator()231 IEnumerator<T> IEnumerable<T>.GetEnumerator() => this.GetEnumerator(); 232 233 /// <summary> 234 /// Returns an enumerator that iterates through the collection. 235 /// </summary> 236 /// <returns> 237 /// A <see cref="IEnumerator{T}"/> that can be used to iterate through the collection. 238 /// </returns> 239 [ExcludeFromCodeCoverage] // internal, never called, but here for interface implementation IEnumerable.GetEnumerator()240 IEnumerator IEnumerable.GetEnumerator() => this.GetEnumerator(); 241 242 #endregion 243 244 /// <summary> 245 /// Returns an enumerator that iterates through the collection. 246 /// </summary> 247 /// <param name="builder">The builder, if applicable.</param> 248 /// <returns> 249 /// A <see cref="IEnumerator{T}"/> that can be used to iterate through the collection. 250 /// </returns> 251 internal Enumerator GetEnumerator(Builder builder) => new Enumerator(this, builder); 252 253 /// <summary> 254 /// Creates a node tree that contains the contents of a list. 255 /// </summary> 256 /// <param name="items">An indexable list with the contents that the new node tree should contain.</param> 257 /// <param name="start">The starting index within <paramref name="items"/> that should be captured by the node tree.</param> 258 /// <param name="length">The number of elements from <paramref name="items"/> that should be captured by the node tree.</param> 259 /// <returns>The root of the created node tree.</returns> 260 [Pure] NodeTreeFromList(IOrderedCollection<T> items, int start, int length)261 internal static Node NodeTreeFromList(IOrderedCollection<T> items, int start, int length) 262 { 263 Requires.NotNull(items, nameof(items)); 264 Requires.Range(start >= 0, nameof(start)); 265 Requires.Range(length >= 0, nameof(length)); 266 267 if (length == 0) 268 { 269 return EmptyNode; 270 } 271 272 int rightCount = (length - 1) / 2; 273 int leftCount = (length - 1) - rightCount; 274 Node left = NodeTreeFromList(items, start, leftCount); 275 Node right = NodeTreeFromList(items, start + leftCount + 1, rightCount); 276 return new Node(items[start + leftCount], left, right, true); 277 } 278 279 /// <summary> 280 /// Adds the specified key to the tree. 281 /// </summary> 282 /// <param name="key">The key.</param> 283 /// <returns>The new tree.</returns> Add(T key)284 internal Node Add(T key) 285 { 286 if (this.IsEmpty) 287 { 288 return CreateLeaf(key); 289 } 290 291 Node newRight = _right.Add(key); 292 Node result = this.MutateRight(newRight); 293 return result.IsBalanced ? result : result.BalanceRight(); 294 } 295 296 /// <summary> 297 /// Adds a value at a given index to this node. 298 /// </summary> 299 /// <param name="index">The location for the new value.</param> 300 /// <param name="key">The value to add.</param> 301 /// <returns>The new tree.</returns> Insert(int index, T key)302 internal Node Insert(int index, T key) 303 { 304 Requires.Range(index >= 0 && index <= this.Count, nameof(index)); 305 306 if (this.IsEmpty) 307 { 308 return CreateLeaf(key); 309 } 310 311 if (index <= _left._count) 312 { 313 Node newLeft = _left.Insert(index, key); 314 Node result = this.MutateLeft(newLeft); 315 return result.IsBalanced ? result : result.BalanceLeft(); 316 } 317 else 318 { 319 Node newRight = _right.Insert(index - _left._count - 1, key); 320 Node result = this.MutateRight(newRight); 321 return result.IsBalanced ? result : result.BalanceRight(); 322 } 323 } 324 325 /// <summary> 326 /// Adds the specified keys to this tree. 327 /// </summary> 328 /// <param name="keys">The keys.</param> 329 /// <returns>The new tree.</returns> AddRange(IEnumerable<T> keys)330 internal Node AddRange(IEnumerable<T> keys) 331 { 332 Requires.NotNull(keys, nameof(keys)); 333 334 if (this.IsEmpty) 335 { 336 return CreateRange(keys); 337 } 338 339 Node newRight = _right.AddRange(keys); 340 Node result = this.MutateRight(newRight); 341 return result.BalanceMany(); 342 } 343 344 /// <summary> 345 /// Adds the specified keys at a given index to this tree. 346 /// </summary> 347 /// <param name="index">The location for the new keys.</param> 348 /// <param name="keys">The keys.</param> 349 /// <returns>The new tree.</returns> InsertRange(int index, IEnumerable<T> keys)350 internal Node InsertRange(int index, IEnumerable<T> keys) 351 { 352 Requires.Range(index >= 0 && index <= this.Count, nameof(index)); 353 Requires.NotNull(keys, nameof(keys)); 354 355 if (this.IsEmpty) 356 { 357 return CreateRange(keys); 358 } 359 360 Node result; 361 if (index <= _left._count) 362 { 363 Node newLeft = _left.InsertRange(index, keys); 364 result = this.MutateLeft(newLeft); 365 } 366 else 367 { 368 Node newRight = _right.InsertRange(index - _left._count - 1, keys); 369 result = this.MutateRight(newRight); 370 } 371 372 return result.BalanceMany(); 373 } 374 375 /// <summary> 376 /// Removes a value at a given index to this node. 377 /// </summary> 378 /// <param name="index">The location for the new value.</param> 379 /// <returns>The new tree.</returns> RemoveAt(int index)380 internal Node RemoveAt(int index) 381 { 382 Requires.Range(index >= 0 && index < this.Count, nameof(index)); 383 384 Node result = this; 385 if (index == _left._count) 386 { 387 // We have a match. If this is a leaf, just remove it 388 // by returning Empty. If we have only one child, 389 // replace the node with the child. 390 if (_right.IsEmpty && _left.IsEmpty) 391 { 392 result = EmptyNode; 393 } 394 else if (_right.IsEmpty && !_left.IsEmpty) 395 { 396 result = _left; 397 } 398 else if (!_right.IsEmpty && _left.IsEmpty) 399 { 400 result = _right; 401 } 402 else 403 { 404 // We have two children. Remove the next-highest node and replace 405 // this node with it. 406 var successor = _right; 407 while (!successor._left.IsEmpty) 408 { 409 successor = successor._left; 410 } 411 412 var newRight = _right.RemoveAt(0); 413 result = successor.MutateBoth(left: _left, right: newRight); 414 } 415 } 416 else if (index < _left._count) 417 { 418 var newLeft = _left.RemoveAt(index); 419 result = this.MutateLeft(newLeft); 420 } 421 else 422 { 423 var newRight = _right.RemoveAt(index - _left._count - 1); 424 result = this.MutateRight(newRight); 425 } 426 427 return result.IsEmpty || result.IsBalanced ? result : result.Balance(); 428 } 429 430 /// <summary> 431 /// Removes all the elements that match the conditions defined by the specified 432 /// predicate. 433 /// </summary> 434 /// <param name="match"> 435 /// The <see cref="Predicate{T}"/> delegate that defines the conditions of the elements 436 /// to remove. 437 /// </param> 438 /// <returns> 439 /// The new node tree. 440 /// </returns> RemoveAll(Predicate<T> match)441 internal Node RemoveAll(Predicate<T> match) 442 { 443 Requires.NotNull(match, nameof(match)); 444 Contract.Ensures(Contract.Result<Node>() != null); 445 446 var result = this; 447 var enumerator = new Enumerator(result); 448 try 449 { 450 var startIndex = 0; 451 while (enumerator.MoveNext()) 452 { 453 if (match(enumerator.Current)) 454 { 455 result = result.RemoveAt(startIndex); 456 enumerator.Dispose(); 457 enumerator = new Enumerator(result, startIndex: startIndex); 458 } 459 else 460 { 461 startIndex++; 462 } 463 } 464 } 465 finally 466 { 467 enumerator.Dispose(); 468 } 469 470 return result; 471 } 472 473 /// <summary> 474 /// Replaces a value at a given index. 475 /// </summary> 476 /// <param name="index">The location for the new value.</param> 477 /// <param name="value">The new value for the node.</param> 478 /// <returns>The new tree.</returns> ReplaceAt(int index, T value)479 internal Node ReplaceAt(int index, T value) 480 { 481 Requires.Range(index >= 0 && index < this.Count, nameof(index)); 482 Debug.Assert(!this.IsEmpty); 483 484 Node result = this; 485 if (index == _left._count) 486 { 487 // We have a match. 488 result = this.MutateKey(value); 489 } 490 else if (index < _left._count) 491 { 492 var newLeft = _left.ReplaceAt(index, value); 493 result = this.MutateLeft(newLeft); 494 } 495 else 496 { 497 var newRight = _right.ReplaceAt(index - _left._count - 1, value); 498 result = this.MutateRight(newRight); 499 } 500 501 return result; 502 } 503 504 /// <summary> 505 /// Reverses the order of the elements in the entire <see cref="ImmutableList{T}"/>. 506 /// </summary> 507 /// <returns>The reversed list.</returns> Reverse()508 internal Node Reverse() => this.Reverse(0, this.Count); 509 510 /// <summary> 511 /// Reverses the order of the elements in the specified range. 512 /// </summary> 513 /// <param name="index">The zero-based starting index of the range to reverse.</param> 514 /// <param name="count">The number of elements in the range to reverse.</param> 515 /// <returns>The reversed list.</returns> Reverse(int index, int count)516 internal Node Reverse(int index, int count) 517 { 518 Requires.Range(index >= 0, nameof(index)); 519 Requires.Range(count >= 0, nameof(count)); 520 Requires.Range(index + count <= this.Count, nameof(index)); 521 522 Node result = this; 523 int start = index; 524 int end = index + count - 1; 525 while (start < end) 526 { 527 #if FEATURE_ITEMREFAPI 528 T a = result.ItemRef(start); 529 T b = result.ItemRef(end); 530 #else 531 T a = result[start]; 532 T b = result[end]; 533 #endif 534 result = result 535 .ReplaceAt(end, a) 536 .ReplaceAt(start, b); 537 start++; 538 end--; 539 } 540 541 return result; 542 } 543 544 /// <summary> 545 /// Sorts the elements in the entire <see cref="ImmutableList{T}"/> using 546 /// the default comparer. 547 /// </summary> Sort()548 internal Node Sort() => this.Sort(Comparer<T>.Default); 549 550 /// <summary> 551 /// Sorts the elements in the entire <see cref="ImmutableList{T}"/> using 552 /// the specified <see cref="Comparison{T}"/>. 553 /// </summary> 554 /// <param name="comparison"> 555 /// The <see cref="Comparison{T}"/> to use when comparing elements. 556 /// </param> 557 /// <returns>The sorted list.</returns> Sort(Comparison<T> comparison)558 internal Node Sort(Comparison<T> comparison) 559 { 560 Requires.NotNull(comparison, nameof(comparison)); 561 Contract.Ensures(Contract.Result<Node>() != null); 562 563 // PERF: Eventually this might be reimplemented in a way that does not require allocating an array. 564 var array = new T[this.Count]; 565 this.CopyTo(array); 566 Array.Sort(array, comparison); 567 return NodeTreeFromList(array.AsOrderedCollection(), 0, this.Count); 568 } 569 570 /// <summary> 571 /// Sorts the elements in the entire <see cref="ImmutableList{T}"/> using 572 /// the specified comparer. 573 /// </summary> 574 /// <param name="comparer"> 575 /// The <see cref="IComparer{T}"/> implementation to use when comparing 576 /// elements, or null to use the default comparer <see cref="Comparer{T}.Default"/>. 577 /// </param> 578 /// <returns>The sorted list.</returns> 579 internal Node Sort(IComparer<T> comparer) => this.Sort(0, this.Count, comparer); 580 581 /// <summary> 582 /// Sorts the elements in a range of elements in <see cref="ImmutableList{T}"/> 583 /// using the specified comparer. 584 /// </summary> 585 /// <param name="index"> 586 /// The zero-based starting index of the range to sort. 587 /// </param> 588 /// <param name="count"> 589 /// The length of the range to sort. 590 /// </param> 591 /// <param name="comparer"> 592 /// The <see cref="IComparer{T}"/> implementation to use when comparing 593 /// elements, or null to use the default comparer <see cref="Comparer{T}.Default"/>. 594 /// </param> 595 /// <returns>The sorted list.</returns> Sort(int index, int count, IComparer<T> comparer)596 internal Node Sort(int index, int count, IComparer<T> comparer) 597 { 598 Requires.Range(index >= 0, nameof(index)); 599 Requires.Range(count >= 0, nameof(count)); 600 Requires.Argument(index + count <= this.Count); 601 602 // PERF: Eventually this might be reimplemented in a way that does not require allocating an array. 603 var array = new T[this.Count]; 604 this.CopyTo(array); 605 Array.Sort(array, index, count, comparer); 606 return NodeTreeFromList(array.AsOrderedCollection(), 0, this.Count); 607 } 608 609 /// <summary> 610 /// Searches a range of elements in the sorted <see cref="ImmutableList{T}"/> 611 /// for an element using the specified comparer and returns the zero-based index 612 /// of the element. 613 /// </summary> 614 /// <param name="index">The zero-based starting index of the range to search.</param> 615 /// <param name="count"> The length of the range to search.</param> 616 /// <param name="item">The object to locate. The value can be null for reference types.</param> 617 /// <param name="comparer"> 618 /// The <see cref="IComparer{T}"/> implementation to use when comparing 619 /// elements, or null to use the default comparer <see cref="Comparer{T}.Default"/>. 620 /// </param> 621 /// <returns> 622 /// The zero-based index of item in the sorted <see cref="ImmutableList{T}"/>, 623 /// if item is found; otherwise, a negative number that is the bitwise complement 624 /// of the index of the next element that is larger than item or, if there is 625 /// no larger element, the bitwise complement of <see cref="ImmutableList{T}.Count"/>. 626 /// </returns> 627 /// <exception cref="ArgumentOutOfRangeException"> 628 /// <paramref name="index"/> is less than 0.-or-<paramref name="count"/> is less than 0. 629 /// </exception> 630 /// <exception cref="ArgumentException"> 631 /// <paramref name="index"/> and <paramref name="count"/> do not denote a valid range in the <see cref="ImmutableList{T}"/>. 632 /// </exception> 633 /// <exception cref="InvalidOperationException"> 634 /// <paramref name="comparer"/> is null, and the default comparer <see cref="Comparer{T}.Default"/> 635 /// cannot find an implementation of the <see cref="IComparable{T}"/> generic interface 636 /// or the <see cref="IComparable"/> interface for type <typeparamref name="T"/>. 637 /// </exception> BinarySearch(int index, int count, T item, IComparer<T> comparer)638 internal int BinarySearch(int index, int count, T item, IComparer<T> comparer) 639 { 640 Requires.Range(index >= 0, nameof(index)); 641 Requires.Range(count >= 0, nameof(count)); 642 comparer = comparer ?? Comparer<T>.Default; 643 644 if (this.IsEmpty || count <= 0) 645 { 646 return ~index; 647 } 648 649 // If this node is not within range, defer to either branch as appropriate. 650 int thisNodeIndex = _left.Count; // this is only the index within the AVL tree, treating this node as root rather than a member of a larger tree. 651 if (index + count <= thisNodeIndex) 652 { 653 return _left.BinarySearch(index, count, item, comparer); 654 } 655 else if (index > thisNodeIndex) 656 { 657 int result = _right.BinarySearch(index - thisNodeIndex - 1, count, item, comparer); 658 int offset = thisNodeIndex + 1; 659 return result < 0 ? result - offset : result + offset; 660 } 661 662 // We're definitely in the caller's designated range now. 663 // Any possible match will be a descendant of this node (or this immediate one). 664 // Some descendants may not be in range, but if we hit any it means no match was found, 665 // and a negative response would come back from the above code to the below code. 666 int compare = comparer.Compare(item, _key); 667 if (compare == 0) 668 { 669 return thisNodeIndex; 670 } 671 else if (compare > 0) 672 { 673 int adjustedCount = count - (thisNodeIndex - index) - 1; 674 int result = adjustedCount < 0 ? -1 : _right.BinarySearch(0, adjustedCount, item, comparer); 675 int offset = thisNodeIndex + 1; 676 return result < 0 ? result - offset : result + offset; 677 } 678 else 679 { 680 if (index == thisNodeIndex) 681 { 682 // We can't go any further left. 683 return ~index; 684 } 685 686 int result = _left.BinarySearch(index, count, item, comparer); 687 return result; 688 } 689 } 690 691 /// <summary> 692 /// Searches for the specified object and returns the zero-based index of the 693 /// first occurrence within the range of elements in the <see cref="ImmutableList{T}"/> 694 /// that starts at the specified index and contains the specified number of elements. 695 /// </summary> 696 /// <param name="item"> 697 /// The object to locate in the <see cref="ImmutableList{T}"/>. The value 698 /// can be null for reference types. 699 /// </param> 700 /// <param name="equalityComparer">The equality comparer to use for testing the match of two elements.</param> 701 /// <returns> 702 /// The zero-based index of the first occurrence of <paramref name="item"/> within the entire 703 /// <see cref="ImmutableList{T}"/>, if found; otherwise, -1. 704 /// </returns> 705 [Pure] IndexOf(T item, IEqualityComparer<T> equalityComparer)706 internal int IndexOf(T item, IEqualityComparer<T> equalityComparer) => this.IndexOf(item, 0, this.Count, equalityComparer); 707 708 /// <summary> 709 /// Searches for the specified object and returns the zero-based index of the 710 /// first occurrence within the range of elements in the <see cref="ImmutableList{T}"/> 711 /// that starts at the specified index and contains the specified number of elements. 712 /// </summary> 713 /// <param name="item"> 714 /// The object to locate in the <see cref="ImmutableList{T}"/>. The value 715 /// can be null for reference types. 716 /// </param> 717 /// <param name="index"> 718 /// The zero-based starting index of the search. 0 (zero) is valid in an empty 719 /// list. 720 /// </param> 721 /// <param name="count"> 722 /// The number of elements in the section to search. 723 /// </param> 724 /// <param name="equalityComparer"> 725 /// The equality comparer to use in the search. 726 /// If <c>null</c>, <see cref="EqualityComparer{T}.Default"/> is used. 727 /// </param> 728 /// <returns> 729 /// The zero-based index of the first occurrence of <paramref name="item"/> within the range of 730 /// elements in the <see cref="ImmutableList{T}"/> that starts at <paramref name="index"/> and 731 /// contains <paramref name="count"/> number of elements, if found; otherwise, -1. 732 /// </returns> 733 [Pure] IndexOf(T item, int index, int count, IEqualityComparer<T> equalityComparer)734 internal int IndexOf(T item, int index, int count, IEqualityComparer<T> equalityComparer) 735 { 736 Requires.Range(index >= 0, nameof(index)); 737 Requires.Range(count >= 0, nameof(count)); 738 Requires.Range(count <= this.Count, nameof(count)); 739 Requires.Range(index + count <= this.Count, nameof(count)); 740 741 equalityComparer = equalityComparer ?? EqualityComparer<T>.Default; 742 using (var enumerator = new Enumerator(this, startIndex: index, count: count)) 743 { 744 while (enumerator.MoveNext()) 745 { 746 if (equalityComparer.Equals(item, enumerator.Current)) 747 { 748 return index; 749 } 750 751 index++; 752 } 753 } 754 755 return -1; 756 } 757 758 /// <summary> 759 /// Searches for the specified object and returns the zero-based index of the 760 /// last occurrence within the range of elements in the <see cref="ImmutableList{T}"/> 761 /// that contains the specified number of elements and ends at the specified 762 /// index. 763 /// </summary> 764 /// <param name="item"> 765 /// The object to locate in the <see cref="ImmutableList{T}"/>. The value 766 /// can be null for reference types. 767 /// </param> 768 /// <param name="index">The zero-based starting index of the backward search.</param> 769 /// <param name="count">The number of elements in the section to search.</param> 770 /// <param name="equalityComparer">The equality comparer to use for testing the match of two elements.</param> 771 /// <returns> 772 /// The zero-based index of the last occurrence of <paramref name="item"/> within the range of elements 773 /// in the <see cref="ImmutableList{T}"/> that contains <paramref name="count"/> number of elements 774 /// and ends at <paramref name="index"/>, if found; otherwise, -1. 775 /// </returns> 776 [Pure] LastIndexOf(T item, int index, int count, IEqualityComparer<T> equalityComparer)777 internal int LastIndexOf(T item, int index, int count, IEqualityComparer<T> equalityComparer) 778 { 779 Requires.Range(index >= 0, nameof(index)); 780 Requires.Range(count >= 0 && count <= this.Count, nameof(count)); 781 Requires.Argument(index - count + 1 >= 0); 782 783 equalityComparer = equalityComparer ?? EqualityComparer<T>.Default; 784 using (var enumerator = new Enumerator(this, startIndex: index, count: count, reversed: true)) 785 { 786 while (enumerator.MoveNext()) 787 { 788 if (equalityComparer.Equals(item, enumerator.Current)) 789 { 790 return index; 791 } 792 793 index--; 794 } 795 } 796 797 return -1; 798 } 799 800 /// <summary> 801 /// Copies the entire <see cref="ImmutableList{T}"/> to a compatible one-dimensional 802 /// array, starting at the beginning of the target array. 803 /// </summary> 804 /// <param name="array"> 805 /// The one-dimensional <see cref="Array"/> that is the destination of the elements 806 /// copied from <see cref="ImmutableList{T}"/>. The <see cref="Array"/> must have 807 /// zero-based indexing. 808 /// </param> CopyTo(T[] array)809 internal void CopyTo(T[] array) 810 { 811 Requires.NotNull(array, nameof(array)); 812 Requires.Range(array.Length >= this.Count, nameof(array)); 813 814 int index = 0; 815 foreach (var element in this) 816 { 817 array[index++] = element; 818 } 819 } 820 821 /// <summary> 822 /// Copies the entire <see cref="ImmutableList{T}"/> to a compatible one-dimensional 823 /// array, starting at the specified index of the target array. 824 /// </summary> 825 /// <param name="array"> 826 /// The one-dimensional <see cref="Array"/> that is the destination of the elements 827 /// copied from <see cref="ImmutableList{T}"/>. The <see cref="Array"/> must have 828 /// zero-based indexing. 829 /// </param> 830 /// <param name="arrayIndex"> 831 /// The zero-based index in <paramref name="array"/> at which copying begins. 832 /// </param> CopyTo(T[] array, int arrayIndex)833 internal void CopyTo(T[] array, int arrayIndex) 834 { 835 Requires.NotNull(array, nameof(array)); 836 Requires.Range(arrayIndex >= 0, nameof(arrayIndex)); 837 Requires.Range(array.Length >= arrayIndex + this.Count, nameof(arrayIndex)); 838 839 foreach (var element in this) 840 { 841 array[arrayIndex++] = element; 842 } 843 } 844 845 /// <summary> 846 /// Copies a range of elements from the <see cref="ImmutableList{T}"/> to 847 /// a compatible one-dimensional array, starting at the specified index of the 848 /// target array. 849 /// </summary> 850 /// <param name="index"> 851 /// The zero-based index in the source <see cref="ImmutableList{T}"/> at 852 /// which copying begins. 853 /// </param> 854 /// <param name="array"> 855 /// The one-dimensional <see cref="Array"/> that is the destination of the elements 856 /// copied from <see cref="ImmutableList{T}"/>. The <see cref="Array"/> must have 857 /// zero-based indexing. 858 /// </param> 859 /// <param name="arrayIndex">The zero-based index in <paramref name="array"/> at which copying begins.</param> 860 /// <param name="count">The number of elements to copy.</param> CopyTo(int index, T[] array, int arrayIndex, int count)861 internal void CopyTo(int index, T[] array, int arrayIndex, int count) 862 { 863 Requires.NotNull(array, nameof(array)); 864 Requires.Range(index >= 0, nameof(index)); 865 Requires.Range(count >= 0, nameof(count)); 866 Requires.Range(index + count <= this.Count, nameof(count)); 867 Requires.Range(arrayIndex >= 0, nameof(arrayIndex)); 868 Requires.Range(arrayIndex + count <= array.Length, nameof(arrayIndex)); 869 870 using (var enumerator = new Enumerator(this, startIndex: index, count: count)) 871 { 872 while (enumerator.MoveNext()) 873 { 874 array[arrayIndex++] = enumerator.Current; 875 } 876 } 877 } 878 879 /// <summary> 880 /// Copies the elements of the <see cref="ICollection"/> to an <see cref="Array"/>, starting at a particular <see cref="Array"/> index. 881 /// </summary> 882 /// <param name="array">The one-dimensional <see cref="Array"/> that is the destination of the elements copied from <see cref="ICollection"/>. The <see cref="Array"/> must have zero-based indexing.</param> 883 /// <param name="arrayIndex">The zero-based index in <paramref name="array"/> at which copying begins.</param> CopyTo(Array array, int arrayIndex)884 internal void CopyTo(Array array, int arrayIndex) 885 { 886 Requires.NotNull(array, nameof(array)); 887 Requires.Range(arrayIndex >= 0, nameof(arrayIndex)); 888 Requires.Range(array.Length >= arrayIndex + this.Count, nameof(arrayIndex)); 889 890 foreach (var element in this) 891 { 892 array.SetValue(element, arrayIndex++); 893 } 894 } 895 896 /// <summary> 897 /// Converts the elements in the current <see cref="ImmutableList{T}"/> to 898 /// another type, and returns a list containing the converted elements. 899 /// </summary> 900 /// <param name="converter"> 901 /// A <see cref="Func{T, TResult}"/> delegate that converts each element from 902 /// one type to another type. 903 /// </param> 904 /// <typeparam name="TOutput"> 905 /// The type of the elements of the target array. 906 /// </typeparam> 907 /// <returns> 908 /// A node tree with the transformed list. 909 /// </returns> ConvertAll(Func<T, TOutput> converter)910 internal ImmutableList<TOutput>.Node ConvertAll<TOutput>(Func<T, TOutput> converter) 911 { 912 var root = ImmutableList<TOutput>.Node.EmptyNode; 913 914 if (this.IsEmpty) 915 { 916 return root; 917 } 918 919 return root.AddRange(Linq.Enumerable.Select(this, converter)); 920 } 921 922 /// <summary> 923 /// Determines whether every element in the <see cref="ImmutableList{T}"/> 924 /// matches the conditions defined by the specified predicate. 925 /// </summary> 926 /// <param name="match"> 927 /// The <see cref="Predicate{T}"/> delegate that defines the conditions to check against 928 /// the elements. 929 /// </param> 930 /// <returns> 931 /// true if every element in the <see cref="ImmutableList{T}"/> matches the 932 /// conditions defined by the specified predicate; otherwise, false. If the list 933 /// has no elements, the return value is true. 934 /// </returns> TrueForAll(Predicate<T> match)935 internal bool TrueForAll(Predicate<T> match) 936 { 937 Requires.NotNull(match, nameof(match)); 938 939 foreach (var item in this) 940 { 941 if (!match(item)) 942 { 943 return false; 944 } 945 } 946 947 return true; 948 } 949 950 /// <summary> 951 /// Determines whether the <see cref="ImmutableList{T}"/> contains elements 952 /// that match the conditions defined by the specified predicate. 953 /// </summary> 954 /// <param name="match"> 955 /// The <see cref="Predicate{T}"/> delegate that defines the conditions of the elements 956 /// to search for. 957 /// </param> 958 /// <returns> 959 /// true if the <see cref="ImmutableList{T}"/> contains one or more elements 960 /// that match the conditions defined by the specified predicate; otherwise, 961 /// false. 962 /// </returns> Exists(Predicate<T> match)963 internal bool Exists(Predicate<T> match) 964 { 965 Requires.NotNull(match, nameof(match)); 966 967 foreach (T item in this) 968 { 969 if (match(item)) 970 { 971 return true; 972 } 973 } 974 975 return false; 976 } 977 978 /// <summary> 979 /// Searches for an element that matches the conditions defined by the specified 980 /// predicate, and returns the first occurrence within the entire <see cref="ImmutableList{T}"/>. 981 /// </summary> 982 /// <param name="match"> 983 /// The <see cref="Predicate{T}"/> delegate that defines the conditions of the element 984 /// to search for. 985 /// </param> 986 /// <returns> 987 /// The first element that matches the conditions defined by the specified predicate, 988 /// if found; otherwise, the default value for type <typeparamref name="T"/>. 989 /// </returns> Find(Predicate<T> match)990 internal T Find(Predicate<T> match) 991 { 992 Requires.NotNull(match, nameof(match)); 993 994 foreach (var item in this) 995 { 996 if (match(item)) 997 { 998 return item; 999 } 1000 } 1001 1002 return default(T); 1003 } 1004 1005 /// <summary> 1006 /// Retrieves all the elements that match the conditions defined by the specified 1007 /// predicate. 1008 /// </summary> 1009 /// <param name="match"> 1010 /// The <see cref="Predicate{T}"/> delegate that defines the conditions of the elements 1011 /// to search for. 1012 /// </param> 1013 /// <returns> 1014 /// A <see cref="ImmutableList{T}"/> containing all the elements that match 1015 /// the conditions defined by the specified predicate, if found; otherwise, an 1016 /// empty <see cref="ImmutableList{T}"/>. 1017 /// </returns> FindAll(Predicate<T> match)1018 internal ImmutableList<T> FindAll(Predicate<T> match) 1019 { 1020 Requires.NotNull(match, nameof(match)); 1021 Contract.Ensures(Contract.Result<ImmutableList<T>>() != null); 1022 1023 if (this.IsEmpty) 1024 { 1025 return ImmutableList<T>.Empty; 1026 } 1027 1028 List<T> list = null; 1029 foreach (var item in this) 1030 { 1031 if (match(item)) 1032 { 1033 if (list == null) 1034 { 1035 list = new List<T>(); 1036 } 1037 1038 list.Add(item); 1039 } 1040 } 1041 1042 return list != null ? 1043 ImmutableList.CreateRange(list) : 1044 ImmutableList<T>.Empty; 1045 } 1046 1047 /// <summary> 1048 /// Searches for an element that matches the conditions defined by the specified 1049 /// predicate, and returns the zero-based index of the first occurrence within 1050 /// the entire <see cref="ImmutableList{T}"/>. 1051 /// </summary> 1052 /// <param name="match"> 1053 /// The <see cref="Predicate{T}"/> delegate that defines the conditions of the element 1054 /// to search for. 1055 /// </param> 1056 /// <returns> 1057 /// The zero-based index of the first occurrence of an element that matches the 1058 /// conditions defined by <paramref name="match"/>, if found; otherwise, -1. 1059 /// </returns> FindIndex(Predicate<T> match)1060 internal int FindIndex(Predicate<T> match) 1061 { 1062 Requires.NotNull(match, nameof(match)); 1063 Contract.Ensures(Contract.Result<int>() >= -1); 1064 1065 return this.FindIndex(0, _count, match); 1066 } 1067 1068 /// <summary> 1069 /// Searches for an element that matches the conditions defined by the specified 1070 /// predicate, and returns the zero-based index of the first occurrence within 1071 /// the range of elements in the <see cref="ImmutableList{T}"/> that extends 1072 /// from the specified index to the last element. 1073 /// </summary> 1074 /// <param name="startIndex">The zero-based starting index of the search.</param> 1075 /// <param name="match">The <see cref="Predicate{T}"/> delegate that defines the conditions of the element to search for.</param> 1076 /// <returns> 1077 /// The zero-based index of the first occurrence of an element that matches the 1078 /// conditions defined by <paramref name="match"/>, if found; otherwise, -1. 1079 /// </returns> FindIndex(int startIndex, Predicate<T> match)1080 internal int FindIndex(int startIndex, Predicate<T> match) 1081 { 1082 Requires.NotNull(match, nameof(match)); 1083 Requires.Range(startIndex >= 0 && startIndex <= this.Count, nameof(startIndex)); 1084 1085 return this.FindIndex(startIndex, this.Count - startIndex, match); 1086 } 1087 1088 /// <summary> 1089 /// Searches for an element that matches the conditions defined by the specified 1090 /// predicate, and returns the zero-based index of the first occurrence within 1091 /// the range of elements in the <see cref="ImmutableList{T}"/> that starts 1092 /// at the specified index and contains the specified number of elements. 1093 /// </summary> 1094 /// <param name="startIndex">The zero-based starting index of the search.</param> 1095 /// <param name="count">The number of elements in the section to search.</param> 1096 /// <param name="match">The <see cref="Predicate{T}"/> delegate that defines the conditions of the element to search for.</param> 1097 /// <returns> 1098 /// The zero-based index of the first occurrence of an element that matches the 1099 /// conditions defined by <paramref name="match"/>, if found; otherwise, -1. 1100 /// </returns> FindIndex(int startIndex, int count, Predicate<T> match)1101 internal int FindIndex(int startIndex, int count, Predicate<T> match) 1102 { 1103 Requires.NotNull(match, nameof(match)); 1104 Requires.Range(startIndex >= 0, nameof(startIndex)); 1105 Requires.Range(count >= 0, nameof(count)); 1106 Requires.Range(startIndex + count <= this.Count, nameof(count)); 1107 1108 using (var enumerator = new Enumerator(this, startIndex: startIndex, count: count)) 1109 { 1110 int index = startIndex; 1111 while (enumerator.MoveNext()) 1112 { 1113 if (match(enumerator.Current)) 1114 { 1115 return index; 1116 } 1117 1118 index++; 1119 } 1120 } 1121 1122 return -1; 1123 } 1124 1125 /// <summary> 1126 /// Searches for an element that matches the conditions defined by the specified 1127 /// predicate, and returns the last occurrence within the entire <see cref="ImmutableList{T}"/>. 1128 /// </summary> 1129 /// <param name="match"> 1130 /// The <see cref="Predicate{T}"/> delegate that defines the conditions of the element 1131 /// to search for. 1132 /// </param> 1133 /// <returns> 1134 /// The last element that matches the conditions defined by the specified predicate, 1135 /// if found; otherwise, the default value for type <typeparamref name="T"/>. 1136 /// </returns> FindLast(Predicate<T> match)1137 internal T FindLast(Predicate<T> match) 1138 { 1139 Requires.NotNull(match, nameof(match)); 1140 1141 using (var enumerator = new Enumerator(this, reversed: true)) 1142 { 1143 while (enumerator.MoveNext()) 1144 { 1145 if (match(enumerator.Current)) 1146 { 1147 return enumerator.Current; 1148 } 1149 } 1150 } 1151 1152 return default(T); 1153 } 1154 1155 /// <summary> 1156 /// Searches for an element that matches the conditions defined by the specified 1157 /// predicate, and returns the zero-based index of the last occurrence within 1158 /// the entire <see cref="ImmutableList{T}"/>. 1159 /// </summary> 1160 /// <param name="match"> 1161 /// The <see cref="Predicate{T}"/> delegate that defines the conditions of the element 1162 /// to search for. 1163 /// </param> 1164 /// <returns> 1165 /// The zero-based index of the last occurrence of an element that matches the 1166 /// conditions defined by <paramref name="match"/>, if found; otherwise, -1. 1167 /// </returns> FindLastIndex(Predicate<T> match)1168 internal int FindLastIndex(Predicate<T> match) 1169 { 1170 Requires.NotNull(match, nameof(match)); 1171 Contract.Ensures(Contract.Result<int>() >= -1); 1172 1173 return this.IsEmpty ? -1 : this.FindLastIndex(this.Count - 1, this.Count, match); 1174 } 1175 1176 /// <summary> 1177 /// Searches for an element that matches the conditions defined by the specified 1178 /// predicate, and returns the zero-based index of the last occurrence within 1179 /// the range of elements in the <see cref="ImmutableList{T}"/> that extends 1180 /// from the first element to the specified index. 1181 /// </summary> 1182 /// <param name="startIndex">The zero-based starting index of the backward search.</param> 1183 /// <param name="match">The <see cref="Predicate{T}"/> delegate that defines the conditions of the element 1184 /// to search for.</param> 1185 /// <returns> 1186 /// The zero-based index of the last occurrence of an element that matches the 1187 /// conditions defined by <paramref name="match"/>, if found; otherwise, -1. 1188 /// </returns> FindLastIndex(int startIndex, Predicate<T> match)1189 internal int FindLastIndex(int startIndex, Predicate<T> match) 1190 { 1191 Requires.NotNull(match, nameof(match)); 1192 Requires.Range(startIndex >= 0, nameof(startIndex)); 1193 Requires.Range(startIndex == 0 || startIndex < this.Count, nameof(startIndex)); 1194 1195 return this.IsEmpty ? -1 : this.FindLastIndex(startIndex, startIndex + 1, match); 1196 } 1197 1198 /// <summary> 1199 /// Searches for an element that matches the conditions defined by the specified 1200 /// predicate, and returns the zero-based index of the last occurrence within 1201 /// the range of elements in the <see cref="ImmutableList{T}"/> that contains 1202 /// the specified number of elements and ends at the specified index. 1203 /// </summary> 1204 /// <param name="startIndex">The zero-based starting index of the backward search.</param> 1205 /// <param name="count">The number of elements in the section to search.</param> 1206 /// <param name="match"> 1207 /// The <see cref="Predicate{T}"/> delegate that defines the conditions of the element 1208 /// to search for. 1209 /// </param> 1210 /// <returns> 1211 /// The zero-based index of the last occurrence of an element that matches the 1212 /// conditions defined by <paramref name="match"/>, if found; otherwise, -1. 1213 /// </returns> FindLastIndex(int startIndex, int count, Predicate<T> match)1214 internal int FindLastIndex(int startIndex, int count, Predicate<T> match) 1215 { 1216 Requires.NotNull(match, nameof(match)); 1217 Requires.Range(startIndex >= 0, nameof(startIndex)); 1218 Requires.Range(count <= this.Count, nameof(count)); 1219 Requires.Range(startIndex - count + 1 >= 0, nameof(startIndex)); 1220 1221 using (var enumerator = new Enumerator(this, startIndex: startIndex, count: count, reversed: true)) 1222 { 1223 int index = startIndex; 1224 while (enumerator.MoveNext()) 1225 { 1226 if (match(enumerator.Current)) 1227 { 1228 return index; 1229 } 1230 1231 index--; 1232 } 1233 } 1234 1235 return -1; 1236 } 1237 1238 /// <summary> 1239 /// Freezes this node and all descendant nodes so that any mutations require a new instance of the nodes. 1240 /// </summary> Freeze()1241 internal void Freeze() 1242 { 1243 // If this node is frozen, all its descendants must already be frozen. 1244 if (!_frozen) 1245 { 1246 _left.Freeze(); 1247 _right.Freeze(); 1248 _frozen = true; 1249 } 1250 } 1251 1252 #region Tree balancing methods 1253 1254 /// <summary> 1255 /// AVL rotate left operation. 1256 /// </summary> 1257 /// <returns>The rotated tree.</returns> RotateLeft()1258 private Node RotateLeft() 1259 { 1260 Debug.Assert(!this.IsEmpty); 1261 Debug.Assert(!_right.IsEmpty); 1262 Contract.Ensures(Contract.Result<Node>() != null); 1263 1264 return _right.MutateLeft(this.MutateRight(_right._left)); 1265 } 1266 1267 /// <summary> 1268 /// AVL rotate right operation. 1269 /// </summary> 1270 /// <returns>The rotated tree.</returns> RotateRight()1271 private Node RotateRight() 1272 { 1273 Debug.Assert(!this.IsEmpty); 1274 Debug.Assert(!_left.IsEmpty); 1275 Contract.Ensures(Contract.Result<Node>() != null); 1276 1277 return _left.MutateRight(this.MutateLeft(_left._right)); 1278 } 1279 1280 /// <summary> 1281 /// AVL rotate double-left operation. 1282 /// </summary> 1283 /// <returns>The rotated tree.</returns> DoubleLeft()1284 private Node DoubleLeft() 1285 { 1286 Debug.Assert(!this.IsEmpty); 1287 Debug.Assert(!_right.IsEmpty); 1288 Debug.Assert(!_right._left.IsEmpty); 1289 Contract.Ensures(Contract.Result<Node>() != null); 1290 1291 // The following is an optimized version of rotating the right child right, then rotating the parent left. 1292 Node right = _right; 1293 Node rightLeft = right._left; 1294 return rightLeft.MutateBoth( 1295 left: this.MutateRight(rightLeft._left), 1296 right: right.MutateLeft(rightLeft._right)); 1297 } 1298 1299 /// <summary> 1300 /// AVL rotate double-right operation. 1301 /// </summary> 1302 /// <returns>The rotated tree.</returns> DoubleRight()1303 private Node DoubleRight() 1304 { 1305 Debug.Assert(!this.IsEmpty); 1306 Debug.Assert(!_left.IsEmpty); 1307 Debug.Assert(!_left._right.IsEmpty); 1308 Contract.Ensures(Contract.Result<Node>() != null); 1309 1310 // The following is an optimized version of rotating the left child left, then rotating the parent right. 1311 Node left = _left; 1312 Node leftRight = left._right; 1313 return leftRight.MutateBoth( 1314 left: left.MutateRight(leftRight._left), 1315 right: this.MutateLeft(leftRight._right)); 1316 } 1317 1318 /// <summary> 1319 /// Gets a value indicating whether this tree is in balance. 1320 /// </summary> 1321 /// <returns> 1322 /// 0 if the heights of both sides are the same, a positive integer if the right side is taller, or a negative integer if the left side is taller. 1323 /// </returns> 1324 private int BalanceFactor 1325 { 1326 get 1327 { 1328 Debug.Assert(!this.IsEmpty); 1329 return _right._height - _left._height; 1330 } 1331 } 1332 1333 /// <summary> 1334 /// Determines whether this tree is right heavy. 1335 /// </summary> 1336 /// <returns> 1337 /// <c>true</c> if this tree is right heavy; otherwise, <c>false</c>. 1338 /// </returns> 1339 private bool IsRightHeavy => this.BalanceFactor >= 2; 1340 1341 /// <summary> 1342 /// Determines whether this tree is left heavy. 1343 /// </summary> 1344 /// <returns> 1345 /// <c>true</c> if this tree is left heavy; otherwise, <c>false</c>. 1346 /// </returns> 1347 private bool IsLeftHeavy => this.BalanceFactor <= -2; 1348 1349 /// <summary> 1350 /// Determines whether this tree has a balance factor of -1, 0, or 1. 1351 /// </summary> 1352 /// <returns> 1353 /// <c>true</c> if this tree is balanced; otherwise, <c>false</c>. 1354 /// </returns> 1355 private bool IsBalanced => unchecked((uint)(this.BalanceFactor + 1)) <= 2; 1356 1357 /// <summary> 1358 /// Balances this tree. 1359 /// </summary> 1360 /// <returns>A balanced tree.</returns> Balance()1361 private Node Balance() => this.IsLeftHeavy ? this.BalanceLeft() : this.BalanceRight(); 1362 1363 /// <summary> 1364 /// Balances the left side of this tree by rotating this tree rightwards. 1365 /// </summary> 1366 /// <returns>A balanced tree.</returns> BalanceLeft()1367 private Node BalanceLeft() 1368 { 1369 Debug.Assert(!this.IsEmpty); 1370 Debug.Assert(this.IsLeftHeavy); 1371 1372 return _left.BalanceFactor > 0 ? this.DoubleRight() : this.RotateRight(); 1373 } 1374 1375 /// <summary> 1376 /// Balances the right side of this tree by rotating this tree leftwards. 1377 /// </summary> 1378 /// <returns>A balanced tree.</returns> BalanceRight()1379 private Node BalanceRight() 1380 { 1381 Debug.Assert(!this.IsEmpty); 1382 Debug.Assert(this.IsRightHeavy); 1383 1384 return _right.BalanceFactor < 0 ? this.DoubleLeft() : this.RotateLeft(); 1385 } 1386 1387 /// <summary> 1388 /// Balances this tree. Allows for a large imbalance between left and 1389 /// right nodes, but assumes left and right nodes are individually balanced. 1390 /// </summary> 1391 /// <returns>A balanced tree.</returns> 1392 /// <remarks> 1393 /// If this tree is already balanced, this method does nothing. 1394 /// </remarks> BalanceMany()1395 private Node BalanceMany() 1396 { 1397 Node tree = this; 1398 while (!tree.IsBalanced) 1399 { 1400 if (tree.IsRightHeavy) 1401 { 1402 tree = tree.BalanceRight(); 1403 tree.MutateLeft(tree._left.BalanceMany()); 1404 } 1405 else 1406 { 1407 tree = tree.BalanceLeft(); 1408 tree.MutateRight(tree._right.BalanceMany()); 1409 } 1410 } 1411 1412 return tree; 1413 } 1414 1415 #endregion 1416 1417 /// <summary> 1418 /// Creates a node mutation, either by mutating this node (if not yet frozen) or by creating a clone of this node 1419 /// with the described changes. 1420 /// </summary> 1421 /// <param name="left">The left branch of the mutated node.</param> 1422 /// <param name="right">The right branch of the mutated node.</param> 1423 /// <returns>The mutated (or created) node.</returns> MutateBoth(Node left, Node right)1424 private Node MutateBoth(Node left, Node right) 1425 { 1426 Requires.NotNull(left, nameof(left)); 1427 Requires.NotNull(right, nameof(right)); 1428 Debug.Assert(!this.IsEmpty); 1429 1430 if (_frozen) 1431 { 1432 return new Node(_key, left, right); 1433 } 1434 else 1435 { 1436 _left = left; 1437 _right = right; 1438 _height = ParentHeight(left, right); 1439 _count = ParentCount(left, right); 1440 return this; 1441 } 1442 } 1443 1444 /// <summary> 1445 /// Creates a node mutation, either by mutating this node (if not yet frozen) or by creating a clone of this node 1446 /// with the described changes. 1447 /// </summary> 1448 /// <param name="left">The left branch of the mutated node.</param> 1449 /// <returns>The mutated (or created) node.</returns> MutateLeft(Node left)1450 private Node MutateLeft(Node left) 1451 { 1452 Requires.NotNull(left, nameof(left)); 1453 Debug.Assert(!this.IsEmpty); 1454 1455 if (_frozen) 1456 { 1457 return new Node(_key, left, _right); 1458 } 1459 else 1460 { 1461 _left = left; 1462 _height = ParentHeight(left, _right); 1463 _count = ParentCount(left, _right); 1464 return this; 1465 } 1466 } 1467 1468 /// <summary> 1469 /// Creates a node mutation, either by mutating this node (if not yet frozen) or by creating a clone of this node 1470 /// with the described changes. 1471 /// </summary> 1472 /// <param name="right">The right branch of the mutated node.</param> 1473 /// <returns>The mutated (or created) node.</returns> MutateRight(Node right)1474 private Node MutateRight(Node right) 1475 { 1476 Requires.NotNull(right, nameof(right)); 1477 Debug.Assert(!this.IsEmpty); 1478 1479 if (_frozen) 1480 { 1481 return new Node(_key, _left, right); 1482 } 1483 else 1484 { 1485 _right = right; 1486 _height = ParentHeight(_left, right); 1487 _count = ParentCount(_left, right); 1488 return this; 1489 } 1490 } 1491 1492 /// <summary> 1493 /// Calculates the height of the parent node from its children. 1494 /// </summary> 1495 /// <param name="left">The left child.</param> 1496 /// <param name="right">The right child.</param> 1497 /// <returns>The height of the parent node.</returns> 1498 [MethodImpl(MethodImplOptions.AggressiveInlining)] ParentHeight(Node left, Node right)1499 private static byte ParentHeight(Node left, Node right) => checked((byte)(1 + Math.Max(left._height, right._height))); 1500 1501 /// <summary> 1502 /// Calculates the number of elements in the parent node from its children. 1503 /// </summary> 1504 /// <param name="left">The left child.</param> 1505 /// <param name="right">The right child.</param> 1506 /// <returns>The number of elements in the parent node.</returns> ParentCount(Node left, Node right)1507 private static int ParentCount(Node left, Node right) => 1 + left._count + right._count; 1508 1509 /// <summary> 1510 /// Creates a node mutation, either by mutating this node (if not yet frozen) or by creating a clone of this node 1511 /// with the described changes. 1512 /// </summary> 1513 /// <param name="key">The new key for this node.</param> 1514 /// <returns>The mutated (or created) node.</returns> MutateKey(T key)1515 private Node MutateKey(T key) 1516 { 1517 Debug.Assert(!this.IsEmpty); 1518 1519 if (_frozen) 1520 { 1521 return new Node(key, _left, _right); 1522 } 1523 else 1524 { 1525 _key = key; 1526 return this; 1527 } 1528 } 1529 1530 /// <summary> 1531 /// Creates a node from the specified keys. 1532 /// </summary> 1533 /// <param name="keys">The keys.</param> 1534 /// <returns>The root of the created node tree.</returns> CreateRange(IEnumerable<T> keys)1535 private static Node CreateRange(IEnumerable<T> keys) 1536 { 1537 ImmutableList<T> other; 1538 if (TryCastToImmutableList(keys, out other)) 1539 { 1540 return other._root; 1541 } 1542 1543 var list = keys.AsOrderedCollection(); 1544 return NodeTreeFromList(list, 0, list.Count); 1545 } 1546 1547 /// <summary> 1548 /// Creates a leaf node. 1549 /// </summary> 1550 /// <param name="key">The leaf node's key.</param> 1551 /// <returns>The leaf node.</returns> 1552 private static Node CreateLeaf(T key) => new Node(key, left: EmptyNode, right: EmptyNode); 1553 } 1554 } 1555 } 1556