/* -*- c++ -*- */
/*
* Copyright (C) 2009 The Android Open Source Project
* All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* * Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* * Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in
* the documentation and/or other materials provided with the
* distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
* FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
* COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
* BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
* OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
* AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
* SUCH DAMAGE.
*/
#ifndef ANDROID_ASTL_ALGORITHM__
#define ANDROID_ASTL_ALGORITHM__
#include <cstddef>
#include <cstring>
#include <iterator>
#include <type_traits.h>
#ifndef ANDROID_ASTL_TYPE_TRAITS_H__
#error "Wrong file included!"
#endif
namespace std {
// This file contains the following template functions:
// - min
// - max
// - swap
// - fill
// - fill_n
// - copy
// - equal
template<typename _T> inline const _T& min(const _T& left, const _T& right)
{
if (left < right) return left;
return right;
}
template<typename _T> inline const _T& max(const _T& left, const _T& right)
{
if (right < left) return left;
return right;
}
template<typename _T> inline void swap(_T& left, _T& right)
{
_T tmp = left;
left = right;
right = tmp;
}
// Basic iterators, loop over the elements, we don't know how many
// elements we need to copy. See the random access specialization
// below.
template<typename _Category>
struct copy_move {
template<typename _InputIterator, typename _OutputIterator>
static _OutputIterator
__copy_move(_InputIterator first, _InputIterator last, _OutputIterator res) {
for (; first != last; ++res, ++first) {
*res = *first;
}
return res;
}
};
// For random access iterators, we know how many elements we have to
// copy (random iterators support operator-).
template<>
struct copy_move<random_access_iterator_tag> {
template<typename _InputIterator, typename _OutputIterator>
static _OutputIterator
__copy_move(_InputIterator first, _InputIterator last, _OutputIterator res) {
typedef typename iterator_traits<_InputIterator>::difference_type
difference_type;
for (difference_type n = last - first; n > 0; --n) {
*res = *first;
++first;
++res;
}
return res;
}
};
// TODO: for simple case and wrapper iterator, should degrade to memmove.
// copy elements in the range [first, last) into the range [result,
// result + (last - first)) starting from first and proceeding to
// last.
//
// For each non negative n < (last - first) performs:
// *(result + n) = *(first + n)
// @require result should not be in the [first, last) range.
// @return result + (last - first)
template<typename _InputIterator, typename _OutputIterator>
inline _OutputIterator
copy(_InputIterator first, _InputIterator last, _OutputIterator res) {
typedef typename iterator_traits<_InputIterator>::iterator_category
_Category;
return copy_move<_Category>::__copy_move(
android::iter<_InputIterator>::base(first),
android::iter<_InputIterator>::base(last),
res);
}
// fill the range [begin, end) with copies of value, return nothing.
// fill_n the range [begin, begin + n) with copies of value, return
// the pointer at begin + n.
//
// TODO: fill and fill_n should take forward and output iterators for
// begin and end params. Fix this when iterator are defined.
template<bool> struct __fill
{
template<typename _T> static void fill(_T *begin, const _T *end,
const _T& value)
{
for (; begin < end; ++begin)
*begin = value;
}
};
template<> struct __fill<true> // scalar version
{
template<typename _T> static void fill(_T *begin, const _T *end,
const _T& value)
{
const _T tmp = value;
for (; begin < end; ++begin)
*begin = tmp;
}
};
template<typename _T> void fill(_T *begin, _T *end, const _T& value)
{
const bool is_scalar = std::is_scalar<_T>::value;
__fill<is_scalar>::fill(begin, end, value);
}
// Specialization: for one-byte types use memset.
inline void fill(unsigned char *begin, unsigned char *end,
const unsigned char& value)
{
if (begin < end)
{
const int tmp = value;
std::memset(begin, tmp, end - begin);
}
}
inline void fill(signed char *begin, signed char *end, const signed char& value)
{
if (begin < end)
{
const int tmp = value;
std::memset(begin, tmp, end - begin);
}
}
inline void fill(char *begin, char *end, const char& value)
{
if (begin < end)
{
const int tmp = value;
std::memset(begin, tmp, end - begin);
}
}
template<bool> struct __fill_n
{
template<typename _T> static _T *fill_n(_T *begin, size_t num,
const _T& value)
{
for (size_t i = 0; i < num; ++i, ++begin)
{
*begin = value;
}
return begin;
}
};
template<> struct __fill_n<true> // scalar version
{
template<typename _T> static _T *fill_n(_T *begin, size_t num,
const _T& value)
{
const _T tmp = value;
for (size_t i = 0; i < num; ++i, ++begin)
{
*begin = tmp;
}
return begin;
}
};
template<typename _T> _T *fill_n(_T *begin, size_t n, const _T& value)
{
const bool is_scalar = std::is_scalar<_T>::value;
return __fill_n<is_scalar>::fill_n(begin, n, value);
}
// Specialization: for one-byte types uses memset.
inline unsigned char *fill_n(unsigned char *begin, size_t num,
const unsigned char& value)
{
const int tmp = value;
std::memset(begin, tmp, num);
return begin + num;
}
inline signed char *fill_n(signed char *begin, size_t num,
const signed char& value)
{
const int tmp = value;
std::memset(begin, tmp, num);
return begin + num;
}
inline char *fill_n(char *begin, size_t num, const char& value)
{
const int tmp = value;
std::memset(begin, tmp, num);
return begin + num;
}
// Test a range for element-wise equality using operator==
// @param begin1 An input iterator.
// @param end1 An input iterator.
// @param begin2 An input iterator.
// @return true if all the elements of the range are equal.
// TODO: When we have a proper structure for iterator as opposed to
// just pointers, we should be able to the get the type for the values
// referenced by the iterator and default to memcmp for simple types.
// TODO: equal should degrade to memcmp for pod.
template<typename _InputIterator1, typename _InputIterator2>
inline bool equal(_InputIterator1 begin1, _InputIterator1 end1,
_InputIterator2 begin2)
{
for (; begin1 < end1; ++begin1, ++begin2)
{
if (!(*begin1 == *begin2))
{
return false;
}
}
return true;
}
// Test a range for element-wise equality using operator==
// @param begin1 An input iterator.
// @param end1 An input iterator.
// @param begin2 An input iterator.
// @param binary_pred A binary predicate function.
// @return true if all the elements of the range are equal.
template<typename _InputIterator1, typename _InputIterator2, typename _BinaryPredicated>
inline bool equal(_InputIterator1 begin1, _InputIterator1 end1,
_InputIterator2 begin2, _BinaryPredicated binary_predicate)
{
for (; begin1 < end1; ++begin1, ++begin2)
{
if (!bool(binary_predicate(*begin1, *begin2)))
{
return false;
}
}
return true;
}
} // namespace std
#endif