ReactOS  0.4.13-dev-100-gc8611ae
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 //
37 struct SortBuffer
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.
48  void PrepareMerge()
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  {
58  PrepareMerge();
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 
68 private:
70 };
71 
72 //
73 // less_by_reference -- a functor for comparing objects against a
74 // constant value.
75 //
76 template <class T>
78 {
79  less_by_reference( const T& arg ) : fArg(arg) {}
80  bool operator()( const T& x ) const { return x < fArg; }
81 private:
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 
134 private:
135  const SortBuffer& orig;
137 };
138 
139 void 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 ====================================================================================*/
146 void assert_sorted_version( const SortBuffer& orig, const SortBuffer& buf )
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 
192 private:
193  const SortBuffer& orig;
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 
209 private:
210  const SortBuffer& orig;
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 
226 private:
227  const SortBuffer& orig;
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 
244 private:
245  const SortBuffer& orig;
246 };
247 
248 void test_algo()
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 
257  SortBuffer buf;
261 }
SortClass partitionPoint
Definition: test_algo.cpp:136
test_stable_partition(const SortBuffer &buf)
Definition: test_algo.cpp:87
GLenum GLuint GLenum GLsizei const GLchar * buf
Definition: glext.h:7751
const SortClass * begin() const
Definition: test_algo.cpp:42
_STLP_MOVE_TO_STD_NAMESPACE void sort(_RandomAccessIter __first, _RandomAccessIter __last)
Definition: _algo.c:993
TestController gTestController
Definition: nc_alloc.cpp:46
void WeakCheck(const Value &v, const Operation &op, long max_iters=2000000)
Definition: LeakCheck.h:65
const SortBuffer & orig
Definition: test_algo.cpp:227
GLint GLint GLint GLint GLint x
Definition: gl.h:1548
bool operator()(const T &x) const
Definition: test_algo.cpp:80
const SortBuffer & orig
Definition: test_algo.cpp:135
void operator()(SortBuffer &buf) const
Definition: test_algo.cpp:186
#define cmp(status, error)
Definition: error.c:114
static void SetCurrentTestName(const char *str)
Definition: nc_alloc.h:172
const T & fArg
Definition: test_algo.cpp:82
const SortBuffer & orig
Definition: test_algo.cpp:210
#define T
Definition: mbstring.h:31
_STLP_MOVE_TO_STD_NAMESPACE void inplace_merge(_BidirectionalIter __first, _BidirectionalIter __middle, _BidirectionalIter __last)
Definition: _algo.c:1553
_STLP_MOVE_TO_STD_NAMESPACE void stable_sort(_RandomAccessIter __first, _RandomAccessIter __last)
Definition: _algo.c:1197
test_stable_sort_1(const SortBuffer &buf)
Definition: test_algo.cpp:181
SortClass items[kBufferSize]
Definition: test_algo.cpp:69
basic_ostream< _CharT, _Traits > &_STLP_CALL endl(basic_ostream< _CharT, _Traits > &__os)
Definition: _ostream.h:357
test_stable_sort_2(const SortBuffer &buf)
Definition: test_algo.cpp:198
test_inplace_merge_2(SortBuffer &buf)
Definition: test_algo.cpp:232
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
const SortClass * end() const
Definition: test_algo.cpp:44
#define d
Definition: ke_i.h:81
_STLP_DECLSPEC _Stl_aligned_buffer< ostream > cerr
Definition: iostream.cpp:102
GLdouble GLdouble GLdouble GLdouble q
Definition: gl.h:2063
less_by_reference(const T &arg)
Definition: test_algo.cpp:79
#define EH_ASSERT
Definition: Prefix.h:37
void operator()(SortBuffer &buf) const
Definition: test_algo.cpp:220
void assert_sorted_version(const SortBuffer &orig, const SortBuffer &buf)
Definition: test_algo.cpp:146
const SortBuffer & orig
Definition: test_algo.cpp:245
_STLP_MOVE_TO_STD_NAMESPACE void fill_n(_OutputIter __first, _Size __n, const _Tp &__val)
Definition: _algobase.h:511
void operator()(SortBuffer &buf) const
Definition: test_algo.cpp:92
void PrepareMerge()
Definition: test_algo.cpp:48
void operator()(SortBuffer &buf) const
Definition: test_algo.cpp:237
_STLP_MOVE_TO_STD_NAMESPACE _ForwardIter stable_partition(_ForwardIter __first, _ForwardIter __last, _Predicate __pred)
Definition: _algo.c:866
void test_algo()
Definition: test_algo.cpp:248
SortClass * end()
Definition: test_algo.cpp:43
void operator()(SortBuffer &buf) const
Definition: test_algo.cpp:203
const SortBuffer & orig
Definition: test_algo.cpp:193
SortBuffer(const SortBuffer &rhs)
Definition: test_algo.cpp:61
static void CancelFailureCountdown()
Definition: nc_alloc.h:143
GLfloat GLfloat p
Definition: glext.h:8902
SortClass * begin()
Definition: test_algo.cpp:41
test_inplace_merge_1(SortBuffer &buf)
Definition: test_algo.cpp:215