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