libstdc++-v3/testsuite/25_algorithms/sort.cc

   1 // Copyright (C) 2001 Free Software Foundation, Inc.
   2 //
   3 // This file is part of the GNU ISO C++ Library.  This library is free
   4 // software; you can redistribute it and/or modify it under the
   5 // terms of the GNU General Public License as published by the
   6 // Free Software Foundation; either version 2, or (at your option)
   7 // any later version.
   8
   9 // This library is distributed in the hope that it will be useful,
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 // GNU General Public License for more details.
  13
  14 // You should have received a copy of the GNU General Public License along
  15 // with this library; see the file COPYING.  If not, write to the Free
  16 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  17 // USA.
  18
  19 // 25.3.1 algorithms, sort()
  20
  21 #include <algorithm>
  22 #include <testsuite_hooks.h>
  23
  24 bool test __attribute__((unused)) = true;
  25
  26 const int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20};
  27 const int B[] = {10, 20, 1, 11, 2, 12, 3, 13, 4, 14, 5, 15, 6, 16, 7, 17, 8, 18, 9, 19};
  28 const int C[] = {20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  29 const int N = sizeof(A) / sizeof(int);
  30 const int logN = 3; // ln(N) rounded up
  31 const int P = 7;
  32
  33 // comparison predicate for stable_sort: order by rightmost digit
  34 struct CompLast
  35 {
  36     bool
  37     operator()(const int x, const int y)
  38     { return x % 10 < y % 10; }
  39 };
  40
  41 // This functor has the equivalent functionality of std::geater<>,
  42 // but there is no dependency on <functional> and it also tracks the
  43 // number of invocations since creation.
  44 class Gt
  45 {
  46 public:
  47     static int count() { return itsCount; }
  48     static void reset() { itsCount = 0; }
  49
  50     bool
  51     operator()(const int& x, const int& y)
  52     {
  53         ++itsCount;
  54         return x > y;
  55     }
  56
  57 private:
  58     static int itsCount;
  59 };
  60
  61 int Gt::itsCount = 0;
  62
  63
  64 // 25.3.1.1 sort()
  65 void
  66 test01()
  67 {
  68     int s1[N];
  69     std::copy(B, B + N, s1);
  70     VERIFY(std::equal(s1, s1 + N, B));
  71
  72     std::sort(s1, s1 + N);
  73     VERIFY(std::equal(s1, s1 + N, A));
  74
  75     Gt gt;
  76     gt.reset();
  77     std::sort(s1, s1 + N, gt);
  78     VERIFY(std::equal(s1, s1 + N, C));
  79 }
  80
  81 // 25.3.1.2 stable_sort()
  82 void
  83 test02()
  84 {
  85     int s1[N];
  86     std::copy(A, A + N, s1);
  87     VERIFY(std::equal(s1, s1 + N, A));
  88
  89     std::stable_sort(s1, s1 + N, CompLast());
  90     VERIFY(std::equal(s1, s1 + N, B));
  91
  92     std::stable_sort(s1, s1 + N);
  93     VERIFY(std::equal(s1, s1 + N, A));
  94
  95     Gt gt;
  96     gt.reset();
  97     std::stable_sort(s1, s1 + N, gt);
  98     VERIFY(std::equal(s1, s1 + N, C));
  99     VERIFY(gt.count() <= N * logN * logN);
 100 }
 101
 102 // 25.3.1.3 partial_sort()
 103 void
 104 test03()
 105 {
 106     int s1[N];
 107     std::copy(B, B + N, s1);
 108     VERIFY(std::equal(s1, s1 + N, B));
 109
 110     std::partial_sort(s1, s1 + P, s1 + N);
 111     VERIFY(std::equal(s1, s1 + P, A));
 112
 113     Gt gt;
 114     gt.reset();
 115     std::partial_sort(s1, s1 + P, s1 + N, gt);
 116     VERIFY(std::equal(s1, s1 + P, C));
 117 }
 118
 119 // 25.3.1.4 partial_sort_copy()
 120 void
 121 test04()
 122 {
 123     using std::partial_sort_copy;
 124
 125     int s1[N];
 126     std::copy(B, B + N, s1);
 127     VERIFY(std::equal(s1, s1 + N, B));
 128
 129     int s2[2*N];
 130
 131     partial_sort_copy(s1, s1 + N, s2, s2 + P);
 132     VERIFY(std::equal(s2, s2 + P, A));
 133
 134     Gt gt;
 135     gt.reset();
 136     partial_sort_copy(s1, s1 + N, s2, s2 + P, gt);
 137     VERIFY(std::equal(s2, s2 + P, C));
 138
 139     VERIFY(std::equal(s2, partial_sort_copy(s1, s1 + N, s2, s2 + 2*N), A));
 140 }
 141
 142 // 25.3.2 nth_element()
 143 void
 144 test05()
 145 {
 146     using std::nth_element;
 147
 148     int s1[N];
 149     std::copy(B, B + N, s1);
 150     VERIFY(std::equal(s1, s1 + N, B));
 151
 152     int* pn = s1 + (N / 2) - 1;
 153     nth_element(s1, pn, s1 + N);
 154     for (const int* i = pn; i < s1 + N; ++i) VERIFY(!(*i < *pn));
 155
 156     CompLast pred;
 157     nth_element(s1, pn, s1 + N, pred);
 158     for (const int* i = pn; i < s1 + N; ++i) VERIFY(!pred(*i, *pn));
 159 }
 160
 161 int
 162 main()
 163 {
 164   test01();
 165   test02();
 166   test03();
 167   test04();
 168   test05();
 169
 170   return 0;
 171 }