// sequence_algorithm.hpp
// v1.0  24/12/2008
//
// by: Shane Harper (http://shaneharper.net)
// 
// sequence_algorithm.hpp provides a convenient interface to the algorithms
// defined in the C++ STL algorithm header file: Rather than specify sequences
// by two arguments (viz. begin and end iterators), a sequence is specified
// with just one argument.
//
// This file doesn't define the following algorithms which are defined in the
// STL algorithm header file:
//   binary_search, equal_range, generate_n, inplace_merge, lower_bound,
//   nth_element, partial_sort, partial_sort_copy, rotate, rotate_copy,
//   upper_bound
//
// XXX Some of the STL algorithms return an end iterator: Consider wrapping
// these with functions that return a Sequence instead. An example of how this
// could be used:  remove(unique(seq), 42);
//
// XXX Many of the functions are overloaded with one function taking a
// comparison functor, while another overloaded function uses the default
// comparison operator.  Consider having just one function where the comparison
// argument has a default value of the default comparison functor, e.g.
//   max_element(_Sequence& seq, _Compare compare = std::less<typename _Sequence::value_type>())


#ifndef _SEQUENCE_ALGORITHM_HPP
#define _SEQUENCE_ALGORITHM_HPP

#include <algorithm>


template<typename _Sequence, typename _Function>
  inline _Function
  for_each(const _Sequence& seq, _Function fn)
  {
    // gcc -O2 inlines the call to std::for_each.
    return std::for_each(seq.begin(), seq.end(), fn);
  }

template<typename _Sequence, typename _Value>
  inline typename _Sequence::iterator
  find(/*const*/ _Sequence& seq, const _Value& value)
  {
    return std::find(seq.begin(), seq.end(), value);
  }

template<typename _Sequence, typename _Predicate>
  inline typename _Sequence::iterator
  find_if(_Sequence& sequence, _Predicate predicate)
  {
    return std::find_if(sequence.begin(), sequence.end(), predicate);
  }

template<typename _Sequence>
  inline typename _Sequence::iterator
  adjacent_find(/*const*/ _Sequence& seq)
  {
    return std::adjacent_find(seq.begin(), seq.end());
  }

template<typename _Sequence, typename _Value>
  inline typename std::iterator_traits< typename _Sequence::iterator >::difference_type
  count(const _Sequence& seq, const _Value& value)
  {
    return std::count(seq.begin(), seq.end(), value);
  }

template<typename _Sequence, typename _Predicate>
  inline typename std::iterator_traits< typename _Sequence::iterator >::difference_type
  count_if(_Sequence& seq, _Predicate predicate)
  {
    return std::count_if(seq.begin(), seq.end(), predicate);
  }

template<typename _Sequence1, typename _Sequence2>
  inline typename _Sequence1::iterator search(_Sequence1& seq1, const _Sequence2& seq2)
  {
    return std::search(seq1.begin(), seq1.end(), seq2.begin(), seq2.end());
  }

template<typename _Sequence1, typename _Sequence2, typename _BinaryPredicate>
  inline typename _Sequence1::iterator search(_Sequence1& seq1, _Sequence2& seq2, _BinaryPredicate binary_predicate)
  {
    return std::search(seq1.begin(), seq1.end(), seq2.begin(), seq2.end(), binary_predicate);
  }

template<typename _Sequence, typename _Integer, typename _Value>
  inline typename _Sequence::iterator search_n(const _Sequence& seq, const _Integer count, const _Value& value)
  {
    return std::search_n(seq.begin(), seq.end(), count, value);
  }

// search_n taking a binary predicate
//   I find this function a bit bizarre. Wouldn't
//    search_n_if(_Sequence, _Integer count, _UnaryPredicate)
//   make more sense? The unary predicate could be a binary function with one of its arguments 'bound'.
template<typename _Sequence, typename _Integer, typename _Value, typename _BinaryPredicate>
  inline typename _Sequence::iterator
  search_n(/*XXX const ?*/ _Sequence& seq, const _Integer count, const _Value& value, _BinaryPredicate binary_predicate)
  {
    return std::search_n(seq.begin(), seq.end(), count, value, binary_predicate);
  }

template<typename _Sequence, typename _Iterator>
  inline _Iterator
  swap_ranges(_Sequence& seq1, const _Iterator& first2)
  {
    return std::swap_ranges(seq1.begin(), seq1.end(), first2);
  }

template<typename _Sequence, typename _OutputIterator, typename _UnaryOperation>
  inline _OutputIterator
  transform(const _Sequence& seq, _OutputIterator output_iterator, _UnaryOperation unary_op)
  {
    return std::transform(seq.begin(), seq.end(), output_iterator, unary_op);
  }

template<typename _Sequence1, typename _Sequence2Iterator, typename _OutputIterator, typename _BinaryOperation>
  inline _OutputIterator
  transform(_Sequence1& input_seq1, _Sequence2Iterator& input_seq2_iterator, _OutputIterator output_iterator, _BinaryOperation binary_op)
  {
    return std::transform(input_seq1.begin(), input_seq1.end(), input_seq2_iterator, output_iterator, binary_op);
  }

template<typename _Sequence, typename _Value>
  inline void
  replace(_Sequence& seq, const _Value& old_value, const _Value& new_value)
  {
    std::replace(seq.begin(), seq.end(), old_value, new_value);
  }

template<typename _Sequence, typename _Predicate, typename _Value>
  inline void
  replace_if(_Sequence& seq, _Predicate predicate, const _Value& new_value)
  {
    return std::replace_if(seq.begin(), seq.end(), predicate, new_value);
  }

template<typename _Sequence, typename _OutputIterator, typename _Value>
  inline void
  replace_copy(const _Sequence& seq, _OutputIterator output_iterator, const _Value& old_value, const _Value& new_value)
  {
    std::replace_copy(seq.begin(), seq.end(), output_iterator, old_value, new_value);
  }

template<typename _Sequence, typename _OutputIterator, typename _Predicate, typename _Value>
  inline void
  replace_copy_if(const _Sequence& seq, _OutputIterator output_iterator, _Predicate predicate, const _Value& new_value)
  {
    return std::replace_copy_if(seq.begin(), seq.end(), output_iterator, predicate, new_value);
  }

template<typename _Sequence, typename _Generator>
  inline void
  generate(_Sequence& seq, _Generator generator)
  {
    std::generate(seq.begin(), seq.end(), generator);
  }

template<typename _Sequence1, typename _OutputIterator, typename _Value>
  inline _OutputIterator
  remove_copy(const _Sequence1& seq, _OutputIterator output_iterator, const _Value& value_to_remove)
  {
    return std::remove_copy(seq.begin(), seq.end(), output_iterator, value_to_remove);
  }

template<typename _Sequence1, typename _OutputIterator, typename _Predicate>
  inline _OutputIterator
  remove_copy_if(const _Sequence1& seq, _OutputIterator output_iterator, _Predicate predicate)
  {
    return std::remove_copy_if(seq.begin(), seq.end(), output_iterator, predicate);
  }

template<typename _Sequence, typename _Value>
  inline typename _Sequence::iterator
  remove(_Sequence& seq, _Value value)
  {
    return std::remove(seq.begin(), seq.end(), value);
  }

template<typename _Sequence, typename _Predicate>
  inline typename _Sequence::iterator
  remove_if(_Sequence& seq, _Predicate predicate)
  {
    return std::remove_if(seq.begin(), seq.end(), predicate);
  }

template<typename _Sequence, typename _OutputIterator>
  inline _OutputIterator
  unique_copy(const _Sequence& seq, _OutputIterator output_iterator)
  {
    return std::unique_copy(seq.begin(), seq.end(), output_iterator);
  }

template<typename _Sequence, typename _OutputIterator, typename _BinaryPredicate>
  inline _OutputIterator
  unique_copy(const _Sequence& seq, _OutputIterator output_iterator, _BinaryPredicate binary_predicate)
  {
    return std::unique_copy(seq.begin(), seq.end(), output_iterator, binary_predicate);
  }

template<typename _Sequence>
  inline typename _Sequence::iterator
  unique(_Sequence& seq)
  {
    return std::unique(seq.begin(), seq.end());
  }

template<typename _Sequence, typename _BinaryPredicate>
  inline typename _Sequence::iterator
  unique(_Sequence& seq, _BinaryPredicate binary_predicate)
  {
    return std::unique(seq.begin(), seq.end(), binary_predicate);
  }

template<typename _Sequence>
  inline void
  reverse(_Sequence& seq)
  {
    std::reverse(seq.begin(), seq.end());
  }

template<typename _Sequence, typename _OutputIterator>
  inline void
  reverse_copy(const _Sequence& seq, _OutputIterator output_iterator)
  {
    std::reverse_copy(seq.begin(), seq.end(), output_iterator);
  }

template<typename _Sequence>
  inline void
  random_shuffle(_Sequence& seq)
  {
    std::random_shuffle(seq.beg(), seq.end());
  }

template<typename _Sequence, typename _RandomNumberGenerator>
  inline void
  random_shuffle(_Sequence& seq, _RandomNumberGenerator& random_number_generator)
  {
    std::random_shuffle(seq.beg(), seq.end(), random_number_generator);
  }

template<typename _Sequence, typename _Predicate>
  inline typename _Sequence::iterator
  partition(_Sequence& seq, _Predicate predicate)
  {
    return std::partition(seq.begin(), seq.end(), predicate);
  }

template<typename _Sequence, typename _Predicate>
  inline typename _Sequence::iterator
  stable_partition(_Sequence& seq, _Predicate predicate)
  {
    return std::stable_partition(seq.begin(), seq.end(), predicate);
  }

template<typename _Sequence>
  inline void
  sort(_Sequence &seq)
  {
    std::sort(seq.begin(), seq.end());
  }

template<typename _Sequence, typename _Compare>
  inline void
  sort(_Sequence &seq, _Compare compare)
  {
    std::sort(seq.begin(), seq.end(), compare);
  }

template<typename _Sequence1, typename _Sequence2, typename _OutputIterator>
  inline _OutputIterator
  merge(const _Sequence1 &seq1, const _Sequence2 &seq2, _OutputIterator output_iterator)
  {
    return std::merge(seq1.begin(), seq1.end(), seq2.begin(), seq2.end(), output_iterator);
  }

template<typename _Sequence1, typename _Sequence2, typename _OutputIterator, typename _Compare>
  inline _OutputIterator
  merge(_Sequence1 &seq1, _Sequence2 &seq2, _OutputIterator output_iterator, _Compare compare)
  {
    return std::merge(seq1.begin(), seq1.end(), seq2.begin(), seq2.end(), output_iterator, compare);
  }

template<typename _Sequence>
  inline void
  stable_sort(_Sequence &seq)
  {
    std::stable_sort(seq.begin(), seq.end());
  }

template<typename _Sequence, typename _Compare>
  inline void
  stable_sort(_Sequence &seq, _Compare compare)
  {
    std::stable_sort(seq.begin(), seq.end(), compare);
  }


// ----------------------------------------------------------------------------
// Set Operations
// ----------------------------------------------------------------------------

// includes
template<typename _SortedSeq1, typename _SortedSeq2>
  inline bool
  includes(const _SortedSeq1& sorted_seq1, const _SortedSeq2& sorted_seq2)
  {
    return std::includes(sorted_seq1.begin(), sorted_seq1.end(), sorted_seq2.begin(), sorted_seq2.end());
  }

template<typename _SortedSeq1, typename _SortedSeq2, typename _Compare>
  inline bool
  includes(/*const*/ _SortedSeq1& sorted_seq1, /*const*/ _SortedSeq2& sorted_seq2, _Compare compare)
  {
    return std::includes(sorted_seq1.begin(), sorted_seq1.end(), sorted_seq2.begin(), sorted_seq2.end(), compare);
  }

// set_union
//   The output range may not overlap either input range.
template<typename _SortedSeq1, typename _SortedSeq2, typename _OutputIterator>
  inline _OutputIterator
  set_union(const _SortedSeq1& sorted_seq1, const _SortedSeq2& sorted_seq2, _OutputIterator result)
  {
    std::set_union(sorted_seq1.begin(), sorted_seq1.end(), sorted_seq2.begin(), sorted_seq2.end(), result);
  }

template<typename _SortedSeq1, typename _SortedSeq2, typename _OutputIterator, typename _Compare>
  inline _OutputIterator
  set_union(/*const*/ _SortedSeq1& sorted_seq1, /*const*/ _SortedSeq2& sorted_seq2, _OutputIterator result, _Compare compare)
  {
    std::set_union(sorted_seq1.begin(), sorted_seq1.end(), sorted_seq2.begin(), sorted_seq2.end(), result, compare);
  }

// set_intersection
//   The output range may not overlap either input range.
template<typename _SortedSeq1, typename _SortedSeq2, typename _OutputIterator>
  inline _OutputIterator
  set_intersection(const _SortedSeq1& sorted_seq1, const _SortedSeq2& sorted_seq2, _OutputIterator result)
  {
    return std::set_intersection(sorted_seq1.begin(), sorted_seq1.end(), sorted_seq2.begin(), sorted_seq2.end(), result);
  }

template<typename _SortedSeq1, typename _SortedSeq2, typename _OutputIterator, typename _Compare>
  inline _OutputIterator
  set_intersection(/*const*/ _SortedSeq1& sorted_seq1, /*const*/ _SortedSeq2& sorted_seq2, _OutputIterator result, _Compare compare)
  {
    return std::set_intersection(sorted_seq1.begin(), sorted_seq1.end(), sorted_seq2.begin(), sorted_seq2.end(), result, compare);
  }

// set_difference
//   The output range may not overlap either input range.
template<typename _SortedSeq1, typename _SortedSeq2, typename _OutputIterator>
  inline _OutputIterator
  set_difference(const _SortedSeq1& sorted_seq1, const _SortedSeq2& sorted_seq2, _OutputIterator result)
  {
    return std::set_difference(sorted_seq1.begin(), sorted_seq1.end(), sorted_seq2.begin(), sorted_seq2.end(), result);
  }

template<typename _SortedSeq1, typename _SortedSeq2, typename _OutputIterator, typename _Compare>
  inline _OutputIterator
  set_difference(/*const*/ _SortedSeq1& sorted_seq1, /*const*/ _SortedSeq2& sorted_seq2, _OutputIterator result, _Compare compare)
  {
    return std::set_difference(sorted_seq1.begin(), sorted_seq1.end(), sorted_seq2.begin(), sorted_seq2.end(), result, compare);
  }

// set_symmetric_difference
//   The output range may not overlap either input range.
template<typename _SortedSeq1, typename _SortedSeq2, typename _OutputIterator>
  inline _OutputIterator
  set_symmetric_difference(const _SortedSeq1& sorted_seq1, const _SortedSeq2& sorted_seq2, _OutputIterator result)
  {
    return std::set_symmetric_difference(sorted_seq1.begin(), sorted_seq1.end(), sorted_seq2.begin(), sorted_seq2.end(), result);
  }

template<typename _SortedSeq1, typename _SortedSeq2, typename _OutputIterator, typename _Compare>
  inline _OutputIterator
  set_symmetric_difference(/*const*/ _SortedSeq1& sorted_seq1, /*const*/ _SortedSeq2& sorted_seq2, _OutputIterator result, _Compare compare)
  {
    return std::set_symmetric_difference(sorted_seq1.begin(), sorted_seq1.end(), sorted_seq2.begin(), sorted_seq2.end(), result, compare);
  }

// ----------------------------------------------------------------------------

template<typename _Sequence>
  inline typename _Sequence::iterator
  max_element(/*const*/ _Sequence& seq)
  {
    return std::max_element(seq.begin(), seq.end());
  }

template<typename _Sequence, typename _Compare>
  inline typename _Sequence::iterator
  max_element(/*const*/ _Sequence& seq, _Compare compare)
  {
    return std::max_element(seq.begin(), seq.end(), compare);
  }

template<typename _Sequence>
  inline typename _Sequence::iterator
  min_element(/*const*/ _Sequence& seq)
  {
    return std::min_element(seq.begin(), seq.end());
  }

template<typename _Sequence, typename _Compare>
  inline typename _Sequence::iterator
  min_element(/*const*/ _Sequence& seq, _Compare compare)
  {
    return std::min_element(seq.begin(), seq.end(), compare);
  }

template<typename _Sequence>
  bool
  next_permutation(_Sequence& sequence)
  {
    return std::next_permutation(sequence.begin(), sequence.end());
  }

template<typename _Sequence, typename _Compare>
  bool
  next_permutation(_Sequence& sequence, _Compare compare)
  {
    return std::next_permutation(sequence.begin(), sequence.end(), compare);
  }

template<typename _Sequence>
  bool
  prev_permutation(_Sequence& sequence)
  {
    return std::prev_permutation(sequence.begin(), sequence.end());
  }

template<typename _Sequence, typename _Compare>
  bool
  prev_permutation(_Sequence& sequence, _Compare compare)
  {
    return std::prev_permutation(sequence.begin(), sequence.end(), compare);
  }

template<typename _Sequence1, typename _Sequence2>
  inline typename _Sequence1::iterator
  find_first_of(/*const*/ _Sequence1& seq1, const _Sequence2& seq2)
  {
    return std::find_first_of(seq1.begin(), seq1.end(), seq2.begin(), seq2.end());
  }

template<typename _Sequence1, typename _Sequence2, typename _BinaryPredicate>
  inline typename _Sequence1::iterator
  find_first_of(/*const*/ _Sequence1& seq1, const _Sequence2& seq2, _BinaryPredicate binary_predicate)
  {
    return std::find_first_of(seq1.begin(), seq1.end(), seq2.begin(), seq2.end(), binary_predicate);
  }

template<typename _Sequence1, typename _Sequence2>
  inline typename _Sequence1::iterator
  find_end(/*XXX const*/ _Sequence1& seq1, const _Sequence2& seq2)
  {
    return std::find_end(seq1.begin(), seq1.end(), seq2.begin(), seq2.end());
  }

template<typename _Sequence1, typename _Sequence2, typename _BinaryPredicate>
  inline typename _Sequence1::iterator
  find_end(/*XXX const*/ _Sequence1& seq1, const _Sequence2& seq2, _BinaryPredicate binary_predicate)
  {
    return std::find_end(seq1.begin(), seq1.end(), seq2.begin(), seq2.end(), binary_predicate);
  }


// ----------------------------------------------------------------------------
// "Missing STL functions"
// ----------------------------------------------------------------------------

// transform
//   applies unary_op to each element of sequence. The output overwrites the
//   input.
template<typename _Sequence, typename _UnaryOperation>
  inline typename _Sequence::iterator
  transform(_Sequence& sequence, _UnaryOperation unary_op)
  {
    return std::transform(sequence.begin(), sequence.end(), sequence.begin(), unary_op);
  }

template<class In, class Out, class Pred>
  inline Out
  copy_if(In first, In last, Out res, Pred p)
  {
    while (first != last)
    {
      if (p(*first)) *res++ = *first;
      ++first;
    }
    return res;
  }

template<typename _Sequence, class _OutputIterator, class _Predicate>
  inline _OutputIterator
  copy_if(const _Sequence& sequence, _OutputIterator result, _Predicate predicate)
  {
    return copy_if(sequence.begin(), sequence.end(), result, predicate);
  }

#endif // _SEQUENCE_ALGORITHM_HPP