/* -*- 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 <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
// - 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;
}
// 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