#ifndef cathlibcpp_algorithm_H
#define cathlibcpp_algorithm_H

// File:       algorithm.h
// Author:     Acorn C/C++ port (c) Miles Sabin, 1996
// Purpose:    approximation to ANSI C++ standard algorithms

// Copyright (c) 1994
// Hewlett-Packard Company
//
// Permission to use, copy, modify, distribute and sell this software
// and its documentation for any purpose is hereby granted without fee,
// provided that the above copyright notice appear in all copies and
// that both that copyright notice and this permission notice appear
// in supporting documentation.  Hewlett-Packard Company makes no
// representations about the suitability of this software for any
// purpose.  It is provided "as is" without express or implied warranty.


#ifndef cathlibcpp_config_H
#include "config.h"
#endif

#ifndef cathlibcpp_bool_H
#include "bool.h"
#endif

#ifndef cathlibcpp_utility_H
#include "utility.h"              // for pair<T1, T2>
#endif


// non-modifying sequence operations

// for_each

template<class InputIterator, class Function>
inline Function for_each(InputIterator first, InputIterator last, Function f)
{
  while(first != last)
  {
    f(*first);
    ++first;
  }
  return f;
}


// find

template<class InputIterator, class T>
inline InputIterator find(InputIterator first, InputIterator last, T const& value)
{
  while(first != last && *first != value)
    ++first;
  return first;
}

template<class InputIterator, class Predicate>
inline InputIterator find_if(InputIterator first, InputIterator last, Predicate pred)
{
  while(first != last && !pred(*first))
    ++first;
  return first;
}


// find_end

template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1
  find_end
    (ForwardIterator1 first1, ForwardIterator1 last1,
     ForwardIterator2 first2, ForwardIterator2 last2);

template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
ForwardIterator1
  find_end
    (ForwardIterator1 first1, ForwardIterator1 last1,
     ForwardIterator2 first2, ForwardIterator2 last2,
     BinaryPredicate pred);


// find_first_of

template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1
  find_first_of
    (ForwardIterator1 first1, ForwardIterator1 last1,
     ForwardIterator2 first2, ForwardIterator2 last2);

template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
ForwardIterator1
  find_first_of
    (ForwardIterator1 first1, ForwardIterator1 last1,
     ForwardIterator2 first2, ForwardIterator2 last2,
     BinaryPredicate pred);


// adjacent_find

template<class ForwardIterator>
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last);

template<class ForwardIterator, class BinaryPredicate>
ForwardIterator adjacent_find(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred);


// count

template<class InputIterator, class T, class Size>
inline void count(InputIterator first, InputIterator last, T const& value, Size& n)
{
  while(first != last)
  {
    if(*first == value)
      ++n;
    ++first;
  }
}

template<class InputIterator, class Predicate, class Size>
inline void count_if(InputIterator first, InputIterator last, Predicate pred, Size& n)
{
  while(first != last)
  {
    if(pred(*first))
      ++n;
    ++first;
  }
}


// mismatch

template<class InputIterator1, class InputIterator2>
inline pair<InputIterator1, InputIterator2>
  mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
{
  while(first1 != last1 && *first1 == *first2)
  {
    ++first1;
    ++first2;
  }
  return pair<InputIterator1, InputIterator2>(first1, first2);
}

template<class InputIterator1, class InputIterator2, class BinaryPredicate>
inline pair<InputIterator1, InputIterator2>
  mismatch(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate binary_pred)
{
  while(first1 != last1 && binary_pred(*first1, *first2))
  {
    ++first1;
    ++first2;
  }
  return pair<InputIterator1, InputIterator2>(first1, first2);
}


// equal

template<class InputIterator1, class InputIterator2>
inline bool
  equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2)
{
  return mismatch(first1, last1, first2).first == last1;
}

template<class InputIterator1, class InputIterator2, class BinaryPredicate>
inline bool
  equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate binary_pred)
{
  return mismatch(first1, last1, first2, binary_pred).first == last1;
}


// search

template<class ForwardIterator1, class ForwardIterator2>
ForwardIterator1
  search
    (ForwardIterator1 first1, ForwardIterator1 last1,
     ForwardIterator2 first2, ForwardIterator2 last2);

template<class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
ForwardIterator1
  search
    (ForwardIterator1 first1, ForwardIterator1 last1,
     ForwardIterator2 first2, ForwardIterator2 last2,
     BinaryPredicate binary_pred);

template<class ForwardIterator, class Size, class T>
ForwardIterator
  search_n(ForwardIterator first, ForwardIterator last, Size count, T const& value);

template<class ForwardIterator, class Size, class T, class BinaryPredicate>
ForwardIterator
  search_n(ForwardIterator first, ForwardIterator last, Size count, T const& value, BinaryPredicate pred);


// mutating sequence operations

// copy

template<class InputIterator, class OutputIterator>
inline OutputIterator
  copy(InputIterator first, InputIterator last, OutputIterator result)
{
  while(first != last)
  {
    *result = *first;
    ++result;
    ++first;
  }
  return result;
}

template<class BidirectionalIterator1, class BidirectionalIterator2>
inline BidirectionalIterator2
  copy_backward(BidirectionalIterator1 first, BidirectionalIterator1 last, BidirectionalIterator2 result)
{
  while(first != last)
    *--result = *--last;
  return result;
}


// swap

template<class T>
inline void swap(T& a, T& b)
{
  T t = a;
  a = b;
  b = t;
}

template<class ForwardIterator1, class ForwardIterator2, class T>
inline void __iter_swap(ForwardIterator1 a, ForwardIterator2 b, T*)
{
  T tmp = *a;
  *a = *b;
  *b = tmp;
}

template<class ForwardIterator1, class ForwardIterator2>
inline void iter_swap(ForwardIterator1 a, ForwardIterator2 b)
{
  __iter_swap(a, b, value_type(a));
}

template<class ForwardIterator1, class ForwardIterator2>
inline ForwardIterator2 swap_ranges(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2)
{
  while(first1 != last1)
  {
    iter_swap(first1, first2);
    ++first1;
    ++first2;
  }
  return first2;
}


// transform

template<class InputIterator, class OutputIterator, class UnaryOperation>
inline OutputIterator
  transform
    (InputIterator first, InputIterator last, OutputIterator result,
     UnaryOperation op)
{
  while(first != last)
  {
    *result = op(*first);
    ++result;
    ++first;
  }

  return result;
}

template<class InputIterator1, class InputIterator2, class OutputIterator, class BinaryOperation>
inline OutputIterator
  transform
    (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result,
     BinaryOperation binary_op)
{
  while(first1 != last1)
  {
    *result = binary_op(*first1, *first2);
    ++result;
    ++first1;
    ++first2;
  }

  return result;
}


// replace

template<class ForwardIterator, class T>
inline void
  replace(ForwardIterator first, ForwardIterator last, T const& old_value, T const& new_value)
{
  while(first != last)
  {
    if(*first == old_value)
      *first = new_value;
    ++first;
  }
}

template<class ForwardIterator, class Predicate, class T>
inline void
  replace_if(ForwardIterator first, ForwardIterator last, Predicate pred, T const& new_value)
{
  while(first != last)
  {
    if(pred(*first))
      *first = new_value;
    ++first;
  }
}

template<class InputIterator, class OutputIterator, class T>
inline OutputIterator
  replace_copy
    (InputIterator first, InputIterator last, OutputIterator result,
     T const& old_value, T const& new_value)
{
  while(first != last)
  {
    *result = (*first == old_value ? new_value : *first);
    ++result;
    ++first;
  }
  return result;
}

template<class Iterator, class OutputIterator, class Predicate, class T>
inline OutputIterator
  replace_copy_if(Iterator first, Iterator last, OutputIterator result, Predicate pred, T const& new_value)
{
  while(first != last)
  {
    *result = (pred(*first) ? new_value : *first);
    ++result;
    ++first;
  }
  return result;
}


// fill

template<class ForwardIterator, class T>
inline void fill(ForwardIterator first, ForwardIterator last, T const& value)
{
  while(first != last)
  {
    *first = value;
    ++first;
  }
}

template<class OutputIterator, class Size, class T>
inline OutputIterator fill_n(OutputIterator first, Size n, T const& value)
{
  while(n-- > 0)
  {
    *first = value;
    ++first;
  }
  return first;
}


// generate

template<class ForwardIterator, class Generator>
inline void generate(ForwardIterator first, ForwardIterator last, Generator gen)
{
  while(first != last)
  {
    *first = gen();
    ++first;
  }
}

template<class OutputIterator, class Size, class Generator>
inline OutputIterator generate_n(OutputIterator first, Size n, Generator gen)
{
  while(n-- > 0)
  {
    *first = gen();
    ++first;
  }

  return first;
}


// remove

template<class InputIterator, class OutputIterator, class T>
inline OutputIterator
  remove_copy(InputIterator first, InputIterator last, OutputIterator result, T const& value)
{
  while(first != last)
  {
    if(*first != value)
    {
      *result = *first;
      ++result;
    }
    ++first;
  }
  return result;
}

template<class InputIterator, class OutputIterator, class Predicate>
inline OutputIterator
  remove_copy_if(InputIterator first, InputIterator last, OutputIterator result, Predicate pred)
{
  while(first != last)
  {
    if(!pred(*first))
    {
      *result = *first;
      ++result;
    }
    ++first;
  }
  return result;
}

template<class ForwardIterator, class T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last, T const& value);

template<class ForwardIterator, class Predicate>
ForwardIterator remove_if(ForwardIterator first, ForwardIterator last, Predicate pred);


// unique

template<class InputIterator, class OutputIterator>
OutputIterator
  unique_copy(InputIterator first, InputIterator last, OutputIterator result);

template<class InputIterator, class OutputIterator, class BinaryPredicate>
OutputIterator
  unique_copy(InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate binary_pred);

template<class ForwardIterator>
ForwardIterator unique(ForwardIterator first, ForwardIterator last);

template<class ForwardIterator, class BinaryPredicate>
ForwardIterator unique(ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred);


// reverse

template<class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last);

template<class BidirectionalIterator, class OutputIterator>
OutputIterator
  reverse_copy(BidirectionalIterator first, BidirectionalIterator last, OutputIterator result);


// rotate

template<class ForwardIterator>
void rotate(ForwardIterator first, ForwardIterator middle, ForwardIterator last);

template<class ForwardIterator, class OutputIterator>
OutputIterator
  rotate_copy(ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result);


// random_shuffle

template<class RandomAccessIterator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle(RandomAccessIterator first, RandomAccessIterator last, RandomNumberGenerator& rand);


// partition operations

// partition

template<class BidirectionalIterator, class Predicate>
BidirectionalIterator partition(BidirectionalIterator first, BidirectionalIterator last, Predicate pred);


// stable_partition

template<class ForwardIterator, class Predicate>
ForwardIterator stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);


// sorting and related operations

// sort

template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)


// stable_sort

template<class RandomAccessIterator>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
void stable_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp);


// partial_sort

template<class RandomAccessIterator>
void partial_sort(RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
void
  partial_sort
    (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last, Compare comp);

template<class InputIterator, class RandomAccessIterator>
RandomAccessIterator
  partial_sort_copy
    (InputIterator first, InputIterator last,
     RandomAccessIterator result_first, RandomAccessIterator result_last);

template<class InputIterator, class RandomAccessIterator, class Compare>
RandomAccessIterator
  partial_sort_copy
    (InputIterator first, InputIterator last,
     RandomAccessIterator result_first, RandomAccessIterator result_last,
     Compare comp);


// Nth element

template<class RandomAccessIterator>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
void nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp)


// binary search

// lower_bound

template<class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, T const& value);

template<class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, T const& value, Compare comp);


// upper_bound

template<class ForwardIterator, class T>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, T const& value);

template<class ForwardIterator, class T, class Compare>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, T const& value, Compare comp);


// equal_range

template<class ForwardIterator, class T>
pair<ForwardIterator, ForwardIterator>
  equal_range(ForwardIterator first, ForwardIterator last, T const& value);

template<class ForwardIterator, class T, class Compare>
pair<ForwardIterator, ForwardIterator>
  equal_range(ForwardIterator first, ForwardIterator last, T const& value, Compare comp)


// binary_search

template<class ForwardIterator, class T>
bool binary_search(ForwardIterator first, ForwardIterator last, T const& value);

template<class ForwardIterator, class T, class Compare>
bool binary_search(ForwardIterator first, ForwardIterator last, T const& value, Compare comp);


// merge

template<class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator
  merge
    (InputIterator1 first1, InputIterator1 last1,
     InputIterator2 first2, InputIterator2 last2,
     OutputIterator result);

template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator
  merge
    (InputIterator1 first1, InputIterator1 last1,
     InputIterator2 first2, InputIterator2 last2,
     OutputIterator result, Compare comp);


// inplace_merge

template<class BidirectionalIterator>
void
  inplace_merge
    (BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last);

template<class BidirectionalIterator, class Compare>
void
  inplace_merge
    (BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last, Compare comp);


// set operations on sorted structures

// includes

template<class InputIterator1, class InputIterator2>
bool
  includes
    (InputIterator1 first1, InputIterator1 last1,
     InputIterator2 first2, InputIterator2 last2);

template<class InputIterator1, class InputIterator2, class Compare>
bool
  includes
    (InputIterator1 first1, InputIterator1 last1,
     InputIterator2 first2, InputIterator2 last2,
     Compare comp);


// set_union

template<class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator
  set_union
    (InputIterator1 first1, InputIterator1 last1,
     InputIterator2 first2, InputIterator2 last2,
     OutputIterator result);

template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator
  set_union
    (InputIterator1 first1, InputIterator1 last1,
     InputIterator2 first2, InputIterator2 last2,
     OutputIterator result,
     Compare comp);


// set_intersection

template<class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator
  set_intersection
    (InputIterator1 first1, InputIterator1 last1,
     InputIterator2 first2, InputIterator2 last2,
     OutputIterator result);

template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator
  set_intersection
    (InputIterator1 first1, InputIterator1 last1,
     InputIterator2 first2, InputIterator2 last2,
     OutputIterator result,
     Compare comp);


// set_difference

template<class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator
  set_difference
    (InputIterator1 first1, InputIterator1 last1,
     InputIterator2 first2, InputIterator2 last2,
     OutputIterator result);

template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator
  set_difference
    (InputIterator1 first1, InputIterator1 last1,
     InputIterator2 first2, InputIterator2 last2,
     OutputIterator result,
     Compare comp);


// set_symmetric_difference

template<class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator
  set_symmetric_difference
    (InputIterator1 first1, InputIterator1 last1,
     InputIterator2 first2, InputIterator2 last2,
     OutputIterator result);

template<class InputIterator1, class InputIterator2, class OutputIterator, class Compare>
OutputIterator
  set_symmetric_difference
    (InputIterator1 first1, InputIterator1 last1,
     InputIterator2 first2, InputIterator2 last2,
     OutputIterator result,
     Compare comp);


// heap operations

template<class RandomAccessIterator>
void push_heap(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
void push_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)

template<class RandomAccessIterator>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
void pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

template<class RandomAccessIterator>
void make_heap(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);

template<class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last);

template<class RandomAccessIterator, class Compare>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp);


// minimum and maximum

template<class T>
inline const T min(T const& a, T const& b)
{
  return (b < a ? b : a);
}

template<class T, class Compare>
inline const T min(T const& a, T const& b, Compare comp)
{
  return (comp(b, a) ? b : a);
}

template<class T>
inline const T max(T const& a, T const& b)
{
  return (a < b ? b : a);
}

template<class T, class Compare>
inline const T max(T const& a, T const& b, Compare comp)
{
  return (comp(a, b) ? b : a);
}

template<class ForwardIterator>
ForwardIterator max_element(ForwardIterator first, ForwardIterator last);

template<class ForwardIterator, class Compare>
ForwardIterator max_element(ForwardIterator first, ForwardIterator last, Compare comp);

template<class ForwardIterator>
ForwardIterator min_element(ForwardIterator first, ForwardIterator last);

template<class ForwardIterator, class Compare>
ForwardIterator min_element(ForwardIterator first, ForwardIterator last, Compare comp);


// lexicographic comparison

template<class InputIterator1, class InputIterator2>
inline bool
  lexicographical_compare
    (InputIterator1 first1, InputIterator1 last1,
     InputIterator2 first2, InputIterator2 last2)
{
  while(first1 != last1 && first2 != last2)
  {
    if(*first1 < *first2)
      return true;
    if(*first2 < *first1)
      return false;
    ++first1;
    ++first2;
  }
  return first1 == last1 && first2 != last2;
}

template<class InputIterator1, class InputIterator2, class Compare>
inline bool
  lexicographical_compare
    (InputIterator1 first1, InputIterator1 last1,
     InputIterator2 first2, InputIterator2 last2, Compare comp)
{
  while(first1 != last1 && first2 != last2)
  {
    if(comp(*first1, *first2))
      return true;
    if(comp(*first2, *first1))
      return false;
    ++first1;
    ++first2;
  }
  return first1 == last1 && first2 != last2;
}


// permutation generators

template<class BidirectionalIterator>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last);

template<class BidirectionalIterator, class Compare>
bool next_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);

template<class BidirectionalIterator>
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last);

template<class BidirectionalIterator, class Compare>
bool prev_permutation(BidirectionalIterator first, BidirectionalIterator last, Compare comp);

#endif
