heap.h revision f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2
1f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 2f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Licensed under the Apache License, Version 2.0 (the "License"); 3f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// you may not use this file except in compliance with the License. 4f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// You may obtain a copy of the License at 5f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 6f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// http://www.apache.org/licenses/LICENSE-2.0 7f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 8f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Unless required by applicable law or agreed to in writing, software 9f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// distributed under the License is distributed on an "AS IS" BASIS, 10f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 11f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// See the License for the specific language governing permissions and 12f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// limitations under the License. 13f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 14f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Copyright 2005-2010 Google, Inc. 15f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// All Rights Reserved. 16f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Author: Johan Schalkwyk (johans@google.com) 17f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 18f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// \file 19f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Implementation of a heap as in STL, but allows tracking positions 20f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// in heap using a key. The key can be used to do an in-place update of 21f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// values in the heap. 22f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 23f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#ifndef FST_LIB_HEAP_H__ 24f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#define FST_LIB_HEAP_H__ 25f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 26f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <vector> 27f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonusing std::vector; 28f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <functional> 29f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 30f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#include <fst/compat.h> 31f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonnamespace fst { 32f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 33f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 34f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// \class Heap 35f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// \brief A templated heap implementation that support in-place update 36f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// of values. 37f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 38f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// The templated heap implementation is a little different from the 39f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// STL priority_queue and the *_heap operations in STL. This heap 40f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// supports indexing of values in the heap via an associated key. 41f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 42f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// Each value is internally associated with a key which is returned 43f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// to the calling functions on heap insert. This key can be used 44f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// to later update the specific value in the heap. 45f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 46f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// \param T the element type of the hash, can be POD, Data or Ptr to Data 47f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// \param Compare Comparison class for determiningg min-heapness. 48f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// \param whether heap top should be max or min element w.r.t. Compare 49f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson// 50f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 51f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonstatic const int kNoKey = -1; 52f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsontemplate <class T, class Compare, bool max> 53f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodsonclass Heap { 54f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson public: 55f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 56f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Initialize with a specific comparator 57f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Heap(Compare comp) : comp_(comp), size_(0) { } 58f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 59f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Create a heap with initial size of internal arrays of 0 60f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Heap() : size_(0) { } 61f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 62f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ~Heap() { } 63f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 64f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Insert a value into the heap 65f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson int Insert(const T& val) { 66f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (size_ < A_.size()) { 67f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson A_[size_] = val; 68f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson pos_[key_[size_]] = size_; 69f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else { 70f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson A_.push_back(val); 71f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson pos_.push_back(size_); 72f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson key_.push_back(size_); 73f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 74f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 75f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson ++size_; 76f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return Insert(val, size_ - 1); 77f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 78f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 79f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Update a value at position given by the key. The pos array is first 80f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // indexed by the key. The position gives the position in the heap array. 81f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Once we have the position we can then use the standard heap operations 82f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // to calculate the parent and child positions. 83f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Update(int key, const T& val) { 84f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson int i = pos_[key]; 85f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (Better(val, A_[Parent(i)])) { 86f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Insert(val, i); 87f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } else { 88f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson A_[i] = val; 89f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Heapify(i); 90f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 91f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 92f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 93f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Return the greatest (max=true) / least (max=false) value w.r.t. 94f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // from the heap. 95f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson T Pop() { 96f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson T top = A_[0]; 97f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 98f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Swap(0, size_-1); 99f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson size_--; 100f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Heapify(0); 101f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return top; 102f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 103f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 104f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Return the greatest (max=true) / least (max=false) value w.r.t. 105f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // comp object from the heap. 106f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson T Top() const { 107f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return A_[0]; 108f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 109f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 110f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Check if the heap is empty 111f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool Empty() const { 112f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return size_ == 0; 113f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 114f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 115f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Clear() { 116f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson size_ = 0; 117f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 118f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 119f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 120f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // 121f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // The following protected routines are used in a supportive role 122f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // for managing the heap and keeping the heap properties. 123f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // 124f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 125f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Compute left child of parent 126f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson int Left(int i) { 127f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return 2*(i+1)-1; // 0 -> 1, 1 -> 3 128f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 129f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 130f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Compute right child of parent 131f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson int Right(int i) { 132f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return 2*(i+1); // 0 -> 2, 1 -> 4 133f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 134f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 135f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Given a child compute parent 136f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson int Parent(int i) { 137f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return (i-1)/2; // 1 -> 0, 2 -> 0, 3 -> 1, 4-> 1 138f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 139f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 140f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Swap a child, parent. Use to move element up/down tree. 141f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Note a little tricky here. When we swap we need to swap: 142f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // the value 143f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // the associated keys 144f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // the position of the value in the heap 145f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Swap(int j, int k) { 146f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson int tkey = key_[j]; 147f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson pos_[key_[j] = key_[k]] = j; 148f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson pos_[key_[k] = tkey] = k; 149f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 150f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson T val = A_[j]; 151f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson A_[j] = A_[k]; 152f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson A_[k] = val; 153f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 154f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 155f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Returns the greater (max=true) / least (max=false) of two 156f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // elements. 157f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson bool Better(const T& x, const T& y) { 158f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return max ? comp_(y, x) : comp_(x, y); 159f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 160f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 161f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Heapify subtree rooted at index i. 162f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson void Heapify(int i) { 163f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson int l = Left(i); 164f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson int r = Right(i); 165f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson int largest; 166f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 167f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (l < size_ && Better(A_[l], A_[i]) ) 168f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson largest = l; 169f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson else 170f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson largest = i; 171f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 172f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (r < size_ && Better(A_[r], A_[largest]) ) 173f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson largest = r; 174f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 175f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson if (largest != i) { 176f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Swap(i, largest); 177f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Heapify(largest); 178f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 179f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 180f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 181f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 182f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // Insert (update) element at subtree rooted at index i 183f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson int Insert(const T& val, int i) { 184f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson int p; 185f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson while (i > 0 && !Better(A_[p = Parent(i)], val)) { 186f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Swap(i, p); 187f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson i = p; 188f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 189f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 190f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson return key_[i]; 191f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson } 192f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 193f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson private: 194f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson Compare comp_; 195f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 196f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<int> pos_; 197f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<int> key_; 198f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson vector<T> A_; 199f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson int size_; 200f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 201f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson // DISALLOW_COPY_AND_ASSIGN(Heap); 202f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson}; 203f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 204f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson} // namespace fst 205f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson 206f4c12fce1ee58e670f9c3fce46c40296ba9ee8a2Ian Hodson#endif // FST_LIB_HEAP_H__ 207