ReactOS 0.4.16-dev-297-gc569aee
test_algo.cpp
Go to the documentation of this file.
1/***********************************************************************************
2 test_algo.cpp
3
4 * Copyright (c) 1997
5 * Mark of the Unicorn, Inc.
6 *
7 * Permission to use, copy, modify, distribute and sell this software
8 * and its documentation for any purpose is hereby granted without fee,
9 * provided that the above copyright notice appear in all copies and
10 * that both that copyright notice and this permission notice appear
11 * in supporting documentation. Mark of the Unicorn makes no
12 * representations about the suitability of this software for any
13 * purpose. It is provided "as is" without express or implied warranty.
14
15***********************************************************************************/
16#include "Tests.h"
17#include "LeakCheck.h"
18#include "SortClass.h"
19
20#if defined (EH_NEW_HEADERS)
21# include <algorithm>
22# include <cassert>
23#else
24# include <algo.h>
25# include <assert.h>
26#endif
27
28#if defined (EH_NEW_IOSTREAMS)
29# include <iostream>
30#else
31# include <iostream.h>
32#endif
33
34//
35// SortBuffer -- a buffer of SortClass objects that can be used to test sorting.
36//
38{
39 enum { kBufferSize = 100 };
40
41 SortClass* begin() { return items; }
42 const SortClass* begin() const { return items; }
43 SortClass* end() { return items + kBufferSize; }
44 const SortClass* end() const { return items + kBufferSize; }
45
46 // Sort each half of the buffer and reset the address of each element
47 // so that merge() can be tested for stability.
49 {
50 EH_STD::sort( begin(), begin() + ( end() - begin() )/2 );
51 EH_STD::sort( begin() + ( end() - begin() )/2, end() );
52 for ( SortClass* p = begin(); p != end(); p++ )
53 p->ResetAddress();
54 }
55
57 {
59 }
60
61 SortBuffer( const SortBuffer& rhs )
62 {
63 SortClass* q = begin();
64 for ( const SortClass* p = rhs.begin() ; p != rhs.end(); p++,q++ )
65 *q = *p;
66 }
67
68private:
70};
71
72//
73// less_by_reference -- a functor for comparing objects against a
74// constant value.
75//
76template <class T>
78{
79 less_by_reference( const T& arg ) : fArg(arg) {}
80 bool operator()( const T& x ) const { return x < fArg; }
81private:
82 const T& fArg;
83};
84
86{
88 : orig( buf ), partitionPoint(SortClass::kRange / 2) {
89 gTestController.SetCurrentTestName("stable_partition()");
90 }
91
92 void operator()( SortBuffer& buf ) const
93 {
95
96 SortClass* d = EH_STD::stable_partition( buf.begin(), buf.end(), throw_cmp );
97
98 // Suppress warning about unused variable.
99 d;
100
101 // If we get here no exception occurred during the operation.
102 // Stop any potential failures that might occur during verification.
104
105 // Prepare an array of counts of the occurrence of each value in
106 // the legal range.
107 unsigned counts[SortClass::kRange];
108 EH_STD::fill_n( counts, (int)SortClass::kRange, 0 );
109 for ( const SortClass *q = orig.begin(); q != orig.end(); q++ )
110 counts[ q->value() ]++;
111
113 for ( const SortClass* p = buf.begin(); p != buf.end(); p++ )
114 {
115 // Check that adjacent items with the same value haven't been
116 // reordered. This could be a more thorough test.
117 if ( p != buf.begin() && p->value() == p[-1].value() ) {
118 EH_ASSERT( p->GetAddress() > p[-1].GetAddress() );
119 }
120
121 // Check that the partitioning worked.
122 EH_ASSERT( (p < d) == cmp( *p ) );
123
124 // Decrement the appropriate count for each value.
125 counts[ p->value() ]--;
126 }
127
128 // Check that the values were only rearranged, and none were lost.
129 for ( unsigned j = 0; j < SortClass::kRange; j++ ) {
130 EH_ASSERT( counts[j] == 0 );
131 }
132 }
133
134private:
137};
138
139void assert_sorted_version( const SortBuffer& orig, const SortBuffer& buf );
140
141/*===================================================================================
142 assert_sorted_version
143
144 EFFECTS: Asserts that buf is a stable-sorted version of orig.
145====================================================================================*/
147{
148 // Stop any potential failures that might occur during verification.
150
151 // Prepare an array of counts of the occurrence of each value in
152 // the legal range.
153 unsigned counts[SortClass::kRange];
154 EH_STD::fill_n( counts, (int)SortClass::kRange, 0 );
155 for ( const SortClass *q = orig.begin(); q != orig.end(); q++ )
156 counts[ q->value() ]++;
157
158 // Check that each element is greater than the previous one, or if they are
159 // equal, that their order has been preserved.
160 for ( const SortClass* p = buf.begin(); p != buf.end(); p++ )
161 {
162 if ( p != buf.begin() ) {
163 EH_ASSERT( p->value() > p[-1].value()
164 || p->value() == p[-1].value() && p->GetAddress() > p[-1].GetAddress() );
165 }
166 // Decrement the appropriate count for each value.
167 counts[ p->value() ]--;
168 }
169
170 // Check that the values were only rearranged, and none were lost.
171 for ( unsigned j = 0; j < SortClass::kRange; j++ ) {
172 EH_ASSERT( counts[j] == 0 );
173 }
174}
175
176//
177// The test operators
178//
180{
182 : orig( buf ) {
183 gTestController.SetCurrentTestName("stable_sort() #1");
184 }
185
186 void operator()( SortBuffer& buf ) const
187 {
188 EH_STD::stable_sort( buf.begin(), buf.end() );
190 }
191
192private:
194};
195
197{
199 : orig( buf ) {
200 gTestController.SetCurrentTestName("stable_sort() #2");
201 }
202
203 void operator()( SortBuffer& buf ) const
204 {
205 EH_STD::stable_sort( buf.begin(), buf.end(), EH_STD::less<SortClass>() );
207 }
208
209private:
211};
212
214{
216 : orig( buf ) {
217 gTestController.SetCurrentTestName("inplace_merge #1()");
218 }
219
220 void operator()( SortBuffer& buf ) const
221 {
222 EH_STD::inplace_merge( buf.begin(), buf.begin() + ( buf.end() - buf.begin() )/2, buf.end() );
224 }
225
226private:
228};
229
231{
233 : orig( buf ) {
234 gTestController.SetCurrentTestName("inplace_merge() #2");
235 }
236
237 void operator()( SortBuffer& buf ) const
238 {
239 EH_STD::inplace_merge( buf.begin(), buf.begin() + ( buf.end() - buf.begin() )/2, buf.end(),
240 EH_STD::less<SortClass>() );
242 }
243
244private:
246};
247
249{
250 SortBuffer mergeBuf;
251 mergeBuf.PrepareMerge();
252
253 EH_STD::cerr<<"EH test : testing algo.h"<<EH_STD::endl;
254 WeakCheck( mergeBuf, test_inplace_merge_1( mergeBuf ) );
255 WeakCheck( mergeBuf, test_inplace_merge_2( mergeBuf ) );
256
261}
void WeakCheck(const Value &v, const Operation &op, long max_iters=2000000)
Definition: LeakCheck.h:65
#define EH_ASSERT
Definition: Prefix.h:37
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
GLdouble GLdouble GLdouble GLdouble q
Definition: gl.h:2063
GLenum GLuint GLenum GLsizei const GLchar * buf
Definition: glext.h:7751
GLfloat GLfloat p
Definition: glext.h:8902
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint GLint GLint j
Definition: glfuncs.h:250
#define d
Definition: ke_i.h:81
#define T
Definition: mbstring.h:31
#define cmp(status, error)
Definition: error.c:114
TestController gTestController
Definition: nc_alloc.cpp:46
SortClass * end()
Definition: test_algo.cpp:43
const SortClass * begin() const
Definition: test_algo.cpp:42
SortClass * begin()
Definition: test_algo.cpp:41
void PrepareMerge()
Definition: test_algo.cpp:48
const SortClass * end() const
Definition: test_algo.cpp:44
SortClass items[kBufferSize]
Definition: test_algo.cpp:69
SortBuffer(const SortBuffer &rhs)
Definition: test_algo.cpp:61
static void SetCurrentTestName(const char *str)
Definition: nc_alloc.h:172
static void CancelFailureCountdown()
Definition: nc_alloc.h:143
less_by_reference(const T &arg)
Definition: test_algo.cpp:79
const T & fArg
Definition: test_algo.cpp:82
bool operator()(const T &x) const
Definition: test_algo.cpp:80
test_inplace_merge_1(SortBuffer &buf)
Definition: test_algo.cpp:215
const SortBuffer & orig
Definition: test_algo.cpp:227
void operator()(SortBuffer &buf) const
Definition: test_algo.cpp:220
test_inplace_merge_2(SortBuffer &buf)
Definition: test_algo.cpp:232
const SortBuffer & orig
Definition: test_algo.cpp:245
void operator()(SortBuffer &buf) const
Definition: test_algo.cpp:237
const SortBuffer & orig
Definition: test_algo.cpp:135
void operator()(SortBuffer &buf) const
Definition: test_algo.cpp:92
SortClass partitionPoint
Definition: test_algo.cpp:136
test_stable_partition(const SortBuffer &buf)
Definition: test_algo.cpp:87
const SortBuffer & orig
Definition: test_algo.cpp:193
void operator()(SortBuffer &buf) const
Definition: test_algo.cpp:186
test_stable_sort_1(const SortBuffer &buf)
Definition: test_algo.cpp:181
void operator()(SortBuffer &buf) const
Definition: test_algo.cpp:203
test_stable_sort_2(const SortBuffer &buf)
Definition: test_algo.cpp:198
const SortBuffer & orig
Definition: test_algo.cpp:210
void test_algo()
Definition: test_algo.cpp:248
void assert_sorted_version(const SortBuffer &orig, const SortBuffer &buf)
Definition: test_algo.cpp:146