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