Line data Source code
1 : #ifndef ROUTING_KIT_ID_QUEUE_H
2 : #define ROUTING_KIT_ID_QUEUE_H
3 :
4 : #include <routingkit/constants.h>
5 : #include <vector>
6 : #include <algorithm>
7 : #include <assert.h>
8 :
9 : namespace RoutingKit{
10 :
11 : struct IDKeyPair{
12 : unsigned id;
13 : unsigned key;
14 : };
15 :
16 : //! A priority queue where the elements are IDs from 0 to id_count-1 where id_count is a number that is set in the constructor.
17 : //! The elements are sorted by integer keys.
18 0 : class MinIDQueue{
19 : private:
20 : static const unsigned tree_arity = 4;
21 : public:
22 : MinIDQueue():heap_size(0){}
23 :
24 0 : explicit MinIDQueue(unsigned id_count):
25 0 : id_pos(id_count, invalid_id),
26 0 : heap(id_count),
27 0 : heap_size(0){}
28 :
29 : //! Returns whether the queue is empty. Equivalent to checking whether size() returns 0.
30 : bool empty()const{
31 0 : return heap_size == 0;
32 : }
33 :
34 : //! Returns the number of elements in the queue.
35 : unsigned size()const{
36 : return heap_size;
37 : }
38 :
39 : //! Returns the id_count value passed to the constructor.
40 : unsigned id_count()const{
41 : return id_pos.size();
42 : }
43 :
44 : //! Checks whether an element is in the queue.
45 : bool contains_id(unsigned id){
46 : assert(id < id_count());
47 0 : return id_pos[id] != invalid_id;
48 : }
49 :
50 : //! Removes all elements from the queue.
51 : void clear(){
52 0 : for(unsigned i=0; i<heap_size; ++i)
53 0 : id_pos[heap[i].id] = invalid_id;
54 0 : heap_size = 0;
55 : }
56 :
57 : friend void swap(MinIDQueue&l, MinIDQueue&r){
58 : using std::swap;
59 : swap(l.id_pos, r.id_pos);
60 : swap(l.heap, r.heap);
61 : swap(l.heap_size, r.heap_size);
62 : }
63 :
64 : //! Returns the current key of an element.
65 : //! Undefined if the element is not part of the queue.
66 : unsigned get_key(unsigned id)const{
67 : assert(id < id_count());
68 : assert(id_pos[id] != invalid_id);
69 0 : return heap[id_pos[id]].key;
70 : }
71 :
72 : //! Returns the smallest element key pair without removing it from the queue.
73 : IDKeyPair peek()const{
74 : assert(!empty());
75 0 : return heap.front();
76 : }
77 :
78 : //! Returns the smallest element key pair and removes it form the queue.
79 0 : IDKeyPair pop(){
80 : assert(!empty());
81 0 : --heap_size;
82 0 : std::swap(heap[0].key, heap[heap_size].key);
83 0 : std::swap(heap[0].id, heap[heap_size].id);
84 0 : id_pos[heap[0].id] = 0;
85 0 : id_pos[heap[heap_size].id] = invalid_id;
86 :
87 0 : move_down_in_tree(0);
88 0 : return heap[heap_size];
89 : }
90 :
91 : //! Inserts a element key pair.
92 : //! Undefined if the element is part of the queue.
93 0 : void push(IDKeyPair p){
94 : assert(p.id < id_count());
95 : assert(!contains_id(p.id));
96 :
97 0 : unsigned pos = heap_size;
98 0 : ++heap_size;
99 0 : heap[pos] = p;
100 0 : id_pos[p.id] = pos;
101 0 : move_up_in_tree(pos);
102 0 : }
103 :
104 : //! Updates the key of an element if the new key is smaller than the old key.
105 : //! Does nothing if the new key is larger.
106 : //! Undefined if the element is not part of the queue.
107 0 : bool decrease_key(IDKeyPair p){
108 : assert(p.id < id_count());
109 : assert(contains_id(p.id));
110 :
111 0 : unsigned pos = id_pos[p.id];
112 :
113 0 : if(heap[pos].key > p.key){
114 0 : heap[pos].key = p.key;
115 0 : move_up_in_tree(pos);
116 0 : return true;
117 : } else {
118 : return false;
119 : }
120 : }
121 :
122 : //! Updates the key of an element if the new key is larger than the old key.
123 : //! Does nothing if the new key is smaller.
124 : //! Undefined if the element is not part of the queue.
125 0 : bool increase_key(IDKeyPair p){
126 : assert(p.id < id_count());
127 : assert(contains_id(p.id));
128 :
129 0 : unsigned pos = id_pos[p.id];
130 :
131 0 : if(heap[pos].key < p.key){
132 0 : heap[pos].key = p.key;
133 0 : move_down_in_tree(pos);
134 0 : return true;
135 : } else {
136 : return false;
137 : }
138 : }
139 :
140 : private:
141 0 : void move_up_in_tree(unsigned pos){
142 0 : while(pos != 0){
143 0 : unsigned parent = (pos-1)/tree_arity;
144 0 : if(heap[parent].key > heap[pos].key){
145 : std::swap(heap[pos], heap[parent]);
146 0 : std::swap(id_pos[heap[pos].id], id_pos[heap[parent].id]);
147 : }
148 : pos = parent;
149 : }
150 0 : }
151 :
152 0 : void move_down_in_tree(unsigned pos){
153 : for(;;){
154 0 : unsigned first_child = tree_arity*pos+1;
155 0 : if(first_child >= heap_size)
156 : return; // no children
157 : unsigned smallest_child = first_child;
158 0 : for(unsigned c = first_child+1; c < std::min(tree_arity*pos+tree_arity+1, heap_size); ++c){
159 0 : if(heap[smallest_child].key > heap[c].key){
160 : smallest_child = c;
161 : }
162 : }
163 :
164 0 : if(heap[smallest_child].key >= heap[pos].key)
165 : return; // no child is smaller
166 :
167 : std::swap(heap[pos], heap[smallest_child]);
168 0 : std::swap(id_pos[heap[pos].id], id_pos[heap[smallest_child].id]);
169 : pos = smallest_child;
170 0 : }
171 : }
172 :
173 : std::vector<unsigned>id_pos;
174 : std::vector<IDKeyPair>heap;
175 :
176 : unsigned heap_size;
177 : };
178 :
179 : } // namespace RoutingKit
180 :
181 : #endif
|
