| /* Copyright 2003-2008 Joaquin M Lopez Munoz. |
| * Distributed under the Boost Software License, Version 1.0. |
| * (See accompanying file LICENSE_1_0.txt or copy at |
| * http://www.boost.org/LICENSE_1_0.txt) |
| * |
| * See http://www.boost.org/libs/multi_index for library home page. |
| */ |
| |
| #ifndef BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_OPS_HPP |
| #define BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_OPS_HPP |
| |
| #if defined(_MSC_VER)&&(_MSC_VER>=1200) |
| #pragma once |
| #endif |
| |
| #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ |
| #include <boost/detail/no_exceptions_support.hpp> |
| #include <boost/multi_index/detail/seq_index_node.hpp> |
| #include <boost/limits.hpp> |
| #include <boost/type_traits/aligned_storage.hpp> |
| #include <boost/type_traits/alignment_of.hpp> |
| #include <cstddef> |
| |
| namespace boost{ |
| |
| namespace multi_index{ |
| |
| namespace detail{ |
| |
| /* Common code for sequenced_index memfuns having templatized and |
| * non-templatized versions. |
| */ |
| |
| template <typename SequencedIndex,typename Predicate> |
| void sequenced_index_remove(SequencedIndex& x,Predicate pred) |
| { |
| typedef typename SequencedIndex::iterator iterator; |
| iterator first=x.begin(),last=x.end(); |
| while(first!=last){ |
| if(pred(*first))x.erase(first++); |
| else ++first; |
| } |
| } |
| |
| template <typename SequencedIndex,class BinaryPredicate> |
| void sequenced_index_unique(SequencedIndex& x,BinaryPredicate binary_pred) |
| { |
| typedef typename SequencedIndex::iterator iterator; |
| iterator first=x.begin(); |
| iterator last=x.end(); |
| if(first!=last){ |
| for(iterator middle=first;++middle!=last;middle=first){ |
| if(binary_pred(*middle,*first))x.erase(middle); |
| else first=middle; |
| } |
| } |
| } |
| |
| template <typename SequencedIndex,typename Compare> |
| void sequenced_index_merge(SequencedIndex& x,SequencedIndex& y,Compare comp) |
| { |
| typedef typename SequencedIndex::iterator iterator; |
| if(&x!=&y){ |
| iterator first0=x.begin(),last0=x.end(); |
| iterator first1=y.begin(),last1=y.end(); |
| while(first0!=last0&&first1!=last1){ |
| if(comp(*first1,*first0))x.splice(first0,y,first1++); |
| else ++first0; |
| } |
| x.splice(last0,y,first1,last1); |
| } |
| } |
| |
| /* sorting */ |
| |
| /* auxiliary stuff */ |
| |
| template<typename Node,typename Compare> |
| void sequenced_index_collate( |
| BOOST_DEDUCED_TYPENAME Node::impl_type* x, |
| BOOST_DEDUCED_TYPENAME Node::impl_type* y, |
| Compare comp |
| BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Node)) |
| { |
| typedef typename Node::impl_type impl_type; |
| typedef typename Node::impl_pointer impl_pointer; |
| |
| impl_pointer first0=x->next(); |
| impl_pointer last0=x; |
| impl_pointer first1=y->next(); |
| impl_pointer last1=y; |
| while(first0!=last0&&first1!=last1){ |
| if(comp( |
| Node::from_impl(first1)->value(),Node::from_impl(first0)->value())){ |
| impl_pointer tmp=first1->next(); |
| impl_type::relink(first0,first1); |
| first1=tmp; |
| } |
| else first0=first0->next(); |
| } |
| impl_type::relink(last0,first1,last1); |
| } |
| |
| /* Some versions of CGG require a bogus typename in counter_spc |
| * inside sequenced_index_sort if the following is defined |
| * also inside sequenced_index_sort. |
| */ |
| |
| BOOST_STATIC_CONSTANT( |
| std::size_t, |
| sequenced_index_sort_max_fill= |
| (std::size_t)std::numeric_limits<std::size_t>::digits+1); |
| |
| template<typename Node,typename Compare> |
| void sequenced_index_sort(Node* header,Compare comp) |
| { |
| /* Musser's mergesort, see http://www.cs.rpi.edu/~musser/gp/List/lists1.html. |
| * The implementation is a little convoluted: in the original code |
| * counter elements and carry are std::lists: here we do not want |
| * to use multi_index instead, so we do things at a lower level, managing |
| * directly the internal node representation. |
| * Incidentally, the implementations I've seen of this algorithm (SGI, |
| * Dinkumware, STLPort) are not exception-safe: this is. Moreover, we do not |
| * use any dynamic storage. |
| */ |
| |
| if(header->next()==header->impl()|| |
| header->next()->next()==header->impl())return; |
| |
| typedef typename Node::impl_type impl_type; |
| typedef typename Node::impl_pointer impl_pointer; |
| |
| typedef typename aligned_storage< |
| sizeof(impl_type), |
| alignment_of<impl_type>::value |
| >::type carry_spc_type; |
| carry_spc_type carry_spc; |
| impl_type& carry= |
| *static_cast<impl_type*>(static_cast<void*>(&carry_spc)); |
| typedef typename aligned_storage< |
| sizeof( |
| impl_type |
| [sequenced_index_sort_max_fill]), |
| alignment_of< |
| impl_type |
| [sequenced_index_sort_max_fill] |
| >::value |
| >::type counter_spc_type; |
| counter_spc_type counter_spc; |
| impl_type* counter= |
| static_cast<impl_type*>(static_cast<void*>(&counter_spc)); |
| std::size_t fill=0; |
| |
| carry.prior()=carry.next()=static_cast<impl_pointer>(&carry); |
| counter[0].prior()=counter[0].next()=static_cast<impl_pointer>(&counter[0]); |
| |
| BOOST_TRY{ |
| while(header->next()!=header->impl()){ |
| impl_type::relink(carry.next(),header->next()); |
| std::size_t i=0; |
| while(i<fill&&counter[i].next()!=static_cast<impl_pointer>(&counter[i])){ |
| sequenced_index_collate<Node>(&carry,&counter[i++],comp); |
| } |
| impl_type::swap( |
| static_cast<impl_pointer>(&carry), |
| static_cast<impl_pointer>(&counter[i])); |
| if(i==fill){ |
| ++fill; |
| counter[fill].prior()=counter[fill].next()= |
| static_cast<impl_pointer>(&counter[fill]); |
| } |
| } |
| |
| for(std::size_t i=1;i<fill;++i){ |
| sequenced_index_collate<Node>(&counter[i],&counter[i-1],comp); |
| } |
| impl_type::swap( |
| header->impl(),static_cast<impl_pointer>(&counter[fill-1])); |
| } |
| BOOST_CATCH(...) |
| { |
| impl_type::relink( |
| header->impl(),carry.next(),static_cast<impl_pointer>(&carry)); |
| for(std::size_t i=0;i<=fill;++i){ |
| impl_type::relink( |
| header->impl(),counter[i].next(), |
| static_cast<impl_pointer>(&counter[i])); |
| } |
| BOOST_RETHROW; |
| } |
| BOOST_CATCH_END |
| } |
| |
| } /* namespace multi_index::detail */ |
| |
| } /* namespace multi_index */ |
| |
| } /* namespace boost */ |
| |
| #endif |