Newer
Older
TheVengeance-Project-IADE-Unity2D / Assets / Scripts / NPC / Pathfinding / Heap.cs
  1. using System;
  2. using System.Collections;
  3. using System.Collections.Generic;
  4. using UnityEditor.Localization.Plugins.XLIFF.V12;
  5. using UnityEditor;
  6. using UnityEngine;
  7. namespace MyCollections.Generic.Heap
  8. {
  9. public class Heap<T> where T : IheapItem<T>
  10. {
  11. //Variables
  12. private T[] items;
  13. private int currentItemCount; // Number items are currently in the heap
  14. //Properties
  15. public int Count => currentItemCount;//Gets the current number of items stored on the Heap
  16. //Constructor
  17. //Initializes the heap given maximum size
  18. public Heap(int maxheapSize) => items = new T[maxheapSize];
  19. //Adds a new item to the heap
  20. public void Add(T item)
  21. {
  22. item.HeapIndex = currentItemCount; //The items HeapIndex is set to the current item count.
  23. //This ensures the item knows its position within the array
  24. items[currentItemCount] = item; //The item is placed in the next available spot in the array.
  25. SortUp(item); //The item is sorted upwards in the heap to maintain the heap property
  26. currentItemCount++; //The count of items is incremented after successfully adding the item
  27. }
  28. //Removes and returns the top (or "first") item from the heap,
  29. //which is typically the item with the highest priority (depending on the type of heap).
  30. public T RemoveFirst()
  31. {
  32. T firstItem = items[0]; //The item at the top(index 0) is stored in first item to be returned later
  33. currentItemCount--; //The item count is decremented since we are removing an item.
  34. items[0] = items[currentItemCount]; //The last item in the heap is moved to the top to fill the gap left by the removed item.
  35. items[0].HeapIndex = 0; // The moved item's index is updated to reflect its new position at the top.
  36. SortDown(items[0]); //The moved item is sorted downward to maintain the heap structure.
  37. return firstItem; //The removed item is returned
  38. }
  39. //If an item in the heap has changed (e.g., its priority),
  40. //this method sorts it back up to ensure the heap maintains the correct order.
  41. //It assumes the item may have moved up in priority
  42. public void UpdateItem(T item) => SortUp(item);
  43. //This checks if a specific item exists in the heap by comparing the items position in the heap (item.HeapIndex)
  44. //to the actual object at that index
  45. public bool Contains(T item) => Equals(items[item.HeapIndex], item);
  46. //This method maintains heap order after removing an item by moving the root element downwards
  47. private void SortDown(T item)
  48. {
  49. while (true)
  50. {
  51. //Gets the left child index
  52. int childIndexLeft = item.HeapIndex * 2 + 1;
  53. //Gets the right child index
  54. int childIndexRight = item.HeapIndex * 2 + 2;
  55. //is initialized to track which child (if any)
  56. //the current node needs to be swapped with during the sorting process.
  57. int swapIndex = 0;
  58. //This checks if the current node (item) has a left child
  59. //if childIndexLeft is out of bounds (i.e., greater than or equal to currentItemCount),
  60. //the node has no children, and the method can terminate early.
  61. if (childIndexLeft < currentItemCount)
  62. {
  63. //Stores the child to swap
  64. swapIndex = childIndexLeft;
  65. //This checks if the current node (item) has a right child
  66. if (childIndexRight < currentItemCount)
  67. {
  68. //If the left child is smaller (or less preferred), the swapIndex remains as the left child
  69. //If the right child is smaller(or less preferred), swapIndex is updated to the right child
  70. if (items[childIndexLeft].CompareTo(items[childIndexRight]) < 0)
  71. {
  72. swapIndex = childIndexRight;
  73. }
  74. }
  75. //If the parent (item) is smaller than the child it’s being compared to,
  76. //a swap is performed.
  77. if (item.CompareTo(items[swapIndex]) < 0)
  78. {
  79. Swap(item, items[swapIndex]); //Swap performed
  80. }
  81. else
  82. {
  83. return;
  84. }
  85. }
  86. else
  87. {
  88. return;
  89. }
  90. }
  91. }
  92. //This is the counterpart to SortDown and is called when adding a new item or updating an item in the heap.
  93. //It moves the item upwards to ensure the heap order is maintained,
  94. //checking the item's parent and swapping them if necessary.
  95. private void SortUp(T item)
  96. {
  97. //The parent index is calculated using the formula for a binary heap
  98. int parentIndex = (item.HeapIndex - 1) / 2;
  99. while (true)
  100. {
  101. //Gets the parent item
  102. T parentItem = items[parentIndex];
  103. //If item is greater than parentItem (indicating the heap property is violated), a swap is needed.
  104. if (item.CompareTo(parentItem) > 0)
  105. {
  106. //Applies the swap
  107. Swap(item, parentItem);
  108. }
  109. else
  110. {
  111. break;
  112. }
  113. //After a swap, the parentIndex is recalculated based on the updated HeapIndex of the item
  114. parentIndex = (item.HeapIndex - 1) / 2;
  115. }
  116. }
  117. //This swaps two items in the heap, updating both their positions
  118. //in the array and their HeapIndex
  119. private void Swap(T itemA, T itemB)
  120. {
  121. items[itemA.HeapIndex] = itemB;
  122. items[itemB.HeapIndex] = itemA;
  123. int itemAIndex = itemA.HeapIndex;
  124. itemA.HeapIndex = itemB.HeapIndex;
  125. itemB.HeapIndex = itemAIndex;
  126. }
  127. }
  128. //This interface is essential because it provides the HeapIndex
  129. //and comparison functionality for sorting items in the heap.
  130. public interface IheapItem<T> : IComparable<T>
  131. {
  132. int HeapIndex { get; set; }
  133. }
  134. }