using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Runtime.Serialization.Formatters.Binary;
using System.Text;

namespace KdTree
{
	// Token: 0x02000009 RID: 9
	[Serializable]
	public class KdTree<TKey, TValue> : IKdTree<TKey, TValue>, IEnumerable<KdTreeNode<TKey, TValue>>, IEnumerable
	{
		// Token: 0x06000024 RID: 36 RVA: 0x000021D5 File Offset: 0x000003D5
		public KdTree(int dimensions, ITypeMath<TKey> typeMath)
		{
			this.dimensions = dimensions;
			this.typeMath = typeMath;
			this.Count = 0;
		}

		// Token: 0x06000025 RID: 37 RVA: 0x000021F2 File Offset: 0x000003F2
		public KdTree(int dimensions, ITypeMath<TKey> typeMath, AddDuplicateBehavior addDuplicateBehavior)
			: this(dimensions, typeMath)
		{
			this.AddDuplicateBehavior = addDuplicateBehavior;
		}

		// Token: 0x1700000A RID: 10
		// (get) Token: 0x06000026 RID: 38 RVA: 0x00002203 File Offset: 0x00000403
		// (set) Token: 0x06000027 RID: 39 RVA: 0x0000220B File Offset: 0x0000040B
		public AddDuplicateBehavior AddDuplicateBehavior { get; private set; }

		// Token: 0x06000028 RID: 40 RVA: 0x00002214 File Offset: 0x00000414
		public bool Add(TKey[] point, TValue value)
		{
			KdTreeNode<TKey, TValue> kdTreeNode = new KdTreeNode<TKey, TValue>(point, value);
			if (this.root == null)
			{
				this.root = new KdTreeNode<TKey, TValue>(point, value);
			}
			else
			{
				int num = -1;
				KdTreeNode<TKey, TValue> kdTreeNode2 = this.root;
				int num2;
				for (;;)
				{
					num = (num + 1) % this.dimensions;
					if (this.typeMath.AreEqual(point, kdTreeNode2.Point))
					{
						switch (this.AddDuplicateBehavior)
						{
						case AddDuplicateBehavior.Skip:
							return false;
						case AddDuplicateBehavior.Error:
							goto IL_6D;
						case AddDuplicateBehavior.Update:
							kdTreeNode2.Value = value;
							goto IL_90;
						case AddDuplicateBehavior.Collect:
							goto IL_7C;
						}
						break;
					}
					IL_90:
					num2 = this.typeMath.Compare(point[num], kdTreeNode2.Point[num]);
					if (kdTreeNode2[num2] == null)
					{
						goto Block_4;
					}
					kdTreeNode2 = kdTreeNode2[num2];
				}
				throw new Exception("Unexpected AddDuplicateBehavior");
				IL_6D:
				throw new DuplicateNodeError();
				IL_7C:
				kdTreeNode2.AddDuplicate(value);
				return false;
				Block_4:
				kdTreeNode2[num2] = kdTreeNode;
			}
			int count = this.Count;
			this.Count = count + 1;
			return true;
		}

		// Token: 0x06000029 RID: 41 RVA: 0x00002304 File Offset: 0x00000504
		private void ReadChildNodes(KdTreeNode<TKey, TValue> removedNode)
		{
			if (removedNode.IsLeaf)
			{
				return;
			}
			Queue<KdTreeNode<TKey, TValue>> queue = new Queue<KdTreeNode<TKey, TValue>>();
			Queue<KdTreeNode<TKey, TValue>> queue2 = new Queue<KdTreeNode<TKey, TValue>>();
			if (removedNode.LeftChild != null)
			{
				queue2.Enqueue(removedNode.LeftChild);
			}
			if (removedNode.RightChild != null)
			{
				queue2.Enqueue(removedNode.RightChild);
			}
			while (queue2.Count > 0)
			{
				KdTreeNode<TKey, TValue> kdTreeNode = queue2.Dequeue();
				queue.Enqueue(kdTreeNode);
				for (int i = -1; i <= 1; i += 2)
				{
					if (kdTreeNode[i] != null)
					{
						queue2.Enqueue(kdTreeNode[i]);
						kdTreeNode[i] = null;
					}
				}
			}
			while (queue.Count > 0)
			{
				KdTreeNode<TKey, TValue> kdTreeNode2 = queue.Dequeue();
				int count = this.Count;
				this.Count = count - 1;
				this.Add(kdTreeNode2.Point, kdTreeNode2.Value);
			}
		}

		// Token: 0x0600002A RID: 42 RVA: 0x000023CC File Offset: 0x000005CC
		public void RemoveAt(TKey[] point)
		{
			if (this.root == null)
			{
				return;
			}
			KdTreeNode<TKey, TValue> kdTreeNode;
			if (this.typeMath.AreEqual(point, this.root.Point))
			{
				kdTreeNode = this.root;
				this.root = null;
				int num = this.Count;
				this.Count = num - 1;
				this.ReadChildNodes(kdTreeNode);
				return;
			}
			kdTreeNode = this.root;
			int num2 = -1;
			for (;;)
			{
				num2 = (num2 + 1) % this.dimensions;
				int num3 = this.typeMath.Compare(point[num2], kdTreeNode.Point[num2]);
				if (kdTreeNode[num3] == null)
				{
					break;
				}
				if (this.typeMath.AreEqual(point, kdTreeNode[num3].Point))
				{
					KdTreeNode<TKey, TValue> kdTreeNode2 = kdTreeNode[num3];
					kdTreeNode[num3] = null;
					int num = this.Count;
					this.Count = num - 1;
					this.ReadChildNodes(kdTreeNode2);
				}
				else
				{
					kdTreeNode = kdTreeNode[num3];
				}
				if (kdTreeNode == null)
				{
					return;
				}
			}
		}

		// Token: 0x0600002B RID: 43 RVA: 0x000024B4 File Offset: 0x000006B4
		public KdTreeNode<TKey, TValue>[] GetNearestNeighbours(TKey[] point, int count)
		{
			if (count > this.Count)
			{
				count = this.Count;
			}
			if (count < 0)
			{
				throw new ArgumentException("Number of neighbors cannot be negative");
			}
			if (count == 0)
			{
				return new KdTreeNode<TKey, TValue>[0];
			}
			new KdTreeNode<TKey, TValue>[count];
			NearestNeighbourList<KdTreeNode<TKey, TValue>, TKey> nearestNeighbourList = new NearestNeighbourList<KdTreeNode<TKey, TValue>, TKey>(count, this.typeMath);
			HyperRect<TKey> hyperRect = HyperRect<TKey>.Infinite(this.dimensions, this.typeMath);
			this.AddNearestNeighbours(this.root, point, hyperRect, 0, nearestNeighbourList, this.typeMath.MaxValue);
			count = nearestNeighbourList.Count;
			KdTreeNode<TKey, TValue>[] array = new KdTreeNode<TKey, TValue>[count];
			for (int i = 0; i < count; i++)
			{
				array[count - i - 1] = nearestNeighbourList.RemoveFurtherest();
			}
			return array;
		}

		// Token: 0x0600002C RID: 44 RVA: 0x00002558 File Offset: 0x00000758
		private void AddNearestNeighbours(KdTreeNode<TKey, TValue> node, TKey[] target, HyperRect<TKey> rect, int depth, NearestNeighbourList<KdTreeNode<TKey, TValue>, TKey> nearestNeighbours, TKey maxSearchRadiusSquared)
		{
			if (node == null)
			{
				return;
			}
			int num = depth % this.dimensions;
			HyperRect<TKey> hyperRect = rect.Clone();
			hyperRect.MaxPoint[num] = node.Point[num];
			HyperRect<TKey> hyperRect2 = rect.Clone();
			hyperRect2.MinPoint[num] = node.Point[num];
			int num2 = this.typeMath.Compare(target[num], node.Point[num]);
			HyperRect<TKey> hyperRect3 = ((num2 <= 0) ? hyperRect : hyperRect2);
			HyperRect<TKey> hyperRect4 = ((num2 <= 0) ? hyperRect2 : hyperRect);
			KdTreeNode<TKey, TValue> kdTreeNode = ((num2 <= 0) ? node.LeftChild : node.RightChild);
			KdTreeNode<TKey, TValue> kdTreeNode2 = ((num2 <= 0) ? node.RightChild : node.LeftChild);
			if (kdTreeNode != null)
			{
				this.AddNearestNeighbours(kdTreeNode, target, hyperRect3, depth + 1, nearestNeighbours, maxSearchRadiusSquared);
			}
			TKey[] closestPoint = hyperRect4.GetClosestPoint(target, this.typeMath);
			TKey tkey = this.typeMath.DistanceSquaredBetweenPoints(closestPoint, target);
			if (this.typeMath.Compare(tkey, maxSearchRadiusSquared) <= 0)
			{
				if (nearestNeighbours.IsCapacityReached)
				{
					if (this.typeMath.Compare(tkey, nearestNeighbours.GetFurtherestDistance()) < 0)
					{
						this.AddNearestNeighbours(kdTreeNode2, target, hyperRect4, depth + 1, nearestNeighbours, maxSearchRadiusSquared);
					}
				}
				else
				{
					this.AddNearestNeighbours(kdTreeNode2, target, hyperRect4, depth + 1, nearestNeighbours, maxSearchRadiusSquared);
				}
			}
			tkey = this.typeMath.DistanceSquaredBetweenPoints(node.Point, target);
			if (this.typeMath.Compare(tkey, maxSearchRadiusSquared) <= 0)
			{
				nearestNeighbours.Add(node, tkey);
			}
		}

		// Token: 0x0600002D RID: 45 RVA: 0x000026D0 File Offset: 0x000008D0
		public KdTreeNode<TKey, TValue>[] RadialSearch(TKey[] center, TKey radius, int count)
		{
			NearestNeighbourList<KdTreeNode<TKey, TValue>, TKey> nearestNeighbourList = new NearestNeighbourList<KdTreeNode<TKey, TValue>, TKey>(count, this.typeMath);
			this.AddNearestNeighbours(this.root, center, HyperRect<TKey>.Infinite(this.dimensions, this.typeMath), 0, nearestNeighbourList, this.typeMath.Multiply(radius, radius));
			count = nearestNeighbourList.Count;
			KdTreeNode<TKey, TValue>[] array = new KdTreeNode<TKey, TValue>[count];
			for (int i = 0; i < count; i++)
			{
				array[count - i - 1] = nearestNeighbourList.RemoveFurtherest();
			}
			return array;
		}

		// Token: 0x1700000B RID: 11
		// (get) Token: 0x0600002E RID: 46 RVA: 0x00002740 File Offset: 0x00000940
		// (set) Token: 0x0600002F RID: 47 RVA: 0x00002748 File Offset: 0x00000948
		public int Count { get; private set; }

		// Token: 0x06000030 RID: 48 RVA: 0x00002754 File Offset: 0x00000954
		public bool TryFindValueAt(TKey[] point, out TValue value)
		{
			KdTreeNode<TKey, TValue> kdTreeNode = this.root;
			int num = -1;
			while (kdTreeNode != null)
			{
				if (this.typeMath.AreEqual(point, kdTreeNode.Point))
				{
					value = kdTreeNode.Value;
					return true;
				}
				num = (num + 1) % this.dimensions;
				int num2 = this.typeMath.Compare(point[num], kdTreeNode.Point[num]);
				kdTreeNode = kdTreeNode[num2];
			}
			value = default(TValue);
			return false;
		}

		// Token: 0x06000031 RID: 49 RVA: 0x000027CC File Offset: 0x000009CC
		public TValue FindValueAt(TKey[] point)
		{
			TValue tvalue;
			if (this.TryFindValueAt(point, out tvalue))
			{
				return tvalue;
			}
			return default(TValue);
		}

		// Token: 0x06000032 RID: 50 RVA: 0x000027F0 File Offset: 0x000009F0
		public bool TryFindValue(TValue value, out TKey[] point)
		{
			if (this.root == null)
			{
				point = null;
				return false;
			}
			Queue<KdTreeNode<TKey, TValue>> queue = new Queue<KdTreeNode<TKey, TValue>>();
			queue.Enqueue(this.root);
			while (queue.Count > 0)
			{
				KdTreeNode<TKey, TValue> kdTreeNode = queue.Dequeue();
				if (kdTreeNode.Value.Equals(value))
				{
					point = kdTreeNode.Point;
					return true;
				}
				for (int i = -1; i <= 1; i += 2)
				{
					KdTreeNode<TKey, TValue> kdTreeNode2 = kdTreeNode[i];
					if (kdTreeNode2 != null)
					{
						queue.Enqueue(kdTreeNode2);
					}
				}
			}
			point = null;
			return false;
		}

		// Token: 0x06000033 RID: 51 RVA: 0x00002874 File Offset: 0x00000A74
		public TKey[] FindValue(TValue value)
		{
			TKey[] array;
			if (this.TryFindValue(value, out array))
			{
				return array;
			}
			return null;
		}

		// Token: 0x06000034 RID: 52 RVA: 0x00002890 File Offset: 0x00000A90
		private void AddNodeToStringBuilder(KdTreeNode<TKey, TValue> node, StringBuilder sb, int depth)
		{
			sb.AppendLine(node.ToString());
			for (int i = -1; i <= 1; i += 2)
			{
				for (int j = 0; j <= depth; j++)
				{
					sb.Append("\t");
				}
				sb.Append((i == -1) ? "L " : "R ");
				if (node[i] == null)
				{
					sb.AppendLine("");
				}
				else
				{
					this.AddNodeToStringBuilder(node[i], sb, depth + 1);
				}
			}
		}

		// Token: 0x06000035 RID: 53 RVA: 0x00002910 File Offset: 0x00000B10
		public override string ToString()
		{
			if (this.root == null)
			{
				return "";
			}
			StringBuilder stringBuilder = new StringBuilder();
			this.AddNodeToStringBuilder(this.root, stringBuilder, 0);
			return stringBuilder.ToString();
		}

		// Token: 0x06000036 RID: 54 RVA: 0x00002948 File Offset: 0x00000B48
		private void AddNodesToList(KdTreeNode<TKey, TValue> node, List<KdTreeNode<TKey, TValue>> nodes)
		{
			if (node == null)
			{
				return;
			}
			nodes.Add(node);
			for (int i = -1; i <= 1; i += 2)
			{
				if (node[i] != null)
				{
					this.AddNodesToList(node[i], nodes);
					node[i] = null;
				}
			}
		}

		// Token: 0x06000037 RID: 55 RVA: 0x0000298C File Offset: 0x00000B8C
		private void SortNodesArray(KdTreeNode<TKey, TValue>[] nodes, int byDimension, int fromIndex, int toIndex)
		{
			for (int i = fromIndex + 1; i <= toIndex; i++)
			{
				int num = i;
				for (;;)
				{
					KdTreeNode<TKey, TValue> kdTreeNode = nodes[num - 1];
					KdTreeNode<TKey, TValue> kdTreeNode2 = nodes[num];
					if (this.typeMath.Compare(kdTreeNode2.Point[byDimension], kdTreeNode.Point[byDimension]) >= 0)
					{
						break;
					}
					nodes[num - 1] = kdTreeNode2;
					nodes[num] = kdTreeNode;
				}
			}
		}

		// Token: 0x06000038 RID: 56 RVA: 0x000029E8 File Offset: 0x00000BE8
		private void AddNodesBalanced(KdTreeNode<TKey, TValue>[] nodes, int byDimension, int fromIndex, int toIndex)
		{
			if (fromIndex == toIndex)
			{
				this.Add(nodes[fromIndex].Point, nodes[fromIndex].Value);
				nodes[fromIndex] = null;
				return;
			}
			this.SortNodesArray(nodes, byDimension, fromIndex, toIndex);
			int num = fromIndex + (int)Math.Round((double)((float)(toIndex + 1 - fromIndex) / 2f)) - 1;
			this.Add(nodes[num].Point, nodes[num].Value);
			nodes[num] = null;
			int num2 = (byDimension + 1) % this.dimensions;
			if (fromIndex < num)
			{
				this.AddNodesBalanced(nodes, num2, fromIndex, num - 1);
			}
			if (toIndex > num)
			{
				this.AddNodesBalanced(nodes, num2, num + 1, toIndex);
			}
		}

		// Token: 0x06000039 RID: 57 RVA: 0x00002A84 File Offset: 0x00000C84
		public void Balance()
		{
			List<KdTreeNode<TKey, TValue>> list = new List<KdTreeNode<TKey, TValue>>();
			this.AddNodesToList(this.root, list);
			this.Clear();
			this.AddNodesBalanced(list.ToArray(), 0, 0, list.Count - 1);
		}

		// Token: 0x0600003A RID: 58 RVA: 0x00002AC0 File Offset: 0x00000CC0
		private void RemoveChildNodes(KdTreeNode<TKey, TValue> node)
		{
			for (int i = -1; i <= 1; i += 2)
			{
				if (node[i] != null)
				{
					this.RemoveChildNodes(node[i]);
					node[i] = null;
				}
			}
		}

		// Token: 0x0600003B RID: 59 RVA: 0x00002AF7 File Offset: 0x00000CF7
		public void Clear()
		{
			if (this.root != null)
			{
				this.RemoveChildNodes(this.root);
			}
		}

		// Token: 0x0600003C RID: 60 RVA: 0x00002B10 File Offset: 0x00000D10
		public void SaveToFile(string filename)
		{
			BinaryFormatter binaryFormatter = new BinaryFormatter();
			using (FileStream fileStream = File.Create(filename))
			{
				binaryFormatter.Serialize(fileStream, this);
				fileStream.Flush();
			}
		}

		// Token: 0x0600003D RID: 61 RVA: 0x00002B54 File Offset: 0x00000D54
		public static KdTree<TKey, TValue> LoadFromFile(string filename)
		{
			BinaryFormatter binaryFormatter = new BinaryFormatter();
			KdTree<TKey, TValue> kdTree;
			using (FileStream fileStream = File.Open(filename, FileMode.Open))
			{
				kdTree = (KdTree<TKey, TValue>)binaryFormatter.Deserialize(fileStream);
			}
			return kdTree;
		}

		// Token: 0x0600003E RID: 62 RVA: 0x00002B9C File Offset: 0x00000D9C
		public IEnumerator<KdTreeNode<TKey, TValue>> GetEnumerator()
		{
			Stack<KdTreeNode<TKey, TValue>> left = new Stack<KdTreeNode<TKey, TValue>>();
			Stack<KdTreeNode<TKey, TValue>> right = new Stack<KdTreeNode<TKey, TValue>>();
			Action<KdTreeNode<TKey, TValue>> addLeft = delegate(KdTreeNode<TKey, TValue> node)
			{
				if (node.LeftChild != null)
				{
					left.Push(node.LeftChild);
				}
			};
			Action<KdTreeNode<TKey, TValue>> addRight = delegate(KdTreeNode<TKey, TValue> node)
			{
				if (node.RightChild != null)
				{
					right.Push(node.RightChild);
				}
			};
			if (this.root != null)
			{
				yield return this.root;
				addLeft(this.root);
				addRight(this.root);
				for (;;)
				{
					if (left.Any<KdTreeNode<TKey, TValue>>())
					{
						KdTreeNode<TKey, TValue> kdTreeNode = left.Pop();
						addLeft(kdTreeNode);
						addRight(kdTreeNode);
						yield return kdTreeNode;
					}
					else
					{
						if (!right.Any<KdTreeNode<TKey, TValue>>())
						{
							break;
						}
						KdTreeNode<TKey, TValue> kdTreeNode2 = right.Pop();
						addLeft(kdTreeNode2);
						addRight(kdTreeNode2);
						yield return kdTreeNode2;
					}
				}
			}
			yield break;
		}

		// Token: 0x0600003F RID: 63 RVA: 0x00002BAB File Offset: 0x00000DAB
		IEnumerator IEnumerable.GetEnumerator()
		{
			return this.GetEnumerator();
		}

		// Token: 0x0400000A RID: 10
		private int dimensions;

		// Token: 0x0400000B RID: 11
		private ITypeMath<TKey> typeMath;

		// Token: 0x0400000C RID: 12
		private KdTreeNode<TKey, TValue> root;
	}
}