#ifndef MSL_ALGORITHM_H_
#define MSL_ALGORITHM_H_

#include <iterator>
#include <cstring>
#include <functional>

namespace std {

template <class ForwardIterator, class T, typename Predicate>
inline ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& val, Predicate p) {
	typedef typename iterator_traits<ForwardIterator>::difference_type difference_type;
	difference_type len = std::distance(first, last);

	while (len > 0) {
		ForwardIterator i = first;
		difference_type step = len / 2;
		std::advance(i, step);

		if (p(*i, val)) {
			first = ++i;
			len -= step + 1;
		} else {
			len = step;
		}
	}

	return first;
}

template <class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& val) {
	// For some reason, calling the other lower_bound matches for debug, but not for retail:
	#if DEBUG
	return lower_bound(first, last, val, std::detail::less<T, T>());
	#else

	typedef typename iterator_traits<ForwardIterator>::difference_type difference_type;
	difference_type len = std::distance(first, last);

	while (len > 0) {
		ForwardIterator i = first;
		difference_type step = len / 2;
		std::advance(i, step);

		if (*i < val) {
			first = ++i;
			len -= step + 1;
		} else {
			len = step;
		}
	}

	return first;
	#endif
}

template <class ForwardIterator, class T, class Predicate>
ForwardIterator upper_bound(ForwardIterator first, ForwardIterator last, const T& val, Predicate p) {
	typedef typename iterator_traits<ForwardIterator>::difference_type difference_type;
	difference_type len = std::distance(first, last);

	while (len > 0) {
		ForwardIterator i = first;
		difference_type step = len / 2;
		std::advance(i, step);

		if (!p(val, *i)) {
			first = ++i;
			len -= step + 1;
		} else {
			len = step;
		}
	}

	return first;
}

// should be inline, but breaks JStudio/JStudio/ctb weak function order
template<class InputIt, class UnaryPredicate>
InputIt find_if(InputIt first, InputIt last, UnaryPredicate p) {
	while (first != last && !p(*first)) {
		++first;
	}
	return first;
}

// fakematch: val should be a const reference, but that breaks JMessage::TResource::toMessageIndex_messageID
template<class ForwardIterator, class T>
inline ForwardIterator find(ForwardIterator first, ForwardIterator last, T& val) {
    while (first != last && !(*first == val)) {
		++first;
	}
    return first;
}

/*
template<class OutputIt, class Size, int A2>
struct __fill_n {
    OutputIt fill_n(OutputIt first, Size count, const unsigned long& value);
};

template<>
unsigned long* __fill_n<unsigned long, long, 0>::fill_n(unsigned long* first, long count, const unsigned long& value) {
    for (; count > 0; count--) {
        *first++ = value;
    }
    return first;
}

template<class OutputIt, class Size, class T>
OutputIt fill_n(OutputIt first, Size count, const T& value) {
    return __fill_n::fill_n(first, count, value);
}


template<class ForwardIt, class T>
void __fill(ForwardIt first, ForwardIt last, const T& value, std::random_access_iterator_tag param_3) {
    fill_n(first, last - first, value);
}
*/

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

#if PLATFORM_SHIELD
template <class T, bool IsPOD = true>
struct __msl_copy {
    static T* copy(T* first, T* last, T* result) {
        for (; first < last; ++first, ++result)
            *result = *first;
        return result;
    }
};

template <class T>
struct __msl_copy<T, true> {
    static T* copy(T* first, T* last, T* result) {
        size_t n = static_cast<size_t>(last - first);
        memmove(result, first, n * sizeof(T));
        return result + n;
    }
};

template <class T>
inline T* copy(T* first, T* last, T* result) {
    return __msl_copy<T>::copy(first, last, result);
}

template <class T>
inline T* copy(const T* first, const T* last, T* result) {
    return __msl_copy<T>::copy(const_cast<T*>(first), const_cast<T*>(last), result);
}
#endif

template<class InputIt, class OutputIt>
inline OutputIt copy(InputIt first, InputIt last,
              OutputIt d_first) {
    for (; first < last; ++first, ++d_first) {
        *d_first = *first;
    }
    return d_first;
}

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

template <class T, bool A>
struct __copy_backward
{
	static T* copy_backward(T* first, T* last, T* result)
	{
		while (last > first)
			*--result = *--last;
		return result;
	}
};

template <class T>
struct __copy_backward<T, true>
{
	static T* copy_backward(T* first, T* last, T* result)
	{
#if DEBUG
		size_t n = static_cast<size_t>(last - first);
		result -= n;
		memmove(result, first, n*sizeof(T));
		return result;
#else
        while (last > first)
			*--result = *--last;
		return result;
#endif
	}
};

template <class T>
inline T* copy_backward(T* first, T* last, T* result) {
	return __copy_backward<T, true>::copy_backward(first, last, result);
}

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

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

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

    return first;
}

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

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

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 TCompare, typename TIt>
inline void __selection_sort(TIt first, TIt last, TCompare compare) {
    if (first == last) {
        return;
    }

    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)
    __attribute__((never_inline)) {
    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 {
            i1--;

            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
