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 <map>
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 MapTest : public CPPUNIT_NS::TestCase
18{
19  CPPUNIT_TEST_SUITE(MapTest);
20  CPPUNIT_TEST(map1);
21  CPPUNIT_TEST(mmap1);
22  CPPUNIT_TEST(mmap2);
23  CPPUNIT_TEST(iterators);
24  CPPUNIT_TEST(equal_range);
25  CPPUNIT_TEST(allocator_with_state);
26#if !defined (STLPORT) || !defined (_STLP_USE_CONTAINERS_EXTENSION)
27  CPPUNIT_IGNORE;
28#endif
29  CPPUNIT_TEST(template_methods);
30  CPPUNIT_TEST_SUITE_END();
31
32protected:
33  void map1();
34  void mmap1();
35  void mmap2();
36  void iterators();
37  void equal_range();
38  void allocator_with_state();
39  void template_methods();
40};
41
42CPPUNIT_TEST_SUITE_REGISTRATION(MapTest);
43
44//
45// tests implementation
46//
47void MapTest::map1()
48{
49  typedef map<char, int, less<char> > maptype;
50  maptype m;
51  // Store mappings between roman numerals and decimals.
52  m['l'] = 50;
53  m['x'] = 20; // Deliberate mistake.
54  m['v'] = 5;
55  m['i'] = 1;
56//  cout << "m['x'] = " << m['x'] << endl;
57  CPPUNIT_ASSERT( m['x']== 20 );
58  m['x'] = 10; // Correct mistake.
59  CPPUNIT_ASSERT( m['x']== 10 );
60  CPPUNIT_ASSERT( m['z']== 0 );
61  //cout << "m['z'] = " << m['z'] << endl; // Note default value is added.
62  CPPUNIT_ASSERT( m.count('z') == 1 );
63  //cout << "m.count('z') = " << m.count('z') << endl;
64  pair<maptype::iterator, bool> p = m.insert(pair<const char, int>('c', 100));
65  CPPUNIT_ASSERT( p.second );
66  CPPUNIT_ASSERT( p.first != m.end() );
67  CPPUNIT_ASSERT( (*p.first).first == 'c' );
68  CPPUNIT_ASSERT( (*p.first).second == 100 );
69
70  p = m.insert(pair<const char, int>('c', 100));
71  CPPUNIT_ASSERT( !p.second ); // already existing pair
72  CPPUNIT_ASSERT( p.first != m.end() );
73  CPPUNIT_ASSERT( (*p.first).first == 'c' );
74  CPPUNIT_ASSERT( (*p.first).second == 100 );
75}
76
77void MapTest::mmap1()
78{
79  typedef multimap<char, int, less<char> > mmap;
80  mmap m;
81  CPPUNIT_ASSERT(m.count('X')==0);
82
83  m.insert(pair<const char, int>('X', 10)); // Standard way.
84  CPPUNIT_ASSERT(m.count('X')==1);
85
86  m.insert(pair<const char, int>('X', 20)); // jbuck: standard way
87  CPPUNIT_ASSERT(m.count('X')==2);
88
89  m.insert(pair<const char, int>('Y', 32)); // jbuck: standard way
90  mmap::iterator i = m.find('X'); // Find first match.
91#ifndef _STLP_CONST
92#  define _STLP_CONST const
93#endif
94  pair<_STLP_CONST char, int> p('X', 10);
95  CPPUNIT_ASSERT(*i == p);
96  CPPUNIT_ASSERT((*i).first == 'X');
97  CPPUNIT_ASSERT((*i).second == 10);
98  i++;
99  CPPUNIT_ASSERT((*i).first == 'X');
100  CPPUNIT_ASSERT((*i).second == 20);
101  i++;
102  CPPUNIT_ASSERT((*i).first == 'Y');
103  CPPUNIT_ASSERT((*i).second == 32);
104  i++;
105  CPPUNIT_ASSERT(i == m.end());
106
107  size_t count = m.erase('X');
108  CPPUNIT_ASSERT(count==2);
109}
110void MapTest::mmap2()
111{
112  typedef pair<const int, char> pair_type;
113
114  pair_type p1(3, 'c');
115  pair_type p2(6, 'f');
116  pair_type p3(1, 'a');
117  pair_type p4(2, 'b');
118  pair_type p5(3, 'x');
119  pair_type p6(6, 'f');
120
121  typedef multimap<int, char, less<int> > mmap;
122
123  pair_type array [] = {
124    p1,
125    p2,
126    p3,
127    p4,
128    p5,
129    p6
130  };
131
132  mmap m(array + 0, array + 6);
133  mmap::iterator i;
134  i = m.lower_bound(3);
135  CPPUNIT_ASSERT((*i).first==3);
136  CPPUNIT_ASSERT((*i).second=='c');
137
138  i = m.upper_bound(3);
139  CPPUNIT_ASSERT((*i).first==6);
140  CPPUNIT_ASSERT((*i).second=='f');
141}
142
143
144void MapTest::iterators()
145{
146  typedef map<int, char, less<int> > int_map;
147  int_map imap;
148  {
149    int_map::iterator ite(imap.begin());
150    int_map::const_iterator cite(imap.begin());
151    CPPUNIT_ASSERT( ite == cite );
152    CPPUNIT_ASSERT( !(ite != cite) );
153    CPPUNIT_ASSERT( cite == ite );
154    CPPUNIT_ASSERT( !(cite != ite) );
155  }
156
157  typedef multimap<int, char, less<int> > mmap;
158  typedef mmap::value_type pair_type;
159
160  pair_type p1(3, 'c');
161  pair_type p2(6, 'f');
162  pair_type p3(1, 'a');
163  pair_type p4(2, 'b');
164  pair_type p5(3, 'x');
165  pair_type p6(6, 'f');
166
167  pair_type array [] = {
168    p1,
169    p2,
170    p3,
171    p4,
172    p5,
173    p6
174  };
175
176  mmap m(array+0, array + 6);
177
178  {
179    mmap::iterator ite(m.begin());
180    mmap::const_iterator cite(m.begin());
181    //test compare between const_iterator and iterator
182    CPPUNIT_ASSERT( ite == cite );
183    CPPUNIT_ASSERT( !(ite != cite) );
184    CPPUNIT_ASSERT( cite == ite );
185    CPPUNIT_ASSERT( !(cite != ite) );
186  }
187
188#if 0
189  /*
190   * A check that map and multimap iterators are NOT comparable
191   * the following code should generate a compile time error
192   */
193  {
194    int_map::iterator mite(imap.begin());
195    int_map::const_iterator mcite(imap.begin());
196    mmap::iterator mmite(m.begin());
197    mmap::const_iterator mmcite(m.begin());
198    CPPUNIT_ASSERT( !(mite == mmite) );
199    CPPUNIT_ASSERT( !(mcite == mmcite) );
200    CPPUNIT_ASSERT( mite != mmite );
201    CPPUNIT_ASSERT( mcite != mmcite );
202    CPPUNIT_ASSERT( !(mite == mmcite) );
203    CPPUNIT_ASSERT( !(mite == mmcite) );
204    CPPUNIT_ASSERT( mite != mmcite );
205    CPPUNIT_ASSERT( mite != mmcite );
206  }
207
208#endif
209
210  mmap::reverse_iterator ri = m.rbegin();
211  CPPUNIT_ASSERT( ri != m.rend() );
212  CPPUNIT_ASSERT( ri == m.rbegin() );
213  CPPUNIT_ASSERT( (*ri).first == 6 );
214  CPPUNIT_ASSERT( (*ri++).second == 'f' );
215  CPPUNIT_ASSERT( (*ri).first == 6 );
216  CPPUNIT_ASSERT( (*ri).second == 'f' );
217
218  mmap const& cm = m;
219  mmap::const_reverse_iterator rci = cm.rbegin();
220  CPPUNIT_ASSERT( rci != cm.rend() );
221  CPPUNIT_ASSERT( (*rci).first == 6 );
222  CPPUNIT_ASSERT( (*rci++).second == 'f' );
223  CPPUNIT_ASSERT( (*rci).first == 6 );
224  CPPUNIT_ASSERT( (*rci).second == 'f' );
225}
226
227void MapTest::equal_range()
228{
229  typedef map<char, int, less<char> > maptype;
230  {
231    maptype m;
232    m['x'] = 10;
233
234    pair<maptype::iterator, maptype::iterator> ret;
235    ret = m.equal_range('x');
236    CPPUNIT_ASSERT( ret.first != ret.second );
237    CPPUNIT_ASSERT( (*(ret.first)).first == 'x' );
238    CPPUNIT_ASSERT( (*(ret.first)).second == 10 );
239    CPPUNIT_ASSERT( ++(ret.first) == ret.second );
240  }
241  {
242    {
243      maptype m;
244
245      maptype::iterator i = m.lower_bound( 'x' );
246      CPPUNIT_ASSERT( i == m.end() );
247
248      i = m.upper_bound( 'x' );
249      CPPUNIT_ASSERT( i == m.end() );
250
251      pair<maptype::iterator, maptype::iterator> ret;
252      ret = m.equal_range('x');
253      CPPUNIT_ASSERT( ret.first == ret.second );
254      CPPUNIT_ASSERT( ret.first == m.end() );
255    }
256
257    {
258      const maptype m;
259      pair<maptype::const_iterator, maptype::const_iterator> ret;
260      ret = m.equal_range('x');
261      CPPUNIT_ASSERT( ret.first == ret.second );
262      CPPUNIT_ASSERT( ret.first == m.end() );
263    }
264  }
265}
266
267void MapTest::allocator_with_state()
268{
269  char buf1[1024];
270  StackAllocator<pair<const int, int> > stack1(buf1, buf1 + sizeof(buf1));
271
272  char buf2[1024];
273  StackAllocator<pair<const int, int> > stack2(buf2, buf2 + sizeof(buf2));
274
275  {
276    typedef map<int, int, less<int>, StackAllocator<pair<const int, int> > > MapInt;
277    less<int> intLess;
278    MapInt mint1(intLess, stack1);
279    int i;
280    for (i = 0; i < 5; ++i)
281      mint1.insert(MapInt::value_type(i, i));
282    MapInt mint1Cpy(mint1);
283
284    MapInt mint2(intLess, stack2);
285    for (; i < 10; ++i)
286      mint2.insert(MapInt::value_type(i, i));
287    MapInt mint2Cpy(mint2);
288
289    mint1.swap(mint2);
290
291    CPPUNIT_ASSERT( mint1.get_allocator().swaped() );
292    CPPUNIT_ASSERT( mint2.get_allocator().swaped() );
293
294    CPPUNIT_ASSERT( mint1 == mint2Cpy );
295    CPPUNIT_ASSERT( mint2 == mint1Cpy );
296    CPPUNIT_ASSERT( mint1.get_allocator() == stack2 );
297    CPPUNIT_ASSERT( mint2.get_allocator() == stack1 );
298  }
299  CPPUNIT_ASSERT( stack1.ok() );
300  CPPUNIT_ASSERT( stack2.ok() );
301}
302
303struct Key
304{
305  Key() : m_data(0) {}
306  explicit Key(int data) : m_data(data) {}
307
308  int m_data;
309};
310
311struct KeyCmp
312{
313  bool operator () (Key lhs, Key rhs) const
314  { return lhs.m_data < rhs.m_data; }
315
316  bool operator () (Key lhs, int rhs) const
317  { return lhs.m_data < rhs; }
318
319  bool operator () (int lhs, Key rhs) const
320  { return lhs < rhs.m_data; }
321};
322
323struct KeyCmpPtr
324{
325  bool operator () (Key const volatile *lhs, Key const volatile *rhs) const
326  { return (*lhs).m_data < (*rhs).m_data; }
327
328  bool operator () (Key const volatile *lhs, int rhs) const
329  { return (*lhs).m_data < rhs; }
330
331  bool operator () (int lhs, Key const volatile *rhs) const
332  { return lhs < (*rhs).m_data; }
333};
334
335void MapTest::template_methods()
336{
337#if defined (STLPORT) && defined (_STLP_USE_CONTAINERS_EXTENSION)
338  {
339    typedef map<Key, int, KeyCmp> Container;
340    typedef Container::value_type value;
341    Container cont;
342    cont.insert(value(Key(1), 1));
343    cont.insert(value(Key(2), 2));
344    cont.insert(value(Key(3), 3));
345    cont.insert(value(Key(4), 4));
346
347    CPPUNIT_ASSERT( cont.count(Key(1)) == 1 );
348    CPPUNIT_ASSERT( cont.count(1) == 1 );
349    CPPUNIT_ASSERT( cont.count(5) == 0 );
350
351    CPPUNIT_ASSERT( cont.find(2) != cont.end() );
352    CPPUNIT_ASSERT( cont.lower_bound(2) != cont.end() );
353    CPPUNIT_ASSERT( cont.upper_bound(2) != cont.end() );
354    CPPUNIT_ASSERT( cont.equal_range(2) != make_pair(cont.begin(), cont.end()) );
355
356    Container const& ccont = cont;
357    CPPUNIT_ASSERT( ccont.find(2) != ccont.end() );
358    CPPUNIT_ASSERT( ccont.lower_bound(2) != ccont.end() );
359    CPPUNIT_ASSERT( ccont.upper_bound(2) != ccont.end() );
360    CPPUNIT_ASSERT( ccont.equal_range(2) != make_pair(ccont.end(), ccont.end()) );
361  }
362
363  {
364    typedef map<Key*, int, KeyCmpPtr> Container;
365    typedef Container::value_type value;
366    Container cont;
367    Key key1(1), key2(2), key3(3), key4(4);
368    cont.insert(value(&key1, 1));
369    cont.insert(value(&key2, 2));
370    cont.insert(value(&key3, 3));
371    cont.insert(value(&key4, 4));
372
373    CPPUNIT_ASSERT( cont.count(1) == 1 );
374    CPPUNIT_ASSERT( cont.count(5) == 0 );
375
376    CPPUNIT_ASSERT( cont.find(2) != cont.end() );
377    CPPUNIT_ASSERT( cont.lower_bound(2) != cont.end() );
378    CPPUNIT_ASSERT( cont.upper_bound(2) != cont.end() );
379    CPPUNIT_ASSERT( cont.equal_range(2) != make_pair(cont.begin(), cont.end()) );
380
381    Container const& ccont = cont;
382    CPPUNIT_ASSERT( ccont.find(2) != ccont.end() );
383    CPPUNIT_ASSERT( ccont.lower_bound(2) != ccont.end() );
384    CPPUNIT_ASSERT( ccont.upper_bound(2) != ccont.end() );
385    CPPUNIT_ASSERT( ccont.equal_range(2) != make_pair(ccont.begin(), ccont.end()) );
386  }
387  {
388    typedef multimap<Key, int, KeyCmp> Container;
389    typedef Container::value_type value;
390    Container cont;
391    cont.insert(value(Key(1), 1));
392    cont.insert(value(Key(2), 2));
393    cont.insert(value(Key(3), 3));
394    cont.insert(value(Key(4), 4));
395
396    CPPUNIT_ASSERT( cont.count(Key(1)) == 1 );
397    CPPUNIT_ASSERT( cont.count(1) == 1 );
398    CPPUNIT_ASSERT( cont.count(5) == 0 );
399
400    CPPUNIT_ASSERT( cont.find(2) != cont.end() );
401    CPPUNIT_ASSERT( cont.lower_bound(2) != cont.end() );
402    CPPUNIT_ASSERT( cont.upper_bound(2) != cont.end() );
403    CPPUNIT_ASSERT( cont.equal_range(2) != make_pair(cont.begin(), cont.end()) );
404
405    Container const& ccont = cont;
406    CPPUNIT_ASSERT( ccont.find(2) != ccont.end() );
407    CPPUNIT_ASSERT( ccont.lower_bound(2) != ccont.end() );
408    CPPUNIT_ASSERT( ccont.upper_bound(2) != ccont.end() );
409    CPPUNIT_ASSERT( ccont.equal_range(2) != make_pair(ccont.end(), ccont.end()) );
410  }
411
412  {
413    typedef multimap<Key const volatile*, int, KeyCmpPtr> Container;
414    typedef Container::value_type value;
415    Container cont;
416    Key key1(1), key2(2), key3(3), key4(4);
417    cont.insert(value(&key1, 1));
418    cont.insert(value(&key2, 2));
419    cont.insert(value(&key3, 3));
420    cont.insert(value(&key4, 4));
421
422    CPPUNIT_ASSERT( cont.count(1) == 1 );
423    CPPUNIT_ASSERT( cont.count(5) == 0 );
424
425    CPPUNIT_ASSERT( cont.find(2) != cont.end() );
426    CPPUNIT_ASSERT( cont.lower_bound(2) != cont.end() );
427    CPPUNIT_ASSERT( cont.upper_bound(2) != cont.end() );
428    CPPUNIT_ASSERT( cont.equal_range(2) != make_pair(cont.begin(), cont.end()) );
429
430    Container const& ccont = cont;
431    CPPUNIT_ASSERT( ccont.find(2) != ccont.end() );
432    CPPUNIT_ASSERT( ccont.lower_bound(2) != ccont.end() );
433    CPPUNIT_ASSERT( ccont.upper_bound(2) != ccont.end() );
434    CPPUNIT_ASSERT( ccont.equal_range(2) != make_pair(ccont.begin(), ccont.end()) );
435  }
436#endif
437}
438
439#if !defined (STLPORT) || \
440    !defined (_STLP_USE_PTR_SPECIALIZATIONS) || defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
441#  if !defined (__DMC__)
442/* Simple compilation test: Check that nested types like iterator
443 * can be access even if type used to instanciate container is not
444 * yet completely defined.
445 */
446class IncompleteClass
447{
448  map<IncompleteClass, IncompleteClass> instances;
449  typedef map<IncompleteClass, IncompleteClass>::iterator it;
450  multimap<IncompleteClass, IncompleteClass> minstances;
451  typedef multimap<IncompleteClass, IncompleteClass>::iterator mit;
452};
453#  endif
454#endif
455