/* Copyright 2003-2006 Joaquín M López Muñoz.

  * 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(

   sequenced_index_node_impl* x,sequenced_index_node_impl* y,Compare comp

   BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Node))

 {

   sequenced_index_node_impl* first0=x->next();

   sequenced_index_node_impl* last0=x;

   sequenced_index_node_impl* first1=y->next();

   sequenced_index_node_impl* last1=y;

   while(first0!=last0&&first1!=last1){

     if(comp(

         Node::from_impl(first1)->value(),Node::from_impl(first0)->value())){

       sequenced_index_node_impl* tmp=first1->next();

       sequenced_index_node_impl::relink(first0,first1);

       first1=tmp;

     }

     else first0=first0->next();

   }

   sequenced_index_node_impl::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;

   aligned_storage<

     sizeof(sequenced_index_node_impl),

     alignment_of<

     sequenced_index_node_impl>::value

   >::type                                   carry_spc;

   sequenced_index_node_impl&                carry=

     *static_cast<sequenced_index_node_impl*>(static_cast<void*>(&carry_spc));

   aligned_storage<

     sizeof(

       sequenced_index_node_impl

         [sequenced_index_sort_max_fill]),

     alignment_of<

       sequenced_index_node_impl

         [sequenced_index_sort_max_fill]

     >::value

   >::type                                   counter_spc;

   sequenced_index_node_impl*                counter=

     static_cast<sequenced_index_node_impl*>(static_cast<void*>(&counter_spc));

   std::size_t                               fill=0;

   carry.prior()=carry.next()=&carry;

   counter[0].prior()=counter[0].next()=&counter[0];

   BOOST_TRY{

     while(header->next()!=header->impl()){

       sequenced_index_node_impl::relink(carry.next(),header->next());

       std::size_t i=0;

       while(i<fill&&counter[i].next()!=&counter[i]){

         sequenced_index_collate<Node>(&carry,&counter[i++],comp);

       }

       sequenced_index_node_impl::swap(&carry,&counter[i]);

       if(i==fill){

         ++fill;

         counter[fill].prior()=counter[fill].next()=&counter[fill];

       }

     }

     for(std::size_t i=1;i<fill;++i){

       sequenced_index_collate<Node>(&counter[i],&counter[i-1],comp);

     }

     sequenced_index_node_impl::swap(header->impl(),&counter[fill-1]);

   }

   BOOST_CATCH(...)

   {

     sequenced_index_node_impl::relink(header->impl(),carry.next(),&carry);

     for(std::size_t i=0;i<=fill;++i){

       sequenced_index_node_impl::relink(

         header->impl(),counter[i].next(),&counter[i]);

     }

     BOOST_RETHROW;

   }

   BOOST_CATCH_END

 }

 } /* namespace multi_index::detail */

 } /* namespace multi_index */

 } /* namespace boost */

 #endif