ualgo.h

// This file is part of the uSTL library, an STL implementation.
//
// Copyright (c) 2005 by Mike Sharov <msharov@users.sourceforge.net>
// This file is free software, distributed under the MIT License.

#pragma once
#include "upair.h"
#include "ufunction.h"
#include "umemory.h"
#include <stdlib.h>	// for rand()

namespace ustl {

/// Swaps corresponding elements of [first, last) and [result,)
/// \ingroup SwapAlgorithms
///
template <typename ForwardIterator1, typename ForwardIterator2>
inline ForwardIterator2 swap_ranges (ForwardIterator1 first, ForwardIterator2 last, ForwardIterator2 result)
{
    for (; first != last; ++first, ++result)
	iter_swap (first, result);
    return (result);
}

/// Returns the first iterator i in the range [first, last) such that
/// *i == value. Returns last if no such iterator exists. 
/// \ingroup SearchingAlgorithms
///
template <typename InputIterator, typename EqualityComparable>
inline InputIterator find (InputIterator first, InputIterator last, const EqualityComparable& value)
{
    while (first != last && !(*first == value))
	++ first;
    return (first);
}

/// Returns the first iterator such that *i == *(i + 1)
/// \ingroup SearchingAlgorithms
///
template <typename ForwardIterator>
ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last)
{
    if (first != last)
	for (ForwardIterator prev = first; ++first != last; ++ prev)
	    if (*prev == *first)
		return (prev);
    return (last);
}

/// Returns the pointer to the first pair of unequal elements.
/// \ingroup SearchingAlgorithms
///
template <typename InputIterator>
pair<InputIterator,InputIterator>
mismatch (InputIterator first1, InputIterator last1, InputIterator first2)
{
    while (first1 != last1 && *first1 == *first2)
	++ first1, ++ first2;
    return (make_pair (first1, first2));
}

/// \brief Returns true if two ranges are equal.
/// This is an extension, present in uSTL and SGI STL.
/// \ingroup SearchingAlgorithms
///
template <typename InputIterator>
inline bool equal (InputIterator first1, InputIterator last1, InputIterator first2)
{
    return (mismatch (first1, last1, first2).first == last1);
}

/// Count finds the number of elements in [first, last) that are equal
/// to value. More precisely, the first version of count returns the
/// number of iterators i in [first, last) such that *i == value.
/// \ingroup SearchingAlgorithms
///
template <typename InputIterator, typename EqualityComparable>
inline size_t count (InputIterator first, InputIterator last, const EqualityComparable& value)
{
    size_t total = 0;
    for (; first != last; ++first)
	if (*first == value)
	    ++ total;
    return (total);
}

///
/// The first version of transform performs the operation op(*i) for each
/// iterator i in the range [first, last), and assigns the result of that
/// operation to *o, where o is the corresponding output iterator. That is,
/// for each n such that 0 <= n < last - first, it performs the assignment
/// *(result + n) = op(*(first + n)).
/// The return value is result + (last - first).
/// \ingroup MutatingAlgorithms
/// \ingroup PredicateAlgorithms
///
template <typename InputIterator, typename OutputIterator, typename UnaryFunction>
inline OutputIterator transform (InputIterator first, InputIterator last, OutputIterator result, UnaryFunction op)
{
    for (; first != last; ++result, ++first)
	*result = op (*first);
    return (result);
}

///
/// The second version of transform is very similar, except that it uses a
/// Binary Function instead of a Unary Function: it performs the operation
/// op(*i1, *i2) for each iterator i1 in the range [first1, last1) and assigns
/// the result to *o, where i2 is the corresponding iterator in the second
/// input range and where o is the corresponding output iterator. That is,
/// for each n such that 0 <= n < last1 - first1, it performs the assignment
/// *(result + n) = op(*(first1 + n), *(first2 + n).
/// The return value is result + (last1 - first1).
/// \ingroup MutatingAlgorithms
/// \ingroup PredicateAlgorithms
///
template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename BinaryFunction>
inline OutputIterator transform (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, OutputIterator result, BinaryFunction op)
{
    for (; first1 != last1; ++result, ++first1, ++first2)
	*result = op (*first1, *first2);
    return (result);
}

/// Replace replaces every element in the range [first, last) equal to
/// old_value with new_value. That is: for every iterator i,
/// if *i == old_value then it performs the assignment *i = new_value.
/// \ingroup MutatingAlgorithms
///
template <typename ForwardIterator, typename T>
inline void replace (ForwardIterator first, ForwardIterator last, const T& old_value, const T& new_value)
{
    for (; first != last; ++first)
	if (*first == old_value)
	    *first = new_value;
}

/// Replace_copy copies elements from the range [first, last) to the range
/// [result, result + (last-first)), except that any element equal to old_value
/// is not copied; new_value is copied instead. More precisely, for every
/// integer n such that 0 <= n < last-first, replace_copy performs the
/// assignment *(result+n) = new_value if *(first+n) == old_value, and
/// *(result+n) = *(first+n) otherwise.
/// \ingroup MutatingAlgorithms
///
template <typename InputIterator, typename OutputIterator, typename T>
inline OutputIterator replace_copy (InputIterator first, InputIterator last, OutputIterator result, const T& old_value, const T& new_value)
{
    for (; first != last; ++result, ++first)
        *result = (*first == old_value) ? new_value : *first;
}

/// Generate assigns the result of invoking gen, a function object that
/// takes no arguments, to each element in the range [first, last).
/// \ingroup GeneratorAlgorithms
/// \ingroup PredicateAlgorithms
///
template <typename ForwardIterator, typename Generator>
inline void generate (ForwardIterator first, ForwardIterator last, Generator gen)
{
    for (; first != last; ++first)
	*first = gen();
}

/// Generate_n assigns the result of invoking gen, a function object that
/// takes no arguments, to each element in the range [first, first+n).
/// The return value is first + n.
/// \ingroup GeneratorAlgorithms
/// \ingroup PredicateAlgorithms
///
template <typename OutputIterator, typename Generator>
inline OutputIterator generate_n (OutputIterator first, size_t n, Generator gen)
{
    for (uoff_t i = 0; i != n; ++i, ++first)
	*first = gen();
    return (first);
}

/// \brief Reverse reverses a range.
/// That is: for every i such that 0 <= i <= (last - first) / 2),
/// it exchanges *(first + i) and *(last - (i + 1)).
/// \ingroup MutatingAlgorithms
///
template <typename BidirectionalIterator>
inline void reverse (BidirectionalIterator first, BidirectionalIterator last)
{
    for (; distance (first, --last) > 0; ++first)
	iter_swap (first, last);
}

/// \brief Reverses [first,last) and writes it to \p output.
/// \ingroup MutatingAlgorithms
///
template <typename BidirectionalIterator, typename OutputIterator>
inline OutputIterator reverse_copy (BidirectionalIterator first, BidirectionalIterator last, OutputIterator result)
{
    for (; first != last; ++result)
	*result = *--last;
    return (result);
}

/// \brief Exchanges ranges [first, middle) and [middle, last)
/// \ingroup MutatingAlgorithms
///
template <typename ForwardIterator>
ForwardIterator rotate (ForwardIterator first, ForwardIterator middle, ForwardIterator last)
{
    if (first == middle || middle == last)
	return (first);
    reverse (first, middle);
    reverse (middle, last);
    for (;first != middle && middle != last; ++first)
	iter_swap (first, --last);
    reverse (first, (first == middle ? last : middle));
    return (first);
}

/// Specialization for pointers, which can be treated identically.
template <typename T>
inline T* rotate (T* first, T* middle, T* last)
{
    rotate_fast (first, middle, last);
    return (first);
}
 

/// \brief Exchanges ranges [first, middle) and [middle, last) into \p result.
/// \ingroup MutatingAlgorithms
///
template <typename ForwardIterator, typename OutputIterator>
inline OutputIterator rotate_copy (ForwardIterator first, ForwardIterator middle, ForwardIterator last, OutputIterator result)
{
    return (copy (first, middle, copy (middle, last, result)));
}

/// \brief Combines two sorted ranges.
/// \ingroup SortingAlgorithms
///
template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
OutputIterator merge (InputIterator1 first1, InputIterator1 last1,
		      InputIterator2 first2, InputIterator2 last2, OutputIterator result)
{
    for (; first1 != last1 && first2 != last2; ++result) {
	if (*first1 < *first2)
	    *result = *first1++;
	else
	    *result = *first2++;
    }
    if (first1 < last1)
	return (copy (first1, last1, result));
    else
	return (copy (first2, last2, result));
}

/// Combines two sorted ranges from the same container.
/// \ingroup SortingAlgorithms
///
template <typename InputIterator>
void inplace_merge (InputIterator first, InputIterator middle, InputIterator last)
{
    for (; middle != last; ++first) {
	while (*first < *middle)
	    ++ first;
	reverse (first, middle);
	reverse (first, ++middle);
    }
}

/// Remove_copy copies elements that are not equal to value from the range
/// [first, last) to a range beginning at result. The return value is the
/// end of the resulting range. This operation is stable, meaning that the
/// relative order of the elements that are copied is the same as in the
/// range [first, last).
/// \ingroup MutatingAlgorithms
///
template <typename InputIterator, typename OutputIterator, typename T>
OutputIterator remove_copy (InputIterator first, InputIterator last, OutputIterator result, const T& value)
{
    for (; first != last; ++first) {
	if (!(*first == value)) {
	    *result = *first;
	    ++ result;
	}
    }
    return (result);
}

/// Remove_copy copies elements pointed to by iterators in [rfirst, rlast)
/// from the range [first, last) to a range beginning at result. The return
/// value is the end of the resulting range. This operation is stable, meaning
/// that the relative order of the elements that are copied is the same as in the
/// range [first, last). Range [rfirst, rlast) is assumed to be sorted.
/// This algorithm is a uSTL extension.
/// \ingroup MutatingAlgorithms
///
template <typename InputIterator, typename OutputIterator, typename RInputIterator>
OutputIterator remove_copy (InputIterator first, InputIterator last, OutputIterator result, RInputIterator rfirst, RInputIterator rlast)
{
    for (; first != last; ++first) {
	while (rfirst != rlast && *rfirst < first)
	    ++ rfirst;
	if (rfirst == rlast || first != *rfirst) {
	    *result = *first;
	    ++ result;
	}
    }
    return (result);
}

/// Remove removes from the range [first, last) all elements that are equal to
/// value. That is, remove returns an iterator new_last such that the range
/// [first, new_last) contains no elements equal to value. [1] The iterators
/// in the range [new_last, last) are all still dereferenceable, but the
/// elements that they point to are unspecified. Remove is stable, meaning
/// that the relative order of elements that are not equal to value is
/// unchanged.
/// \ingroup MutatingAlgorithms
///
template <typename ForwardIterator, typename T>
inline ForwardIterator remove (ForwardIterator first, ForwardIterator last, const T& value)
{
    return (remove_copy (first, last, first, value));
}

/// Unique_copy copies elements from the range [first, last) to a range
/// beginning with result, except that in a consecutive group of duplicate
/// elements only the first one is copied. The return value is the end of
/// the range to which the elements are copied. This behavior is similar
/// to the Unix filter uniq.
/// \ingroup MutatingAlgorithms
///
template <typename InputIterator, typename OutputIterator>
OutputIterator unique_copy (InputIterator first, InputIterator last, OutputIterator result)
{
    if (first != last) {
	*result = *first;
	while (++first != last)
	    if (!(*first == *result))
		*++result = *first;
	++ result;
    }
    return (result);
}

/// Every time a consecutive group of duplicate elements appears in the range
/// [first, last), the algorithm unique removes all but the first element.
/// That is, unique returns an iterator new_last such that the range [first,
/// new_last) contains no two consecutive elements that are duplicates.
/// The iterators in the range [new_last, last) are all still dereferenceable,
/// but the elements that they point to are unspecified. Unique is stable,
/// meaning that the relative order of elements that are not removed is
/// unchanged.
/// \ingroup MutatingAlgorithms
///
template <typename ForwardIterator>
inline ForwardIterator unique (ForwardIterator first, ForwardIterator last)
{
    return (unique_copy (first, last, first));
}

/// Returns the furthermost iterator i in [first, last) such that,
/// for every iterator j in [first, i), *j < value
/// Assumes the range is sorted.
/// \ingroup SearchingAlgorithms
///
template <typename ForwardIterator, typename LessThanComparable>
ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const LessThanComparable& value)
{
    ForwardIterator mid;
    while (first != last) {
	mid = advance (first, size_t(distance (first,last)) / 2);
	if (*mid < value)
	    first = mid + 1;
	else
	    last = mid;
    }
    return (first);
}

/// Performs a binary search inside the sorted range.
/// \ingroup SearchingAlgorithms
///
template <typename ForwardIterator, typename LessThanComparable>
inline bool binary_search (ForwardIterator first, ForwardIterator last, const LessThanComparable& value)
{
    ForwardIterator found = lower_bound (first, last, value);
    return (found != last && !(value < *found));
}

/// Returns the furthermost iterator i in [first,last) such that for
/// every iterator j in [first,i), value < *j is false.
/// \ingroup SearchingAlgorithms
///
template <typename ForwardIterator, typename LessThanComparable>
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const LessThanComparable& value)
{
    ForwardIterator mid;
    while (first != last) {
	mid = advance (first, size_t(distance (first,last)) / 2);
	if (value < *mid)
	    last = mid;
	else
	    first = mid + 1;
    }
    return (last);
}

/// Returns pair<lower_bound,upper_bound>
/// \ingroup SearchingAlgorithms
///
template <typename ForwardIterator, typename LessThanComparable>
inline pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const LessThanComparable& value)
{
    pair<ForwardIterator,ForwardIterator> rv;
    rv.second = rv.first = lower_bound (first, last, value);
    while (rv.second != last && !(value < *(rv.second)))
	++ rv.second;
    return (rv);
}

/// Randomly permute the elements of the container.
/// \ingroup GeneratorAlgorithms
///
template <typename RandomAccessIterator>
void random_shuffle (RandomAccessIterator first, RandomAccessIterator last)
{
    for (; first != last; ++ first)
	iter_swap (first, first + (rand() % distance (first, last)));
}

/// \brief Generic compare function adaptor to pass to qsort
/// \ingroup FunctorObjects
template <typename ConstPointer, typename Compare>
int qsort_adapter (const void* p1, const void* p2)
{
    ConstPointer i1 = reinterpret_cast<ConstPointer>(p1);
    ConstPointer i2 = reinterpret_cast<ConstPointer>(p2);
    Compare comp;
    return (comp (*i1, *i2) ? -1 : (comp (*i2, *i1) ? 1 : 0));
}

/// Sorts the container
/// \ingroup SortingAlgorithms
/// \ingroup PredicateAlgorithms
///
template <typename RandomAccessIterator, typename Compare>
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare)
{
    typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
    typedef typename iterator_traits<RandomAccessIterator>::const_pointer const_pointer;
    qsort (first, distance (first, last), sizeof(value_type),
	   &qsort_adapter<const_pointer, Compare>);
}

/// Sorts the container
/// \ingroup SortingAlgorithms
///
template <typename RandomAccessIterator>
inline void sort (RandomAccessIterator first, RandomAccessIterator last)
{
    typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
    sort (first, last, less<value_type>());
}

/// Sorts the container preserving order of equal elements.
/// \ingroup SortingAlgorithms
/// \ingroup PredicateAlgorithms
///
template <typename RandomAccessIterator, typename Compare>
void stable_sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
    for (RandomAccessIterator j, i = first; ++i < last;) { // Insertion sort
	for (j = i; j-- > first && comp(*i, *j);) ;
	if (++j != i) rotate (j, i, i + 1);
    }
}

/// Sorts the container
/// \ingroup SortingAlgorithms
///
template <typename RandomAccessIterator>
inline void stable_sort (RandomAccessIterator first, RandomAccessIterator last)
{
    typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
    stable_sort (first, last, less<value_type>());
}

/// \brief Searches for the first subsequence [first2,last2) in [first1,last1)
/// \ingroup SearchingAlgorithms
template <typename ForwardIterator1, typename ForwardIterator2>
inline ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)
{
    typedef typename iterator_traits<ForwardIterator1>::value_type value_type;
    return (search (first1, last1, first2, last2, equal_to<value_type>()));
}

/// \brief Searches for the last subsequence [first2,last2) in [first1,last1)
/// \ingroup SearchingAlgorithms
template <typename ForwardIterator1, typename ForwardIterator2>
inline ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2)
{
    typedef typename iterator_traits<ForwardIterator1>::value_type value_type;
    return (find_end (first1, last1, first2, last2, equal_to<value_type>()));
}

/// \brief Searches for the first occurence of \p count \p values in [first, last)
/// \ingroup SearchingAlgorithms
template <typename Iterator, typename T>
inline Iterator search_n (Iterator first, Iterator last, size_t count, const T& value)
{
    typedef typename iterator_traits<Iterator>::value_type value_type;
    return (search_n (first, last, count, value, equal_to<value_type>()));
}

/// \brief Searches [first1,last1) for the first occurrence of an element from [first2,last2)
/// \ingroup SearchingAlgorithms
template <typename InputIterator, typename ForwardIterator>
inline InputIterator find_first_of (InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2)
{
    typedef typename iterator_traits<InputIterator>::value_type value_type;
    return (find_first_of (first1, last1, first2, last2, equal_to<value_type>()));
}

/// \brief Returns true if [first2,last2) is a subset of [first1,last1)
/// \ingroup ConditionAlgorithms
/// \ingroup SetAlgorithms
template <typename InputIterator1, typename InputIterator2>
inline bool includes (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
{
    typedef typename iterator_traits<InputIterator1>::value_type value_type;
    return (includes (first1, last1, first2, last2, less<value_type>()));
}

/// \brief Merges [first1,last1) with [first2,last2)
///
/// Result will contain every element that is in either set. If duplicate
/// elements are present, max(n,m) is placed in the result.
///
/// \ingroup SetAlgorithms
template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
inline OutputIterator set_union (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)
{
    typedef typename iterator_traits<InputIterator1>::value_type value_type;
    return (set_union (first1, last1, first2, last2, result, less<value_type>()));
}

/// \brief Creates a set containing elements shared by the given ranges.
/// \ingroup SetAlgorithms
template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
inline OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)
{
    typedef typename iterator_traits<InputIterator1>::value_type value_type;
    return (set_intersection (first1, last1, first2, last2, result, less<value_type>()));
}

/// \brief Removes from [first1,last1) elements present in [first2,last2)
/// \ingroup SetAlgorithms
template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
inline OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)
{
    typedef typename iterator_traits<InputIterator1>::value_type value_type;
    return (set_difference (first1, last1, first2, last2, result, less<value_type>()));
}

/// \brief Performs union of sets A-B and B-A.
/// \ingroup SetAlgorithms
template <typename InputIterator1, typename InputIterator2, typename OutputIterator>
inline OutputIterator set_symmetric_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result)
{
    typedef typename iterator_traits<InputIterator1>::value_type value_type;
    return (set_symmetric_difference (first1, last1, first2, last2, result, less<value_type>()));
}

/// \brief Returns true if the given range is sorted.
/// \ingroup ConditionAlgorithms
template <typename ForwardIterator>
inline bool is_sorted (ForwardIterator first, ForwardIterator last)
{
    typedef typename iterator_traits<ForwardIterator>::value_type value_type;
    return (is_sorted (first, last, less<value_type>()));
}

/// \brief Compares two given containers like strcmp compares strings.
/// \ingroup ConditionAlgorithms
template <typename InputIterator1, typename InputIterator2>
inline bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2)
{
    typedef typename iterator_traits<InputIterator1>::value_type value_type;
    return (lexicographical_compare (first1, last1, first2, last2, less<value_type>()));
}

/// \brief Creates the next lexicographical permutation of [first,last).
/// Returns false if no further permutations can be created.
/// \ingroup GeneratorAlgorithms
template <typename BidirectionalIterator>
inline bool next_permutation (BidirectionalIterator first, BidirectionalIterator last)
{
    typedef typename iterator_traits<BidirectionalIterator>::value_type value_type;
    return (next_permutation (first, last, less<value_type>()));
}

/// \brief Creates the previous lexicographical permutation of [first,last).
/// Returns false if no further permutations can be created.
/// \ingroup GeneratorAlgorithms
template <typename BidirectionalIterator>
inline bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last)
{
    typedef typename iterator_traits<BidirectionalIterator>::value_type value_type;
    return (prev_permutation (first, last, less<value_type>()));
}

/// \brief Returns iterator to the max element in [first,last)
/// \ingroup SearchingAlgorithms
template <typename ForwardIterator>
inline ForwardIterator max_element (ForwardIterator first, ForwardIterator last)
{
    typedef typename iterator_traits<ForwardIterator>::value_type value_type;
    return (max_element (first, last, less<value_type>()));
}

/// \brief Returns iterator to the min element in [first,last)
/// \ingroup SearchingAlgorithms
template <typename ForwardIterator>
inline ForwardIterator min_element (ForwardIterator first, ForwardIterator last)
{
    typedef typename iterator_traits<ForwardIterator>::value_type value_type;
    return (min_element (first, last, less<value_type>()));
}

/// \brief Makes [first,middle) a part of the sorted array.
/// Contents of [middle,last) is undefined. This implementation just calls stable_sort.
/// \ingroup SortingAlgorithms
template <typename RandomAccessIterator>
inline void partial_sort (RandomAccessIterator first, RandomAccessIterator middle, RandomAccessIterator last)
{
    typedef typename iterator_traits<RandomAccessIterator>::value_type value_type;
    partial_sort (first, middle, last, less<value_type>());
}

/// \brief Puts \p nth element into its sorted position.
/// In this implementation, the entire array is sorted. I can't think of any
/// use for it where the time gained would be useful.
/// \ingroup SortingAlgorithms
/// \ingroup SearchingAlgorithms
///
template <typename RandomAccessIterator>
inline void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last)
{
    partial_sort (first, nth, last);
}

/// \brief Like partial_sort, but outputs to [result_first,result_last)
/// \ingroup SortingAlgorithms
template <typename InputIterator, typename RandomAccessIterator>
inline RandomAccessIterator partial_sort_copy (InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last)
{
    typedef typename iterator_traits<InputIterator>::value_type value_type;
    return (partial_sort_copy (first, last, result_first, result_last, less<value_type>()));
}

} // namespace ustl