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//
37struct 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
56  SortBuffer()
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
68private:
69    SortClass items[kBufferSize];
70};
71
72//
73// less_by_reference -- a functor for comparing objects against a
74//   constant value.
75//
76template <class T>
77struct less_by_reference
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
85struct test_stable_partition
86{
87    test_stable_partition( const SortBuffer& buf )
88        : orig( buf ), partitionPoint(SortClass::kRange / 2) {
89        gTestController.SetCurrentTestName("stable_partition()");
90        }
91
92    void operator()( SortBuffer& buf ) const
93    {
94        less_by_reference<SortClass> throw_cmp( partitionPoint );
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.
103        gTestController.CancelFailureCountdown();
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
112        less_by_reference<TestClass> cmp( partitionPoint );
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:
135    const SortBuffer& orig;
136    SortClass partitionPoint;
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====================================================================================*/
146void assert_sorted_version( const SortBuffer& orig, const SortBuffer& buf )
147{
148  // Stop any potential failures that might occur during verification.
149    gTestController.CancelFailureCountdown();
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//
179struct test_stable_sort_1
180{
181    test_stable_sort_1( const SortBuffer& buf )
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() );
189        assert_sorted_version( orig, buf );
190    }
191
192private:
193    const SortBuffer& orig;
194};
195
196struct test_stable_sort_2
197{
198    test_stable_sort_2( const SortBuffer& buf )
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>() );
206      assert_sorted_version( orig, buf );
207    }
208
209private:
210    const SortBuffer& orig;
211};
212
213struct test_inplace_merge_1
214{
215    test_inplace_merge_1( SortBuffer& buf )
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() );
223        assert_sorted_version( orig, buf );
224    }
225
226private:
227    const SortBuffer& orig;
228};
229
230struct test_inplace_merge_2
231{
232    test_inplace_merge_2( SortBuffer& buf )
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>() );
241        assert_sorted_version( orig, buf );
242    }
243
244private:
245    const SortBuffer& orig;
246};
247
248void 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;
258    WeakCheck( buf, test_stable_sort_1( buf ) );
259    WeakCheck( buf, test_stable_sort_2( buf ) );
260    WeakCheck( buf, test_stable_partition( buf ) );
261}
262