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)
11using namespace std;
12#endif
13
14//
15// TestCase class
16//
17class 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
36protected:
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
50CPPUNIT_TEST_SUITE_REGISTRATION(SetTest);
51
52
53//
54// tests implementation
55//
56void 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
68void 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
94void 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
105void SetTest::insert()
106{
107  set<int> s;
108  set<int>::iterator i = s.insert( s.end(), 0 );
109  CPPUNIT_ASSERT( *i == 0 );
110}
111
112void 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
123void 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
193class SetTestClass {
194public:
195  SetTestClass (int data) : _data(data)
196  {}
197
198  int data() const {
199    return _data;
200  }
201
202private:
203  int _data;
204};
205
206#if !defined (STLPORT) || defined (_STLP_USE_NAMESPACES)
207namespace std {
208#endif
209#if defined (STLPORT)
210  _STLP_TEMPLATE_NULL
211#else
212  template <>
213#endif
214  struct less<SetTestClass> {
215    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
223void 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
238void 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
254void 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
276void 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
360struct Key
361{
362  Key() : m_data(0) {}
363  explicit Key(int data) : m_data(data) {}
364
365  int m_data;
366};
367
368struct KeyCmp
369{
370  bool operator () (Key lhs, Key rhs) const
371  { return lhs.m_data < rhs.m_data; }
372
373  bool operator () (Key lhs, int rhs) const
374  { return lhs.m_data < rhs; }
375
376  bool operator () (int lhs, Key rhs) const
377  { return lhs < rhs.m_data; }
378};
379
380struct KeyCmpPtr
381{
382  bool operator () (Key const volatile *lhs, Key const volatile *rhs) const
383  { return (*lhs).m_data < (*rhs).m_data; }
384
385  bool operator () (Key const volatile *lhs, int rhs) const
386  { return (*lhs).m_data < rhs; }
387
388  bool operator () (int lhs, Key const volatile *rhs) const
389  { return lhs < (*rhs).m_data; }
390};
391
392void 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 */
499class 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