niko
724 lines
16 KiB
C#
724 lines
16 KiB
C#
using System;
|
|
|
|
namespace System.Collections.Generic
|
|
{
|
|
// Token: 0x02000010 RID: 16
|
|
internal class RBTree : IEnumerable, IEnumerable<RBTree.Node>
|
|
{
|
|
// Token: 0x0600005C RID: 92 RVA: 0x00003348 File Offset: 0x00001548
|
|
public RBTree(object hlp)
|
|
{
|
|
this.hlp = hlp;
|
|
}
|
|
|
|
// Token: 0x0600005D RID: 93 RVA: 0x00003358 File Offset: 0x00001558
|
|
IEnumerator<RBTree.Node> IEnumerable<RBTree.Node>.GetEnumerator()
|
|
{
|
|
return this.GetEnumerator();
|
|
}
|
|
|
|
// Token: 0x0600005E RID: 94 RVA: 0x00003368 File Offset: 0x00001568
|
|
IEnumerator IEnumerable.GetEnumerator()
|
|
{
|
|
return this.GetEnumerator();
|
|
}
|
|
|
|
// Token: 0x0600005F RID: 95 RVA: 0x00003378 File Offset: 0x00001578
|
|
private static List<RBTree.Node> alloc_path()
|
|
{
|
|
if (RBTree.cached_path == null)
|
|
{
|
|
return new List<RBTree.Node>();
|
|
}
|
|
List<RBTree.Node> list = RBTree.cached_path;
|
|
RBTree.cached_path = null;
|
|
return list;
|
|
}
|
|
|
|
// Token: 0x06000060 RID: 96 RVA: 0x000033A4 File Offset: 0x000015A4
|
|
private static void release_path(List<RBTree.Node> path)
|
|
{
|
|
if (RBTree.cached_path == null || RBTree.cached_path.Capacity < path.Capacity)
|
|
{
|
|
path.Clear();
|
|
RBTree.cached_path = path;
|
|
}
|
|
}
|
|
|
|
// Token: 0x06000061 RID: 97 RVA: 0x000033D4 File Offset: 0x000015D4
|
|
public void Clear()
|
|
{
|
|
this.root = null;
|
|
this.version += 1U;
|
|
}
|
|
|
|
// Token: 0x06000062 RID: 98 RVA: 0x000033EC File Offset: 0x000015EC
|
|
public RBTree.Node Intern<T>(T key, RBTree.Node new_node)
|
|
{
|
|
if (this.root == null)
|
|
{
|
|
if (new_node == null)
|
|
{
|
|
new_node = ((RBTree.INodeHelper<T>)this.hlp).CreateNode(key);
|
|
}
|
|
this.root = new_node;
|
|
this.root.IsBlack = true;
|
|
this.version += 1U;
|
|
return this.root;
|
|
}
|
|
List<RBTree.Node> list = RBTree.alloc_path();
|
|
int num = this.find_key<T>(key, list);
|
|
RBTree.Node node = list[list.Count - 1];
|
|
if (node == null)
|
|
{
|
|
if (new_node == null)
|
|
{
|
|
new_node = ((RBTree.INodeHelper<T>)this.hlp).CreateNode(key);
|
|
}
|
|
node = this.do_insert(num, new_node, list);
|
|
}
|
|
RBTree.release_path(list);
|
|
return node;
|
|
}
|
|
|
|
// Token: 0x06000063 RID: 99 RVA: 0x00003494 File Offset: 0x00001694
|
|
public RBTree.Node Remove<T>(T key)
|
|
{
|
|
if (this.root == null)
|
|
{
|
|
return null;
|
|
}
|
|
List<RBTree.Node> list = RBTree.alloc_path();
|
|
int num = this.find_key<T>(key, list);
|
|
RBTree.Node node = null;
|
|
if (num == 0)
|
|
{
|
|
node = this.do_remove(list);
|
|
}
|
|
RBTree.release_path(list);
|
|
return node;
|
|
}
|
|
|
|
// Token: 0x06000064 RID: 100 RVA: 0x000034D4 File Offset: 0x000016D4
|
|
public RBTree.Node Lookup<T>(T key)
|
|
{
|
|
RBTree.INodeHelper<T> nodeHelper = (RBTree.INodeHelper<T>)this.hlp;
|
|
RBTree.Node node;
|
|
int num;
|
|
for (node = this.root; node != null; node = ((num >= 0) ? node.right : node.left))
|
|
{
|
|
num = nodeHelper.Compare(key, node);
|
|
if (num == 0)
|
|
{
|
|
break;
|
|
}
|
|
}
|
|
return node;
|
|
}
|
|
|
|
// Token: 0x17000015 RID: 21
|
|
// (get) Token: 0x06000065 RID: 101 RVA: 0x00003530 File Offset: 0x00001730
|
|
public int Count
|
|
{
|
|
get
|
|
{
|
|
return (int)((this.root != null) ? this.root.Size : 0U);
|
|
}
|
|
}
|
|
|
|
// Token: 0x17000016 RID: 22
|
|
public RBTree.Node this[int index]
|
|
{
|
|
get
|
|
{
|
|
if (index < 0 || index >= this.Count)
|
|
{
|
|
throw new IndexOutOfRangeException("index");
|
|
}
|
|
RBTree.Node node = this.root;
|
|
while (node != null)
|
|
{
|
|
int num = (int)((node.left != null) ? node.left.Size : 0U);
|
|
if (index == num)
|
|
{
|
|
return node;
|
|
}
|
|
if (index < num)
|
|
{
|
|
node = node.left;
|
|
}
|
|
else
|
|
{
|
|
index -= num + 1;
|
|
node = node.right;
|
|
}
|
|
}
|
|
throw new SystemException("Internal Error: index calculation");
|
|
}
|
|
}
|
|
|
|
// Token: 0x06000067 RID: 103 RVA: 0x000035E0 File Offset: 0x000017E0
|
|
public RBTree.NodeEnumerator GetEnumerator()
|
|
{
|
|
return new RBTree.NodeEnumerator(this);
|
|
}
|
|
|
|
// Token: 0x06000068 RID: 104 RVA: 0x000035E8 File Offset: 0x000017E8
|
|
private int find_key<T>(T key, List<RBTree.Node> path)
|
|
{
|
|
RBTree.INodeHelper<T> nodeHelper = (RBTree.INodeHelper<T>)this.hlp;
|
|
int num = 0;
|
|
RBTree.Node node = this.root;
|
|
if (path != null)
|
|
{
|
|
path.Add(this.root);
|
|
}
|
|
while (node != null)
|
|
{
|
|
num = nodeHelper.Compare(key, node);
|
|
if (num == 0)
|
|
{
|
|
return num;
|
|
}
|
|
RBTree.Node node2;
|
|
if (num < 0)
|
|
{
|
|
node2 = node.right;
|
|
node = node.left;
|
|
}
|
|
else
|
|
{
|
|
node2 = node.left;
|
|
node = node.right;
|
|
}
|
|
if (path != null)
|
|
{
|
|
path.Add(node2);
|
|
path.Add(node);
|
|
}
|
|
}
|
|
return num;
|
|
}
|
|
|
|
// Token: 0x06000069 RID: 105 RVA: 0x00003678 File Offset: 0x00001878
|
|
private RBTree.Node do_insert(int in_tree_cmp, RBTree.Node current, List<RBTree.Node> path)
|
|
{
|
|
path[path.Count - 1] = current;
|
|
RBTree.Node node = path[path.Count - 3];
|
|
if (in_tree_cmp < 0)
|
|
{
|
|
node.left = current;
|
|
}
|
|
else
|
|
{
|
|
node.right = current;
|
|
}
|
|
for (int i = 0; i < path.Count - 2; i += 2)
|
|
{
|
|
path[i].Size += 1U;
|
|
}
|
|
if (!node.IsBlack)
|
|
{
|
|
this.rebalance_insert(path);
|
|
}
|
|
if (!this.root.IsBlack)
|
|
{
|
|
throw new SystemException("Internal error: root is not black");
|
|
}
|
|
this.version += 1U;
|
|
return current;
|
|
}
|
|
|
|
// Token: 0x0600006A RID: 106 RVA: 0x00003728 File Offset: 0x00001928
|
|
private RBTree.Node do_remove(List<RBTree.Node> path)
|
|
{
|
|
int num = path.Count - 1;
|
|
RBTree.Node node = path[num];
|
|
if (node.left != null)
|
|
{
|
|
RBTree.Node node2 = RBTree.right_most(node.left, node.right, path);
|
|
node.SwapValue(node2);
|
|
if (node2.left != null)
|
|
{
|
|
RBTree.Node left = node2.left;
|
|
path.Add(null);
|
|
path.Add(left);
|
|
node2.SwapValue(left);
|
|
}
|
|
}
|
|
else if (node.right != null)
|
|
{
|
|
RBTree.Node right = node.right;
|
|
path.Add(null);
|
|
path.Add(right);
|
|
node.SwapValue(right);
|
|
}
|
|
num = path.Count - 1;
|
|
node = path[num];
|
|
if (node.Size != 1U)
|
|
{
|
|
throw new SystemException("Internal Error: red-black violation somewhere");
|
|
}
|
|
path[num] = null;
|
|
this.node_reparent((num != 0) ? path[num - 2] : null, node, 0U, null);
|
|
for (int i = 0; i < path.Count - 2; i += 2)
|
|
{
|
|
path[i].Size -= 1U;
|
|
}
|
|
if (num != 0 && node.IsBlack)
|
|
{
|
|
this.rebalance_delete(path);
|
|
}
|
|
if (this.root != null && !this.root.IsBlack)
|
|
{
|
|
throw new SystemException("Internal Error: root is not black");
|
|
}
|
|
this.version += 1U;
|
|
return node;
|
|
}
|
|
|
|
// Token: 0x0600006B RID: 107 RVA: 0x00003890 File Offset: 0x00001A90
|
|
private void rebalance_insert(List<RBTree.Node> path)
|
|
{
|
|
int num = path.Count - 1;
|
|
while (path[num - 3] != null && !path[num - 3].IsBlack)
|
|
{
|
|
RBTree.Node node = path[num - 2];
|
|
bool flag = true;
|
|
path[num - 3].IsBlack = flag;
|
|
node.IsBlack = flag;
|
|
num -= 4;
|
|
if (num == 0)
|
|
{
|
|
return;
|
|
}
|
|
path[num].IsBlack = false;
|
|
if (path[num - 2].IsBlack)
|
|
{
|
|
return;
|
|
}
|
|
}
|
|
this.rebalance_insert__rotate_final(num, path);
|
|
}
|
|
|
|
// Token: 0x0600006C RID: 108 RVA: 0x0000391C File Offset: 0x00001B1C
|
|
private void rebalance_delete(List<RBTree.Node> path)
|
|
{
|
|
int num = path.Count - 1;
|
|
for (;;)
|
|
{
|
|
RBTree.Node node = path[num - 1];
|
|
if (!node.IsBlack)
|
|
{
|
|
num = this.ensure_sibling_black(num, path);
|
|
node = path[num - 1];
|
|
}
|
|
if ((node.left != null && !node.left.IsBlack) || (node.right != null && !node.right.IsBlack))
|
|
{
|
|
break;
|
|
}
|
|
node.IsBlack = false;
|
|
num -= 2;
|
|
if (num == 0)
|
|
{
|
|
return;
|
|
}
|
|
if (!path[num].IsBlack)
|
|
{
|
|
goto Block_5;
|
|
}
|
|
}
|
|
this.rebalance_delete__rotate_final(num, path);
|
|
return;
|
|
Block_5:
|
|
path[num].IsBlack = true;
|
|
}
|
|
|
|
// Token: 0x0600006D RID: 109 RVA: 0x000039CC File Offset: 0x00001BCC
|
|
private void rebalance_insert__rotate_final(int curpos, List<RBTree.Node> path)
|
|
{
|
|
RBTree.Node node = path[curpos];
|
|
RBTree.Node node2 = path[curpos - 2];
|
|
RBTree.Node node3 = path[curpos - 4];
|
|
uint size = node3.Size;
|
|
bool flag = node2 == node3.left;
|
|
bool flag2 = node == node2.left;
|
|
RBTree.Node node4;
|
|
if (flag && flag2)
|
|
{
|
|
node3.left = node2.right;
|
|
node2.right = node3;
|
|
node4 = node2;
|
|
}
|
|
else if (flag && !flag2)
|
|
{
|
|
node3.left = node.right;
|
|
node.right = node3;
|
|
node2.right = node.left;
|
|
node.left = node2;
|
|
node4 = node;
|
|
}
|
|
else if (!flag && flag2)
|
|
{
|
|
node3.right = node.left;
|
|
node.left = node3;
|
|
node2.left = node.right;
|
|
node.right = node2;
|
|
node4 = node;
|
|
}
|
|
else
|
|
{
|
|
node3.right = node2.left;
|
|
node2.left = node3;
|
|
node4 = node2;
|
|
}
|
|
node3.FixSize();
|
|
node3.IsBlack = false;
|
|
if (node4 != node2)
|
|
{
|
|
node2.FixSize();
|
|
}
|
|
node4.IsBlack = true;
|
|
this.node_reparent((curpos != 4) ? path[curpos - 6] : null, node3, size, node4);
|
|
}
|
|
|
|
// Token: 0x0600006E RID: 110 RVA: 0x00003B10 File Offset: 0x00001D10
|
|
private void rebalance_delete__rotate_final(int curpos, List<RBTree.Node> path)
|
|
{
|
|
RBTree.Node node = path[curpos - 1];
|
|
RBTree.Node node2 = path[curpos - 2];
|
|
uint size = node2.Size;
|
|
bool isBlack = node2.IsBlack;
|
|
RBTree.Node node3;
|
|
if (node2.right == node)
|
|
{
|
|
if (node.right == null || node.right.IsBlack)
|
|
{
|
|
RBTree.Node left = node.left;
|
|
node2.right = left.left;
|
|
left.left = node2;
|
|
node.left = left.right;
|
|
left.right = node;
|
|
node3 = left;
|
|
}
|
|
else
|
|
{
|
|
node2.right = node.left;
|
|
node.left = node2;
|
|
node.right.IsBlack = true;
|
|
node3 = node;
|
|
}
|
|
}
|
|
else if (node.left == null || node.left.IsBlack)
|
|
{
|
|
RBTree.Node right = node.right;
|
|
node2.left = right.right;
|
|
right.right = node2;
|
|
node.right = right.left;
|
|
right.left = node;
|
|
node3 = right;
|
|
}
|
|
else
|
|
{
|
|
node2.left = node.right;
|
|
node.right = node2;
|
|
node.left.IsBlack = true;
|
|
node3 = node;
|
|
}
|
|
node2.FixSize();
|
|
node2.IsBlack = true;
|
|
if (node3 != node)
|
|
{
|
|
node.FixSize();
|
|
}
|
|
node3.IsBlack = isBlack;
|
|
this.node_reparent((curpos != 2) ? path[curpos - 4] : null, node2, size, node3);
|
|
}
|
|
|
|
// Token: 0x0600006F RID: 111 RVA: 0x00003C88 File Offset: 0x00001E88
|
|
private int ensure_sibling_black(int curpos, List<RBTree.Node> path)
|
|
{
|
|
RBTree.Node node = path[curpos];
|
|
RBTree.Node node2 = path[curpos - 1];
|
|
RBTree.Node node3 = path[curpos - 2];
|
|
uint size = node3.Size;
|
|
bool flag;
|
|
if (node3.right == node2)
|
|
{
|
|
node3.right = node2.left;
|
|
node2.left = node3;
|
|
flag = true;
|
|
}
|
|
else
|
|
{
|
|
node3.left = node2.right;
|
|
node2.right = node3;
|
|
flag = false;
|
|
}
|
|
node3.FixSize();
|
|
node3.IsBlack = false;
|
|
node2.IsBlack = true;
|
|
this.node_reparent((curpos != 2) ? path[curpos - 4] : null, node3, size, node2);
|
|
if (curpos + 1 == path.Count)
|
|
{
|
|
path.Add(null);
|
|
path.Add(null);
|
|
}
|
|
path[curpos - 2] = node2;
|
|
path[curpos - 1] = ((!flag) ? node2.left : node2.right);
|
|
path[curpos] = node3;
|
|
path[curpos + 1] = ((!flag) ? node3.left : node3.right);
|
|
path[curpos + 2] = node;
|
|
return curpos + 2;
|
|
}
|
|
|
|
// Token: 0x06000070 RID: 112 RVA: 0x00003DA4 File Offset: 0x00001FA4
|
|
private void node_reparent(RBTree.Node orig_parent, RBTree.Node orig, uint orig_size, RBTree.Node updated)
|
|
{
|
|
if (updated != null && updated.FixSize() != orig_size)
|
|
{
|
|
throw new SystemException("Internal error: rotation");
|
|
}
|
|
if (orig == this.root)
|
|
{
|
|
this.root = updated;
|
|
}
|
|
else if (orig == orig_parent.left)
|
|
{
|
|
orig_parent.left = updated;
|
|
}
|
|
else
|
|
{
|
|
if (orig != orig_parent.right)
|
|
{
|
|
throw new SystemException("Internal error: path error");
|
|
}
|
|
orig_parent.right = updated;
|
|
}
|
|
}
|
|
|
|
// Token: 0x06000071 RID: 113 RVA: 0x00003E28 File Offset: 0x00002028
|
|
private static RBTree.Node right_most(RBTree.Node current, RBTree.Node sibling, List<RBTree.Node> path)
|
|
{
|
|
for (;;)
|
|
{
|
|
path.Add(sibling);
|
|
path.Add(current);
|
|
if (current.right == null)
|
|
{
|
|
break;
|
|
}
|
|
sibling = current.left;
|
|
current = current.right;
|
|
}
|
|
return current;
|
|
}
|
|
|
|
// Token: 0x0400003D RID: 61
|
|
private RBTree.Node root;
|
|
|
|
// Token: 0x0400003E RID: 62
|
|
private object hlp;
|
|
|
|
// Token: 0x0400003F RID: 63
|
|
private uint version;
|
|
|
|
// Token: 0x04000040 RID: 64
|
|
[ThreadStatic]
|
|
private static List<RBTree.Node> cached_path;
|
|
|
|
// Token: 0x02000011 RID: 17
|
|
public interface INodeHelper<T>
|
|
{
|
|
// Token: 0x06000072 RID: 114
|
|
int Compare(T key, RBTree.Node node);
|
|
|
|
// Token: 0x06000073 RID: 115
|
|
RBTree.Node CreateNode(T key);
|
|
}
|
|
|
|
// Token: 0x02000012 RID: 18
|
|
public abstract class Node
|
|
{
|
|
// Token: 0x06000074 RID: 116 RVA: 0x00003E6C File Offset: 0x0000206C
|
|
public Node()
|
|
{
|
|
this.size_black = 2U;
|
|
}
|
|
|
|
// Token: 0x17000017 RID: 23
|
|
// (get) Token: 0x06000075 RID: 117 RVA: 0x00003E7C File Offset: 0x0000207C
|
|
// (set) Token: 0x06000076 RID: 118 RVA: 0x00003E8C File Offset: 0x0000208C
|
|
public bool IsBlack
|
|
{
|
|
get
|
|
{
|
|
return (this.size_black & 1U) == 1U;
|
|
}
|
|
set
|
|
{
|
|
this.size_black = ((!value) ? (this.size_black & 4294967294U) : (this.size_black | 1U));
|
|
}
|
|
}
|
|
|
|
// Token: 0x17000018 RID: 24
|
|
// (get) Token: 0x06000077 RID: 119 RVA: 0x00003EBC File Offset: 0x000020BC
|
|
// (set) Token: 0x06000078 RID: 120 RVA: 0x00003EC8 File Offset: 0x000020C8
|
|
public uint Size
|
|
{
|
|
get
|
|
{
|
|
return this.size_black >> 1;
|
|
}
|
|
set
|
|
{
|
|
this.size_black = (value << 1) | (this.size_black & 1U);
|
|
}
|
|
}
|
|
|
|
// Token: 0x06000079 RID: 121 RVA: 0x00003EDC File Offset: 0x000020DC
|
|
public uint FixSize()
|
|
{
|
|
this.Size = 1U;
|
|
if (this.left != null)
|
|
{
|
|
this.Size += this.left.Size;
|
|
}
|
|
if (this.right != null)
|
|
{
|
|
this.Size += this.right.Size;
|
|
}
|
|
return this.Size;
|
|
}
|
|
|
|
// Token: 0x0600007A RID: 122
|
|
public abstract void SwapValue(RBTree.Node other);
|
|
|
|
// Token: 0x04000041 RID: 65
|
|
private const uint black_mask = 1U;
|
|
|
|
// Token: 0x04000042 RID: 66
|
|
private const int black_shift = 1;
|
|
|
|
// Token: 0x04000043 RID: 67
|
|
public RBTree.Node left;
|
|
|
|
// Token: 0x04000044 RID: 68
|
|
public RBTree.Node right;
|
|
|
|
// Token: 0x04000045 RID: 69
|
|
private uint size_black;
|
|
}
|
|
|
|
// Token: 0x02000013 RID: 19
|
|
public struct NodeEnumerator : IEnumerator, IDisposable, IEnumerator<RBTree.Node>
|
|
{
|
|
// Token: 0x0600007B RID: 123 RVA: 0x00003F3C File Offset: 0x0000213C
|
|
internal NodeEnumerator(RBTree tree)
|
|
{
|
|
this.tree = tree;
|
|
this.version = tree.version;
|
|
this.pennants = null;
|
|
}
|
|
|
|
// Token: 0x17000019 RID: 25
|
|
// (get) Token: 0x0600007C RID: 124 RVA: 0x00003F58 File Offset: 0x00002158
|
|
object IEnumerator.Current
|
|
{
|
|
get
|
|
{
|
|
this.check_current();
|
|
return this.Current;
|
|
}
|
|
}
|
|
|
|
// Token: 0x0600007D RID: 125 RVA: 0x00003F68 File Offset: 0x00002168
|
|
public void Reset()
|
|
{
|
|
this.check_version();
|
|
this.pennants = null;
|
|
}
|
|
|
|
// Token: 0x1700001A RID: 26
|
|
// (get) Token: 0x0600007E RID: 126 RVA: 0x00003F78 File Offset: 0x00002178
|
|
public RBTree.Node Current
|
|
{
|
|
get
|
|
{
|
|
return this.pennants.Peek();
|
|
}
|
|
}
|
|
|
|
// Token: 0x0600007F RID: 127 RVA: 0x00003F88 File Offset: 0x00002188
|
|
public bool MoveNext()
|
|
{
|
|
this.check_version();
|
|
RBTree.Node node;
|
|
if (this.pennants == null)
|
|
{
|
|
if (this.tree.root == null)
|
|
{
|
|
return false;
|
|
}
|
|
this.pennants = new Stack<RBTree.Node>();
|
|
node = this.tree.root;
|
|
}
|
|
else
|
|
{
|
|
if (this.pennants.Count == 0)
|
|
{
|
|
return false;
|
|
}
|
|
RBTree.Node node2 = this.pennants.Pop();
|
|
node = node2.right;
|
|
}
|
|
while (node != null)
|
|
{
|
|
this.pennants.Push(node);
|
|
node = node.left;
|
|
}
|
|
return this.pennants.Count != 0;
|
|
}
|
|
|
|
// Token: 0x06000080 RID: 128 RVA: 0x00004028 File Offset: 0x00002228
|
|
public void Dispose()
|
|
{
|
|
this.tree = null;
|
|
this.pennants = null;
|
|
}
|
|
|
|
// Token: 0x06000081 RID: 129 RVA: 0x00004038 File Offset: 0x00002238
|
|
private void check_version()
|
|
{
|
|
if (this.tree == null)
|
|
{
|
|
throw new ObjectDisposedException("enumerator");
|
|
}
|
|
if (this.version != this.tree.version)
|
|
{
|
|
throw new InvalidOperationException("tree modified");
|
|
}
|
|
}
|
|
|
|
// Token: 0x06000082 RID: 130 RVA: 0x00004074 File Offset: 0x00002274
|
|
internal void check_current()
|
|
{
|
|
this.check_version();
|
|
if (this.pennants == null)
|
|
{
|
|
throw new InvalidOperationException("state invalid before the first MoveNext()");
|
|
}
|
|
}
|
|
|
|
// Token: 0x04000046 RID: 70
|
|
private RBTree tree;
|
|
|
|
// Token: 0x04000047 RID: 71
|
|
private uint version;
|
|
|
|
// Token: 0x04000048 RID: 72
|
|
private Stack<RBTree.Node> pennants;
|
|
}
|
|
}
|
|
}
|