src/libswift/binheap.cpp

   1 /*
   2  *  sbit.cpp
   3  *  serp++
   4  *
   5  *  Created by Victor Grishchenko on 4/1/09.
   6  *  Copyright 2009 Delft University of Technology. All rights reserved.
   7  *
   8  */
   9
  10 #include <algorithm>
  11 #include <cstdlib>
  12
  13 #include "binheap.h"
  14
  15
  16 binheap::binheap() {
  17     size_ = 32;
  18     heap_ = (bin_t*) malloc(size_*sizeof(bin_t));
  19     filled_ = 0;
  20 }
  21
  22 bool bincomp (const bin_t& a, const bin_t& b) {
  23     register uint64_t ab = a.base_offset(), bb = b.base_offset();
  24     if (ab==bb)
  25         return a.layer_bits() < b.layer_bits();
  26     else
  27         return ab > bb;
  28 }
  29
  30 bool bincomp_rev (const bin_t& a, const bin_t& b) {
  31     register uint64_t ab = a.base_offset(), bb = b.base_offset();
  32     if (ab==bb)
  33         return a.layer_bits() > b.layer_bits();
  34     else
  35         return ab < bb;
  36 }
  37
  38 bin_t binheap::pop() {
  39     if (!filled_)
  40         return bin_t::NONE;
  41     bin_t ret = heap_[0];
  42     std::pop_heap(heap_, heap_+filled_--,bincomp);
  43     while (filled_ && ret.contains(heap_[0]))
  44         std::pop_heap(heap_, heap_+filled_--,bincomp);
  45     return ret;
  46 }
  47
  48 void    binheap::extend() {
  49     std::sort(heap_,heap_+filled_,bincomp_rev);
  50     int solid = 0;
  51     for(int i=1; i<filled_; i++)
  52         if (!heap_[solid].contains(heap_[i]))
  53             heap_[++solid] = heap_[i];
  54     filled_ = solid+1;
  55     if (2*filled_>size_) {
  56         size_ <<= 1;
  57         heap_ = (bin_t*) realloc(heap_,size_*sizeof(bin_t));
  58     }
  59 }
  60
  61 void    binheap::push(bin_t val) {
  62     if (filled_==size_)
  63         extend();
  64     heap_[filled_++] = val;
  65     std::push_heap(heap_, heap_+filled_,bincomp);
  66 }
  67
  68 binheap::~binheap() {
  69     free(heap_);
  70 }
  71