22internal static readonly Node EmptyNode = new Node(); 278return new Node(items[start + leftCount], left, right, true); 297return new Node(items[leftCount], left, right, frozen: true); 1470return new Node(_key, left, right); 1495return new Node(_key, left, _right!); 1519return new Node(_key, _left!, right); 1559return new Node(key, _left!, _right!); 1590private static Node CreateLeaf(T key) => new Node(key, left: EmptyNode, right: EmptyNode);

34private readonly ImmutableList<KeyValuePair<TKey, TValue>>.Node _additionalElements; 41private HashBucket(KeyValuePair<TKey, TValue> firstElement, ImmutableList<KeyValuePair<TKey, TValue>>.Node? additionalElements = null) 44_additionalElements = additionalElements ?? ImmutableList<KeyValuePair<TKey, TValue>>.Node.EmptyNode; 77internal ImmutableList<KeyValuePair<TKey, TValue>>.Node AdditionalElements

49private readonly ImmutableList<T>.Node _additionalElements; 56private HashBucket(T firstElement, ImmutableList<T>.Node? additionalElements = null) 59_additionalElements = additionalElements ?? ImmutableList<T>.Node.EmptyNode;

36private Node _root = Node.EmptyNode; 97internal Node Root 202this.Root = ImmutableList<T>.Node.EmptyNode; 340return ImmutableList<T>.WrapNode(Node.NodeTreeFromList(this, index, count));

29private readonly Node _root; 34internal ImmutableList() => _root = Node.EmptyNode; 40private ImmutableList(Node root) 216ImmutableList<T>.Node result = _root.Add(value); 233ImmutableList<T>.Node result = _root.AddRange(items); 250return new ImmutableList<T>(Node.NodeTreeFromList(items)); 280ImmutableList<T>.Node result = _root.InsertRange(index, items); 310ImmutableList<T>.Node result = _root; 352ImmutableList<T>.Node result = _root; 371ImmutableList<T>.Node result = _root.RemoveAt(index); 566return this.Wrap(Node.NodeTreeFromList(this, index, count)); 1101/// Returns the root <see cref="Node"/> of the list 1103internal Node Root => _root; 1110private static ImmutableList<T> WrapNode(Node root) 1161private ImmutableList<T> Wrap(Node root) 1200Node root = Node.NodeTreeFromList(list, 0, list.Count);

62private Node _root; 67private SecurePooledObject<Stack<RefAsValueType<Node>>>? _stack; 72private Node? _current; 87internal Enumerator(Node root, Builder? builder = null, int startIndex = -1, int count = -1, bool reversed = false) 107if (!SecureObjectPool<Stack<RefAsValueType<Node>>, Enumerator>.TryTake(this, out _stack)) 109_stack = SecureObjectPool<Stack<RefAsValueType<Node>>, Enumerator>.PrepNew(this, new Stack<RefAsValueType<Node>>(root.Height)); 148if (_stack != null && _stack.TryUse(ref this, out Stack<RefAsValueType<Node>>? stack)) 151SecureObjectPool<Stack<RefAsValueType<Node>>, Enumerator>.TryAdd(this, _stack!); 168Stack<RefAsValueType<ImmutableList<T>.Node>> stack = _stack.Use(ref this); 171Node n = stack.Pop().Value; 202Stack<RefAsValueType<ImmutableList<T>.Node>> stack = _stack.Use(ref this); 205ImmutableList<T>.Node node = _root; 211stack.Push(new RefAsValueType<Node>(node)); 223stack.Push(new RefAsValueType<Node>(node)); 230private Node? NextBranch(Node node) => _reversed ? node.Left : node.Right; 235private Node? PreviousBranch(Node node) => _reversed ? node.Right : node.Left; 270private void PushNext(Node node) 276Stack<RefAsValueType<ImmutableList<T>.Node>> stack = _stack.Use(ref this); 279stack.Push(new RefAsValueType<Node>(node));

22internal static readonly Node EmptyNode = new Node(); 57private Node? _left; 62private Node? _right; 65/// Initializes a new instance of the <see cref="ImmutableList{T}.Node"/> class 75/// Initializes a new instance of the <see cref="ImmutableList{T}.Node"/> class 82private Node(T key, Node left, Node right, bool frozen = false) 121public Node? Left => _left; 131public Node? Right => _right; 263internal static Node NodeTreeFromList(IOrderedCollection<T> items, int start, int length) 276Node left = NodeTreeFromList(items, start, leftCount); 277Node right = NodeTreeFromList(items, start + leftCount + 1, rightCount); 286internal static Node NodeTreeFromList(ReadOnlySpan<T> items) 295Node left = NodeTreeFromList(items.Slice(0, leftCount)); 296Node right = NodeTreeFromList(items.Slice(leftCount + 1)); 305internal Node Add(T key) 312Node newRight = _right!.Add(key); 313Node result = this.MutateRight(newRight); 323internal Node Insert(int index, T key) 334Node newLeft = _left.Insert(index, key); 335Node result = this.MutateLeft(newLeft); 340Node newRight = _right!.Insert(index - _left._count - 1, key); 341Node result = this.MutateRight(newRight); 351internal Node AddRange(IEnumerable<T> keys) 360Node newRight = _right!.AddRange(keys); 361Node result = this.MutateRight(newRight); 370internal Node AddRange(ReadOnlySpan<T> keys) 377Node newRight = _right!.AddRange(keys); 378Node result = this.MutateRight(newRight); 388internal Node InsertRange(int index, IEnumerable<T> keys) 398Node result; 401Node newLeft = _left.InsertRange(index, keys); 406Node newRight = _right!.InsertRange(index - _left._count - 1, keys); 418internal Node RemoveAt(int index) 423Node result; 445ImmutableList<T>.Node successor = _right; 451ImmutableList<T>.Node newRight = _right.RemoveAt(0); 457ImmutableList<T>.Node newLeft = _left.RemoveAt(index); 462ImmutableList<T>.Node newRight = _right.RemoveAt(index - _left._count - 1); 480internal Node RemoveAll(Predicate<T> match) 484ImmutableList<T>.Node result = this; 518internal Node ReplaceAt(int index, T value) 523Node result; 531ImmutableList<T>.Node newLeft = _left.ReplaceAt(index, value); 536ImmutableList<T>.Node newRight = _right!.ReplaceAt(index - _left._count - 1, value); 547internal Node Reverse() => this.Reverse(0, this.Count); 555internal Node Reverse(int index, int count) 561Node result = this; 582internal Node Sort() => this.Sort(Comparer<T>.Default); 592internal Node Sort(Comparison<T> comparison) 612internal Node Sort(IComparer<T>? comparer) => this.Sort(0, this.Count, comparer); 629internal Node Sort(int index, int count, IComparer<T>? comparer) 955internal ImmutableList<TOutput>.Node ConvertAll<TOutput>(Func<T, TOutput> converter) 957ImmutableList<TOutput>.Node root = ImmutableList<TOutput>.Node.EmptyNode; 1297private Node RotateLeft() 1309private Node RotateRight() 1321private Node DoubleLeft() 1328Node right = _right; 1329Node rightLeft = right._left; 1339private Node DoubleRight() 1346Node left = _left; 1347Node leftRight = left._right; 1396private Node Balance() => this.IsLeftHeavy ? this.BalanceLeft() : this.BalanceRight(); 1402private Node BalanceLeft() 1414private Node BalanceRight() 1430private Node BalanceMany() 1432Node tree = this; 1462private Node MutateBoth(Node left, Node right) 1488private Node MutateLeft(Node left) 1512private Node MutateRight(Node right) 1537private static byte ParentHeight(Node left, Node right) => checked((byte)(1 + Math.Max(left._height, right._height))); 1545private static int ParentCount(Node left, Node right) => 1 + left._count + right._count; 1553private Node MutateKey(T key) 1573private static Node CreateRange(IEnumerable<T> keys) 1590private static Node CreateLeaf(T key) => new Node(key, left: EmptyNode, right: EmptyNode); 1606private static bool Contains(Node node, T value, IEqualityComparer<T> equalityComparer) => !node.IsEmpty && (equalityComparer.Equals(value, node._key) || Contains(node._left!, value, equalityComparer) || Contains(node._right!, value, equalityComparer));