diff options
Diffstat (limited to 'kaldi_io/src/kaldi/util/stl-utils.h')
| -rw-r--r-- | kaldi_io/src/kaldi/util/stl-utils.h | 327 |
1 files changed, 327 insertions, 0 deletions
diff --git a/kaldi_io/src/kaldi/util/stl-utils.h b/kaldi_io/src/kaldi/util/stl-utils.h new file mode 100644 index 0000000..12526ff --- /dev/null +++ b/kaldi_io/src/kaldi/util/stl-utils.h @@ -0,0 +1,327 @@ +// util/stl-utils.h + +// Copyright 2009-2011 Microsoft Corporation; Saarland University + +// See ../../COPYING for clarification regarding multiple authors +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// THIS CODE IS PROVIDED *AS IS* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, EITHER EXPRESS OR IMPLIED, INCLUDING WITHOUT LIMITATION ANY IMPLIED +// WARRANTIES OR CONDITIONS OF TITLE, FITNESS FOR A PARTICULAR PURPOSE, +// MERCHANTABLITY OR NON-INFRINGEMENT. +// See the Apache 2 License for the specific language governing permissions and +// limitations under the License. + +#ifndef KALDI_UTIL_STL_UTILS_H_ +#define KALDI_UTIL_STL_UTILS_H_ + +#include <algorithm> +#include <map> +#include <set> +#include <string> +#include <vector> +#include "base/kaldi-common.h" + +#ifdef _MSC_VER +#include <unordered_map> +#include <unordered_set> +using std::unordered_map; +using std::unordered_set; +#elif __cplusplus > 199711L || defined(__GXX_EXPERIMENTAL_CXX0X__) +#include <unordered_map> +#include <unordered_set> +using std::unordered_map; +using std::unordered_set; +#else +#include <tr1/unordered_map> +#include <tr1/unordered_set> +using std::tr1::unordered_map; +using std::tr1::unordered_set; +#endif + + +namespace kaldi { + +/// Sorts and uniq's (removes duplicates) from a vector. +template<typename T> +inline void SortAndUniq(std::vector<T> *vec) { + std::sort(vec->begin(), vec->end()); + vec->erase(std::unique(vec->begin(), vec->end()), vec->end()); +} + + +/// Returns true if the vector is sorted. +template<typename T> +inline bool IsSorted(const std::vector<T> &vec) { + typename std::vector<T>::const_iterator iter = vec.begin(), end = vec.end(); + if (iter == end) return true; + while (1) { + typename std::vector<T>::const_iterator next_iter = iter; + ++next_iter; + if (next_iter == end) return true; // end of loop and nothing out of order + if (*next_iter < *iter) return false; + iter = next_iter; + } +} + + +/// Returns true if the vector is sorted and contains each element +/// only once. +template<typename T> +inline bool IsSortedAndUniq(const std::vector<T> &vec) { + typename std::vector<T>::const_iterator iter = vec.begin(), end = vec.end(); + if (iter == end) return true; + while (1) { + typename std::vector<T>::const_iterator next_iter = iter; + ++next_iter; + if (next_iter == end) return true; // end of loop and nothing out of order + if (*next_iter <= *iter) return false; + iter = next_iter; + } +} + + +/// Removes duplicate elements from a sorted list. +template<typename T> +inline void Uniq(std::vector<T> *vec) { // must be already sorted. + KALDI_PARANOID_ASSERT(IsSorted(*vec)); + KALDI_ASSERT(vec); + vec->erase(std::unique(vec->begin(), vec->end()), vec->end()); +} + +/// Copies the elements of a set to a vector. +template<class T> +void CopySetToVector(const std::set<T> &s, std::vector<T> *v) { + // adds members of s to v, in sorted order from lowest to highest + // (because the set was in sorted order). + KALDI_ASSERT(v != NULL); + v->resize(s.size()); + typename std::set<T>::const_iterator siter = s.begin(), send = s.end(); + typename std::vector<T>::iterator viter = v->begin(); + for (; siter != send; ++siter, ++viter) { + *viter = *siter; + } +} + +template<class T> +void CopySetToVector(const unordered_set<T> &s, std::vector<T> *v) { + // adds members of s to v, in sorted order from lowest to highest + // (because the set was in sorted order). + KALDI_ASSERT(v != NULL); + v->resize(s.size()); + typename unordered_set<T>::const_iterator siter = s.begin(), send = s.end(); + typename std::vector<T>::iterator viter = v->begin(); + for (; siter != send; ++siter, ++viter) { + *viter = *siter; + } +} + + +/// Copies the (key, value) pairs in a map to a vector of pairs. +template<class A, class B> +void CopyMapToVector(const std::map<A, B> &m, + std::vector<std::pair<A, B> > *v) { + KALDI_ASSERT(v != NULL); + v->resize(m.size()); + typename std::map<A, B>::const_iterator miter = m.begin(), mend = m.end(); + typename std::vector<std::pair<A, B> >::iterator viter = v->begin(); + for (; miter != mend; ++miter, ++viter) { + *viter = std::make_pair(miter->first, miter->second); + // do it like this because of const casting. + } +} + +/// Copies the keys in a map to a vector. +template<class A, class B> +void CopyMapKeysToVector(const std::map<A, B> &m, std::vector<A> *v) { + KALDI_ASSERT(v != NULL); + v->resize(m.size()); + typename std::map<A, B>::const_iterator miter = m.begin(), mend = m.end(); + typename std::vector<A>::iterator viter = v->begin(); + for (; miter != mend; ++miter, ++viter) { + *viter = miter->first; + } +} + +/// Copies the values in a map to a vector. +template<class A, class B> +void CopyMapValuesToVector(const std::map<A, B> &m, std::vector<B> *v) { + KALDI_ASSERT(v != NULL); + v->resize(m.size()); + typename std::map<A, B>::const_iterator miter = m.begin(), mend = m.end(); + typename std::vector<B>::iterator viter = v->begin(); + for (; miter != mend; ++miter, ++viter) { + *viter = miter->second; + } +} + +/// Copies the keys in a map to a set. +template<class A, class B> +void CopyMapKeysToSet(const std::map<A, B> &m, std::set<A> *s) { + KALDI_ASSERT(s != NULL); + s->clear(); + typename std::map<A, B>::const_iterator miter = m.begin(), mend = m.end(); + for (; miter != mend; ++miter) { + s->insert(s->end(), miter->first); + } +} + +/// Copies the values in a map to a set. +template<class A, class B> +void CopyMapValuesToSet(const std::map<A, B> &m, std::set<B> *s) { + KALDI_ASSERT(s != NULL); + s->clear(); + typename std::map<A, B>::const_iterator miter = m.begin(), mend = m.end(); + for (; miter != mend; ++miter) + s->insert(s->end(), miter->second); +} + + +/// Copies the contents of a vector to a set. +template<class A> +void CopyVectorToSet(const std::vector<A> &v, std::set<A> *s) { + KALDI_ASSERT(s != NULL); + s->clear(); + typename std::vector<A>::const_iterator iter = v.begin(), end = v.end(); + for (; iter != end; ++iter) + s->insert(s->end(), *iter); + // s->end() is a hint in case v was sorted. will work regardless. +} + +/// Deletes any non-NULL pointers in the vector v, and sets +/// the corresponding entries of v to NULL +template<class A> +void DeletePointers(std::vector<A*> *v) { + KALDI_ASSERT(v != NULL); + typename std::vector<A*>::iterator iter = v->begin(), end = v->end(); + for (; iter != end; ++iter) { + if (*iter != NULL) { + delete *iter; + *iter = NULL; // set to NULL for extra safety. + } + } +} + +/// Returns true if the vector of pointers contains NULL pointers. +template<class A> +bool ContainsNullPointers(const std::vector<A*> &v) { + typename std::vector<A*>::const_iterator iter = v.begin(), end = v.end(); + for (; iter != end; ++iter) + if (*iter == static_cast<A*> (NULL)) return true; + return false; +} + +/// Copies the contents a vector of one type to a vector +/// of another type. +template<typename A, typename B> +void CopyVectorToVector(const std::vector<A> &vec_in, std::vector<B> *vec_out) { + KALDI_ASSERT(vec_out != NULL); + vec_out->resize(vec_in.size()); + for (size_t i = 0; i < vec_in.size(); i++) + (*vec_out)[i] = static_cast<B> (vec_in[i]); +} + +/// A hashing function-object for vectors. +template<typename Int> +struct VectorHasher { // hashing function for vector<Int>. + size_t operator()(const std::vector<Int> &x) const { + size_t ans = 0; + typename std::vector<Int>::const_iterator iter = x.begin(), end = x.end(); + for (; iter != end; ++iter) { + ans *= kPrime; + ans += *iter; + } + return ans; + } + VectorHasher() { // Check we're instantiated with an integer type. + KALDI_ASSERT_IS_INTEGER_TYPE(Int); + } + private: + static const int kPrime = 7853; +}; + +/// A hashing function-object for pairs of ints +template<typename Int> +struct PairHasher { // hashing function for pair<int> + size_t operator()(const std::pair<Int,Int> &x) const { + return x.first + x.second * kPrime; + } + PairHasher() { // Check we're instantiated with an integer type. + KALDI_ASSERT_IS_INTEGER_TYPE(Int); + } + private: + static const int kPrime = 7853; +}; + + +/// A hashing function object for strings. +struct StringHasher { // hashing function for std::string + size_t operator()(const std::string &str) const { + size_t ans = 0, len = str.length(); + const char *c = str.c_str(), *end = c + len; + for (; c != end; c++) { + ans *= kPrime; + ans += *c; + } + return ans; + } + private: + static const int kPrime = 7853; +}; + +/// Reverses the contents of a vector. +template<typename T> +inline void ReverseVector(std::vector<T> *vec) { + KALDI_ASSERT(vec != NULL); + size_t sz = vec->size(); + for (size_t i = 0; i < sz/2; i++) + std::swap( (*vec)[i], (*vec)[sz-1-i]); +} + + +/// Comparator object for pairs that compares only the first pair. +template<class A, class B> +struct CompareFirstMemberOfPair { + inline bool operator() (const std::pair<A, B> &p1, + const std::pair<A, B> &p2) { + return p1.first < p2.first; + } +}; + +/// For a vector of pair<I, F> where I is an integer and F a floating-point or +/// integer type, this function sorts a vector of type vector<pair<I, F> > on +/// the I value and then merges elements with equal I values, summing these over +/// the F component and then removing any F component with zero value. This +/// is for where the vector of pairs represents a map from the integer to float +/// component, with an "adding" type of semantics for combining the elements. +template<typename I, typename F> +inline void MergePairVectorSumming(std::vector<std::pair<I, F> > *vec) { + KALDI_ASSERT_IS_INTEGER_TYPE(I); + CompareFirstMemberOfPair<I, F> c; + std::sort(vec->begin(), vec->end(), c); // sort on 1st element. + typename std::vector<std::pair<I, F> >::iterator out = vec->begin(), + in = vec->begin(), end = vec->end(); + while (in < end) { + // We reach this point only at the first element of + // each stretch of identical .first elements. + *out = *in; + ++in; + while (in < end && in->first == out->first) { + out->second += in->second; // this is the merge operation. + ++in; + } + if (out->second != static_cast<F>(0)) // Don't keep zero elements. + out++; + } + vec->erase(out, end); +} + +} // namespace kaldi + +#endif // KALDI_UTIL_STL_UTILS_H_ + |