22internal static readonly Node EmptyNode = new Node(); 258return new Node(items[start + leftCount], left, right, true); 277return new Node(items[leftCount], left, right, frozen: true); 1450return new Node(_key, left, right); 1475return new Node(_key, left, _right!); 1499return new Node(_key, _left!, right); 1539return new Node(key, _left!, _right!); 1570private 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 191this.Root = ImmutableList<T>.Node.EmptyNode; 329return ImmutableList<T>.WrapNode(Node.NodeTreeFromList(this, index, count));

29private readonly Node _root; 34internal ImmutableList() => _root = Node.EmptyNode; 40private ImmutableList(Node root) 209ImmutableList<T>.Node result = _root.Add(value); 226ImmutableList<T>.Node result = _root.AddRange(items); 243return new ImmutableList<T>(Node.NodeTreeFromList(items)); 273ImmutableList<T>.Node result = _root.InsertRange(index, items); 303ImmutableList<T>.Node result = _root; 345ImmutableList<T>.Node result = _root; 364ImmutableList<T>.Node result = _root.RemoveAt(index); 559return this.Wrap(Node.NodeTreeFromList(this, index, count)); 1098private static ImmutableList<T> WrapNode(Node root) 1149private ImmutableList<T> Wrap(Node root) 1188Node 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; 126public Node? Right => _right; 243internal static Node NodeTreeFromList(IReadOnlyList<T> items, int start, int length) 256Node left = NodeTreeFromList(items, start, leftCount); 257Node right = NodeTreeFromList(items, start + leftCount + 1, rightCount); 266internal static Node NodeTreeFromList(ReadOnlySpan<T> items) 275Node left = NodeTreeFromList(items.Slice(0, leftCount)); 276Node right = NodeTreeFromList(items.Slice(leftCount + 1)); 285internal Node Add(T key) 292Node newRight = _right!.Add(key); 293Node result = this.MutateRight(newRight); 303internal Node Insert(int index, T key) 314Node newLeft = _left.Insert(index, key); 315Node result = this.MutateLeft(newLeft); 320Node newRight = _right!.Insert(index - _left._count - 1, key); 321Node result = this.MutateRight(newRight); 331internal Node AddRange(IEnumerable<T> keys) 340Node newRight = _right!.AddRange(keys); 341Node result = this.MutateRight(newRight); 350internal Node AddRange(ReadOnlySpan<T> keys) 357Node newRight = _right!.AddRange(keys); 358Node result = this.MutateRight(newRight); 368internal Node InsertRange(int index, IEnumerable<T> keys) 378Node result; 381Node newLeft = _left.InsertRange(index, keys); 386Node newRight = _right!.InsertRange(index - _left._count - 1, keys); 398internal Node RemoveAt(int index) 403Node result; 425ImmutableList<T>.Node successor = _right; 431ImmutableList<T>.Node newRight = _right.RemoveAt(0); 437ImmutableList<T>.Node newLeft = _left.RemoveAt(index); 442ImmutableList<T>.Node newRight = _right.RemoveAt(index - _left._count - 1); 460internal Node RemoveAll(Predicate<T> match) 464ImmutableList<T>.Node result = this; 498internal Node ReplaceAt(int index, T value) 503Node result; 511ImmutableList<T>.Node newLeft = _left.ReplaceAt(index, value); 516ImmutableList<T>.Node newRight = _right!.ReplaceAt(index - _left._count - 1, value); 527internal Node Reverse() => this.Reverse(0, this.Count); 535internal Node Reverse(int index, int count) 541Node result = this; 562internal Node Sort() => this.Sort(Comparer<T>.Default); 572internal Node Sort(Comparison<T> comparison) 592internal Node Sort(IComparer<T>? comparer) => this.Sort(0, this.Count, comparer); 609internal Node Sort(int index, int count, IComparer<T>? comparer) 935internal ImmutableList<TOutput>.Node ConvertAll<TOutput>(Func<T, TOutput> converter) 937ImmutableList<TOutput>.Node root = ImmutableList<TOutput>.Node.EmptyNode; 1277private Node RotateLeft() 1289private Node RotateRight() 1301private Node DoubleLeft() 1308Node right = _right; 1309Node rightLeft = right._left; 1319private Node DoubleRight() 1326Node left = _left; 1327Node leftRight = left._right; 1376private Node Balance() => this.IsLeftHeavy ? this.BalanceLeft() : this.BalanceRight(); 1382private Node BalanceLeft() 1394private Node BalanceRight() 1410private Node BalanceMany() 1412Node tree = this; 1442private Node MutateBoth(Node left, Node right) 1468private Node MutateLeft(Node left) 1492private Node MutateRight(Node right) 1517private static byte ParentHeight(Node left, Node right) => checked((byte)(1 + Math.Max(left._height, right._height))); 1525private static int ParentCount(Node left, Node right) => 1 + left._count + right._count; 1533private Node MutateKey(T key) 1553private static Node CreateRange(IEnumerable<T> keys) 1570private static Node CreateLeaf(T key) => new Node(key, left: EmptyNode, right: EmptyNode); 1586private 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));