stl-utils.h
Go to the documentation of this file.
1 // util/stl-utils.h
2 
3 // Copyright 2009-2011 Microsoft Corporation; Saarland University
4 
5 // See ../../COPYING for clarification regarding multiple authors
6 //
7 // Licensed under the Apache License, Version 2.0 (the "License");
8 // you may not use this file except in compliance with the License.
9 // You may obtain a copy of the License at
10 //
11 // http://www.apache.org/licenses/LICENSE-2.0
12 //
13 // THIS CODE IS PROVIDED *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14 // KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED
15 // WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE,
16 // MERCHANTABLITY OR NON-INFRINGEMENT.
17 // See the Apache 2 License for the specific language governing permissions and
18 // limitations under the License.
19 
20 #ifndef KALDI_UTIL_STL_UTILS_H_
21 #define KALDI_UTIL_STL_UTILS_H_
22 
23 #include <unordered_map>
24 #include <unordered_set>
25 using std::unordered_map;
26 using std::unordered_set;
27 
28 #include <algorithm>
29 #include <map>
30 #include <set>
31 #include <string>
32 #include <vector>
33 #include "base/kaldi-common.h"
34 
35 namespace kaldi {
36 
38 template<typename T>
39 inline void SortAndUniq(std::vector<T> *vec) {
40  std::sort(vec->begin(), vec->end());
41  vec->erase(std::unique(vec->begin(), vec->end()), vec->end());
42 }
43 
44 
46 template<typename T>
47 inline bool IsSorted(const std::vector<T> &vec) {
48  typename std::vector<T>::const_iterator iter = vec.begin(), end = vec.end();
49  if (iter == end) return true;
50  while (1) {
51  typename std::vector<T>::const_iterator next_iter = iter;
52  ++next_iter;
53  if (next_iter == end) return true; // end of loop and nothing out of order
54  if (*next_iter < *iter) return false;
55  iter = next_iter;
56  }
57 }
58 
59 
62 template<typename T>
63 inline bool IsSortedAndUniq(const std::vector<T> &vec) {
64  typename std::vector<T>::const_iterator iter = vec.begin(), end = vec.end();
65  if (iter == end) return true;
66  while (1) {
67  typename std::vector<T>::const_iterator next_iter = iter;
68  ++next_iter;
69  if (next_iter == end) return true; // end of loop and nothing out of order
70  if (*next_iter <= *iter) return false;
71  iter = next_iter;
72  }
73 }
74 
75 
77 template<typename T>
78 inline void Uniq(std::vector<T> *vec) { // must be already sorted.
80  KALDI_ASSERT(vec);
81  vec->erase(std::unique(vec->begin(), vec->end()), vec->end());
82 }
83 
85 template<class T>
86 void CopySetToVector(const std::set<T> &s, std::vector<T> *v) {
87  // copies members of s into v, in sorted order from lowest to highest
88  // (because the set was in sorted order).
89  KALDI_ASSERT(v != NULL);
90  v->resize(s.size());
91  typename std::set<T>::const_iterator siter = s.begin(), send = s.end();
92  typename std::vector<T>::iterator viter = v->begin();
93  for (; siter != send; ++siter, ++viter) {
94  *viter = *siter;
95  }
96 }
97 
98 template<class T>
99 void CopySetToVector(const unordered_set<T> &s, std::vector<T> *v) {
100  KALDI_ASSERT(v != NULL);
101  v->resize(s.size());
102  typename unordered_set<T>::const_iterator siter = s.begin(), send = s.end();
103  typename std::vector<T>::iterator viter = v->begin();
104  for (; siter != send; ++siter, ++viter) {
105  *viter = *siter;
106  }
107 }
108 
109 
111 template<class A, class B>
112 void CopyMapToVector(const std::map<A, B> &m,
113  std::vector<std::pair<A, B> > *v) {
114  KALDI_ASSERT(v != NULL);
115  v->resize(m.size());
116  typename std::map<A, B>::const_iterator miter = m.begin(), mend = m.end();
117  typename std::vector<std::pair<A, B> >::iterator viter = v->begin();
118  for (; miter != mend; ++miter, ++viter) {
119  *viter = std::make_pair(miter->first, miter->second);
120  // do it like this because of const casting.
121  }
122 }
123 
125 template<class A, class B>
126 void CopyMapKeysToVector(const std::map<A, B> &m, std::vector<A> *v) {
127  KALDI_ASSERT(v != NULL);
128  v->resize(m.size());
129  typename std::map<A, B>::const_iterator miter = m.begin(), mend = m.end();
130  typename std::vector<A>::iterator viter = v->begin();
131  for (; miter != mend; ++miter, ++viter) {
132  *viter = miter->first;
133  }
134 }
135 
137 template<class A, class B>
138 void CopyMapValuesToVector(const std::map<A, B> &m, std::vector<B> *v) {
139  KALDI_ASSERT(v != NULL);
140  v->resize(m.size());
141  typename std::map<A, B>::const_iterator miter = m.begin(), mend = m.end();
142  typename std::vector<B>::iterator viter = v->begin();
143  for (; miter != mend; ++miter, ++viter) {
144  *viter = miter->second;
145  }
146 }
147 
149 template<class A, class B>
150 void CopyMapKeysToSet(const std::map<A, B> &m, std::set<A> *s) {
151  KALDI_ASSERT(s != NULL);
152  s->clear();
153  typename std::map<A, B>::const_iterator miter = m.begin(), mend = m.end();
154  for (; miter != mend; ++miter) {
155  s->insert(s->end(), miter->first);
156  }
157 }
158 
160 template<class A, class B>
161 void CopyMapValuesToSet(const std::map<A, B> &m, std::set<B> *s) {
162  KALDI_ASSERT(s != NULL);
163  s->clear();
164  typename std::map<A, B>::const_iterator miter = m.begin(), mend = m.end();
165  for (; miter != mend; ++miter)
166  s->insert(s->end(), miter->second);
167 }
168 
169 
171 template<class A>
172 void CopyVectorToSet(const std::vector<A> &v, std::set<A> *s) {
173  KALDI_ASSERT(s != NULL);
174  s->clear();
175  typename std::vector<A>::const_iterator iter = v.begin(), end = v.end();
176  for (; iter != end; ++iter)
177  s->insert(s->end(), *iter);
178  // s->end() is a hint in case v was sorted. will work regardless.
179 }
180 
183 template<class A>
184 void DeletePointers(std::vector<A*> *v) {
185  KALDI_ASSERT(v != NULL);
186  typename std::vector<A*>::iterator iter = v->begin(), end = v->end();
187  for (; iter != end; ++iter) {
188  if (*iter != NULL) {
189  delete *iter;
190  *iter = NULL; // set to NULL for extra safety.
191  }
192  }
193 }
194 
196 template<class A>
197 bool ContainsNullPointers(const std::vector<A*> &v) {
198  typename std::vector<A*>::const_iterator iter = v.begin(), end = v.end();
199  for (; iter != end; ++iter)
200  if (*iter == static_cast<A*> (NULL)) return true;
201  return false;
202 }
203 
206 template<typename A, typename B>
207 void CopyVectorToVector(const std::vector<A> &vec_in, std::vector<B> *vec_out) {
208  KALDI_ASSERT(vec_out != NULL);
209  vec_out->resize(vec_in.size());
210  for (size_t i = 0; i < vec_in.size(); i++)
211  (*vec_out)[i] = static_cast<B> (vec_in[i]);
212 }
213 
215 template<typename Int>
216 struct VectorHasher { // hashing function for vector<Int>.
217  size_t operator()(const std::vector<Int> &x) const noexcept {
218  size_t ans = 0;
219  typename std::vector<Int>::const_iterator iter = x.begin(), end = x.end();
220  for (; iter != end; ++iter) {
221  ans *= kPrime;
222  ans += *iter;
223  }
224  return ans;
225  }
226  VectorHasher() { // Check we're instantiated with an integer type.
228  }
229  private:
230  static const int kPrime = 7853;
231 };
232 
234 template<typename Int1, typename Int2 = Int1>
235 struct PairHasher { // hashing function for pair<int>
236  size_t operator()(const std::pair<Int1, Int2> &x) const noexcept {
237  // 7853 was chosen at random from a list of primes.
238  return x.first + x.second * 7853;
239  }
240  PairHasher() { // Check we're instantiated with an integer type.
243  }
244 };
245 
246 
248 struct StringHasher { // hashing function for std::string
249  size_t operator()(const std::string &str) const noexcept {
250  size_t ans = 0, len = str.length();
251  const char *c = str.c_str(), *end = c + len;
252  for (; c != end; c++) {
253  ans *= kPrime;
254  ans += *c;
255  }
256  return ans;
257  }
258  private:
259  static const int kPrime = 7853;
260 };
261 
263 template<typename T>
264 inline void ReverseVector(std::vector<T> *vec) {
265  KALDI_ASSERT(vec != NULL);
266  size_t sz = vec->size();
267  for (size_t i = 0; i < sz/2; i++)
268  std::swap( (*vec)[i], (*vec)[sz-1-i]);
269 }
270 
271 
273 template<class A, class B>
275  inline bool operator() (const std::pair<A, B> &p1,
276  const std::pair<A, B> &p2) {
277  return p1.first < p2.first;
278  }
279 };
280 
287 template<typename I, typename F>
288 inline void MergePairVectorSumming(std::vector<std::pair<I, F> > *vec) {
291  std::sort(vec->begin(), vec->end(), c); // sort on 1st element.
292  typename std::vector<std::pair<I, F> >::iterator out = vec->begin(),
293  in = vec->begin(), end = vec->end();
294  // special case: while there is nothing to be changed, skip over
295  // initial input (avoids unnecessary copying).
296  while (in + 1 < end && in[0].first != in[1].first && in[0].second != 0.0) {
297  in++;
298  out++;
299  }
300  while (in < end) {
301  // We reach this point only at the first element of
302  // each stretch of identical .first elements.
303  *out = *in;
304  ++in;
305  while (in < end && in->first == out->first) {
306  out->second += in->second; // this is the merge operation.
307  ++in;
308  }
309  if (out->second != static_cast<F>(0)) // Don't keep zero elements.
310  out++;
311  }
312  vec->erase(out, end);
313 }
314 
315 } // namespace kaldi
316 
317 #endif // KALDI_UTIL_STL_UTILS_H_
This code computes Goodness of Pronunciation (GOP) and extracts phone-level pronunciation feature for...
Definition: chain.dox:20
void CopySetToVector(const std::set< T > &s, std::vector< T > *v)
Copies the elements of a set to a vector.
Definition: stl-utils.h:86
void DeletePointers(std::vector< A *> *v)
Deletes any non-NULL pointers in the vector v, and sets the corresponding entries of v to NULL...
Definition: stl-utils.h:184
A hashing function-object for vectors.
Definition: stl-utils.h:216
void CopyMapValuesToSet(const std::map< A, B > &m, std::set< B > *s)
Copies the values in a map to a set.
Definition: stl-utils.h:161
void CopyMapKeysToVector(const std::map< A, B > &m, std::vector< A > *v)
Copies the keys in a map to a vector.
Definition: stl-utils.h:126
#define KALDI_ASSERT_IS_INTEGER_TYPE(I)
Definition: kaldi-utils.h:133
void CopyVectorToVector(const std::vector< A > &vec_in, std::vector< B > *vec_out)
Copies the contents a vector of one type to a vector of another type.
Definition: stl-utils.h:207
void Uniq(std::vector< T > *vec)
Removes duplicate elements from a sorted list.
Definition: stl-utils.h:78
Comparator object for pairs that compares only the first pair.
Definition: stl-utils.h:274
void swap(basic_filebuf< CharT, Traits > &x, basic_filebuf< CharT, Traits > &y)
static const int kPrime
Definition: stl-utils.h:230
bool ContainsNullPointers(const std::vector< A *> &v)
Returns true if the vector of pointers contains NULL pointers.
Definition: stl-utils.h:197
void CopyVectorToSet(const std::vector< A > &v, std::set< A > *s)
Copies the contents of a vector to a set.
Definition: stl-utils.h:172
void SortAndUniq(std::vector< T > *vec)
Sorts and uniq&#39;s (removes duplicates) from a vector.
Definition: stl-utils.h:39
A hashing function object for strings.
Definition: stl-utils.h:248
size_t operator()(const std::pair< Int1, Int2 > &x) const noexcept
Definition: stl-utils.h:236
size_t operator()(const std::string &str) const noexcept
Definition: stl-utils.h:249
void CopyMapKeysToSet(const std::map< A, B > &m, std::set< A > *s)
Copies the keys in a map to a set.
Definition: stl-utils.h:150
void CopyMapValuesToVector(const std::map< A, B > &m, std::vector< B > *v)
Copies the values in a map to a vector.
Definition: stl-utils.h:138
#define KALDI_PARANOID_ASSERT(cond)
Definition: kaldi-error.h:206
void ReverseVector(std::vector< T > *vec)
Reverses the contents of a vector.
Definition: stl-utils.h:264
bool IsSorted(const std::vector< T > &vec)
Returns true if the vector is sorted.
Definition: stl-utils.h:47
#define KALDI_ASSERT(cond)
Definition: kaldi-error.h:185
void MergePairVectorSumming(std::vector< std::pair< I, F > > *vec)
For a vector of pair<I, F> where I is an integer and F a floating-point or integer type...
Definition: stl-utils.h:288
bool IsSortedAndUniq(const std::vector< T > &vec)
Returns true if the vector is sorted and contains each element only once.
Definition: stl-utils.h:63
void CopyMapToVector(const std::map< A, B > &m, std::vector< std::pair< A, B > > *v)
Copies the (key, value) pairs in a map to a vector of pairs.
Definition: stl-utils.h:112
size_t operator()(const std::vector< Int > &x) const noexcept
Definition: stl-utils.h:217
A hashing function-object for pairs of ints.
Definition: stl-utils.h:235