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>
27using std::vector;
28#include <functional>
29
30#include <fst/compat.h>
31namespace 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
51static const int kNoKey = -1;
52template <class T, class Compare, bool max>
53class Heap {
54 public:
55
56  // Initialize with a specific comparator
57  Heap(Compare comp) : comp_(comp), size_(0) { }
58
59  // Create a heap with initial size of internal arrays of 0
60  Heap() : size_(0) { }
61
62  ~Heap() { }
63
64  // Insert a value into the heap
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.
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.
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.
106  T Top() const {
107    return A_[0];
108  }
109
110  // Check if the heap is empty
111  bool Empty() const {
112    return size_ == 0;
113  }
114
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
126  int Left(int i) {
127    return 2*(i+1)-1;   // 0 -> 1, 1 -> 3
128  }
129
130  // Compute right child of parent
131  int Right(int i) {
132    return 2*(i+1);     // 0 -> 2, 1 -> 4
133  }
134
135  // Given a child compute parent
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
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.
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.
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
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