Subversion Repositories openrisc

// This file is part of the uSTL library, an STL implementation.

//

// Copyright (c) 2005-2009 by Mike Sharov <msharov@users.sourceforge.net>

// This file is free software, distributed under the MIT License.

#ifndef UPREDALGO_H_2CB058AE0807A01A2F6A51BA5D5820A5

#define UPREDALGO_H_2CB058AE0807A01A2F6A51BA5D5820A5

namespace ustl {

/// Copy_if copies elements from the range [first, last) to the range

/// [result, result + (last - first)) if pred(*i) returns true.

/// \ingroup MutatingAlgorithms

/// \ingroup PredicateAlgorithms

///

template <typename InputIterator, typename OutputIterator, typename Predicate>

inline OutputIterator copy_if (InputIterator first, InputIterator last, OutputIterator result, Predicate pred)

{

    for (; first != last; ++first) {

        if (pred(*first)) {

            *result = *first;

            ++ result;

        }

    }

    return (result);

}

/// Returns the first iterator i in the range [first, last) such that

/// pred(*i) is true. Returns last if no such iterator exists.

/// \ingroup SearchingAlgorithms

/// \ingroup PredicateAlgorithms

///

template <typename InputIterator, typename Predicate>

inline InputIterator find_if (InputIterator first, InputIterator last, Predicate pred)

{

    while (first != last && !pred (*first))

        ++ first;

    return (first);

}

/// Returns the first iterator such that p(*i, *(i + 1)) == true.

/// \ingroup SearchingAlgorithms

/// \ingroup PredicateAlgorithms

///

template <typename ForwardIterator, typename BinaryPredicate>

inline ForwardIterator adjacent_find (ForwardIterator first, ForwardIterator last, BinaryPredicate p)

{

    if (first != last)

        for (ForwardIterator prev = first; ++first != last; ++ prev)

            if (p (*prev, *first))

                return (prev);

    return (last);

}

/// Returns the pointer to the first pair of unequal elements.

/// \ingroup SearchingAlgorithms

/// \ingroup PredicateAlgorithms

///

template <typename InputIterator, typename BinaryPredicate>

inline pair<InputIterator,InputIterator>

mismatch (InputIterator first1, InputIterator last1, InputIterator first2, BinaryPredicate comp)

{

    while (first1 != last1 && comp(*first1, *first2))

        ++ first1, ++ first2;

    return (make_pair (first1, first2));

}

/// Returns true if two ranges are equal.

/// This is an extension, present in uSTL and SGI STL.

/// \ingroup ConditionAlgorithms

/// \ingroup PredicateAlgorithms

///

template <typename InputIterator, typename BinaryPredicate>

inline bool equal (InputIterator first1, InputIterator last1, InputIterator first2, BinaryPredicate comp)

{

    return (mismatch (first1, last1, first2, comp).first == last1);

}

/// Count_if finds the number of elements in [first, last) that satisfy the

/// predicate pred. More precisely, the first version of count_if returns the

/// number of iterators i in [first, last) such that pred(*i) is true.

/// \ingroup ConditionAlgorithms

/// \ingroup PredicateAlgorithms

///

template <typename InputIterator, typename Predicate>

inline size_t count_if (InputIterator first, InputIterator last, Predicate pred)

{

    size_t total = 0;

    for (; first != last; ++first)

        if (pred (*first))

            ++ total;

    return (total);

}

/// Replace_if replaces every element in the range [first, last) for which

/// pred returns true with new_value. That is: for every iterator i, if

/// pred(*i) is true then it performs the assignment *i = new_value.

/// \ingroup MutatingAlgorithms

/// \ingroup PredicateAlgorithms

///

template <typename ForwardIterator, typename Predicate, typename T>

inline void replace_if (ForwardIterator first, ForwardIterator last, Predicate pred, const T& new_value)

{

    for (; first != last; ++first)

        if (pred (*first))

            *first = new_value;

}

/// Replace_copy_if copies elements from the range [first, last) to the range

/// [result, result + (last-first)), except that any element for which pred is

/// true is not copied; new_value is copied instead. More precisely, for every

/// integer n such that 0 <= n < last-first, replace_copy_if performs the

/// assignment *(result+n) = new_value if pred(*(first+n)),

/// and *(result+n) = *(first+n) otherwise.

/// \ingroup MutatingAlgorithms

/// \ingroup PredicateAlgorithms

///

template <typename InputIterator, typename OutputIterator, typename Predicate, typename T>

inline OutputIterator replace_copy_if (InputIterator first, InputIterator last, OutputIterator result, Predicate pred, const T& new_value)

{

    for (; first != last; ++result, ++first)

        *result = pred(*first) ? new_value : *first;

}

/// Remove_copy_if copies elements from the range [first, last) to a range

/// beginning at result, except that elements for which pred is true are not

/// copied. 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

/// \ingroup PredicateAlgorithms

///

template <typename InputIterator, typename OutputIterator, typename Predicate>

inline OutputIterator remove_copy_if (InputIterator first, InputIterator last, OutputIterator result, Predicate pred)

{

    for (; first != last; ++first)

        if (pred (*first))

            *result++ = *first;

    return (result);

}

/// Remove_if removes from the range [first, last) every element x such that

/// pred(x) is true. That is, remove_if returns an iterator new_last such that

/// the range [first, new_last) contains no elements for which pred is true.

/// The iterators in the range [new_last, last) are all still dereferenceable,

/// but the elements that they point to are unspecified. Remove_if is stable,

/// meaning that the relative order of elements that are not removed is

/// unchanged.

/// \ingroup MutatingAlgorithms

/// \ingroup PredicateAlgorithms

///

template <typename ForwardIterator, typename Predicate>

inline ForwardIterator remove_if (ForwardIterator first, ForwardIterator last, Predicate pred)

{

    return (remove_copy_if (first, last, first, pred));

}

/// The reason there are two different versions of unique_copy is that there

/// are two different definitions of what it means for a consecutive group of

/// elements to be duplicates. In the first version, the test is simple

/// equality: the elements in a range [f, l) are duplicates if, for every

/// iterator i in the range, either i == f or else *i == *(i-1). In the second,

/// the test is an arbitrary Binary Predicate binary_pred: the elements in

/// [f, l) are duplicates if, for every iterator i in the range, either

/// i == f or else binary_pred(*i, *(i-1)) is true.

/// \ingroup MutatingAlgorithms

/// \ingroup PredicateAlgorithms

///

template <typename InputIterator, typename OutputIterator, typename BinaryPredicate>

OutputIterator unique_copy (InputIterator first, InputIterator last, OutputIterator result, BinaryPredicate binary_pred)

{

    if (first != last) {

        *result = *first;

        while (++first != last)

            if (!binary_pred (*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

/// \ingroup PredicateAlgorithms

///

template <typename ForwardIterator, typename BinaryPredicate>

inline ForwardIterator unique (ForwardIterator first, ForwardIterator last, BinaryPredicate binary_pred)

{

    return (unique_copy (first, last, first, binary_pred));

}

/// Returns the furthermost iterator i in [first, last) such that,

/// for every iterator j in [first, i), comp(*j, value) is true.

/// Assumes the range is sorted.

/// \ingroup SearchingAlgorithms

/// \ingroup PredicateAlgorithms

///

template <typename ForwardIterator, typename T, typename StrictWeakOrdering>

ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp)

{

    ForwardIterator mid;

    while (first != last) {

        mid = advance (first, distance (first,last) / 2);

        if (comp (*mid, value))

            first = mid + 1;

        else

            last = mid;

    }

    return (first);

}

/// Performs a binary search inside the sorted range.

/// \ingroup SearchingAlgorithms

/// \ingroup PredicateAlgorithms

///

template <typename ForwardIterator, typename T, typename StrictWeakOrdering>

inline bool binary_search (ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp)

{

    ForwardIterator found = lower_bound (first, last, value, comp);

    return (found != last && !comp(*found, value));

}

/// Returns the furthermost iterator i in [first,last) such that for

/// every iterator j in [first,i), comp(value,*j) is false.

/// \ingroup SearchingAlgorithms

/// \ingroup PredicateAlgorithms

///

template <typename ForwardIterator, typename T, typename StrictWeakOrdering>

ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp)

{

    ForwardIterator mid;

    while (first != last) {

        mid = advance (first, distance (first,last) / 2);

        if (comp (value, *mid))

            last = mid;

        else

            first = mid + 1;

    }

    return (last);

}

/// Returns pair<lower_bound,upper_bound>

/// \ingroup SearchingAlgorithms

/// \ingroup PredicateAlgorithms

///

template <typename ForwardIterator, typename T, typename StrictWeakOrdering>

inline pair<ForwardIterator,ForwardIterator> equal_range (ForwardIterator first, ForwardIterator last, const T& value, StrictWeakOrdering comp)

{

    pair<ForwardIterator,ForwardIterator> rv;

    rv.second = rv.first = lower_bound (first, last, value, comp);

    while (rv.second != last && !comp(value, *(rv.second)))

        ++ rv.second;

    return (rv);

}

/// \brief Puts \p nth element into its sorted position.

/// In this implementation, the entire array is sorted. The performance difference is

/// so small and the function use is so rare, there is no need to have code for it.

/// \ingroup SortingAlgorithms

/// \ingroup SearchingAlgorithms

/// \ingroup PredicateAlgorithms

///

template <typename RandomAccessIterator, typename Compare>

inline void nth_element (RandomAccessIterator first, RandomAccessIterator, RandomAccessIterator last, Compare comp)

{

    sort (first, last, comp);

}

/// \brief Searches for the first subsequence [first2,last2) in [first1,last1)

/// \ingroup SearchingAlgorithms

/// \ingroup PredicateAlgorithms

template <typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>

ForwardIterator1 search (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate comp)

{

    const ForwardIterator1 slast = last1 - distance(first2, last2) + 1;

    for (; first1 < slast; ++first1) {

        ForwardIterator2 i = first2;

        ForwardIterator1 j = first1;

        for (; i != last2 && comp(*j, *i); ++i, ++j) ;

        if (i == last2)

            return (first1);

    }

    return (last1);

}

/// \brief Searches for the last subsequence [first2,last2) in [first1,last1)

/// \ingroup SearchingAlgorithms

/// \ingroup PredicateAlgorithms

template <typename ForwardIterator1, typename ForwardIterator2, typename BinaryPredicate>

ForwardIterator1 find_end (ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2, ForwardIterator2 last2, BinaryPredicate comp)

{

    ForwardIterator1 s = last1 - distance(first2, last2);

    for (; first1 < s; --s) {

        ForwardIterator2 i = first2, j = s;

        for (; i != last2 && comp(*j, *i); ++i, ++j) ;

        if (i == last2)

            return (s);

    }

    return (last1);

}

/// \brief Searches for the first occurence of \p count \p values in [first, last)

/// \ingroup SearchingAlgorithms

/// \ingroup PredicateAlgorithms

template <typename Iterator, typename T, typename BinaryPredicate>

Iterator search_n (Iterator first, Iterator last, size_t count, const T& value, BinaryPredicate comp)

{

    size_t n = 0;

    for (; first != last; ++first) {

        if (!comp (*first, value))

            n = 0;

        else if (++n == count)

            return (first - --n);

    }

    return (last);

}

/// \brief Searches [first1,last1) for the first occurrence of an element from [first2,last2)

/// \ingroup SearchingAlgorithms

/// \ingroup PredicateAlgorithms

template <typename InputIterator, typename ForwardIterator, typename BinaryPredicate>

InputIterator find_first_of (InputIterator first1, InputIterator last1, ForwardIterator first2, ForwardIterator last2, BinaryPredicate comp)

{

    for (; first1 != last1; ++first1)

        for (ForwardIterator i = first2; i != last2; ++i)

            if (comp (*first1, *i))

                return (first1);

    return (first1);

}

/// \brief Returns true if [first2,last2) is a subset of [first1,last1)

/// \ingroup ConditionAlgorithms

/// \ingroup SetAlgorithms

/// \ingroup PredicateAlgorithms

template <typename InputIterator1, typename InputIterator2, typename StrictWeakOrdering>

bool includes (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, StrictWeakOrdering comp)

{

    for (; (first1 != last1) & (first2 != last2); ++first1) {

        if (comp (*first2, *first1))

            return (false);

        first2 += !comp (*first1, *first2);

    }

    return (first2 == last2);

}

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

/// \ingroup PredicateAlgorithms

template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename StrictWeakOrdering>

OutputIterator set_union (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp)

{

    for (; (first1 != last1) & (first2 != last2); ++result) {

        if (comp (*first2, *first1))

            *result = *first2++;

        else {

            first2 += !comp (*first1, *first2);

            *result = *first1++;

        }

    }

    return (copy (first2, last2, copy (first1, last1, result)));

}

/// \brief Creates a set containing elements shared by the given ranges.

/// \ingroup SetAlgorithms

/// \ingroup PredicateAlgorithms

template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename StrictWeakOrdering>

OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp)

{

    while ((first1 != last1) & (first2 != last2)) {

        bool b1ge2 = !comp (*first1, *first2), b2ge1 = !comp (*first2, *first1);

        if (b1ge2 & b2ge1)

            *result++ = *first1;

        first1 += b2ge1;

        first2 += b1ge2;

    }

    return (result);

}

/// \brief Removes from [first1,last1) elements present in [first2,last2)

/// \ingroup SetAlgorithms

/// \ingroup PredicateAlgorithms

template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename StrictWeakOrdering>

OutputIterator set_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp)

{

    while ((first1 != last1) & (first2 != last2)) {

        bool b1ge2 = !comp (*first1, *first2), b2ge1 = !comp (*first2, *first1);

        if (!b1ge2)

            *result++ = *first1;

        first1 += b2ge1;

        first2 += b1ge2;

    }

    return (copy (first1, last1, result));

}

/// \brief Performs union of sets A-B and B-A.

/// \ingroup SetAlgorithms

/// \ingroup PredicateAlgorithms

template <typename InputIterator1, typename InputIterator2, typename OutputIterator, typename StrictWeakOrdering>

OutputIterator set_symmetric_difference (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, StrictWeakOrdering comp)

{

    while ((first1 != last1) & (first2 != last2)) {

        bool b1l2 = comp (*first1, *first2), b2l1 = comp (*first2, *first1);

        if (b1l2)

            *result++ = *first1;

        else if (b2l1)

            *result++ = *first2;

        first1 += !b2l1;

        first2 += !b1l2;

    }

    return (copy (first2, last2, copy (first1, last1, result)));

}

/// \brief Returns true if the given range is sorted.

/// \ingroup ConditionAlgorithms

/// \ingroup PredicateAlgorithms

template <typename ForwardIterator, typename StrictWeakOrdering>

bool is_sorted (ForwardIterator first, ForwardIterator last, StrictWeakOrdering comp)

{

    for (ForwardIterator i = first; ++i < last; ++first)

        if (comp (*i, *first))

            return (false);

    return (true);

}

/// \brief Compares two given containers like strcmp compares strings.

/// \ingroup ConditionAlgorithms

/// \ingroup PredicateAlgorithms

template <typename InputIterator1, typename InputIterator2, typename BinaryPredicate>

bool lexicographical_compare (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, BinaryPredicate comp)

{

    for (; (first1 != last1) & (first2 != last2); ++first1, ++first2) {

        if (comp (*first1, *first2))

            return (true);

        if (comp (*first2, *first1))

            return (false);

    }

    return ((first1 == last1) & (first2 != last2));

}

/// \brief Creates the next lexicographical permutation of [first,last).

/// Returns false if no further permutations can be created.

/// \ingroup GeneratorAlgorithms

/// \ingroup PredicateAlgorithms

template <typename BidirectionalIterator, typename StrictWeakOrdering>

bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, StrictWeakOrdering comp)

{

    if (distance (first, last) < 2)

        return (false);

    BidirectionalIterator i = last;

    for (--i; i != first; ) {

        --i;

        if (comp (i[0], i[1])) {

            BidirectionalIterator j = last;

            while (!comp (*i, *--j)) ;

            iter_swap (i, j);

            reverse (i + 1, last);

            return (true);

        }

    }

    reverse (first, last);

    return (false);

}

/// \brief Creates the previous lexicographical permutation of [first,last).

/// Returns false if no further permutations can be created.

/// \ingroup GeneratorAlgorithms

/// \ingroup PredicateAlgorithms

template <typename BidirectionalIterator, typename StrictWeakOrdering>

bool prev_permutation (BidirectionalIterator first, BidirectionalIterator last, StrictWeakOrdering comp)

{

    if (distance (first, last) < 2)

        return (false);

    BidirectionalIterator i = last;

    for (--i; i != first; ) {

        --i;

        if (comp(i[1], i[0])) {

            BidirectionalIterator j = last;

            while (!comp (*--j, *i)) ;

            iter_swap (i, j);

            reverse (i + 1, last);

            return (true);

        }

    }

    reverse (first, last);

    return (false);

}

/// \brief Returns iterator to the max element in [first,last)

/// \ingroup SearchingAlgorithms

/// \ingroup PredicateAlgorithms

template <typename ForwardIterator, typename BinaryPredicate>

inline ForwardIterator max_element (ForwardIterator first, ForwardIterator last, BinaryPredicate comp)

{

    ForwardIterator result = first;

    for (; first != last; ++first)

        if (comp (*result, *first))

            result = first;

    return (result);

}

/// \brief Returns iterator to the min element in [first,last)

/// \ingroup SearchingAlgorithms

/// \ingroup PredicateAlgorithms

template <typename ForwardIterator, typename BinaryPredicate>

inline ForwardIterator min_element (ForwardIterator first, ForwardIterator last, BinaryPredicate comp)

{

    ForwardIterator result = first;

    for (; first != last; ++first)

        if (comp (*first, *result))

            result = first;

    return (result);

}

/// \brief Makes [first,middle) a part of the sorted array.

/// Contents of [middle,last) is undefined. This implementation just calls stable_sort.

/// \ingroup SortingAlgorithms

/// \ingroup PredicateAlgorithms

template <typename RandomAccessIterator, typename StrictWeakOrdering>

inline void partial_sort (RandomAccessIterator first, RandomAccessIterator, RandomAccessIterator last, StrictWeakOrdering comp)

{

    stable_sort (first, last, comp);

}

/// \brief Like partial_sort, but outputs to [result_first,result_last)

/// \ingroup SortingAlgorithms

/// \ingroup PredicateAlgorithms

template <typename InputIterator, typename RandomAccessIterator, typename StrictWeakOrdering>

RandomAccessIterator partial_sort_copy (InputIterator first, InputIterator last, RandomAccessIterator result_first, RandomAccessIterator result_last, StrictWeakOrdering comp)

{

    RandomAccessIterator rend = result_first;

    for (; first != last; ++first) {

        RandomAccessIterator i = result_first;

        for (; i != rend && comp (*i, *first); ++i) ;

        if (i == result_last)

            continue;

        rend += (rend < result_last);

        copy_backward (i, rend - 1, rend);

        *i = *first;

    }

    return (rend);

}

/// \brief Like partition, but preserves equal element order.

/// \ingroup SortingAlgorithms

/// \ingroup PredicateAlgorithms

template <typename ForwardIterator, typename Predicate>

ForwardIterator stable_partition (ForwardIterator first, ForwardIterator last, Predicate pred)

{

    if (first == last)

        return (first);

    ForwardIterator l, r, m = advance (first, distance (first, last) / 2);

    if (first == m)

        return (pred(*first) ? last : first);

    l = stable_partition (first, m, pred);

    r = stable_partition (m, last, pred);

    rotate (l, m, r);

    return (advance (l, distance (m, r)));

}

/// \brief Splits [first,last) in two by \p pred.

///

/// Creates two ranges [first,middle) and [middle,last), where every element

/// in the former is less than every element in the latter.

/// The return value is middle.

///

/// \ingroup SortingAlgorithms

/// \ingroup PredicateAlgorithms

template <typename ForwardIterator, typename Predicate>

inline ForwardIterator partition (ForwardIterator first, ForwardIterator last, Predicate pred)

{

    return (stable_partition (first, last, pred));

}

} // namespace ustl

#endif