ReactOS Development > Doxygen

00001 //Has to be first for StackAllocator swap overload to be taken
00002 //into account (at least using GCC 4.0.1)
00003 #include "stack_allocator.h"
00004 
00005 #include <set>
00006 #include <algorithm>
00007 
00008 #include "cppunit/cppunit_proxy.h"
00009 
00010 #if !defined (STLPORT) || defined(_STLP_USE_NAMESPACES)
00011 using namespace std;
00012 #endif
00013 
00014 //
00015 // TestCase class
00016 //
00017 class SetTest : public CPPUNIT_NS::TestCase
00018 {
00019   CPPUNIT_TEST_SUITE(SetTest);
00020   CPPUNIT_TEST(set1);
00021   CPPUNIT_TEST(set2);
00022   CPPUNIT_TEST(erase);
00023   CPPUNIT_TEST(insert);
00024   CPPUNIT_TEST(find);
00025   CPPUNIT_TEST(bounds);
00026   CPPUNIT_TEST(specialized_less);
00027   CPPUNIT_TEST(implementation_check);
00028   CPPUNIT_TEST(allocator_with_state);
00029   CPPUNIT_TEST(reverse_iterator_test);
00030 #if !defined (STLPORT) || !defined (_STLP_USE_CONTAINERS_EXTENSION)
00031   CPPUNIT_IGNORE;
00032 #endif
00033   CPPUNIT_TEST(template_methods);
00034   CPPUNIT_TEST_SUITE_END();
00035 
00036 protected:
00037   void set1();
00038   void set2();
00039   void erase();
00040   void insert();
00041   void find();
00042   void bounds();
00043   void specialized_less();
00044   void implementation_check();
00045   void allocator_with_state();
00046   void reverse_iterator_test();
00047   void template_methods();
00048 };
00049 
00050 CPPUNIT_TEST_SUITE_REGISTRATION(SetTest);
00051 
00052 
00053 //
00054 // tests implementation
00055 //
00056 void SetTest::set1()
00057 {
00058   set<int, less<int> > s;
00059   CPPUNIT_ASSERT (s.count(42) == 0);
00060   s.insert(42);
00061   CPPUNIT_ASSERT (s.count(42) == 1);
00062   s.insert(42);
00063   CPPUNIT_ASSERT (s.count(42) == 1);
00064   size_t count = s.erase(42);
00065   CPPUNIT_ASSERT (count == 1);
00066 }
00067 
00068 void SetTest::set2()
00069 {
00070   typedef set<int, less<int> > int_set;
00071   int_set s;
00072   pair<int_set::iterator, bool> p = s.insert(42);
00073   CPPUNIT_ASSERT (p.second == true);
00074   p = s.insert(42);
00075   CPPUNIT_ASSERT (p.second == false);
00076 
00077   int array1 [] = { 1, 3, 6, 7 };
00078   s.insert(array1, array1 + 4);
00079   CPPUNIT_ASSERT (distance(s.begin(), s.end()) == 5);
00080 
00081   int_set s2;
00082   s2.swap(s);
00083   CPPUNIT_ASSERT (distance(s2.begin(), s2.end()) == 5);
00084   CPPUNIT_ASSERT (distance(s.begin(), s.end()) == 0);
00085 
00086   int_set s3;
00087   s3.swap(s);
00088   s3.swap(s2);
00089   CPPUNIT_ASSERT (distance(s.begin(), s.end()) == 0);
00090   CPPUNIT_ASSERT (distance(s2.begin(), s2.end()) == 0);
00091   CPPUNIT_ASSERT (distance(s3.begin(), s3.end()) == 5);
00092 }
00093 
00094 void SetTest::erase()
00095 {
00096   set<int, less<int> > s;
00097   s.insert(1);
00098   s.erase(s.begin());
00099   CPPUNIT_ASSERT( s.empty() );
00100 
00101   size_t nb = s.erase(1);
00102   CPPUNIT_ASSERT(nb == 0);
00103 }
00104 
00105 void SetTest::insert()
00106 {
00107   set<int> s;
00108   set<int>::iterator i = s.insert( s.end(), 0 );
00109   CPPUNIT_ASSERT( *i == 0 );
00110 }
00111 
00112 void SetTest::find()
00113 {
00114   set<int> s;
00115 
00116   CPPUNIT_ASSERT( s.find(0) == s.end() );
00117 
00118   set<int> const& crs = s;
00119 
00120   CPPUNIT_ASSERT( crs.find(0) == crs.end() );
00121 }
00122 
00123 void SetTest::bounds()
00124 {
00125   int array1 [] = { 1, 3, 6, 7 };
00126   set<int> s(array1, array1 + sizeof(array1) / sizeof(array1[0]));
00127   set<int> const& crs = s;
00128 
00129   set<int>::iterator sit;
00130   set<int>::const_iterator scit;
00131   pair<set<int>::iterator, set<int>::iterator> pit;
00132   pair<set<int>::const_iterator, set<int>::const_iterator> pcit;
00133 
00134   //Check iterator on mutable set
00135   sit = s.lower_bound(2);
00136   CPPUNIT_ASSERT( sit != s.end() );
00137   CPPUNIT_ASSERT( *sit == 3 );
00138 
00139   sit = s.upper_bound(5);
00140   CPPUNIT_ASSERT( sit != s.end() );
00141   CPPUNIT_ASSERT( *sit == 6 );
00142 
00143   pit = s.equal_range(6);
00144   CPPUNIT_ASSERT( pit.first != pit.second );
00145   CPPUNIT_ASSERT( pit.first != s.end() );
00146   CPPUNIT_ASSERT( *pit.first == 6 );
00147   CPPUNIT_ASSERT( pit.second != s.end() );
00148   CPPUNIT_ASSERT( *pit.second == 7 );
00149 
00150   pit = s.equal_range(4);
00151   CPPUNIT_ASSERT( pit.first == pit.second );
00152   CPPUNIT_ASSERT( pit.first != s.end() );
00153   CPPUNIT_ASSERT( *pit.first == 6 );
00154   CPPUNIT_ASSERT( pit.second != s.end() );
00155   CPPUNIT_ASSERT( *pit.second == 6 );
00156 
00157   //Check const_iterator on mutable set
00158   scit = s.lower_bound(2);
00159   CPPUNIT_ASSERT( scit != s.end() );
00160   CPPUNIT_ASSERT( *scit == 3 );
00161 
00162   scit = s.upper_bound(5);
00163   CPPUNIT_ASSERT( scit != s.end() );
00164   CPPUNIT_ASSERT( *scit == 6 );
00165 
00166 #ifdef _STLP_MEMBER_TEMPLATES
00167   pcit = s.equal_range(6);
00168   CPPUNIT_ASSERT( pcit.first != pcit.second );
00169   CPPUNIT_ASSERT( pcit.first != s.end() );
00170   CPPUNIT_ASSERT( *pcit.first == 6 );
00171   CPPUNIT_ASSERT( pcit.second != s.end() );
00172   CPPUNIT_ASSERT( *pcit.second == 7 );
00173 #endif
00174 
00175   //Check const_iterator on const set
00176   scit = crs.lower_bound(2);
00177   CPPUNIT_ASSERT( scit != crs.end() );
00178   CPPUNIT_ASSERT( *scit == 3 );
00179 
00180   scit = crs.upper_bound(5);
00181   CPPUNIT_ASSERT( scit != crs.end() );
00182   CPPUNIT_ASSERT( *scit == 6 );
00183 
00184   pcit = crs.equal_range(6);
00185   CPPUNIT_ASSERT( pcit.first != pcit.second );
00186   CPPUNIT_ASSERT( pcit.first != crs.end() );
00187   CPPUNIT_ASSERT( *pcit.first == 6 );
00188   CPPUNIT_ASSERT( pcit.second != crs.end() );
00189   CPPUNIT_ASSERT( *pcit.second == 7 );
00190 }
00191 
00192 
00193 class SetTestClass {
00194 public:
00195   SetTestClass (int data) : _data(data)
00196   {}
00197 
00198   int data() const {
00199     return _data;
00200   }
00201 
00202 private:
00203   int _data;
00204 };
00205 
00206 #if !defined (STLPORT) || defined (_STLP_USE_NAMESPACES)
00207 namespace std {
00208 #endif
00209 #if defined (STLPORT)
00210   _STLP_TEMPLATE_NULL
00211 #else
00212   template <>
00213 #endif
00214   struct less<SetTestClass> {
00215     bool operator () (SetTestClass const& lhs, SetTestClass const& rhs) const {
00216       return lhs.data() < rhs.data();
00217     }
00218   };
00219 #if !defined (STLPORT) || defined (_STLP_USE_NAMESPACES)
00220 }
00221 #endif
00222 
00223 void SetTest::specialized_less()
00224 {
00225   set<SetTestClass> s;
00226   s.insert(SetTestClass(1));
00227   s.insert(SetTestClass(3));
00228   s.insert(SetTestClass(2));
00229   s.insert(SetTestClass(0));
00230 
00231   set<SetTestClass>::iterator sit(s.begin()), sitEnd(s.end());
00232   int i = 0;
00233   for (; sit != sitEnd; ++sit, ++i) {
00234     CPPUNIT_ASSERT( sit->data() == i );
00235   }
00236 }
00237 
00238 void SetTest::implementation_check()
00239 {
00240   set<int> tree;
00241   tree.insert(1);
00242   set<int>::iterator it = tree.begin();
00243   int const& int_ref = *it++;
00244   CPPUNIT_ASSERT( int_ref == 1 );
00245 
00246   CPPUNIT_ASSERT( it == tree.end() );
00247   CPPUNIT_ASSERT( it != tree.begin() );
00248 
00249   set<int>::const_iterator cit = tree.begin();
00250   int const& int_cref = *cit++;
00251   CPPUNIT_ASSERT( int_cref == 1 );
00252 }
00253 
00254 void SetTest::reverse_iterator_test()
00255 {
00256   set<int> tree;
00257   tree.insert(1);
00258   tree.insert(2);
00259 
00260   {
00261     set<int>::reverse_iterator rit(tree.rbegin());
00262     CPPUNIT_ASSERT( *(rit++) == 2 );
00263     CPPUNIT_ASSERT( *(rit++) == 1 );
00264     CPPUNIT_ASSERT( rit == tree.rend() );
00265   }
00266 
00267   {
00268     set<int> const& ctree = tree;
00269     set<int>::const_reverse_iterator rit(ctree.rbegin());
00270     CPPUNIT_ASSERT( *(rit++) == 2 );
00271     CPPUNIT_ASSERT( *(rit++) == 1 );
00272     CPPUNIT_ASSERT( rit == ctree.rend() );
00273   }
00274 }
00275 
00276 void SetTest::allocator_with_state()
00277 {
00278   char buf1[1024];
00279   StackAllocator<int> stack1(buf1, buf1 + sizeof(buf1));
00280 
00281   char buf2[1024];
00282   StackAllocator<int> stack2(buf2, buf2 + sizeof(buf2));
00283 
00284   int i;
00285   typedef set<int, less<int>, StackAllocator<int> > SetInt;
00286   less<int> intLess;
00287 
00288   {
00289     SetInt sint1(intLess, stack1);
00290     for (i = 0; i < 5; ++i)
00291       sint1.insert(i);
00292     SetInt sint1Cpy(sint1);
00293 
00294     SetInt sint2(intLess, stack2);
00295     for (; i < 10; ++i)
00296       sint2.insert(i);
00297     SetInt sint2Cpy(sint2);
00298 
00299     sint1.swap(sint2);
00300 
00301     CPPUNIT_ASSERT( sint1.get_allocator().swaped() );
00302     CPPUNIT_ASSERT( sint2.get_allocator().swaped() );
00303 
00304     CPPUNIT_ASSERT( sint1 == sint2Cpy );
00305     CPPUNIT_ASSERT( sint2 == sint1Cpy );
00306     CPPUNIT_ASSERT( sint1.get_allocator() == stack2 );
00307     CPPUNIT_ASSERT( sint2.get_allocator() == stack1 );
00308   }
00309   CPPUNIT_ASSERT( stack1.ok() );
00310   CPPUNIT_ASSERT( stack2.ok() );
00311   stack1.reset(); stack2.reset();
00312 
00313   {
00314     SetInt sint1(intLess, stack1);
00315     SetInt sint1Cpy(sint1);
00316 
00317     SetInt sint2(intLess, stack2);
00318     for (i = 0; i < 10; ++i)
00319       sint2.insert(i);
00320     SetInt sint2Cpy(sint2);
00321 
00322     sint1.swap(sint2);
00323 
00324     CPPUNIT_ASSERT( sint1.get_allocator().swaped() );
00325     CPPUNIT_ASSERT( sint2.get_allocator().swaped() );
00326 
00327     CPPUNIT_ASSERT( sint1 == sint2Cpy );
00328     CPPUNIT_ASSERT( sint2 == sint1Cpy );
00329     CPPUNIT_ASSERT( sint1.get_allocator() == stack2 );
00330     CPPUNIT_ASSERT( sint2.get_allocator() == stack1 );
00331   }
00332   CPPUNIT_ASSERT( stack1.ok() );
00333   CPPUNIT_ASSERT( stack2.ok() );
00334   stack1.reset(); stack2.reset();
00335 
00336   {
00337     SetInt sint1(intLess, stack1);
00338     for (i = 0; i < 10; ++i)
00339       sint1.insert(i);
00340     SetInt sint1Cpy(sint1);
00341 
00342     SetInt sint2(intLess, stack2);
00343     SetInt sint2Cpy(sint2);
00344 
00345     sint1.swap(sint2);
00346 
00347     CPPUNIT_ASSERT( sint1.get_allocator().swaped() );
00348     CPPUNIT_ASSERT( sint2.get_allocator().swaped() );
00349 
00350     CPPUNIT_ASSERT( sint1 == sint2Cpy );
00351     CPPUNIT_ASSERT( sint2 == sint1Cpy );
00352     CPPUNIT_ASSERT( sint1.get_allocator() == stack2 );
00353     CPPUNIT_ASSERT( sint2.get_allocator() == stack1 );
00354   }
00355   CPPUNIT_ASSERT( stack1.ok() );
00356   CPPUNIT_ASSERT( stack2.ok() );
00357   stack1.reset(); stack2.reset();
00358 }
00359 
00360 struct Key
00361 {
00362   Key() : m_data(0) {}
00363   explicit Key(int data) : m_data(data) {}
00364 
00365   int m_data;
00366 };
00367 
00368 struct KeyCmp
00369 {
00370   bool operator () (Key lhs, Key rhs) const
00371   { return lhs.m_data < rhs.m_data; }
00372 
00373   bool operator () (Key lhs, int rhs) const
00374   { return lhs.m_data < rhs; }
00375 
00376   bool operator () (int lhs, Key rhs) const
00377   { return lhs < rhs.m_data; }
00378 };
00379 
00380 struct KeyCmpPtr
00381 {
00382   bool operator () (Key const volatile *lhs, Key const volatile *rhs) const
00383   { return (*lhs).m_data < (*rhs).m_data; }
00384 
00385   bool operator () (Key const volatile *lhs, int rhs) const
00386   { return (*lhs).m_data < rhs; }
00387 
00388   bool operator () (int lhs, Key const volatile *rhs) const
00389   { return lhs < (*rhs).m_data; }
00390 };
00391 
00392 void SetTest::template_methods()
00393 {
00394 #if defined (STLPORT) && defined (_STLP_USE_CONTAINERS_EXTENSION)
00395   {
00396     typedef set<Key, KeyCmp> KeySet;
00397     KeySet keySet;
00398     keySet.insert(Key(1));
00399     keySet.insert(Key(2));
00400     keySet.insert(Key(3));
00401     keySet.insert(Key(4));
00402 
00403     CPPUNIT_ASSERT( keySet.count(Key(1)) == 1 );
00404     CPPUNIT_ASSERT( keySet.count(1) == 1 );
00405     CPPUNIT_ASSERT( keySet.count(5) == 0 );
00406 
00407     CPPUNIT_ASSERT( keySet.find(2) != keySet.end() );
00408     CPPUNIT_ASSERT( keySet.lower_bound(2) != keySet.end() );
00409     CPPUNIT_ASSERT( keySet.upper_bound(2) != keySet.end() );
00410     CPPUNIT_ASSERT( keySet.equal_range(2) != make_pair(keySet.begin(), keySet.end()) );
00411 
00412     KeySet const& ckeySet = keySet;
00413     CPPUNIT_ASSERT( ckeySet.find(2) != ckeySet.end() );
00414     CPPUNIT_ASSERT( ckeySet.lower_bound(2) != ckeySet.end() );
00415     CPPUNIT_ASSERT( ckeySet.upper_bound(2) != ckeySet.end() );
00416     CPPUNIT_ASSERT( ckeySet.equal_range(2) != make_pair(ckeySet.begin(), ckeySet.end()) );
00417   }
00418 
00419   {
00420     typedef set<Key*, KeyCmpPtr> KeySet;
00421     KeySet keySet;
00422     Key key1(1), key2(2), key3(3), key4(4);
00423     keySet.insert(&key1);
00424     keySet.insert(&key2);
00425     keySet.insert(&key3);
00426     keySet.insert(&key4);
00427 
00428     CPPUNIT_ASSERT( keySet.count(1) == 1 );
00429     CPPUNIT_ASSERT( keySet.count(5) == 0 );
00430 
00431     CPPUNIT_ASSERT( keySet.find(2) != keySet.end() );
00432     CPPUNIT_ASSERT( keySet.lower_bound(2) != keySet.end() );
00433     CPPUNIT_ASSERT( keySet.upper_bound(2) != keySet.end() );
00434     CPPUNIT_ASSERT( keySet.equal_range(2) != make_pair(keySet.begin(), keySet.end()) );
00435 
00436     KeySet const& ckeySet = keySet;
00437     CPPUNIT_ASSERT( ckeySet.find(2) != ckeySet.end() );
00438     CPPUNIT_ASSERT( ckeySet.lower_bound(2) != ckeySet.end() );
00439     CPPUNIT_ASSERT( ckeySet.upper_bound(2) != ckeySet.end() );
00440     CPPUNIT_ASSERT( ckeySet.equal_range(2) != make_pair(ckeySet.begin(), ckeySet.end()) );
00441   }
00442   {
00443     typedef multiset<Key, KeyCmp> KeySet;
00444     KeySet keySet;
00445     keySet.insert(Key(1));
00446     keySet.insert(Key(2));
00447     keySet.insert(Key(3));
00448     keySet.insert(Key(4));
00449 
00450     CPPUNIT_ASSERT( keySet.count(Key(1)) == 1 );
00451     CPPUNIT_ASSERT( keySet.count(1) == 1 );
00452     CPPUNIT_ASSERT( keySet.count(5) == 0 );
00453 
00454     CPPUNIT_ASSERT( keySet.find(2) != keySet.end() );
00455     CPPUNIT_ASSERT( keySet.lower_bound(2) != keySet.end() );
00456     CPPUNIT_ASSERT( keySet.upper_bound(2) != keySet.end() );
00457     CPPUNIT_ASSERT( keySet.equal_range(2) != make_pair(keySet.begin(), keySet.end()) );
00458 
00459     KeySet const& ckeySet = keySet;
00460     CPPUNIT_ASSERT( ckeySet.find(2) != ckeySet.end() );
00461     CPPUNIT_ASSERT( ckeySet.lower_bound(2) != ckeySet.end() );
00462     CPPUNIT_ASSERT( ckeySet.upper_bound(2) != ckeySet.end() );
00463     CPPUNIT_ASSERT( ckeySet.equal_range(2) != make_pair(ckeySet.begin(), ckeySet.end()) );
00464   }
00465 
00466   {
00467     typedef multiset<Key const volatile*, KeyCmpPtr> KeySet;
00468     KeySet keySet;
00469     Key key1(1), key2(2), key3(3), key4(4);
00470     keySet.insert(&key1);
00471     keySet.insert(&key2);
00472     keySet.insert(&key3);
00473     keySet.insert(&key4);
00474 
00475     CPPUNIT_ASSERT( keySet.count(1) == 1 );
00476     CPPUNIT_ASSERT( keySet.count(5) == 0 );
00477 
00478     CPPUNIT_ASSERT( keySet.find(2) != keySet.end() );
00479     CPPUNIT_ASSERT( keySet.lower_bound(2) != keySet.end() );
00480     CPPUNIT_ASSERT( keySet.upper_bound(2) != keySet.end() );
00481     CPPUNIT_ASSERT( keySet.equal_range(2) != make_pair(keySet.begin(), keySet.end()) );
00482 
00483     KeySet const& ckeySet = keySet;
00484     CPPUNIT_ASSERT( ckeySet.find(2) != ckeySet.end() );
00485     CPPUNIT_ASSERT( ckeySet.lower_bound(2) != ckeySet.end() );
00486     CPPUNIT_ASSERT( ckeySet.upper_bound(2) != ckeySet.end() );
00487     CPPUNIT_ASSERT( ckeySet.equal_range(2) != make_pair(ckeySet.begin(), ckeySet.end()) );
00488   }
00489 #endif
00490 }
00491 
00492 #if !defined (STLPORT) || \
00493     !defined (_STLP_USE_PTR_SPECIALIZATIONS) || defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
00494 #  if !defined (__DMC__)
00495 /* Simple compilation test: Check that nested types like iterator
00496  * can be access even if type used to instanciate container is not
00497  * yet completely defined.
00498  */
00499 class IncompleteClass
00500 {
00501   set<IncompleteClass> instances;
00502   typedef set<IncompleteClass>::iterator it;
00503   multiset<IncompleteClass> minstances;
00504   typedef multiset<IncompleteClass>::iterator mit;
00505 };
00506 #  endif
00507 #endif
Generated on Sat May 26 2012 04:34:44 for ReactOS by
1.7.6.1