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