ImmutableTree<TKey, TValue>
using System;
using System.Collections.Generic;
using System.Runtime.CompilerServices;
namespace Stashbox.Utils.Data.Immutable
{
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 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, Func<TValue, TValue, TValue> updateDelegate = null)
{
return AddOrUpdate(RuntimeHelpers.GetHashCode(key), key, value, updateDelegate, false);
}
public ImmutableTree<TKey, TValue> AddOrUpdate(TKey key, TValue value, bool forceUpdate)
{
return AddOrUpdate(RuntimeHelpers.GetHashCode(key), key, value, null, forceUpdate);
}
public ImmutableTree<TKey, TValue> UpdateIfExists(TKey key, Func<TValue, TValue> updateDelegate)
{
return UpdateIfExists(RuntimeHelpers.GetHashCode(key), key, updateDelegate);
}
public ImmutableTree<TKey, TValue> UpdateIfExists(TKey key, TValue value)
{
return UpdateIfExists(RuntimeHelpers.GetHashCode(key), key, value);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public TValue GetOrDefault(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 || (object)key != (object)immutableTree.storedKey) {
if (immutableTree.collisions != null)
return immutableTree.collisions.GetOrDefault(key, true);
return default(TValue);
}
return immutableTree.storedValue;
}
private ImmutableTree<TKey, TValue> AddOrUpdate(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 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, updateDelegate, forceUpdate);
if (immutableTree == leftNode)
return this;
return Balance(storedHash, storedKey, storedValue, immutableTree, rightNode, collisions);
}
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, updateDelegate, forceUpdate);
if (immutableTree2 == rightNode)
return this;
return Balance(storedHash, storedKey, storedValue, leftNode, immutableTree2, collisions);
}
private ImmutableTree<TKey, TValue> UpdateIfExists(int hash, TKey key, Func<TValue, TValue> updateDelegate)
{
if (IsEmpty)
return this;
if (hash == storedHash)
return ReplaceInCollisionsIfExist(hash, key, updateDelegate);
if (hash < storedHash) {
if (leftNode.UpdateIfExists(hash, key, updateDelegate) == leftNode)
return this;
} else if (rightNode.UpdateIfExists(hash, key, updateDelegate) == rightNode) {
return this;
}
return new ImmutableTree<TKey, TValue>(storedHash, storedKey, storedValue, leftNode, rightNode, collisions);
}
private ImmutableTree<TKey, TValue> UpdateIfExists(int hash, TKey key, TValue value)
{
if (IsEmpty)
return this;
if (hash == storedHash)
return ReplaceInCollisionsIfExist(hash, key, value);
if (hash < storedHash) {
if (leftNode.UpdateIfExists(hash, key, value) == leftNode)
return this;
} else if (rightNode.UpdateIfExists(hash, key, value) == rightNode) {
return this;
}
return new ImmutableTree<TKey, TValue>(storedHash, storedKey, storedValue, leftNode, 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) {
if (forceUpdate)
return new ImmutableTree<TKey, TValue>(hash, key, value, leftNode, rightNode, collisions);
if (updateDelegate != null) {
TValue val = updateDelegate(storedValue, value);
if ((object)val == (object)storedValue)
return this;
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, true, null));
}
private ImmutableTree<TKey, TValue> ReplaceInCollisionsIfExist(int hash, TKey key, Func<TValue, TValue> updateDelegate)
{
if ((object)key == (object)storedKey)
return new ImmutableTree<TKey, TValue>(hash, key, updateDelegate(storedValue), leftNode, rightNode, collisions);
if (collisions != null) {
ImmutableBucket<TKey, TValue> immutableBucket = collisions.ReplaceIfExists(key, updateDelegate, true);
if (immutableBucket == collisions)
return this;
return new ImmutableTree<TKey, TValue>(storedHash, storedKey, storedValue, leftNode, rightNode, immutableBucket);
}
return this;
}
private ImmutableTree<TKey, TValue> ReplaceInCollisionsIfExist(int hash, TKey key, TValue value)
{
if ((object)key == (object)storedKey)
return new ImmutableTree<TKey, TValue>(hash, key, value, leftNode, rightNode, collisions);
if (collisions != null) {
ImmutableBucket<TKey, TValue> immutableBucket = collisions.ReplaceIfExists(key, value, true, null);
if (immutableBucket == collisions)
return this;
return new ImmutableTree<TKey, TValue>(storedHash, storedKey, storedValue, leftNode, rightNode, immutableBucket);
}
return this;
}
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) {
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, 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";
}
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) {
KeyValue<TKey, TValue>[] repository = currentNode2.collisions.Repository;
foreach (KeyValue<TKey, TValue> keyValue in repository) {
yield return keyValue;
}
}
currentNode2 = currentNode2.rightNode;
}
}
}
}
}
}