// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// Copyright 2005-2010 Google, Inc.
// All Rights Reserved.
// Author: Johan Schalkwyk (johans@google.com)
//
// \file
// Implementation of a heap as in STL, but allows tracking positions
// in heap using a key. The key can be used to do an in-place update of
// values in the heap.
#ifndef FST_LIB_HEAP_H__
#define FST_LIB_HEAP_H__
#include <vector>
using std::vector;
#include <functional>
#include <fst/compat.h>
namespace fst {
//
// \class Heap
// \brief A templated heap implementation that support in-place update
// of values.
//
// The templated heap implementation is a little different from the
// STL priority_queue and the *_heap operations in STL. This heap
// supports indexing of values in the heap via an associated key.
//
// Each value is internally associated with a key which is returned
// to the calling functions on heap insert. This key can be used
// to later update the specific value in the heap.
//
// \param T the element type of the hash, can be POD, Data or Ptr to Data
// \param Compare Comparison class for determiningg min-heapness.
// \param whether heap top should be max or min element w.r.t. Compare
//
static const int kNoKey = -1;
template <class T, class Compare, bool max>
class Heap {
public:
// Initialize with a specific comparator
Heap(Compare comp) : comp_(comp), size_(0) { }
// Create a heap with initial size of internal arrays of 0
Heap() : size_(0) { }
~Heap() { }
// Insert a value into the heap
int Insert(const T& val) {
if (size_ < A_.size()) {
A_[size_] = val;
pos_[key_[size_]] = size_;
} else {
A_.push_back(val);
pos_.push_back(size_);
key_.push_back(size_);
}
++size_;
return Insert(val, size_ - 1);
}
// Update a value at position given by the key. The pos array is first
// indexed by the key. The position gives the position in the heap array.
// Once we have the position we can then use the standard heap operations
// to calculate the parent and child positions.
void Update(int key, const T& val) {
int i = pos_[key];
if (Better(val, A_[Parent(i)])) {
Insert(val, i);
} else {
A_[i] = val;
Heapify(i);
}
}
// Return the greatest (max=true) / least (max=false) value w.r.t.
// from the heap.
T Pop() {
T top = A_[0];
Swap(0, size_-1);
size_--;
Heapify(0);
return top;
}
// Return the greatest (max=true) / least (max=false) value w.r.t.
// comp object from the heap.
T Top() const {
return A_[0];
}
// Check if the heap is empty
bool Empty() const {
return size_ == 0;
}
void Clear() {
size_ = 0;
}
//
// The following protected routines are used in a supportive role
// for managing the heap and keeping the heap properties.
//
private:
// Compute left child of parent
int Left(int i) {
return 2*(i+1)-1; // 0 -> 1, 1 -> 3
}
// Compute right child of parent
int Right(int i) {
return 2*(i+1); // 0 -> 2, 1 -> 4
}
// Given a child compute parent
int Parent(int i) {
return (i-1)/2; // 1 -> 0, 2 -> 0, 3 -> 1, 4-> 1
}
// Swap a child, parent. Use to move element up/down tree.
// Note a little tricky here. When we swap we need to swap:
// the value
// the associated keys
// the position of the value in the heap
void Swap(int j, int k) {
int tkey = key_[j];
pos_[key_[j] = key_[k]] = j;
pos_[key_[k] = tkey] = k;
T val = A_[j];
A_[j] = A_[k];
A_[k] = val;
}
// Returns the greater (max=true) / least (max=false) of two
// elements.
bool Better(const T& x, const T& y) {
return max ? comp_(y, x) : comp_(x, y);
}
// Heapify subtree rooted at index i.
void Heapify(int i) {
int l = Left(i);
int r = Right(i);
int largest;
if (l < size_ && Better(A_[l], A_[i]) )
largest = l;
else
largest = i;
if (r < size_ && Better(A_[r], A_[largest]) )
largest = r;
if (largest != i) {
Swap(i, largest);
Heapify(largest);
}
}
// Insert (update) element at subtree rooted at index i
int Insert(const T& val, int i) {
int p;
while (i > 0 && !Better(A_[p = Parent(i)], val)) {
Swap(i, p);
i = p;
}
return key_[i];
}
private:
Compare comp_;
vector<int> pos_;
vector<int> key_;
vector<T> A_;
int size_;
// DISALLOW_COPY_AND_ASSIGN(Heap);
};
} // namespace fst
#endif // FST_LIB_HEAP_H__