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
27namespace boost
28{
29namespace 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
776

source code of boost/boost/ptr_container/ptr_sequence_adapter.hpp