14a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// heap.h 24a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 34a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Licensed under the Apache License, Version 2.0 (the "License"); 44a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// you may not use this file except in compliance with the License. 54a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// You may obtain a copy of the License at 64a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 74a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// http://www.apache.org/licenses/LICENSE-2.0 84a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 94a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Unless required by applicable law or agreed to in writing, software 104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// distributed under the License is distributed on an "AS IS" BASIS, 114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// See the License for the specific language governing permissions and 134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// limitations under the License. 144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// \file 174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Implementation of a heap as in STL, but allows tracking positions 184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// in heap using a key. The key can be used to do an in place update of 194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// values in the heap. 204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#ifndef FST_LIB_HEAP_H__ 224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#define FST_LIB_HEAP_H__ 234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <functional> 254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#include <vector> 264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectnamespace fst { 284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// \class Heap 314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// \brief A templated heap implementation that support in place update 324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// of values. 334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// The templated heap implementation is a little different from the 354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// STL priority_queue and the *_heap operations in STL. The heap 364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// supports indexing of values in the heap via an associated key. 374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// Each value is internally associated with a key which is returned 394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// to the calling functions on heap insert. This key can be used 404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// to later update the specific value in the heap. 414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// \param T the element type of the hash, can be POD, Data or Ptr to Data 434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// \param Compare Comparison class for determing min-heapness of max-heapness 444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project// 454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectstatic const int kNoKey = -1; 464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projecttemplate <class T, class Compare> 474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Projectclass Heap { 484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project public: 494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // initialize with a specific comparator 514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Heap(Compare comp) : comp_(comp), size_(0) { } 524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Create a heap with initial size of internal arrays of 1024 544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Heap() : size_(0) { } 554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ~Heap() { } 574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // insert a value into the heap 594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project int Insert(const T& val) { 604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (size_ < (int)A_.size()) { 614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project A_[size_] = val; 624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pos_[key_[size_]] = size_; 634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project A_.push_back(val); 654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pos_.push_back(size_); 664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project key_.push_back(size_); 674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project ++size_; 704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return Insert(val, size_ - 1); 714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // update a value at position given by the key. The pos array is first 744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // indexed by the key. The position gives the position in the heap array. 754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // Once we have the position we can then use the standard heap operations 764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // to calculate the parent and child positions. 774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Update(int key, const T& val) { 784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project int i = pos_[key]; 794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (comp_(val, A_[Parent(i)])) { 804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Insert(val, i); 814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } else { 824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project A_[i] = val; 834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Heapify(i); 844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // pop the (best/worst) from the heap 884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project T Pop() { 894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project T max = A_[0]; 904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Swap(0, size_-1); 924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_--; 934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Heapify(0); 944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return(max); 954a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 964a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 974a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // return value of best in heap 984a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project T Top() const { 994a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return A_[0]; 1004a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1014a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1024a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // check if the heap is empty 1034a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project bool Empty() const { 1044a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return(size_ == 0); 1054a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1064a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1074a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Clear() { 1084a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project size_ = 0; 1094a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1104a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1114a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1124a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // 1134a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // The following protected routines is used in a supportive role 1144a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // for managing the heap and keeping the heap properties. 1154a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // 1164a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 1174a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // compute left child of parent 1184a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project int Left(int i) { 1194a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return 2*(i+1)-1; // 0 -> 1, 1 -> 3 1204a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1214a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1224a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // compute right child of parent 1234a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project int Right(int i) { 1244a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return 2*(i+1); // 0 -> 2, 1 -> 4 1254a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1264a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1274a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // given a child compute parent 1284a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project int Parent(int i) { 1294a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return (i-1)/2; // 1 -> 0, 2 -> 0, 3 -> 1, 4-> 1 1304a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1314a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1324a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // swap a child, parent. Use to move element up/down tree 1334a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // note a little tricky here. When we swap we need to swap 1344a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // the value 1354a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // the associated keys 1364a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // the position of the value in the heap 1374a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Swap(int j, int k) { 1384a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project int tkey = key_[j]; 1394a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pos_[key_[j] = key_[k]] = j; 1404a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project pos_[key_[k] = tkey] = k; 1414a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1424a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project T val = A_[j]; 1434a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project A_[j] = A_[k]; 1444a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project A_[k] = val; 1454a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1464a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1474a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1484a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // heapify subtree rooted at index i. 1494a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project void Heapify(int i) { 1504a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project int l = Left(i); 1514a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project int r = Right(i); 1524a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project int largest; 1534a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1544a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (l < size_ && comp_(A_[l], A_[i]) ) 1554a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project largest = l; 1564a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project else 1574a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project largest = i; 1584a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1594a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (r < size_ && comp_(A_[r], A_[largest]) ) 1604a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project largest = r; 1614a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1624a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project if (largest != i) { 1634a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Swap(i, largest); 1644a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Heapify(largest); 1654a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1664a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1674a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1684a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1694a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // insert(update) element at subtree rooted at index i 1704a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project int Insert(const T& val, int i) { 1714a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project int p; 1724a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project while (i > 0 && !comp_(A_[p = Parent(i)], val)) { 1734a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Swap(i, p); 1744a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project i = p; 1754a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1764a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1774a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project return key_[i]; 1784a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project } 1794a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1804a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1814a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project private: 1824a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project Compare comp_; 1834a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1844a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<int> pos_; 1854a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<int> key_; 1864a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project vector<T> A_; 1874a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project int size_; 1884a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1894a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project // DISALLOW_EVIL_CONSTRUCTORS(Heap); 1904a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project}; 1914a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1924a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project} 1934a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project 1944a68b3365c8c50aa93505e99ead2565ab73dcdb0The Android Open Source Project#endif // FST_LIB_HEAP_H__ 195