niko
144 lines
3.4 KiB
C#
144 lines
3.4 KiB
C#
using System;
|
|
|
|
namespace KDTree
|
|
{
|
|
// Token: 0x02000007 RID: 7
|
|
public class MinHeap<T>
|
|
{
|
|
// Token: 0x0600002A RID: 42 RVA: 0x00002FBD File Offset: 0x000011BD
|
|
public MinHeap()
|
|
: this(MinHeap<T>.DEFAULT_SIZE)
|
|
{
|
|
}
|
|
|
|
// Token: 0x0600002B RID: 43 RVA: 0x00002FCD File Offset: 0x000011CD
|
|
public MinHeap(int iCapacity)
|
|
{
|
|
this.tData = new T[iCapacity];
|
|
this.tKeys = new double[iCapacity];
|
|
this.Capacity = iCapacity;
|
|
this.Size = 0;
|
|
}
|
|
|
|
// Token: 0x17000009 RID: 9
|
|
// (get) Token: 0x0600002C RID: 44 RVA: 0x00003000 File Offset: 0x00001200
|
|
// (set) Token: 0x0600002D RID: 45 RVA: 0x00003017 File Offset: 0x00001217
|
|
public int Size { get; private set; }
|
|
|
|
// Token: 0x1700000A RID: 10
|
|
// (get) Token: 0x0600002E RID: 46 RVA: 0x00003020 File Offset: 0x00001220
|
|
// (set) Token: 0x0600002F RID: 47 RVA: 0x00003037 File Offset: 0x00001237
|
|
public int Capacity { get; private set; }
|
|
|
|
// Token: 0x06000030 RID: 48 RVA: 0x00003040 File Offset: 0x00001240
|
|
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.tData[this.Size] = value;
|
|
this.tKeys[this.Size] = key;
|
|
this.SiftUp(this.Size);
|
|
this.Size++;
|
|
}
|
|
|
|
// Token: 0x06000031 RID: 49 RVA: 0x00003100 File Offset: 0x00001300
|
|
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.SiftDown(0);
|
|
}
|
|
|
|
// Token: 0x1700000B RID: 11
|
|
// (get) Token: 0x06000032 RID: 50 RVA: 0x00003188 File Offset: 0x00001388
|
|
public T Min
|
|
{
|
|
get
|
|
{
|
|
if (this.Size == 0)
|
|
{
|
|
throw new Exception();
|
|
}
|
|
return this.tData[0];
|
|
}
|
|
}
|
|
|
|
// Token: 0x1700000C RID: 12
|
|
// (get) Token: 0x06000033 RID: 51 RVA: 0x000031BC File Offset: 0x000013BC
|
|
public double MinKey
|
|
{
|
|
get
|
|
{
|
|
if (this.Size == 0)
|
|
{
|
|
throw new Exception();
|
|
}
|
|
return this.tKeys[0];
|
|
}
|
|
}
|
|
|
|
// Token: 0x06000034 RID: 52 RVA: 0x000031EC File Offset: 0x000013EC
|
|
private void SiftUp(int iChild)
|
|
{
|
|
int num = (iChild - 1) / 2;
|
|
while (iChild != 0 && this.tKeys[iChild] < this.tKeys[num])
|
|
{
|
|
T t = this.tData[num];
|
|
double num2 = this.tKeys[num];
|
|
this.tData[num] = this.tData[iChild];
|
|
this.tKeys[num] = this.tKeys[iChild];
|
|
this.tData[iChild] = t;
|
|
this.tKeys[iChild] = num2;
|
|
iChild = num;
|
|
num = (iChild - 1) / 2;
|
|
}
|
|
}
|
|
|
|
// Token: 0x06000035 RID: 53 RVA: 0x00003280 File Offset: 0x00001480
|
|
private void SiftDown(int iParent)
|
|
{
|
|
for (int i = iParent * 2 + 1; i < this.Size; i = iParent * 2 + 1)
|
|
{
|
|
if (i + 1 < this.Size && this.tKeys[i] > this.tKeys[i + 1])
|
|
{
|
|
i++;
|
|
}
|
|
if (this.tKeys[iParent] <= this.tKeys[i])
|
|
{
|
|
break;
|
|
}
|
|
T t = this.tData[iParent];
|
|
double num = this.tKeys[iParent];
|
|
this.tData[iParent] = this.tData[i];
|
|
this.tKeys[iParent] = this.tKeys[i];
|
|
this.tData[i] = t;
|
|
this.tKeys[i] = num;
|
|
iParent = i;
|
|
}
|
|
}
|
|
|
|
// Token: 0x04000012 RID: 18
|
|
private static int DEFAULT_SIZE = 64;
|
|
|
|
// Token: 0x04000013 RID: 19
|
|
private T[] tData;
|
|
|
|
// Token: 0x04000014 RID: 20
|
|
private double[] tKeys;
|
|
}
|
|
}
|