1#include <algorithm>
2#include <vector>
3#include <cstdlib>
4#include <iterator>
5#include <functional>
6
7#include "cppunit/cppunit_proxy.h"
8
9#if !defined (STLPORT) || defined(_STLP_USE_NAMESPACES)
10using namespace std;
11#endif
12
13//
14// TestCase class
15//
16class PartitionTest : public CPPUNIT_NS::TestCase
17{
18  CPPUNIT_TEST_SUITE(PartitionTest);
19  CPPUNIT_TEST(ptition0);
20  CPPUNIT_TEST(ptition1);
21  CPPUNIT_TEST(stblptn0);
22  CPPUNIT_TEST(stblptn1);
23  CPPUNIT_TEST_SUITE_END();
24
25protected:
26  void ptition0();
27  void ptition1();
28  void stblptn0();
29  void stblptn1();
30
31  struct less_n {
32    less_n(int limit, size_t &nb_calls)
33      : _limit(limit), _nb_calls(nb_calls) {}
34
35    bool operator() (int a_) const {
36      ++_nb_calls;
37      return a_ < _limit;
38    }
39
40    int _limit;
41    size_t &_nb_calls;
42
43  private:
44    //explicitely defined as private to avoid warnings:
45    less_n& operator = (less_n const&);
46  };
47};
48
49CPPUNIT_TEST_SUITE_REGISTRATION(PartitionTest);
50
51//
52// tests implementation
53//
54void PartitionTest::stblptn0()
55{
56  int numbers[6] = { 10, 5, 11, 20, 6, -2 };
57
58  size_t nb_pred_calls = 0;
59  stable_partition((int*)numbers, (int*)numbers + 6, less_n(10, nb_pred_calls));
60  // 5 6 -2 10 11 20
61  CPPUNIT_ASSERT(numbers[0]==5);
62  CPPUNIT_ASSERT(numbers[1]==6);
63  CPPUNIT_ASSERT(numbers[2]==-2);
64  CPPUNIT_ASSERT(numbers[3]==10);
65  CPPUNIT_ASSERT(numbers[4]==11);
66  CPPUNIT_ASSERT(numbers[5]==20);
67
68  //Complexity check:
69  CPPUNIT_ASSERT( nb_pred_calls == sizeof(numbers) / sizeof(numbers[0]) );
70}
71void PartitionTest::stblptn1()
72{
73  //5 5 2 10 0 12 5 0 0 19
74  //5 5 2 10 0 5 0 0 12 19
75  int numbers[] = { 5, 5, 2, 10, 0, 12, 5, 0, 0, 19 };
76  vector <int> v1(numbers, numbers+10);
77
78  size_t nb_pred_calls = 0;
79  stable_partition(v1.begin(), v1.end(), less_n(11, nb_pred_calls));
80
81  CPPUNIT_ASSERT(v1[0]==5);
82  CPPUNIT_ASSERT(v1[1]==5);
83  CPPUNIT_ASSERT(v1[2]==2);
84  CPPUNIT_ASSERT(v1[3]==10);
85  CPPUNIT_ASSERT(v1[4]==0);
86  CPPUNIT_ASSERT(v1[5]==5);
87  CPPUNIT_ASSERT(v1[6]==0);
88  CPPUNIT_ASSERT(v1[7]==0);
89  CPPUNIT_ASSERT(v1[8]==12);
90  CPPUNIT_ASSERT(v1[9]==19);
91  CPPUNIT_ASSERT( nb_pred_calls == v1.size() );
92}
93void PartitionTest::ptition0()
94{
95  int numbers[6] = { 6, 12, 3, 10, 1, 20 };
96  size_t nb_pred_calls = 0;
97  // 6 1 3 10 12 20
98  partition((int*)numbers, (int*)numbers + 6, less_n(10, nb_pred_calls));
99  CPPUNIT_ASSERT(numbers[0]==6);
100  CPPUNIT_ASSERT(numbers[1]==1);
101  CPPUNIT_ASSERT(numbers[2]==3);
102  CPPUNIT_ASSERT(numbers[3]==10);
103  CPPUNIT_ASSERT(numbers[4]==12);
104  CPPUNIT_ASSERT(numbers[5]==20);
105
106  CPPUNIT_ASSERT( nb_pred_calls == sizeof(numbers) / sizeof(numbers[0]) );
107}
108void PartitionTest::ptition1()
109{
110  // 19 3 11 14 10 19 8 17 9 6
111  // 6 3 9 8 10 19 14 17 11 19
112
113  int numbers[10] ={ 19, 3, 11, 14, 10, 19, 8, 17, 9, 6 };
114
115  vector <int> v1(numbers, numbers+10);
116  size_t nb_pred_calls = 0;
117  partition(v1.begin(), v1.end(), less_n(11, nb_pred_calls));
118
119  CPPUNIT_ASSERT(v1[0]==6);
120  CPPUNIT_ASSERT(v1[1]==3);
121  CPPUNIT_ASSERT(v1[2]==9);
122  CPPUNIT_ASSERT(v1[3]==8);
123  CPPUNIT_ASSERT(v1[4]==10);
124  CPPUNIT_ASSERT(v1[5]==19);
125  CPPUNIT_ASSERT(v1[6]==14);
126  CPPUNIT_ASSERT(v1[7]==17);
127  CPPUNIT_ASSERT(v1[8]==11);
128  CPPUNIT_ASSERT(v1[9]==19);
129  CPPUNIT_ASSERT( nb_pred_calls == v1.size() );
130}
131