/* Copyright 2003-2005 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_RND_INDEX_OPS_HPP

#define BOOST_MULTI_INDEX_DETAIL_RND_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 <algorithm>

#include <boost/multi_index/detail/rnd_index_ptr_array.hpp>

#include <functional>

namespace boost{

namespace multi_index{

namespace detail{

/* Common code for random_access_index memfuns having templatized and

 * non-templatized versions.

 */

template<typename Node,typename Allocator,typename Predicate>

Node* random_access_index_remove(

  random_access_index_ptr_array<Allocator>& ptrs,Predicate pred

  BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Node))

{

  typedef typename Node::value_type value_type;

  random_access_index_node_impl** first=ptrs.begin(),

                               ** res=first,

                               ** last=ptrs.end();

  for(;first!=last;++first){

    if(!pred(

        const_cast<const value_type&>(Node::from_impl(*first)->value()))){

      if(first!=res){

        std::swap(*first,*res);

        (*first)->up()=first;

        (*res)->up()=res;

      }

      ++res;

    }

  }

  return Node::from_impl(*res);

}

template<typename Node,typename Allocator,class BinaryPredicate>

Node* random_access_index_unique(

  random_access_index_ptr_array<Allocator>& ptrs,BinaryPredicate binary_pred

  BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Node))

{

  typedef typename Node::value_type value_type;

  random_access_index_node_impl** first=ptrs.begin(),

                               ** res=first,

                               ** last=ptrs.end();

  if(first!=last){

    for(;++first!=last;){

      if(!binary_pred(

           const_cast<const value_type&>(Node::from_impl(*res)->value()),

           const_cast<const value_type&>(Node::from_impl(*first)->value()))){

        ++res;

        if(first!=res){

          std::swap(*first,*res);

          (*first)->up()=first;

          (*res)->up()=res;

        }

      }

    }

    ++res;

  }

  return Node::from_impl(*res);

}

template<typename Node,typename Allocator,typename Compare>

void random_access_index_inplace_merge(

  const Allocator& al,

  random_access_index_ptr_array<Allocator>& ptrs,

  random_access_index_node_impl** first1,Compare comp

  BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Node))

{

  typedef typename Node::value_type value_type;

  auto_space<random_access_index_node_impl*,Allocator> spc(al,ptrs.size());

  random_access_index_node_impl** first0=ptrs.begin(),

                               ** last0=first1,

                               ** last1=ptrs.end(),

                               ** out=spc.data();

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

    if(comp(

        const_cast<const value_type&>(Node::from_impl(*first1)->value()),

        const_cast<const value_type&>(Node::from_impl(*first0)->value()))){

      *out++=*first1++;

    }

    else{

      *out++=*first0++;

    }

  }

  std::copy(first0,last0,out);

  std::copy(first1,last1,out);

  first1=ptrs.begin();

  out=spc.data();

  while(first1!=last1){

    *first1=*out++;

    (*first1)->up()=first1;

    ++first1;

  }

}

/* sorting */

/* auxiliary stuff */

template<typename Node,typename Compare>

struct random_access_index_sort_compare:

  std::binary_function<

    const typename Node::value_type*,const typename Node::value_type*,bool>

{

  random_access_index_sort_compare(Compare comp_=Compare()):comp(comp_){}

  bool operator()(

    random_access_index_node_impl* x,

    random_access_index_node_impl* y)const

  {

    typedef typename Node::value_type value_type;

    return comp(

      const_cast<const value_type&>(Node::from_impl(x)->value()),

      const_cast<const value_type&>(Node::from_impl(y)->value()));

  }

private:

  Compare comp;

};

template<typename Node,typename Allocator,class Compare>

void random_access_index_sort(

  const Allocator& al,

  random_access_index_ptr_array<Allocator>& ptrs,

  Compare comp

  BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Node))

{

  /* The implementation is extremely simple: an auxiliary

   * array of pointers is sorted using stdlib facilities and

   * then used to rearrange the index. This is suboptimal

   * in space and time, but has some advantages over other

   * possible approaches:

   *   - Use std::stable_sort() directly on ptrs using some

   *     special iterator in charge of maintaining pointers

   *     and up() pointers in sync: we cannot guarantee

   *     preservation of the container invariants in the face of

   *     exceptions, if, for instance, std::stable_sort throws

   *     when ptrs transitorily contains duplicate elements.

   *   - Rewrite the internal algorithms of std::stable_sort

   *     adapted for this case: besides being a fair amount of

   *     work, making a stable sort compatible with Boost.MultiIndex

   *     invariants (basically, no duplicates or missing elements

   *     even if an exception is thrown) is complicated, error-prone

   *     and possibly won't perform much better than the

   *     solution adopted.

   */

  typedef typename Node::value_type         value_type;

  typedef random_access_index_sort_compare<

    Node,Compare>                           ptr_compare;

  random_access_index_node_impl**   first=ptrs.begin();

  random_access_index_node_impl**   last=ptrs.end();

  auto_space<

    random_access_index_node_impl*,

    Allocator>                      spc(al,ptrs.size());

  random_access_index_node_impl**   buf=spc.data();

  std::copy(first,last,buf);

  std::stable_sort(buf,buf+ptrs.size(),ptr_compare(comp));

  while(first!=last){

    *first=*buf++;

    (*first)->up()=first;

    ++first;

  }

}

} /* namespace multi_index::detail */

} /* namespace multi_index */

} /* namespace boost */

#endif