id_queue.h

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