11 instantiations of Node
System.Collections (11)
System\Collections\Generic\SortedSet.cs (11)
308
root = new
Node
(item, NodeColor.Black);
357
Node node = new
Node
(item, NodeColor.Red);
945
root = new
Node
(arr[startIndex], NodeColor.Black);
952
root = new
Node
(arr[startIndex], NodeColor.Black);
953
root.Right = new
Node
(arr[endIndex], NodeColor.Black);
961
root = new
Node
(arr[startIndex + 1], NodeColor.Black);
962
root.Left = new
Node
(arr[startIndex], NodeColor.Black);
963
root.Right = new
Node
(arr[endIndex], NodeColor.Black);
971
root = new
Node
(arr[midpt], NodeColor.Black);
974
ConstructRootFromSortedArray(arr, midpt + 2, endIndex, new
Node
(arr[midpt + 1], NodeColor.Red)) :
1684
public Node ShallowClone() => new
Node
(Item, Color);
107 references to Node
System.Collections (107)
System\Collections\Generic\SortedDictionary.cs (11)
66
TreeSet<KeyValuePair<TKey, TValue>>.
Node
? node = _set.FindNode(keyValuePair);
84
TreeSet<KeyValuePair<TKey, TValue>>.
Node
? node = _set.FindNode(keyValuePair);
112
TreeSet<KeyValuePair<TKey, TValue>>.
Node
? node = _set.FindNode(new KeyValuePair<TKey, TValue>(key, default(TValue)!));
124
TreeSet<KeyValuePair<TKey, TValue>>.
Node
? node = _set.FindNode(new KeyValuePair<TKey, TValue>(key, default(TValue)!));
213
_set.InOrderTreeWalk(delegate (TreeSet<KeyValuePair<TKey, TValue>>.
Node
node)
226
_set.InOrderTreeWalk(delegate (TreeSet<KeyValuePair<TKey, TValue>>.
Node
node)
261
TreeSet<KeyValuePair<TKey, TValue>>.
Node
? node = _set.FindNode(new KeyValuePair<TKey, TValue>(key, default(TValue)!));
545
_dictionary._set.InOrderTreeWalk(delegate (TreeSet<KeyValuePair<TKey, TValue>>.
Node
node) { array[index++] = node.Item.Key; return true; });
578
_dictionary._set.InOrderTreeWalk(delegate (TreeSet<KeyValuePair<TKey, TValue>>.
Node
node) { objects[index++] = node.Item.Key; return true; });
706
_dictionary._set.InOrderTreeWalk(delegate (TreeSet<KeyValuePair<TKey, TValue>>.
Node
node) { array[index++] = node.Item.Value; return true; });
739
_dictionary._set.InOrderTreeWalk(delegate (TreeSet<KeyValuePair<TKey, TValue>>.
Node
node) { objects[index++] = node.Item.Value; return true; });
System\Collections\Generic\SortedSet.cs (86)
35
internal delegate bool TreeWalkPredicate<T>(SortedSet<T>.
Node
node);
53
private
Node
? root;
194
var stack = new Stack<
Node
>(2 * (int)Log2(Count + 1));
195
Node
? current = root;
211
Node
? node = current.Right;
237
var processQueue = new Queue<
Node
>();
240
Node
current;
317
Node
? current = root;
318
Node
? parent = null;
319
Node
? grandParent = null;
320
Node
? greatGrandParent = null;
343
if (
Node
.IsNonNullRed(parent))
357
Node
node = new Node(item, NodeColor.Red);
400
Node
? current = root;
401
Node
? parent = null;
402
Node
? grandParent = null;
403
Node
? match = null;
404
Node
? parentOfMatch = null;
418
Node
sibling = parent.GetSibling(current);
448
Debug.Assert(
Node
.IsNonNullBlack(sibling));
458
Node
newGrandParent = parent.Rotate(parent.GetRotation(current, sibling))!;
607
private void InsertionBalance(
Node
current, ref
Node
parent,
Node
grandParent,
Node
greatGrandParent)
615
Node
newChildOfGreatGrandParent;
642
private void ReplaceChildOrRoot(
Node
? parent,
Node
child,
Node
newChild)
657
private void ReplaceNode(
Node
match,
Node
parentOfMatch,
Node
successor,
Node
parentOfSuccessor)
690
internal virtual
Node
? FindNode(T item)
692
Node
? current = root;
723
Node
? current = root;
740
internal
Node
? FindRange(T? from, T? to) => FindRange(from, to, lowerBoundActive: true, upperBoundActive: true);
742
internal
Node
? FindRange(T? from, T? to, bool lowerBoundActive, bool upperBoundActive)
744
Node
? current = root;
917
private static
Node
? ConstructRootFromSortedArray(T[] arr, int startIndex, int endIndex,
Node
? redNode)
938
Node
root;
1468
Node
current = root;
1489
Node
current = root;
1599
public static bool IsNonNullBlack(
Node
? node) => node != null && node.IsBlack;
1601
public static bool IsNonNullRed(
Node
? node) => node != null && node.IsRed;
1603
public static bool IsNullOrBlack(
Node
? node) => node == null || node.IsBlack;
1607
public
Node
? Left { get; set; }
1609
public
Node
? Right { get; set; }
1625
public
Node
DeepClone(int count)
1630
Node
newRoot = ShallowClone();
1632
var pendingNodes = new Stack<(
Node
source,
Node
target)>(2 * Log2(count) + 2);
1637
Node
clonedNode;
1639
if (next.source.Left is
Node
left)
1646
if (next.source.Right is
Node
right)
1660
public TreeRotation GetRotation(
Node
current,
Node
sibling)
1676
public
Node
GetSibling(
Node
node)
1684
public
Node
ShallowClone() => new Node(Item, Color);
1699
public
Node
? Rotate(TreeRotation rotation)
1701
Node
removeRed;
1729
public
Node
RotateLeft()
1731
Node
child = Right!;
1740
public
Node
RotateLeftRight()
1742
Node
child = Left!;
1743
Node
grandChild = child.Right!;
1755
public
Node
RotateRight()
1757
Node
child = Left!;
1766
public
Node
RotateRightLeft()
1768
Node
child = Right!;
1769
Node
grandChild = child.Left!;
1798
public void ReplaceChild(
Node
child,
Node
newChild)
1817
private bool HasChild(
Node
child) => child == Left || child == Right;
1819
private bool HasChildren(
Node
child1,
Node
child2)
1834
private readonly Stack<
Node
> _stack;
1835
private
Node
? _current;
1851
_stack = new Stack<
Node
>(2 * (int)Log2(set.TotalCount() + 1));
1871
Node
? node = _tree.root;
1872
Node
? next, other;
1910
Node
? node = (_reverse ? _current.Left : _current.Right);
1911
Node
? next, other;
2000
Node
? node = FindNode(equalValue);
System\Collections\Generic\SortedSet.TreeSubSet.cs (10)
129
Node
? current = root;
160
Node
? current = root;
196
Stack<
Node
> stack = new Stack<
Node
>(2 * (int)SortedSet<T>.Log2(count + 1)); // this is not exactly right if count is out of date, but the stack can grow
197
Node
? current = root;
223
Node
? node = current.Right;
253
Queue<
Node
> processQueue = new Queue<
Node
>();
255
Node
current;
276
internal override SortedSet<T>.
Node
? FindNode(T item)