3 #ifndef CDSHDRTEST_PQUEUE_H
4 #define CDSHDRTEST_PQUEUE_H
6 #include "cppunit/cppunit_proxy.h"
7 #include "size_check.h"
9 #include <functional> // ref
11 namespace priority_queue {
14 static size_t const c_nCapacity = 1024 * 16;
30 template <typename PQueue>
32 static size_t const nCapacity = c_nCapacity;
36 class PQueueHdrTest: public CppUnitMini::TestCase
39 static size_t const c_nCapacity = pqueue::c_nCapacity;
42 static key_type const c_nMinValue = -123;
51 value_type( value_type const& kv )
56 value_type( key_type key )
61 value_type( key_type key, int val )
66 value_type( std::pair<key_type, int> const& p )
73 int operator()( value_type k1, value_type k2 ) const
80 bool operator()( value_type k1, value_type k2 ) const
93 data_array( size_t nSize )
94 : pFirst( new T[nSize] )
95 , pLast( pFirst + nSize )
97 key_type i = c_nMinValue;
98 for ( T * p = pFirst; p != pLast; ++p, ++i )
101 std::random_shuffle( pFirst, pLast );
109 T * begin() { return pFirst; }
110 T * end() { return pLast ; }
113 return pLast - pFirst;
118 template <class PQueue>
119 void test_bounded_with( PQueue& pq )
121 data_array<value_type> arr( pq.capacity() );
122 value_type * pFirst = arr.begin();
123 value_type * pLast = pFirst + pq.capacity();
125 CPPUNIT_ASSERT( pq.empty() );
126 CPPUNIT_ASSERT( pq.size() == 0 );
127 CPPUNIT_ASSERT_EX( pq.capacity() == pqueue::constants<PQueue>::nCapacity,
128 "pq.capacity() = " << pq.capacity() << ", pqueue::constants<PQueue>::nCapacity = " << pqueue::constants<PQueue>::nCapacity
134 for ( value_type * p = pFirst; p < pLast; ++p ) {
135 switch ( pq.size() & 3 ) {
137 CPPUNIT_ASSERT( pq.push_with( [p]( value_type& dest ) { dest = *p; } ));
140 CPPUNIT_ASSERT( pq.emplace( p->k, p->v ));
143 CPPUNIT_ASSERT( pq.emplace( std::make_pair( p->k, p->v ) ));
146 CPPUNIT_ASSERT( pq.push( *p ));
148 CPPUNIT_ASSERT( !pq.empty() );
149 CPPUNIT_ASSERT( pq.size() == ++nSize );
152 CPPUNIT_ASSERT( pq.full() );
153 CPPUNIT_ASSERT( pq.size() == pq.capacity() );
156 key_type k = c_nMinValue + key_type(c_nCapacity);
157 CPPUNIT_ASSERT( !pq.push( k ));
158 CPPUNIT_ASSERT( pq.full() );
159 CPPUNIT_ASSERT( pq.size() == pq.capacity() );
162 key_type nPrev = c_nMinValue + key_type(pq.capacity()) - 1;
165 CPPUNIT_ASSERT( pq.pop(kv) );
166 CPPUNIT_CHECK_EX( kv.k == nPrev, "Expected=" << nPrev << ", current=" << kv.k );
168 CPPUNIT_ASSERT( pq.size() == pq.capacity() - 1 );
169 CPPUNIT_ASSERT( !pq.full() );
170 CPPUNIT_ASSERT( !pq.empty() );
173 while ( pq.size() > 1 ) {
174 if ( pq.size() & 1 ) {
175 CPPUNIT_ASSERT( pq.pop(kv) );
176 CPPUNIT_CHECK_EX( kv.k == nPrev - 1, "Expected=" << nPrev - 1 << ", current=" << kv.k );
180 CPPUNIT_ASSERT( pq.pop_with( [&key]( value_type& src ) { key = src.k; } ) );
181 CPPUNIT_CHECK_EX( key == nPrev - 1, "Expected=" << nPrev - 1 << ", current=" << key );
186 CPPUNIT_ASSERT( pq.size() == nSize );
189 CPPUNIT_ASSERT( !pq.full() );
190 CPPUNIT_ASSERT( !pq.empty() );
191 CPPUNIT_ASSERT( pq.size() == 1 );
193 CPPUNIT_ASSERT( pq.pop(kv) );
194 CPPUNIT_CHECK_EX( kv.k == c_nMinValue, "Expected=" << c_nMinValue << ", current=" << kv.k );
196 CPPUNIT_ASSERT( !pq.full() );
197 CPPUNIT_ASSERT( pq.empty() );
198 CPPUNIT_ASSERT( pq.size() == 0 );
201 for ( value_type * p = pFirst; p < pLast; ++p ) {
202 CPPUNIT_ASSERT( pq.push( *p ));
204 CPPUNIT_ASSERT( !pq.empty() );
205 CPPUNIT_ASSERT( pq.full() );
206 CPPUNIT_ASSERT( pq.size() == pq.capacity() );
208 CPPUNIT_ASSERT( pq.empty() );
209 CPPUNIT_ASSERT( !pq.full() );
210 CPPUNIT_ASSERT( pq.size() == 0 );
213 for ( value_type * p = pFirst; p < pLast; ++p ) {
214 CPPUNIT_ASSERT( pq.push( *p ));
216 CPPUNIT_ASSERT( !pq.empty() );
217 CPPUNIT_ASSERT( pq.full() );
218 CPPUNIT_ASSERT( pq.size() == pq.capacity() );
221 pqueue::disposer disp;
222 pq.clear_with( std::ref(disp) );
223 CPPUNIT_ASSERT( pq.empty() );
224 CPPUNIT_ASSERT( !pq.full() );
225 CPPUNIT_ASSERT( pq.size() == 0 );
226 CPPUNIT_ASSERT( disp.m_nCallCount == pq.capacity() );
230 template <class PQueue>
233 PQueue pq( 0 ); // argument should be ignored for static buffer
234 test_bounded_with( pq );
236 template <class PQueue>
239 PQueue pq( c_nCapacity );
240 test_bounded_with( pq );
243 template <class PQueue>
248 data_array<value_type> arr( c_nCapacity );
249 value_type * pFirst = arr.begin();
250 value_type * pLast = pFirst + c_nCapacity;
252 CPPUNIT_ASSERT( pq.empty() );
253 CPPUNIT_ASSERT( pq.size() == 0 );
258 for ( value_type * p = pFirst; p < pLast; ++p ) {
259 CPPUNIT_ASSERT( pq.push( *p ));
260 CPPUNIT_ASSERT( !pq.empty() );
261 CPPUNIT_ASSERT( pq.size() == ++nSize );
264 CPPUNIT_ASSERT( pq.size() == c_nCapacity );
267 key_type nPrev = c_nMinValue + key_type(c_nCapacity) - 1;
270 CPPUNIT_ASSERT( pq.pop(kv) );
271 CPPUNIT_CHECK_EX( kv.k == nPrev, "Expected=" << nPrev << ", current=" << kv.k );
273 CPPUNIT_ASSERT( pq.size() == c_nCapacity - 1 );
274 CPPUNIT_ASSERT( !pq.empty() );
277 while ( pq.size() > 1 ) {
278 CPPUNIT_ASSERT( pq.pop(kv) );
279 CPPUNIT_CHECK_EX( kv.k == nPrev - 1, "Expected=" << nPrev - 1 << ", current=" << kv.k );
283 CPPUNIT_ASSERT( pq.size() == nSize );
286 CPPUNIT_ASSERT( !pq.empty() );
287 CPPUNIT_ASSERT( pq.size() == 1 );
289 CPPUNIT_ASSERT( pq.pop(kv) );
290 CPPUNIT_CHECK_EX( kv.k == c_nMinValue, "Expected=" << c_nMinValue << ", current=" << kv.k );
292 CPPUNIT_ASSERT( pq.empty() );
293 CPPUNIT_ASSERT( pq.size() == 0 );
296 for ( value_type * p = pFirst; p < pLast; ++p ) {
297 CPPUNIT_ASSERT( pq.push( *p ));
299 CPPUNIT_ASSERT( !pq.empty() );
300 CPPUNIT_ASSERT( pq.size() == c_nCapacity );
303 CPPUNIT_ASSERT( pq.empty() );
304 CPPUNIT_ASSERT( pq.size() == 0 );
309 void MSPQueue_st_cmp();
310 void MSPQueue_st_less();
311 void MSPQueue_st_cmpless();
312 void MSPQueue_st_cmp_mtx();
314 void MSPQueue_dyn_cmp();
315 void MSPQueue_dyn_less();
316 void MSPQueue_dyn_cmpless();
317 void MSPQueue_dyn_cmp_mtx();
319 void FCPQueue_vector();
320 void FCPQueue_vector_stat();
321 void FCPQueue_vector_mutex();
322 void FCPQueue_deque();
323 void FCPQueue_deque_stat();
324 void FCPQueue_deque_mutex();
325 void FCPQueue_boost_deque();
326 void FCPQueue_boost_deque_stat();
327 void FCPQueue_stablevector();
328 void FCPQueue_stablevector_stat();
330 CPPUNIT_TEST_SUITE(PQueueHdrTest)
331 CPPUNIT_TEST(MSPQueue_st)
332 CPPUNIT_TEST(MSPQueue_st_cmp)
333 CPPUNIT_TEST(MSPQueue_st_less)
334 CPPUNIT_TEST(MSPQueue_st_cmpless)
335 CPPUNIT_TEST(MSPQueue_st_cmp_mtx)
336 CPPUNIT_TEST(MSPQueue_dyn)
337 CPPUNIT_TEST(MSPQueue_dyn_cmp)
338 CPPUNIT_TEST(MSPQueue_dyn_less)
339 CPPUNIT_TEST(MSPQueue_dyn_cmpless)
340 CPPUNIT_TEST(MSPQueue_dyn_cmp_mtx)
342 CPPUNIT_TEST(FCPQueue_vector)
343 CPPUNIT_TEST(FCPQueue_vector_stat)
344 CPPUNIT_TEST(FCPQueue_vector_mutex)
345 CPPUNIT_TEST(FCPQueue_deque)
346 CPPUNIT_TEST(FCPQueue_deque_stat)
347 CPPUNIT_TEST(FCPQueue_deque_mutex)
348 CPPUNIT_TEST(FCPQueue_boost_deque)
349 CPPUNIT_TEST(FCPQueue_boost_deque_stat)
350 CPPUNIT_TEST(FCPQueue_stablevector)
351 CPPUNIT_TEST(FCPQueue_stablevector_stat)
352 CPPUNIT_TEST_SUITE_END()
355 } // namespace priority_queue
359 struct less<priority_queue::PQueueHdrTest::value_type>
361 bool operator()( priority_queue::PQueueHdrTest::value_type const& v1, priority_queue::PQueueHdrTest::value_type const& v2) const
363 return priority_queue::PQueueHdrTest::less()( v1, v2 );
368 #endif // #ifndef CDSHDRTEST_PQUEUE_H