Line data Source code
1 : #ifndef ROUTING_KIT_ID_SET_QUEUE_H
2 : #define ROUTING_KIT_ID_SET_QUEUE_H
3 :
4 : #include <routingkit/constants.h>
5 : #include <routingkit/min_max.h>
6 : #include <vector>
7 : #include <assert.h>
8 :
9 : namespace RoutingKit{
10 :
11 : //! This is min queue that can only contain IDs from a given range.
12 : //! IDs are compared by their value. Ids in the queue cannot be
13 : //! duplicated.
14 : class IDSetMinQueue{
15 :
16 : private:
17 : // Internally, the queue is represented using an implicit binary tree
18 : // For every node in the tree, a bit is stored in data.
19 : //
20 : // Suppose that id_count() is 6, then the tree nodes are organized as
21 : // follows:
22 : // 1
23 : // / |
24 : // / |
25 : // / |
26 : // / |
27 : // 2 3
28 : // / | / |
29 : // / | / |
30 : // 4 5 6 7
31 : // /| /| / |
32 : // 8 9 10 11 12 13
33 : //
34 : // Node ids are counted starting from 1 and not from 0. IDs are counted
35 : // starting from 0.
36 : //
37 : // The lowest level contains 6 bits because we have at most 6 IDs. Each of
38 : // these lowest level bits encodes whether an ID is in the queue or not.
39 : //
40 : // If the number of IDs is uneven, for example 5, then we add another node
41 : // to the lowest level to make sure that every node has a sibling. This
42 : // padding bit will always remain false.
43 : //
44 : // The bit of upper level nodes is set, iff, there is a child whose bit is
45 : // set. If the queue would contain the IDs 1 and 2, then the nodes
46 : // 9, 10, 4, 5, 2, and 1 would have their bits sets.
47 : //
48 : // Whether a bit is set is stored in data. data[0] is not used. The first
49 : // meaningful bit is data[1].
50 : //
51 : // offset stores the node number of the first node of the lowest level.
52 : // Because of the way that the tree is constructed, this is always
53 : // a power of two and it is never smaller than id_count().
54 : //
55 : // min_id stores the smallest id in the queue or invalid_id.
56 : //
57 : //
58 : // parent maps a node onto its parent.
59 : //
60 : // other_child turns a node into its sibling.
61 : // is_larger_child checks whether a node is a right child in the
62 : // above diagram.
63 : // is_smaller_child
64 :
65 :
66 : static const unsigned root = 1;
67 :
68 : //! Maps a node onto its parent. Only works if x != root.
69 : static unsigned parent(unsigned x){
70 159289949 : return x>>1;
71 : }
72 :
73 : //! Maps a node onto its sibling. Only works if x != root.
74 : static unsigned other_child(unsigned x){
75 94979704 : return x^1;
76 : }
77 :
78 : //! True if other_child(x) < x. Only works if x != root.
79 : static unsigned is_larger_child(unsigned x){
80 : return x&1;
81 : }
82 :
83 : //! True if other_child(x) > x. Only works if x != root.
84 : static unsigned is_smaller_child(unsigned x){
85 : return !is_larger_child(x);
86 : }
87 :
88 : //! Returns the node y such that parent(y) == x and y < other_child(y).
89 : static unsigned smaller_child(unsigned x){
90 90917448 : return x<<1;
91 : }
92 :
93 : //! Returns the node y such that parent(y) == x and y > other_child(y).
94 : static unsigned larger_child(unsigned x){
95 : return (x<<1)|1;
96 : }
97 :
98 : static unsigned smallest_two_power_no_smaller_than(unsigned x){
99 : unsigned y = 1;
100 9336 : while(y < x){
101 7887 : y <<= 1;
102 : assert(y != 0);
103 : }
104 : return y;
105 : }
106 :
107 : public:
108 : IDSetMinQueue(){}
109 :
110 : //! The queue may contain IDs from 0 to n-1.
111 1449 : explicit IDSetMinQueue(unsigned n):
112 1449 : max_number_of_ids(n),
113 1449 : min_id(invalid_id),
114 1449 : offset(smallest_two_power_no_smaller_than(n)),
115 1449 : data(n+offset+(n&1), false)// +(n&1) add an element if n is odd
116 1449 : {}
117 :
118 : unsigned id_count() const {
119 1350287 : return max_number_of_ids;
120 : }
121 :
122 : //! Adds an ID to the queue. If the ID is already in the queue, then
123 : //! nothing happens.
124 88492287 : void push(unsigned id){
125 : assert(id < id_count() && "id out of bounds");
126 :
127 88492287 : if(min_id == invalid_id)
128 1315296 : min_id = id;
129 : else
130 : min_to(min_id, id);
131 :
132 88492287 : unsigned x = id + offset;
133 :
134 88492287 : if(data[x])
135 : return;
136 :
137 : for(;;)
138 : {
139 : assert(!data[x]);
140 : data[x] = true;
141 :
142 160605245 : if(x == root)
143 : break;
144 :
145 : x = parent(x);
146 :
147 159289949 : if(data[x])
148 : break;
149 : }
150 : }
151 :
152 : //! Checks whether an ID is in the queue.
153 : bool contains(unsigned id) const {
154 : assert(id < id_count() && "id out of bounds");
155 : return data[offset + id];
156 : }
157 :
158 : //! Checks whether the queue contains any element.
159 : bool empty() const {
160 64687480 : return min_id == invalid_id;
161 : }
162 :
163 : //! Returns the smallest ID in the queue without removing it.
164 : //! Returns invalid_id if the queue is empty.
165 : unsigned peek() const {
166 : return min_id;
167 : }
168 :
169 : //! Returns the smallest ID in the queue and removes it.
170 : //! Returns invalid_id if the queue is empty.
171 64075578 : unsigned pop() {
172 : assert(!empty());
173 :
174 64075578 : unsigned ret = min_id;
175 :
176 64075578 : unsigned x = min_id + offset;
177 :
178 : for(;;)
179 : {
180 : assert(data[x]);
181 : data[x] = false;
182 :
183 160605245 : if(x == root){
184 1315296 : min_id = invalid_id;
185 1315296 : return ret;
186 : }
187 :
188 159289949 : if(is_smaller_child(x)){
189 : unsigned y = other_child(x);
190 : assert(y < data.size());
191 80679188 : if(data[y])
192 : break;
193 : } else {
194 : assert(!data[other_child(x)]);
195 : }
196 :
197 : x = parent(x);
198 96529667 : }
199 :
200 : assert(is_smaller_child(x));
201 : x = other_child(x);
202 : assert(data[x]);
203 : for(;;){
204 153677730 : if(x >= offset)
205 : break;
206 :
207 : x = smaller_child(x);
208 90917448 : if(!data[x])
209 : x = other_child(x);
210 : assert(data[x]);
211 : }
212 62760282 : min_id = x - offset;
213 :
214 62760282 : return ret;
215 : }
216 :
217 : //! Removes all elements from the queue.
218 : void clear(){
219 1350287 : while(!empty())
220 0 : pop();
221 : }
222 :
223 : private:
224 :
225 : unsigned max_number_of_ids;
226 : unsigned min_id;
227 : unsigned offset;
228 : std::vector<bool>data;
229 : };
230 :
231 : } // RoutingKit
232 :
233 : #endif
234 :
|
