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)
10 using namespace std;
11 #endif
12 
13 //
14 // TestCase class
15 //
16 class 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 
25 protected:
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 
49 CPPUNIT_TEST_SUITE_REGISTRATION(PartitionTest);
50 
51 //
52 // tests implementation
53 //
54 void 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 }
71 void 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 }
93 void 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 }
108 void 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