1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */ 2 /* */ 3 /* This file is part of the program and library */ 4 /* SCIP --- Solving Constraint Integer Programs */ 5 /* */ 6 /* Copyright (C) 2002-2021 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 // node(const Key & k,const Data & d)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 // ~node()61 ~node() 62 {} 63 64 private: 65 // delete_children_recursive()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. */ pqueue()103 pqueue(): 104 root( NULL ) 105 {} /*lint !e1401*/ 106 107 /** Destructs queue */ ~pqueue()108 ~pqueue() 109 { 110 clear(); /*lint !e1551*/ 111 } /*lint !e1579*/ 112 113 /** Empties queue */ clear()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. */ empty()125 bool empty() const 126 { 127 return ( root == NULL ); 128 } 129 130 /** Returns size of queue. */ size()131 int size() const 132 { 133 return ( root == NULL ? 0 : root->sleft + root->sright + 1 ); 134 } 135 136 /** Returns key of queue item. */ get_key(pqueue_item it)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. */ get_data(pqueue_item it)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). */ top()155 pqueue_item top() 156 { 157 return root; 158 } 159 160 /** Inserts a new entry into the queue, returns new item */ insert(const Key & key,const Data & data)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. */ decrease_key(pqueue_item item,const Key & new_key)182 void decrease_key( 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. */ pop()195 void pop() 196 { 197 assert ( root != NULL ); 198 remove( root ); 199 } 200 201 /** Removes the item from the queue */ remove(node * item)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 */ create_new_node(const Key & key,const Data & data,node * subproblem)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 swap_with_father(node * n1)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 rotate_backward(node * item)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 */ 384