ImmutableTree<TKey, TValue>
using System;
using System.Collections.Generic;
using System.Runtime.CompilerServices;
namespace Stashbox.Utils.Data.Immutable
{
[System.Runtime.CompilerServices.NullableContext(1)]
[System.Runtime.CompilerServices.Nullable(0)]
internal sealed class ImmutableTree<TKey, [System.Runtime.CompilerServices.Nullable(2)] TValue> where TKey : class
{
public static readonly ImmutableTree<TKey, TValue> Empty = new ImmutableTree<TKey, TValue>();
private readonly int height;
private readonly int storedHash;
[System.Runtime.CompilerServices.Nullable(2)]
private readonly TKey storedKey;
[System.Runtime.CompilerServices.Nullable(2)]
private readonly TValue storedValue;
[System.Runtime.CompilerServices.Nullable(new byte[] {
2,
1,
1
})]
private readonly ImmutableTree<TKey, TValue> leftNode;
[System.Runtime.CompilerServices.Nullable(new byte[] {
2,
1,
1
})]
private readonly ImmutableTree<TKey, TValue> rightNode;
[System.Runtime.CompilerServices.Nullable(new byte[] {
2,
1,
1
})]
private readonly ImmutableBucket<TKey, TValue> collisions;
public readonly bool IsEmpty = true;
private ImmutableTree(int hash, TKey key, TValue value, ImmutableTree<TKey, TValue> left, ImmutableTree<TKey, TValue> right, ImmutableBucket<TKey, TValue> collisions)
{
this.collisions = collisions;
storedKey = key;
storedHash = hash;
leftNode = left;
rightNode = right;
storedValue = value;
IsEmpty = false;
height = 1 + ((left.height > right.height) ? left.height : right.height);
}
private ImmutableTree()
{
}
private ImmutableTree(int hash, TKey key, TValue value)
{
storedKey = key;
storedHash = hash;
leftNode = Empty;
rightNode = Empty;
storedValue = value;
IsEmpty = false;
height = 1;
}
public ImmutableTree<TKey, TValue> AddOrUpdate(TKey key, TValue value, bool byRef, [System.Runtime.CompilerServices.Nullable(new byte[] {
2,
1,
1,
1
})] Func<TValue, TValue, TValue> updateDelegate = null)
{
return AddOrUpdate(byRef ? RuntimeHelpers.GetHashCode(key) : key.GetHashCode(), key, value, byRef, updateDelegate, false);
}
public ImmutableTree<TKey, TValue> AddOrUpdate(TKey key, TValue value, bool byRef, bool forceUpdate)
{
return AddOrUpdate(byRef ? RuntimeHelpers.GetHashCode(key) : key.GetHashCode(), key, value, byRef, null, forceUpdate);
}
public ImmutableTree<TKey, TValue> UpdateIfExists(TKey key, bool byRef, Func<TValue, TValue> updateDelegate)
{
return UpdateIfExists(byRef ? RuntimeHelpers.GetHashCode(key) : key.GetHashCode(), key, byRef, updateDelegate);
}
public ImmutableTree<TKey, TValue> UpdateIfExists(TKey key, TValue value, bool byRef)
{
return UpdateIfExists(byRef ? RuntimeHelpers.GetHashCode(key) : key.GetHashCode(), key, byRef, value);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
[return: System.Runtime.CompilerServices.Nullable(2)]
public TValue GetOrDefaultByValue(TKey key)
{
if (IsEmpty)
return default(TValue);
int hashCode = key.GetHashCode();
ImmutableTree<TKey, TValue> immutableTree = this;
while (!immutableTree.IsEmpty && immutableTree.storedHash != hashCode) {
immutableTree = ((hashCode < immutableTree.storedHash) ? immutableTree.leftNode : immutableTree.rightNode);
}
if (immutableTree.IsEmpty || !object.Equals(key, immutableTree.storedKey)) {
if (immutableTree.collisions != null)
return immutableTree.collisions.GetOrDefaultByValue(key);
return default(TValue);
}
return immutableTree.storedValue;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
[return: System.Runtime.CompilerServices.Nullable(2)]
public TValue GetOrDefaultByRef(TKey key)
{
if (IsEmpty)
return default(TValue);
int hashCode = RuntimeHelpers.GetHashCode(key);
ImmutableTree<TKey, TValue> immutableTree = this;
while (!immutableTree.IsEmpty && immutableTree.storedHash != hashCode) {
immutableTree = ((hashCode < immutableTree.storedHash) ? immutableTree.leftNode : immutableTree.rightNode);
}
if (immutableTree.IsEmpty || key != immutableTree.storedKey) {
if (immutableTree.collisions != null)
return immutableTree.collisions.GetOrDefaultByRef(key);
return default(TValue);
}
return immutableTree.storedValue;
}
private ImmutableTree<TKey, TValue> AddOrUpdate(int hash, TKey key, TValue value, bool byRef, [System.Runtime.CompilerServices.Nullable(new byte[] {
2,
1,
1,
1
})] Func<TValue, TValue, TValue> updateDelegate, bool forceUpdate)
{
if (IsEmpty)
return new ImmutableTree<TKey, TValue>(hash, key, value);
if (hash == storedHash)
return CheckCollision(hash, key, value, byRef, updateDelegate, forceUpdate);
if (hash < storedHash) {
if (height == 1)
return new ImmutableTree<TKey, TValue>(storedHash, storedKey, storedValue, new ImmutableTree<TKey, TValue>(hash, key, value), rightNode, collisions);
ImmutableTree<TKey, TValue> immutableTree = leftNode.AddOrUpdate(hash, key, value, byRef, updateDelegate, forceUpdate);
if (immutableTree != leftNode)
return Balance(storedHash, storedKey, storedValue, immutableTree, rightNode, collisions);
return this;
}
if (height == 1)
return new ImmutableTree<TKey, TValue>(storedHash, storedKey, storedValue, leftNode, new ImmutableTree<TKey, TValue>(hash, key, value), collisions);
ImmutableTree<TKey, TValue> immutableTree2 = rightNode.AddOrUpdate(hash, key, value, byRef, updateDelegate, forceUpdate);
if (immutableTree2 != rightNode)
return Balance(storedHash, storedKey, storedValue, leftNode, immutableTree2, collisions);
return this;
}
private ImmutableTree<TKey, TValue> UpdateIfExists(int hash, TKey key, bool byRef, Func<TValue, TValue> updateDelegate)
{
if (IsEmpty)
return this;
if (hash == storedHash)
return ReplaceInCollisionsIfExist(hash, key, byRef, updateDelegate);
if (hash < storedHash) {
ImmutableTree<TKey, TValue> immutableTree = leftNode.UpdateIfExists(hash, key, byRef, updateDelegate);
if (immutableTree == leftNode)
return this;
return new ImmutableTree<TKey, TValue>(storedHash, storedKey, storedValue, immutableTree, rightNode, collisions);
}
ImmutableTree<TKey, TValue> immutableTree2 = rightNode.UpdateIfExists(hash, key, byRef, updateDelegate);
if (immutableTree2 == rightNode)
return this;
return new ImmutableTree<TKey, TValue>(storedHash, storedKey, storedValue, leftNode, immutableTree2, collisions);
}
private ImmutableTree<TKey, TValue> UpdateIfExists(int hash, TKey key, bool byRef, TValue value)
{
if (IsEmpty)
return this;
if (hash == storedHash)
return ReplaceInCollisionsIfExist(hash, key, value, byRef);
if (hash < storedHash) {
ImmutableTree<TKey, TValue> immutableTree = leftNode.UpdateIfExists(hash, key, byRef, value);
if (immutableTree == leftNode)
return this;
return new ImmutableTree<TKey, TValue>(storedHash, storedKey, storedValue, immutableTree, rightNode, collisions);
}
ImmutableTree<TKey, TValue> immutableTree2 = rightNode.UpdateIfExists(hash, key, byRef, value);
if (immutableTree2 == rightNode)
return this;
return new ImmutableTree<TKey, TValue>(storedHash, storedKey, storedValue, leftNode, immutableTree2, collisions);
}
private ImmutableTree<TKey, TValue> CheckCollision(int hash, TKey key, TValue value, bool byRef, [System.Runtime.CompilerServices.Nullable(new byte[] {
2,
1,
1,
1
})] Func<TValue, TValue, TValue> updateDelegate, bool forceUpdate)
{
if ((byRef && key == storedKey) || (!byRef && object.Equals(key, storedKey))) {
if (forceUpdate)
return new ImmutableTree<TKey, TValue>(hash, key, value, leftNode, rightNode, collisions);
if (updateDelegate == null)
return this;
TValue val = updateDelegate(storedValue, value);
if ((object)val != (object)storedValue)
return new ImmutableTree<TKey, TValue>(hash, key, val, leftNode, rightNode, collisions);
return this;
}
if (collisions == null)
return new ImmutableTree<TKey, TValue>(hash, key, value, leftNode, rightNode, ImmutableBucket<TKey, TValue>.Empty.Add(key, value));
TValue val2 = ((updateDelegate == null) | forceUpdate) ? value : updateDelegate(storedValue, value);
if ((object)val2 == (object)storedValue)
return this;
return new ImmutableTree<TKey, TValue>(hash, key, value, leftNode, rightNode, collisions.AddOrUpdate(key, val2, byRef, null));
}
private ImmutableTree<TKey, TValue> ReplaceInCollisionsIfExist(int hash, TKey key, bool byRef, Func<TValue, TValue> updateDelegate)
{
if (key == storedKey)
return new ImmutableTree<TKey, TValue>(hash, key, updateDelegate(storedValue), leftNode, rightNode, collisions);
if (collisions == null)
return this;
ImmutableBucket<TKey, TValue> immutableBucket = collisions.ReplaceIfExists(key, updateDelegate, byRef);
if (immutableBucket == collisions)
return this;
return new ImmutableTree<TKey, TValue>(storedHash, storedKey, storedValue, leftNode, rightNode, immutableBucket);
}
private ImmutableTree<TKey, TValue> ReplaceInCollisionsIfExist(int hash, TKey key, TValue value, bool byRef)
{
if (key == storedKey)
return new ImmutableTree<TKey, TValue>(hash, key, value, leftNode, rightNode, collisions);
if (collisions == null)
return this;
ImmutableBucket<TKey, TValue> immutableBucket = collisions.ReplaceIfExists(key, value, byRef, null);
if (immutableBucket == collisions)
return this;
return new ImmutableTree<TKey, TValue>(storedHash, storedKey, storedValue, leftNode, rightNode, immutableBucket);
}
private static ImmutableTree<TKey, TValue> Balance(int hash, TKey key, TValue value, ImmutableTree<TKey, TValue> left, ImmutableTree<TKey, TValue> right, ImmutableBucket<TKey, TValue> collisions)
{
int num = left.height - right.height;
if (num >= 2)
return (left.leftNode.height - left.rightNode.height == -1) ? RotateLeftRight(hash, key, value, left, right, collisions) : RotateRight(hash, key, value, left, right, collisions);
if (num <= -2)
return (right.leftNode.height - right.rightNode.height == 1) ? RotateRightLeft(hash, key, value, left, right, collisions) : RotateLeft(hash, key, value, left, right, collisions);
return new ImmutableTree<TKey, TValue>(hash, key, value, left, right, collisions);
}
private static ImmutableTree<TKey, TValue> RotateRight(int hash, TKey key, TValue value, ImmutableTree<TKey, TValue> left, ImmutableTree<TKey, TValue> right, ImmutableBucket<TKey, TValue> collisions)
{
ImmutableTree<TKey, TValue> right2 = new ImmutableTree<TKey, TValue>(hash, key, value, left.rightNode, right, collisions);
return new ImmutableTree<TKey, TValue>(left.storedHash, left.storedKey, left.storedValue, left.leftNode, right2, left.collisions);
}
private static ImmutableTree<TKey, TValue> RotateLeft(int hash, TKey key, TValue value, ImmutableTree<TKey, TValue> left, ImmutableTree<TKey, TValue> right, ImmutableBucket<TKey, TValue> collisions)
{
ImmutableTree<TKey, TValue> left2 = new ImmutableTree<TKey, TValue>(hash, key, value, left, right.leftNode, collisions);
return new ImmutableTree<TKey, TValue>(right.storedHash, right.storedKey, right.storedValue, left2, right.rightNode, right.collisions);
}
private static ImmutableTree<TKey, TValue> RotateRightLeft(int hash, TKey key, TValue value, ImmutableTree<TKey, TValue> left, ImmutableTree<TKey, TValue> right, ImmutableBucket<TKey, TValue> collisions)
{
ImmutableTree<TKey, TValue> left2 = new ImmutableTree<TKey, TValue>(hash, key, value, left, right.leftNode.leftNode, collisions);
ImmutableTree<TKey, TValue> right2 = new ImmutableTree<TKey, TValue>(right.storedHash, right.storedKey, right.storedValue, right.leftNode.rightNode, right.rightNode, right.collisions);
return new ImmutableTree<TKey, TValue>(right.leftNode.storedHash, right.leftNode.storedKey, right.leftNode.storedValue, left2, right2, right.leftNode.collisions);
}
private static ImmutableTree<TKey, TValue> RotateLeftRight(int hash, TKey key, TValue value, ImmutableTree<TKey, TValue> left, ImmutableTree<TKey, TValue> right, ImmutableBucket<TKey, TValue> collisions)
{
ImmutableTree<TKey, TValue> left2 = new ImmutableTree<TKey, TValue>(left.storedHash, left.storedKey, left.storedValue, left.leftNode, left.rightNode.leftNode, left.collisions);
ImmutableTree<TKey, TValue> right2 = new ImmutableTree<TKey, TValue>(hash, key, value, left.rightNode.rightNode, right, collisions);
return new ImmutableTree<TKey, TValue>(left.rightNode.storedHash, left.rightNode.storedKey, left.rightNode.storedValue, left2, right2, left.rightNode.collisions);
}
public override string ToString()
{
if (!IsEmpty)
return $"{storedKey}""{storedValue}";
return "empty";
}
[return: System.Runtime.CompilerServices.Nullable(new byte[] {
1,
0,
1,
1
})]
public IEnumerable<ReadOnlyKeyValue<TKey, TValue>> Walk()
{
if (!this.IsEmpty) {
ImmutableTree<TKey, TValue>[] nodes = new ImmutableTree<TKey, TValue>[this.height];
ImmutableTree<TKey, TValue> currentNode2 = this;
int index = -1;
while (!currentNode2.IsEmpty || index != -1) {
if (!currentNode2.IsEmpty) {
ImmutableTree<TKey, TValue>[] array = nodes;
int num = index + 1;
index = num;
array[num] = currentNode2;
currentNode2 = currentNode2.leftNode;
} else {
ImmutableTree<TKey, TValue>[] array2 = nodes;
int num = index;
index = num - 1;
currentNode2 = array2[num];
yield return new ReadOnlyKeyValue<TKey, TValue>(currentNode2.storedKey, currentNode2.storedValue);
if (currentNode2.collisions != null) {
ReadOnlyKeyValue<TKey, TValue>[] repository = currentNode2.collisions.Repository;
foreach (ReadOnlyKeyValue<TKey, TValue> readOnlyKeyValue in repository) {
yield return readOnlyKeyValue;
}
}
currentNode2 = currentNode2.rightNode;
}
}
}
}
}
}