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