Branch data Line data Source code
1 : : // $Id: PriorityQueue.cc 6219 2008-10-01 05:39:07Z vern $
2 : : //
3 : : // See the file "COPYING" in the main distribution directory for copyright.
4 : :
5 : : #include "config.h"
6 : :
7 : : #include <stdio.h>
8 : : #include <stdlib.h>
9 : :
10 : : #include "PriorityQueue.h"
11 : : #include "util.h"
12 : :
13 : 3 : PriorityQueue::PriorityQueue(int initial_size)
14 : : {
15 : 3 : max_heap_size = initial_size;
16 : 3 : heap = new PQ_Element*[max_heap_size];
17 : 3 : peak_heap_size = heap_size = 0;
18 : 3 : }
19 : :
20 : 1 : PriorityQueue::~PriorityQueue()
21 : : {
22 [ - + ][ # # ]: 1 : for ( int i = 0; i < heap_size; ++i )
23 [ # # ][ # # ]: 0 : delete heap[i];
24 : :
25 [ + - ][ # # ]: 1 : delete [] heap;
26 : 1 : }
27 : :
28 : 29819 : PQ_Element* PriorityQueue::Remove()
29 : : {
30 [ + + ]: 29819 : if ( heap_size == 0 )
31 : 2 : return 0;
32 : :
33 : 29817 : PQ_Element* top = heap[0];
34 : :
35 : 29817 : --heap_size;
36 : 29817 : SetElement(0, heap[heap_size]);
37 : 29817 : BubbleDown(0);
38 : :
39 : 29817 : top->SetOffset(-1); // = not in heap
40 : 29819 : return top;
41 : : }
42 : :
43 : 2310 : PQ_Element* PriorityQueue::Remove(PQ_Element* e)
44 : : {
45 [ + - ][ + - ]: 2310 : if ( e->Offset() < 0 || e->Offset() >= heap_size ||
[ - + ][ - + ]
46 : : heap[e->Offset()] != e )
47 : 0 : return 0; // not in heap
48 : :
49 : 2310 : e->MinimizeTime();
50 : 2310 : BubbleUp(e->Offset());
51 : :
52 : 2310 : PQ_Element* e2 = Remove();
53 : :
54 [ - + ]: 2310 : if ( e != e2 )
55 : 0 : internal_error("inconsistency in PriorityQueue::Remove");
56 : :
57 : 2310 : return e2;
58 : : }
59 : :
60 : 29889 : int PriorityQueue::Add(PQ_Element* e)
61 : : {
62 : 29889 : SetElement(heap_size, e);
63 : :
64 : 29889 : BubbleUp(heap_size);
65 : :
66 [ + + ]: 29889 : if ( ++heap_size > peak_heap_size )
67 : 601 : peak_heap_size = heap_size;
68 : :
69 [ + + ]: 29889 : if ( heap_size >= max_heap_size )
70 : 9 : return Resize(max_heap_size * 2);
71 : : else
72 : 29889 : return 1;
73 : : }
74 : :
75 : 9 : int PriorityQueue::Resize(int new_size)
76 : : {
77 : 9 : PQ_Element** tmp = new PQ_Element*[new_size];
78 [ + + ]: 1129 : for ( int i = 0; i < max_heap_size; ++i )
79 : 1120 : tmp[i] = heap[i];
80 : :
81 [ + - ]: 9 : delete [] heap;
82 : 9 : heap = tmp;
83 : :
84 : 9 : max_heap_size = new_size;
85 : :
86 : 9 : return heap != 0;
87 : : }
88 : :
89 : 57735 : void PriorityQueue::BubbleUp(int bin)
90 : : {
91 [ + + ]: 57735 : if ( bin == 0 )
92 : 2498 : return;
93 : :
94 : 55237 : int p = Parent(bin);
95 [ + + ]: 55237 : if ( heap[p]->Time() > heap[bin]->Time() )
96 : : {
97 : 25536 : Swap(p, bin);
98 : 57735 : BubbleUp(p);
99 : : }
100 : : }
101 : :
102 : 234451 : void PriorityQueue::BubbleDown(int bin)
103 : : {
104 : 234451 : double v = heap[bin]->Time();
105 : :
106 : 234451 : int l = LeftChild(bin);
107 : 234451 : int r = RightChild(bin);
108 : :
109 [ + + ]: 234451 : if ( l >= heap_size )
110 : 14146 : return; // No children.
111 : :
112 [ + + ]: 220305 : if ( r >= heap_size )
113 : : { // Just a left child.
114 [ + + ]: 622 : if ( heap[l]->Time() < v )
115 : 622 : Swap(l, bin);
116 : : }
117 : :
118 : : else
119 : : {
120 : 219683 : double lv = heap[l]->Time();
121 : 219683 : double rv = heap[r]->Time();
122 : :
123 [ + + ]: 219683 : if ( lv < rv )
124 : : {
125 [ + + ]: 100150 : if ( lv < v )
126 : : {
127 : 95493 : Swap(l, bin);
128 : 100150 : BubbleDown(l);
129 : : }
130 : : }
131 : :
132 [ + + ]: 119533 : else if ( rv < v )
133 : : {
134 : 109141 : Swap(r, bin);
135 : 234451 : BubbleDown(r);
136 : : }
137 : : }
138 : : }
|