source: NonGTP/Boost/boost/ptr_container/ptr_sequence_adapter.hpp @ 857

Revision 857, 19.5 KB checked in by igarcia, 19 years ago (diff)
Line 
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/range/reverse_iterator.hpp>
24#include <boost/range/const_reverse_iterator.hpp>
25#include <boost/type_traits/remove_pointer.hpp>
26#include <boost/type_traits/is_same.hpp>
27#include <boost/type_traits/is_pointer.hpp>
28#include <boost/type_traits/is_integral.hpp>
29#include <boost/iterator/iterator_categories.hpp>
30
31namespace boost
32{   
33namespace ptr_container_detail
34{
35       
36    template
37    <
38        class T,
39        class VoidPtrSeq
40    >
41    struct sequence_config
42    {
43        typedef BOOST_DEDUCED_TYPENAME remove_nullable<T>::type
44                    U;
45        typedef VoidPtrSeq
46                    void_container_type;
47
48        typedef BOOST_DEDUCED_TYPENAME VoidPtrSeq::allocator_type
49                    allocator_type;
50       
51        typedef U   value_type;
52
53        typedef void_ptr_iterator<
54                        BOOST_DEDUCED_TYPENAME VoidPtrSeq::iterator, U >
55                    iterator;
56       
57        typedef void_ptr_iterator<
58                        BOOST_DEDUCED_TYPENAME VoidPtrSeq::const_iterator, const U >
59                    const_iterator;
60       
61        typedef void_ptr_iterator<
62                       BOOST_DEDUCED_TYPENAME VoidPtrSeq::reverse_iterator, U >
63                   reverse_iterator;
64       
65        typedef void_ptr_iterator<
66                       BOOST_DEDUCED_TYPENAME VoidPtrSeq::const_reverse_iterator, const U >
67                   const_reverse_iterator;
68       
69        typedef value_type
70                   object_type;
71
72#ifdef BOOST_NO_SFINAE
73
74        template< class Iter >
75        static U* get_pointer( Iter i )
76        {
77            return static_cast<U*>( *i.base() );
78        }
79       
80#else
81        template< class Iter >
82        static U* get_pointer( void_ptr_iterator<Iter,U> i )
83        {
84            return static_cast<U*>( *i.base() );
85        }
86
87        template< class Iter >
88        static U* get_pointer( Iter i )
89        {
90            return &*i;
91        }
92#endif       
93
94#if defined(BOOST_NO_SFINAE) && !BOOST_WORKAROUND(__MWERKS__, <= 0x3003)
95
96        template< class Iter >
97        static const U* get_const_pointer( Iter i )
98        {
99            return static_cast<const U*>( *i.base() );
100        }
101       
102#else // BOOST_NO_SFINAE
103
104#if BOOST_WORKAROUND(__MWERKS__, <= 0x3003)
105        template< class Iter >
106        static const U* get_const_pointer( void_ptr_iterator<Iter,U> i )
107        {
108            return static_cast<const U*>( *i.base() );
109        }
110#else // BOOST_WORKAROUND
111        template< class Iter >
112        static const U* get_const_pointer( void_ptr_iterator<Iter,const U> i )
113        {
114            return static_cast<const U*>( *i.base() );
115        }
116#endif // BOOST_WORKAROUND
117
118        template< class Iter >
119        static const U* get_const_pointer( Iter i )
120        {
121            return &*i;
122        }
123#endif // BOOST_NO_SFINAE
124
125        BOOST_STATIC_CONSTANT(bool, allow_null = boost::is_nullable<T>::value );
126    };
127   
128} // ptr_container_detail
129
130
131    template< class Iterator, class T >
132    inline bool is_null( void_ptr_iterator<Iterator,T> i )
133    {
134        return *i.base() == 0;
135    }
136
137
138   
139    template
140    <
141        class T,
142        class VoidPtrSeq,
143        class CloneAllocator = heap_clone_allocator
144    >
145    class ptr_sequence_adapter : public
146        ptr_container_detail::reversible_ptr_container< ptr_container_detail::sequence_config<T,VoidPtrSeq>,
147                                            CloneAllocator >
148    {
149        typedef ptr_container_detail::reversible_ptr_container< ptr_container_detail::sequence_config<T,VoidPtrSeq>,
150                                                    CloneAllocator >
151             base_type;
152       
153        typedef BOOST_DEDUCED_TYPENAME base_type::scoped_deleter scoped_deleter;
154
155        typedef ptr_sequence_adapter<T,VoidPtrSeq,CloneAllocator> this_type;
156         
157    public:
158        typedef BOOST_DEDUCED_TYPENAME base_type::value_type  value_type;
159        typedef BOOST_DEDUCED_TYPENAME base_type::reference   reference;
160        typedef BOOST_DEDUCED_TYPENAME base_type::auto_type   auto_type;
161         
162        BOOST_PTR_CONTAINER_DEFINE_CONSTRUCTORS( ptr_sequence_adapter,
163                                                 base_type )
164   
165        template< class PtrContainer >
166        ptr_sequence_adapter( std::auto_ptr<PtrContainer> clone )
167          : base_type( clone )
168        { }
169
170        template< class PtrContainer >
171        void operator=( std::auto_ptr<PtrContainer> clone )   
172        {
173            base_type::operator=( clone );
174        }
175
176        /////////////////////////////////////////////////////////////
177        // modifiers
178        /////////////////////////////////////////////////////////////
179
180        void push_back( value_type x )  // strong               
181        {
182            this->enforce_null_policy( x, "Null pointer in 'push_back()'" );
183
184            auto_type ptr( x );                // notrow
185            this->c_private().push_back( x );  // strong, commit
186            ptr.release();                     // nothrow
187        }
188
189        void push_front( value_type x )               
190        {
191            this->enforce_null_policy( x, "Null pointer in 'push_front()'" );
192
193            auto_type ptr( x );                // nothrow
194            this->c_private().push_front( x ); // strong, commit
195            ptr.release();                     // nothrow
196        }
197
198        auto_type pop_back()
199        {
200            if( this->empty() )
201                throw bad_ptr_container_operation( "'pop_back()' "
202                                                     " on empty container" );
203            auto_type ptr( static_cast<value_type>(
204                         this->c_private().back() ) ); // nothrow
205            this->c_private().pop_back();              // nothrow
206            return ptr_container_detail::move( ptr );                        // nothrow
207        }
208
209        auto_type pop_front()
210        {
211            if( this->empty() )
212                throw bad_ptr_container_operation( "'pop_front()' on"
213                                                     " empty container" );
214            auto_type ptr( static_cast<value_type>(
215                        this->c_private().front() ) ); // nothrow
216            this->c_private().pop_front();              // nothrow
217            return ptr_container_detail::move( ptr );
218        }
219       
220        reference front()       
221        {
222            if( this->empty() )
223                throw bad_ptr_container_operation( "accessing 'front()' on empty container" );
224            BOOST_ASSERT( !::boost::is_null( this->begin() ) );
225            return *this->begin();
226        }
227
228        const_reference front() const 
229        {
230            if( this->empty() )
231                throw bad_ptr_container_operation( "accessing 'front()' on empty container" );
232            BOOST_ASSERT( !::boost::is_null( this->begin() ) );
233            return *this->begin();
234        }
235
236        reference back()
237        {
238            if( this->empty() )
239                throw bad_ptr_container_operation( "accessing 'back()' on empty container" );
240            BOOST_ASSERT( !::boost::is_null( --this->end() ) );
241            return *--this->end();
242        }
243
244        const_reference back() const
245        {
246            if( this->empty() )
247                throw bad_ptr_container_operation( "accessing 'back()' on empty container" );
248            BOOST_ASSERT( !::boost::is_null( --this->end() ) );
249            return *--this->end();
250        }
251
252    public: // deque/vector inerface
253       
254        reference operator[]( size_type n ) // nothrow
255        {
256            BOOST_ASSERT( n < this->size() );
257            BOOST_ASSERT( !this->is_null( n ) );
258            return *static_cast<value_type>( this->c_private()[n] );
259        }
260       
261        const_reference operator[]( size_type n ) const // nothrow 
262        {
263            BOOST_ASSERT( n < this->size() );
264            BOOST_ASSERT( !this->is_null( n ) );
265            return *static_cast<value_type>( this->c_private()[n] );
266        }
267       
268        reference at( size_type n )
269        {
270            if( n >= this->size() )
271                throw bad_index( "'at()' out of bounds" );
272            BOOST_ASSERT( !this->is_null( n ) );
273            return (*this)[n];
274        }
275       
276        const_reference at( size_type n ) const
277        {
278            if( n >= this->size() )
279                throw bad_index( "'at()' out of bounds" );
280            BOOST_ASSERT( !this->is_null( n ) );
281            return (*this)[n];
282        }
283       
284    public: // vector interface
285       
286        size_type capacity() const
287        {
288            return this->c_private().capacity();
289        }
290       
291        void reserve( size_type n )
292        {
293            this->c_private().reserve( n );
294        }
295
296        void reverse()
297        {
298            this->c_private().reverse();
299        }
300
301    public: // assign, insert, transfer
302
303        // overhead: 1 heap allocation (very cheap compared to cloning)
304        template< class InputIterator >
305        void assign( InputIterator first, InputIterator last ) // strong
306        {
307//#ifdef BOOST_NO_SFINAE
308//#else
309//            BOOST_STATIC_ASSERT(( boost::is_convertible< typename iterator_reference<InputIterator>::type,
310//                                                         reference_type >::value ));
311//#endif           
312            base_type temp( first, last );
313            this->swap( temp );
314        }
315
316        template< class Range >
317        void assign( const Range& r )
318        {
319            assign( this->adl_begin(r), this->adl_end(r ) );
320        }
321
322    private:
323        template< class I >
324        void insert_impl( iterator before, I first, I last, std::input_iterator_tag ) // strong
325        {
326            ptr_sequence_adapter temp(first,last);  // strong
327            transfer( before, temp );               // strong, commit
328        }
329
330        template< class I >
331        void insert_impl( iterator before, I first, I last, std::forward_iterator_tag ) // strong
332        {
333            if( first == last )
334                return;
335            scoped_deleter sd( first, last );                // strong
336            this->insert_clones_and_release( sd, before );   // strong, commit
337        }
338
339    public:
340
341        using base_type::insert;
342       
343        template< class InputIterator >
344        void insert( iterator before, InputIterator first, InputIterator last ) // strong
345        {
346            insert_impl( before, first, last, BOOST_DEDUCED_TYPENAME
347                         iterator_category<InputIterator>::type() );
348        }
349
350#ifdef BOOST_NO_SFINAE
351#else
352        template< class Range >
353        BOOST_DEDUCED_TYPENAME
354        boost::disable_if< ptr_container_detail::is_pointer_or_integral<Range> >::type
355        insert( iterator before, const Range& r )// ptr_container_detail::is_range_tag )
356        {
357            insert( before, this->adl_begin(r), this->adl_end(r) );
358        }
359
360#endif
361
362        void transfer( iterator before,
363                       iterator first,
364                       iterator last,
365                       ptr_sequence_adapter& from ) // strong
366        {
367            BOOST_ASSERT( &from != this );
368            if( from.empty() )
369                return;
370            this->c_private().
371                insert( before.base(),
372                        first.base(), last.base() ); // strong
373            from.c_private().erase( first.base(),
374                                    last.base() );   // nothrow
375        }
376
377        void transfer( iterator before,
378                       iterator object,
379                       ptr_sequence_adapter& from ) // strong
380        {
381            BOOST_ASSERT( &from != this );
382            if( from.empty() )
383                return;
384            this->c_private().
385                insert( before.base(),
386                        *object.base() );                 // strong
387            from.c_private().erase( object.base() );      // nothrow
388        }
389
390#ifdef BOOST_NO_SFINAE
391#else
392       
393        template< class Range >
394        BOOST_DEDUCED_TYPENAME boost::disable_if< boost::is_same< Range,
395                                                                  iterator > >::type
396        transfer( iterator before, const Range& r, ptr_sequence_adapter& from ) // strong
397        {
398            transfer( before, this->adl_begin(r), this->adl_end(r), from );
399        }
400
401#endif
402       
403        void transfer( iterator before, ptr_sequence_adapter& from ) // strong
404        {
405            BOOST_ASSERT( &from != this );
406            if( from.empty() )
407                return;
408            this->c_private().
409                insert( before.base(),
410                        from.begin().base(), from.end().base() ); // strong
411            from.c_private().clear();                       // nothrow
412        }
413
414    public: // null functions
415         
416        bool is_null( size_type idx ) const
417        {
418            BOOST_ASSERT( idx < this->size() );
419            return this->c_private()[idx] == 0;
420        }
421
422    public: // algorithms
423
424        void sort( iterator first, iterator last )
425        {
426            sort( first, last, std::less<T>() );
427        }
428       
429        void sort()
430        {
431            sort( this->begin(), this->end() );
432        }
433
434        template< class Compare >
435        void sort( iterator first, iterator last, Compare comp )
436        {
437            BOOST_ASSERT( first <= last && "out of range sort()" );
438            BOOST_ASSERT( this->begin() <= first && "out of range sort()" );
439            BOOST_ASSERT( last <= this->end() && "out of range sort()" );
440            // some static assert on the arguments of the comparison
441            std::sort( first.base(), last.base(),
442                       void_ptr_indirect_fun<Compare,T>(comp) );
443        }
444       
445        template< class Compare >
446        void sort( Compare comp )
447        {
448            sort( this->begin(), this->end(), comp );
449        }
450       
451        void unique( iterator first, iterator last )
452        {
453            unique( first, last, std::equal_to<T>() );
454        }
455       
456        void unique()
457        {
458            unique( this->begin(), this->end() );
459        }
460
461    private:
462        struct is_not_zero_ptr
463        {
464            template< class U >
465            bool operator()( const U* r ) const
466            {
467                return r != 0;
468            }
469        };
470
471        void compact_and_erase_nulls( iterator first, iterator last ) // nothrow
472        {
473           
474            typename base_type::ptr_iterator p = std::stable_partition(
475                                                    first.base(),
476                                                    last.base(),
477                                                    is_not_zero_ptr() );
478            this->c_private().erase( p, this->end().base() );
479           
480        }
481
482        void range_check_impl( iterator first, iterator last,
483                               std::bidirectional_iterator_tag )
484        { /* do nothing */ }
485
486        void range_check_impl( iterator first, iterator last,
487                               std::random_access_iterator_tag )
488        {
489            BOOST_ASSERT( first <= last && "out of range unique()/erase_if()" );
490            BOOST_ASSERT( this->begin() <= first && "out of range unique()/erase_if()" );
491            BOOST_ASSERT( last <= this->end() && "out of range unique()/erase_if)(" );             
492        }
493       
494        void range_check( iterator first, iterator last )
495        {
496            range_check_impl( first, last,
497                              BOOST_DEDUCED_TYPENAME iterator_category<iterator>::type() );
498        }
499       
500    public:
501       
502        template< class Compare >
503        void unique( iterator first, iterator last, Compare comp )
504        {
505            range_check(first,last);
506           
507            iterator prev = first;
508            iterator next = first;
509            ++next;
510            for( ; next != last; ++next )
511            {
512                BOOST_ASSERT( !::boost::is_null(prev) );
513                BOOST_ASSERT( !::boost::is_null(next) );
514                if( comp( *prev, *next ) )
515                {
516                    this->remove( next ); // delete object
517                    *next.base() = 0;     // mark pointer as deleted
518                }
519                else
520                {
521                    prev = next;
522                }
523                // ++next
524            }
525
526            compact_and_erase_nulls( first, last );
527        }
528       
529        template< class Compare >
530        void unique( Compare comp )
531        {
532            unique( this->begin(), this->end(), comp );
533        }
534
535        template< class Pred >
536        void erase_if( iterator first, iterator last, Pred pred )
537        {
538            range_check(first,last);
539
540            iterator next = first;
541            for( ; next != last; ++next )
542            {
543                BOOST_ASSERT( !::boost::is_null(next) );
544                if( pred( *next ) )
545                {
546                    this->remove( next ); // delete object
547                    *next.base() = 0;     // mark pointer as deleted
548                }
549            }
550
551            compact_and_erase_nulls( first, last );
552        }
553       
554        template< class Pred >
555        void erase_if( Pred pred )
556        {
557            erase_if( this->begin(), this->end(), pred );
558        }
559
560
561        void merge( iterator first, iterator last,
562                    ptr_sequence_adapter& from )
563        {
564             merge( first, last, from, std::less<T>() );
565        }
566       
567        template< class BinPred >
568        void merge( iterator first, iterator last,
569                    ptr_sequence_adapter& from, BinPred pred )
570        {
571            void_ptr_indirect_fun<BinPred,T>  bin_pred(pred);
572            size_type                         current_size = this->size();
573            this->transfer( this->end(), first, last, from );
574            typename base_type::ptr_iterator middle = this->begin().base();
575            std::advance(middle,current_size);
576            std::inplace_merge( this->begin().base(),
577                                middle,
578                                this->end().base(),
579                                bin_pred );
580        }
581       
582        void merge( ptr_sequence_adapter& r )
583        {
584            merge( r, std::less<T>() );
585            BOOST_ASSERT( r.empty() );
586        }
587       
588        template< class BinPred >
589        void merge( ptr_sequence_adapter& r, BinPred pred )
590        {
591            merge( r.begin(), r.end(), r, pred );
592            BOOST_ASSERT( r.empty() );   
593        }
594
595    };
596
597
598} // namespace 'boost' 
599
600#endif
Note: See TracBrowser for help on using the repository browser.