]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // |
2 | // Boost.Pointer Container | |
3 | // | |
4 | // Copyright Thorsten Ottosen 2003-2005. Use, modification and | |
5 | // distribution is subject to the Boost Software License, Version | |
6 | // 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
7 | // http://www.boost.org/LICENSE_1_0.txt) | |
8 | // | |
9 | // For more information, see http://www.boost.org/libs/ptr_container/ | |
10 | // | |
11 | ||
12 | #ifndef BOOST_PTR_CONTAINER_PTR_SEQUENCE_ADAPTER_HPP | |
13 | #define BOOST_PTR_CONTAINER_PTR_SEQUENCE_ADAPTER_HPP | |
14 | ||
15 | #if defined(_MSC_VER) && (_MSC_VER >= 1200) | |
16 | # pragma once | |
17 | #endif | |
18 | ||
19 | ||
20 | #include <boost/ptr_container/detail/reversible_ptr_container.hpp> | |
21 | #include <boost/ptr_container/indirect_fun.hpp> | |
22 | #include <boost/ptr_container/detail/void_ptr_iterator.hpp> | |
23 | #include <boost/type_traits/remove_pointer.hpp> | |
24 | #include <boost/type_traits/is_same.hpp> | |
25 | ||
26 | ||
27 | namespace boost | |
28 | { | |
29 | namespace ptr_container_detail | |
30 | { | |
31 | template | |
32 | < | |
33 | class T, | |
34 | class VoidPtrSeq | |
35 | > | |
36 | struct sequence_config | |
37 | { | |
38 | typedef BOOST_DEDUCED_TYPENAME remove_nullable<T>::type | |
39 | U; | |
40 | typedef VoidPtrSeq | |
41 | void_container_type; | |
42 | ||
43 | typedef BOOST_DEDUCED_TYPENAME VoidPtrSeq::allocator_type | |
44 | allocator_type; | |
45 | ||
46 | typedef U value_type; | |
47 | ||
48 | typedef void_ptr_iterator< | |
49 | BOOST_DEDUCED_TYPENAME VoidPtrSeq::iterator, U > | |
50 | iterator; | |
51 | ||
52 | typedef void_ptr_iterator< | |
53 | BOOST_DEDUCED_TYPENAME VoidPtrSeq::const_iterator, const U > | |
54 | const_iterator; | |
55 | ||
56 | #if defined(BOOST_NO_SFINAE) || defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) | |
57 | ||
58 | template< class Iter > | |
59 | static U* get_pointer( Iter i ) | |
60 | { | |
61 | return static_cast<U*>( *i.base() ); | |
62 | } | |
63 | ||
64 | #else | |
65 | template< class Iter > | |
66 | static U* get_pointer( void_ptr_iterator<Iter,U> i ) | |
67 | { | |
68 | return static_cast<U*>( *i.base() ); | |
69 | } | |
70 | ||
71 | template< class Iter > | |
72 | static U* get_pointer( Iter i ) | |
73 | { | |
74 | return &*i; | |
75 | } | |
76 | #endif | |
77 | ||
78 | #if defined(BOOST_NO_SFINAE) && !BOOST_WORKAROUND(__MWERKS__, <= 0x3003) | |
79 | ||
80 | template< class Iter > | |
81 | static const U* get_const_pointer( Iter i ) | |
82 | { | |
83 | return static_cast<const U*>( *i.base() ); | |
84 | } | |
85 | ||
86 | #else // BOOST_NO_SFINAE | |
87 | ||
88 | #if BOOST_WORKAROUND(__MWERKS__, <= 0x3003) | |
89 | template< class Iter > | |
90 | static const U* get_const_pointer( void_ptr_iterator<Iter,U> i ) | |
91 | { | |
92 | return static_cast<const U*>( *i.base() ); | |
93 | } | |
94 | #else // BOOST_WORKAROUND | |
95 | template< class Iter > | |
96 | static const U* get_const_pointer( void_ptr_iterator<Iter,const U> i ) | |
97 | { | |
98 | return static_cast<const U*>( *i.base() ); | |
99 | } | |
100 | #endif // BOOST_WORKAROUND | |
101 | ||
102 | template< class Iter > | |
103 | static const U* get_const_pointer( Iter i ) | |
104 | { | |
105 | return &*i; | |
106 | } | |
107 | #endif // BOOST_NO_SFINAE | |
108 | ||
109 | BOOST_STATIC_CONSTANT(bool, allow_null = boost::is_nullable<T>::value ); | |
110 | }; | |
111 | ||
112 | } // ptr_container_detail | |
113 | ||
114 | ||
115 | template< class Iterator, class T > | |
116 | inline bool is_null( void_ptr_iterator<Iterator,T> i ) | |
117 | { | |
118 | return *i.base() == 0; | |
119 | } | |
120 | ||
121 | ||
122 | ||
123 | template | |
124 | < | |
125 | class T, | |
126 | class VoidPtrSeq, | |
127 | class CloneAllocator = heap_clone_allocator | |
128 | > | |
129 | class ptr_sequence_adapter : public | |
130 | ptr_container_detail::reversible_ptr_container< ptr_container_detail::sequence_config<T,VoidPtrSeq>, | |
131 | CloneAllocator > | |
132 | { | |
133 | typedef ptr_container_detail::reversible_ptr_container< ptr_container_detail::sequence_config<T,VoidPtrSeq>, | |
134 | CloneAllocator > | |
135 | base_type; | |
136 | ||
137 | typedef ptr_sequence_adapter<T,VoidPtrSeq,CloneAllocator> | |
138 | this_type; | |
139 | ||
140 | protected: | |
141 | typedef BOOST_DEDUCED_TYPENAME base_type::scoped_deleter scoped_deleter; | |
142 | ||
143 | public: | |
144 | typedef BOOST_DEDUCED_TYPENAME base_type::value_type value_type; | |
145 | typedef BOOST_DEDUCED_TYPENAME base_type::reference reference; | |
146 | typedef BOOST_DEDUCED_TYPENAME base_type::const_reference | |
147 | const_reference; | |
148 | typedef BOOST_DEDUCED_TYPENAME base_type::auto_type auto_type; | |
149 | typedef BOOST_DEDUCED_TYPENAME base_type::clone_allocator_type | |
150 | clone_allocator_type; | |
151 | typedef BOOST_DEDUCED_TYPENAME base_type::iterator iterator; | |
152 | typedef BOOST_DEDUCED_TYPENAME base_type::size_type size_type; | |
153 | typedef BOOST_DEDUCED_TYPENAME base_type::allocator_type | |
154 | allocator_type; | |
155 | ||
156 | ptr_sequence_adapter() | |
157 | { } | |
158 | ||
159 | template< class Allocator > | |
160 | explicit ptr_sequence_adapter( const Allocator& a ) | |
161 | : base_type( a ) | |
162 | { } | |
163 | ||
164 | template< class SizeType > | |
165 | ptr_sequence_adapter( SizeType n, | |
166 | ptr_container_detail::fixed_length_sequence_tag tag ) | |
167 | : base_type( n, tag ) | |
168 | { } | |
169 | ||
170 | template< class SizeType, class Allocator > | |
171 | ptr_sequence_adapter( SizeType n, const Allocator& a, | |
172 | ptr_container_detail::fixed_length_sequence_tag tag ) | |
173 | : base_type( n, a, tag ) | |
174 | { } | |
175 | ||
176 | template< class InputIterator > | |
177 | ptr_sequence_adapter( InputIterator first, InputIterator last ) | |
178 | : base_type( first, last ) | |
179 | { } | |
180 | ||
181 | template< class InputIterator, class Allocator > | |
182 | ptr_sequence_adapter( InputIterator first, InputIterator last, | |
183 | const Allocator& a ) | |
184 | : base_type( first, last, a ) | |
185 | { } | |
186 | ||
187 | template< class ForwardIterator > | |
188 | ptr_sequence_adapter( ForwardIterator first, | |
189 | ForwardIterator last, | |
190 | ptr_container_detail::fixed_length_sequence_tag tag ) | |
191 | : base_type( first, last, tag ) | |
192 | { } | |
193 | ||
194 | template< class SizeType, class ForwardIterator > | |
195 | ptr_sequence_adapter( SizeType n, | |
196 | ForwardIterator first, | |
197 | ForwardIterator last, | |
198 | ptr_container_detail::fixed_length_sequence_tag tag ) | |
199 | : base_type( n, first, last, tag ) | |
200 | { } | |
201 | ||
202 | ptr_sequence_adapter( const ptr_sequence_adapter& r ) | |
203 | : base_type( r ) | |
204 | { } | |
205 | ||
206 | template< class U > | |
207 | ptr_sequence_adapter( const ptr_sequence_adapter<U,VoidPtrSeq,CloneAllocator>& r ) | |
208 | : base_type( r ) | |
209 | { } | |
210 | ||
211 | ptr_sequence_adapter( const ptr_sequence_adapter& r, | |
212 | ptr_container_detail::fixed_length_sequence_tag tag ) | |
213 | : base_type( r, tag ) | |
214 | { } | |
215 | ||
216 | template< class U > | |
217 | ptr_sequence_adapter( const ptr_sequence_adapter<U,VoidPtrSeq,CloneAllocator>& r, | |
218 | ptr_container_detail::fixed_length_sequence_tag tag ) | |
219 | : base_type( r, tag ) | |
220 | { } | |
221 | ||
222 | template< class PtrContainer > | |
223 | explicit ptr_sequence_adapter( std::auto_ptr<PtrContainer> clone ) | |
224 | : base_type( clone ) | |
225 | { } | |
226 | ||
227 | ptr_sequence_adapter& operator=( const ptr_sequence_adapter r ) | |
228 | { | |
229 | this->swap( r ); | |
230 | return *this; | |
231 | } | |
232 | ||
233 | template< class PtrContainer > | |
234 | ptr_sequence_adapter& operator=( std::auto_ptr<PtrContainer> clone ) | |
235 | { | |
236 | base_type::operator=( clone ); | |
237 | return *this; | |
238 | } | |
239 | ||
240 | ///////////////////////////////////////////////////////////// | |
241 | // modifiers | |
242 | ///////////////////////////////////////////////////////////// | |
243 | ||
244 | void push_back( value_type x ) // strong | |
245 | { | |
246 | this->enforce_null_policy( x, "Null pointer in 'push_back()'" ); | |
247 | ||
248 | auto_type ptr( x ); // notrow | |
249 | this->base().push_back( x ); // strong, commit | |
250 | ptr.release(); // nothrow | |
251 | } | |
252 | ||
253 | template< class U > | |
254 | void push_back( std::auto_ptr<U> x ) | |
255 | { | |
256 | push_back( x.release() ); | |
257 | } | |
258 | ||
259 | void push_front( value_type x ) | |
260 | { | |
261 | this->enforce_null_policy( x, "Null pointer in 'push_front()'" ); | |
262 | ||
263 | auto_type ptr( x ); // nothrow | |
264 | this->base().push_front( x ); // strong, commit | |
265 | ptr.release(); // nothrow | |
266 | } | |
267 | ||
268 | template< class U > | |
269 | void push_front( std::auto_ptr<U> x ) | |
270 | { | |
271 | push_front( x.release() ); | |
272 | } | |
273 | ||
274 | auto_type pop_back() | |
275 | { | |
276 | BOOST_ASSERT( !this->empty() && | |
277 | "'pop_back()' on empty container" ); | |
278 | auto_type ptr( static_cast<value_type>( this->base().back() ) ); | |
279 | // nothrow | |
280 | this->base().pop_back(); // nothrow | |
281 | return ptr_container_detail::move( ptr ); // nothrow | |
282 | } | |
283 | ||
284 | auto_type pop_front() | |
285 | { | |
286 | BOOST_ASSERT( !this->empty() && | |
287 | "'pop_front()' on empty container" ); | |
288 | auto_type ptr( static_cast<value_type>( this->base().front() ) ); | |
289 | // nothrow | |
290 | this->base().pop_front(); // nothrow | |
291 | return ptr_container_detail::move( ptr ); | |
292 | } | |
293 | ||
294 | reference front() | |
295 | { | |
296 | BOOST_ASSERT( !this->empty() && | |
297 | "accessing 'front()' on empty container" ); | |
298 | ||
299 | BOOST_ASSERT( !::boost::is_null( this->begin() ) ); | |
300 | return *this->begin(); | |
301 | } | |
302 | ||
303 | const_reference front() const | |
304 | { | |
305 | return const_cast<ptr_sequence_adapter*>(this)->front(); | |
306 | } | |
307 | ||
308 | reference back() | |
309 | { | |
310 | BOOST_ASSERT( !this->empty() && | |
311 | "accessing 'back()' on empty container" ); | |
312 | BOOST_ASSERT( !::boost::is_null( --this->end() ) ); | |
313 | return *--this->end(); | |
314 | } | |
315 | ||
316 | const_reference back() const | |
317 | { | |
318 | return const_cast<ptr_sequence_adapter*>(this)->back(); | |
319 | } | |
320 | ||
321 | public: // deque/vector inerface | |
322 | ||
323 | reference operator[]( size_type n ) // nothrow | |
324 | { | |
325 | BOOST_ASSERT( n < this->size() ); | |
326 | BOOST_ASSERT( !this->is_null( n ) ); | |
327 | return *static_cast<value_type>( this->base()[n] ); | |
328 | } | |
329 | ||
330 | const_reference operator[]( size_type n ) const // nothrow | |
331 | { | |
332 | BOOST_ASSERT( n < this->size() ); | |
333 | BOOST_ASSERT( !this->is_null( n ) ); | |
334 | return *static_cast<value_type>( this->base()[n] ); | |
335 | } | |
336 | ||
337 | reference at( size_type n ) | |
338 | { | |
339 | BOOST_PTR_CONTAINER_THROW_EXCEPTION( n >= this->size(), bad_index, | |
340 | "'at()' out of bounds" ); | |
341 | BOOST_ASSERT( !this->is_null( n ) ); | |
342 | return (*this)[n]; | |
343 | } | |
344 | ||
345 | const_reference at( size_type n ) const | |
346 | { | |
347 | BOOST_PTR_CONTAINER_THROW_EXCEPTION( n >= this->size(), bad_index, | |
348 | "'at()' out of bounds" ); | |
349 | BOOST_ASSERT( !this->is_null( n ) ); | |
350 | return (*this)[n]; | |
351 | } | |
352 | ||
353 | public: // vector interface | |
354 | ||
355 | size_type capacity() const | |
356 | { | |
357 | return this->base().capacity(); | |
358 | } | |
359 | ||
360 | void reserve( size_type n ) | |
361 | { | |
362 | this->base().reserve( n ); | |
363 | } | |
364 | ||
365 | void reverse() | |
366 | { | |
367 | this->base().reverse(); | |
368 | } | |
369 | ||
370 | public: // assign, insert, transfer | |
371 | ||
372 | // overhead: 1 heap allocation (very cheap compared to cloning) | |
373 | template< class InputIterator > | |
374 | void assign( InputIterator first, InputIterator last ) // strong | |
375 | { | |
376 | base_type temp( first, last ); | |
377 | this->swap( temp ); | |
378 | } | |
379 | ||
380 | template< class Range > | |
381 | void assign( const Range& r ) // strong | |
382 | { | |
383 | assign( boost::begin(r), boost::end(r ) ); | |
384 | } | |
385 | ||
386 | private: | |
387 | template< class I > | |
388 | void insert_impl( iterator before, I first, I last, std::input_iterator_tag ) // strong | |
389 | { | |
390 | ptr_sequence_adapter temp(first,last); // strong | |
391 | transfer( before, temp ); // strong, commit | |
392 | } | |
393 | ||
394 | template< class I > | |
395 | void insert_impl( iterator before, I first, I last, std::forward_iterator_tag ) // strong | |
396 | { | |
397 | if( first == last ) | |
398 | return; | |
399 | scoped_deleter sd( first, last ); // strong | |
400 | this->insert_clones_and_release( sd, before ); // strong, commit | |
401 | } | |
402 | ||
403 | public: | |
404 | ||
405 | using base_type::insert; | |
406 | ||
407 | template< class InputIterator > | |
408 | void insert( iterator before, InputIterator first, InputIterator last ) // strong | |
409 | { | |
410 | insert_impl( before, first, last, BOOST_DEDUCED_TYPENAME | |
411 | iterator_category<InputIterator>::type() ); | |
412 | } | |
413 | ||
414 | #if defined(BOOST_NO_SFINAE) || defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) | |
415 | #else | |
416 | template< class Range > | |
417 | BOOST_DEDUCED_TYPENAME | |
418 | boost::disable_if< ptr_container_detail::is_pointer_or_integral<Range> >::type | |
419 | insert( iterator before, const Range& r ) | |
420 | { | |
421 | insert( before, boost::begin(r), boost::end(r) ); | |
422 | } | |
423 | ||
424 | #endif | |
425 | ||
426 | template< class PtrSeqAdapter > | |
427 | void transfer( iterator before, | |
428 | BOOST_DEDUCED_TYPENAME PtrSeqAdapter::iterator first, | |
429 | BOOST_DEDUCED_TYPENAME PtrSeqAdapter::iterator last, | |
430 | PtrSeqAdapter& from ) // strong | |
431 | { | |
432 | BOOST_ASSERT( (void*)&from != (void*)this ); | |
433 | if( from.empty() ) | |
434 | return; | |
435 | this->base(). | |
436 | insert( before.base(), first.base(), last.base() ); // strong | |
437 | from.base().erase( first.base(), last.base() ); // nothrow | |
438 | } | |
439 | ||
440 | template< class PtrSeqAdapter > | |
441 | void transfer( iterator before, | |
442 | BOOST_DEDUCED_TYPENAME PtrSeqAdapter::iterator object, | |
443 | PtrSeqAdapter& from ) // strong | |
444 | { | |
445 | BOOST_ASSERT( (void*)&from != (void*)this ); | |
446 | if( from.empty() ) | |
447 | return; | |
448 | this->base().insert( before.base(), *object.base() ); // strong | |
449 | from.base().erase( object.base() ); // nothrow | |
450 | } | |
451 | ||
452 | #if defined(BOOST_NO_SFINAE) || defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING) | |
453 | #else | |
454 | ||
455 | template< class PtrSeqAdapter, class Range > | |
456 | BOOST_DEDUCED_TYPENAME boost::disable_if< boost::is_same< Range, | |
457 | BOOST_DEDUCED_TYPENAME PtrSeqAdapter::iterator > >::type | |
458 | transfer( iterator before, const Range& r, PtrSeqAdapter& from ) // strong | |
459 | { | |
460 | transfer( before, boost::begin(r), boost::end(r), from ); | |
461 | } | |
462 | ||
463 | #endif | |
464 | template< class PtrSeqAdapter > | |
465 | void transfer( iterator before, PtrSeqAdapter& from ) // strong | |
466 | { | |
467 | BOOST_ASSERT( (void*)&from != (void*)this ); | |
468 | if( from.empty() ) | |
469 | return; | |
470 | this->base(). | |
471 | insert( before.base(), | |
472 | from.begin().base(), from.end().base() ); // strong | |
473 | from.base().clear(); // nothrow | |
474 | } | |
475 | ||
476 | public: // C-array support | |
477 | ||
478 | void transfer( iterator before, value_type* from, | |
479 | size_type size, bool delete_from = true ) // strong | |
480 | { | |
481 | BOOST_ASSERT( from != 0 ); | |
482 | if( delete_from ) | |
483 | { | |
484 | BOOST_DEDUCED_TYPENAME base_type::scoped_deleter | |
485 | deleter( from, size ); // nothrow | |
486 | this->base().insert( before.base(), from, from + size ); // strong | |
487 | deleter.release(); // nothrow | |
488 | } | |
489 | else | |
490 | { | |
491 | this->base().insert( before.base(), from, from + size ); // strong | |
492 | } | |
493 | } | |
494 | ||
495 | value_type* c_array() // nothrow | |
496 | { | |
497 | if( this->empty() ) | |
498 | return 0; | |
499 | T** res = reinterpret_cast<T**>( &this->begin().base()[0] ); | |
500 | return res; | |
501 | } | |
502 | ||
503 | public: // null functions | |
504 | ||
505 | bool is_null( size_type idx ) const | |
506 | { | |
507 | BOOST_ASSERT( idx < this->size() ); | |
508 | return this->base()[idx] == 0; | |
509 | } | |
510 | ||
511 | public: // resize | |
512 | ||
513 | void resize( size_type size ) // basic | |
514 | { | |
515 | size_type old_size = this->size(); | |
516 | if( old_size > size ) | |
517 | { | |
518 | this->erase( boost::next( this->begin(), size ), this->end() ); | |
519 | } | |
520 | else if( size > old_size ) | |
521 | { | |
522 | for( ; old_size != size; ++old_size ) | |
523 | this->push_back( new BOOST_DEDUCED_TYPENAME | |
524 | boost::remove_pointer<value_type>::type() ); | |
525 | } | |
526 | ||
527 | BOOST_ASSERT( this->size() == size ); | |
528 | } | |
529 | ||
530 | void resize( size_type size, value_type to_clone ) // basic | |
531 | { | |
532 | size_type old_size = this->size(); | |
533 | if( old_size > size ) | |
534 | { | |
535 | this->erase( boost::next( this->begin(), size ), this->end() ); | |
536 | } | |
537 | else if( size > old_size ) | |
538 | { | |
539 | for( ; old_size != size; ++old_size ) | |
540 | this->push_back( this->null_policy_allocate_clone( to_clone ) ); | |
541 | } | |
542 | ||
543 | BOOST_ASSERT( this->size() == size ); | |
544 | } | |
545 | ||
546 | void rresize( size_type size ) // basic | |
547 | { | |
548 | size_type old_size = this->size(); | |
549 | if( old_size > size ) | |
550 | { | |
551 | this->erase( this->begin(), | |
552 | boost::next( this->begin(), old_size - size ) ); | |
553 | } | |
554 | else if( size > old_size ) | |
555 | { | |
556 | for( ; old_size != size; ++old_size ) | |
557 | this->push_front( new BOOST_DEDUCED_TYPENAME | |
558 | boost::remove_pointer<value_type>::type() ); | |
559 | } | |
560 | ||
561 | BOOST_ASSERT( this->size() == size ); | |
562 | } | |
563 | ||
564 | void rresize( size_type size, value_type to_clone ) // basic | |
565 | { | |
566 | size_type old_size = this->size(); | |
567 | if( old_size > size ) | |
568 | { | |
569 | this->erase( this->begin(), | |
570 | boost::next( this->begin(), old_size - size ) ); | |
571 | } | |
572 | else if( size > old_size ) | |
573 | { | |
574 | for( ; old_size != size; ++old_size ) | |
575 | this->push_front( this->null_policy_allocate_clone( to_clone ) ); | |
576 | } | |
577 | ||
578 | BOOST_ASSERT( this->size() == size ); | |
579 | } | |
580 | ||
581 | public: // algorithms | |
582 | ||
583 | void sort( iterator first, iterator last ) | |
584 | { | |
585 | sort( first, last, std::less<T>() ); | |
586 | } | |
587 | ||
588 | void sort() | |
589 | { | |
590 | sort( this->begin(), this->end() ); | |
591 | } | |
592 | ||
593 | template< class Compare > | |
594 | void sort( iterator first, iterator last, Compare comp ) | |
595 | { | |
596 | BOOST_ASSERT( first <= last && "out of range sort()" ); | |
597 | BOOST_ASSERT( this->begin() <= first && "out of range sort()" ); | |
598 | BOOST_ASSERT( last <= this->end() && "out of range sort()" ); | |
599 | // some static assert on the arguments of the comparison | |
600 | std::sort( first.base(), last.base(), | |
601 | void_ptr_indirect_fun<Compare,T>(comp) ); | |
602 | } | |
603 | ||
604 | template< class Compare > | |
605 | void sort( Compare comp ) | |
606 | { | |
607 | sort( this->begin(), this->end(), comp ); | |
608 | } | |
609 | ||
610 | void unique( iterator first, iterator last ) | |
611 | { | |
612 | unique( first, last, std::equal_to<T>() ); | |
613 | } | |
614 | ||
615 | void unique() | |
616 | { | |
617 | unique( this->begin(), this->end() ); | |
618 | } | |
619 | ||
620 | private: | |
621 | struct is_not_zero_ptr | |
622 | { | |
623 | template< class U > | |
624 | bool operator()( const U* r ) const | |
625 | { | |
626 | return r != 0; | |
627 | } | |
628 | }; | |
629 | ||
630 | protected: | |
631 | template< class Fun, class Arg1 > | |
632 | class void_ptr_delete_if | |
633 | { | |
634 | Fun fun; | |
635 | public: | |
636 | ||
637 | void_ptr_delete_if() : fun(Fun()) | |
638 | { } | |
639 | ||
640 | void_ptr_delete_if( Fun f ) : fun(f) | |
641 | { } | |
642 | ||
643 | bool operator()( void* r ) const | |
644 | { | |
645 | BOOST_ASSERT( r != 0 ); | |
646 | Arg1 arg1 = static_cast<Arg1>(r); | |
647 | if( fun( *arg1 ) ) | |
648 | { | |
649 | clone_allocator_type::deallocate_clone( arg1 ); | |
650 | return true; | |
651 | } | |
652 | return false; | |
653 | } | |
654 | }; | |
655 | ||
656 | private: | |
657 | void compact_and_erase_nulls( iterator first, iterator last ) // nothrow | |
658 | { | |
659 | typename base_type::ptr_iterator p = std::stable_partition( | |
660 | first.base(), | |
661 | last.base(), | |
662 | is_not_zero_ptr() ); | |
663 | this->base().erase( p, this->end().base() ); | |
664 | ||
665 | } | |
666 | ||
667 | void range_check_impl( iterator first, iterator last, | |
668 | std::bidirectional_iterator_tag ) | |
669 | { /* do nothing */ } | |
670 | ||
671 | void range_check_impl( iterator first, iterator last, | |
672 | std::random_access_iterator_tag ) | |
673 | { | |
674 | BOOST_ASSERT( first <= last && "out of range unique()/erase_if()" ); | |
675 | BOOST_ASSERT( this->begin() <= first && "out of range unique()/erase_if()" ); | |
676 | BOOST_ASSERT( last <= this->end() && "out of range unique()/erase_if)(" ); | |
677 | } | |
678 | ||
679 | void range_check( iterator first, iterator last ) | |
680 | { | |
681 | range_check_impl( first, last, | |
682 | BOOST_DEDUCED_TYPENAME iterator_category<iterator>::type() ); | |
683 | } | |
684 | ||
685 | public: | |
686 | ||
687 | template< class Compare > | |
688 | void unique( iterator first, iterator last, Compare comp ) | |
689 | { | |
690 | range_check(first,last); | |
691 | ||
692 | iterator prev = first; | |
693 | iterator next = first; | |
694 | ++next; | |
695 | for( ; next != last; ++next ) | |
696 | { | |
697 | BOOST_ASSERT( !::boost::is_null(prev) ); | |
698 | BOOST_ASSERT( !::boost::is_null(next) ); | |
699 | if( comp( *prev, *next ) ) | |
700 | { | |
701 | this->remove( next ); // delete object | |
702 | *next.base() = 0; // mark pointer as deleted | |
703 | } | |
704 | else | |
705 | { | |
706 | prev = next; | |
707 | } | |
708 | // ++next | |
709 | } | |
710 | ||
711 | compact_and_erase_nulls( first, last ); | |
712 | } | |
713 | ||
714 | template< class Compare > | |
715 | void unique( Compare comp ) | |
716 | { | |
717 | unique( this->begin(), this->end(), comp ); | |
718 | } | |
719 | ||
720 | template< class Pred > | |
721 | void erase_if( iterator first, iterator last, Pred pred ) | |
722 | { | |
723 | range_check(first,last); | |
724 | this->base().erase( std::remove_if( first.base(), last.base(), | |
725 | void_ptr_delete_if<Pred,value_type>(pred) ), | |
726 | last.base() ); | |
727 | } | |
728 | ||
729 | template< class Pred > | |
730 | void erase_if( Pred pred ) | |
731 | { | |
732 | erase_if( this->begin(), this->end(), pred ); | |
733 | } | |
734 | ||
735 | ||
736 | void merge( iterator first, iterator last, | |
737 | ptr_sequence_adapter& from ) | |
738 | { | |
739 | merge( first, last, from, std::less<T>() ); | |
740 | } | |
741 | ||
742 | template< class BinPred > | |
743 | void merge( iterator first, iterator last, | |
744 | ptr_sequence_adapter& from, BinPred pred ) | |
745 | { | |
746 | void_ptr_indirect_fun<BinPred,T> bin_pred(pred); | |
747 | size_type current_size = this->size(); | |
748 | this->transfer( this->end(), first, last, from ); | |
749 | typename base_type::ptr_iterator middle = this->begin().base(); | |
750 | std::advance(middle,current_size); | |
751 | std::inplace_merge( this->begin().base(), | |
752 | middle, | |
753 | this->end().base(), | |
754 | bin_pred ); | |
755 | } | |
756 | ||
757 | void merge( ptr_sequence_adapter& r ) | |
758 | { | |
759 | merge( r, std::less<T>() ); | |
760 | BOOST_ASSERT( r.empty() ); | |
761 | } | |
762 | ||
763 | template< class BinPred > | |
764 | void merge( ptr_sequence_adapter& r, BinPred pred ) | |
765 | { | |
766 | merge( r.begin(), r.end(), r, pred ); | |
767 | BOOST_ASSERT( r.empty() ); | |
768 | } | |
769 | ||
770 | }; | |
771 | ||
772 | ||
773 | } // namespace 'boost' | |
774 | ||
775 | #endif |