BucketPQ.h

Go to the documentation of this file.

#ifndef ExponentialBuckets_HEADER
#define ExponentialBuckets_HEADER

#ifdef HAVE_CONFIG_H
#  include <config.h>
#endif

#include <math.h>
#include "SmallList.h"

#if 0
#define dprintf(...) printf(__VA_ARGS__);
#else
#define dprintf(...)
#endif

namespace hudson {

template <class Item>
class BucketPQ : public SmallMemoryItem< BucketPQ<Item> > {

  typedef SmallList<Item> Bucket;

  Bucket *buckets_;
  unsigned nbuckets_;
  int base_;

  // Mutable: To get the runtimes, we need to update the finger even in const
  // functions.
  mutable unsigned finger_;

  void find_non_empty_bucket() const {
    while(finger_ != nbuckets_ && buckets_[finger_].empty()) {
      finger_++;
    }
  }

  void expand_range(int key, bool less_than_base) {
    int min, max; // min and max non-empty value after the current insertion

    // If we're expanding downward, then 'key' is the minimum value after
    // inserting; compute the max.  Otherwise, 'key' is the max and we
    // compute the min.  If the list is empty, then both should be equal
    // to 'key'.
    min = max = key;
    if (less_than_base) {
      for(int i = nbuckets_ - 1; i >= 0; --i) {
        if (!buckets_[i].empty()) { max = base_ + i; break; }
      }
    } else {
      for(unsigned i = 0; i < nbuckets_; ++i) {
        if (!buckets_[i].empty()) { min = base_ + i; break; }
      }
    }
    assert(max >= min);
    unsigned new_range = max - min + 1;
    dprintf("Current base %d, nbuckets %u, key %d\n", base_, nbuckets_, key);
    dprintf("New range: %u (from %d to %d)\n", new_range, min, max);

    if (new_range == 1) { // i.e. queue currently empty
      delete [] buckets_;
      nbuckets_ = 1;
      buckets_ = new Bucket[1];
      base_ = key;
      finger_ = 0;
    } else {
      // double the range we need.  TODO: reuse buckets_ if possible?
      new_range *= 2;
      int new_base = ((max + min) - int(new_range)) / 2;
      dprintf(" grow: %u base %d\n", new_range, new_base);
      assert(min >= new_base);
      assert(unsigned(max - new_base) < new_range);

      // Create the new buckets, copying in from the old.
      Bucket *new_buckets = new Bucket[new_range];
      int copy_begin = less_than_base ? base_ : min;
      int copy_end = less_than_base ? (max+1) : (base_ + nbuckets_);
      dprintf(" copying from %d to %d (%u to %u)\n",
          copy_begin, copy_end, copy_begin - base_, copy_end - base_);
      for(int value = copy_begin; value < copy_end; ++value) {
        unsigned old_i = value - base_;
        unsigned new_i = value - new_base;
        assert(old_i < nbuckets_);
        assert(new_i < new_range);
        buckets_[old_i].swap(new_buckets[new_i]);
      }
      delete [] buckets_;

      // Set the new fields.
      buckets_ = new_buckets;
      nbuckets_ = new_range;
      base_ = new_base;
      finger_ = getIndex(min);
    }
  }

  unsigned getIndex(int key) const {
    assert(key >= base_);
    return key - base_;
  }

  public:
  BucketPQ() {
    buckets_ = NULL;
    nbuckets_ = 0;
    base_ = 0;
    finger_ = 0;
  }

  bool empty() const {
    find_non_empty_bucket();
    return finger_ == nbuckets_;
  }

  void push(int key, const Item& item) {
    if (buckets_ == NULL) {
      buckets_ = new Bucket[1];
      nbuckets_ = 1;
      base_ = key;
      finger_ = 0;
    } else if (key < base_) {
      expand_range(key, true);
    } else if ( getIndex(key) >= nbuckets_) {
      expand_range(key, false);
    }

    unsigned index = getIndex(key);
    dprintf("%d, %d, %u, %u\n", base_, key, index, nbuckets_);
    assert(index < nbuckets_);
    buckets_[index].push_front(item);
    if (index < finger_) {
      finger_ = index;
    }
  }

  Item& top() {
    find_non_empty_bucket();
    assert(finger_ != nbuckets_);
    return buckets_[finger_].front();
  }

  const Item& top() const {
    find_non_empty_bucket();
    assert(finger_ != nbuckets_);
    return buckets_[finger_].front();
  }

  void pop() {
    find_non_empty_bucket();
    assert(finger_ != nbuckets_);
    buckets_[finger_].pop_front();
  }

};

template <class Item>
class BucketDoublePQ : public SmallMemoryItem< BucketDoublePQ<Item> > {
  BucketPQ<Item> pq_;

  public:
  bool empty() const { return pq_.empty(); }
  void push(double key, const Item& item) {
    assert(key > 0.0);
    pq_.push(bithacks::log2_norm(key), item);
  }
  Item& top() { return pq_.top(); }
  const Item& top() const { return pq_.top(); }
  void pop() { return pq_.pop(); }
};

}

#undef dprintf

#endif

---