1 //Has to be first for StackAllocator swap overload to be taken
2 //into account (at least using GCC 4.0.1)
3 #include "stack_allocator.h"
4 
5 #include <set>
6 #include <algorithm>
7 
8 #include "cppunit/cppunit_proxy.h"
9 
10 #if !defined (STLPORT) || defined(_STLP_USE_NAMESPACES)
11 using namespace std;
12 #endif
13 
14 //
15 // TestCase class
16 //
17 class SetTest : public CPPUNIT_NS::TestCase
18 {
19   CPPUNIT_TEST_SUITE(SetTest);
20   CPPUNIT_TEST(set1);
21   CPPUNIT_TEST(set2);
22   CPPUNIT_TEST(erase);
23   CPPUNIT_TEST(insert);
24   CPPUNIT_TEST(find);
25   CPPUNIT_TEST(bounds);
26   CPPUNIT_TEST(specialized_less);
27   CPPUNIT_TEST(implementation_check);
28   CPPUNIT_TEST(allocator_with_state);
29   CPPUNIT_TEST(reverse_iterator_test);
30 #if !defined (STLPORT) || !defined (_STLP_USE_CONTAINERS_EXTENSION)
31   CPPUNIT_IGNORE;
32 #endif
33   CPPUNIT_TEST(template_methods);
34   CPPUNIT_TEST_SUITE_END();
35 
36 protected:
37   void set1();
38   void set2();
39   void erase();
40   void insert();
41   void find();
42   void bounds();
43   void specialized_less();
44   void implementation_check();
45   void allocator_with_state();
46   void reverse_iterator_test();
47   void template_methods();
48 };
49 
50 CPPUNIT_TEST_SUITE_REGISTRATION(SetTest);
51 
52 
53 //
54 // tests implementation
55 //
set1()56 void SetTest::set1()
57 {
58   set<int, less<int> > s;
59   CPPUNIT_ASSERT (s.count(42) == 0);
60   s.insert(42);
61   CPPUNIT_ASSERT (s.count(42) == 1);
62   s.insert(42);
63   CPPUNIT_ASSERT (s.count(42) == 1);
64   size_t count = s.erase(42);
65   CPPUNIT_ASSERT (count == 1);
66 }
67 
set2()68 void SetTest::set2()
69 {
70   typedef set<int, less<int> > int_set;
71   int_set s;
72   pair<int_set::iterator, bool> p = s.insert(42);
73   CPPUNIT_ASSERT (p.second == true);
74   p = s.insert(42);
75   CPPUNIT_ASSERT (p.second == false);
76 
77   int array1 [] = { 1, 3, 6, 7 };
78   s.insert(array1, array1 + 4);
79   CPPUNIT_ASSERT (distance(s.begin(), s.end()) == 5);
80 
81   int_set s2;
82   s2.swap(s);
83   CPPUNIT_ASSERT (distance(s2.begin(), s2.end()) == 5);
84   CPPUNIT_ASSERT (distance(s.begin(), s.end()) == 0);
85 
86   int_set s3;
87   s3.swap(s);
88   s3.swap(s2);
89   CPPUNIT_ASSERT (distance(s.begin(), s.end()) == 0);
90   CPPUNIT_ASSERT (distance(s2.begin(), s2.end()) == 0);
91   CPPUNIT_ASSERT (distance(s3.begin(), s3.end()) == 5);
92 }
93 
erase()94 void SetTest::erase()
95 {
96   set<int, less<int> > s;
97   s.insert(1);
98   s.erase(s.begin());
99   CPPUNIT_ASSERT( s.empty() );
100 
101   size_t nb = s.erase(1);
102   CPPUNIT_ASSERT(nb == 0);
103 }
104 
insert()105 void SetTest::insert()
106 {
107   set<int> s;
108   set<int>::iterator i = s.insert( s.end(), 0 );
109   CPPUNIT_ASSERT( *i == 0 );
110 }
111 
find()112 void SetTest::find()
113 {
114   set<int> s;
115 
116   CPPUNIT_ASSERT( s.find(0) == s.end() );
117 
118   set<int> const& crs = s;
119 
120   CPPUNIT_ASSERT( crs.find(0) == crs.end() );
121 }
122 
bounds()123 void SetTest::bounds()
124 {
125   int array1 [] = { 1, 3, 6, 7 };
126   set<int> s(array1, array1 + sizeof(array1) / sizeof(array1[0]));
127   set<int> const& crs = s;
128 
129   set<int>::iterator sit;
130   set<int>::const_iterator scit;
131   pair<set<int>::iterator, set<int>::iterator> pit;
132   pair<set<int>::const_iterator, set<int>::const_iterator> pcit;
133 
134   //Check iterator on mutable set
135   sit = s.lower_bound(2);
136   CPPUNIT_ASSERT( sit != s.end() );
137   CPPUNIT_ASSERT( *sit == 3 );
138 
139   sit = s.upper_bound(5);
140   CPPUNIT_ASSERT( sit != s.end() );
141   CPPUNIT_ASSERT( *sit == 6 );
142 
143   pit = s.equal_range(6);
144   CPPUNIT_ASSERT( pit.first != pit.second );
145   CPPUNIT_ASSERT( pit.first != s.end() );
146   CPPUNIT_ASSERT( *pit.first == 6 );
147   CPPUNIT_ASSERT( pit.second != s.end() );
148   CPPUNIT_ASSERT( *pit.second == 7 );
149 
150   pit = s.equal_range(4);
151   CPPUNIT_ASSERT( pit.first == pit.second );
152   CPPUNIT_ASSERT( pit.first != s.end() );
153   CPPUNIT_ASSERT( *pit.first == 6 );
154   CPPUNIT_ASSERT( pit.second != s.end() );
155   CPPUNIT_ASSERT( *pit.second == 6 );
156 
157   //Check const_iterator on mutable set
158   scit = s.lower_bound(2);
159   CPPUNIT_ASSERT( scit != s.end() );
160   CPPUNIT_ASSERT( *scit == 3 );
161 
162   scit = s.upper_bound(5);
163   CPPUNIT_ASSERT( scit != s.end() );
164   CPPUNIT_ASSERT( *scit == 6 );
165 
166 #ifdef _STLP_MEMBER_TEMPLATES
167   pcit = s.equal_range(6);
168   CPPUNIT_ASSERT( pcit.first != pcit.second );
169   CPPUNIT_ASSERT( pcit.first != s.end() );
170   CPPUNIT_ASSERT( *pcit.first == 6 );
171   CPPUNIT_ASSERT( pcit.second != s.end() );
172   CPPUNIT_ASSERT( *pcit.second == 7 );
173 #endif
174 
175   //Check const_iterator on const set
176   scit = crs.lower_bound(2);
177   CPPUNIT_ASSERT( scit != crs.end() );
178   CPPUNIT_ASSERT( *scit == 3 );
179 
180   scit = crs.upper_bound(5);
181   CPPUNIT_ASSERT( scit != crs.end() );
182   CPPUNIT_ASSERT( *scit == 6 );
183 
184   pcit = crs.equal_range(6);
185   CPPUNIT_ASSERT( pcit.first != pcit.second );
186   CPPUNIT_ASSERT( pcit.first != crs.end() );
187   CPPUNIT_ASSERT( *pcit.first == 6 );
188   CPPUNIT_ASSERT( pcit.second != crs.end() );
189   CPPUNIT_ASSERT( *pcit.second == 7 );
190 }
191 
192 
193 class SetTestClass {
194 public:
SetTestClass(int data)195   SetTestClass (int data) : _data(data)
196   {}
197 
data() const198   int data() const {
199     return _data;
200   }
201 
202 private:
203   int _data;
204 };
205 
206 #if !defined (STLPORT) || defined (_STLP_USE_NAMESPACES)
207 namespace std {
208 #endif
209 #if defined (STLPORT)
210   _STLP_TEMPLATE_NULL
211 #else
212   template <>
213 #endif
214   struct less<SetTestClass> {
operator ()std::less215     bool operator () (SetTestClass const& lhs, SetTestClass const& rhs) const {
216       return lhs.data() < rhs.data();
217     }
218   };
219 #if !defined (STLPORT) || defined (_STLP_USE_NAMESPACES)
220 }
221 #endif
222 
specialized_less()223 void SetTest::specialized_less()
224 {
225   set<SetTestClass> s;
226   s.insert(SetTestClass(1));
227   s.insert(SetTestClass(3));
228   s.insert(SetTestClass(2));
229   s.insert(SetTestClass(0));
230 
231   set<SetTestClass>::iterator sit(s.begin()), sitEnd(s.end());
232   int i = 0;
233   for (; sit != sitEnd; ++sit, ++i) {
234     CPPUNIT_ASSERT( sit->data() == i );
235   }
236 }
237 
implementation_check()238 void SetTest::implementation_check()
239 {
240   set<int> tree;
241   tree.insert(1);
242   set<int>::iterator it = tree.begin();
243   int const& int_ref = *it++;
244   CPPUNIT_ASSERT( int_ref == 1 );
245 
246   CPPUNIT_ASSERT( it == tree.end() );
247   CPPUNIT_ASSERT( it != tree.begin() );
248 
249   set<int>::const_iterator cit = tree.begin();
250   int const& int_cref = *cit++;
251   CPPUNIT_ASSERT( int_cref == 1 );
252 }
253 
reverse_iterator_test()254 void SetTest::reverse_iterator_test()
255 {
256   set<int> tree;
257   tree.insert(1);
258   tree.insert(2);
259 
260   {
261     set<int>::reverse_iterator rit(tree.rbegin());
262     CPPUNIT_ASSERT( *(rit++) == 2 );
263     CPPUNIT_ASSERT( *(rit++) == 1 );
264     CPPUNIT_ASSERT( rit == tree.rend() );
265   }
266 
267   {
268     set<int> const& ctree = tree;
269     set<int>::const_reverse_iterator rit(ctree.rbegin());
270     CPPUNIT_ASSERT( *(rit++) == 2 );
271     CPPUNIT_ASSERT( *(rit++) == 1 );
272     CPPUNIT_ASSERT( rit == ctree.rend() );
273   }
274 }
275 
allocator_with_state()276 void SetTest::allocator_with_state()
277 {
278   char buf1[1024];
279   StackAllocator<int> stack1(buf1, buf1 + sizeof(buf1));
280 
281   char buf2[1024];
282   StackAllocator<int> stack2(buf2, buf2 + sizeof(buf2));
283 
284   int i;
285   typedef set<int, less<int>, StackAllocator<int> > SetInt;
286   less<int> intLess;
287 
288   {
289     SetInt sint1(intLess, stack1);
290     for (i = 0; i < 5; ++i)
291       sint1.insert(i);
292     SetInt sint1Cpy(sint1);
293 
294     SetInt sint2(intLess, stack2);
295     for (; i < 10; ++i)
296       sint2.insert(i);
297     SetInt sint2Cpy(sint2);
298 
299     sint1.swap(sint2);
300 
301     CPPUNIT_ASSERT( sint1.get_allocator().swaped() );
302     CPPUNIT_ASSERT( sint2.get_allocator().swaped() );
303 
304     CPPUNIT_ASSERT( sint1 == sint2Cpy );
305     CPPUNIT_ASSERT( sint2 == sint1Cpy );
306     CPPUNIT_ASSERT( sint1.get_allocator() == stack2 );
307     CPPUNIT_ASSERT( sint2.get_allocator() == stack1 );
308   }
309   CPPUNIT_ASSERT( stack1.ok() );
310   CPPUNIT_ASSERT( stack2.ok() );
311   stack1.reset(); stack2.reset();
312 
313   {
314     SetInt sint1(intLess, stack1);
315     SetInt sint1Cpy(sint1);
316 
317     SetInt sint2(intLess, stack2);
318     for (i = 0; i < 10; ++i)
319       sint2.insert(i);
320     SetInt sint2Cpy(sint2);
321 
322     sint1.swap(sint2);
323 
324     CPPUNIT_ASSERT( sint1.get_allocator().swaped() );
325     CPPUNIT_ASSERT( sint2.get_allocator().swaped() );
326 
327     CPPUNIT_ASSERT( sint1 == sint2Cpy );
328     CPPUNIT_ASSERT( sint2 == sint1Cpy );
329     CPPUNIT_ASSERT( sint1.get_allocator() == stack2 );
330     CPPUNIT_ASSERT( sint2.get_allocator() == stack1 );
331   }
332   CPPUNIT_ASSERT( stack1.ok() );
333   CPPUNIT_ASSERT( stack2.ok() );
334   stack1.reset(); stack2.reset();
335 
336   {
337     SetInt sint1(intLess, stack1);
338     for (i = 0; i < 10; ++i)
339       sint1.insert(i);
340     SetInt sint1Cpy(sint1);
341 
342     SetInt sint2(intLess, stack2);
343     SetInt sint2Cpy(sint2);
344 
345     sint1.swap(sint2);
346 
347     CPPUNIT_ASSERT( sint1.get_allocator().swaped() );
348     CPPUNIT_ASSERT( sint2.get_allocator().swaped() );
349 
350     CPPUNIT_ASSERT( sint1 == sint2Cpy );
351     CPPUNIT_ASSERT( sint2 == sint1Cpy );
352     CPPUNIT_ASSERT( sint1.get_allocator() == stack2 );
353     CPPUNIT_ASSERT( sint2.get_allocator() == stack1 );
354   }
355   CPPUNIT_ASSERT( stack1.ok() );
356   CPPUNIT_ASSERT( stack2.ok() );
357   stack1.reset(); stack2.reset();
358 }
359 
360 struct Key
361 {
KeyKey362   Key() : m_data(0) {}
KeyKey363   explicit Key(int data) : m_data(data) {}
364 
365   int m_data;
366 };
367 
368 struct KeyCmp
369 {
operator ()KeyCmp370   bool operator () (Key lhs, Key rhs) const
371   { return lhs.m_data < rhs.m_data; }
372 
operator ()KeyCmp373   bool operator () (Key lhs, int rhs) const
374   { return lhs.m_data < rhs; }
375 
operator ()KeyCmp376   bool operator () (int lhs, Key rhs) const
377   { return lhs < rhs.m_data; }
378 };
379 
380 struct KeyCmpPtr
381 {
operator ()KeyCmpPtr382   bool operator () (Key const volatile *lhs, Key const volatile *rhs) const
383   { return (*lhs).m_data < (*rhs).m_data; }
384 
operator ()KeyCmpPtr385   bool operator () (Key const volatile *lhs, int rhs) const
386   { return (*lhs).m_data < rhs; }
387 
operator ()KeyCmpPtr388   bool operator () (int lhs, Key const volatile *rhs) const
389   { return lhs < (*rhs).m_data; }
390 };
391 
template_methods()392 void SetTest::template_methods()
393 {
394 #if defined (STLPORT) && defined (_STLP_USE_CONTAINERS_EXTENSION)
395   {
396     typedef set<Key, KeyCmp> KeySet;
397     KeySet keySet;
398     keySet.insert(Key(1));
399     keySet.insert(Key(2));
400     keySet.insert(Key(3));
401     keySet.insert(Key(4));
402 
403     CPPUNIT_ASSERT( keySet.count(Key(1)) == 1 );
404     CPPUNIT_ASSERT( keySet.count(1) == 1 );
405     CPPUNIT_ASSERT( keySet.count(5) == 0 );
406 
407     CPPUNIT_ASSERT( keySet.find(2) != keySet.end() );
408     CPPUNIT_ASSERT( keySet.lower_bound(2) != keySet.end() );
409     CPPUNIT_ASSERT( keySet.upper_bound(2) != keySet.end() );
410     CPPUNIT_ASSERT( keySet.equal_range(2) != make_pair(keySet.begin(), keySet.end()) );
411 
412     KeySet const& ckeySet = keySet;
413     CPPUNIT_ASSERT( ckeySet.find(2) != ckeySet.end() );
414     CPPUNIT_ASSERT( ckeySet.lower_bound(2) != ckeySet.end() );
415     CPPUNIT_ASSERT( ckeySet.upper_bound(2) != ckeySet.end() );
416     CPPUNIT_ASSERT( ckeySet.equal_range(2) != make_pair(ckeySet.begin(), ckeySet.end()) );
417   }
418 
419   {
420     typedef set<Key*, KeyCmpPtr> KeySet;
421     KeySet keySet;
422     Key key1(1), key2(2), key3(3), key4(4);
423     keySet.insert(&key1);
424     keySet.insert(&key2);
425     keySet.insert(&key3);
426     keySet.insert(&key4);
427 
428     CPPUNIT_ASSERT( keySet.count(1) == 1 );
429     CPPUNIT_ASSERT( keySet.count(5) == 0 );
430 
431     CPPUNIT_ASSERT( keySet.find(2) != keySet.end() );
432     CPPUNIT_ASSERT( keySet.lower_bound(2) != keySet.end() );
433     CPPUNIT_ASSERT( keySet.upper_bound(2) != keySet.end() );
434     CPPUNIT_ASSERT( keySet.equal_range(2) != make_pair(keySet.begin(), keySet.end()) );
435 
436     KeySet const& ckeySet = keySet;
437     CPPUNIT_ASSERT( ckeySet.find(2) != ckeySet.end() );
438     CPPUNIT_ASSERT( ckeySet.lower_bound(2) != ckeySet.end() );
439     CPPUNIT_ASSERT( ckeySet.upper_bound(2) != ckeySet.end() );
440     CPPUNIT_ASSERT( ckeySet.equal_range(2) != make_pair(ckeySet.begin(), ckeySet.end()) );
441   }
442   {
443     typedef multiset<Key, KeyCmp> KeySet;
444     KeySet keySet;
445     keySet.insert(Key(1));
446     keySet.insert(Key(2));
447     keySet.insert(Key(3));
448     keySet.insert(Key(4));
449 
450     CPPUNIT_ASSERT( keySet.count(Key(1)) == 1 );
451     CPPUNIT_ASSERT( keySet.count(1) == 1 );
452     CPPUNIT_ASSERT( keySet.count(5) == 0 );
453 
454     CPPUNIT_ASSERT( keySet.find(2) != keySet.end() );
455     CPPUNIT_ASSERT( keySet.lower_bound(2) != keySet.end() );
456     CPPUNIT_ASSERT( keySet.upper_bound(2) != keySet.end() );
457     CPPUNIT_ASSERT( keySet.equal_range(2) != make_pair(keySet.begin(), keySet.end()) );
458 
459     KeySet const& ckeySet = keySet;
460     CPPUNIT_ASSERT( ckeySet.find(2) != ckeySet.end() );
461     CPPUNIT_ASSERT( ckeySet.lower_bound(2) != ckeySet.end() );
462     CPPUNIT_ASSERT( ckeySet.upper_bound(2) != ckeySet.end() );
463     CPPUNIT_ASSERT( ckeySet.equal_range(2) != make_pair(ckeySet.begin(), ckeySet.end()) );
464   }
465 
466   {
467     typedef multiset<Key const volatile*, KeyCmpPtr> KeySet;
468     KeySet keySet;
469     Key key1(1), key2(2), key3(3), key4(4);
470     keySet.insert(&key1);
471     keySet.insert(&key2);
472     keySet.insert(&key3);
473     keySet.insert(&key4);
474 
475     CPPUNIT_ASSERT( keySet.count(1) == 1 );
476     CPPUNIT_ASSERT( keySet.count(5) == 0 );
477 
478     CPPUNIT_ASSERT( keySet.find(2) != keySet.end() );
479     CPPUNIT_ASSERT( keySet.lower_bound(2) != keySet.end() );
480     CPPUNIT_ASSERT( keySet.upper_bound(2) != keySet.end() );
481     CPPUNIT_ASSERT( keySet.equal_range(2) != make_pair(keySet.begin(), keySet.end()) );
482 
483     KeySet const& ckeySet = keySet;
484     CPPUNIT_ASSERT( ckeySet.find(2) != ckeySet.end() );
485     CPPUNIT_ASSERT( ckeySet.lower_bound(2) != ckeySet.end() );
486     CPPUNIT_ASSERT( ckeySet.upper_bound(2) != ckeySet.end() );
487     CPPUNIT_ASSERT( ckeySet.equal_range(2) != make_pair(ckeySet.begin(), ckeySet.end()) );
488   }
489 #endif
490 }
491 
492 #if !defined (STLPORT) || \
493     !defined (_STLP_USE_PTR_SPECIALIZATIONS) || defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
494 #  if !defined (__DMC__)
495 /* Simple compilation test: Check that nested types like iterator
496  * can be access even if type used to instanciate container is not
497  * yet completely defined.
498  */
499 class IncompleteClass
500 {
501   set<IncompleteClass> instances;
502   typedef set<IncompleteClass>::iterator it;
503   multiset<IncompleteClass> minstances;
504   typedef multiset<IncompleteClass>::iterator mit;
505 };
506 #  endif
507 #endif
508