ImmutableTree<TKey, TValue>
using Stashbox.Entity;
using System;
using System.Collections.Generic;
using System.Runtime.CompilerServices;
namespace Stashbox.Utils
{
internal sealed class ImmutableTree<TKey, TValue>
{
public static readonly ImmutableTree<TKey, TValue> Empty = new ImmutableTree<TKey, TValue>();
private readonly int height;
private readonly int storedHash;
private readonly TKey storedKey;
private readonly TValue storedValue;
private readonly ImmutableTree<TKey, TValue> leftNode;
private readonly ImmutableTree<TKey, TValue> rightNode;
private readonly ImmutableArray<TKey, TValue> collisions;
public bool IsEmpty = true;
private ImmutableTree(int hash, TKey key, TValue value, ImmutableTree<TKey, TValue> left, ImmutableTree<TKey, TValue> right, ImmutableArray<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, Func<TValue, TValue, TValue> updateDelegate = null)
{
return Add(key.GetHashCode(), key, value, updateDelegate, false);
}
public ImmutableTree<TKey, TValue> AddOrUpdate(TKey key, TValue value, bool forceUpdate)
{
return Add(key.GetHashCode(), key, value, null, forceUpdate);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public TValue GetOrDefault(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)key != (object)immutableTree.storedKey && !key.Equals(immutableTree.storedKey))) {
if (immutableTree.collisions != null)
return immutableTree.collisions.GetOrDefault(key);
return default(TValue);
}
return immutableTree.storedValue;
}
private ImmutableTree<TKey, TValue> Add(int hash, TKey key, TValue value, 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, updateDelegate, forceUpdate);
if (hash >= storedHash) {
if (height != 1)
return Balance(storedHash, storedKey, storedValue, leftNode, rightNode.Add(hash, key, value, updateDelegate, forceUpdate), collisions);
return new ImmutableTree<TKey, TValue>(storedHash, storedKey, storedValue, leftNode, new ImmutableTree<TKey, TValue>(hash, key, value), collisions);
}
if (height != 1)
return Balance(storedHash, storedKey, storedValue, leftNode.Add(hash, key, value, updateDelegate, forceUpdate), rightNode, collisions);
return new ImmutableTree<TKey, TValue>(storedHash, storedKey, storedValue, new ImmutableTree<TKey, TValue>(hash, key, value), rightNode, collisions);
}
private ImmutableTree<TKey, TValue> CheckCollision(int hash, TKey key, TValue value, Func<TValue, TValue, TValue> updateDelegate, bool forceUpdate)
{
if ((object)key == (object)storedKey || key.Equals(storedKey)) {
if (updateDelegate == null) {
if (!forceUpdate)
return this;
return new ImmutableTree<TKey, TValue>(hash, key, value, leftNode, rightNode, collisions);
}
return new ImmutableTree<TKey, TValue>(hash, key, updateDelegate(storedValue, value), leftNode, rightNode, collisions);
}
if (collisions == null)
return new ImmutableTree<TKey, TValue>(hash, key, value, leftNode, rightNode, ImmutableArray<TKey, TValue>.Empty.Add(key, value));
return new ImmutableTree<TKey, TValue>(hash, key, value, leftNode, rightNode, collisions.AddOrUpdate(key, ((updateDelegate == null) | forceUpdate) ? value : updateDelegate(storedValue, value), true, null));
}
private static ImmutableTree<TKey, TValue> Balance(int hash, TKey key, TValue value, ImmutableTree<TKey, TValue> left, ImmutableTree<TKey, TValue> right, ImmutableArray<TKey, TValue> collisions)
{
int num = left.height - right.height;
if (num >= 2) {
if (left.leftNode.height - left.rightNode.height != -1)
return RotateRight(hash, key, value, left, right, collisions);
return RotateLeftRight(hash, key, value, left, right, collisions);
}
if (num <= -2) {
if (right.leftNode.height - right.rightNode.height != 1)
return RotateLeft(hash, key, value, left, right, collisions);
return RotateRightLeft(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, ImmutableArray<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, ImmutableArray<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, ImmutableArray<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, ImmutableArray<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";
}
public IEnumerable<KeyValue<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 KeyValue<TKey, TValue>(currentNode2.storedKey, currentNode2.storedValue);
if (currentNode2.collisions != null && currentNode2.collisions.Length > 0) {
for (int i = 0; i < currentNode2.collisions.Length; i++) {
yield return currentNode2.collisions.Repository[i];
}
}
currentNode2 = currentNode2.rightNode;
}
}
}
}
}
}