1 #ifndef NALL_PRIORITYQUEUE_HPP 2 #define NALL_PRIORITYQUEUE_HPP 3 4 #include <limits> 5 #include <nall/function.hpp> 6 #include <nall/serializer.hpp> 7 #include <nall/utility.hpp> 8 9 namespace nall_v059 { priority_queue_nocallback(type_t)10 template<typename type_t> void priority_queue_nocallback(type_t) {} 11 12 //priority queue implementation using binary min-heap array; 13 //does not require normalize() function. 14 //O(1) find (tick) 15 //O(log n) insert (enqueue) 16 //O(log n) remove (dequeue) 17 template<typename type_t> class priority_queue : noncopyable { 18 public: tick(unsigned ticks)19 inline void tick(unsigned ticks) { 20 basecounter += ticks; 21 while(heapsize && gte(basecounter, heap[0].counter)) callback(dequeue()); 22 } 23 24 //counter is relative to current time (eg enqueue(64, ...) fires in 64 ticks); 25 //counter cannot exceed std::numeric_limits<unsigned>::max() >> 1. enqueue(unsigned counter,type_t event)26 void enqueue(unsigned counter, type_t event) { 27 if(heapsize >= heapcapacity) 28 { 29 //puts("IYEEE"); 30 return; 31 } 32 33 unsigned child = heapsize++; 34 counter += basecounter; 35 36 while(child) { 37 unsigned parent = (child - 1) >> 1; 38 if(gte(counter, heap[parent].counter)) break; 39 40 heap[child].counter = heap[parent].counter; 41 heap[child].event = heap[parent].event; 42 child = parent; 43 } 44 45 heap[child].counter = counter; 46 heap[child].event = event; 47 } 48 dequeue()49 type_t dequeue() { 50 type_t event(heap[0].event); 51 unsigned parent = 0; 52 unsigned counter = heap[--heapsize].counter; 53 54 while(true) { 55 unsigned child = (parent << 1) + 1; 56 if(child >= heapsize) break; 57 if(child + 1 < heapsize && gte(heap[child].counter, heap[child + 1].counter)) child++; 58 if(gte(heap[child].counter, counter)) break; 59 60 heap[parent].counter = heap[child].counter; 61 heap[parent].event = heap[child].event; 62 parent = child; 63 } 64 65 heap[parent].counter = counter; 66 heap[parent].event = heap[heapsize].event; 67 return event; 68 } 69 reset()70 void reset() { 71 basecounter = 0; 72 heapsize = 0; 73 } 74 serialize(serializer & s)75 void serialize(serializer &s) { 76 s.integer(basecounter); 77 s.integer(heapsize); 78 79 for(unsigned n = 0; n < heapcapacity; n++) { 80 s.integer(heap[n].counter); 81 s.integer(heap[n].event); 82 } 83 84 if(s.mode() == serializer::Load) 85 { 86 bool error_condition = false; 87 unsigned prev; 88 89 if(heapsize > heapcapacity) 90 { 91 heapsize = 0; // So the loop isn't iterated through below. 92 error_condition = true; 93 } 94 95 #if 0 96 prev = heap[0].counter - basecounter; 97 for(unsigned n = 0; n < heapsize; n++) 98 { 99 unsigned cur = heap[n].counter - basecounter; 100 101 if(cur > heaptimesanity) 102 { 103 error_condition = true; 104 break; 105 } 106 107 if(cur < prev) 108 { 109 error_condition = true; 110 break; 111 } 112 113 prev = cur; 114 } 115 #endif 116 if(error_condition) 117 { 118 puts("Priority queue error"); 119 reset(); 120 } 121 } 122 } 123 priority_queue(unsigned size,function<void (type_t)> callback_=& priority_queue_nocallback<type_t>,unsigned time_sanity=(std::numeric_limits<unsigned>::max ()>>1))124 priority_queue(unsigned size, function<void (type_t)> callback_ = &priority_queue_nocallback<type_t>, unsigned time_sanity = (std::numeric_limits<unsigned>::max() >> 1)) 125 : callback(callback_), heaptimesanity(time_sanity) { 126 heap = new heap_t[size]; 127 heapcapacity = size; 128 reset(); 129 } 130 ~priority_queue()131 ~priority_queue() { 132 delete[] heap; 133 } 134 135 private: 136 function<void (type_t)> callback; 137 unsigned basecounter; 138 unsigned heapsize; 139 unsigned heapcapacity; 140 unsigned heaptimesanity; 141 struct heap_t { 142 unsigned counter; 143 type_t event; 144 } *heap; 145 146 //return true if x is greater than or equal to y gte(unsigned x,unsigned y)147 inline bool gte(unsigned x, unsigned y) { 148 return x - y < (std::numeric_limits<unsigned>::max() >> 1); 149 } 150 }; 151 } 152 153 #endif 154