multi_index/detail/rnd_index_ops.hpp

0001 /* Copyright 2003-2015 Joaquin M Lopez Munoz.
0002  * Distributed under the Boost Software License, Version 1.0.
0003  * (See accompanying file LICENSE_1_0.txt or copy at
0004  * http://www.boost.org/LICENSE_1_0.txt)
0005  *
0006  * See http://www.boost.org/libs/multi_index for library home page.
0007  */
0008
0009 #ifndef BOOST_MULTI_INDEX_DETAIL_RND_INDEX_OPS_HPP
0010 #define BOOST_MULTI_INDEX_DETAIL_RND_INDEX_OPS_HPP
0011
0012 #if defined(_MSC_VER)
0013 #pragma once
0014 #endif
0015
0016 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
0017 #include <algorithm>
0018 #include <boost/multi_index/detail/rnd_index_ptr_array.hpp>
0019
0020 namespace boost{
0021
0022 namespace multi_index{
0023
0024 namespace detail{
0025
0026 /* Common code for random_access_index memfuns having templatized and
0027  * non-templatized versions.
0028  */
0029
0030 template<typename Node,typename Allocator,typename Predicate>
0031 Node* random_access_index_remove(
0032   random_access_index_ptr_array<Allocator>& ptrs,Predicate pred)
0033 {
0034   typedef typename Node::value_type value_type;
0035   typedef typename Node::impl_ptr_pointer impl_ptr_pointer;
0036
0037   impl_ptr_pointer first=ptrs.begin(),
0038                    res=first,
0039                    last=ptrs.end();
0040   for(;first!=last;++first){
0041     if(!pred(
0042         const_cast<const value_type&>(Node::from_impl(*first)->value()))){
0043       if(first!=res){
0044         std::swap(*first,*res);
0045         (*first)->up()=first;
0046         (*res)->up()=res;
0047       }
0048       ++res;
0049     }
0050   }
0051   return Node::from_impl(*res);
0052 }
0053
0054 template<typename Node,typename Allocator,class BinaryPredicate>
0055 Node* random_access_index_unique(
0056   random_access_index_ptr_array<Allocator>& ptrs,BinaryPredicate binary_pred)
0057 {
0058   typedef typename Node::value_type       value_type;
0059   typedef typename Node::impl_ptr_pointer impl_ptr_pointer;
0060
0061   impl_ptr_pointer first=ptrs.begin(),
0062                    res=first,
0063                    last=ptrs.end();
0064   if(first!=last){
0065     for(;++first!=last;){
0066       if(!binary_pred(
0067            const_cast<const value_type&>(Node::from_impl(*res)->value()),
0068            const_cast<const value_type&>(Node::from_impl(*first)->value()))){
0069         ++res;
0070         if(first!=res){
0071           std::swap(*first,*res);
0072           (*first)->up()=first;
0073           (*res)->up()=res;
0074         }
0075       }
0076     }
0077     ++res;
0078   }
0079   return Node::from_impl(*res);
0080 }
0081
0082 template<typename Node,typename Allocator,typename Compare>
0083 void random_access_index_inplace_merge(
0084   const Allocator& al,
0085   random_access_index_ptr_array<Allocator>& ptrs,
0086   BOOST_DEDUCED_TYPENAME Node::impl_ptr_pointer first1,Compare comp)
0087 {
0088   typedef typename Node::value_type       value_type;
0089   typedef typename Node::impl_pointer     impl_pointer;
0090   typedef typename Node::impl_ptr_pointer impl_ptr_pointer;
0091
0092   auto_space<impl_pointer,Allocator> spc(al,ptrs.size());
0093
0094   impl_ptr_pointer first0=ptrs.begin(),
0095                    last0=first1,
0096                    last1=ptrs.end(),
0097                    out=spc.data();
0098   while(first0!=last0&&first1!=last1){
0099     if(comp(
0100         const_cast<const value_type&>(Node::from_impl(*first1)->value()),
0101         const_cast<const value_type&>(Node::from_impl(*first0)->value()))){
0102       *out++=*first1++;
0103     }
0104     else{
0105       *out++=*first0++;
0106     }
0107   }
0108   std::copy(&*first0,&*last0,&*out);
0109   std::copy(&*first1,&*last1,&*out);
0110
0111   first1=ptrs.begin();
0112   out=spc.data();
0113   while(first1!=last1){
0114     *first1=*out++;
0115     (*first1)->up()=first1;
0116     ++first1;
0117   }
0118 }
0119
0120 /* sorting */
0121
0122 /* auxiliary stuff */
0123
0124 template<typename Node,typename Compare>
0125 struct random_access_index_sort_compare
0126 {
0127   typedef typename Node::impl_pointer first_argument_type;
0128   typedef typename Node::impl_pointer second_argument_type;
0129   typedef bool                        result_type;
0130
0131   random_access_index_sort_compare(Compare comp_=Compare()):comp(comp_){}
0132
0133   bool operator()(
0134     typename Node::impl_pointer x,typename Node::impl_pointer y)const
0135   {
0136     typedef typename Node::value_type value_type;
0137
0138     return comp(
0139       const_cast<const value_type&>(Node::from_impl(x)->value()),
0140       const_cast<const value_type&>(Node::from_impl(y)->value()));
0141   }
0142
0143 private:
0144   Compare comp;
0145 };
0146
0147 template<typename Node,typename Allocator,class Compare>
0148 void random_access_index_sort(
0149   const Allocator& al,
0150   random_access_index_ptr_array<Allocator>& ptrs,
0151   Compare comp)
0152 {
0153   /* The implementation is extremely simple: an auxiliary
0154    * array of pointers is sorted using stdlib facilities and
0155    * then used to rearrange the index. This is suboptimal
0156    * in space and time, but has some advantages over other
0157    * possible approaches:
0158    *   - Use std::stable_sort() directly on ptrs using some
0159    *     special iterator in charge of maintaining pointers
0160    *     and up() pointers in sync: we cannot guarantee
0161    *     preservation of the container invariants in the face of
0162    *     exceptions, if, for instance, std::stable_sort throws
0163    *     when ptrs transitorily contains duplicate elements.
0164    *   - Rewrite the internal algorithms of std::stable_sort
0165    *     adapted for this case: besides being a fair amount of
0166    *     work, making a stable sort compatible with Boost.MultiIndex
0167    *     invariants (basically, no duplicates or missing elements
0168    *     even if an exception is thrown) is complicated, error-prone
0169    *     and possibly won't perform much better than the
0170    *     solution adopted.
0171    */
0172
0173   if(ptrs.size()<=1)return;
0174
0175   typedef typename Node::impl_pointer       impl_pointer;
0176   typedef typename Node::impl_ptr_pointer   impl_ptr_pointer;
0177   typedef random_access_index_sort_compare<
0178     Node,Compare>                           ptr_compare;
0179
0180   impl_ptr_pointer   first=ptrs.begin();
0181   impl_ptr_pointer   last=ptrs.end();
0182   auto_space<
0183     impl_pointer,
0184     Allocator>       spc(al,ptrs.size());
0185   impl_ptr_pointer   buf=spc.data();
0186
0187   std::copy(&*first,&*last,&*buf);
0188   std::stable_sort(&*buf,&*buf+ptrs.size(),ptr_compare(comp));
0189
0190   while(first!=last){
0191     *first=*buf++;
0192     (*first)->up()=first;
0193     ++first;
0194   }
0195 }
0196
0197 } /* namespace multi_index::detail */
0198
0199 } /* namespace multi_index */
0200
0201 } /* namespace boost */
0202
0203 #endif