Branch data Line data Source code
1 : : // $Id: PriorityQueue.h 6219 2008-10-01 05:39:07Z vern $
2 : : //
3 : : // See the file "COPYING" in the main distribution directory for copyright.
4 : :
5 : : #ifndef __PriorityQueue__
6 : : #define __PriorityQueue__
7 : :
8 : : #include <math.h>
9 : :
10 : : class PriorityQueue;
11 : :
12 : : class PQ_Element {
13 : : public:
14 : 29889 : PQ_Element(double t) { time = t; offset = -1; }
15 [ # # ][ # # ]: 0 : virtual ~PQ_Element() { }
16 : :
17 : 861186 : double Time() const { return time; }
18 : :
19 : 9240 : int Offset() const { return offset; }
20 : 550415 : void SetOffset(int off) { offset = off; }
21 : :
22 : 2310 : void MinimizeTime() { time = -HUGE_VAL; }
23 : :
24 : : protected:
25 : 0 : PQ_Element() { }
26 : : double time;
27 : : int offset;
28 : : };
29 : :
30 : : class PriorityQueue {
31 : : public:
32 : : PriorityQueue(int initial_size = 16);
33 : : ~PriorityQueue();
34 : :
35 : : // Returns the top of queue, or nil if the queue is empty.
36 : 48810 : PQ_Element* Top() const
37 : : {
38 [ - + ]: 48810 : if ( heap_size == 0 )
39 : 0 : return 0;
40 : : else
41 : 48810 : return heap[0];
42 : : }
43 : :
44 : : // Removes (and returns) top of queue. Returns nil if the queue
45 : : // is empty.
46 : : PQ_Element* Remove();
47 : :
48 : : // Removes element e. Returns e, or nil if e wasn't in the queue.
49 : : // Note that e will be modified via MinimizeTime().
50 : : PQ_Element* Remove(PQ_Element* e);
51 : :
52 : : // Add a new element to the queue. Returns 0 on failure (not enough
53 : : // memory to add the element), 1 on success.
54 : : int Add(PQ_Element* e);
55 : :
56 : 0 : int Size() const { return heap_size; }
57 : 0 : int PeakSize() const { return peak_heap_size; }
58 : :
59 : : protected:
60 : : int Resize(int new_size);
61 : :
62 : : void BubbleUp(int bin);
63 : : void BubbleDown(int bin);
64 : :
65 : 55237 : int Parent(int bin) const
66 : : {
67 : 55237 : return bin >> 1;
68 : : }
69 : :
70 : 468902 : int LeftChild(int bin) const
71 : : {
72 : 468902 : return bin << 1;
73 : : }
74 : :
75 : 234451 : int RightChild(int bin) const
76 : : {
77 : 234451 : return LeftChild(bin) + 1;
78 : : }
79 : :
80 : 520598 : void SetElement(int bin, PQ_Element* e)
81 : : {
82 : 520598 : heap[bin] = e;
83 : 520598 : e->SetOffset(bin);
84 : 520598 : }
85 : :
86 : 230446 : void Swap(int bin1, int bin2)
87 : : {
88 : 230446 : PQ_Element* t = heap[bin1];
89 : 230446 : SetElement(bin1, heap[bin2]);
90 : 230446 : SetElement(bin2, t);
91 : 230446 : }
92 : :
93 : : PQ_Element** heap;
94 : : int heap_size;
95 : : int peak_heap_size;
96 : : int max_heap_size;
97 : : };
98 : :
99 : : #endif
|