Heap.cs 3.08 KB
Newer Older
Cody A Burchett's avatar
Cody A Burchett committed
1 2 3 4 5
using UnityEngine;
using System;
using System.Collections;
using System.Collections.Generic;

6
/*
Cody A Burchett's avatar
Cody A Burchett committed
7 8 9 10 11
public class Heap <Tile> where Tile : HeapItem<Tile>{

    Tile[] heapTiles;
    int itemCount;

Cody A Burchett's avatar
Cody A Burchett committed
12 13
    //replace openList with Heap

Cody A Burchett's avatar
Cody A Burchett committed
14 15
    //add heapIndex, compareTo to tile class
    //compare fCost of node then hCost
Cody A Burchett's avatar
Cody A Burchett committed
16
    //item.compareTo(item2) should return pos if item is less than item2, neg if item is greater than item2
Cody A Burchett's avatar
Cody A Burchett committed
17

Cody A Burchett's avatar
Cody A Burchett committed
18
    //create heap
Cody A Burchett's avatar
Cody A Burchett committed
19 20 21 22 23
    public Heap(int maxSize)
    {
        heapTiles = new Tile[maxSize];
    }

Cody A Burchett's avatar
Cody A Burchett committed
24
    //add item into heap and sort it into position
Cody A Burchett's avatar
Cody A Burchett committed
25 26 27 28 29 30 31 32
    public void Add(Tile item)
    {
        item.heapIndex = itemCount;
        heapTiles[itemCount] = item;
        SortUp(item);
        itemCount++;
    }

Cody A Burchett's avatar
Cody A Burchett committed
33
    //remove first tile and resort heap
Cody A Burchett's avatar
Cody A Burchett committed
34 35 36 37 38 39 40 41 42 43
    public Tile RemoveFirst()
    {
        Tile first = heapTiles[0];
        itemCount--;
        heapTiles[0] = heapTiles[itemCount];
        heapTiles[0].heapIndex = 0;
        SortDown(heapTiles[0]);
        return first;
    }

Cody A Burchett's avatar
Cody A Burchett committed
44
    //resort item position
Cody A Burchett's avatar
Cody A Burchett committed
45 46 47 48 49
    public void UpdateItem(Tile item)
    {
        SortUp(item);
    }

Cody A Burchett's avatar
Cody A Burchett committed
50
    
Cody A Burchett's avatar
Cody A Burchett committed
51 52 53 54 55 56 57 58
    public int Count
    {
        get
        {
            return itemCount;
        }
    }

Cody A Burchett's avatar
Cody A Burchett committed
59
    //does heap contain item
Cody A Burchett's avatar
Cody A Burchett committed
60 61 62 63 64
    public bool Contains(Tile item)
    {
        return Equals(heapTiles[item.heapIndex], item);
    }

Cody A Burchett's avatar
Cody A Burchett committed
65
    //sort tile lower into heap
Cody A Burchett's avatar
Cody A Burchett committed
66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101
    void SortDown(Tile item)
    {
        while (true)
        {
            int leftChildIndex = item.heapIndex * 2 + 1;
            int rightChildIndex = (item.heapIndex * 2) + 2;
            int swapIndex = 0;

            if (leftChildIndex < itemCount)
            {
                swapIndex = leftChildIndex;

                if (rightChildIndex < itemCount)
                {
                    if (heapTiles[leftChildIndex].CompareTo(heapTiles[rightChildIndex]) < 0)
                    {
                        swapIndex = rightChildIndex;
                    }
                }

                if (item.CompareTo(heapTiles[swapIndex]) < 0)
                {
                    Swap(item, heapTiles[swapIndex]);
                }
                else
                {
                    return;
                }
            }
            else
            {
                return;
            }
        }
    }

Cody A Burchett's avatar
Cody A Burchett committed
102
    //sort item higher into heap
Cody A Burchett's avatar
Cody A Burchett committed
103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122
    void SortUp(Tile item)
    {
        int indexOfParent = (item.heapIndex - 1) / 2;

        while (true)
        {
            Tile parent = heapTiles[indexOfParent];

            if (item.CompareTo(parent) > 0)
            {
                Swap(item, parent);
            }
            else
            {
                break;
            }
            indexOfParent = (item.heapIndex - 1) / 2;
        }
    }

Cody A Burchett's avatar
Cody A Burchett committed
123
    //swap tiles
Cody A Burchett's avatar
Cody A Burchett committed
124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141
    void Swap(Tile item1, Tile item2)
    {
        heapTiles[item1.heapIndex] = item2;
        heapTiles[item2.heapIndex] = item1;
        int tempIndex = item1.heapIndex;
        item1.heapIndex = item2.heapIndex;
        item2.heapIndex = tempIndex;
    }
}

public interface HeapItem<Tile> : IComparable<Tile>
{
    int heapIndex
    {
        get;

        set;
    }
142 143
}
*/