bvt/bvt05.cc

   1 // This file is part of the ustl library, an STL implementation.
   2 //
   3 // Copyright (C) 2005 by Mike Sharov <msharov@users.sourceforge.net>
   4 // This file is free software, distributed under the MIT License.
   5 //
   6
   7 #include "stdtest.h"
   8
   9 typedef vector<int>                     intvec_t;
  10 typedef const intvec_t&                 rcintvec_t;
  11 typedef intvec_t::const_iterator        intiter_t;
  12
  13 static void printint (int i)
  14 {
  15     cout.format ("%d ", i);
  16 }
  17
  18 static void PrintVector (rcintvec_t v)
  19 {
  20     cout << "{ ";
  21     foreach (intiter_t, i, v)
  22         printint (*i);
  23     cout << "}\n";
  24 }
  25
  26 static bool is_even (int i)
  27 {
  28     return (i % 2 == 0);
  29 }
  30
  31 static int sqr (int i)
  32 {
  33     return (i * i);
  34 }
  35
  36 static int genint (void)
  37 {
  38     static int counter = 0;
  39     return (counter++);
  40 }
  41
  42 // In its own function because compilers differ in selecting const/nonconst
  43 // members where no choice is needed.
  44 //
  45 static void TestEqualRange (rcintvec_t v)
  46 {
  47     pair<intiter_t,intiter_t> rv;
  48     rv = equal_range (v, 10);
  49     cout.format ("Range of  10 is { %2zd, %2zd }\n", abs_distance (v.begin(), rv.first), abs_distance (v.begin(), rv.second));
  50     rv = equal_range (v, 0);
  51     cout.format ("Range of   0 is { %2zd, %2zd }\n", abs_distance (v.begin(), rv.first), abs_distance (v.begin(), rv.second));
  52     rv = equal_range (v, 100);
  53     cout.format ("Range of 100 is { %2zd, %2zd }\n", abs_distance (v.begin(), rv.first), abs_distance (v.begin(), rv.second));
  54 }
  55
  56 template <typename T>
  57 void TestBigFill (const size_t size, const T magic)
  58 {
  59     vector<T> vbig (size);
  60     fill (vbig.begin() + 1, vbig.end(), magic);         // offset to test prealignment loop
  61     typename vector<T>::const_iterator iMismatch;
  62     iMismatch = find_if (vbig.begin() + 1, vbig.end(), bind1st (not_equal_to<T>(), magic));
  63     if (iMismatch == vbig.end())
  64         cout << "works\n";
  65     else
  66         cout.format ("does not work: mismatch at %zd, =0x%lX\n", abs_distance (vbig.begin(), iMismatch), (unsigned long)(*iMismatch));
  67 }
  68
  69 template <typename T>
  70 void TestBigCopy (const size_t size, const T magic)
  71 {
  72     vector<T> vbig1 (size), vbig2 (size);
  73     fill (vbig1, magic);
  74     copy (vbig1.begin() + 1, vbig1.end(), vbig2.begin() + 1);   // offset to test prealignment loop
  75     typedef typename vector<T>::const_iterator iter_t;
  76     pair<iter_t, iter_t> iMismatch;
  77     iMismatch = mismatch (vbig1.begin() + 1, vbig1.end(), vbig2.begin() + 1);
  78     assert (iMismatch.second <= vbig2.end());
  79     if (iMismatch.first == vbig1.end())
  80         cout << "works\n";
  81     else
  82         cout.format ("does not work: mismatch at %zd, 0x%lX != 0x%lX\n", abs_distance(vbig1.begin(), iMismatch.first), (unsigned long)(*iMismatch.first), (unsigned long)(*iMismatch.second));
  83 }
  84
  85 static void TestAlgorithms (void)
  86 {
  87     static const int c_TestNumbers[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 11, 12, 13, 13, 14, 15, 16, 17, 18 };
  88     const int* first = c_TestNumbers;
  89     const int* last = first + VectorSize(c_TestNumbers);
  90     intvec_t v, buf;
  91     v.assign (first, last);
  92     PrintVector (v);
  93
  94     cout << "swap(1,2)\n";
  95     swap (v[0], v[1]);
  96     PrintVector (v);
  97     v.assign (first, last);
  98
  99     cout << "copy(0,8,9)\n";
 100     copy (v.begin(), v.begin() + 8, v.begin() + 9);
 101     PrintVector (v);
 102     v.assign (first, last);
 103
 104     cout << "copy with back_inserter\n";
 105     v.clear();
 106     copy (first, last, back_inserter(v));
 107     PrintVector (v);
 108     v.assign (first, last);
 109
 110     cout << "copy with inserter\n";
 111     v.clear();
 112     copy (first, first + 5, inserter(v, v.begin()));
 113     copy (first, first + 5, inserter(v, v.begin() + 3));
 114     PrintVector (v);
 115     v.assign (first, last);
 116
 117     cout << "copy_n(0,8,9)\n";
 118     copy_n (v.begin(), 8, v.begin() + 9);
 119     PrintVector (v);
 120     v.assign (first, last);
 121
 122     cout << "copy_if(is_even)\n";
 123     intvec_t v_even;
 124     copy_if (v, back_inserter(v_even), &is_even);
 125     PrintVector (v_even);
 126     v.assign (first, last);
 127
 128     cout << "for_each(printint)\n{ ";
 129     for_each (v, &printint);
 130     cout << "}\n";
 131
 132     cout << "for_each(reverse_iterator, printint)\n{ ";
 133     for_each (v.rbegin(), v.rend(), &printint);
 134     cout << "}\n";
 135
 136     cout << "find(10)\n";
 137     cout.format ("10 found at offset %zd\n", abs_distance (v.begin(), find (v, 10)));
 138
 139     cout << "count(13)\n";
 140     cout.format ("%zu values of 13, %zu values of 18\n", count(v,13), count(v,18));
 141
 142     cout << "transform(sqr)\n";
 143     transform (v, &sqr);
 144     PrintVector (v);
 145     v.assign (first, last);
 146
 147     cout << "replace(13,666)\n";
 148     replace (v, 13, 666);
 149     PrintVector (v);
 150     v.assign (first, last);
 151
 152     cout << "fill(13)\n";
 153     fill (v, 13);
 154     PrintVector (v);
 155     v.assign (first, last);
 156
 157     cout << "fill_n(5, 13)\n";
 158     fill_n (v.begin(), 5, 13);
 159     PrintVector (v);
 160     v.assign (first, last);
 161
 162     cout << "fill 64083 uint8_t(0x41) ";
 163     TestBigFill<uint8_t> (64083, 0x41);
 164     cout << "fill 64083 uint16_t(0x4142) ";
 165     TestBigFill<uint16_t> (64083, 0x4142);
 166     cout << "fill 64083 uint32_t(0x41424344) ";
 167     TestBigFill<uint32_t> (64083, 0x41424344);
 168     cout << "fill 64083 float(0.4242) ";
 169     TestBigFill<float> (64083, 0x4242f);
 170 #ifdef HAVE_INT64_T
 171     cout << "fill 64083 uint64_t(0x4142434445464748) ";
 172     TestBigFill<uint64_t> (64083, UINT64_C(0x4142434445464748));
 173 #else
 174     cout << "No 64bit types available on this platform\n";
 175 #endif
 176
 177     cout << "copy 64083 uint8_t(0x41) ";
 178     TestBigCopy<uint8_t> (64083, 0x41);
 179     cout << "copy 64083 uint16_t(0x4142) ";
 180     TestBigCopy<uint16_t> (64083, 0x4142);
 181     cout << "copy 64083 uint32_t(0x41424344) ";
 182     TestBigCopy<uint32_t> (64083, 0x41424344);
 183     cout << "copy 64083 float(0.4242) ";
 184     TestBigCopy<float> (64083, 0.4242f);
 185 #ifdef HAVE_INT64_T
 186     cout << "copy 64083 uint64_t(0x4142434445464748) ";
 187     TestBigCopy<uint64_t> (64083, UINT64_C(0x4142434445464748));
 188 #else
 189     cout << "No 64bit types available on this platform\n";
 190 #endif
 191
 192     cout << "generate(genint)\n";
 193     generate (v, &genint);
 194     PrintVector (v);
 195     v.assign (first, last);
 196
 197     cout << "rotate(4)\n";
 198     rotate (v, 7);
 199     rotate (v, -3);
 200     PrintVector (v);
 201     v.assign (first, last);
 202
 203     cout << "merge with (3,5,10,11,11,14)\n";
 204     const int c_MergeWith[] = { 3,5,10,11,11,14 };
 205     intvec_t vmerged;
 206     merge (v.begin(), v.end(), VectorRange(c_MergeWith), back_inserter(vmerged));
 207     PrintVector (vmerged);
 208     v.assign (first, last);
 209
 210     cout << "inplace_merge with (3,5,10,11,11,14)\n";
 211     v.insert (v.end(), VectorRange(c_MergeWith));
 212     inplace_merge (v.begin(), v.end() - VectorSize(c_MergeWith), v.end());
 213     PrintVector (v);
 214     v.assign (first, last);
 215
 216     cout << "remove(13)\n";
 217     remove (v, 13);
 218     PrintVector (v);
 219     v.assign (first, last);
 220
 221     cout << "remove (elements 3, 4, 6, 15, and 45)\n";
 222     vector<uoff_t> toRemove;
 223     toRemove.push_back (3);
 224     toRemove.push_back (4);
 225     toRemove.push_back (6);
 226     toRemove.push_back (15);
 227     toRemove.push_back (45);
 228     typedef index_iterate<intvec_t::iterator, vector<uoff_t>::iterator> riiter_t;
 229     riiter_t rfirst = index_iterator (v.begin(), toRemove.begin());
 230     riiter_t rlast = index_iterator (v.begin(), toRemove.end());
 231     remove (v, rfirst, rlast);
 232     PrintVector (v);
 233     v.assign (first, last);
 234
 235     cout << "unique\n";
 236     unique (v);
 237     PrintVector (v);
 238     v.assign (first, last);
 239
 240     cout << "reverse\n";
 241     reverse (v);
 242     PrintVector (v);
 243     v.assign (first, last);
 244
 245     cout << "lower_bound(10)\n";
 246     PrintVector (v);
 247     cout.format ("10 begins at position %zd\n", abs_distance (v.begin(), lower_bound (v, 10)));
 248     v.assign (first, last);
 249
 250     cout << "upper_bound(10)\n";
 251     PrintVector (v);
 252     cout.format ("10 ends at position %zd\n", abs_distance (v.begin(), upper_bound (v, 10)));
 253     v.assign (first, last);
 254
 255     cout << "equal_range(10)\n";
 256     PrintVector (v);
 257     TestEqualRange (v);
 258     v.assign (first, last);
 259
 260     cout << "sort\n";
 261     reverse (v);
 262     PrintVector (v);
 263     random_shuffle (v);
 264     sort (v);
 265     PrintVector (v);
 266     v.assign (first, last);
 267
 268     cout << "stable_sort\n";
 269     reverse (v);
 270     PrintVector (v);
 271     random_shuffle (v);
 272     stable_sort (v);
 273     PrintVector (v);
 274     v.assign (first, last);
 275
 276     cout << "is_sorted\n";
 277     random_shuffle (v);
 278     const bool bNotSorted = is_sorted (v.begin(), v.end());
 279     sort (v);
 280     const bool bSorted = is_sorted (v.begin(), v.end());
 281     cout << "unsorted=" << bNotSorted << ", sorted=" << bSorted << endl;
 282     v.assign (first, last);
 283
 284     cout << "find_first_of\n";
 285     static const int c_FFO[] = { 10000, -34, 14, 27 };
 286     cout.format ("found 14 at position %zd\n", abs_distance (v.begin(), find_first_of (v.begin(), v.end(), VectorRange(c_FFO))));
 287     v.assign (first, last);
 288
 289     static const int LC1[] = { 3, 1, 4, 1, 5, 9, 3 };
 290     static const int LC2[] = { 3, 1, 4, 2, 8, 5, 7 };
 291     static const int LC3[] = { 1, 2, 3, 4 };
 292     static const int LC4[] = { 1, 2, 3, 4, 5 };
 293     cout << "lexicographical_compare";
 294     cout << "\nLC1 < LC2 == " << lexicographical_compare (VectorRange(LC1), VectorRange(LC2));
 295     cout << "\nLC2 < LC2 == " << lexicographical_compare (VectorRange(LC2), VectorRange(LC2));
 296     cout << "\nLC3 < LC4 == " << lexicographical_compare (VectorRange(LC3), VectorRange(LC4));
 297     cout << "\nLC4 < LC1 == " << lexicographical_compare (VectorRange(LC4), VectorRange(LC1));
 298     cout << "\nLC1 < LC4 == " << lexicographical_compare (VectorRange(LC1), VectorRange(LC4));
 299
 300     cout << "\nmax_element\n";
 301     cout.format ("max element is %d\n", *max_element (v.begin(), v.end()));
 302     v.assign (first, last);
 303
 304     cout << "min_element\n";
 305     cout.format ("min element is %d\n", *min_element (v.begin(), v.end()));
 306     v.assign (first, last);
 307
 308     cout << "partial_sort\n";
 309     reverse (v);
 310     partial_sort (v.begin(), v.iat(v.size() / 2), v.end());
 311     PrintVector (v);
 312     v.assign (first, last);
 313
 314     cout << "partial_sort_copy\n";
 315     reverse (v);
 316     buf.resize (v.size());
 317     partial_sort_copy (v.begin(), v.end(), buf.begin(), buf.end());
 318     PrintVector (buf);
 319     v.assign (first, last);
 320
 321     cout << "partition\n";
 322     partition (v.begin(), v.end(), &is_even);
 323     PrintVector (v);
 324     v.assign (first, last);
 325
 326     cout << "stable_partition\n";
 327     stable_partition (v.begin(), v.end(), &is_even);
 328     PrintVector (v);
 329     v.assign (first, last);
 330
 331     cout << "next_permutation\n";
 332     buf.resize (3);
 333     iota (buf.begin(), buf.end(), 1);
 334     PrintVector (buf);
 335     while (next_permutation (buf.begin(), buf.end()))
 336         PrintVector (buf);
 337     cout << "prev_permutation\n";
 338     reverse (buf);
 339     PrintVector (buf);
 340     while (prev_permutation (buf.begin(), buf.end()))
 341         PrintVector (buf);
 342     v.assign (first, last);
 343
 344     cout << "reverse_copy\n";
 345     buf.resize (v.size());
 346     reverse_copy (v.begin(), v.end(), buf.begin());
 347     PrintVector (buf);
 348     v.assign (first, last);
 349
 350     cout << "rotate_copy\n";
 351     buf.resize (v.size());
 352     rotate_copy (v.begin(), v.iat (v.size() / 3), v.end(), buf.begin());
 353     PrintVector (buf);
 354     v.assign (first, last);
 355
 356     static const int c_Search1[] = { 5, 6, 7, 8, 9 }, c_Search2[] = { 10, 10, 11, 14 };
 357     cout << "search\n";
 358     cout.format ("{5,6,7,8,9} at %zd\n", abs_distance (v.begin(), search (v.begin(), v.end(), VectorRange(c_Search1))));
 359     cout.format ("{10,10,11,14} at %zd\n", abs_distance (v.begin(), search (v.begin(), v.end(), VectorRange(c_Search2))));
 360     cout << "find_end\n";
 361     cout.format ("{5,6,7,8,9} at %zd\n", abs_distance (v.begin(), find_end (v.begin(), v.end(), VectorRange(c_Search1))));
 362     cout.format ("{10,10,11,14} at %zd\n", abs_distance (v.begin(), find_end (v.begin(), v.end(), VectorRange(c_Search2))));
 363     cout << "search_n\n";
 364     cout.format ("{14} at %zd\n", abs_distance (v.begin(), search_n (v.begin(), v.end(), 1, 14)));
 365     cout.format ("{13,13} at %zd\n", abs_distance (v.begin(), search_n (v.begin(), v.end(), 2, 13)));
 366     cout.format ("{10,10,10} at %zd\n", abs_distance (v.begin(), search_n (v.begin(), v.end(), 3, 10)));
 367     v.assign (first, last);
 368
 369     cout << "includes\n";
 370     static const int c_Includes[] = { 5, 14, 15, 18, 20 };
 371     cout << "includes=" << includes (v.begin(), v.end(), VectorRange(c_Includes)-1);
 372     cout << ", not includes=" << includes (v.begin(), v.end(), VectorRange(c_Includes));
 373     cout << endl;
 374
 375     static const int c_Set1[] = { 1, 2, 3, 4, 5, 6 }, c_Set2[] = { 4, 4, 6, 7, 8 };
 376     intvec_t::iterator setEnd;
 377     cout << "set_difference\n";
 378     v.resize (4);
 379     setEnd = set_difference (VectorRange(c_Set1), VectorRange(c_Set2), v.begin());
 380     PrintVector (v);
 381     assert (setEnd == v.end());
 382     cout << "set_symmetric_difference\n";
 383     v.resize (7);
 384     setEnd = set_symmetric_difference (VectorRange(c_Set1), VectorRange(c_Set2), v.begin());
 385     PrintVector (v);
 386     assert (setEnd == v.end());
 387     cout << "set_intersection\n";
 388     v.resize (2);
 389     setEnd = set_intersection (VectorRange(c_Set1), VectorRange(c_Set2), v.begin());
 390     PrintVector (v);
 391     assert (setEnd == v.end());
 392     cout << "set_union\n";
 393     v.resize (9);
 394     setEnd = set_union (VectorRange(c_Set1), VectorRange(c_Set2), v.begin());
 395     PrintVector (v);
 396     assert (setEnd == v.end());
 397     v.assign (first, last);
 398 }
 399
 400 StdBvtMain (TestAlgorithms)
 401