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