#ifndef ALGORITHM_H
#define ALGORITHM_H

#include <functional.hpp>

namespace std {

    template < typename T >
    const T& min(const T& rA, const T& rB) {
        return rB < rA ? rB : rA;
    }

    template < typename T >
    const T& max(const T& rA, const T& rB) {
        return rA < rB ? rB : rA;
    }

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

        return f;
    }

    template < class InputIterator, class Function >
    inline Function for_each_array(InputIterator* pFirst, InputIterator* pLast, Function f) {
        for (; pFirst != pLast; pFirst++) {
            f(pFirst);
        }

        return f;
    }

    template < typename TIt, typename T >
    inline TIt find(TIt first, TIt last, T& rValue) {
        TIt it = first;

        for (; first != last && !(*first == rValue); first++) {
        }

        return first;
    }

    template < typename TIt, typename T >
    inline TIt find(TIt first, TIt last, const T& rValue) {
        TIt it = first;

        for (; first != last && !(*first == rValue); first++) {
        }

        return first;
    }

    template < class InputIt, class UnaryPredicate >
    InputIt find_if(InputIt first, InputIt last, UnaryPredicate p) {
        for (; first != last && !p(*first); first++) {
        }

        return first;
    }

    template < class InputIt, class UnaryPredicate >
    InputIt* find_if_array(InputIt* pFirst, InputIt* pLast, UnaryPredicate p) {
        for (; pFirst != pLast && !p(pFirst); pFirst++) {
        }

        return pFirst;
    }

    template < class InputIt, class UnaryPredicate >
    InputIt rfind_if(InputIt first, InputIt last, UnaryPredicate p) {
        for (; first != last && !p(*first); first--) {
        }

        return first;
    }

    template < class ForwardIt, class T >
    inline void fill(ForwardIt first, ForwardIt last, const T& rValue) {
        for (; first != last; first++) {
            *first = rValue;
        }
    }

    template < class OutputIt, class Size, class T >
    inline OutputIt fill_n(OutputIt first, Size count, const T& rValue) {
        for (; count > 0; count--, first++) {
            *first = rValue;
        }

        return first;
    }

    // mostly yoinked from OGWS decomp
    template < typename TIt, typename TCompare >
    inline TIt min_element(TIt first, TIt last, TCompare compare) {
        TIt it = first;

        if (first != last) {
            for (first++; first != last; first++) {
                if (compare(*first, *it)) {
                    it = first;
                }
            }
        }

        return it;
    }

    template < typename T >
    inline T& move(T& rX) {
        return rX;
    }

    template < typename T >
    inline void swap(T& rA, T& rB) {
        T tmp = move(rA);
        rA = move(rB);
        rB = move(tmp);
    }

    template < typename TCompare, typename TIt >
    inline void __selection_sort(TIt first, TIt last, TCompare compare) {
        if (first != last) {
            TIt j = last;
            for (j--; first != j; first++) {
                TIt i = min_element< TIt, TCompare& >(first, last, compare);

                if (i != first) {
                    swap(*i, *first);
                }
            }
        }
    }

    template < typename TCompare, typename TIt >
    void __sort132(TIt a1, TIt a2, TIt a3, TCompare compare) {
        bool b1 = !compare(*a3, *a1);
        bool b2 = !compare(*a2, *a3);

        if (!b1 || !b2) {
            if (!b1 && !b2) {
                swap(*a1, *a2);
                return;
            }

            if (compare(*a2, *a1)) {
                swap(*a1, *a2);
            }

            if (b1) {
                swap(*a2, *a3);
                return;
            }

            swap(*a1, *a3);
        }
    }

    template < typename TIt, typename TCompare >
    void sort(TIt first, TIt last, TCompare compare) {
        static const int SHUFFLE_MIN = -4;
        static const int SHUFFLE_MAX = 5;
        static const int SELECTION_SORT_MIN = 20;

        while (true) {
            long len = static_cast< long >(last - first);
            if (len <= 1) {
                return;
            }

            if (len <= SELECTION_SORT_MIN) {
                __selection_sort< TCompare&, TIt >(first, last, compare);
                return;
            }

            static int shuffle = -4;
            TIt m = first + (len / static_cast< long >(sizeof(TIt)) + shuffle % SHUFFLE_MAX);

            if (++shuffle >= SHUFFLE_MAX) {
                shuffle = SHUFFLE_MIN;
            }

            TIt i1 = first + (len * static_cast< long >(sizeof(TIt) - 1) / static_cast< long >(sizeof(TIt)) + shuffle % SHUFFLE_MAX);

            if (++shuffle >= SHUFFLE_MAX) {
                shuffle = SHUFFLE_MIN;
            }

            TIt j = last - 1;
            __sort132< TCompare&, TIt >(m, i1, j, compare);

            m = first;
            i1 = j;
            while (compare(*m, *j)) {
                m++;
            }

            do {
                if (m == --i1) {
                    break;
                }
            } while (!compare(*i1, *j));

            if (m < i1) {
                swap(*m, *i1);
                m++;

                while (true) {
                    while (compare(*m, *j)) {
                        m++;
                    }

                    while (!compare(*(--i1), *j)) {
                        ;
                    }

                    if (m < i1) {
                        swap(*m, *i1);
                        m++;
                    } else {
                        break;
                    }
                }
            }

            if (m == first) {
                swap(*m, *j);
                m++;

                i1 = last;
                if (!compare(*first, *(--i1))) {
                    while (m != last && !compare(*first, *m)) {
                        m++;
                    }

                    if (m < i1) {
                        swap(*m, *i1);
                    }
                }

                if (m < i1) {
                    while (true) {
                        while (!compare(*first, *m)) {
                            m++;
                        }

                        while (compare(*first, *(--i1))) {
                            ;
                        }

                        if (m < i1) {
                            swap(*m, *i1);
                            m++;
                        } else {
                            break;
                        }
                    }
                }

                first = m;
            } else if (m - first < last - m) {
                sort< TIt, TCompare& >(first, m, compare);
                first = m;
            } else {
                sort< TIt, TCompare& >(m, last, compare);
                last = m;
            }
        }
    }

}  // namespace std

#endif  // ALGORITHM_H