heap.h

/* MLPACK 0.2
 *
 * Copyright (c) 2008, 2009 Alexander Gray,
 *                          Garry Boyer,
 *                          Ryan Riegel,
 *                          Nikolaos Vasiloglou,
 *                          Dongryeol Lee,
 *                          Chip Mappus, 
 *                          Nishant Mehta,
 *                          Hua Ouyang,
 *                          Parikshit Ram,
 *                          Long Tran,
 *                          Wee Chin Wong
 *
 * Copyright (c) 2008, 2009 Georgia Institute of Technology
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
 * 02110-1301, USA.
 */
#ifndef COLLECTIONS_HEAP_H
#define COLLECTIONS_HEAP_H

#include "fastlib/col/arraylist.h"
//#include "arraylist.h"

template <typename TKey, typename TValue = Empty>
class MinHeap {
  // TODO: A copiable heap probably isn't a bad idea

 public:
  typedef TKey Key;
  typedef TValue Value;

 private:
  struct Entry {
    TKey key;
    TValue value;

    OBJECT_TRAVERSAL_SHALLOW(Entry) {
      OT_OBJ(key);
      OT_OBJ(value);
    }
  };

  ArrayList<Entry> entries_;

  OBJECT_TRAVERSAL(MinHeap) {
    OT_OBJ(entries_);
  }

 public:
  void Init() {
    entries_.Init();
  }

  bool is_empty() const {
    return entries_.size() == 0;
  }

  void Put(Key key, Value value) {
    Entry entry;

    entries_.PushBack();

    entry.key = key;
    entry.value = value;

    WalkUp_(entry, entries_.size() - 1);
  }

  Value Pop() {
    Value t = entries_[0].value;

    PopOnly();

    return t;
  }

  void PopOnly() {
    Entry entry;
    entries_.PopBackInit(&entry);

    if (likely(entries_.size() != 0)) {
      WalkDown_(entry, 0);
    }
  }

  Value top() const {
    return entries_[0].value;
  }

  Key top_key() const {
    return entries_[0].key;
  }
  
  void set_top(Value v) {
    entries_[0].value = v;
  }

  index_t size() const {
    return entries_.size();
  }

 private:
  static index_t ChildIndex_(index_t i) {
    return (i << 1) + 1;
  }

  static index_t ParentIndex_(index_t i) {
    return (i - 1) >> 1;
  }

  index_t WalkDown_(const Entry& entry, index_t i) {
    Key key = entry.key;
    Entry *entries = entries_.begin();
    index_t last = entries_.size() - 1;

    for (;;) {
      index_t c = ChildIndex_(i);

      if (unlikely(c > last)) {
        break;
      }

      // TODO: This "if" can be avoided if we're more intelligent...
      if (likely(c != last)) {
        c += entries[c + 1].key < entries[c].key ? 1 : 0;
      }

      if (key <= entries[c].key) {
        break;
      }

      entries[i] = entries[c];
      i = c;
    }

    entries[i] = entry;

    return i;
  }

  index_t WalkUp_(const Entry& entry, index_t i) {
    Key key = entry.key;
    Entry *entries = entries_.begin();

    for (;;) {
      index_t p;

      if (unlikely(i == 0)) {
        break; // highly unlikely, we found the best!
      }

      p = ParentIndex_(i);

      if (key >= entries[p].key) {
        break;
      }

      entries[i] = entries[p];

      i = p;
    }

    entries[i] = entry;

    return i;
  }
};

#endif