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;
		}
	}
}