boost/ptr_container/ptr_set_adapter.hpp

   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_SET_ADAPTER_HPP
  13 #define BOOST_PTR_CONTAINER_PTR_SET_ADAPTER_HPP
  14
  15 #if defined(_MSC_VER) && (_MSC_VER >= 1200)
  16 # pragma once
  17 #endif
  18
  19 #include <boost/ptr_container/detail/associative_ptr_container.hpp>
  20 #include <boost/ptr_container/detail/meta_functions.hpp>
  21 #include <boost/ptr_container/detail/void_ptr_iterator.hpp>
  22 #include <boost/range/iterator_range.hpp>
  23
  24 namespace boost
  25 {
  26 namespace ptr_container_detail
  27 {
  28     template
  29     <
  30         class Key,
  31         class VoidPtrSet,
  32         bool  Ordered
  33     >
  34     struct set_config
  35     {
  36        typedef VoidPtrSet
  37                     void_container_type;
  38
  39        typedef BOOST_DEDUCED_TYPENAME VoidPtrSet::allocator_type
  40                     allocator_type;
  41
  42        typedef Key  value_type;
  43
  44        typedef value_type
  45                     key_type;
  46
  47        typedef BOOST_DEDUCED_TYPENAME
  48            mpl::eval_if_c<Ordered,
  49                           select_value_compare<VoidPtrSet>,
  50                           mpl::identity<void> >::type
  51                     value_compare;
  52
  53        typedef value_compare
  54                     key_compare;
  55
  56        typedef BOOST_DEDUCED_TYPENAME
  57            mpl::eval_if_c<Ordered,
  58                           mpl::identity<void>,
  59                           select_hasher<VoidPtrSet> >::type
  60                     hasher;
  61
  62        typedef BOOST_DEDUCED_TYPENAME
  63            mpl::eval_if_c<Ordered,
  64                           mpl::identity<void>,
  65                           select_key_equal<VoidPtrSet> >::type
  66                     key_equal;
  67
  68        typedef BOOST_DEDUCED_TYPENAME
  69            mpl::if_c<Ordered,
  70                      ordered_associative_container_tag,
  71                      unordered_associative_container_tag>::type
  72                     container_type;
  73
  74        typedef void_ptr_iterator<
  75                        BOOST_DEDUCED_TYPENAME VoidPtrSet::iterator, Key >
  76                     iterator;
  77
  78        typedef void_ptr_iterator<
  79                         BOOST_DEDUCED_TYPENAME VoidPtrSet::const_iterator, const Key >
  80                     const_iterator;
  81
  82        typedef void_ptr_iterator<
  83            BOOST_DEDUCED_TYPENAME
  84              mpl::eval_if_c<Ordered,
  85                             select_iterator<VoidPtrSet>,
  86                             select_local_iterator<VoidPtrSet> >::type,
  87              Key >
  88                     local_iterator;
  89
  90        typedef void_ptr_iterator<
  91            BOOST_DEDUCED_TYPENAME
  92              mpl::eval_if_c<Ordered,
  93                             select_iterator<VoidPtrSet>,
  94                             select_const_local_iterator<VoidPtrSet> >::type,
  95              const Key >
  96                     const_local_iterator;
  97
  98        template< class Iter >
  99        static Key* get_pointer( Iter i )
 100        {
 101            return static_cast<Key*>( *i.base() );
 102        }
 103
 104        template< class Iter >
 105        static const Key* get_const_pointer( Iter i )
 106        {
 107            return static_cast<const Key*>( *i.base() );
 108        }
 109
 110        BOOST_STATIC_CONSTANT(bool, allow_null = false );
 111     };
 112
 113
 114
 115     template
 116     <
 117         class Key,
 118         class VoidPtrSet,
 119         class CloneAllocator = heap_clone_allocator,
 120         bool  Ordered        = true
 121     >
 122     class ptr_set_adapter_base
 123         : public ptr_container_detail::associative_ptr_container< set_config<Key,VoidPtrSet,Ordered>,
 124                                                       CloneAllocator >
 125     {
 126         typedef ptr_container_detail::associative_ptr_container< set_config<Key,VoidPtrSet,Ordered>,
 127                                                      CloneAllocator >
 128               base_type;
 129     public:
 130         typedef BOOST_DEDUCED_TYPENAME base_type::iterator
 131                       iterator;
 132         typedef BOOST_DEDUCED_TYPENAME base_type::const_iterator
 133                       const_iterator;
 134         typedef Key   key_type;
 135         typedef BOOST_DEDUCED_TYPENAME base_type::size_type
 136                       size_type;
 137
 138     public:
 139         ptr_set_adapter_base()
 140         { }
 141
 142         template< class SizeType >
 143         ptr_set_adapter_base( SizeType n,
 144                               ptr_container_detail::unordered_associative_container_tag tag )
 145           : base_type( n, tag )
 146         { }
 147
 148         template< class Compare, class Allocator >
 149         ptr_set_adapter_base( const Compare& comp,
 150                               const Allocator& a )
 151          : base_type( comp, a )
 152         { }
 153
 154         template< class Hash, class Pred, class Allocator >
 155         ptr_set_adapter_base( const Hash& hash,
 156                               const Pred& pred,
 157                               const Allocator& a )
 158          : base_type( hash, pred, a )
 159         { }
 160
 161         template< class InputIterator, class Compare, class Allocator >
 162         ptr_set_adapter_base( InputIterator first, InputIterator last,
 163                               const Compare& comp,
 164                               const Allocator& a )
 165          : base_type( first, last, comp, a )
 166         { }
 167
 168         template< class InputIterator, class Hash, class Pred, class Allocator >
 169         ptr_set_adapter_base( InputIterator first, InputIterator last,
 170                               const Hash& hash,
 171                               const Pred& pred,
 172                               const Allocator& a )
 173          : base_type( first, last, hash, pred, a )
 174         { }
 175
 176         template< class U, class Set, class CA, bool b >
 177         ptr_set_adapter_base( const ptr_set_adapter_base<U,Set,CA,b>& r )
 178           : base_type( r )
 179         { }
 180
 181         ptr_set_adapter_base( const ptr_set_adapter_base& r )
 182           : base_type( r )
 183         { }
 184
 185         template< class PtrContainer >
 186         explicit ptr_set_adapter_base( std::auto_ptr<PtrContainer> clone )
 187          : base_type( clone )
 188         { }
 189
 190         ptr_set_adapter_base& operator=( ptr_set_adapter_base r )
 191         {
 192             this->swap( r );
 193             return *this;
 194         }
 195
 196         template< typename PtrContainer >
 197         ptr_set_adapter_base& operator=( std::auto_ptr<PtrContainer> clone )
 198         {
 199             base_type::operator=( clone );
 200             return *this;
 201         }
 202
 203         using base_type::erase;
 204
 205         size_type erase( const key_type& x ) // nothrow
 206         {
 207             key_type* key = const_cast<key_type*>(&x);
 208             iterator i( this->base().find( key ) );
 209             if( i == this->end() )                                  // nothrow
 210                 return 0u;                                          // nothrow
 211             key = static_cast<key_type*>(*i.base());                // nothrow
 212             size_type res = this->base().erase( key );              // nothrow
 213             this->remove( key );                                    // nothrow
 214             return res;
 215         }
 216
 217
 218         iterator find( const key_type& x )
 219         {
 220             return iterator( this->base().
 221                              find( const_cast<key_type*>(&x) ) );
 222         }
 223
 224         const_iterator find( const key_type& x ) const
 225         {
 226             return const_iterator( this->base().
 227                                    find( const_cast<key_type*>(&x) ) );
 228         }
 229
 230         size_type count( const key_type& x ) const
 231         {
 232             return this->base().count( const_cast<key_type*>(&x) );
 233         }
 234
 235         iterator lower_bound( const key_type& x )
 236         {
 237             return iterator( this->base().
 238                              lower_bound( const_cast<key_type*>(&x) ) );
 239         }
 240
 241         const_iterator lower_bound( const key_type& x ) const
 242         {
 243             return const_iterator( this->base().
 244                                    lower_bound( const_cast<key_type*>(&x) ) );
 245         }
 246
 247         iterator upper_bound( const key_type& x )
 248         {
 249             return iterator( this->base().
 250                              upper_bound( const_cast<key_type*>(&x) ) );
 251         }
 252
 253         const_iterator upper_bound( const key_type& x ) const
 254         {
 255             return const_iterator( this->base().
 256                                    upper_bound( const_cast<key_type*>(&x) ) );
 257         }
 258
 259         iterator_range<iterator> equal_range( const key_type& x )
 260         {
 261             std::pair<BOOST_DEDUCED_TYPENAME base_type::ptr_iterator,
 262                       BOOST_DEDUCED_TYPENAME base_type::ptr_iterator>
 263                 p = this->base().
 264                 equal_range( const_cast<key_type*>(&x) );
 265             return make_iterator_range( iterator( p.first ),
 266                                         iterator( p.second ) );
 267         }
 268
 269         iterator_range<const_iterator> equal_range( const key_type& x ) const
 270         {
 271             std::pair<BOOST_DEDUCED_TYPENAME base_type::ptr_const_iterator,
 272                       BOOST_DEDUCED_TYPENAME base_type::ptr_const_iterator>
 273                 p = this->base().
 274                 equal_range( const_cast<key_type*>(&x) );
 275             return make_iterator_range( const_iterator( p.first ),
 276                                         const_iterator( p.second ) );
 277         }
 278
 279     protected:
 280         size_type bucket( const key_type& key ) const
 281         {
 282             return this->base().bucket( const_cast<key_type*>(&key) );
 283         }
 284     };
 285
 286 } // ptr_container_detail
 287
 288     /////////////////////////////////////////////////////////////////////////
 289     // ptr_set_adapter
 290     /////////////////////////////////////////////////////////////////////////
 291
 292     template
 293     <
 294         class Key,
 295         class VoidPtrSet,
 296         class CloneAllocator = heap_clone_allocator,
 297         bool  Ordered        = true
 298     >
 299     class ptr_set_adapter :
 300         public ptr_container_detail::ptr_set_adapter_base<Key,VoidPtrSet,CloneAllocator,Ordered>
 301     {
 302         typedef ptr_container_detail::ptr_set_adapter_base<Key,VoidPtrSet,CloneAllocator,Ordered>
 303             base_type;
 304
 305     public: // typedefs
 306
 307         typedef BOOST_DEDUCED_TYPENAME base_type::iterator
 308                      iterator;
 309         typedef BOOST_DEDUCED_TYPENAME base_type::const_iterator
 310                      const_iterator;
 311         typedef BOOST_DEDUCED_TYPENAME base_type::size_type
 312                      size_type;
 313         typedef Key  key_type;
 314         typedef BOOST_DEDUCED_TYPENAME base_type::auto_type
 315                      auto_type;
 316         typedef BOOST_DEDUCED_TYPENAME VoidPtrSet::allocator_type
 317                      allocator_type;
 318     private:
 319
 320         template< typename II >
 321         void set_basic_clone_and_insert( II first, II last ) // basic
 322         {
 323             while( first != last )
 324             {
 325                 if( this->find( *first ) == this->end() )
 326                     insert( CloneAllocator::allocate_clone( *first ) ); // strong, commit
 327                 ++first;
 328             }
 329         }
 330
 331     public:
 332         ptr_set_adapter()
 333         { }
 334
 335         template< class SizeType >
 336         ptr_set_adapter( SizeType n,
 337                          ptr_container_detail::unordered_associative_container_tag tag )
 338           : base_type( n, tag )
 339         { }
 340
 341         template< class Comp >
 342         explicit ptr_set_adapter( const Comp& comp,
 343                                   const allocator_type& a )
 344           : base_type( comp, a )
 345         {
 346             BOOST_ASSERT( this->empty() );
 347         }
 348
 349         template< class Hash, class Pred, class Allocator >
 350         ptr_set_adapter( const Hash& hash,
 351                          const Pred& pred,
 352                          const Allocator& a )
 353          : base_type( hash, pred, a )
 354         { }
 355
 356         template< class InputIterator >
 357         ptr_set_adapter( InputIterator first, InputIterator last )
 358          : base_type( first, last )
 359         { }
 360
 361         template< class InputIterator, class Compare, class Allocator >
 362         ptr_set_adapter( InputIterator first, InputIterator last,
 363                          const Compare& comp,
 364                          const Allocator a = Allocator() )
 365           : base_type( comp, a )
 366         {
 367             BOOST_ASSERT( this->empty() );
 368             set_basic_clone_and_insert( first, last );
 369         }
 370
 371         template< class InputIterator, class Hash, class Pred, class Allocator >
 372         ptr_set_adapter( InputIterator first, InputIterator last,
 373                          const Hash& hash,
 374                          const Pred& pred,
 375                          const Allocator& a )
 376           : base_type( first, last, hash, pred, a )
 377         { }
 378
 379         explicit ptr_set_adapter( const ptr_set_adapter& r )
 380           : base_type( r )
 381         { }
 382
 383         template< class U, class Set, class CA, bool b >
 384         explicit ptr_set_adapter( const ptr_set_adapter<U,Set,CA,b>& r )
 385           : base_type( r )
 386         { }
 387
 388         template< class PtrContainer >
 389         explicit ptr_set_adapter( std::auto_ptr<PtrContainer> clone )
 390          : base_type( clone )
 391         { }
 392
 393         template< class U, class Set, class CA, bool b >
 394         ptr_set_adapter& operator=( const ptr_set_adapter<U,Set,CA,b>& r )
 395         {
 396             base_type::operator=( r );
 397             return *this;
 398         }
 399
 400         template< class T >
 401         void operator=( std::auto_ptr<T> r )
 402         {
 403             base_type::operator=( r );
 404         }
 405
 406         std::pair<iterator,bool> insert( key_type* x ) // strong
 407         {
 408             this->enforce_null_policy( x, "Null pointer in 'ptr_set::insert()'" );
 409
 410             auto_type ptr( x );
 411             std::pair<BOOST_DEDUCED_TYPENAME base_type::ptr_iterator,bool>
 412                  res = this->base().insert( x );
 413             if( res.second )
 414                 ptr.release();
 415             return std::make_pair( iterator( res.first ), res.second );
 416         }
 417
 418         template< class U >
 419         std::pair<iterator,bool> insert( std::auto_ptr<U> x )
 420         {
 421             return insert( x.release() );
 422         }
 423
 424
 425         iterator insert( iterator where, key_type* x ) // strong
 426         {
 427             this->enforce_null_policy( x, "Null pointer in 'ptr_set::insert()'" );
 428
 429             auto_type ptr( x );
 430             BOOST_DEDUCED_TYPENAME base_type::ptr_iterator
 431                 res = this->base().insert( where.base(), x );
 432             if( *res == x )
 433                 ptr.release();
 434             return iterator( res);
 435         }
 436
 437         template< class U >
 438         iterator insert( iterator where, std::auto_ptr<U> x )
 439         {
 440             return insert( where, x.release() );
 441         }
 442
 443         template< typename InputIterator >
 444         void insert( InputIterator first, InputIterator last ) // basic
 445         {
 446             set_basic_clone_and_insert( first, last );
 447         }
 448
 449 #if defined(BOOST_NO_SFINAE) || defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)
 450 #else
 451
 452         template< class Range >
 453         BOOST_DEDUCED_TYPENAME
 454         boost::disable_if< ptr_container_detail::is_pointer_or_integral<Range> >::type
 455         insert( const Range& r )
 456         {
 457             insert( boost::begin(r), boost::end(r) );
 458         }
 459
 460 #endif
 461
 462         template< class PtrSetAdapter >
 463         bool transfer( BOOST_DEDUCED_TYPENAME PtrSetAdapter::iterator object,
 464                        PtrSetAdapter& from ) // strong
 465         {
 466             return this->single_transfer( object, from );
 467         }
 468
 469         template< class PtrSetAdapter >
 470         size_type
 471         transfer( BOOST_DEDUCED_TYPENAME PtrSetAdapter::iterator first,
 472                   BOOST_DEDUCED_TYPENAME PtrSetAdapter::iterator last,
 473                   PtrSetAdapter& from ) // basic
 474         {
 475             return this->single_transfer( first, last, from );
 476         }
 477
 478 #if defined(BOOST_NO_SFINAE) || defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)
 479 #else
 480
 481         template< class PtrSetAdapter, class Range >
 482         BOOST_DEDUCED_TYPENAME boost::disable_if< boost::is_same< Range,
 483                             BOOST_DEDUCED_TYPENAME PtrSetAdapter::iterator >,
 484                                                             size_type >::type
 485         transfer( const Range& r, PtrSetAdapter& from ) // basic
 486         {
 487             return transfer( boost::begin(r), boost::end(r), from );
 488         }
 489
 490 #endif
 491
 492         template< class PtrSetAdapter >
 493         size_type transfer( PtrSetAdapter& from ) // basic
 494         {
 495             return transfer( from.begin(), from.end(), from );
 496         }
 497
 498     };
 499
 500     /////////////////////////////////////////////////////////////////////////
 501     // ptr_multiset_adapter
 502     /////////////////////////////////////////////////////////////////////////
 503
 504     template
 505     <
 506         class Key,
 507         class VoidPtrMultiSet,
 508         class CloneAllocator = heap_clone_allocator,
 509         bool Ordered         = true
 510     >
 511     class ptr_multiset_adapter :
 512         public ptr_container_detail::ptr_set_adapter_base<Key,VoidPtrMultiSet,CloneAllocator,Ordered>
 513     {
 514          typedef ptr_container_detail::ptr_set_adapter_base<Key,VoidPtrMultiSet,CloneAllocator,Ordered> base_type;
 515
 516     public: // typedefs
 517
 518         typedef BOOST_DEDUCED_TYPENAME base_type::iterator
 519                        iterator;
 520         typedef BOOST_DEDUCED_TYPENAME base_type::size_type
 521                        size_type;
 522         typedef Key    key_type;
 523         typedef BOOST_DEDUCED_TYPENAME base_type::auto_type
 524                        auto_type;
 525         typedef BOOST_DEDUCED_TYPENAME VoidPtrMultiSet::allocator_type
 526                        allocator_type;
 527     private:
 528         template< typename II >
 529         void set_basic_clone_and_insert( II first, II last ) // basic
 530         {
 531             while( first != last )
 532             {
 533                 insert( CloneAllocator::allocate_clone( *first ) ); // strong, commit
 534                 ++first;
 535             }
 536         }
 537
 538     public:
 539         ptr_multiset_adapter()
 540         { }
 541
 542         template< class SizeType >
 543         ptr_multiset_adapter( SizeType n,
 544                               ptr_container_detail::unordered_associative_container_tag tag )
 545           : base_type( n, tag )
 546         { }
 547
 548         template< class Comp >
 549         explicit ptr_multiset_adapter( const Comp& comp,
 550                                        const allocator_type& a )
 551         : base_type( comp, a )
 552         { }
 553
 554         template< class Hash, class Pred, class Allocator >
 555         ptr_multiset_adapter( const Hash& hash,
 556                               const Pred& pred,
 557                               const Allocator& a )
 558          : base_type( hash, pred, a )
 559         { }
 560
 561         template< class InputIterator >
 562         ptr_multiset_adapter( InputIterator first, InputIterator last )
 563          : base_type( first, last )
 564         { }
 565
 566         template< class InputIterator, class Comp >
 567         ptr_multiset_adapter( InputIterator first, InputIterator last,
 568                               const Comp& comp,
 569                               const allocator_type& a = allocator_type() )
 570         : base_type( comp, a )
 571         {
 572             set_basic_clone_and_insert( first, last );
 573         }
 574
 575         template< class InputIterator, class Hash, class Pred, class Allocator >
 576         ptr_multiset_adapter( InputIterator first, InputIterator last,
 577                               const Hash& hash,
 578                               const Pred& pred,
 579                               const Allocator& a )
 580          : base_type( first, last, hash, pred, a )
 581         { }
 582
 583         template< class U, class Set, class CA, bool b >
 584         explicit ptr_multiset_adapter( const ptr_multiset_adapter<U,Set,CA,b>& r )
 585           : base_type( r )
 586         { }
 587
 588         template< class PtrContainer >
 589         explicit ptr_multiset_adapter( std::auto_ptr<PtrContainer> clone )
 590          : base_type( clone )
 591         { }
 592
 593         template< class U, class Set, class CA, bool b >
 594         ptr_multiset_adapter& operator=( const ptr_multiset_adapter<U,Set,CA,b>& r )
 595         {
 596             base_type::operator=( r );
 597             return *this;
 598         }
 599
 600         template< class T >
 601         void operator=( std::auto_ptr<T> r )
 602         {
 603             base_type::operator=( r );
 604         }
 605
 606         iterator insert( iterator before, key_type* x ) // strong
 607         {
 608             return base_type::insert( before, x );
 609         }
 610
 611         template< class U >
 612         iterator insert( iterator before, std::auto_ptr<U> x )
 613         {
 614             return insert( before, x.release() );
 615         }
 616
 617         iterator insert( key_type* x ) // strong
 618         {
 619             this->enforce_null_policy( x, "Null pointer in 'ptr_multiset::insert()'" );
 620
 621             auto_type ptr( x );
 622             BOOST_DEDUCED_TYPENAME base_type::ptr_iterator
 623                  res = this->base().insert( x );
 624             ptr.release();
 625             return iterator( res );
 626         }
 627
 628         template< class U >
 629         iterator insert( std::auto_ptr<U> x )
 630         {
 631             return insert( x.release() );
 632         }
 633
 634         template< typename InputIterator >
 635         void insert( InputIterator first, InputIterator last ) // basic
 636         {
 637             set_basic_clone_and_insert( first, last );
 638         }
 639
 640 #if defined(BOOST_NO_SFINAE) || defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)
 641 #else
 642
 643         template< class Range >
 644         BOOST_DEDUCED_TYPENAME
 645         boost::disable_if< ptr_container_detail::is_pointer_or_integral<Range> >::type
 646         insert( const Range& r )
 647         {
 648             insert( boost::begin(r), boost::end(r) );
 649         }
 650
 651 #endif
 652
 653         template< class PtrSetAdapter >
 654         void transfer( BOOST_DEDUCED_TYPENAME PtrSetAdapter::iterator object,
 655                        PtrSetAdapter& from ) // strong
 656         {
 657             this->multi_transfer( object, from );
 658         }
 659
 660         template< class PtrSetAdapter >
 661         size_type transfer( BOOST_DEDUCED_TYPENAME PtrSetAdapter::iterator first,
 662                             BOOST_DEDUCED_TYPENAME PtrSetAdapter::iterator last,
 663                             PtrSetAdapter& from ) // basic
 664         {
 665             return this->multi_transfer( first, last, from );
 666         }
 667
 668 #if defined(BOOST_NO_SFINAE) || defined(BOOST_NO_FUNCTION_TEMPLATE_ORDERING)
 669 #else
 670
 671         template< class PtrSetAdapter, class Range >
 672         BOOST_DEDUCED_TYPENAME boost::disable_if< boost::is_same< Range,
 673                        BOOST_DEDUCED_TYPENAME PtrSetAdapter::iterator >, size_type >::type
 674         transfer(  const Range& r, PtrSetAdapter& from ) // basic
 675         {
 676             return transfer( boost::begin(r), boost::end(r), from );
 677         }
 678
 679 #endif
 680
 681         template< class PtrSetAdapter >
 682         void transfer( PtrSetAdapter& from ) // basic
 683         {
 684             transfer( from.begin(), from.end(), from );
 685             BOOST_ASSERT( from.empty() );
 686         }
 687
 688     };
 689
 690 } // namespace 'boost'
 691
 692 #endif