williamr@2: /* Copyright 2003-2006 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_SEQ_INDEX_OPS_HPP
williamr@2: #define BOOST_MULTI_INDEX_DETAIL_SEQ_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 <boost/detail/no_exceptions_support.hpp>
williamr@2: #include <boost/multi_index/detail/seq_index_node.hpp>
williamr@2: #include <boost/limits.hpp>
williamr@2: #include <boost/type_traits/aligned_storage.hpp>
williamr@2: #include <boost/type_traits/alignment_of.hpp> 
williamr@2: #include <cstddef>
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 sequenced_index memfuns having templatized and
williamr@2:  * non-templatized versions.
williamr@2:  */
williamr@2: 
williamr@2: template <typename SequencedIndex,typename Predicate>
williamr@2: void sequenced_index_remove(SequencedIndex& x,Predicate pred)
williamr@2: {
williamr@2:   typedef typename SequencedIndex::iterator iterator;
williamr@2:   iterator first=x.begin(),last=x.end();
williamr@2:   while(first!=last){
williamr@2:     if(pred(*first))x.erase(first++);
williamr@2:     else ++first;
williamr@2:   }
williamr@2: }
williamr@2: 
williamr@2: template <typename SequencedIndex,class BinaryPredicate>
williamr@2: void sequenced_index_unique(SequencedIndex& x,BinaryPredicate binary_pred)
williamr@2: {
williamr@2:   typedef typename SequencedIndex::iterator iterator;
williamr@2:   iterator first=x.begin();
williamr@2:   iterator last=x.end();
williamr@2:   if(first!=last){
williamr@2:     for(iterator middle=first;++middle!=last;middle=first){
williamr@2:       if(binary_pred(*middle,*first))x.erase(middle);
williamr@2:       else first=middle;
williamr@2:     }
williamr@2:   }
williamr@2: }
williamr@2: 
williamr@2: template <typename SequencedIndex,typename Compare>
williamr@2: void sequenced_index_merge(SequencedIndex& x,SequencedIndex& y,Compare comp)
williamr@2: {
williamr@2:   typedef typename SequencedIndex::iterator iterator;
williamr@2:   if(&x!=&y){
williamr@2:     iterator first0=x.begin(),last0=x.end();
williamr@2:     iterator first1=y.begin(),last1=y.end();
williamr@2:     while(first0!=last0&&first1!=last1){
williamr@2:       if(comp(*first1,*first0))x.splice(first0,y,first1++);
williamr@2:       else ++first0;
williamr@2:     }
williamr@2:     x.splice(last0,y,first1,last1);
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: void sequenced_index_collate(
williamr@2:   sequenced_index_node_impl* x,sequenced_index_node_impl* y,Compare comp
williamr@2:   BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Node))
williamr@2: {
williamr@2:   sequenced_index_node_impl* first0=x->next();
williamr@2:   sequenced_index_node_impl* last0=x;
williamr@2:   sequenced_index_node_impl* first1=y->next();
williamr@2:   sequenced_index_node_impl* last1=y;
williamr@2:   while(first0!=last0&&first1!=last1){
williamr@2:     if(comp(
williamr@2:         Node::from_impl(first1)->value(),Node::from_impl(first0)->value())){
williamr@2:       sequenced_index_node_impl* tmp=first1->next();
williamr@2:       sequenced_index_node_impl::relink(first0,first1);
williamr@2:       first1=tmp;
williamr@2:     }
williamr@2:     else first0=first0->next();
williamr@2:   }
williamr@2:   sequenced_index_node_impl::relink(last0,first1,last1);
williamr@2: }
williamr@2: 
williamr@2: /* Some versions of CGG require a bogus typename in counter_spc
williamr@2:  * inside sequenced_index_sort if the following is defined
williamr@2:  * also inside sequenced_index_sort.
williamr@2:  */
williamr@2: 
williamr@2: BOOST_STATIC_CONSTANT(
williamr@2:   std::size_t,
williamr@2:   sequenced_index_sort_max_fill=
williamr@2:     (std::size_t)std::numeric_limits<std::size_t>::digits+1);
williamr@2: 
williamr@2: template<typename Node,typename Compare>
williamr@2: void sequenced_index_sort(Node* header,Compare comp)
williamr@2: {
williamr@2:   /* Musser's mergesort, see http://www.cs.rpi.edu/~musser/gp/List/lists1.html.
williamr@2:    * The implementation is a little convoluted: in the original code
williamr@2:    * counter elements and carry are std::lists: here we do not want
williamr@2:    * to use multi_index instead, so we do things at a lower level, managing
williamr@2:    * directly the internal node representation.
williamr@2:    * Incidentally, the implementations I've seen of this algorithm (SGI,
williamr@2:    * Dinkumware, STLPort) are not exception-safe: this is. Moreover, we do not
williamr@2:    * use any dynamic storage.
williamr@2:    */
williamr@2: 
williamr@2:   if(header->next()==header->impl()||
williamr@2:      header->next()->next()==header->impl())return;
williamr@2: 
williamr@2:   aligned_storage<
williamr@2:     sizeof(sequenced_index_node_impl),
williamr@2:     alignment_of<
williamr@2:     sequenced_index_node_impl>::value
williamr@2:   >::type                                   carry_spc;
williamr@2:   sequenced_index_node_impl&                carry=
williamr@2:     *static_cast<sequenced_index_node_impl*>(static_cast<void*>(&carry_spc));
williamr@2:   aligned_storage<
williamr@2:     sizeof(
williamr@2:       sequenced_index_node_impl
williamr@2:         [sequenced_index_sort_max_fill]),
williamr@2:     alignment_of<
williamr@2:       sequenced_index_node_impl
williamr@2:         [sequenced_index_sort_max_fill]
williamr@2:     >::value
williamr@2:   >::type                                   counter_spc;
williamr@2:   sequenced_index_node_impl*                counter=
williamr@2:     static_cast<sequenced_index_node_impl*>(static_cast<void*>(&counter_spc));
williamr@2:   std::size_t                               fill=0;
williamr@2: 
williamr@2:   carry.prior()=carry.next()=&carry;
williamr@2:   counter[0].prior()=counter[0].next()=&counter[0];
williamr@2: 
williamr@2:   BOOST_TRY{
williamr@2:     while(header->next()!=header->impl()){
williamr@2:       sequenced_index_node_impl::relink(carry.next(),header->next());
williamr@2:       std::size_t i=0;
williamr@2:       while(i<fill&&counter[i].next()!=&counter[i]){
williamr@2:         sequenced_index_collate<Node>(&carry,&counter[i++],comp);
williamr@2:       }
williamr@2:       sequenced_index_node_impl::swap(&carry,&counter[i]);
williamr@2:       if(i==fill){
williamr@2:         ++fill;
williamr@2:         counter[fill].prior()=counter[fill].next()=&counter[fill];
williamr@2:       }
williamr@2:     }
williamr@2: 
williamr@2:     for(std::size_t i=1;i<fill;++i){
williamr@2:       sequenced_index_collate<Node>(&counter[i],&counter[i-1],comp);
williamr@2:     }
williamr@2:     sequenced_index_node_impl::swap(header->impl(),&counter[fill-1]);
williamr@2:   }
williamr@2:   BOOST_CATCH(...)
williamr@2:   {
williamr@2:     sequenced_index_node_impl::relink(header->impl(),carry.next(),&carry);
williamr@2:     for(std::size_t i=0;i<=fill;++i){
williamr@2:       sequenced_index_node_impl::relink(
williamr@2:         header->impl(),counter[i].next(),&counter[i]);
williamr@2:     }
williamr@2:     BOOST_RETHROW;
williamr@2:   }
williamr@2:   BOOST_CATCH_END
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