AvlTree<TValue>
using Stashbox.Entity;
using System;
using System.Collections.Generic;
using System.Runtime.CompilerServices;
namespace Stashbox.Utils
{
internal sealed class AvlTree<TValue>
{
public static readonly AvlTree<TValue> Empty = new AvlTree<TValue>();
private readonly int storedHash;
private readonly TValue storedValue;
private readonly AvlTree<TValue> leftNode;
private readonly AvlTree<TValue> rightNode;
private readonly int height;
public bool IsEmpty = true;
private AvlTree(int hash, TValue value, AvlTree<TValue> left, AvlTree<TValue> right)
{
storedHash = hash;
leftNode = left;
rightNode = right;
storedValue = value;
IsEmpty = false;
height = 1 + ((left.height > right.height) ? left.height : right.height);
}
private AvlTree(int hash, TValue value)
{
storedHash = hash;
leftNode = Empty;
rightNode = Empty;
storedValue = value;
IsEmpty = false;
height = 1;
}
private AvlTree()
{
}
public AvlTree<TValue> AddOrUpdate(int key, TValue value, Func<TValue, TValue, TValue> updateDelegate = null)
{
return Add(key, value, updateDelegate, false);
}
public AvlTree<TValue> AddOrUpdate(int key, TValue value, bool forceUpdate)
{
return Add(key, value, null, true);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public TValue GetOrDefault(int key)
{
AvlTree<TValue> avlTree = this;
while (!avlTree.IsEmpty && avlTree.storedHash != key) {
avlTree = ((key < avlTree.storedHash) ? avlTree.leftNode : avlTree.rightNode);
}
if (avlTree.IsEmpty)
return default(TValue);
return avlTree.storedValue;
}
private AvlTree<TValue> Add(int hash, TValue value, Func<TValue, TValue, TValue> updateDelegate, bool forceUpdate)
{
if (IsEmpty)
return new AvlTree<TValue>(hash, value);
if (hash == storedHash) {
if (updateDelegate == null) {
if (!forceUpdate)
return this;
return new AvlTree<TValue>(hash, value, leftNode, rightNode);
}
return new AvlTree<TValue>(hash, updateDelegate(storedValue, value), leftNode, rightNode);
}
if (hash >= storedHash) {
if (height != 1)
return Balance(storedHash, storedValue, leftNode, rightNode.Add(hash, value, updateDelegate, forceUpdate));
return new AvlTree<TValue>(storedHash, storedValue, leftNode, new AvlTree<TValue>(hash, value));
}
if (height != 1)
return Balance(storedHash, storedValue, leftNode.Add(hash, value, updateDelegate, forceUpdate), rightNode);
return new AvlTree<TValue>(storedHash, storedValue, new AvlTree<TValue>(hash, value), rightNode);
}
private static AvlTree<TValue> Balance(int hash, TValue value, AvlTree<TValue> left, AvlTree<TValue> right)
{
int num = left.height - right.height;
if (num >= 2) {
if (left.leftNode.height - left.rightNode.height != -1)
return RotateRight(hash, value, left, right);
return RotateLeftRight(hash, value, left, right);
}
if (num <= -2) {
if (right.leftNode.height - right.rightNode.height != 1)
return RotateLeft(hash, value, left, right);
return RotateRightLeft(hash, value, left, right);
}
return new AvlTree<TValue>(hash, value, left, right);
}
private static AvlTree<TValue> RotateRight(int hash, TValue value, AvlTree<TValue> left, AvlTree<TValue> right)
{
AvlTree<TValue> right2 = new AvlTree<TValue>(hash, value, left.rightNode, right);
return new AvlTree<TValue>(left.storedHash, left.storedValue, left.leftNode, right2);
}
private static AvlTree<TValue> RotateLeft(int hash, TValue value, AvlTree<TValue> left, AvlTree<TValue> right)
{
AvlTree<TValue> left2 = new AvlTree<TValue>(hash, value, left, right.leftNode);
return new AvlTree<TValue>(right.storedHash, right.storedValue, left2, right.rightNode);
}
private static AvlTree<TValue> RotateRightLeft(int hash, TValue value, AvlTree<TValue> left, AvlTree<TValue> right)
{
AvlTree<TValue> left2 = new AvlTree<TValue>(hash, value, left, right.leftNode.leftNode);
AvlTree<TValue> right2 = new AvlTree<TValue>(right.storedHash, right.storedValue, right.leftNode.rightNode, right.rightNode);
return new AvlTree<TValue>(right.leftNode.storedHash, right.leftNode.storedValue, left2, right2);
}
private static AvlTree<TValue> RotateLeftRight(int hash, TValue value, AvlTree<TValue> left, AvlTree<TValue> right)
{
AvlTree<TValue> left2 = new AvlTree<TValue>(left.storedHash, left.storedValue, left.leftNode, left.rightNode.leftNode);
AvlTree<TValue> right2 = new AvlTree<TValue>(hash, value, left.rightNode.rightNode, right);
return new AvlTree<TValue>(left.rightNode.storedHash, left.rightNode.storedValue, left2, right2);
}
public override string ToString()
{
if (!IsEmpty)
return $"{storedHash}""{storedValue}";
return "empty";
}
public IEnumerable<KeyValue<int, TValue>> Walk()
{
if (!this.IsEmpty) {
AvlTree<TValue>[] nodes = new AvlTree<TValue>[this.height];
AvlTree<TValue> currentNode2 = this;
int index = -1;
while (!currentNode2.IsEmpty || index != -1) {
if (!currentNode2.IsEmpty) {
AvlTree<TValue>[] array = nodes;
int num = index + 1;
index = num;
array[num] = currentNode2;
currentNode2 = currentNode2.leftNode;
} else {
AvlTree<TValue>[] array2 = nodes;
int num = index;
index = num - 1;
currentNode2 = array2[num];
yield return new KeyValue<int, TValue>(currentNode2.storedHash, currentNode2.storedValue);
currentNode2 = currentNode2.rightNode;
}
}
}
}
}
}