1#include <list>
2#if defined (STLPORT) && !defined (_STLP_NO_EXTENSIONS)
3#  include <slist>
4#endif
5#include <deque>
6#include <vector>
7#include <algorithm>
8#include <functional>
9#include <map>
10#include <string>
11
12#include "cppunit/cppunit_proxy.h"
13
14#if !defined (STLPORT) || defined(_STLP_USE_NAMESPACES)
15using namespace std;
16#endif
17
18//
19// TestCase class
20//
21class AlgTest : public CPPUNIT_NS::TestCase
22{
23  CPPUNIT_TEST_SUITE(AlgTest);
24  CPPUNIT_TEST(min_max);
25  CPPUNIT_TEST(count_test);
26  CPPUNIT_TEST(sort_test);
27  CPPUNIT_TEST(search_n_test);
28  CPPUNIT_TEST(find_first_of_test);
29  CPPUNIT_TEST(find_first_of_nsc_test);
30  CPPUNIT_TEST_SUITE_END();
31
32protected:
33  void min_max();
34  void count_test();
35  void sort_test();
36  void search_n_test();
37  void find_first_of_test();
38  void find_first_of_nsc_test();
39};
40
41CPPUNIT_TEST_SUITE_REGISTRATION(AlgTest);
42
43//
44// tests implementation
45//
46void AlgTest::min_max()
47{
48  int i = min(4, 7);
49  CPPUNIT_ASSERT( i == 4 );
50  char c = max('a', 'z');
51  CPPUNIT_ASSERT( c == 'z' );
52
53#if defined (STLPORT) && !defined (_STLP_NO_EXTENSIONS)
54  c = min('a', 'z', greater<char>());
55  CPPUNIT_ASSERT( c == 'z' );
56  i = max(4, 7, greater<int>());
57  CPPUNIT_ASSERT( i == 4 );
58#endif
59}
60
61void AlgTest::count_test()
62{
63  {
64    int i[] = { 1, 4, 2, 8, 2, 2 };
65    int n = count(i, i + 6, 2);
66    CPPUNIT_ASSERT(n==3);
67#if defined (STLPORT) && !defined (_STLP_NO_ANACHRONISMS)
68    n = 0;
69    count(i, i + 6, 2, n);
70    CPPUNIT_ASSERT(n==3);
71#endif
72  }
73  {
74    vector<int> i;
75    i.push_back(1);
76    i.push_back(4);
77    i.push_back(2);
78    i.push_back(8);
79    i.push_back(2);
80    i.push_back(2);
81    int n = count(i.begin(), i.end(), 2);
82    CPPUNIT_ASSERT(n==3);
83#if defined (STLPORT) && !defined (_STLP_NO_ANACHRONISMS)
84    n = 0;
85    count(i.begin(), i.end(), 2, n);
86    CPPUNIT_ASSERT(n==3);
87#endif
88  }
89}
90
91void AlgTest::sort_test()
92{
93  {
94    vector<int> years;
95    years.push_back(1962);
96    years.push_back(1992);
97    years.push_back(2001);
98    years.push_back(1999);
99    sort(years.begin(), years.end());
100    CPPUNIT_ASSERT(years[0]==1962);
101    CPPUNIT_ASSERT(years[1]==1992);
102    CPPUNIT_ASSERT(years[2]==1999);
103    CPPUNIT_ASSERT(years[3]==2001);
104  }
105  {
106    deque<int> years;
107    years.push_back(1962);
108    years.push_back(1992);
109    years.push_back(2001);
110    years.push_back(1999);
111    sort(years.begin(), years.end()); // <-- changed!
112    CPPUNIT_ASSERT(years[0]==1962);
113    CPPUNIT_ASSERT(years[1]==1992);
114    CPPUNIT_ASSERT(years[2]==1999);
115    CPPUNIT_ASSERT(years[3]==2001);
116  }
117}
118
119#define ARRAY_SIZE(arr) sizeof(arr) / sizeof(arr[0])
120
121void AlgTest::search_n_test()
122{
123  int ints[] = {0, 1, 2, 3, 3, 4, 4, 4, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5};
124
125#if defined (STLPORT) && !defined (_STLP_NO_EXTENSIONS)
126  //search_n
127  //Forward iterator
128  {
129    slist<int> slint(ints, ints + ARRAY_SIZE(ints));
130    slist<int>::iterator slit = search_n(slint.begin(), slint.end(), 2, 2);
131    CPPUNIT_ASSERT( slit != slint.end() );
132    CPPUNIT_ASSERT( *(slit++) == 2 );
133    CPPUNIT_ASSERT( *slit == 2 );
134  }
135#endif
136
137  //Bidirectionnal iterator
138  {
139    list<int> lint(ints, ints + ARRAY_SIZE(ints));
140    list<int>::iterator lit = search_n(lint.begin(), lint.end(), 3, 3);
141    CPPUNIT_ASSERT( lit != lint.end() );
142    CPPUNIT_ASSERT( *(lit++) == 3 );
143    CPPUNIT_ASSERT( *(lit++) == 3 );
144    CPPUNIT_ASSERT( *lit == 3 );
145  }
146
147  //Random access iterator
148  {
149    deque<int> dint(ints, ints + ARRAY_SIZE(ints));
150    deque<int>::iterator dit = search_n(dint.begin(), dint.end(), 4, 4);
151    CPPUNIT_ASSERT( dit != dint.end() );
152    CPPUNIT_ASSERT( *(dit++) == 4 );
153    CPPUNIT_ASSERT( *(dit++) == 4 );
154    CPPUNIT_ASSERT( *(dit++) == 4 );
155    CPPUNIT_ASSERT( *dit == 4 );
156  }
157
158#if defined (STLPORT) && !defined (_STLP_NO_EXTENSIONS)
159  //search_n with predicate
160  //Forward iterator
161  {
162    slist<int> slint(ints, ints + ARRAY_SIZE(ints));
163    slist<int>::iterator slit = search_n(slint.begin(), slint.end(), 2, 1, greater<int>());
164    CPPUNIT_ASSERT( slit != slint.end() );
165    CPPUNIT_ASSERT( *(slit++) > 1 );
166    CPPUNIT_ASSERT( *slit > 2 );
167  }
168#endif
169
170  //Bidirectionnal iterator
171  {
172    list<int> lint(ints, ints + ARRAY_SIZE(ints));
173    list<int>::iterator lit = search_n(lint.begin(), lint.end(), 3, 2, greater<int>());
174    CPPUNIT_ASSERT( lit != lint.end() );
175    CPPUNIT_ASSERT( *(lit++) > 2 );
176    CPPUNIT_ASSERT( *(lit++) > 2 );
177    CPPUNIT_ASSERT( *lit > 2 );
178  }
179
180  //Random access iterator
181  {
182    deque<int> dint(ints, ints + ARRAY_SIZE(ints));
183    deque<int>::iterator dit = search_n(dint.begin(), dint.end(), 4, 3, greater<int>());
184    CPPUNIT_ASSERT( dit != dint.end() );
185    CPPUNIT_ASSERT( *(dit++) > 3 );
186    CPPUNIT_ASSERT( *(dit++) > 3 );
187    CPPUNIT_ASSERT( *(dit++) > 3 );
188    CPPUNIT_ASSERT( *dit > 3 );
189  }
190
191  // test for bug reported by Jim Xochellis
192  {
193    int array[] = {0, 0, 1, 0, 1, 1};
194    int* array_end = array + sizeof(array) / sizeof(*array);
195    CPPUNIT_ASSERT(search_n(array, array_end, 3, 1) == array_end);
196  }
197
198  // test for bug with counter == 1, reported by Timmie Smith
199  {
200    int array[] = {0, 1, 2, 3, 4, 5};
201    int* array_end = array + sizeof(array) / sizeof(*array);
202    CPPUNIT_ASSERT( search_n(array, array_end, 1, 1, equal_to<int>() ) == &array[1] );
203  }
204}
205
206struct MyIntComparable {
207  MyIntComparable(int val) : _val(val) {}
208  bool operator == (const MyIntComparable& other) const
209  { return _val == other._val; }
210
211private:
212  int _val;
213};
214
215void AlgTest::find_first_of_test()
216{
217#if defined (STLPORT) && !defined (_STLP_NO_EXTENSIONS)
218  slist<int> intsl;
219  intsl.push_front(1);
220  intsl.push_front(2);
221
222  {
223    vector<int> intv;
224    intv.push_back(0);
225    intv.push_back(1);
226    intv.push_back(2);
227    intv.push_back(3);
228
229    vector<int>::iterator first;
230    first = find_first_of(intv.begin(), intv.end(), intsl.begin(), intsl.end());
231    CPPUNIT_ASSERT( first != intv.end() );
232    CPPUNIT_ASSERT( *first == 1 );
233  }
234  {
235    vector<int> intv;
236    intv.push_back(3);
237    intv.push_back(2);
238    intv.push_back(1);
239    intv.push_back(0);
240
241    vector<int>::iterator first;
242    first = find_first_of(intv.begin(), intv.end(), intsl.begin(), intsl.end());
243    CPPUNIT_ASSERT( first != intv.end() );
244    CPPUNIT_ASSERT( *first == 2 );
245  }
246#endif
247
248  list<int> intl;
249  intl.push_front(1);
250  intl.push_front(2);
251
252  {
253    vector<int> intv;
254    intv.push_back(0);
255    intv.push_back(1);
256    intv.push_back(2);
257    intv.push_back(3);
258
259    vector<int>::iterator first;
260    first = find_first_of(intv.begin(), intv.end(), intl.begin(), intl.end());
261    CPPUNIT_ASSERT( first != intv.end() );
262    CPPUNIT_ASSERT( *first == 1 );
263  }
264  {
265    vector<int> intv;
266    intv.push_back(3);
267    intv.push_back(2);
268    intv.push_back(1);
269    intv.push_back(0);
270
271    vector<int>::iterator first;
272    first = find_first_of(intv.begin(), intv.end(), intl.begin(), intl.end());
273    CPPUNIT_ASSERT( first != intv.end() );
274    CPPUNIT_ASSERT( *first == 2 );
275  }
276  {
277    char chars[] = {1, 2};
278
279    vector<int> intv;
280    intv.push_back(0);
281    intv.push_back(1);
282    intv.push_back(2);
283    intv.push_back(3);
284
285    vector<int>::iterator first;
286    first = find_first_of(intv.begin(), intv.end(), chars, chars + sizeof(chars));
287    CPPUNIT_ASSERT( first != intv.end() );
288    CPPUNIT_ASSERT( *first == 1 );
289  }
290  {
291    unsigned char chars[] = {1, 2, 255};
292
293    vector<int> intv;
294    intv.push_back(-10);
295    intv.push_back(1029);
296    intv.push_back(255);
297    intv.push_back(4);
298
299    vector<int>::iterator first;
300    first = find_first_of(intv.begin(), intv.end(), chars, chars + sizeof(chars));
301    CPPUNIT_ASSERT( first != intv.end() );
302    CPPUNIT_ASSERT( *first == 255 );
303  }
304  {
305    signed char chars[] = {93, 2, -101, 13};
306
307    vector<int> intv;
308    intv.push_back(-10);
309    intv.push_back(1029);
310    intv.push_back(-2035);
311    intv.push_back(-101);
312    intv.push_back(4);
313
314    vector<int>::iterator first;
315    first = find_first_of(intv.begin(), intv.end(), chars, chars + sizeof(chars));
316    CPPUNIT_ASSERT( first != intv.end() );
317    CPPUNIT_ASSERT( *first == -101 );
318  }
319  {
320    char chars[] = {1, 2};
321
322    vector<MyIntComparable> intv;
323    intv.push_back(0);
324    intv.push_back(1);
325    intv.push_back(2);
326    intv.push_back(3);
327
328    vector<MyIntComparable>::iterator first;
329    first = find_first_of(intv.begin(), intv.end(), chars, chars + sizeof(chars));
330    CPPUNIT_ASSERT( first != intv.end() );
331    CPPUNIT_ASSERT( *first == 1 );
332  }
333}
334
335typedef pair<int, string> Pair;
336
337struct ValueFinder :
338    public binary_function<const Pair&, const string&, bool>
339{
340    bool operator () ( const Pair &p, const string& value ) const
341      { return p.second == value; }
342};
343
344void AlgTest::find_first_of_nsc_test()
345{
346  // Non-symmetrical comparator
347
348  map<int, string> m;
349  vector<string> values;
350
351  m[1] = "one";
352  m[4] = "four";
353  m[10] = "ten";
354  m[20] = "twenty";
355
356  values.push_back( "four" );
357  values.push_back( "ten" );
358
359  map<int, string>::iterator i = find_first_of(m.begin(), m.end(), values.begin(), values.end(), ValueFinder());
360
361  CPPUNIT_ASSERT( i != m.end() );
362  CPPUNIT_ASSERT( i->first == 4 || i->first == 10 );
363  CPPUNIT_ASSERT( i->second == "four" || i->second == "ten" );
364}
365