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