algorithm revision 8b5f35d0aa39e39119dc1e3e2fc4d283995faa2a 
1/* -*- c++ -*- */
2/*
3 * Copyright (C) 2009 The Android Open Source Project
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *  * Redistributions of source code must retain the above copyright
10 *    notice, this list of conditions and the following disclaimer.
11 *  * Redistributions in binary form must reproduce the above copyright
12 *    notice, this list of conditions and the following disclaimer in
13 *    the documentation and/or other materials provided with the
14 *    distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
19 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
20 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
22 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
23 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
24 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
25 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
26 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * SUCH DAMAGE.
28 */
29
30#ifndef ANDROID_ASTL_ALGORITHM__
31#define ANDROID_ASTL_ALGORITHM__
32
33#include <cstddef>
34#include <cstring>
35#include <type_traits.h>
36#ifndef ANDROID_ASTL_TYPE_TRAITS_H__
37#error "Wrong file included!"
38#endif
39
40namespace std {
41
42// This file contains the following template functions:
43// - min
44// - max
45// - swap
46// - fill
47// - fill_n
48// - equal
49
50template<typename _T> inline const _T& min(const _T& left, const _T& right)
51{
52    if (left < right) return left;
53    return right;
54}
55
56template<typename _T> inline const _T& max(const _T& left, const _T& right)
57{
58    if (right < left) return left;
59    return right;
60}
61
62template<typename _T> inline void swap(_T& left, _T& right)
63{
64    _T tmp = left;
65    left = right;
66    right = tmp;
67}
68
69// fill the range [begin, end) with copies of value, return nothing.
70// fill_n the range [begin, begin + n) with copies of value, return
71// the pointer at begin + n.
72//
73// TODO: fill and fill_n should take forward and output iterators for
74// begin and end params. Fix this when iterator are defined.
75
76
77template<bool> struct __fill
78{
79    template<typename _T> static void fill(_T *begin, const _T *end,
80                                           const _T& value)
81    {
82        for (; begin < end; ++begin)
83            *begin = value;
84    }
85};
86
87template<> struct __fill<true>  // scalar version
88{
89    template<typename _T> static void fill(_T *begin, const _T *end,
90                                           const _T& value)
91    {
92        const _T tmp = value;
93
94        for (; begin < end; ++begin)
95            *begin = tmp;
96    }
97};
98
99template<typename _T> void fill(_T *begin, _T *end, const _T& value)
100{
101    const bool is_scalar = std::is_scalar<_T>::value;
102    __fill<is_scalar>::fill(begin, end, value);
103}
104
105// Specialization: for one-byte types use memset.
106inline void fill(unsigned char *begin, unsigned char *end,
107                 const unsigned char& value)
108{
109    if (begin < end)
110    {
111        const int tmp = value;
112        std::memset(begin, tmp, end - begin);
113    }
114}
115
116inline void fill(signed char *begin, signed char *end, const signed char& value)
117{
118    if (begin < end)
119    {
120        const int tmp = value;
121        std::memset(begin, tmp, end - begin);
122    }
123}
124
125inline void fill(char *begin, char *end, const char& value)
126{
127    if (begin < end)
128    {
129        const int tmp = value;
130        std::memset(begin, tmp, end - begin);
131    }
132}
133
134template<bool> struct __fill_n
135{
136    template<typename _T> static _T *fill_n(_T *begin, size_t num,
137                                            const _T& value)
138    {
139        for (size_t i = 0; i < num; ++i, ++begin)
140        {
141            *begin = value;
142        }
143        return begin;
144    }
145};
146
147template<> struct __fill_n<true>  // scalar version
148{
149    template<typename _T> static _T *fill_n(_T *begin, size_t num,
150                                            const _T& value)
151    {
152        const _T tmp = value;
153
154        for (size_t i = 0; i < num; ++i, ++begin)
155        {
156            *begin = tmp;
157        }
158        return begin;
159    }
160};
161
162template<typename _T> _T *fill_n(_T *begin, size_t n, const _T& value)
163{
164    const bool is_scalar = std::is_scalar<_T>::value;
165    return __fill_n<is_scalar>::fill_n(begin, n, value);
166}
167
168
169// Specialization: for one-byte types uses memset.
170inline unsigned char *fill_n(unsigned char *begin, size_t num,
171                             const unsigned char& value)
172{
173    const int tmp = value;
174    std::memset(begin, tmp, num);
175    return begin + num;
176}
177
178inline signed char *fill_n(signed char *begin, size_t num,
179                           const signed char& value)
180{
181    const int tmp = value;
182    std::memset(begin, tmp, num);
183    return begin + num;
184}
185
186inline char *fill_n(char *begin, size_t num, const char& value)
187{
188    const int tmp = value;
189    std::memset(begin, tmp, num);
190    return begin + num;
191}
192
193
194// Test a range for element-wise equality using operator==
195// @param begin1  An input iterator.
196// @param end1    An input iterator.
197// @param begin2  An input iterator.
198// @return true if all the elements of the range are equal.
199// TODO: When we have a proper structure for iterator as opposed to
200// just pointers, we should be able to the get the type for the values
201// referenced by the iterator and default to memcmp for simple types.
202template<typename _InputIterator1, typename _InputIterator2>
203inline bool equal(_InputIterator1 begin1, _InputIterator1 end1,
204                  _InputIterator2 begin2)
205{
206    for (; begin1 < end1; ++begin1, ++begin2)
207    {
208        if (!(*begin1 == *begin2))
209        {
210            return false;
211        }
212    }
213    return true;
214}
215
216// Test a range for element-wise equality using operator==
217// @param  begin1  An input iterator.
218// @param  end1    An input iterator.
219// @param  begin2  An input iterator.
220// @param  binary_pred A binary predicate function.
221// @return  true if all the elements of the range are equal.
222template<typename _InputIterator1, typename _InputIterator2, typename _BinaryPredicated>
223inline bool equal(_InputIterator1 begin1, _InputIterator1 end1,
224                  _InputIterator2 begin2, _BinaryPredicated binary_predicate)
225{
226    for (; begin1 < end1; ++begin1, ++begin2)
227    {
228        if (!bool(binary_predicate(*begin1, *begin2)))
229        {
230            return false;
231        }
232    }
233    return true;
234}
235
236}  // namespace std
237
238
239#endif
240