Chris@101: /* Copyright 2003-2015 Joaquin M Lopez Munoz.
Chris@16:  * Distributed under the Boost Software License, Version 1.0.
Chris@16:  * (See accompanying file LICENSE_1_0.txt or copy at
Chris@16:  * http://www.boost.org/LICENSE_1_0.txt)
Chris@16:  *
Chris@16:  * See http://www.boost.org/libs/multi_index for library home page.
Chris@16:  */
Chris@16: 
Chris@16: #ifndef BOOST_MULTI_INDEX_DETAIL_RND_INDEX_OPS_HPP
Chris@16: #define BOOST_MULTI_INDEX_DETAIL_RND_INDEX_OPS_HPP
Chris@16: 
Chris@101: #if defined(_MSC_VER)
Chris@16: #pragma once
Chris@16: #endif
Chris@16: 
Chris@16: #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
Chris@16: #include <algorithm>
Chris@16: #include <boost/multi_index/detail/rnd_index_ptr_array.hpp>
Chris@16: #include <functional>
Chris@16: 
Chris@16: namespace boost{
Chris@16: 
Chris@16: namespace multi_index{
Chris@16: 
Chris@16: namespace detail{
Chris@16: 
Chris@16: /* Common code for random_access_index memfuns having templatized and
Chris@16:  * non-templatized versions.
Chris@16:  */
Chris@16: 
Chris@16: template<typename Node,typename Allocator,typename Predicate>
Chris@16: Node* random_access_index_remove(
Chris@101:   random_access_index_ptr_array<Allocator>& ptrs,Predicate pred)
Chris@16: {
Chris@16:   typedef typename Node::value_type value_type;
Chris@16:   typedef typename Node::impl_ptr_pointer impl_ptr_pointer;
Chris@16: 
Chris@16:   impl_ptr_pointer first=ptrs.begin(),
Chris@16:                    res=first,
Chris@16:                    last=ptrs.end();
Chris@16:   for(;first!=last;++first){
Chris@16:     if(!pred(
Chris@16:         const_cast<const value_type&>(Node::from_impl(*first)->value()))){
Chris@16:       if(first!=res){
Chris@16:         std::swap(*first,*res);
Chris@16:         (*first)->up()=first;
Chris@16:         (*res)->up()=res;
Chris@16:       }
Chris@16:       ++res;
Chris@16:     }
Chris@16:   }
Chris@16:   return Node::from_impl(*res);
Chris@16: }
Chris@16: 
Chris@16: template<typename Node,typename Allocator,class BinaryPredicate>
Chris@16: Node* random_access_index_unique(
Chris@101:   random_access_index_ptr_array<Allocator>& ptrs,BinaryPredicate binary_pred)
Chris@16: {
Chris@16:   typedef typename Node::value_type       value_type;
Chris@16:   typedef typename Node::impl_ptr_pointer impl_ptr_pointer;
Chris@16: 
Chris@16:   impl_ptr_pointer first=ptrs.begin(),
Chris@16:                    res=first,
Chris@16:                    last=ptrs.end();
Chris@16:   if(first!=last){
Chris@16:     for(;++first!=last;){
Chris@16:       if(!binary_pred(
Chris@16:            const_cast<const value_type&>(Node::from_impl(*res)->value()),
Chris@16:            const_cast<const value_type&>(Node::from_impl(*first)->value()))){
Chris@16:         ++res;
Chris@16:         if(first!=res){
Chris@16:           std::swap(*first,*res);
Chris@16:           (*first)->up()=first;
Chris@16:           (*res)->up()=res;
Chris@16:         }
Chris@16:       }
Chris@16:     }
Chris@16:     ++res;
Chris@16:   }
Chris@16:   return Node::from_impl(*res);
Chris@16: }
Chris@16: 
Chris@16: template<typename Node,typename Allocator,typename Compare>
Chris@16: void random_access_index_inplace_merge(
Chris@16:   const Allocator& al,
Chris@16:   random_access_index_ptr_array<Allocator>& ptrs,
Chris@101:   BOOST_DEDUCED_TYPENAME Node::impl_ptr_pointer first1,Compare comp)
Chris@16: {
Chris@16:   typedef typename Node::value_type       value_type;
Chris@16:   typedef typename Node::impl_pointer     impl_pointer;
Chris@16:   typedef typename Node::impl_ptr_pointer impl_ptr_pointer;
Chris@16: 
Chris@16:   auto_space<impl_pointer,Allocator> spc(al,ptrs.size());
Chris@16: 
Chris@16:   impl_ptr_pointer first0=ptrs.begin(),
Chris@16:                    last0=first1,
Chris@16:                    last1=ptrs.end(),
Chris@16:                    out=spc.data();
Chris@16:   while(first0!=last0&&first1!=last1){
Chris@16:     if(comp(
Chris@16:         const_cast<const value_type&>(Node::from_impl(*first1)->value()),
Chris@16:         const_cast<const value_type&>(Node::from_impl(*first0)->value()))){
Chris@16:       *out++=*first1++;
Chris@16:     }
Chris@16:     else{
Chris@16:       *out++=*first0++;
Chris@16:     }
Chris@16:   }
Chris@16:   std::copy(&*first0,&*last0,&*out);
Chris@16:   std::copy(&*first1,&*last1,&*out);
Chris@16: 
Chris@16:   first1=ptrs.begin();
Chris@16:   out=spc.data();
Chris@16:   while(first1!=last1){
Chris@16:     *first1=*out++;
Chris@16:     (*first1)->up()=first1;
Chris@16:     ++first1;
Chris@16:   }
Chris@16: }
Chris@16: 
Chris@16: /* sorting */
Chris@16: 
Chris@16: /* auxiliary stuff */
Chris@16: 
Chris@16: template<typename Node,typename Compare>
Chris@16: struct random_access_index_sort_compare:
Chris@16:   std::binary_function<
Chris@16:     typename Node::impl_pointer,
Chris@16:     typename Node::impl_pointer,bool>
Chris@16: {
Chris@16:   random_access_index_sort_compare(Compare comp_=Compare()):comp(comp_){}
Chris@16: 
Chris@16:   bool operator()(
Chris@16:     typename Node::impl_pointer x,typename Node::impl_pointer y)const
Chris@16:   {
Chris@16:     typedef typename Node::value_type value_type;
Chris@16: 
Chris@16:     return comp(
Chris@16:       const_cast<const value_type&>(Node::from_impl(x)->value()),
Chris@16:       const_cast<const value_type&>(Node::from_impl(y)->value()));
Chris@16:   }
Chris@16: 
Chris@16: private:
Chris@16:   Compare comp;
Chris@16: };
Chris@16: 
Chris@16: template<typename Node,typename Allocator,class Compare>
Chris@16: void random_access_index_sort(
Chris@16:   const Allocator& al,
Chris@16:   random_access_index_ptr_array<Allocator>& ptrs,
Chris@101:   Compare comp)
Chris@16: {
Chris@16:   /* The implementation is extremely simple: an auxiliary
Chris@16:    * array of pointers is sorted using stdlib facilities and
Chris@16:    * then used to rearrange the index. This is suboptimal
Chris@16:    * in space and time, but has some advantages over other
Chris@16:    * possible approaches:
Chris@16:    *   - Use std::stable_sort() directly on ptrs using some
Chris@16:    *     special iterator in charge of maintaining pointers
Chris@16:    *     and up() pointers in sync: we cannot guarantee
Chris@16:    *     preservation of the container invariants in the face of
Chris@16:    *     exceptions, if, for instance, std::stable_sort throws
Chris@16:    *     when ptrs transitorily contains duplicate elements.
Chris@16:    *   - Rewrite the internal algorithms of std::stable_sort
Chris@16:    *     adapted for this case: besides being a fair amount of
Chris@16:    *     work, making a stable sort compatible with Boost.MultiIndex
Chris@16:    *     invariants (basically, no duplicates or missing elements
Chris@16:    *     even if an exception is thrown) is complicated, error-prone
Chris@16:    *     and possibly won't perform much better than the
Chris@16:    *     solution adopted.
Chris@16:    */
Chris@16: 
Chris@16:   if(ptrs.size()<=1)return;
Chris@16: 
Chris@16:   typedef typename Node::impl_pointer       impl_pointer;
Chris@16:   typedef typename Node::impl_ptr_pointer   impl_ptr_pointer;
Chris@16:   typedef random_access_index_sort_compare<
Chris@16:     Node,Compare>                           ptr_compare;
Chris@16:   
Chris@16:   impl_ptr_pointer   first=ptrs.begin();
Chris@16:   impl_ptr_pointer   last=ptrs.end();
Chris@16:   auto_space<
Chris@16:     impl_pointer,
Chris@16:     Allocator>       spc(al,ptrs.size());
Chris@16:   impl_ptr_pointer   buf=spc.data();
Chris@16: 
Chris@16:   std::copy(&*first,&*last,&*buf);
Chris@16:   std::stable_sort(&*buf,&*buf+ptrs.size(),ptr_compare(comp));
Chris@16: 
Chris@16:   while(first!=last){
Chris@16:     *first=*buf++;
Chris@16:     (*first)->up()=first;
Chris@16:     ++first;
Chris@16:   }
Chris@16: }
Chris@16: 
Chris@16: } /* namespace multi_index::detail */
Chris@16: 
Chris@16: } /* namespace multi_index */
Chris@16: 
Chris@16: } /* namespace boost */
Chris@16: 
Chris@16: #endif