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