Scippy

SCIP

Solving Constraint Integer Programs

pqueue.h
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright 2002-2022 Zuse Institute Berlin */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file pqueue.h
26  * @brief class for priority queues
27  * @author Andreas Bley
28  * @author Marc Pfetsch
29  */
30 
31 #ifndef _PQUEUE_H
32 #define _PQUEUE_H
33 
34 #include <algorithm>
35 #include <functional>
36 
37 namespace std
38 {
39  ///
40  template<typename Key,
41  typename Data,
42  typename Compare = less<Key> >
43 
44  class pqueue
45  {
46  private:
47 
48  //--------------------
49  // item node class
50  //--------------------
51  class node
52  {
53  friend class pqueue;
54 
55  public:
56  //
57  node(
58  const Key& k,
59  const Data& d ):
60  key (k),
61  data (d),
62  sleft (0),
63  sright(0),
64  left (NULL),
65  right (NULL),
66  father(NULL)
67  {}
68 
69  //
70  ~node()
71  {}
72 
73  private:
74  //
75  void delete_children_recursive()
76  {
77  if ( left != NULL )
78  {
79  left->delete_children_recursive();
80  delete left;
81  left = NULL;
82  }
83  if ( right != NULL )
84  {
85  right->delete_children_recursive();
86  delete right;
87  right = NULL;
88  }
89  }
90 
91  Key key;
92  Data data;
93  int sleft;
94  int sright;
95  node* left;
96  node* right;
97  node* father;
98  };
99 
100  public:
101 
102  typedef node* pqueue_item;
103 
104  private:
105 
106  node* root;
107  Compare compare;
108 
109  public:
110 
111  /** Default constructor, creates empty priority queue. */
113  root( NULL )
114  {} /*lint !e1401*/
115 
116  /** Destructs queue */
118  {
119  clear(); /*lint !e1551*/
120  } /*lint !e1579*/
121 
122  /** Empties queue */
123  void clear()
124  {
125  if ( root != NULL )
126  {
127  root->delete_children_recursive();
128  delete root;
129  root = NULL;
130  }
131  }
132 
133  /** Returns true if the pqueue is empty. */
134  bool empty() const
135  {
136  return ( root == NULL );
137  }
138 
139  /** Returns size of queue. */
140  int size() const
141  {
142  return ( root == NULL ? 0 : root->sleft + root->sright + 1 );
143  }
144 
145  /** Returns key of queue item. */
146  const Key& get_key(
147  pqueue_item it
148  ) const
149  {
150  assert( it != NULL );
151  return it->key;
152  }
153 
154  /** Returns data of queue item. */
155  const Data& get_data(
156  pqueue_item it
157  ) const
158  {
159  assert( it != NULL );
160  return it->data;
161  }
162 
163  /** Returns queue item at top (with lowers key). */
164  pqueue_item top()
165  {
166  return root;
167  }
168 
169  /** Inserts a new entry into the queue, returns new item */
170  pqueue_item insert(
171  const Key& key,
172  const Data& data
173  )
174  {
175  node* nn = NULL;
176  if ( root == NULL )
177  {
178  nn = new node(key,data);
179  if ( nn == NULL ) /*lint !e774*/
180  throw std::bad_alloc();
181  root = nn;
182  }
183  else
184  nn = create_new_node(key, data, root);
185 
186  rotate_backward(nn);
187  return nn;
188  }
189 
190  /** Reduces the key a queue item. */
192  pqueue_item item,
193  const Key& new_key
194  )
195  {
196  assert( item );
197  assert( compare(new_key, item->key) );
198 
199  item->key = new_key;
200  rotate_backward(item);
201  }
202 
203  /** Removes the topmost item from the queue. */
204  void pop()
205  {
206  assert ( root != NULL );
207  remove( root );
208  }
209 
210  /** Removes the item from the queue */
211  void remove(
212  node* item
213  )
214  {
215  assert ( item != NULL );
216  assert ( root != NULL );
217 
218  bool goto_left = ( item->left != NULL );
219  bool goto_right = ( item->right != NULL );
220  if ( goto_left && goto_right )
221  {
222  goto_right = ( compare( item->right->key, item->left->key ) );
223  goto_left = ! goto_right;
224  }
225  if ( goto_right )
226  {
227  swap_with_father( item->right );
228  remove( item );
229  return;
230  }
231  if ( goto_left )
232  {
233  swap_with_father( item->left );
234  remove( item );
235  return;
236  }
237  // at leave: remove and update all sizes
238  for (node* n = item, *f = n->father; f != NULL; n = f, f = n->father)
239  {
240  if ( f->left == n )
241  {
242  f->sleft -= 1;
243  }
244  else
245  {
246  assert( f->right == n );
247  f->sright -= 1;
248  }
249  }
250  if ( item->father )
251  {
252  if ( item->father->left == item )
253  {
254  assert( item->father->sleft == 0 );
255  item->father->left = NULL;
256  }
257  else
258  {
259  assert( item->father->right == item );
260  assert( item->father->sright == 0 );
261  item->father->right = NULL;
262  }
263  }
264  else
265  {
266  assert( item == root );
267  root = NULL;
268  }
269  delete item;
270  }
271 
272 
273  private:
274 
275  /** creates new element in the tree such that tree remains balanced */
276  node* create_new_node(
277  const Key& key,
278  const Data& data,
279  node* subproblem
280  )
281  {
282  assert( subproblem != NULL );
283 
284  if ( subproblem->sleft == 0 )
285  {
286  assert( subproblem->left == NULL );
287 
288  node* nn = new node(key,data);
289  subproblem->left = nn;
290  subproblem->sleft = 1;
291  nn->father = subproblem;
292  return nn;
293  }
294  if ( subproblem->sright == 0 )
295  {
296  assert( subproblem->right == NULL );
297 
298  node* nn = new node(key,data);
299  subproblem->right = nn;
300  subproblem->sright = 1;
301  nn->father = subproblem;
302  return nn;
303  }
304  assert( subproblem->left != NULL );
305  assert( subproblem->right != NULL );
306 
307  if ( subproblem->sleft <= subproblem->sright )
308  {
309  subproblem->sleft += 1;
310  return create_new_node(key, data, subproblem->left);
311  }
312 
313  subproblem->sright += 1;
314  return create_new_node(key, data, subproblem->right);
315  }
316 
317 
318  void swap_with_father(
319  node* n1
320  )
321  {
322  int n1_sleft = n1->sleft;
323  int n1_sright = n1->sright;
324  node* n1_left = n1->left;
325  node* n1_right = n1->right;
326  node* n1_father = n1->father;
327  assert( n1_father != NULL );
328  assert( n1_father->left == n1 || n1_father->right == n1 );
329 
330  if ( root == n1_father )
331  root = n1;
332 
333  if ( n1_father->left == n1 )
334  {
335  n1->left = n1_father;
336  n1->right = n1_father->right;
337  }
338  else
339  {
340  assert( n1_father->right == n1 );
341 
342  n1->left = n1_father->left;
343  n1->right = n1_father;
344  }
345  n1_father->left = n1_left;
346  n1_father->right = n1_right;
347 
348  n1->sleft = n1_father->sleft;
349  n1->sright = n1_father->sright;
350  n1_father->sleft = n1_sleft;
351  n1_father->sright = n1_sright;
352 
353  n1->father = n1_father->father;
354  n1_father->father = n1;
355 
356  if ( n1->left )
357  n1->left-> father = n1;
358  if ( n1->right )
359  n1->right->father = n1;
360  if ( n1_father->left )
361  n1_father->left->father = n1_father;
362  if ( n1_father->right )
363  n1_father->right->father = n1_father;
364  if ( n1->father )
365  {
366  if ( n1->father->left == n1_father )
367  n1->father->left = n1;
368  if ( n1->father->right == n1_father )
369  n1->father->right = n1;
370  }
371  }
372 
373  void rotate_backward(
374  node* item
375  )
376  {
377  assert( item != NULL );
378 
379  if ( item->father )
380  {
381  if ( ! compare( item->father->key, item->key ) )
382  {
383  swap_with_father( item );
384  rotate_backward( item );
385  }
386  }
387  }
388  }; /*lint !e1712*/
389 
390 } // namespace std
391 
392 #endif /* _PQUEUE_H */
void pop()
Definition: pqueue.h:204
bool empty() const
Definition: pqueue.h:134
pqueue_item top()
Definition: pqueue.h:164
Definition: pqueue.h:37
#define NULL
Definition: lpi_spx1.cpp:164
node * pqueue_item
Definition: pqueue.h:102
pqueue_item insert(const Key &key, const Data &data)
Definition: pqueue.h:170
void clear()
Definition: pqueue.h:123
int size() const
Definition: pqueue.h:140
void decrease_key(pqueue_item item, const Key &new_key)
Definition: pqueue.h:191
const Key & get_key(pqueue_item it) const
Definition: pqueue.h:146
const Data & get_data(pqueue_item it) const
Definition: pqueue.h:155