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