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)
15 using namespace std;
16 #endif
17
18 //
19 // TestCase class
20 //
21 class 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
32 protected:
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
41 CPPUNIT_TEST_SUITE_REGISTRATION(AlgTest);
42
43 //
44 // tests implementation
45 //
min_max()46 void 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
count_test()61 void 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
sort_test()91 void 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
search_n_test()121 void 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
206 struct MyIntComparable {
MyIntComparableMyIntComparable207 MyIntComparable(int val) : _val(val) {}
operator ==MyIntComparable208 bool operator == (const MyIntComparable& other) const
209 { return _val == other._val; }
210
211 private:
212 int _val;
213 };
214
find_first_of_test()215 void 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
335 typedef pair<int, string> Pair;
336
337 struct ValueFinder :
338 public binary_function<const Pair&, const string&, bool>
339 {
operator ()ValueFinder340 bool operator () ( const Pair &p, const string& value ) const
341 { return p.second == value; }
342 };
343
find_first_of_nsc_test()344 void 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