diff options
Diffstat (limited to 'src/Ryujinx.Common/Collections')
5 files changed, 134 insertions, 136 deletions
diff --git a/src/Ryujinx.Common/Collections/IntervalTree.cs b/src/Ryujinx.Common/Collections/IntervalTree.cs index b5188cc7..2ea260a5 100644 --- a/src/Ryujinx.Common/Collections/IntervalTree.cs +++ b/src/Ryujinx.Common/Collections/IntervalTree.cs @@ -7,9 +7,9 @@ namespace Ryujinx.Common.Collections /// <summary> /// An Augmented Interval Tree based off of the "TreeDictionary"'s Red-Black Tree. Allows fast overlap checking of ranges. /// </summary> - /// <typeparam name="K">Key</typeparam> - /// <typeparam name="V">Value</typeparam> - public class IntervalTree<K, V> : IntrusiveRedBlackTreeImpl<IntervalTreeNode<K, V>> where K : IComparable<K> + /// <typeparam name="TKey">Key</typeparam> + /// <typeparam name="TValue">Value</typeparam> + public class IntervalTree<TKey, TValue> : IntrusiveRedBlackTreeImpl<IntervalTreeNode<TKey, TValue>> where TKey : IComparable<TKey> { private const int ArrayGrowthSize = 32; @@ -22,11 +22,11 @@ namespace Ryujinx.Common.Collections /// <param name="overlaps">Overlaps array to place results in</param> /// <returns>Number of values found</returns> /// <exception cref="ArgumentNullException"><paramref name="key"/> is null</exception> - public int Get(K key, ref V[] overlaps) + public int Get(TKey key, ref TValue[] overlaps) { ArgumentNullException.ThrowIfNull(key); - IntervalTreeNode<K, V> node = GetNode(key); + IntervalTreeNode<TKey, TValue> node = GetNode(key); if (node == null) { @@ -39,7 +39,7 @@ namespace Ryujinx.Common.Collections } int overlapsCount = 0; - foreach (RangeNode<K, V> value in node.Values) + foreach (RangeNode<TKey, TValue> value in node.Values) { overlaps[overlapsCount++] = value.Value; } @@ -56,7 +56,7 @@ namespace Ryujinx.Common.Collections /// <param name="overlapCount">Index to start writing results into the array. Defaults to 0</param> /// <returns>Number of values found</returns> /// <exception cref="ArgumentNullException"><paramref name="start"/> or <paramref name="end"/> is null</exception> - public int Get(K start, K end, ref V[] overlaps, int overlapCount = 0) + public int Get(TKey start, TKey end, ref TValue[] overlaps, int overlapCount = 0) { ArgumentNullException.ThrowIfNull(start); ArgumentNullException.ThrowIfNull(end); @@ -73,7 +73,7 @@ namespace Ryujinx.Common.Collections /// <param name="end">End of the range to insert</param> /// <param name="value">Value to add</param> /// <exception cref="ArgumentNullException"><paramref name="start"/>, <paramref name="end"/> or <paramref name="value"/> are null</exception> - public void Add(K start, K end, V value) + public void Add(TKey start, TKey end, TValue value) { ArgumentNullException.ThrowIfNull(start); ArgumentNullException.ThrowIfNull(end); @@ -89,7 +89,7 @@ namespace Ryujinx.Common.Collections /// <param name="value">Value to remove</param> /// <exception cref="ArgumentNullException"><paramref name="key"/> is null</exception> /// <returns>Number of deleted values</returns> - public int Remove(K key, V value) + public int Remove(TKey key, TValue value) { ArgumentNullException.ThrowIfNull(key); @@ -104,9 +104,9 @@ namespace Ryujinx.Common.Collections /// Adds all the nodes in the dictionary into <paramref name="list"/>. /// </summary> /// <returns>A list of all RangeNodes sorted by Key Order</returns> - public List<RangeNode<K, V>> AsList() + public List<RangeNode<TKey, TValue>> AsList() { - List<RangeNode<K, V>> list = new List<RangeNode<K, V>>(); + List<RangeNode<TKey, TValue>> list = new(); AddToList(Root, list); @@ -122,7 +122,7 @@ namespace Ryujinx.Common.Collections /// </summary> /// <param name="node">The node to search for RangeNodes within</param> /// <param name="list">The list to add RangeNodes to</param> - private void AddToList(IntervalTreeNode<K, V> node, List<RangeNode<K, V>> list) + private void AddToList(IntervalTreeNode<TKey, TValue> node, List<RangeNode<TKey, TValue>> list) { if (node == null) { @@ -142,11 +142,11 @@ namespace Ryujinx.Common.Collections /// <param name="key">Key of the node to get</param> /// <returns>Node reference in the tree</returns> /// <exception cref="ArgumentNullException"><paramref name="key"/> is null</exception> - private IntervalTreeNode<K, V> GetNode(K key) + private IntervalTreeNode<TKey, TValue> GetNode(TKey key) { ArgumentNullException.ThrowIfNull(key); - IntervalTreeNode<K, V> node = Root; + IntervalTreeNode<TKey, TValue> node = Root; while (node != null) { int cmp = key.CompareTo(node.Start); @@ -173,7 +173,7 @@ namespace Ryujinx.Common.Collections /// <param name="end">End of the range</param> /// <param name="overlaps">Overlaps array to place results in</param> /// <param name="overlapCount">Overlaps count to update</param> - private void GetValues(IntervalTreeNode<K, V> node, K start, K end, ref V[] overlaps, ref int overlapCount) + private void GetValues(IntervalTreeNode<TKey, TValue> node, TKey start, TKey end, ref TValue[] overlaps, ref int overlapCount) { if (node == null || start.CompareTo(node.Max) >= 0) { @@ -188,7 +188,7 @@ namespace Ryujinx.Common.Collections if (start.CompareTo(node.End) < 0) { // Contains this node. Add overlaps to list. - foreach (RangeNode<K,V> overlap in node.Values) + foreach (RangeNode<TKey, TValue> overlap in node.Values) { if (start.CompareTo(overlap.End) < 0) { @@ -212,9 +212,9 @@ namespace Ryujinx.Common.Collections /// <param name="start">Start of the range to insert</param> /// <param name="end">End of the range to insert</param> /// <param name="value">Value to insert</param> - private void Insert(K start, K end, V value) + private void Insert(TKey start, TKey end, TValue value) { - IntervalTreeNode<K, V> newNode = BSTInsert(start, end, value); + IntervalTreeNode<TKey, TValue> newNode = BSTInsert(start, end, value); RestoreBalanceAfterInsertion(newNode); } @@ -223,10 +223,10 @@ namespace Ryujinx.Common.Collections /// This should only be called if the max increases - not for rebalancing or removals. /// </summary> /// <param name="node">The node to start propagating from</param> - private void PropagateIncrease(IntervalTreeNode<K, V> node) + private static void PropagateIncrease(IntervalTreeNode<TKey, TValue> node) { - K max = node.Max; - IntervalTreeNode<K, V> ptr = node; + TKey max = node.Max; + IntervalTreeNode<TKey, TValue> ptr = node; while ((ptr = ptr.Parent) != null) { @@ -246,13 +246,13 @@ namespace Ryujinx.Common.Collections /// This fully recalculates the max value from all children when there is potential for it to decrease. /// </summary> /// <param name="node">The node to start propagating from</param> - private void PropagateFull(IntervalTreeNode<K, V> node) + private static void PropagateFull(IntervalTreeNode<TKey, TValue> node) { - IntervalTreeNode<K, V> ptr = node; + IntervalTreeNode<TKey, TValue> ptr = node; do { - K max = ptr.End; + TKey max = ptr.End; if (ptr.Left != null && ptr.Left.Max.CompareTo(max) > 0) { @@ -278,10 +278,10 @@ namespace Ryujinx.Common.Collections /// <param name="end">End of the range to insert</param> /// <param name="value">Value to insert</param> /// <returns>The inserted Node</returns> - private IntervalTreeNode<K, V> BSTInsert(K start, K end, V value) + private IntervalTreeNode<TKey, TValue> BSTInsert(TKey start, TKey end, TValue value) { - IntervalTreeNode<K, V> parent = null; - IntervalTreeNode<K, V> node = Root; + IntervalTreeNode<TKey, TValue> parent = null; + IntervalTreeNode<TKey, TValue> node = Root; while (node != null) { @@ -297,7 +297,7 @@ namespace Ryujinx.Common.Collections } else { - node.Values.Add(new RangeNode<K, V>(start, end, value)); + node.Values.Add(new RangeNode<TKey, TValue>(start, end, value)); if (end.CompareTo(node.End) > 0) { @@ -313,7 +313,7 @@ namespace Ryujinx.Common.Collections return node; } } - IntervalTreeNode<K, V> newNode = new IntervalTreeNode<K, V>(start, end, value, parent); + IntervalTreeNode<TKey, TValue> newNode = new(start, end, value, parent); if (newNode.Parent == null) { Root = newNode; @@ -338,9 +338,9 @@ namespace Ryujinx.Common.Collections /// <param name="key">Key to search for</param> /// <param name="value">Value to delete</param> /// <returns>Number of deleted values</returns> - private int Delete(K key, V value) + private int Delete(TKey key, TValue value) { - IntervalTreeNode<K, V> nodeToDelete = GetNode(key); + IntervalTreeNode<TKey, TValue> nodeToDelete = GetNode(key); if (nodeToDelete == null) { @@ -362,7 +362,7 @@ namespace Ryujinx.Common.Collections return removed; } - IntervalTreeNode<K, V> replacementNode; + IntervalTreeNode<TKey, TValue> replacementNode; if (LeftOf(nodeToDelete) == null || RightOf(nodeToDelete) == null) { @@ -373,7 +373,7 @@ namespace Ryujinx.Common.Collections replacementNode = PredecessorOf(nodeToDelete); } - IntervalTreeNode<K, V> tmp = LeftOf(replacementNode) ?? RightOf(replacementNode); + IntervalTreeNode<TKey, TValue> tmp = LeftOf(replacementNode) ?? RightOf(replacementNode); if (tmp != null) { @@ -413,7 +413,7 @@ namespace Ryujinx.Common.Collections #endregion - protected override void RotateLeft(IntervalTreeNode<K, V> node) + protected override void RotateLeft(IntervalTreeNode<TKey, TValue> node) { if (node != null) { @@ -423,7 +423,7 @@ namespace Ryujinx.Common.Collections } } - protected override void RotateRight(IntervalTreeNode<K, V> node) + protected override void RotateRight(IntervalTreeNode<TKey, TValue> node) { if (node != null) { @@ -433,7 +433,7 @@ namespace Ryujinx.Common.Collections } } - public bool ContainsKey(K key) + public bool ContainsKey(TKey key) { ArgumentNullException.ThrowIfNull(key); @@ -444,15 +444,15 @@ namespace Ryujinx.Common.Collections /// <summary> /// Represents a value and its start and end keys. /// </summary> - /// <typeparam name="K"></typeparam> - /// <typeparam name="V"></typeparam> - public readonly struct RangeNode<K, V> + /// <typeparam name="TKey"></typeparam> + /// <typeparam name="TValue"></typeparam> + public readonly struct RangeNode<TKey, TValue> { - public readonly K Start; - public readonly K End; - public readonly V Value; + public readonly TKey Start; + public readonly TKey End; + public readonly TValue Value; - public RangeNode(K start, K end, V value) + public RangeNode(TKey start, TKey end, TValue value) { Start = start; End = end; @@ -463,36 +463,36 @@ namespace Ryujinx.Common.Collections /// <summary> /// Represents a node in the IntervalTree which contains start and end keys of type K, and a value of generic type V. /// </summary> - /// <typeparam name="K">Key type of the node</typeparam> - /// <typeparam name="V">Value type of the node</typeparam> - public class IntervalTreeNode<K, V> : IntrusiveRedBlackTreeNode<IntervalTreeNode<K, V>> + /// <typeparam name="TKey">Key type of the node</typeparam> + /// <typeparam name="TValue">Value type of the node</typeparam> + public class IntervalTreeNode<TKey, TValue> : IntrusiveRedBlackTreeNode<IntervalTreeNode<TKey, TValue>> { /// <summary> /// The start of the range. /// </summary> - internal K Start; + internal TKey Start; /// <summary> /// The end of the range - maximum of all in the Values list. /// </summary> - internal K End; + internal TKey End; /// <summary> /// The maximum end value of this node and all its children. /// </summary> - internal K Max; + internal TKey Max; /// <summary> /// Values contained on the node that shares a common Start value. /// </summary> - internal List<RangeNode<K, V>> Values; + internal List<RangeNode<TKey, TValue>> Values; - internal IntervalTreeNode(K start, K end, V value, IntervalTreeNode<K, V> parent) + internal IntervalTreeNode(TKey start, TKey end, TValue value, IntervalTreeNode<TKey, TValue> parent) { Start = start; End = end; Max = end; - Values = new List<RangeNode<K, V>> { new RangeNode<K, V>(start, end, value) }; + Values = new List<RangeNode<TKey, TValue>> { new RangeNode<TKey, TValue>(start, end, value) }; Parent = parent; } } diff --git a/src/Ryujinx.Common/Collections/IntrusiveRedBlackTree.cs b/src/Ryujinx.Common/Collections/IntrusiveRedBlackTree.cs index 0063d91e..9e56f707 100644 --- a/src/Ryujinx.Common/Collections/IntrusiveRedBlackTree.cs +++ b/src/Ryujinx.Common/Collections/IntrusiveRedBlackTree.cs @@ -180,11 +180,6 @@ namespace Ryujinx.Common.Collections parent.Right = child; } - if (ParentOf(element) == old) - { - parent = element; - } - element.Color = old.Color; element.Left = old.Left; element.Right = old.Right; @@ -258,11 +253,11 @@ namespace Ryujinx.Common.Collections /// <param name="tree">Tree to search at</param> /// <param name="key">Key of the node to be found</param> /// <returns>Node that is equal to <paramref name="key"/></returns> - public static N GetNodeByKey<N, K>(this IntrusiveRedBlackTree<N> tree, K key) - where N : IntrusiveRedBlackTreeNode<N>, IComparable<N>, IComparable<K> - where K : struct + public static TNode GetNodeByKey<TNode, TKey>(this IntrusiveRedBlackTree<TNode> tree, TKey key) + where TNode : IntrusiveRedBlackTreeNode<TNode>, IComparable<TNode>, IComparable<TKey> + where TKey : struct { - N node = tree.RootNode; + TNode node = tree.RootNode; while (node != null) { int cmp = node.CompareTo(key); diff --git a/src/Ryujinx.Common/Collections/IntrusiveRedBlackTreeImpl.cs b/src/Ryujinx.Common/Collections/IntrusiveRedBlackTreeImpl.cs index bcb2e2a2..49f97223 100644 --- a/src/Ryujinx.Common/Collections/IntrusiveRedBlackTreeImpl.cs +++ b/src/Ryujinx.Common/Collections/IntrusiveRedBlackTreeImpl.cs @@ -10,7 +10,7 @@ namespace Ryujinx.Common.Collections { protected const bool Black = true; protected const bool Red = false; - protected T Root = null; + protected T Root; internal T RootNode => Root; diff --git a/src/Ryujinx.Common/Collections/IntrusiveRedBlackTreeNode.cs b/src/Ryujinx.Common/Collections/IntrusiveRedBlackTreeNode.cs index 7143240d..8480d51a 100644 --- a/src/Ryujinx.Common/Collections/IntrusiveRedBlackTreeNode.cs +++ b/src/Ryujinx.Common/Collections/IntrusiveRedBlackTreeNode.cs @@ -13,4 +13,4 @@ namespace Ryujinx.Common.Collections public T Predecessor => IntrusiveRedBlackTreeImpl<T>.PredecessorOf((T)this); public T Successor => IntrusiveRedBlackTreeImpl<T>.SuccessorOf((T)this); } -}
\ No newline at end of file +} diff --git a/src/Ryujinx.Common/Collections/TreeDictionary.cs b/src/Ryujinx.Common/Collections/TreeDictionary.cs index d118a30c..ff179488 100644 --- a/src/Ryujinx.Common/Collections/TreeDictionary.cs +++ b/src/Ryujinx.Common/Collections/TreeDictionary.cs @@ -8,9 +8,9 @@ namespace Ryujinx.Common.Collections /// <summary> /// 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. /// </summary> - /// <typeparam name="K">Key</typeparam> - /// <typeparam name="V">Value</typeparam> - public class TreeDictionary<K, V> : IntrusiveRedBlackTreeImpl<Node<K, V>>, IDictionary<K, V> where K : IComparable<K> + /// <typeparam name="TKey">Key</typeparam> + /// <typeparam name="TValue">Value</typeparam> + public class TreeDictionary<TKey, TValue> : IntrusiveRedBlackTreeImpl<Node<TKey, TValue>>, IDictionary<TKey, TValue> where TKey : IComparable<TKey> { #region Public Methods @@ -20,11 +20,11 @@ namespace Ryujinx.Common.Collections /// <param name="key">Key of the node value to get</param> /// <returns>Value associated w/ <paramref name="key"/></returns> /// <exception cref="ArgumentNullException"><paramref name="key"/> is null</exception> - public V Get(K key) + public TValue Get(TKey key) { ArgumentNullException.ThrowIfNull(key); - Node<K, V> node = GetNode(key); + Node<TKey, TValue> node = GetNode(key); if (node == null) { @@ -42,7 +42,7 @@ namespace Ryujinx.Common.Collections /// <param name="key">Key of the node to add</param> /// <param name="value">Value of the node to add</param> /// <exception cref="ArgumentNullException"><paramref name="key"/> or <paramref name="value"/> are null</exception> - public void Add(K key, V value) + public void Add(TKey key, TValue value) { ArgumentNullException.ThrowIfNull(key); ArgumentNullException.ThrowIfNull(value); @@ -55,7 +55,7 @@ namespace Ryujinx.Common.Collections /// </summary> /// <param name="key">Key of the node to remove</param> /// <exception cref="ArgumentNullException"><paramref name="key"/> is null</exception> - public void Remove(K key) + public void Remove(TKey key) { ArgumentNullException.ThrowIfNull(key); @@ -71,9 +71,9 @@ namespace Ryujinx.Common.Collections /// <param name="key">Key for which to find the floor value of</param> /// <returns>Key of node immediately less than <paramref name="key"/></returns> /// <exception cref="ArgumentNullException"><paramref name="key"/> is null</exception> - public K Floor(K key) + public TKey Floor(TKey key) { - Node<K, V> node = FloorNode(key); + Node<TKey, TValue> node = FloorNode(key); if (node != null) { return node.Key; @@ -87,9 +87,9 @@ namespace Ryujinx.Common.Collections /// <param name="key">Key for which to find the ceiling node of</param> /// <returns>Key of node immediately greater than <paramref name="key"/></returns> /// <exception cref="ArgumentNullException"><paramref name="key"/> is null</exception> - public K Ceiling(K key) + public TKey Ceiling(TKey key) { - Node<K, V> node = CeilingNode(key); + Node<TKey, TValue> node = CeilingNode(key); if (node != null) { return node.Key; @@ -102,12 +102,12 @@ namespace Ryujinx.Common.Collections /// </summary> /// <param name="key">Key to find the successor of</param> /// <returns>Value</returns> - public K SuccessorOf(K key) + public TKey SuccessorOf(TKey key) { - Node<K, V> node = GetNode(key); + Node<TKey, TValue> node = GetNode(key); if (node != null) { - Node<K, V> successor = SuccessorOf(node); + Node<TKey, TValue> successor = SuccessorOf(node); return successor != null ? successor.Key : default; } @@ -119,12 +119,12 @@ namespace Ryujinx.Common.Collections /// </summary> /// <param name="key">Key to find the predecessor of</param> /// <returns>Value</returns> - public K PredecessorOf(K key) + public TKey PredecessorOf(TKey key) { - Node<K, V> node = GetNode(key); + Node<TKey, TValue> node = GetNode(key); if (node != null) { - Node<K, V> predecessor = PredecessorOf(node); + Node<TKey, TValue> predecessor = PredecessorOf(node); return predecessor != null ? predecessor.Key : default; } @@ -137,19 +137,19 @@ namespace Ryujinx.Common.Collections /// The key/value pairs will be added in Level Order. /// </summary> /// <param name="list">List to add the tree pairs into</param> - public List<KeyValuePair<K, V>> AsLevelOrderList() + public List<KeyValuePair<TKey, TValue>> AsLevelOrderList() { - List<KeyValuePair<K, V>> list = new List<KeyValuePair<K, V>>(); + List<KeyValuePair<TKey, TValue>> list = new(); - Queue<Node<K, V>> nodes = new Queue<Node<K, V>>(); + Queue<Node<TKey, TValue>> nodes = new(); if (this.Root != null) { nodes.Enqueue(this.Root); } - while (nodes.TryDequeue(out Node<K, V> node)) + while (nodes.TryDequeue(out Node<TKey, TValue> node)) { - list.Add(new KeyValuePair<K, V>(node.Key, node.Value)); + list.Add(new KeyValuePair<TKey, TValue>(node.Key, node.Value)); if (node.Left != null) { nodes.Enqueue(node.Left); @@ -166,9 +166,9 @@ namespace Ryujinx.Common.Collections /// Adds all the nodes in the dictionary into <paramref name="list"/>. /// </summary> /// <returns>A list of all KeyValuePairs sorted by Key Order</returns> - public List<KeyValuePair<K, V>> AsList() + public List<KeyValuePair<TKey, TValue>> AsList() { - List<KeyValuePair<K, V>> list = new List<KeyValuePair<K, V>>(); + List<KeyValuePair<TKey, TValue>> list = new(); AddToList(Root, list); @@ -184,7 +184,7 @@ namespace Ryujinx.Common.Collections /// </summary> /// <param name="node">The node to search for nodes within</param> /// <param name="list">The list to add node to</param> - private void AddToList(Node<K, V> node, List<KeyValuePair<K, V>> list) + private void AddToList(Node<TKey, TValue> node, List<KeyValuePair<TKey, TValue>> list) { if (node == null) { @@ -193,7 +193,7 @@ namespace Ryujinx.Common.Collections AddToList(node.Left, list); - list.Add(new KeyValuePair<K, V>(node.Key, node.Value)); + list.Add(new KeyValuePair<TKey, TValue>(node.Key, node.Value)); AddToList(node.Right, list); } @@ -204,11 +204,11 @@ namespace Ryujinx.Common.Collections /// <param name="key">Key of the node to get</param> /// <returns>Node reference in the tree</returns> /// <exception cref="ArgumentNullException"><paramref name="key"/> is null</exception> - private Node<K, V> GetNode(K key) + private Node<TKey, TValue> GetNode(TKey key) { ArgumentNullException.ThrowIfNull(key); - Node<K, V> node = Root; + Node<TKey, TValue> node = Root; while (node != null) { int cmp = key.CompareTo(node.Key); @@ -235,9 +235,9 @@ namespace Ryujinx.Common.Collections /// </summary> /// <param name="key">Key of the node to insert</param> /// <param name="value">Value of the node to insert</param> - private void Insert(K key, V value) + private void Insert(TKey key, TValue value) { - Node<K, V> newNode = BSTInsert(key, value); + Node<TKey, TValue> newNode = BSTInsert(key, value); RestoreBalanceAfterInsertion(newNode); } @@ -251,10 +251,10 @@ namespace Ryujinx.Common.Collections /// <param name="key">Key of the node to insert</param> /// <param name="value">Value of the node to insert</param> /// <returns>The inserted Node</returns> - private Node<K, V> BSTInsert(K key, V value) + private Node<TKey, TValue> BSTInsert(TKey key, TValue value) { - Node<K, V> parent = null; - Node<K, V> node = Root; + Node<TKey, TValue> parent = null; + Node<TKey, TValue> node = Root; while (node != null) { @@ -274,7 +274,7 @@ namespace Ryujinx.Common.Collections return node; } } - Node<K, V> newNode = new Node<K, V>(key, value, parent); + Node<TKey, TValue> newNode = new(key, value, parent); if (newNode.Parent == null) { Root = newNode; @@ -296,14 +296,17 @@ namespace Ryujinx.Common.Collections /// </summary> /// <param name="key">Key of the node to delete</param> /// <returns>The deleted Node</returns> - private Node<K, V> Delete(K key) + private Node<TKey, TValue> Delete(TKey key) { // O(1) Retrieval - Node<K, V> nodeToDelete = GetNode(key); + Node<TKey, TValue> nodeToDelete = GetNode(key); - if (nodeToDelete == null) return null; + if (nodeToDelete == null) + { + return null; + } - Node<K, V> replacementNode; + Node<TKey, TValue> replacementNode; if (LeftOf(nodeToDelete) == null || RightOf(nodeToDelete) == null) { @@ -314,7 +317,7 @@ namespace Ryujinx.Common.Collections replacementNode = PredecessorOf(nodeToDelete); } - Node<K, V> tmp = LeftOf(replacementNode) ?? RightOf(replacementNode); + Node<TKey, TValue> tmp = LeftOf(replacementNode) ?? RightOf(replacementNode); if (tmp != null) { @@ -354,11 +357,11 @@ namespace Ryujinx.Common.Collections /// <param name="key">Key for which to find the floor node of</param> /// <returns>Node whose key is immediately less than or equal to <paramref name="key"/>, or null if no such node is found.</returns> /// <exception cref="ArgumentNullException"><paramref name="key"/> is null</exception> - private Node<K, V> FloorNode(K key) + private Node<TKey, TValue> FloorNode(TKey key) { ArgumentNullException.ThrowIfNull(key); - Node<K, V> tmp = Root; + Node<TKey, TValue> tmp = Root; while (tmp != null) { @@ -382,8 +385,8 @@ namespace Ryujinx.Common.Collections } else { - Node<K, V> parent = tmp.Parent; - Node<K, V> ptr = tmp; + Node<TKey, TValue> parent = tmp.Parent; + Node<TKey, TValue> ptr = tmp; while (parent != null && ptr == parent.Left) { ptr = parent; @@ -406,11 +409,11 @@ namespace Ryujinx.Common.Collections /// <param name="key">Key for which to find the ceiling node of</param> /// <returns>Node whose key is immediately greater than or equal to <paramref name="key"/>, or null if no such node is found.</returns> /// <exception cref="ArgumentNullException"><paramref name="key"/> is null</exception> - private Node<K, V> CeilingNode(K key) + private Node<TKey, TValue> CeilingNode(TKey key) { ArgumentNullException.ThrowIfNull(key); - Node<K, V> tmp = Root; + Node<TKey, TValue> tmp = Root; while (tmp != null) { @@ -434,8 +437,8 @@ namespace Ryujinx.Common.Collections } else { - Node<K, V> parent = tmp.Parent; - Node<K, V> ptr = tmp; + Node<TKey, TValue> parent = tmp.Parent; + Node<TKey, TValue> ptr = tmp; while (parent != null && ptr == parent.Right) { ptr = parent; @@ -457,44 +460,44 @@ namespace Ryujinx.Common.Collections #region Interface Implementations // Method descriptions are not provided as they are already included as part of the interface. - public bool ContainsKey(K key) + public bool ContainsKey(TKey key) { ArgumentNullException.ThrowIfNull(key); return GetNode(key) != null; } - bool IDictionary<K, V>.Remove(K key) + bool IDictionary<TKey, TValue>.Remove(TKey key) { int count = Count; Remove(key); return count > Count; } - public bool TryGetValue(K key, [MaybeNullWhen(false)] out V value) + public bool TryGetValue(TKey key, [MaybeNullWhen(false)] out TValue value) { ArgumentNullException.ThrowIfNull(key); - Node<K, V> node = GetNode(key); + Node<TKey, TValue> node = GetNode(key); value = node != null ? node.Value : default; return node != null; } - public void Add(KeyValuePair<K, V> item) + public void Add(KeyValuePair<TKey, TValue> item) { ArgumentNullException.ThrowIfNull(item.Key); Add(item.Key, item.Value); } - public bool Contains(KeyValuePair<K, V> item) + public bool Contains(KeyValuePair<TKey, TValue> item) { if (item.Key == null) { return false; } - Node<K, V> node = GetNode(item.Key); + Node<TKey, TValue> node = GetNode(item.Key); if (node != null) { return node.Key.Equals(item.Key) && node.Value.Equals(item.Value); @@ -502,27 +505,27 @@ namespace Ryujinx.Common.Collections return false; } - public void CopyTo(KeyValuePair<K, V>[] array, int arrayIndex) + public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex) { if (arrayIndex < 0 || array.Length - arrayIndex < this.Count) { throw new ArgumentOutOfRangeException(nameof(arrayIndex)); } - SortedList<K, V> list = GetKeyValues(); + SortedList<TKey, TValue> list = GetKeyValues(); int offset = 0; for (int i = arrayIndex; i < array.Length && offset < list.Count; i++) { - array[i] = new KeyValuePair<K, V>(list.Keys[i], list.Values[i]); + array[i] = new KeyValuePair<TKey, TValue>(list.Keys[i], list.Values[i]); offset++; } } - public bool Remove(KeyValuePair<K, V> item) + public bool Remove(KeyValuePair<TKey, TValue> item) { - Node<K, V> node = GetNode(item.Key); + Node<TKey, TValue> node = GetNode(item.Key); if (node == null) { @@ -539,7 +542,7 @@ namespace Ryujinx.Common.Collections return false; } - public IEnumerator<KeyValuePair<K, V>> GetEnumerator() + public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator() { return GetKeyValues().GetEnumerator(); } @@ -549,13 +552,13 @@ namespace Ryujinx.Common.Collections return GetKeyValues().GetEnumerator(); } - public ICollection<K> Keys => GetKeyValues().Keys; + public ICollection<TKey> Keys => GetKeyValues().Keys; - public ICollection<V> Values => GetKeyValues().Values; + public ICollection<TValue> Values => GetKeyValues().Values; public bool IsReadOnly => false; - public V this[K key] + public TValue this[TKey key] { get => Get(key); set => Add(key, value); @@ -569,16 +572,16 @@ namespace Ryujinx.Common.Collections /// Returns a sorted list of all the node keys / values in the tree. /// </summary> /// <returns>List of node keys</returns> - private SortedList<K, V> GetKeyValues() + private SortedList<TKey, TValue> GetKeyValues() { - SortedList<K, V> set = new SortedList<K, V>(); - Queue<Node<K, V>> queue = new Queue<Node<K, V>>(); + SortedList<TKey, TValue> set = new(); + Queue<Node<TKey, TValue>> queue = new(); if (Root != null) { queue.Enqueue(Root); } - while (queue.TryDequeue(out Node<K, V> node)) + while (queue.TryDequeue(out Node<TKey, TValue> node)) { set.Add(node.Key, node.Value); if (null != node.Left) @@ -600,14 +603,14 @@ namespace Ryujinx.Common.Collections /// <summary> /// Represents a node in the TreeDictionary which contains a key and value of generic type K and V, respectively. /// </summary> - /// <typeparam name="K">Key of the node</typeparam> - /// <typeparam name="V">Value of the node</typeparam> - public class Node<K, V> : IntrusiveRedBlackTreeNode<Node<K, V>> where K : IComparable<K> + /// <typeparam name="TKey">Key of the node</typeparam> + /// <typeparam name="TValue">Value of the node</typeparam> + public class Node<TKey, TValue> : IntrusiveRedBlackTreeNode<Node<TKey, TValue>> where TKey : IComparable<TKey> { - internal K Key; - internal V Value; + internal TKey Key; + internal TValue Value; - internal Node(K key, V value, Node<K, V> parent) + internal Node(TKey key, TValue value, Node<TKey, TValue> parent) { Key = key; Value = value; |