id_queue.h

Go to the documentation of this file.

#ifndef ROUTING_KIT_ID_QUEUE_H
#define ROUTING_KIT_ID_QUEUE_H
 
#include <routingkit/constants.h>
#include <vector>
#include <algorithm>
#include <assert.h>
 
namespace RoutingKit{
 
struct IDKeyPair{
    unsigned id;
    unsigned key;
};
 
class MinIDQueue{
private:
    static const unsigned tree_arity = 4;
public:
    MinIDQueue():heap_size(0){}
 
    explicit MinIDQueue(unsigned id_count):
        id_pos(id_count, invalid_id),
        heap(id_count),
        heap_size(0){}
 
    bool empty()const{
        return heap_size == 0;
    }
 
    unsigned size()const{
        return heap_size;
    }
 
    unsigned id_count()const{
        return id_pos.size();
    }
 
    bool contains_id(unsigned id){
        assert(id < id_count());
        return id_pos[id] != invalid_id;
    }
 
    void clear(){
        for(unsigned i=0; i<heap_size; ++i)
            id_pos[heap[i].id] = invalid_id;
        heap_size = 0;
    }
 
    friend void swap(MinIDQueue&l, MinIDQueue&r){
        using std::swap;
        swap(l.id_pos, r.id_pos);
        swap(l.heap, r.heap);
        swap(l.heap_size, r.heap_size);
    }
 
    unsigned get_key(unsigned id)const{
        assert(id < id_count());
        assert(id_pos[id] != invalid_id);
        return heap[id_pos[id]].key;
    }
 
    IDKeyPair peek()const{
        assert(!empty());
        return heap.front();
    }
 
    IDKeyPair pop(){
        assert(!empty());
        --heap_size;
        std::swap(heap[0].key, heap[heap_size].key);
        std::swap(heap[0].id,  heap[heap_size].id);
        id_pos[heap[0].id] = 0;
        id_pos[heap[heap_size].id] = invalid_id;
        
        move_down_in_tree(0);
        return heap[heap_size];
    }
 
    void push(IDKeyPair p){
        assert(p.id < id_count());
        assert(!contains_id(p.id));
    
        unsigned pos = heap_size;
        ++heap_size;
        heap[pos] = p;
        id_pos[p.id] = pos;
        move_up_in_tree(pos);
    }
 
    bool decrease_key(IDKeyPair p){
        assert(p.id < id_count());
        assert(contains_id(p.id));
    
        unsigned pos = id_pos[p.id];
 
        if(heap[pos].key > p.key){
            heap[pos].key = p.key;
            move_up_in_tree(pos);
            return true;
        } else {
            return false;
        }
    }
 
    bool increase_key(IDKeyPair p){
        assert(p.id < id_count());
        assert(contains_id(p.id));
    
        unsigned pos = id_pos[p.id];
 
        if(heap[pos].key < p.key){
            heap[pos].key = p.key;
            move_down_in_tree(pos);
            return true;
        } else {
            return false;
        }
    }
 
private:
    void move_up_in_tree(unsigned pos){
        while(pos != 0){
            unsigned parent = (pos-1)/tree_arity;
            if(heap[parent].key > heap[pos].key){
                std::swap(heap[pos],  heap[parent]);
                std::swap(id_pos[heap[pos].id], id_pos[heap[parent].id]);
            }
            pos = parent;
        }
    }
 
    void move_down_in_tree(unsigned pos){
        for(;;){
            unsigned first_child = tree_arity*pos+1;
            if(first_child >= heap_size)
                return; // no children
            unsigned smallest_child = first_child;
            for(unsigned c = first_child+1; c < std::min(tree_arity*pos+tree_arity+1, heap_size); ++c){
                if(heap[smallest_child].key > heap[c].key){
                    smallest_child = c;
                }
            }
 
            if(heap[smallest_child].key >= heap[pos].key)
                return; // no child is smaller
 
            std::swap(heap[pos],  heap[smallest_child]);
            std::swap(id_pos[heap[pos].id], id_pos[heap[smallest_child].id]);
            pos = smallest_child;
        }
    }
 
    std::vector<unsigned>id_pos;
    std::vector<IDKeyPair>heap;
 
    unsigned heap_size;
};
 
} // namespace RoutingKit
 
#endif