1// tPriorityQueue.h 
2// 
3// A priority queue implemented using the heap data structure. Priority queues support retrieval of min or max item 
4// in the collection in O(1) time. Removal of the min or max in O(lg(n)) time, and insertion in O(lg(n)) time. 
5// 
6// Copyright (c) 2004-2006, 2017 Tristan Grimmer. 
7// Permission to use, copy, modify, and/or distribute this software for any purpose with or without fee is hereby 
8// granted, provided that the above copyright notice and this permission notice appear in all copies. 
9// 
10// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL 
11// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, 
12// INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN 
13// AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR 
14// PERFORMANCE OF THIS SOFTWARE. 
15 
16#pragma once 
17#include "Foundation/tStandard.h" 
18 
19 
20template <typename T> class tPriorityQueue 
21{ 
22public: 
23 // A tPriorityQueue places nodes with smaller key values closer to the root of the tree. If you set 'ascending' to 
24 // false then it will place larger key values closer to the root. 
25 tPriorityQueue(int initialSize, int growSize, bool ascending = true); 
26 virtual ~tPriorityQueue() { delete[] Heap; } 
27 
28 struct tItem 
29 { 
30 tItem() : Data(), Key(0x0000000000000000) { } 
31 tItem(const tItem& src) : Data(src.Data), Key(src.Key) { } 
32 tItem(T d, int64 k) : Data(d), Key(k) { } 
33 T Data; // Up to client what this is for. A pointer is often used. 
34 int64 Key; 
35 }; 
36 
37 void Insert(const tItem&); // Put a node into the queue. 
38 tItem GetMin() const /* Error to call if GetCount() < 1. */ { tAssert(NumItems > 0); return Heap[0]; } 
39 tItem GetRemoveMin(); // Error to call if Count() < 1. 
40 
41 int GetNumItems() const { return NumItems; } 
42 bool IsEmpty() const { return NumItems == 0; } 
43 
44 // Iterates through all nodes updating their data if it matches origData. Returns number of replacements. 
45 int Replace(T origData, T newData); 
46 
47private: 
48 int GetLeftIndex(int i) const { return 1 + (i << 1); } 
49 int GetRightIndex(int i) const { return 2 + (i << 1); } 
50 int GetParentIndex(int i) const { return (i - 1) >> 1; } 
51 void Heapify(int i); 
52 
53 bool Ascending; 
54 int NumItems; // Number of items in the heap. 
55 int MaxItems; // Total number of items currently available to be used. 
56 int NumItemsGrow; // How many items to grow by if we run out of room. 
57 tItem* Heap; 
58}; 
59template<typename T> using tPQ = tPriorityQueue<T>; 
60 
61 
62// Implementation below this line. 
63 
64 
65template <typename T> inline tPriorityQueue<T>::tPriorityQueue(int initSize, int growSize, bool ascending) : 
66 Ascending(ascending), 
67 NumItems(0), 
68 MaxItems(initSize), 
69 NumItemsGrow(growSize) 
70{ 
71 tAssert((MaxItems >= 1) && (NumItemsGrow >= 1)); 
72 Heap = new tItem[initSize]; 
73} 
74 
75 
76template <typename T> inline void tPriorityQueue<T>::Heapify(int i) 
77{ 
78 tAssert(i >= 0); 
79 
80 // Initially an invalid index. 
81 int smallest = -1; 
82 while (smallest != i) 
83 { 
84 if (smallest != -1) 
85 { 
86 // Exchange. 
87 tItem temp = Heap[i]; 
88 Heap[i] = Heap[smallest]; 
89 Heap[smallest] = temp; 
90 i = smallest; 
91 } 
92 
93 int left = GetLeftIndex(i); 
94 if 
95 ( 
96 (left < NumItems) && 
97 (Ascending ? (Heap[left].Key < Heap[i].Key) : (Heap[left].Key > Heap[i].Key)) 
98 ) 
99 { 
100 smallest = left; 
101 } 
102 else 
103 { 
104 smallest = i; 
105 } 
106 
107 int right = GetRightIndex(i); 
108 if 
109 ( 
110 (right < NumItems) && 
111 (Ascending ? (Heap[right].Key < Heap[smallest].Key) : (Heap[right].Key > Heap[smallest].Key)) 
112 ) 
113 { 
114 smallest = right; 
115 } 
116 } 
117} 
118 
119 
120template <typename T> inline typename tPriorityQueue<T>::tItem tPriorityQueue<T>::GetRemoveMin() 
121{ 
122 tAssert(NumItems > 0); 
123 tItem min = Heap[0]; 
124 Heap[0] = Heap[NumItems-1]; 
125 
126 NumItems--; 
127 Heapify(0); 
128 return min; 
129} 
130 
131 
132template <typename T> inline void tPriorityQueue<T>::Insert(const typename tPriorityQueue<T>::tItem& k) 
133{ 
134 NumItems++; 
135 
136 // Do we need to grow array? 
137 if (NumItems > MaxItems) 
138 { 
139 MaxItems += NumItemsGrow; 
140 tItem* newHeap = new tItem[MaxItems]; 
141 
142 tStd::tMemcpy(newHeap, Heap, sizeof(tItem)*(NumItems-1)); 
143 delete[] Heap; 
144 Heap = newHeap; 
145 } 
146 
147 int i = NumItems - 1; 
148 while 
149 ( 
150 (i > 0) && 
151 (Ascending ? (Heap[GetParentIndex(i)].Key > k.Key) : (Heap[GetParentIndex(i)].Key < k.Key)) 
152 ) 
153 { 
154 Heap[i] = Heap[GetParentIndex(i)]; 
155 i = GetParentIndex(i); 
156 } 
157 
158 Heap[i] = k; 
159} 
160 
161 
162template <typename T> inline int tPriorityQueue<T>::Replace(T origData, T newData) 
163{ 
164 int numReplaced = 0; 
165 for (int i = 0; i < NumItems; i++) 
166 { 
167 if (Heap[i].Data == origData) 
168 { 
169 Heap[i].Data = newData; 
170 numReplaced++; 
171 } 
172 } 
173 
174 return numReplaced; 
175} 
176