From cee712105850ac3385cd0091a923438167433f9f Mon Sep 17 00:00:00 2001
From: TSR Berry <20988865+TSRBerry@users.noreply.github.com>
Date: Sat, 8 Apr 2023 01:22:00 +0200
Subject: Move solution and projects to src
---
Ryujinx.Common/Collections/IntervalTree.cs | 499 -----------------
.../Collections/IntrusiveRedBlackTree.cs | 285 ----------
.../Collections/IntrusiveRedBlackTreeImpl.cs | 354 ------------
.../Collections/IntrusiveRedBlackTreeNode.cs | 16 -
Ryujinx.Common/Collections/TreeDictionary.cs | 617 ---------------------
5 files changed, 1771 deletions(-)
delete mode 100644 Ryujinx.Common/Collections/IntervalTree.cs
delete mode 100644 Ryujinx.Common/Collections/IntrusiveRedBlackTree.cs
delete mode 100644 Ryujinx.Common/Collections/IntrusiveRedBlackTreeImpl.cs
delete mode 100644 Ryujinx.Common/Collections/IntrusiveRedBlackTreeNode.cs
delete mode 100644 Ryujinx.Common/Collections/TreeDictionary.cs
(limited to 'Ryujinx.Common/Collections')
diff --git a/Ryujinx.Common/Collections/IntervalTree.cs b/Ryujinx.Common/Collections/IntervalTree.cs
deleted file mode 100644
index b5188cc7..00000000
--- a/Ryujinx.Common/Collections/IntervalTree.cs
+++ /dev/null
@@ -1,499 +0,0 @@
-using System;
-using System.Collections.Generic;
-using System.Linq;
-
-namespace Ryujinx.Common.Collections
-{
- ///
- /// An Augmented Interval Tree based off of the "TreeDictionary"'s Red-Black Tree. Allows fast overlap checking of ranges.
- ///
- /// Key
- /// Value
- public class IntervalTree : IntrusiveRedBlackTreeImpl> where K : IComparable
- {
- private const int ArrayGrowthSize = 32;
-
- #region Public Methods
-
- ///
- /// Gets the values of the interval whose key is .
- ///
- /// Key of the node value to get
- /// Overlaps array to place results in
- /// Number of values found
- /// is null
- public int Get(K key, ref V[] overlaps)
- {
- ArgumentNullException.ThrowIfNull(key);
-
- IntervalTreeNode node = GetNode(key);
-
- if (node == null)
- {
- return 0;
- }
-
- if (node.Values.Count > overlaps.Length)
- {
- Array.Resize(ref overlaps, node.Values.Count);
- }
-
- int overlapsCount = 0;
- foreach (RangeNode value in node.Values)
- {
- overlaps[overlapsCount++] = value.Value;
- }
-
- return overlapsCount;
- }
-
- ///
- /// Returns the values of the intervals whose start and end keys overlap the given range.
- ///
- /// Start of the range
- /// End of the range
- /// Overlaps array to place results in
- /// Index to start writing results into the array. Defaults to 0
- /// Number of values found
- /// or is null
- public int Get(K start, K end, ref V[] overlaps, int overlapCount = 0)
- {
- ArgumentNullException.ThrowIfNull(start);
- ArgumentNullException.ThrowIfNull(end);
-
- GetValues(Root, start, end, ref overlaps, ref overlapCount);
-
- return overlapCount;
- }
-
- ///
- /// Adds a new interval into the tree whose start is , end is and value is .
- ///
- /// Start of the range to add
- /// End of the range to insert
- /// Value to add
- /// , or are null
- public void Add(K start, K end, V value)
- {
- ArgumentNullException.ThrowIfNull(start);
- ArgumentNullException.ThrowIfNull(end);
- ArgumentNullException.ThrowIfNull(value);
-
- Insert(start, end, value);
- }
-
- ///
- /// Removes the given from the tree, searching for it with .
- ///
- /// Key of the node to remove
- /// Value to remove
- /// is null
- /// Number of deleted values
- public int Remove(K key, V value)
- {
- ArgumentNullException.ThrowIfNull(key);
-
- int removed = Delete(key, value);
-
- Count -= removed;
-
- return removed;
- }
-
- ///
- /// Adds all the nodes in the dictionary into .
- ///
- /// A list of all RangeNodes sorted by Key Order
- public List> AsList()
- {
- List> list = new List>();
-
- AddToList(Root, list);
-
- return list;
- }
-
- #endregion
-
- #region Private Methods (BST)
-
- ///
- /// Adds all RangeNodes that are children of or contained within into , in Key Order.
- ///
- /// The node to search for RangeNodes within
- /// The list to add RangeNodes to
- private void AddToList(IntervalTreeNode node, List> list)
- {
- if (node == null)
- {
- return;
- }
-
- AddToList(node.Left, list);
-
- list.AddRange(node.Values);
-
- AddToList(node.Right, list);
- }
-
- ///
- /// Retrieve the node reference whose key is , or null if no such node exists.
- ///
- /// Key of the node to get
- /// Node reference in the tree
- /// is null
- private IntervalTreeNode GetNode(K key)
- {
- ArgumentNullException.ThrowIfNull(key);
-
- IntervalTreeNode node = Root;
- while (node != null)
- {
- int cmp = key.CompareTo(node.Start);
- if (cmp < 0)
- {
- node = node.Left;
- }
- else if (cmp > 0)
- {
- node = node.Right;
- }
- else
- {
- return node;
- }
- }
- return null;
- }
-
- ///
- /// Retrieve all values that overlap the given start and end keys.
- ///
- /// Start of the range
- /// End of the range
- /// Overlaps array to place results in
- /// Overlaps count to update
- private void GetValues(IntervalTreeNode node, K start, K end, ref V[] overlaps, ref int overlapCount)
- {
- if (node == null || start.CompareTo(node.Max) >= 0)
- {
- return;
- }
-
- GetValues(node.Left, start, end, ref overlaps, ref overlapCount);
-
- bool endsOnRight = end.CompareTo(node.Start) > 0;
- if (endsOnRight)
- {
- if (start.CompareTo(node.End) < 0)
- {
- // Contains this node. Add overlaps to list.
- foreach (RangeNode overlap in node.Values)
- {
- if (start.CompareTo(overlap.End) < 0)
- {
- if (overlaps.Length >= overlapCount)
- {
- Array.Resize(ref overlaps, overlapCount + ArrayGrowthSize);
- }
-
- overlaps[overlapCount++] = overlap.Value;
- }
- }
- }
-
- GetValues(node.Right, start, end, ref overlaps, ref overlapCount);
- }
- }
-
- ///
- /// Inserts a new node into the tree with a given , and .
- ///
- /// Start of the range to insert
- /// End of the range to insert
- /// Value to insert
- private void Insert(K start, K end, V value)
- {
- IntervalTreeNode newNode = BSTInsert(start, end, value);
- RestoreBalanceAfterInsertion(newNode);
- }
-
- ///
- /// Propagate an increase in max value starting at the given node, heading up the tree.
- /// This should only be called if the max increases - not for rebalancing or removals.
- ///
- /// The node to start propagating from
- private void PropagateIncrease(IntervalTreeNode node)
- {
- K max = node.Max;
- IntervalTreeNode ptr = node;
-
- while ((ptr = ptr.Parent) != null)
- {
- if (max.CompareTo(ptr.Max) > 0)
- {
- ptr.Max = max;
- }
- else
- {
- break;
- }
- }
- }
-
- ///
- /// Propagate recalculating max value starting at the given node, heading up the tree.
- /// This fully recalculates the max value from all children when there is potential for it to decrease.
- ///
- /// The node to start propagating from
- private void PropagateFull(IntervalTreeNode node)
- {
- IntervalTreeNode ptr = node;
-
- do
- {
- K max = ptr.End;
-
- if (ptr.Left != null && ptr.Left.Max.CompareTo(max) > 0)
- {
- max = ptr.Left.Max;
- }
-
- if (ptr.Right != null && ptr.Right.Max.CompareTo(max) > 0)
- {
- max = ptr.Right.Max;
- }
-
- ptr.Max = max;
- } while ((ptr = ptr.Parent) != null);
- }
-
- ///
- /// Insertion Mechanism for the interval tree. Similar to a BST insert, with the start of the range as the key.
- /// Iterates the tree starting from the root and inserts a new node where all children in the left subtree are less than , and all children in the right subtree are greater than .
- /// Each node can contain multiple values, and has an end address which is the maximum of all those values.
- /// Post insertion, the "max" value of the node and all parents are updated.
- ///
- /// Start of the range to insert
- /// End of the range to insert
- /// Value to insert
- /// The inserted Node
- private IntervalTreeNode BSTInsert(K start, K end, V value)
- {
- IntervalTreeNode parent = null;
- IntervalTreeNode node = Root;
-
- while (node != null)
- {
- parent = node;
- int cmp = start.CompareTo(node.Start);
- if (cmp < 0)
- {
- node = node.Left;
- }
- else if (cmp > 0)
- {
- node = node.Right;
- }
- else
- {
- node.Values.Add(new RangeNode(start, end, value));
-
- if (end.CompareTo(node.End) > 0)
- {
- node.End = end;
- if (end.CompareTo(node.Max) > 0)
- {
- node.Max = end;
- PropagateIncrease(node);
- }
- }
-
- Count++;
- return node;
- }
- }
- IntervalTreeNode newNode = new IntervalTreeNode(start, end, value, parent);
- if (newNode.Parent == null)
- {
- Root = newNode;
- }
- else if (start.CompareTo(parent.Start) < 0)
- {
- parent.Left = newNode;
- }
- else
- {
- parent.Right = newNode;
- }
-
- PropagateIncrease(newNode);
- Count++;
- return newNode;
- }
-
- ///
- /// Removes instances of from the dictionary after searching for it with .
- ///
- /// Key to search for
- /// Value to delete
- /// Number of deleted values
- private int Delete(K key, V value)
- {
- IntervalTreeNode nodeToDelete = GetNode(key);
-
- if (nodeToDelete == null)
- {
- return 0;
- }
-
- int removed = nodeToDelete.Values.RemoveAll(node => node.Value.Equals(value));
-
- if (nodeToDelete.Values.Count > 0)
- {
- if (removed > 0)
- {
- nodeToDelete.End = nodeToDelete.Values.Max(node => node.End);
-
- // Recalculate max from children and new end.
- PropagateFull(nodeToDelete);
- }
-
- return removed;
- }
-
- IntervalTreeNode replacementNode;
-
- if (LeftOf(nodeToDelete) == null || RightOf(nodeToDelete) == null)
- {
- replacementNode = nodeToDelete;
- }
- else
- {
- replacementNode = PredecessorOf(nodeToDelete);
- }
-
- IntervalTreeNode tmp = LeftOf(replacementNode) ?? RightOf(replacementNode);
-
- if (tmp != null)
- {
- tmp.Parent = ParentOf(replacementNode);
- }
-
- if (ParentOf(replacementNode) == null)
- {
- Root = tmp;
- }
- else if (replacementNode == LeftOf(ParentOf(replacementNode)))
- {
- ParentOf(replacementNode).Left = tmp;
- }
- else
- {
- ParentOf(replacementNode).Right = tmp;
- }
-
- if (replacementNode != nodeToDelete)
- {
- nodeToDelete.Start = replacementNode.Start;
- nodeToDelete.Values = replacementNode.Values;
- nodeToDelete.End = replacementNode.End;
- nodeToDelete.Max = replacementNode.Max;
- }
-
- PropagateFull(replacementNode);
-
- if (tmp != null && ColorOf(replacementNode) == Black)
- {
- RestoreBalanceAfterRemoval(tmp);
- }
-
- return removed;
- }
-
- #endregion
-
- protected override void RotateLeft(IntervalTreeNode node)
- {
- if (node != null)
- {
- base.RotateLeft(node);
-
- PropagateFull(node);
- }
- }
-
- protected override void RotateRight(IntervalTreeNode node)
- {
- if (node != null)
- {
- base.RotateRight(node);
-
- PropagateFull(node);
- }
- }
-
- public bool ContainsKey(K key)
- {
- ArgumentNullException.ThrowIfNull(key);
-
- return GetNode(key) != null;
- }
- }
-
- ///
- /// Represents a value and its start and end keys.
- ///
- ///
- ///
- public readonly struct RangeNode
- {
- public readonly K Start;
- public readonly K End;
- public readonly V Value;
-
- public RangeNode(K start, K end, V value)
- {
- Start = start;
- End = end;
- Value = value;
- }
- }
-
- ///
- /// Represents a node in the IntervalTree which contains start and end keys of type K, and a value of generic type V.
- ///
- /// Key type of the node
- /// Value type of the node
- public class IntervalTreeNode : IntrusiveRedBlackTreeNode>
- {
- ///
- /// The start of the range.
- ///
- internal K Start;
-
- ///
- /// The end of the range - maximum of all in the Values list.
- ///
- internal K End;
-
- ///
- /// The maximum end value of this node and all its children.
- ///
- internal K Max;
-
- ///
- /// Values contained on the node that shares a common Start value.
- ///
- internal List> Values;
-
- internal IntervalTreeNode(K start, K end, V value, IntervalTreeNode parent)
- {
- Start = start;
- End = end;
- Max = end;
- Values = new List> { new RangeNode(start, end, value) };
- Parent = parent;
- }
- }
-}
diff --git a/Ryujinx.Common/Collections/IntrusiveRedBlackTree.cs b/Ryujinx.Common/Collections/IntrusiveRedBlackTree.cs
deleted file mode 100644
index 0063d91e..00000000
--- a/Ryujinx.Common/Collections/IntrusiveRedBlackTree.cs
+++ /dev/null
@@ -1,285 +0,0 @@
-using System;
-
-namespace Ryujinx.Common.Collections
-{
- ///
- /// Tree that provides the ability for O(logN) lookups for keys that exist in the tree, and O(logN) lookups for keys immediately greater than or less than a specified key.
- ///
- /// Derived node type
- public class IntrusiveRedBlackTree : IntrusiveRedBlackTreeImpl where T : IntrusiveRedBlackTreeNode, IComparable
- {
- #region Public Methods
-
- ///
- /// Adds a new node into the tree.
- ///
- /// Node to be added
- /// is null
- public void Add(T node)
- {
- ArgumentNullException.ThrowIfNull(node);
-
- Insert(node);
- }
-
- ///
- /// Removes a node from the tree.
- ///
- /// Note to be removed
- /// is null
- public void Remove(T node)
- {
- ArgumentNullException.ThrowIfNull(node);
-
- if (Delete(node) != null)
- {
- Count--;
- }
- }
-
- ///
- /// Retrieve the node that is considered equal to the specified node by the comparator.
- ///
- /// Node to compare with
- /// Node that is equal to
- /// is null
- public T GetNode(T searchNode)
- {
- ArgumentNullException.ThrowIfNull(searchNode);
-
- T node = Root;
- while (node != null)
- {
- int cmp = searchNode.CompareTo(node);
- if (cmp < 0)
- {
- node = node.Left;
- }
- else if (cmp > 0)
- {
- node = node.Right;
- }
- else
- {
- return node;
- }
- }
- return null;
- }
-
- #endregion
-
- #region Private Methods (BST)
-
- ///
- /// Inserts a new node into the tree.
- ///
- /// Node to be inserted
- private void Insert(T node)
- {
- T newNode = BSTInsert(node);
- RestoreBalanceAfterInsertion(newNode);
- }
-
- ///
- /// Insertion Mechanism for a Binary Search Tree (BST).
- ///
- /// Iterates the tree starting from the root and inserts a new node
- /// where all children in the left subtree are less than ,
- /// and all children in the right subtree are greater than .
- ///
- /// Node to be inserted
- /// The inserted Node
- private T BSTInsert(T newNode)
- {
- T parent = null;
- T node = Root;
-
- while (node != null)
- {
- parent = node;
- int cmp = newNode.CompareTo(node);
- if (cmp < 0)
- {
- node = node.Left;
- }
- else if (cmp > 0)
- {
- node = node.Right;
- }
- else
- {
- return node;
- }
- }
- newNode.Parent = parent;
- if (parent == null)
- {
- Root = newNode;
- }
- else if (newNode.CompareTo(parent) < 0)
- {
- parent.Left = newNode;
- }
- else
- {
- parent.Right = newNode;
- }
- Count++;
- return newNode;
- }
-
- ///
- /// Removes from the tree, if it exists.
- ///
- /// Node to be removed
- /// The deleted Node
- private T Delete(T nodeToDelete)
- {
- if (nodeToDelete == null)
- {
- return null;
- }
-
- T old = nodeToDelete;
- T child;
- T parent;
- bool color;
-
- if (LeftOf(nodeToDelete) == null)
- {
- child = RightOf(nodeToDelete);
- }
- else if (RightOf(nodeToDelete) == null)
- {
- child = LeftOf(nodeToDelete);
- }
- else
- {
- T element = Minimum(RightOf(nodeToDelete));
-
- child = RightOf(element);
- parent = ParentOf(element);
- color = ColorOf(element);
-
- if (child != null)
- {
- child.Parent = parent;
- }
-
- if (parent == null)
- {
- Root = child;
- }
- else if (element == LeftOf(parent))
- {
- parent.Left = child;
- }
- else
- {
- parent.Right = child;
- }
-
- if (ParentOf(element) == old)
- {
- parent = element;
- }
-
- element.Color = old.Color;
- element.Left = old.Left;
- element.Right = old.Right;
- element.Parent = old.Parent;
-
- if (ParentOf(old) == null)
- {
- Root = element;
- }
- else if (old == LeftOf(ParentOf(old)))
- {
- ParentOf(old).Left = element;
- }
- else
- {
- ParentOf(old).Right = element;
- }
-
- LeftOf(old).Parent = element;
-
- if (RightOf(old) != null)
- {
- RightOf(old).Parent = element;
- }
-
- if (child != null && color == Black)
- {
- RestoreBalanceAfterRemoval(child);
- }
-
- return old;
- }
-
- parent = ParentOf(nodeToDelete);
- color = ColorOf(nodeToDelete);
-
- if (child != null)
- {
- child.Parent = parent;
- }
-
- if (parent == null)
- {
- Root = child;
- }
- else if (nodeToDelete == LeftOf(parent))
- {
- parent.Left = child;
- }
- else
- {
- parent.Right = child;
- }
-
- if (child != null && color == Black)
- {
- RestoreBalanceAfterRemoval(child);
- }
-
- return old;
- }
-
- #endregion
- }
-
- public static class IntrusiveRedBlackTreeExtensions
- {
- ///
- /// Retrieve the node that is considered equal to the key by the comparator.
- ///
- /// Tree to search at
- /// Key of the node to be found
- /// Node that is equal to
- public static N GetNodeByKey(this IntrusiveRedBlackTree tree, K key)
- where N : IntrusiveRedBlackTreeNode, IComparable, IComparable
- where K : struct
- {
- N node = tree.RootNode;
- while (node != null)
- {
- int cmp = node.CompareTo(key);
- if (cmp < 0)
- {
- node = node.Right;
- }
- else if (cmp > 0)
- {
- node = node.Left;
- }
- else
- {
- return node;
- }
- }
- return null;
- }
- }
-}
diff --git a/Ryujinx.Common/Collections/IntrusiveRedBlackTreeImpl.cs b/Ryujinx.Common/Collections/IntrusiveRedBlackTreeImpl.cs
deleted file mode 100644
index bcb2e2a2..00000000
--- a/Ryujinx.Common/Collections/IntrusiveRedBlackTreeImpl.cs
+++ /dev/null
@@ -1,354 +0,0 @@
-using System;
-
-namespace Ryujinx.Common.Collections
-{
- ///
- /// Tree that provides the ability for O(logN) lookups for keys that exist in the tree, and O(logN) lookups for keys immediately greater than or less than a specified key.
- ///
- /// Derived node type
- public class IntrusiveRedBlackTreeImpl where T : IntrusiveRedBlackTreeNode
- {
- protected const bool Black = true;
- protected const bool Red = false;
- protected T Root = null;
-
- internal T RootNode => Root;
-
- ///
- /// Number of nodes on the tree.
- ///
- public int Count { get; protected set; }
-
- ///
- /// Removes all nodes on the tree.
- ///
- public void Clear()
- {
- Root = null;
- Count = 0;
- }
-
- ///
- /// Finds the node whose key is immediately greater than .
- ///
- /// Node to find the successor of
- /// Successor of
- internal static T SuccessorOf(T node)
- {
- if (node.Right != null)
- {
- return Minimum(node.Right);
- }
- T parent = node.Parent;
- while (parent != null && node == parent.Right)
- {
- node = parent;
- parent = parent.Parent;
- }
- return parent;
- }
-
- ///
- /// Finds the node whose key is immediately less than .
- ///
- /// Node to find the predecessor of
- /// Predecessor of
- internal static T PredecessorOf(T node)
- {
- if (node.Left != null)
- {
- return Maximum(node.Left);
- }
- T parent = node.Parent;
- while (parent != null && node == parent.Left)
- {
- node = parent;
- parent = parent.Parent;
- }
- return parent;
- }
-
- ///
- /// Returns the node with the largest key where is considered the root node.
- ///
- /// Root node
- /// Node with the maximum key in the tree of
- protected static T Maximum(T node)
- {
- T tmp = node;
- while (tmp.Right != null)
- {
- tmp = tmp.Right;
- }
-
- return tmp;
- }
-
- ///
- /// Returns the node with the smallest key where is considered the root node.
- ///
- /// Root node
- /// Node with the minimum key in the tree of
- /// is null
- protected static T Minimum(T node)
- {
- ArgumentNullException.ThrowIfNull(node);
-
- T tmp = node;
- while (tmp.Left != null)
- {
- tmp = tmp.Left;
- }
-
- return tmp;
- }
-
- protected void RestoreBalanceAfterRemoval(T balanceNode)
- {
- T ptr = balanceNode;
-
- while (ptr != Root && ColorOf(ptr) == Black)
- {
- if (ptr == LeftOf(ParentOf(ptr)))
- {
- T sibling = RightOf(ParentOf(ptr));
-
- if (ColorOf(sibling) == Red)
- {
- SetColor(sibling, Black);
- SetColor(ParentOf(ptr), Red);
- RotateLeft(ParentOf(ptr));
- sibling = RightOf(ParentOf(ptr));
- }
- if (ColorOf(LeftOf(sibling)) == Black && ColorOf(RightOf(sibling)) == Black)
- {
- SetColor(sibling, Red);
- ptr = ParentOf(ptr);
- }
- else
- {
- if (ColorOf(RightOf(sibling)) == Black)
- {
- SetColor(LeftOf(sibling), Black);
- SetColor(sibling, Red);
- RotateRight(sibling);
- sibling = RightOf(ParentOf(ptr));
- }
- SetColor(sibling, ColorOf(ParentOf(ptr)));
- SetColor(ParentOf(ptr), Black);
- SetColor(RightOf(sibling), Black);
- RotateLeft(ParentOf(ptr));
- ptr = Root;
- }
- }
- else
- {
- T sibling = LeftOf(ParentOf(ptr));
-
- if (ColorOf(sibling) == Red)
- {
- SetColor(sibling, Black);
- SetColor(ParentOf(ptr), Red);
- RotateRight(ParentOf(ptr));
- sibling = LeftOf(ParentOf(ptr));
- }
- if (ColorOf(RightOf(sibling)) == Black && ColorOf(LeftOf(sibling)) == Black)
- {
- SetColor(sibling, Red);
- ptr = ParentOf(ptr);
- }
- else
- {
- if (ColorOf(LeftOf(sibling)) == Black)
- {
- SetColor(RightOf(sibling), Black);
- SetColor(sibling, Red);
- RotateLeft(sibling);
- sibling = LeftOf(ParentOf(ptr));
- }
- SetColor(sibling, ColorOf(ParentOf(ptr)));
- SetColor(ParentOf(ptr), Black);
- SetColor(LeftOf(sibling), Black);
- RotateRight(ParentOf(ptr));
- ptr = Root;
- }
- }
- }
- SetColor(ptr, Black);
- }
-
- protected void RestoreBalanceAfterInsertion(T balanceNode)
- {
- SetColor(balanceNode, Red);
- while (balanceNode != null && balanceNode != Root && ColorOf(ParentOf(balanceNode)) == Red)
- {
- if (ParentOf(balanceNode) == LeftOf(ParentOf(ParentOf(balanceNode))))
- {
- T sibling = RightOf(ParentOf(ParentOf(balanceNode)));
-
- if (ColorOf(sibling) == Red)
- {
- SetColor(ParentOf(balanceNode), Black);
- SetColor(sibling, Black);
- SetColor(ParentOf(ParentOf(balanceNode)), Red);
- balanceNode = ParentOf(ParentOf(balanceNode));
- }
- else
- {
- if (balanceNode == RightOf(ParentOf(balanceNode)))
- {
- balanceNode = ParentOf(balanceNode);
- RotateLeft(balanceNode);
- }
- SetColor(ParentOf(balanceNode), Black);
- SetColor(ParentOf(ParentOf(balanceNode)), Red);
- RotateRight(ParentOf(ParentOf(balanceNode)));
- }
- }
- else
- {
- T sibling = LeftOf(ParentOf(ParentOf(balanceNode)));
-
- if (ColorOf(sibling) == Red)
- {
- SetColor(ParentOf(balanceNode), Black);
- SetColor(sibling, Black);
- SetColor(ParentOf(ParentOf(balanceNode)), Red);
- balanceNode = ParentOf(ParentOf(balanceNode));
- }
- else
- {
- if (balanceNode == LeftOf(ParentOf(balanceNode)))
- {
- balanceNode = ParentOf(balanceNode);
- RotateRight(balanceNode);
- }
- SetColor(ParentOf(balanceNode), Black);
- SetColor(ParentOf(ParentOf(balanceNode)), Red);
- RotateLeft(ParentOf(ParentOf(balanceNode)));
- }
- }
- }
- SetColor(Root, Black);
- }
-
- protected virtual void RotateLeft(T node)
- {
- if (node != null)
- {
- T right = RightOf(node);
- node.Right = LeftOf(right);
- if (node.Right != null)
- {
- node.Right.Parent = node;
- }
- T nodeParent = ParentOf(node);
- right.Parent = nodeParent;
- if (nodeParent == null)
- {
- Root = right;
- }
- else if (node == LeftOf(nodeParent))
- {
- nodeParent.Left = right;
- }
- else
- {
- nodeParent.Right = right;
- }
- right.Left = node;
- node.Parent = right;
- }
- }
-
- protected virtual void RotateRight(T node)
- {
- if (node != null)
- {
- T left = LeftOf(node);
- node.Left = RightOf(left);
- if (node.Left != null)
- {
- node.Left.Parent = node;
- }
- T nodeParent = ParentOf(node);
- left.Parent = nodeParent;
- if (nodeParent == null)
- {
- Root = left;
- }
- else if (node == RightOf(nodeParent))
- {
- nodeParent.Right = left;
- }
- else
- {
- nodeParent.Left = left;
- }
- left.Right = node;
- node.Parent = left;
- }
- }
-
- #region Safety-Methods
-
- // These methods save memory by allowing us to forego sentinel nil nodes, as well as serve as protection against NullReferenceExceptions.
-
- ///
- /// Returns the color of , or Black if it is null.
- ///
- /// Node
- /// The boolean color of , or black if null
- protected static bool ColorOf(T node)
- {
- return node == null || node.Color;
- }
-
- ///
- /// Sets the color of node to .
- ///
- /// This method does nothing if is null.
- ///
- /// Node to set the color of
- /// Color (Boolean)
- protected static void SetColor(T node, bool color)
- {
- if (node != null)
- {
- node.Color = color;
- }
- }
-
- ///
- /// This method returns the left node of , or null if is null.
- ///
- /// Node to retrieve the left child from
- /// Left child of
- protected static T LeftOf(T node)
- {
- return node?.Left;
- }
-
- ///
- /// This method returns the right node of , or null if is null.
- ///
- /// Node to retrieve the right child from
- /// Right child of
- protected static T RightOf(T node)
- {
- return node?.Right;
- }
-
- ///
- /// Returns the parent node of , or null if is null.
- ///
- /// Node to retrieve the parent from
- /// Parent of
- protected static T ParentOf(T node)
- {
- return node?.Parent;
- }
-
- #endregion
- }
-}
diff --git a/Ryujinx.Common/Collections/IntrusiveRedBlackTreeNode.cs b/Ryujinx.Common/Collections/IntrusiveRedBlackTreeNode.cs
deleted file mode 100644
index 7143240d..00000000
--- a/Ryujinx.Common/Collections/IntrusiveRedBlackTreeNode.cs
+++ /dev/null
@@ -1,16 +0,0 @@
-namespace Ryujinx.Common.Collections
-{
- ///
- /// Represents a node in the Red-Black Tree.
- ///
- public class IntrusiveRedBlackTreeNode where T : IntrusiveRedBlackTreeNode
- {
- internal bool Color = true;
- internal T Left;
- internal T Right;
- internal T Parent;
-
- public T Predecessor => IntrusiveRedBlackTreeImpl.PredecessorOf((T)this);
- public T Successor => IntrusiveRedBlackTreeImpl.SuccessorOf((T)this);
- }
-}
\ No newline at end of file
diff --git a/Ryujinx.Common/Collections/TreeDictionary.cs b/Ryujinx.Common/Collections/TreeDictionary.cs
deleted file mode 100644
index d118a30c..00000000
--- a/Ryujinx.Common/Collections/TreeDictionary.cs
+++ /dev/null
@@ -1,617 +0,0 @@
-using System;
-using System.Collections;
-using System.Collections.Generic;
-using System.Diagnostics.CodeAnalysis;
-
-namespace Ryujinx.Common.Collections
-{
- ///
- /// Dictionary that provides the ability for O(logN) Lookups for keys that exist in the Dictionary, and O(logN) lookups for keys immediately greater than or less than a specified key.
- ///
- /// Key
- /// Value
- public class TreeDictionary : IntrusiveRedBlackTreeImpl>, IDictionary where K : IComparable
- {
- #region Public Methods
-
- ///
- /// Returns the value of the node whose key is , or the default value if no such node exists.
- ///
- /// Key of the node value to get
- /// Value associated w/
- /// is null
- public V Get(K key)
- {
- ArgumentNullException.ThrowIfNull(key);
-
- Node node = GetNode(key);
-
- if (node == null)
- {
- return default;
- }
-
- return node.Value;
- }
-
- ///
- /// Adds a new node into the tree whose key is key and value is .
- ///
- /// Note: Adding the same key multiple times will cause the value for that key to be overwritten.
- ///
- /// Key of the node to add
- /// Value of the node to add
- /// or are null
- public void Add(K key, V value)
- {
- ArgumentNullException.ThrowIfNull(key);
- ArgumentNullException.ThrowIfNull(value);
-
- Insert(key, value);
- }
-
- ///
- /// Removes the node whose key is from the tree.
- ///
- /// Key of the node to remove
- /// is null
- public void Remove(K key)
- {
- ArgumentNullException.ThrowIfNull(key);
-
- if (Delete(key) != null)
- {
- Count--;
- }
- }
-
- ///
- /// Returns the value whose key is equal to or immediately less than .
- ///
- /// Key for which to find the floor value of
- /// Key of node immediately less than
- /// is null
- public K Floor(K key)
- {
- Node node = FloorNode(key);
- if (node != null)
- {
- return node.Key;
- }
- return default;
- }
-
- ///
- /// Returns the node whose key is equal to or immediately greater than .
- ///
- /// Key for which to find the ceiling node of
- /// Key of node immediately greater than
- /// is null
- public K Ceiling(K key)
- {
- Node node = CeilingNode(key);
- if (node != null)
- {
- return node.Key;
- }
- return default;
- }
-
- ///
- /// Finds the value whose key is immediately greater than .
- ///
- /// Key to find the successor of
- /// Value
- public K SuccessorOf(K key)
- {
- Node node = GetNode(key);
- if (node != null)
- {
- Node successor = SuccessorOf(node);
-
- return successor != null ? successor.Key : default;
- }
- return default;
- }
-
- ///
- /// Finds the value whose key is immediately less than .
- ///
- /// Key to find the predecessor of
- /// Value
- public K PredecessorOf(K key)
- {
- Node node = GetNode(key);
- if (node != null)
- {
- Node predecessor = PredecessorOf(node);
-
- return predecessor != null ? predecessor.Key : default;
- }
- return default;
- }
-
- ///
- /// Adds all the nodes in the dictionary as key/value pairs into .
- ///
- /// The key/value pairs will be added in Level Order.
- ///
- /// List to add the tree pairs into
- public List> AsLevelOrderList()
- {
- List> list = new List>();
-
- Queue> nodes = new Queue>();
-
- if (this.Root != null)
- {
- nodes.Enqueue(this.Root);
- }
- while (nodes.TryDequeue(out Node node))
- {
- list.Add(new KeyValuePair(node.Key, node.Value));
- if (node.Left != null)
- {
- nodes.Enqueue(node.Left);
- }
- if (node.Right != null)
- {
- nodes.Enqueue(node.Right);
- }
- }
- return list;
- }
-
- ///
- /// Adds all the nodes in the dictionary into .
- ///
- /// A list of all KeyValuePairs sorted by Key Order
- public List> AsList()
- {
- List> list = new List>();
-
- AddToList(Root, list);
-
- return list;
- }
-
- #endregion
-
- #region Private Methods (BST)
-
- ///
- /// Adds all nodes that are children of or contained within into , in Key Order.
- ///
- /// The node to search for nodes within
- /// The list to add node to
- private void AddToList(Node node, List> list)
- {
- if (node == null)
- {
- return;
- }
-
- AddToList(node.Left, list);
-
- list.Add(new KeyValuePair(node.Key, node.Value));
-
- AddToList(node.Right, list);
- }
-
- ///
- /// Retrieve the node reference whose key is , or null if no such node exists.
- ///
- /// Key of the node to get
- /// Node reference in the tree
- /// is null
- private Node GetNode(K key)
- {
- ArgumentNullException.ThrowIfNull(key);
-
- Node node = Root;
- while (node != null)
- {
- int cmp = key.CompareTo(node.Key);
- if (cmp < 0)
- {
- node = node.Left;
- }
- else if (cmp > 0)
- {
- node = node.Right;
- }
- else
- {
- return node;
- }
- }
- return null;
- }
-
- ///
- /// Inserts a new node into the tree whose key is and value is .
- ///
- /// Adding the same key multiple times will overwrite the previous value.
- ///
- /// Key of the node to insert
- /// Value of the node to insert
- private void Insert(K key, V value)
- {
- Node newNode = BSTInsert(key, value);
- RestoreBalanceAfterInsertion(newNode);
- }
-
- ///
- /// Insertion Mechanism for a Binary Search Tree (BST).
- ///
- /// Iterates the tree starting from the root and inserts a new node where all children in the left subtree are less than , and all children in the right subtree are greater than .
- ///
- /// Note: If a node whose key is already exists, it's value will be overwritten.
- ///
- /// Key of the node to insert
- /// Value of the node to insert
- /// The inserted Node
- private Node BSTInsert(K key, V value)
- {
- Node parent = null;
- Node node = Root;
-
- while (node != null)
- {
- parent = node;
- int cmp = key.CompareTo(node.Key);
- if (cmp < 0)
- {
- node = node.Left;
- }
- else if (cmp > 0)
- {
- node = node.Right;
- }
- else
- {
- node.Value = value;
- return node;
- }
- }
- Node newNode = new Node(key, value, parent);
- if (newNode.Parent == null)
- {
- Root = newNode;
- }
- else if (key.CompareTo(parent.Key) < 0)
- {
- parent.Left = newNode;
- }
- else
- {
- parent.Right = newNode;
- }
- Count++;
- return newNode;
- }
-
- ///
- /// Removes from the dictionary, if it exists.
- ///
- /// Key of the node to delete
- /// The deleted Node
- private Node Delete(K key)
- {
- // O(1) Retrieval
- Node nodeToDelete = GetNode(key);
-
- if (nodeToDelete == null) return null;
-
- Node replacementNode;
-
- if (LeftOf(nodeToDelete) == null || RightOf(nodeToDelete) == null)
- {
- replacementNode = nodeToDelete;
- }
- else
- {
- replacementNode = PredecessorOf(nodeToDelete);
- }
-
- Node tmp = LeftOf(replacementNode) ?? RightOf(replacementNode);
-
- if (tmp != null)
- {
- tmp.Parent = ParentOf(replacementNode);
- }
-
- if (ParentOf(replacementNode) == null)
- {
- Root = tmp;
- }
- else if (replacementNode == LeftOf(ParentOf(replacementNode)))
- {
- ParentOf(replacementNode).Left = tmp;
- }
- else
- {
- ParentOf(replacementNode).Right = tmp;
- }
-
- if (replacementNode != nodeToDelete)
- {
- nodeToDelete.Key = replacementNode.Key;
- nodeToDelete.Value = replacementNode.Value;
- }
-
- if (tmp != null && ColorOf(replacementNode) == Black)
- {
- RestoreBalanceAfterRemoval(tmp);
- }
-
- return replacementNode;
- }
-
- ///
- /// Returns the node whose key immediately less than or equal to .
- ///
- /// Key for which to find the floor node of
- /// Node whose key is immediately less than or equal to , or null if no such node is found.
- /// is null
- private Node FloorNode(K key)
- {
- ArgumentNullException.ThrowIfNull(key);
-
- Node tmp = Root;
-
- while (tmp != null)
- {
- int cmp = key.CompareTo(tmp.Key);
- if (cmp > 0)
- {
- if (tmp.Right != null)
- {
- tmp = tmp.Right;
- }
- else
- {
- return tmp;
- }
- }
- else if (cmp < 0)
- {
- if (tmp.Left != null)
- {
- tmp = tmp.Left;
- }
- else
- {
- Node parent = tmp.Parent;
- Node ptr = tmp;
- while (parent != null && ptr == parent.Left)
- {
- ptr = parent;
- parent = parent.Parent;
- }
- return parent;
- }
- }
- else
- {
- return tmp;
- }
- }
- return null;
- }
-
- ///
- /// Returns the node whose key is immediately greater than or equal to than .
- ///
- /// Key for which to find the ceiling node of
- /// Node whose key is immediately greater than or equal to , or null if no such node is found.
- /// is null
- private Node CeilingNode(K key)
- {
- ArgumentNullException.ThrowIfNull(key);
-
- Node tmp = Root;
-
- while (tmp != null)
- {
- int cmp = key.CompareTo(tmp.Key);
- if (cmp < 0)
- {
- if (tmp.Left != null)
- {
- tmp = tmp.Left;
- }
- else
- {
- return tmp;
- }
- }
- else if (cmp > 0)
- {
- if (tmp.Right != null)
- {
- tmp = tmp.Right;
- }
- else
- {
- Node parent = tmp.Parent;
- Node ptr = tmp;
- while (parent != null && ptr == parent.Right)
- {
- ptr = parent;
- parent = parent.Parent;
- }
- return parent;
- }
- }
- else
- {
- return tmp;
- }
- }
- return null;
- }
-
- #endregion
-
- #region Interface Implementations
-
- // Method descriptions are not provided as they are already included as part of the interface.
- public bool ContainsKey(K key)
- {
- ArgumentNullException.ThrowIfNull(key);
-
- return GetNode(key) != null;
- }
-
- bool IDictionary.Remove(K key)
- {
- int count = Count;
- Remove(key);
- return count > Count;
- }
-
- public bool TryGetValue(K key, [MaybeNullWhen(false)] out V value)
- {
- ArgumentNullException.ThrowIfNull(key);
-
- Node node = GetNode(key);
- value = node != null ? node.Value : default;
- return node != null;
- }
-
- public void Add(KeyValuePair item)
- {
- ArgumentNullException.ThrowIfNull(item.Key);
-
- Add(item.Key, item.Value);
- }
-
- public bool Contains(KeyValuePair item)
- {
- if (item.Key == null)
- {
- return false;
- }
-
- Node node = GetNode(item.Key);
- if (node != null)
- {
- return node.Key.Equals(item.Key) && node.Value.Equals(item.Value);
- }
- return false;
- }
-
- public void CopyTo(KeyValuePair[] array, int arrayIndex)
- {
- if (arrayIndex < 0 || array.Length - arrayIndex < this.Count)
- {
- throw new ArgumentOutOfRangeException(nameof(arrayIndex));
- }
-
- SortedList list = GetKeyValues();
-
- int offset = 0;
-
- for (int i = arrayIndex; i < array.Length && offset < list.Count; i++)
- {
- array[i] = new KeyValuePair(list.Keys[i], list.Values[i]);
- offset++;
- }
- }
-
- public bool Remove(KeyValuePair item)
- {
- Node node = GetNode(item.Key);
-
- if (node == null)
- {
- return false;
- }
-
- if (node.Value.Equals(item.Value))
- {
- int count = Count;
- Remove(item.Key);
- return count > Count;
- }
-
- return false;
- }
-
- public IEnumerator> GetEnumerator()
- {
- return GetKeyValues().GetEnumerator();
- }
-
- IEnumerator IEnumerable.GetEnumerator()
- {
- return GetKeyValues().GetEnumerator();
- }
-
- public ICollection Keys => GetKeyValues().Keys;
-
- public ICollection Values => GetKeyValues().Values;
-
- public bool IsReadOnly => false;
-
- public V this[K key]
- {
- get => Get(key);
- set => Add(key, value);
- }
-
- #endregion
-
- #region Private Interface Helper Methods
-
- ///
- /// Returns a sorted list of all the node keys / values in the tree.
- ///
- /// List of node keys
- private SortedList GetKeyValues()
- {
- SortedList set = new SortedList();
- Queue> queue = new Queue>();
- if (Root != null)
- {
- queue.Enqueue(Root);
- }
-
- while (queue.TryDequeue(out Node node))
- {
- set.Add(node.Key, node.Value);
- if (null != node.Left)
- {
- queue.Enqueue(node.Left);
- }
- if (null != node.Right)
- {
- queue.Enqueue(node.Right);
- }
- }
-
- return set;
- }
-
- #endregion
- }
-
- ///
- /// Represents a node in the TreeDictionary which contains a key and value of generic type K and V, respectively.
- ///
- /// Key of the node
- /// Value of the node
- public class Node : IntrusiveRedBlackTreeNode> where K : IComparable
- {
- internal K Key;
- internal V Value;
-
- internal Node(K key, V value, Node parent)
- {
- Key = key;
- Value = value;
- Parent = parent;
- }
- }
-}
--
cgit v1.2.3