]>
Commit | Line | Data |
---|---|---|
02d92e3b SW |
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, 59 Temple Place - Suite 330, Boston, MA 02111-1307, | |
17 | // USA. | |
18 | ||
19 | // 25.3.1 algorithms, sort() | |
20 | ||
21 | #include <algorithm> | |
fe413112 | 22 | #include <testsuite_hooks.h> |
02d92e3b SW |
23 | |
24 | bool test = 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(int argc, char* argv[]) | |
163 | { | |
164 | test01(); | |
165 | test02(); | |
166 | test03(); | |
167 | test04(); | |
168 | test05(); | |
169 | ||
170 | return !test; | |
171 | } |