// 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_