niko
363 lines
7.5 KiB
C#
363 lines
7.5 KiB
C#
using System;
|
|
|
|
namespace KDTree
|
|
{
|
|
// Token: 0x02000004 RID: 4
|
|
public class IntervalHeap<T>
|
|
{
|
|
// Token: 0x06000006 RID: 6 RVA: 0x0000211D File Offset: 0x0000031D
|
|
public IntervalHeap()
|
|
: this(64)
|
|
{
|
|
}
|
|
|
|
// Token: 0x06000007 RID: 7 RVA: 0x0000212A File Offset: 0x0000032A
|
|
public IntervalHeap(int capacity)
|
|
{
|
|
this.tData = new T[capacity];
|
|
this.tKeys = new double[capacity];
|
|
this.Capacity = capacity;
|
|
this.Size = 0;
|
|
}
|
|
|
|
// Token: 0x17000001 RID: 1
|
|
// (get) Token: 0x06000008 RID: 8 RVA: 0x00002160 File Offset: 0x00000360
|
|
// (set) Token: 0x06000009 RID: 9 RVA: 0x00002177 File Offset: 0x00000377
|
|
public int Size { get; private set; }
|
|
|
|
// Token: 0x17000002 RID: 2
|
|
// (get) Token: 0x0600000A RID: 10 RVA: 0x00002180 File Offset: 0x00000380
|
|
// (set) Token: 0x0600000B RID: 11 RVA: 0x00002197 File Offset: 0x00000397
|
|
public int Capacity { get; private set; }
|
|
|
|
// Token: 0x17000003 RID: 3
|
|
// (get) Token: 0x0600000C RID: 12 RVA: 0x000021A0 File Offset: 0x000003A0
|
|
public T Min
|
|
{
|
|
get
|
|
{
|
|
if (this.Size == 0)
|
|
{
|
|
throw new Exception();
|
|
}
|
|
return this.tData[0];
|
|
}
|
|
}
|
|
|
|
// Token: 0x17000004 RID: 4
|
|
// (get) Token: 0x0600000D RID: 13 RVA: 0x000021D4 File Offset: 0x000003D4
|
|
public T Max
|
|
{
|
|
get
|
|
{
|
|
if (this.Size == 0)
|
|
{
|
|
throw new Exception();
|
|
}
|
|
T t;
|
|
if (this.Size == 1)
|
|
{
|
|
t = this.tData[0];
|
|
}
|
|
else
|
|
{
|
|
t = this.tData[1];
|
|
}
|
|
return t;
|
|
}
|
|
}
|
|
|
|
// Token: 0x17000005 RID: 5
|
|
// (get) Token: 0x0600000E RID: 14 RVA: 0x0000222C File Offset: 0x0000042C
|
|
public double MinKey
|
|
{
|
|
get
|
|
{
|
|
if (this.Size == 0)
|
|
{
|
|
throw new Exception();
|
|
}
|
|
return this.tKeys[0];
|
|
}
|
|
}
|
|
|
|
// Token: 0x17000006 RID: 6
|
|
// (get) Token: 0x0600000F RID: 15 RVA: 0x0000225C File Offset: 0x0000045C
|
|
public double MaxKey
|
|
{
|
|
get
|
|
{
|
|
if (this.Size == 0)
|
|
{
|
|
throw new Exception();
|
|
}
|
|
double num;
|
|
if (this.Size == 1)
|
|
{
|
|
num = this.tKeys[0];
|
|
}
|
|
else
|
|
{
|
|
num = this.tKeys[1];
|
|
}
|
|
return num;
|
|
}
|
|
}
|
|
|
|
// Token: 0x06000010 RID: 16 RVA: 0x000022AC File Offset: 0x000004AC
|
|
public void Insert(double key, T value)
|
|
{
|
|
if (this.Size >= this.Capacity)
|
|
{
|
|
this.Capacity *= 2;
|
|
T[] array = new T[this.Capacity];
|
|
Array.Copy(this.tData, array, this.tData.Length);
|
|
this.tData = array;
|
|
double[] array2 = new double[this.Capacity];
|
|
Array.Copy(this.tKeys, array2, this.tKeys.Length);
|
|
this.tKeys = array2;
|
|
}
|
|
this.Size++;
|
|
this.tData[this.Size - 1] = value;
|
|
this.tKeys[this.Size - 1] = key;
|
|
this.SiftInsertedValueUp();
|
|
}
|
|
|
|
// Token: 0x06000011 RID: 17 RVA: 0x00002368 File Offset: 0x00000568
|
|
public void RemoveMin()
|
|
{
|
|
if (this.Size == 0)
|
|
{
|
|
throw new Exception();
|
|
}
|
|
this.Size--;
|
|
this.tData[0] = this.tData[this.Size];
|
|
this.tKeys[0] = this.tKeys[this.Size];
|
|
this.tData[this.Size] = default(T);
|
|
this.SiftDownMin(0);
|
|
}
|
|
|
|
// Token: 0x06000012 RID: 18 RVA: 0x000023F0 File Offset: 0x000005F0
|
|
public void ReplaceMin(double key, T value)
|
|
{
|
|
if (this.Size == 0)
|
|
{
|
|
throw new Exception();
|
|
}
|
|
this.tData[0] = value;
|
|
this.tKeys[0] = key;
|
|
if (this.Size > 1)
|
|
{
|
|
if (this.tKeys[1] < key)
|
|
{
|
|
this.Swap(0, 1);
|
|
}
|
|
this.SiftDownMin(0);
|
|
}
|
|
}
|
|
|
|
// Token: 0x06000013 RID: 19 RVA: 0x00002460 File Offset: 0x00000660
|
|
public void RemoveMax()
|
|
{
|
|
if (this.Size == 0)
|
|
{
|
|
throw new Exception();
|
|
}
|
|
if (this.Size == 1)
|
|
{
|
|
this.RemoveMin();
|
|
}
|
|
else
|
|
{
|
|
this.Size--;
|
|
this.tData[1] = this.tData[this.Size];
|
|
this.tKeys[1] = this.tKeys[this.Size];
|
|
this.tData[this.Size] = default(T);
|
|
this.SiftDownMax(1);
|
|
}
|
|
}
|
|
|
|
// Token: 0x06000014 RID: 20 RVA: 0x00002504 File Offset: 0x00000704
|
|
public void ReplaceMax(double key, T value)
|
|
{
|
|
if (this.Size == 0)
|
|
{
|
|
throw new Exception();
|
|
}
|
|
if (this.Size == 1)
|
|
{
|
|
this.ReplaceMin(key, value);
|
|
}
|
|
else
|
|
{
|
|
this.tData[1] = value;
|
|
this.tKeys[1] = key;
|
|
if (key < this.tKeys[0])
|
|
{
|
|
this.Swap(0, 1);
|
|
}
|
|
this.SiftDownMax(1);
|
|
}
|
|
}
|
|
|
|
// Token: 0x06000015 RID: 21 RVA: 0x00002580 File Offset: 0x00000780
|
|
private int Swap(int x, int y)
|
|
{
|
|
T t = this.tData[y];
|
|
double num = this.tKeys[y];
|
|
this.tData[y] = this.tData[x];
|
|
this.tKeys[y] = this.tKeys[x];
|
|
this.tData[x] = t;
|
|
this.tKeys[x] = num;
|
|
return y;
|
|
}
|
|
|
|
// Token: 0x06000016 RID: 22 RVA: 0x000025E8 File Offset: 0x000007E8
|
|
private void SiftInsertedValueUp()
|
|
{
|
|
int num = this.Size - 1;
|
|
if (num != 0)
|
|
{
|
|
if (num == 1)
|
|
{
|
|
if (this.tKeys[num] < this.tKeys[num - 1])
|
|
{
|
|
this.Swap(num, num - 1);
|
|
}
|
|
}
|
|
else if (num % 2 == 1)
|
|
{
|
|
int num2 = (num / 2 - 1) | 1;
|
|
if (this.tKeys[num] < this.tKeys[num - 1])
|
|
{
|
|
num = this.Swap(num, num - 1);
|
|
if (this.tKeys[num] < this.tKeys[num2 - 1])
|
|
{
|
|
num = this.Swap(num, num2 - 1);
|
|
this.SiftUpMin(num);
|
|
}
|
|
}
|
|
else if (this.tKeys[num] > this.tKeys[num2])
|
|
{
|
|
num = this.Swap(num, num2);
|
|
this.SiftUpMax(num);
|
|
}
|
|
}
|
|
else
|
|
{
|
|
int num2 = (num / 2 - 1) | 1;
|
|
if (this.tKeys[num] > this.tKeys[num2])
|
|
{
|
|
num = this.Swap(num, num2);
|
|
this.SiftUpMax(num);
|
|
}
|
|
else if (this.tKeys[num] < this.tKeys[num2 - 1])
|
|
{
|
|
num = this.Swap(num, num2 - 1);
|
|
this.SiftUpMin(num);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
// Token: 0x06000017 RID: 23 RVA: 0x00002758 File Offset: 0x00000958
|
|
private void SiftUpMin(int iChild)
|
|
{
|
|
int num = (iChild / 2 - 1) & -2;
|
|
while (num >= 0 && this.tKeys[iChild] < this.tKeys[num])
|
|
{
|
|
this.Swap(iChild, num);
|
|
iChild = num;
|
|
num = (iChild / 2 - 1) & -2;
|
|
}
|
|
}
|
|
|
|
// Token: 0x06000018 RID: 24 RVA: 0x000027A8 File Offset: 0x000009A8
|
|
private void SiftUpMax(int iChild)
|
|
{
|
|
int num = (iChild / 2 - 1) | 1;
|
|
while (num >= 0 && this.tKeys[iChild] > this.tKeys[num])
|
|
{
|
|
this.Swap(iChild, num);
|
|
iChild = num;
|
|
num = (iChild / 2 - 1) | 1;
|
|
}
|
|
}
|
|
|
|
// Token: 0x06000019 RID: 25 RVA: 0x000027F4 File Offset: 0x000009F4
|
|
private void SiftDownMin(int iParent)
|
|
{
|
|
for (int i = iParent * 2 + 2; i < this.Size; i = iParent * 2 + 2)
|
|
{
|
|
if (i + 2 < this.Size && this.tKeys[i + 2] < this.tKeys[i])
|
|
{
|
|
i += 2;
|
|
}
|
|
if (this.tKeys[i] >= this.tKeys[iParent])
|
|
{
|
|
break;
|
|
}
|
|
this.Swap(iParent, i);
|
|
if (i + 1 < this.Size && this.tKeys[i + 1] < this.tKeys[i])
|
|
{
|
|
this.Swap(i, i + 1);
|
|
}
|
|
iParent = i;
|
|
}
|
|
}
|
|
|
|
// Token: 0x0600001A RID: 26 RVA: 0x000028B8 File Offset: 0x00000AB8
|
|
private void SiftDownMax(int iParent)
|
|
{
|
|
for (int i = iParent * 2 + 1; i <= this.Size; i = iParent * 2 + 1)
|
|
{
|
|
if (i == this.Size)
|
|
{
|
|
if (this.tKeys[i - 1] > this.tKeys[iParent])
|
|
{
|
|
this.Swap(iParent, i - 1);
|
|
}
|
|
break;
|
|
}
|
|
if (i + 2 == this.Size)
|
|
{
|
|
if (this.tKeys[i + 1] > this.tKeys[i])
|
|
{
|
|
if (this.tKeys[i + 1] > this.tKeys[iParent])
|
|
{
|
|
this.Swap(iParent, i + 1);
|
|
}
|
|
break;
|
|
}
|
|
}
|
|
else if (i + 2 < this.Size)
|
|
{
|
|
if (this.tKeys[i + 2] > this.tKeys[i])
|
|
{
|
|
i += 2;
|
|
}
|
|
}
|
|
if (this.tKeys[i] <= this.tKeys[iParent])
|
|
{
|
|
break;
|
|
}
|
|
this.Swap(iParent, i);
|
|
if (this.tKeys[i - 1] > this.tKeys[i])
|
|
{
|
|
this.Swap(i, i - 1);
|
|
}
|
|
iParent = i;
|
|
}
|
|
}
|
|
|
|
// Token: 0x04000001 RID: 1
|
|
private const int DEFAULT_SIZE = 64;
|
|
|
|
// Token: 0x04000002 RID: 2
|
|
private T[] tData;
|
|
|
|
// Token: 0x04000003 RID: 3
|
|
private double[] tKeys;
|
|
}
|
|
}
|