algorithm.h

/* ScummVM - Graphic Adventure Engine
 *
 * ScummVM is the legal property of its developers, whose names
 * are too numerous to list here. Please refer to the COPYRIGHT
 * file distributed with this source distribution.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 *
 */

#ifndef COMMON_ALGORITHM_H
#define COMMON_ALGORITHM_H

#include "common/scummsys.h"
#include "common/func.h"
#include "common/util.h"

namespace Common {

template<class In, class Out>
Out copy(In first, In last, Out dst) {
    while (first != last)
        *dst++ = *first++;
    return dst;
}

template<class In, class Out>
Out copy_backward(In first, In last, Out dst) {
    while (first != last)
        *--dst = *--last;
    return dst;
}

template<class In, class Out, class Op>
Out copy_if(In first, In last, Out dst, Op op) {
    while (first != last) {
        if (op(*first))
            *dst++ = *first;
        ++first;
    }
    return dst;
}

template<class In, class Out>
Out move(In first, In last, Out dst) {
    while (first != last)
        *dst++ = Common::move(*first++);
    return dst;
}

template<class In, class Out>
Out move_backward(In first, In last, Out dst) {
    while (first != last)
        *--dst = Common::move(*--last);
    return dst;
}

template<class In, class Out, class Op>
Out move_if(In first, In last, Out dst, Op op) {
    while (first != last) {
        if (op(*first))
            *dst++ = Common::move(*first);
        ++first;
    }
    return dst;
}

template<class Value>
signed char *fill(signed char *first, signed char *last, Value val) {
    memset(first, (val & 0xFF), last - first);
    return last;
}

template<class Value>
unsigned char *fill(unsigned char *first, unsigned char *last, Value val) {
    memset(first, (val & 0xFF), last - first);
    return last;
}

template<class Value>
char *fill(char *first, char *last, Value val) {
    memset(first, (val & 0xFF), last - first);
    return last;
}

template<class In, class Value>
In fill(In first, In last, const Value &val) {
    while (first != last)
        *first++ = val;
    return first;
}

template<class In, class T>
In find(In first, In last, const T &v) {
    while (first != last) {
        if (*first == v)
            return first;
        ++first;
    }
    return last;
}

template<class In, class Pred>
In find_if(In first, In last, Pred p) {
    while (first != last) {
        if (p(*first))
            return first;
        ++first;
    }
    return last;
}

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

template<typename T>
void reverse(T first, T last) {
  for (; first != last && first != --last; ++first)
    SWAP(*first, *last);
}

template<typename T>
unsigned int distance(T *first, T *last) {
    return last - first;
}

template<typename T>
unsigned int distance(T first, T last) {
    unsigned int n = 0;
    while (first != last) {
        ++n;
        ++first;
    }
    return n;
}

template<typename T>
T *sortChoosePivot(T *first, T *last) {
    return first + distance(first, last) / 2;
}

template<typename T>
T sortChoosePivot(T first, T last) {
    unsigned int n = distance(first, last);
    n /= 2;
    while (n--)
        ++first;
    return first;
}

template<typename T, class StrictWeakOrdering>
T sortPartition(T first, T last, T pivot, StrictWeakOrdering &comp) {
    --last;
    if (pivot != last)
        SWAP(*pivot, *last);

    T sorted;
    for (sorted = first; first != last; ++first) {
        if (!comp(*last, *first)) {
            if (first != sorted)
                SWAP(*first, *sorted);
            ++sorted;
        }
    }

    if (last != sorted)
        SWAP(*last, *sorted);
    return sorted;
}

template<typename T, class StrictWeakOrdering>
void sort(T first, T last, StrictWeakOrdering comp) {
    if (first == last)
        return;

    T pivot = sortChoosePivot(first, last);
    pivot = sortPartition(first, last, pivot, comp);
    sort<T, StrictWeakOrdering>(first, pivot, comp);
    sort<T, StrictWeakOrdering>(++pivot, last, comp);
}

template<typename T>
void sort(T *first, T *last) {
    sort(first, last, Less<T>());
}

template<class T>
void sort(T first, T last) {
    sort(first, last, Less<typename T::ValueType>());
}

// MSVC is complaining about the minus operator being applied to an unsigned type
// We disable this warning for the affected section of code
#if defined(_MSC_VER)
#pragma warning(push)
#pragma warning(disable: 4146)
#endif

template<class T>
T gcd(T a, T b) {
    // Note: We check for <= instead of < to avoid spurious compiler
    // warnings if T is an unsigned type, i.e. warnings like "comparison
    // of unsigned expression < 0 is always false".
    if (a <= 0)
        a = -a;
    if (b <= 0)
        b = -b;

    while (a > 0) {
        T tmp = a;
        a = b % a;
        b = tmp;
    }

    return b;
}

#if defined(_MSC_VER)
#pragma warning(pop)
#endif

template<class T>
T nextHigher2(T v) {
    if (v == 0)
        return 1;
    v--;
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    return ++v;
}

template<class It, class Dat>
void replace(It begin, It end, const Dat &original, const Dat &replaced) {
    for (; begin != end; ++begin) {
        if (*begin == original) {
            *begin = replaced;
        }
    }
}

template<class It, class T>
It remove(It first, It last, const T& val) {
    first = find(first, last, val);
    if (first != last) {
        It i = first;
        while (++i != last) {
            if (!(*i == val)) {
                *first = move(*i);
                first++;
            }
        }
    }
    return first;
}

template<typename RandomIt, typename V, typename Comp = Less<V> >
RandomIt lowerBound(RandomIt first, RandomIt last, const V &val, Comp comp = {}) {
    while (first < last) {
        const RandomIt mid = first + distance(first, last) / 2;
        if (comp(*mid, val))
            first = mid + 1;
        else
            last = mid;
    }
    return first;
}

template<typename RandomIt, typename V, typename Comp = Less<V> >
RandomIt upperBound(RandomIt first, RandomIt last, const V &val, Comp comp = {}) {
    while (first < last) {
        const RandomIt mid = first + distance(first, last) / 2;
        if (!comp(val, *mid))
            first = mid + 1;
        else
            last = mid;
    }
    return first;
}

} // End of namespace Common

#endif