code:
// Copyright 2002 The Trustees of Indiana University.

// Use, modification and distribution is subject to 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)

//  Boost.MultiArray Library
//  Authors: Ronald Garcia
//           Jeremy Siek
//           Andrew Lumsdaine
//  See http://www.boost.org/libs/multi_array for documentation.

#ifndef BOOST_MULTI_ARRAY_VIEW_RG071301_HPP
#define BOOST_MULTI_ARRAY_VIEW_RG071301_HPP

//
// view.hpp - code for creating "views" of array data.
//

#include "boost/multi_array/base.hpp"
#include "boost/multi_array/concept_checks.hpp"
#include "boost/multi_array/iterator.hpp"
#include "boost/multi_array/storage_order.hpp"
#include "boost/multi_array/subarray.hpp"
#include "boost/multi_array/algorithm.hpp"
#include "boost/type_traits/is_integral.hpp"
#include "boost/utility/enable_if.hpp"
#include "boost/array.hpp"
#include "boost/limits.hpp"
#include <algorithm>
#include <cstddef>
#include <functional>
#include <numeric>

namespace boost {
namespace detail {
namespace multi_array {

// TPtr = const T* defaulted in base.hpp
template <typename T, std::size_t NumDims, typename TPtr>
class const_multi_array_view :
    public boost::detail::multi_array::multi_array_impl_base<T,NumDims>
{
  typedef boost::detail::multi_array::multi_array_impl_base<T,NumDims> super_type;
public:
  typedef typename super_type::value_type value_type;
  typedef typename super_type::const_reference const_reference;
  typedef typename super_type::const_iterator const_iterator;
  typedef typename super_type::const_reverse_iterator const_reverse_iterator;
  typedef typename super_type::element element;
  typedef typename super_type::size_type size_type;
  typedef typename super_type::difference_type difference_type;
  typedef typename super_type::index index;
  typedef typename super_type::extent_range extent_range;

  // template typedefs
  template <std::size_t NDims>
  struct const_array_view {
    typedef boost::detail::multi_array::const_multi_array_view<T,NDims> type;
  };

  template <std::size_t NDims>
  struct array_view {
    typedef boost::detail::multi_array::multi_array_view<T,NDims> type;
  };

  template <typename OPtr>
  const_multi_array_view(const
                         const_multi_array_view<T,NumDims,OPtr>& other) :
    base_(other.base_), origin_offset_(other.origin_offset_),
    num_elements_(other.num_elements_), extent_list_(other.extent_list_),
    stride_list_(other.stride_list_), index_base_list_(other.index_base_list_)
  { }

  template <class BaseList>
#ifdef BOOST_NO_SFINAE
  void
#else
  typename
  disable_if<typename boost::is_integral<BaseList>::type,void >::type
#endif
  reindex(const BaseList& values) {
    boost::function_requires<
      CollectionConcept<BaseList> >();
    boost::detail::multi_array::
      copy_n(values.begin(),num_dimensions(),index_base_list_.begin());
    origin_offset_ =
      this->calculate_indexing_offset(stride_list_,index_base_list_);
  }

  void reindex(index value) {
    index_base_list_.assign(value);
    origin_offset_ =
      this->calculate_indexing_offset(stride_list_,index_base_list_);
  }

  size_type num_dimensions() const { return NumDims; }

  size_type size() const { return extent_list_.front(); }
  size_type max_size() const { return num_elements(); }
  bool empty() const { return size() == 0; }

  const size_type* shape() const {
    return extent_list_.data();
  }

  const index* strides() const {
    return stride_list_.data();
  }

  const T* origin() const { return base_+origin_offset_; }

  size_type num_elements() const { return num_elements_; }

  const index* index_bases() const {
    return index_base_list_.data();
  }

  template <typename IndexList>
  const element& operator()(IndexList indices) const {
    boost::function_requires<
      CollectionConcept<IndexList> >();
    return super_type::access_element(boost::type<const element&>(),
                                      indices,origin(),
                                      shape(),strides(),index_bases());
  }

  // Only allow const element access
  const_reference operator[](index idx) const {
    return super_type::access(boost::type<const_reference>(),
                              idx,origin(),
                              shape(),strides(),
                              index_bases());
  }

  // see generate_array_view in base.hpp
  template <int NDims>
  typename const_array_view<NDims>::type
  operator[](const boost::detail::multi_array::
             index_gen<NumDims,NDims>& indices)
    const {
    typedef typename const_array_view<NDims>::type return_type;
    return
      super_type::generate_array_view(boost::type<return_type>(),
                                      indices,
                                      shape(),
                                      strides(),
                                      index_bases(),
                                      origin());
  }
  const_iterator begin() const {
    return const_iterator(*index_bases(),origin(),
                          shape(),strides(),index_bases());
  }

  const_iterator end() const {
    return const_iterator(*index_bases()+(index)*shape(),origin(),
                          shape(),strides(),index_bases());
  }

  const_reverse_iterator rbegin() const {
    return const_reverse_iterator(end());
  }

  const_reverse_iterator rend() const {
    return const_reverse_iterator(begin());
  }

  template <typename OPtr>
  bool operator==(const
                  const_multi_array_view<T,NumDims,OPtr>& rhs)
    const {
    if(std::equal(extent_list_.begin(),
                  extent_list_.end(),
                  rhs.extent_list_.begin()))
      return std::equal(begin(),end(),rhs.begin());
    else return false;
  }

  template <typename OPtr>
  bool operator<(const
                 const_multi_array_view<T,NumDims,OPtr>& rhs)
    const {
    return std::lexicographical_compare(begin(),end(),rhs.begin(),rhs.end());
  }

  template <typename OPtr>
  bool operator!=(const
                  const_multi_array_view<T,NumDims,OPtr>& rhs)
    const {
    return !(*this == rhs);
  }

  template <typename OPtr>
  bool operator>(const
                 const_multi_array_view<T,NumDims,OPtr>& rhs)
    const {
    return rhs < *this;
  }

  template <typename OPtr>
  bool operator<=(const
                 const_multi_array_view<T,NumDims,OPtr>& rhs)
    const {
    return !(*this > rhs);
  }

  template <typename OPtr>
  bool operator>=(const
                 const_multi_array_view<T,NumDims,OPtr>& rhs)
    const {
    return !(*this < rhs);
  }

#ifndef BOOST_NO_MEMBER_TEMPLATE_FRIENDS
protected:
  template <typename,std::size_t> friend class multi_array_impl_base;
  template <typename,std::size_t,typename> friend class const_multi_array_view;
#else
public: // should be protected
#endif

  // This constructor is used by multi_array_impl_base::generate_array_view
  // to create strides
  template <typename ExtentList, typename Index>
  explicit const_multi_array_view(TPtr base,
                           const ExtentList& extents,
                           const boost::array<Index,NumDims>& strides):
    base_(base), origin_offset_(0) {

    index_base_list_.assign(0);

    // Get the extents and strides
    boost::detail::multi_array::
      copy_n(extents.begin(),NumDims,extent_list_.begin());
    boost::detail::multi_array::
      copy_n(strides.begin(),NumDims,stride_list_.begin());

    // Calculate the array size
    num_elements_ = std::accumulate(extent_list_.begin(),extent_list_.end(),
                                    size_type(1),std::multiplies<size_type>());
  }

  typedef boost::array<size_type,NumDims> size_list;
  typedef boost::array<index,NumDims> index_list;

  TPtr base_;
  index origin_offset_;
  size_type num_elements_;
  size_list extent_list_;
  index_list stride_list_;
  index_list index_base_list_;

private:
  // const_multi_array_view cannot be assigned to (no deep copies!)
  const_multi_array_view& operator=(const const_multi_array_view& other);
};

template <typename T, std::size_t NumDims>
class multi_array_view :
  public const_multi_array_view<T,NumDims,T*>
{
  typedef const_multi_array_view<T,NumDims,T*> super_type;
public:
  typedef typename super_type::value_type value_type;
  typedef typename super_type::reference reference;
  typedef typename super_type::iterator iterator;
  typedef typename super_type::reverse_iterator reverse_iterator;
  typedef typename super_type::const_reference const_reference;
  typedef typename super_type::const_iterator const_iterator;
  typedef typename super_type::const_reverse_iterator const_reverse_iterator;
  typedef typename super_type::element element;
  typedef typename super_type::size_type size_type;
  typedef typename super_type::difference_type difference_type;
  typedef typename super_type::index index;
  typedef typename super_type::extent_range extent_range;

  // template typedefs
  template <std::size_t NDims>
  struct const_array_view {
    typedef boost::detail::multi_array::const_multi_array_view<T,NDims> type;
  };

  template <std::size_t NDims>
  struct array_view {
    typedef boost::detail::multi_array::multi_array_view<T,NDims> type;
  };

  // Assignment from other ConstMultiArray types.
  template <typename ConstMultiArray>
  multi_array_view& operator=(const ConstMultiArray& other) {
    function_requires<
      boost::multi_array_concepts::
      ConstMultiArrayConcept<ConstMultiArray,NumDims> >();

    // make sure the dimensions agree
    BOOST_ASSERT(other.num_dimensions() == this->num_dimensions());
    BOOST_ASSERT(std::equal(other.shape(),other.shape()+this->num_dimensions(),
                            this->shape()));
    // iterator-based copy
    std::copy(other.begin(),other.end(),begin());
    return *this;
  }

  multi_array_view& operator=(const multi_array_view& other) {
    if (&other != this) {
      // make sure the dimensions agree
      BOOST_ASSERT(other.num_dimensions() == this->num_dimensions());
      BOOST_ASSERT(std::equal(other.shape(),
                              other.shape()+this->num_dimensions(),
                              this->shape()));
      // iterator-based copy
      std::copy(other.begin(),other.end(),begin());
    }
    return *this;
  }

  element* origin() { return this->base_+this->origin_offset_; }

  template <class IndexList>
  element& operator()(const IndexList& indices) {
    boost::function_requires<
      CollectionConcept<IndexList> >();
    return super_type::access_element(boost::type<element&>(),
                                      indices,origin(),
                                      this->shape(),this->strides(),
                                      this->index_bases());
  }

  reference operator[](index idx) {
    return super_type::access(boost::type<reference>(),
                              idx,origin(),
                              this->shape(),this->strides(),
                              this->index_bases());
  }

  // see generate_array_view in base.hpp
  template <int NDims>
  typename array_view<NDims>::type
  operator[](const boost::detail::multi_array::
             index_gen<NumDims,NDims>& indices) {
    typedef typename array_view<NDims>::type return_type;
    return
      super_type::generate_array_view(boost::type<return_type>(),
                                      indices,
                                      this->shape(),
                                      this->strides(),
                                      this->index_bases(),
                                      origin());
  }

  iterator begin() {
    return iterator(*this->index_bases(),origin(),
                    this->shape(),this->strides(),
                    this->index_bases());
  }

  iterator end() {
    return iterator(*this->index_bases()+(index)*this->shape(),origin(),
                    this->shape(),this->strides(),
                    this->index_bases());
  }

  reverse_iterator rbegin() {
    return reverse_iterator(end());
  }

  reverse_iterator rend() {
    return reverse_iterator(begin());
  }

  // Using declarations don't seem to work for g++
  // These are the proxies to work around this.

  const element* origin() const { return super_type::origin(); }

  template <class IndexList>
  const element& operator()(const IndexList& indices) const {
    boost::function_requires<
      CollectionConcept<IndexList> >();
    return super_type::operator()(indices);
  }

  const_reference operator[](index idx) const {
    return super_type::operator[](idx);
  }

  // see generate_array_view in base.hpp
  template <int NDims>
  typename const_array_view<NDims>::type
  operator[](const boost::detail::multi_array::
             index_gen<NumDims,NDims>& indices)
    const {
    return super_type::operator[](indices);
  }

  const_iterator begin() const {
    return super_type::begin();
  }

  const_iterator end() const {
    return super_type::end();
  }

  const_reverse_iterator rbegin() const {
    return super_type::rbegin();
  }

  const_reverse_iterator rend() const {
    return super_type::rend();
  }

#ifndef BOOST_NO_MEMBER_TEMPLATE_FRIENDS
private:
  template <typename,std::size_t> friend class multi_array_impl_base;
#else
public: // should be private
#endif

  // constructor used by multi_array_impl_base::generate_array_view to
  // generate array views
  template <typename ExtentList, typename Index>
  explicit multi_array_view(T* base,
                            const ExtentList& extents,
                            const boost::array<Index,NumDims>& strides) :
    super_type(base,extents,strides) { }

};

} // namespace multi_array
} // namespace detail

//
// traits classes to get array_view types
//
template <typename Array, int N>
class array_view_gen {
  typedef typename Array::element element;
public:
  typedef boost::detail::multi_array::multi_array_view<element,N> type;
};

template <typename Array, int N>
class const_array_view_gen {
  typedef typename Array::element element;
public:
  typedef boost::detail::multi_array::const_multi_array_view<element,N> type;
};

} // namespace boost

#endif // BOOST_MULTI_ARRAY_VIEW_RG071301_HPP


code:
/* Copyright 2003-2013 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_ACCESS_SPECIFIER_HPP
#define BOOST_MULTI_INDEX_DETAIL_ACCESS_SPECIFIER_HPP

#if defined(_MSC_VER)
#pragma once
#endif

#include <boost/config.hpp>
#include <boost/detail/workaround.hpp>

/* In those compilers that do not accept the member template friend syntax,
 * some protected and private sections might need to be specified as
 * public.
 */

#if defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
#define BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS public
#define BOOST_MULTI_INDEX_PRIVATE_IF_MEMBER_TEMPLATE_FRIENDS public
#else
#define BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS protected
#define BOOST_MULTI_INDEX_PRIVATE_IF_MEMBER_TEMPLATE_FRIENDS private
#endif

/* GCC does not correctly support in-class using declarations for template
 * functions. See http://gcc.gnu.org/bugzilla/show_bug.cgi?id=9810
 * MSVC 7.1/8.0 seem to have a similar problem, though the conditions in
 * which the error happens are not that simple. I have yet to isolate this
 * into a snippet suitable for bug reporting.
 * Sun Studio also has this problem, which might be related, from the
 * information gathered at Sun forums, with a known issue notified at the
 * internal bug report 6421933. The bug is present up to Studio Express 2,
 * the latest preview version of the future Sun Studio 12. As of this writing
 * (October 2006) it is not known whether a fix will finally make it into the
 * official Sun Studio 12.
 */

#if BOOST_WORKAROUND(__GNUC__,==3)&&(__GNUC_MINOR__<4)||\
    BOOST_WORKAROUND(BOOST_MSVC,==1310)||\
    BOOST_WORKAROUND(BOOST_MSVC,==1400)||\
    BOOST_WORKAROUND(__SUNPRO_CC,BOOST_TESTED_AT(0x590))
#define BOOST_MULTI_INDEX_PRIVATE_IF_USING_DECL_FOR_TEMPL_FUNCTIONS public
#else
#define BOOST_MULTI_INDEX_PRIVATE_IF_USING_DECL_FOR_TEMPL_FUNCTIONS private
#endif

#endif

license: mit


code:
/* Copyright 2003-2013 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_ADL_SWAP_HPP
#define BOOST_MULTI_INDEX_DETAIL_ADL_SWAP_HPP

#if defined(_MSC_VER)
#pragma once
#endif

#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
#include <algorithm>

namespace boost{

namespace multi_index{

namespace detail{

template<typename T>
void adl_swap(T& x,T& y)
{

#if !defined(BOOST_FUNCTION_SCOPE_USING_DECLARATION_BREAKS_ADL)
  using std::swap;
  swap(x,y);
#else
  std::swap(x,y);
#endif

}

} /* namespace multi_index::detail */

} /* namespace multi_index */

} /* namespace boost */

#endif


code:
/* Copyright 2003-2015 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_ARCHIVE_CONSTRUCTED_HPP
#define BOOST_MULTI_INDEX_DETAIL_ARCHIVE_CONSTRUCTED_HPP

#if defined(_MSC_VER)
#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/noncopyable.hpp>
#include <boost/serialization/serialization.hpp>
#include <boost/type_traits/aligned_storage.hpp>
#include <boost/type_traits/alignment_of.hpp>

namespace boost{

namespace multi_index{

namespace detail{

/* constructs a stack-based object from a serialization archive */

template<typename T>
struct archive_constructed:private noncopyable
{
  template<class Archive>
  archive_constructed(Archive& ar,const unsigned int version)
  {
    serialization::load_construct_data_adl(ar,&get(),version);
    BOOST_TRY{
      ar>>get();
    }
    BOOST_CATCH(...){
      (&get())->~T();
      BOOST_RETHROW;
    }
    BOOST_CATCH_END
  }

  template<class Archive>
  archive_constructed(const char* name,Archive& ar,const unsigned int version)
  {
    serialization::load_construct_data_adl(ar,&get(),version);
    BOOST_TRY{
      ar>>serialization::make_nvp(name,get());
    }
    BOOST_CATCH(...){
      (&get())->~T();
      BOOST_RETHROW;
    }
    BOOST_CATCH_END
  }

  ~archive_constructed()
  {
    (&get())->~T();
  }

  T& get(){return *reinterpret_cast<T*>(&space);}

private:
  typename aligned_storage<sizeof(T),alignment_of<T>::value>::type space;
};

} /* namespace multi_index::detail */

} /* namespace multi_index */

} /* namespace boost */

#endif


code:
/* Copyright 2003-2013 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_AUTO_SPACE_HPP
#define BOOST_MULTI_INDEX_DETAIL_AUTO_SPACE_HPP

#if defined(_MSC_VER)
#pragma once
#endif

#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
#include <algorithm>
#include <boost/detail/allocator_utilities.hpp>
#include <boost/multi_index/detail/adl_swap.hpp>
#include <boost/noncopyable.hpp>
#include <memory>

namespace boost{

namespace multi_index{

namespace detail{

/* auto_space provides uninitialized space suitably to store
 * a given number of elements of a given type.
 */

/* NB: it is not clear whether using an allocator to handle
 * zero-sized arrays of elements is conformant or not. GCC 3.3.1
 * and prior fail here, other stdlibs handle the issue gracefully.
 * To be on the safe side, the case n==0 is given special treatment.
 * References:
 *   GCC Bugzilla, "standard allocator crashes when deallocating segment
 *    "of zero length", http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14176
 *   C++ Standard Library Defect Report List (Revision 28), issue 199
 *     "What does allocate(0) return?",
 *     http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#199
 */

template<typename T,typename Allocator=std::allocator<T> >
struct auto_space:private noncopyable
{
  typedef typename boost::detail::allocator::rebind_to<
    Allocator,T
  >::type::pointer pointer;

  explicit auto_space(const Allocator& al=Allocator(),std::size_t n=1):
  al_(al),n_(n),data_(n_?al_.allocate(n_):pointer(0))
  {}

  ~auto_space()
  {
    if(n_)al_.deallocate(data_,n_);
  }

  Allocator get_allocator()const{return al_;}

  pointer data()const{return data_;}

  void swap(auto_space& x)
  {
    if(al_!=x.al_)adl_swap(al_,x.al_);
    std::swap(n_,x.n_);
    std::swap(data_,x.data_);
  }

private:
  typename boost::detail::allocator::rebind_to<
    Allocator,T>::type                          al_;
  std::size_t                                   n_;
  pointer                                       data_;
};

template<typename T,typename Allocator>
void swap(auto_space<T,Allocator>& x,auto_space<T,Allocator>& y)
{
  x.swap(y);
}

} /* namespace multi_index::detail */

} /* namespace multi_index */

} /* namespace boost */

#endif


code:
/* Copyright 2003-2013 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_BASE_TYPE_HPP
#define BOOST_MULTI_INDEX_DETAIL_BASE_TYPE_HPP

#if defined(_MSC_VER)
#pragma once
#endif

#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
#include <boost/detail/workaround.hpp>
#include <boost/mpl/at.hpp>
#include <boost/mpl/apply.hpp>
#include <boost/mpl/size.hpp>
#include <boost/multi_index/detail/index_base.hpp>
#include <boost/multi_index/detail/is_index_list.hpp>
#include <boost/static_assert.hpp>

namespace boost{

namespace multi_index{

namespace detail{

/* MPL machinery to construct a linear hierarchy of indices out of
 * a index list.
 */

struct index_applier
{
  template<typename IndexSpecifierMeta,typename SuperMeta>
  struct apply
  {
    typedef typename IndexSpecifierMeta::type            index_specifier;
    typedef typename index_specifier::
      BOOST_NESTED_TEMPLATE index_class<SuperMeta>::type type;
  };
};

template<int N,typename Value,typename IndexSpecifierList,typename Allocator>
struct nth_layer
{
  BOOST_STATIC_CONSTANT(int,length=mpl::size<IndexSpecifierList>::value);

  typedef typename  mpl::eval_if_c<
    N==length,
    mpl::identity<index_base<Value,IndexSpecifierList,Allocator> >,
    mpl::apply2<
      index_applier,
      mpl::at_c<IndexSpecifierList,N>,
      nth_layer<N+1,Value,IndexSpecifierList,Allocator>
    >
  >::type type;
};

template<typename Value,typename IndexSpecifierList,typename Allocator>
struct multi_index_base_type:nth_layer<0,Value,IndexSpecifierList,Allocator>
{
  BOOST_STATIC_ASSERT(detail::is_index_list<IndexSpecifierList>::value);
};

} /* namespace multi_index::detail */

} /* namespace multi_index */

} /* namespace boost */

#endif


code:
/* Copyright 2003-2014 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_BIDIR_NODE_ITERATOR_HPP
#define BOOST_MULTI_INDEX_DETAIL_BIDIR_NODE_ITERATOR_HPP

#if defined(_MSC_VER)
#pragma once
#endif

#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
#include <boost/operators.hpp>

#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
#include <boost/serialization/nvp.hpp>
#include <boost/serialization/split_member.hpp>
#endif

namespace boost{

namespace multi_index{

namespace detail{

/* Iterator class for node-based indices with bidirectional
 * iterators (ordered and sequenced indices.)
 */

template<typename Node>
class bidir_node_iterator:
  public bidirectional_iterator_helper<
    bidir_node_iterator<Node>,
    typename Node::value_type,
    std::ptrdiff_t,
    const typename Node::value_type*,
    const typename Node::value_type&>
{
public:
  /* coverity[uninit_ctor]: suppress warning */
  bidir_node_iterator(){}
  explicit bidir_node_iterator(Node* node_):node(node_){}

  const typename Node::value_type& operator*()const
  {
    return node->value();
  }

  bidir_node_iterator& operator++()
  {
    Node::increment(node);
    return *this;
  }

  bidir_node_iterator& operator--()
  {
    Node::decrement(node);
    return *this;
  }

#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
  /* Serialization. As for why the following is public,
   * see explanation in safe_mode_iterator notes in safe_mode.hpp.
   */

  BOOST_SERIALIZATION_SPLIT_MEMBER()

  typedef typename Node::base_type node_base_type;

  template<class Archive>
  void save(Archive& ar,const unsigned int)const
  {
    node_base_type* bnode=node;
    ar<<serialization::make_nvp("pointer",bnode);
  }

  template<class Archive>
  void load(Archive& ar,const unsigned int)
  {
    node_base_type* bnode;
    ar>>serialization::make_nvp("pointer",bnode);
    node=static_cast<Node*>(bnode);
  }
#endif

  /* get_node is not to be used by the user */

  typedef Node node_type;

  Node* get_node()const{return node;}

private:
  Node* node;
};

template<typename Node>
bool operator==(
  const bidir_node_iterator<Node>& x,
  const bidir_node_iterator<Node>& y)
{
  return x.get_node()==y.get_node();
}

} /* namespace multi_index::detail */

} /* namespace multi_index */

} /* namespace boost */

#endif


code:
/* Copyright 2003-2015 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_BUCKET_ARRAY_HPP
#define BOOST_MULTI_INDEX_DETAIL_BUCKET_ARRAY_HPP

#if defined(_MSC_VER)
#pragma once
#endif

#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
#include <algorithm>
#include <boost/multi_index/detail/auto_space.hpp>
#include <boost/multi_index/detail/hash_index_node.hpp>
#include <boost/noncopyable.hpp>
#include <boost/preprocessor/repetition/repeat.hpp>
#include <boost/preprocessor/seq/elem.hpp>
#include <boost/preprocessor/seq/enum.hpp>
#include <boost/preprocessor/seq/size.hpp>
#include <cstddef>
#include <limits.h>

#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
#include <boost/archive/archive_exception.hpp>
#include <boost/serialization/access.hpp>
#include <boost/throw_exception.hpp>
#endif

namespace boost{

namespace multi_index{

namespace detail{

/* bucket structure for use by hashed indices */

#define BOOST_MULTI_INDEX_BA_SIZES_32BIT                                  \
(53ul)(97ul)(193ul)(389ul)(769ul)                                         \
(1543ul)(3079ul)(6151ul)(12289ul)(24593ul)                                \
(49157ul)(98317ul)(196613ul)(393241ul)(786433ul)                          \
(1572869ul)(3145739ul)(6291469ul)(12582917ul)(25165843ul)                 \
(50331653ul)(100663319ul)(201326611ul)(402653189ul)(805306457ul)          \
(1610612741ul)(3221225473ul)

#if ((((ULONG_MAX>>16)>>16)>>16)>>15)==0 /* unsigned long less than 64 bits */
#define BOOST_MULTI_INDEX_BA_SIZES                                         \
BOOST_MULTI_INDEX_BA_SIZES_32BIT                                           \
(4294967291ul)
#else
  /* obtained with aid from
   *   http://javaboutique.internet.com/prime_numb/
   *   http://www.rsok.com/~jrm/next_ten_primes.html
   * and verified with
   *   http://www.alpertron.com.ar/ECM.HTM
   */

#define BOOST_MULTI_INDEX_BA_SIZES                                         \
BOOST_MULTI_INDEX_BA_SIZES_32BIT                                           \
(6442450939ul)(12884901893ul)(25769803751ul)(51539607551ul)                \
(103079215111ul)(206158430209ul)(412316860441ul)(824633720831ul)           \
(1649267441651ul)(3298534883309ul)(6597069766657ul)(13194139533299ul)      \
(26388279066623ul)(52776558133303ul)(105553116266489ul)(211106232532969ul) \
(422212465066001ul)(844424930131963ul)(1688849860263953ul)                 \
(3377699720527861ul)(6755399441055731ul)(13510798882111483ul)              \
(27021597764222939ul)(54043195528445957ul)(108086391056891903ul)           \
(216172782113783843ul)(432345564227567621ul)(864691128455135207ul)         \
(1729382256910270481ul)(3458764513820540933ul)(6917529027641081903ul)      \
(13835058055282163729ul)(18446744073709551557ul)
#endif

template<bool _=true> /* templatized to have in-header static var defs */
class bucket_array_base:private noncopyable
{
protected:
  static const std::size_t sizes[
    BOOST_PP_SEQ_SIZE(BOOST_MULTI_INDEX_BA_SIZES)];

  static std::size_t size_index(std::size_t n)
  {
    const std::size_t *bound=std::lower_bound(sizes,sizes+sizes_length,n);
    if(bound==sizes+sizes_length)--bound;
    return bound-sizes;
  }

#define BOOST_MULTI_INDEX_BA_POSITION_CASE(z,n,_)                    \
  case n:return hash%BOOST_PP_SEQ_ELEM(n,BOOST_MULTI_INDEX_BA_SIZES);

  static std::size_t position(std::size_t hash,std::size_t size_index_)
  {
    /* Accelerate hash%sizes[size_index_] by replacing with a switch on
     * hash%Ci expressions, each Ci a compile-time constant, which the
     * compiler can implement without using integer division.
     */

    switch(size_index_){
      default: /* never used */
      BOOST_PP_REPEAT(
        BOOST_PP_SEQ_SIZE(BOOST_MULTI_INDEX_BA_SIZES),
        BOOST_MULTI_INDEX_BA_POSITION_CASE,~)
    }
  }

private:
  static const std::size_t sizes_length;
};

template<bool _>
const std::size_t bucket_array_base<_>::sizes[]={
  BOOST_PP_SEQ_ENUM(BOOST_MULTI_INDEX_BA_SIZES)
};

template<bool _>
const std::size_t bucket_array_base<_>::sizes_length=
  sizeof(bucket_array_base<_>::sizes)/
  sizeof(bucket_array_base<_>::sizes[0]);

#undef BOOST_MULTI_INDEX_BA_POSITION_CASE
#undef BOOST_MULTI_INDEX_BA_SIZES
#undef BOOST_MULTI_INDEX_BA_SIZES_32BIT

template<typename Allocator>
class bucket_array:bucket_array_base<>
{
  typedef bucket_array_base<>                        super;
  typedef hashed_index_base_node_impl<
    typename boost::detail::allocator::rebind_to<
      Allocator,
      char
    >::type
  >                                                  base_node_impl_type;

public:
  typedef typename base_node_impl_type::base_pointer base_pointer;
  typedef typename base_node_impl_type::pointer      pointer;

  bucket_array(const Allocator& al,pointer end_,std::size_t size_):
    size_index_(super::size_index(size_)),
    spc(al,super::sizes[size_index_]+1)
  {
    clear(end_);
  }

  std::size_t size()const
  {
    return super::sizes[size_index_];
  }

  std::size_t position(std::size_t hash)const
  {
    return super::position(hash,size_index_);
  }

  base_pointer begin()const{return buckets();}
  base_pointer end()const{return buckets()+size();}
  base_pointer at(std::size_t n)const{return buckets()+n;}

  void clear(pointer end_)
  {
    for(base_pointer x=begin(),y=end();x!=y;++x)x->prior()=pointer(0);
    end()->prior()=end_->prior()=end_;
    end_->next()=end();
 }

  void swap(bucket_array& x)
  {
    std::swap(size_index_,x.size_index_);
    spc.swap(x.spc);
  }

private:
  std::size_t                               size_index_;
  auto_space<base_node_impl_type,Allocator> spc;

  base_pointer buckets()const
  {
    return spc.data();
  }

#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
  friend class boost::serialization::access;

  /* bucket_arrays do not emit any kind of serialization info. They are
   * fed to Boost.Serialization as hashed index iterators need to track
   * them during serialization.
   */

  template<class Archive>
  void serialize(Archive&,const unsigned int)
  {
  }
#endif
};

template<typename Allocator>
void swap(bucket_array<Allocator>& x,bucket_array<Allocator>& y)
{
  x.swap(y);
}

} /* namespace multi_index::detail */

} /* namespace multi_index */

#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
/* bucket_arrays never get constructed directly by Boost.Serialization,
 * as archives are always fed pointers to previously existent
 * arrays. So, if this is called it means we are dealing with a
 * somehow invalid archive.
 */

#if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
namespace serialization{
#else
namespace multi_index{
namespace detail{
#endif

template<class Archive,typename Allocator>
inline void load_construct_data(
  Archive&,boost::multi_index::detail::bucket_array<Allocator>*,
  const unsigned int)
{
  throw_exception(
    archive::archive_exception(archive::archive_exception::other_exception));
}

#if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
} /* namespace serialization */
#else
} /* namespace multi_index::detail */
} /* namespace multi_index */
#endif

#endif

} /* namespace boost */

#endif


code:
/* Copyright 2003-2013 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_CONVERTER_HPP
#define BOOST_MULTI_INDEX_DETAIL_CONVERTER_HPP

#if defined(_MSC_VER)
#pragma once
#endif

namespace boost{

namespace multi_index{

namespace detail{

/* converter offers means to access indices of a given multi_index_container
 * and for convertibilty between index iterators, so providing a
 * localized access point for get() and project() functions.
 */

template<typename MultiIndexContainer,typename Index>
struct converter
{
  static const Index& index(const MultiIndexContainer& x){return x;}
  static Index&       index(MultiIndexContainer& x){return x;}

  static typename Index::const_iterator const_iterator(
    const MultiIndexContainer& x,typename MultiIndexContainer::node_type* node)
  {
    return x.Index::make_iterator(node);
  }

  static typename Index::iterator iterator(
    MultiIndexContainer& x,typename MultiIndexContainer::node_type* node)
  {
    return x.Index::make_iterator(node);
  }
};

} /* namespace multi_index::detail */

} /* namespace multi_index */

} /* namespace boost */

#endif


code:
/* Copyright 2003-2015 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_COPY_MAP_HPP
#define BOOST_MULTI_INDEX_DETAIL_COPY_MAP_HPP

#if defined(_MSC_VER)
#pragma once
#endif

#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
#include <algorithm>
#include <boost/detail/no_exceptions_support.hpp>
#include <boost/multi_index/detail/auto_space.hpp>
#include <boost/multi_index/detail/raw_ptr.hpp>
#include <boost/noncopyable.hpp>
#include <cstddef>
#include <functional>

namespace boost{

namespace multi_index{

namespace detail{

/* copy_map is used as an auxiliary structure during copy_() operations.
 * When a container with n nodes is replicated, node_map holds the pairings
 * between original and copied nodes, and provides a fast way to find a
 * copied node from an original one.
 * The semantics of the class are not simple, and no attempt has been made
 * to enforce it: multi_index_container handles it right. On the other hand,
 * the const interface, which is the one provided to index implementations,
 * only allows for:
 *   - Enumeration of pairs of (original,copied) nodes (excluding the headers),
 *   - fast retrieval of copied nodes (including the headers.)
 */

template <typename Node>
struct copy_map_entry
{
  copy_map_entry(Node* f,Node* s):first(f),second(s){}

  Node* first;
  Node* second;

  bool operator<(const copy_map_entry<Node>& x)const
  {
    return std::less<Node*>()(first,x.first);
  }
};

template <typename Node,typename Allocator>
class copy_map:private noncopyable
{
public:
  typedef const copy_map_entry<Node>* const_iterator;

  copy_map(
    const Allocator& al,std::size_t size,Node* header_org,Node* header_cpy):
    al_(al),size_(size),spc(al_,size_),n(0),
    header_org_(header_org),header_cpy_(header_cpy),released(false)
  {}

  ~copy_map()
  {
    if(!released){
      for(std::size_t i=0;i<n;++i){
        boost::detail::allocator::destroy(&(spc.data()+i)->second->value());
        deallocate((spc.data()+i)->second);
      }
    }
  }

  const_iterator begin()const{return raw_ptr<const_iterator>(spc.data());}
  const_iterator end()const{return raw_ptr<const_iterator>(spc.data()+n);}

  void clone(Node* node)
  {
    (spc.data()+n)->first=node;
    (spc.data()+n)->second=raw_ptr<Node*>(al_.allocate(1));
    BOOST_TRY{
      boost::detail::allocator::construct(
        &(spc.data()+n)->second->value(),node->value());
    }
    BOOST_CATCH(...){
      deallocate((spc.data()+n)->second);
      BOOST_RETHROW;
    }
    BOOST_CATCH_END
    ++n;

    if(n==size_){
      std::sort(
        raw_ptr<copy_map_entry<Node>*>(spc.data()),
        raw_ptr<copy_map_entry<Node>*>(spc.data())+size_);
    }
  }

  Node* find(Node* node)const
  {
    if(node==header_org_)return header_cpy_;
    return std::lower_bound(
      begin(),end(),copy_map_entry<Node>(node,0))->second;
  }

  void release()
  {
    released=true;
  }

private:
  typedef typename boost::detail::allocator::rebind_to<
    Allocator,Node
  >::type                                               allocator_type;
  typedef typename allocator_type::pointer              allocator_pointer;

  allocator_type                                        al_;
  std::size_t                                           size_;
  auto_space<copy_map_entry<Node>,Allocator>            spc;
  std::size_t                                           n;
  Node*                                                 header_org_;
  Node*                                                 header_cpy_;
  bool                                                  released;

  void deallocate(Node* node)
  {
    al_.deallocate(static_cast<allocator_pointer>(node),1);
  }
};

} /* namespace multi_index::detail */

} /* namespace multi_index */

} /* namespace boost */

#endif


code:
/* Copyright 2003-2013 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_DO_NOT_COPY_ELEMENTS_TAG_HPP
#define BOOST_MULTI_INDEX_DETAIL_DO_NOT_COPY_ELEMENTS_TAG_HPP

#if defined(_MSC_VER)
#pragma once
#endif

namespace boost{

namespace multi_index{

namespace detail{

/* Used to mark a special ctor variant that copies the internal objects of
 * a container but not its elements.
 */

struct do_not_copy_elements_tag{};

} /* namespace multi_index::detail */

} /* namespace multi_index */

} /* namespace boost */

#endif


code:
/* Copyright 2003-2013 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_DUPLICATES_ITERATOR_HPP
#define BOOST_MULTI_INDEX_DETAIL_DUPLICATES_ITERATOR_HPP

#if defined(_MSC_VER)
#pragma once
#endif

#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
#include <cstddef>
#include <iterator>

namespace boost{

namespace multi_index{

namespace detail{

/* duplicates_operator is given a range of ordered elements and
 * passes only over those which are duplicated.
 */

template<typename Node,typename Predicate>
class duplicates_iterator
{
public:
  typedef typename Node::value_type        value_type;
  typedef std::ptrdiff_t                   difference_type;
  typedef const typename Node::value_type* pointer;
  typedef const typename Node::value_type& reference;
  typedef std::forward_iterator_tag        iterator_category;

  duplicates_iterator(Node* node_,Node* end_,Predicate pred_):
    node(node_),begin_chunk(0),end(end_),pred(pred_)
  {
    advance();
  }

  duplicates_iterator(Node* end_,Predicate pred_):
    node(end_),begin_chunk(end_),end(end_),pred(pred_)
  {
  }

  reference operator*()const
  {
    return node->value();
  }

  pointer operator->()const
  {
    return &node->value();
  }

  duplicates_iterator& operator++()
  {
    Node::increment(node);
    sync();
    return *this;
  }

  duplicates_iterator operator++(int)
  {
    duplicates_iterator tmp(*this);
    ++(*this);
    return tmp;
  }

  Node* get_node()const{return node;}

private:
  void sync()
  {
    if(node!=end&&pred(begin_chunk->value(),node->value()))advance();
  }

  void advance()
  {
    for(Node* node2=node;node!=end;node=node2){
      Node::increment(node2);
      if(node2!=end&&!pred(node->value(),node2->value()))break;
    }
    begin_chunk=node;
  }

  Node*     node;
  Node*     begin_chunk;
  Node*     end;
  Predicate pred;
};

template<typename Node,typename Predicate>
bool operator==(
  const duplicates_iterator<Node,Predicate>& x,
  const duplicates_iterator<Node,Predicate>& y)
{
  return x.get_node()==y.get_node();
}

template<typename Node,typename Predicate>
bool operator!=(
  const duplicates_iterator<Node,Predicate>& x,
  const duplicates_iterator<Node,Predicate>& y)
{
  return !(x==y);
}

} /* namespace multi_index::detail */

} /* namespace multi_index */

} /* namespace boost */

#endif


code:
/* Copyright 2003-2013 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_HAS_TAG_HPP
#define BOOST_MULTI_INDEX_DETAIL_HAS_TAG_HPP

#if defined(_MSC_VER)
#pragma once
#endif

#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
#include <boost/mpl/contains.hpp>

namespace boost{

namespace multi_index{

namespace detail{

/* determines whether an index type has a given tag in its tag list */

template<typename Tag>
struct has_tag
{
  template<typename Index>
  struct apply:mpl::contains<BOOST_DEDUCED_TYPENAME Index::tag_list,Tag>
  {
  };
};

} /* namespace multi_index::detail */

} /* namespace multi_index */

} /* namespace boost */

#endif


code:
/* Copyright 2003-2013 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_HASH_INDEX_ARGS_HPP
#define BOOST_MULTI_INDEX_DETAIL_HASH_INDEX_ARGS_HPP

#if defined(_MSC_VER)
#pragma once
#endif

#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
#include <boost/functional/hash.hpp>
#include <boost/mpl/aux_/na.hpp>
#include <boost/mpl/eval_if.hpp>
#include <boost/mpl/identity.hpp>
#include <boost/mpl/if.hpp>
#include <boost/multi_index/tag.hpp>
#include <boost/static_assert.hpp>
#include <boost/type_traits/is_same.hpp>
#include <functional>

namespace boost{

namespace multi_index{

namespace detail{

/* Hashed index specifiers can be instantiated in two forms:
 *
 *   (hashed_unique|hashed_non_unique)<
 *     KeyFromValue,
 *     Hash=boost::hash<KeyFromValue::result_type>,
 *     Pred=std::equal_to<KeyFromValue::result_type> >
 *   (hashed_unique|hashed_non_unique)<
 *     TagList,
 *     KeyFromValue,
 *     Hash=boost::hash<KeyFromValue::result_type>,
 *     Pred=std::equal_to<KeyFromValue::result_type> >
 *
 * hashed_index_args implements the machinery to accept this
 * argument-dependent polymorphism.
 */

template<typename KeyFromValue>
struct index_args_default_hash
{
  typedef ::boost::hash<typename KeyFromValue::result_type> type;
};

template<typename KeyFromValue>
struct index_args_default_pred
{
  typedef std::equal_to<typename KeyFromValue::result_type> type;
};

template<typename Arg1,typename Arg2,typename Arg3,typename Arg4>
struct hashed_index_args
{
  typedef is_tag<Arg1> full_form;

  typedef typename mpl::if_<
    full_form,
    Arg1,
    tag< > >::type                                   tag_list_type;
  typedef typename mpl::if_<
    full_form,
    Arg2,
    Arg1>::type                                      key_from_value_type;
  typedef typename mpl::if_<
    full_form,
    Arg3,
    Arg2>::type                                      supplied_hash_type;
  typedef typename mpl::eval_if<
    mpl::is_na<supplied_hash_type>,
    index_args_default_hash<key_from_value_type>,
    mpl::identity<supplied_hash_type>
  >::type                                            hash_type;
  typedef typename mpl::if_<
    full_form,
    Arg4,
    Arg3>::type                                      supplied_pred_type;
  typedef typename mpl::eval_if<
    mpl::is_na<supplied_pred_type>,
    index_args_default_pred<key_from_value_type>,
    mpl::identity<supplied_pred_type>
  >::type                                            pred_type;

  BOOST_STATIC_ASSERT(is_tag<tag_list_type>::value);
  BOOST_STATIC_ASSERT(!mpl::is_na<key_from_value_type>::value);
  BOOST_STATIC_ASSERT(!mpl::is_na<hash_type>::value);
  BOOST_STATIC_ASSERT(!mpl::is_na<pred_type>::value);
};

} /* namespace multi_index::detail */

} /* namespace multi_index */

} /* namespace boost */

#endif


code:
/* Copyright 2003-2014 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_HASH_INDEX_ITERATOR_HPP
#define BOOST_MULTI_INDEX_DETAIL_HASH_INDEX_ITERATOR_HPP

#if defined(_MSC_VER)
#pragma once
#endif

#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
#include <boost/operators.hpp>

#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
#include <boost/serialization/nvp.hpp>
#include <boost/serialization/split_member.hpp>
#include <boost/serialization/version.hpp>
#endif

namespace boost{

namespace multi_index{

namespace detail{

/* Iterator class for hashed indices.
 */

struct hashed_index_global_iterator_tag{};
struct hashed_index_local_iterator_tag{};

template<typename Node,typename BucketArray,typename Category>
class hashed_index_iterator:
  public forward_iterator_helper<
    hashed_index_iterator<Node,BucketArray,Category>,
    typename Node::value_type,
    std::ptrdiff_t,
    const typename Node::value_type*,
    const typename Node::value_type&>
{
public:
  /* coverity[uninit_ctor]: suppress warning */
  hashed_index_iterator(){}
  hashed_index_iterator(Node* node_):node(node_){}

  const typename Node::value_type& operator*()const
  {
    return node->value();
  }

  hashed_index_iterator& operator++()
  {
    this->increment(Category());
    return *this;
  }

#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
  /* Serialization. As for why the following is public,
   * see explanation in safe_mode_iterator notes in safe_mode.hpp.
   */

  BOOST_SERIALIZATION_SPLIT_MEMBER()

  typedef typename Node::base_type node_base_type;

  template<class Archive>
  void save(Archive& ar,const unsigned int)const
  {
    node_base_type* bnode=node;
    ar<<serialization::make_nvp("pointer",bnode);
  }

  template<class Archive>
  void load(Archive& ar,const unsigned int version)
  {
    load(ar,version,Category());
  }

  template<class Archive>
  void load(
    Archive& ar,const unsigned int version,hashed_index_global_iterator_tag)
  {
    node_base_type* bnode;
    ar>>serialization::make_nvp("pointer",bnode);
    node=static_cast<Node*>(bnode);
    if(version<1){
      BucketArray* throw_away; /* consume unused ptr */
      ar>>serialization::make_nvp("pointer",throw_away);
    }
  }

  template<class Archive>
  void load(
    Archive& ar,const unsigned int version,hashed_index_local_iterator_tag)
  {
    node_base_type* bnode;
    ar>>serialization::make_nvp("pointer",bnode);
    node=static_cast<Node*>(bnode);
    if(version<1){
      BucketArray* buckets;
      ar>>serialization::make_nvp("pointer",buckets);
      if(buckets&&node&&node->impl()==buckets->end()->prior()){
        /* end local_iterators used to point to end node, now they are null */
        node=0;
      }
    }
  }
#endif

  /* get_node is not to be used by the user */

  typedef Node node_type;

  Node* get_node()const{return node;}

private:

  void increment(hashed_index_global_iterator_tag)
  {
    Node::increment(node);
  }

  void increment(hashed_index_local_iterator_tag)
  {
    Node::increment_local(node);
  }

  Node* node;
};

template<typename Node,typename BucketArray,typename Category>
bool operator==(
  const hashed_index_iterator<Node,BucketArray,Category>& x,
  const hashed_index_iterator<Node,BucketArray,Category>& y)
{
  return x.get_node()==y.get_node();
}

} /* namespace multi_index::detail */

} /* namespace multi_index */

#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
/* class version = 1 : hashed_index_iterator does no longer serialize a bucket
 * array pointer.
 */

namespace serialization {
template<typename Node,typename BucketArray,typename Category>
struct version<
  boost::multi_index::detail::hashed_index_iterator<Node,BucketArray,Category>
>
{
  BOOST_STATIC_CONSTANT(int,value=1);
};
} /* namespace serialization */
#endif

} /* namespace boost */

#endif


code:
/* Copyright 2003-2015 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_HASH_INDEX_NODE_HPP
#define BOOST_MULTI_INDEX_DETAIL_HASH_INDEX_NODE_HPP

#if defined(_MSC_VER)
#pragma once
#endif

#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
#include <boost/detail/allocator_utilities.hpp>
#include <boost/multi_index/detail/raw_ptr.hpp>
#include <utility>

namespace boost{

namespace multi_index{

namespace detail{

/* Certain C++ requirements on unordered associative containers (see LWG issue
 * #579) imply a data structure where nodes are linked in a single list, which
 * in its turn forces implementors to add additional overhed per node to
 * associate each with its corresponding bucket. Others resort to storing hash
 * values, we use an alternative structure providing unconditional O(1)
 * manipulation, even in situations of unfair hash distribution, plus some
 * lookup speedups. For unique indices we maintain a doubly linked list of
 * nodes except that if N is the first node of a bucket its associated
 * bucket node is embedded between N and the preceding node in the following
 * manner:
 *
 *        +---+   +---+       +---+   +---+
 *     <--+   |<--+   |    <--+   |<--+   |
 *   ...  | B0|   | B1|  ...  | B1|   | B2|  ...
 *        |   |-+ |   +-->    |   |-+ |   +-->
 *        +-+-+ | +---+       +-+-+ | +---+
 *              |   ^               |   ^
 *              |   |               |   |
 *              | +-+               | +-+
 *              | |                 | |
 *              v |                 v |
 *       --+---+---+---+--   --+---+---+---+--
 *     ... |   | B1|   |  ...  |   | B2|   | ...
 *       --+---+---+---+--   --+---+---+---+--
 *
 *
 * The fist and last nodes of buckets can be checked with
 *
 *   first node of a bucket: Npn != N
 *   last node of a bucket:  Nnp != N
 *
 * (n and p short for ->next(), ->prior(), bucket nodes have prior pointers
 * only). Pure insert and erase (without lookup) can be unconditionally done
 * in O(1).
 * For non-unique indices we add the following additional complexity: when
 * there is a group of 3 or more equivalent elements, they are linked as
 * follows:
 *
 *         +-----------------------+
 *         |                       v
 *   +---+ | +---+       +---+   +---+
 *   |   | +-+   |       |   |<--+   |
 *   | F |   | S |  ...  | P |   | L |
 *   |   +-->|   |       |   +-+ |   |
 *   +---+   +---+       +---+ | +---+
 *     ^                       |
 *     +-----------------------+
 *
 * F, S, P and L are the first, second, penultimate and last node in the
 * group, respectively (S and P can coincide if the group has size 3.) This
 * arrangement is used to skip equivalent elements in O(1) when doing lookup,
 * while preserving O(1) insert/erase. The following invariants identify
 * special positions (some of the operations have to be carefully implemented
 * as Xnn is not valid if Xn points to a bucket):
 *
 *   first node of a bucket: Npnp  == N
 *   last node of a bucket:  Nnpp  == N
 *   first node of a group:  Nnp != N && Nnppn == N
 *   second node of a group: Npn != N && Nppnn == N
 *   n-1 node of a group:    Nnp != N && Nnnpp == N
 *   last node of a group:   Npn != N && Npnnp == N
 *
 * The memory overhead is one pointer per bucket plus two pointers per node,
 * probably unbeatable. The resulting structure is bidirectonally traversable,
 * though currently we are just providing forward iteration.
 */

template<typename Allocator>
struct hashed_index_node_impl;

/* half-header (only prior() pointer) to use for the bucket array */

template<typename Allocator>
struct hashed_index_base_node_impl
{
  typedef typename
  boost::detail::allocator::rebind_to<
      Allocator,hashed_index_base_node_impl
  >::type::pointer                          base_pointer;
  typedef typename
  boost::detail::allocator::rebind_to<
    Allocator,hashed_index_base_node_impl
  >::type::const_pointer                    const_base_pointer;
  typedef typename
  boost::detail::allocator::rebind_to<
    Allocator,
    hashed_index_node_impl<Allocator>
  >::type::pointer                          pointer;
  typedef typename
  boost::detail::allocator::rebind_to<
    Allocator,
    hashed_index_node_impl<Allocator>
  >::type::const_pointer                    const_pointer;

  pointer& prior(){return prior_;}
  pointer  prior()const{return prior_;}

private:
  pointer prior_;
};

/* full header (prior() and next()) for the nodes */

template<typename Allocator>
struct hashed_index_node_impl:hashed_index_base_node_impl<Allocator>
{
private:
  typedef hashed_index_base_node_impl<Allocator> super;

public:
  typedef typename super::base_pointer           base_pointer;
  typedef typename super::const_base_pointer     const_base_pointer;
  typedef typename super::pointer                pointer;
  typedef typename super::const_pointer          const_pointer;

  base_pointer& next(){return next_;}
  base_pointer  next()const{return next_;}

  static pointer pointer_from(base_pointer x)
  {
    return static_cast<pointer>(
      static_cast<hashed_index_node_impl*>(
        raw_ptr<super*>(x)));
  }

  static base_pointer base_pointer_from(pointer x)
  {
    return static_cast<base_pointer>(
      raw_ptr<hashed_index_node_impl*>(x));
  }

private:
  base_pointer next_;
};

/* Boost.MultiIndex requires machinery to reverse unlink operations. A simple
 * way to make a pointer-manipulation function undoable is to templatize
 * its internal pointer assignments with a functor that, besides doing the
 * assignment, keeps track of the original pointer values and can later undo
 * the operations in reverse order.
 */

struct default_assigner
{
  template<typename T> void operator()(T& x,const T& val){x=val;}
};

template<typename Node>
struct unlink_undo_assigner
{
  typedef typename Node::base_pointer base_pointer;
  typedef typename Node::pointer      pointer;

  unlink_undo_assigner():pointer_track_count(0),base_pointer_track_count(0){}

  void operator()(pointer& x,pointer val)
  {
    pointer_tracks[pointer_track_count].x=&x;
    pointer_tracks[pointer_track_count++].val=x;
    x=val;
  }

  void operator()(base_pointer& x,base_pointer val)
  {
    base_pointer_tracks[base_pointer_track_count].x=&x;
    base_pointer_tracks[base_pointer_track_count++].val=x;
    x=val;
  }

  void operator()() /* undo op */
  {
    /* in the absence of aliasing, restitution order is immaterial */

    while(pointer_track_count--){
      *(pointer_tracks[pointer_track_count].x)=
        pointer_tracks[pointer_track_count].val;
    }
    while(base_pointer_track_count--){
      *(base_pointer_tracks[base_pointer_track_count].x)=
        base_pointer_tracks[base_pointer_track_count].val;
    }
  }

  struct pointer_track     {pointer*      x; pointer      val;};
  struct base_pointer_track{base_pointer* x; base_pointer val;};

  /* We know the maximum number of pointer and base pointer assignments that
   * the two unlink versions do, so we can statically reserve the needed
   * storage.
   */

  pointer_track      pointer_tracks[3];
  int                pointer_track_count;
  base_pointer_track base_pointer_tracks[2];
  int                base_pointer_track_count;
};

/* algorithmic stuff for unique and non-unique variants */

struct hashed_unique_tag{};
struct hashed_non_unique_tag{};

template<typename Node,typename Category>
struct hashed_index_node_alg;

template<typename Node>
struct hashed_index_node_alg<Node,hashed_unique_tag>
{
  typedef typename Node::base_pointer       base_pointer;
  typedef typename Node::const_base_pointer const_base_pointer;
  typedef typename Node::pointer            pointer;
  typedef typename Node::const_pointer      const_pointer;

  static bool is_first_of_bucket(pointer x)
  {
    return x->prior()->next()!=base_pointer_from(x);
  }

  static pointer after(pointer x)
  {
    return is_last_of_bucket(x)?x->next()->prior():pointer_from(x->next());
  }

  static pointer after_local(pointer x)
  {
    return is_last_of_bucket(x)?pointer(0):pointer_from(x->next());
  }

  static pointer next_to_inspect(pointer x)
  {
    return is_last_of_bucket(x)?pointer(0):pointer_from(x->next());
  }

  static void link(pointer x,base_pointer buc,pointer end)
  {
    if(buc->prior()==pointer(0)){ /* empty bucket */
      x->prior()=end->prior();
      x->next()=end->prior()->next();
      x->prior()->next()=buc;
      buc->prior()=x;
      end->prior()=x;
    }
    else{
      x->prior()=buc->prior()->prior();
      x->next()=base_pointer_from(buc->prior());
      buc->prior()=x;
      x->next()->prior()=x;
    }
  }

  static void unlink(pointer x)
  {
    default_assigner assign;
    unlink(x,assign);
  }

  typedef unlink_undo_assigner<Node> unlink_undo;

  template<typename Assigner>
  static void unlink(pointer x,Assigner& assign)
  {
    if(is_first_of_bucket(x)){
      if(is_last_of_bucket(x)){
        assign(x->prior()->next()->prior(),pointer(0));
        assign(x->prior()->next(),x->next());
        assign(x->next()->prior()->prior(),x->prior());
      }
      else{
        assign(x->prior()->next()->prior(),pointer_from(x->next()));
        assign(x->next()->prior(),x->prior());
      }
    }
    else if(is_last_of_bucket(x)){
      assign(x->prior()->next(),x->next());
      assign(x->next()->prior()->prior(),x->prior());
    }
    else{
      assign(x->prior()->next(),x->next());
      assign(x->next()->prior(),x->prior());
    }
  }

  /* used only at rehashing */

  static void append(pointer x,pointer end)
  {
    x->prior()=end->prior();
    x->next()=end->prior()->next();
    x->prior()->next()=base_pointer_from(x);
    end->prior()=x;
  }

  static bool unlink_last(pointer end)
  {
    /* returns true iff bucket is emptied */

    pointer x=end->prior();
    if(x->prior()->next()==base_pointer_from(x)){
      x->prior()->next()=x->next();
      end->prior()=x->prior();
      return false;
    }
    else{
      x->prior()->next()->prior()=pointer(0);
      x->prior()->next()=x->next();
      end->prior()=x->prior();
      return true;
    }
  }

private:
  static pointer pointer_from(base_pointer x)
  {
    return Node::pointer_from(x);
  }

  static base_pointer base_pointer_from(pointer x)
  {
    return Node::base_pointer_from(x);
  }

  static bool is_last_of_bucket(pointer x)
  {
    return x->next()->prior()!=x;
  }
};

template<typename Node>
struct hashed_index_node_alg<Node,hashed_non_unique_tag>
{
  typedef typename Node::base_pointer       base_pointer;
  typedef typename Node::const_base_pointer const_base_pointer;
  typedef typename Node::pointer            pointer;
  typedef typename Node::const_pointer      const_pointer;

  static bool is_first_of_bucket(pointer x)
  {
    return x->prior()->next()->prior()==x;
  }

  static bool is_first_of_group(pointer x)
  {
    return
      x->next()->prior()!=x&&
      x->next()->prior()->prior()->next()==base_pointer_from(x);
  }

  static pointer after(pointer x)
  {
    if(x->next()->prior()==x)return pointer_from(x->next());
    if(x->next()->prior()->prior()==x)return x->next()->prior();
    if(x->next()->prior()->prior()->next()==base_pointer_from(x))
      return pointer_from(x->next());
    return pointer_from(x->next())->next()->prior();
  }

  static pointer after_local(pointer x)
  {
    if(x->next()->prior()==x)return pointer_from(x->next());
    if(x->next()->prior()->prior()==x)return pointer(0);
    if(x->next()->prior()->prior()->next()==base_pointer_from(x))
      return pointer_from(x->next());
    return pointer_from(x->next())->next()->prior();
  }

  static pointer next_to_inspect(pointer x)
  {
    if(x->next()->prior()==x)return pointer_from(x->next());
    if(x->next()->prior()->prior()==x)return pointer(0);
    if(x->next()->prior()->next()->prior()!=x->next()->prior())
      return pointer(0);
    return pointer_from(x->next()->prior()->next());
  }

  static void link(pointer x,base_pointer buc,pointer end)
  {
    if(buc->prior()==pointer(0)){ /* empty bucket */
      x->prior()=end->prior();
      x->next()=end->prior()->next();
      x->prior()->next()=buc;
      buc->prior()=x;
      end->prior()=x;
    }
    else{
      x->prior()=buc->prior()->prior();
      x->next()=base_pointer_from(buc->prior());
      buc->prior()=x;
      x->next()->prior()=x;
    }
  };

  static void link(pointer x,pointer first,pointer last)
  {
    x->prior()=first->prior();
    x->next()=base_pointer_from(first);
    if(is_first_of_bucket(first)){
      x->prior()->next()->prior()=x;
    }
    else{
      x->prior()->next()=base_pointer_from(x);
    }

    if(first==last){
      last->prior()=x;
    }
    else if(first->next()==base_pointer_from(last)){
      first->prior()=last;
      first->next()=base_pointer_from(x);
    }
    else{
      pointer second=pointer_from(first->next()),
              lastbutone=last->prior();
      second->prior()=first;
      first->prior()=last;
      lastbutone->next()=base_pointer_from(x);
    }
  }

  static void unlink(pointer x)
  {
    default_assigner assign;
    unlink(x,assign);
  }

  typedef unlink_undo_assigner<Node> unlink_undo;

  template<typename Assigner>
  static void unlink(pointer x,Assigner& assign)
  {
    if(x->prior()->next()==base_pointer_from(x)){
      if(x->next()->prior()==x){
        left_unlink(x,assign);
        right_unlink(x,assign);
      }
      else if(x->next()->prior()->prior()==x){           /* last of bucket */
        left_unlink(x,assign);
        right_unlink_last_of_bucket(x,assign);
      }
      else if(x->next()->prior()->prior()->next()==
              base_pointer_from(x)){                /* first of group size */
        left_unlink(x,assign);
        right_unlink_first_of_group(x,assign);
      }
      else{                                                /* n-1 of group */
        unlink_last_but_one_of_group(x,assign);
      }
    }
    else if(x->prior()->next()->prior()==x){            /* first of bucket */
      if(x->next()->prior()==x){
        left_unlink_first_of_bucket(x,assign);
        right_unlink(x,assign);
      }
      else if(x->next()->prior()->prior()==x){           /* last of bucket */
        assign(x->prior()->next()->prior(),pointer(0));
        assign(x->prior()->next(),x->next());
        assign(x->next()->prior()->prior(),x->prior());
      }
      else{                                              /* first of group */
        left_unlink_first_of_bucket(x,assign);
        right_unlink_first_of_group(x,assign);
      }
    }
    else if(x->next()->prior()->prior()==x){   /* last of group and bucket */
      left_unlink_last_of_group(x,assign);
      right_unlink_last_of_bucket(x,assign);
    }
    else if(pointer_from(x->prior()->prior()->next())
            ->next()==base_pointer_from(x)){            /* second of group */
      unlink_second_of_group(x,assign);
    }
    else{                              /* last of group, ~(last of bucket) */
      left_unlink_last_of_group(x,assign);
      right_unlink(x,assign);
    }
  }

  /* used only at rehashing */

  static void link_range(
    pointer first,pointer last,base_pointer buc,pointer cend)
  {
    if(buc->prior()==pointer(0)){ /* empty bucket */
      first->prior()=cend->prior();
      last->next()=cend->prior()->next();
      first->prior()->next()=buc;
      buc->prior()=first;
      cend->prior()=last;
    }
    else{
      first->prior()=buc->prior()->prior();
      last->next()=base_pointer_from(buc->prior());
      buc->prior()=first;
      last->next()->prior()=last;
    }
  }

  static void append_range(pointer first,pointer last,pointer cend)
  {
    first->prior()=cend->prior();
    last->next()=cend->prior()->next();
    first->prior()->next()=base_pointer_from(first);
    cend->prior()=last;
  }

  static std::pair<pointer,bool> unlink_last_group(pointer end)
  {
    /* returns first of group true iff bucket is emptied */

    pointer x=end->prior();
    if(x->prior()->next()==base_pointer_from(x)){
      x->prior()->next()=x->next();
      end->prior()=x->prior();
      return std::make_pair(x,false);
    }
    else if(x->prior()->next()->prior()==x){
      x->prior()->next()->prior()=pointer(0);
      x->prior()->next()=x->next();
      end->prior()=x->prior();
      return std::make_pair(x,true);
    }
    else{
      pointer y=pointer_from(x->prior()->next());

      if(y->prior()->next()==base_pointer_from(y)){
        y->prior()->next()=x->next();
        end->prior()=y->prior();
        return std::make_pair(y,false);
      }
      else{
        y->prior()->next()->prior()=pointer(0);
        y->prior()->next()=x->next();
        end->prior()=y->prior();
        return std::make_pair(y,true);
      }
    }
  }

  static void unlink_range(pointer first,pointer last)
  {
    if(is_first_of_bucket(first)){
      if(is_last_of_bucket(last)){
        first->prior()->next()->prior()=pointer(0);
        first->prior()->next()=last->next();
        last->next()->prior()->prior()=first->prior();
      }
      else{
        first->prior()->next()->prior()=pointer_from(last->next());
        last->next()->prior()=first->prior();
      }
    }
    else if(is_last_of_bucket(last)){
      first->prior()->next()=last->next();
      last->next()->prior()->prior()=first->prior();
    }
    else{
      first->prior()->next()=last->next();
      last->next()->prior()=first->prior();
    }
  }

private:
  static pointer pointer_from(base_pointer x)
  {
    return Node::pointer_from(x);
  }

  static base_pointer base_pointer_from(pointer x)
  {
    return Node::base_pointer_from(x);
  }

  static bool is_last_of_bucket(pointer x)
  {
    return x->next()->prior()->prior()==x;
  }

  template<typename Assigner>
  static void left_unlink(pointer x,Assigner& assign)
  {
    assign(x->prior()->next(),x->next());
  }

  template<typename Assigner>
  static void right_unlink(pointer x,Assigner& assign)
  {
    assign(x->next()->prior(),x->prior());
  }

  template<typename Assigner>
  static void left_unlink_first_of_bucket(pointer x,Assigner& assign)
  {
    assign(x->prior()->next()->prior(),pointer_from(x->next()));
  }

  template<typename Assigner>
  static void right_unlink_last_of_bucket(pointer x,Assigner& assign)
  {
    assign(x->next()->prior()->prior(),x->prior());
  }

  template<typename Assigner>
  static void right_unlink_first_of_group(pointer x,Assigner& assign)
  {
    pointer second=pointer_from(x->next()),
            last=second->prior(),
            lastbutone=last->prior();
    if(second==lastbutone){
      assign(second->next(),base_pointer_from(last));
      assign(second->prior(),x->prior());
    }
    else{
      assign(lastbutone->next(),base_pointer_from(second));
      assign(second->next()->prior(),last);
      assign(second->prior(),x->prior());
    }
  }

  template<typename Assigner>
  static void left_unlink_last_of_group(pointer x,Assigner& assign)
  {
    pointer lastbutone=x->prior(),
            first=pointer_from(lastbutone->next()),
            second=pointer_from(first->next());
    if(lastbutone==second){
      assign(lastbutone->prior(),first);
      assign(lastbutone->next(),x->next());
    }
    else{
      assign(second->prior(),lastbutone);
      assign(lastbutone->prior()->next(),base_pointer_from(first));
      assign(lastbutone->next(),x->next());
    }
  }

  template<typename Assigner>
  static void unlink_last_but_one_of_group(pointer x,Assigner& assign)
  {
    pointer first=pointer_from(x->next()),
            second=pointer_from(first->next()),
            last=second->prior();
    if(second==x){
      assign(last->prior(),first);
      assign(first->next(),base_pointer_from(last));
    }
    else{
      assign(last->prior(),x->prior());
      assign(x->prior()->next(),base_pointer_from(first));
    }
  }

  template<typename Assigner>
  static void unlink_second_of_group(pointer x,Assigner& assign)
  {
    pointer last=x->prior(),
            lastbutone=last->prior(),
            first=pointer_from(lastbutone->next());
    if(lastbutone==x){
      assign(first->next(),base_pointer_from(last));
      assign(last->prior(),first);
    }
    else{
      assign(first->next(),x->next());
      assign(x->next()->prior(),last);
    }
  }
};

template<typename Super>
struct hashed_index_node_trampoline:
  hashed_index_node_impl<
    typename boost::detail::allocator::rebind_to<
      typename Super::allocator_type,
      char
    >::type
  >
{
  typedef typename boost::detail::allocator::rebind_to<
    typename Super::allocator_type,
    char
  >::type                                               impl_allocator_type;
  typedef hashed_index_node_impl<impl_allocator_type>   impl_type;
};

template<typename Super,typename Category>
struct hashed_index_node:
  Super,hashed_index_node_trampoline<Super>
{
private:
  typedef hashed_index_node_trampoline<Super> trampoline;

public:
  typedef typename trampoline::impl_type          impl_type;
  typedef hashed_index_node_alg<
    impl_type,Category>                           node_alg;
  typedef typename trampoline::base_pointer       impl_base_pointer;
  typedef typename trampoline::const_base_pointer const_impl_base_pointer;
  typedef typename trampoline::pointer            impl_pointer;
  typedef typename trampoline::const_pointer      const_impl_pointer;

  impl_pointer&      prior(){return trampoline::prior();}
  impl_pointer       prior()const{return trampoline::prior();}
  impl_base_pointer& next(){return trampoline::next();}
  impl_base_pointer  next()const{return trampoline::next();}

  impl_pointer impl()
  {
    return static_cast<impl_pointer>(
      static_cast<impl_type*>(static_cast<trampoline*>(this)));
  }

  const_impl_pointer impl()const
  {
    return static_cast<const_impl_pointer>(
      static_cast<const impl_type*>(static_cast<const trampoline*>(this)));
  }

  static hashed_index_node* from_impl(impl_pointer x)
  {
    return
      static_cast<hashed_index_node*>(
        static_cast<trampoline*>(
          raw_ptr<impl_type*>(x)));
  }

  static const hashed_index_node* from_impl(const_impl_pointer x)
  {
    return
      static_cast<const hashed_index_node*>(
        static_cast<const trampoline*>(
          raw_ptr<const impl_type*>(x)));
  }

  /* interoperability with hashed_index_iterator */

  static void increment(hashed_index_node*& x)
  {
    x=from_impl(node_alg::after(x->impl()));
  }

  static void increment_local(hashed_index_node*& x)
  {
    x=from_impl(node_alg::after_local(x->impl()));
  }
};

} /* namespace multi_index::detail */

} /* namespace multi_index */

} /* namespace boost */

#endif


code:
/* 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_HEADER_HOLDER_HPP
#define BOOST_MULTI_INDEX_DETAIL_HEADER_HOLDER_HPP

#if defined(_MSC_VER)
#pragma once
#endif

#include <boost/noncopyable.hpp>

namespace boost{

namespace multi_index{

namespace detail{

/* A utility class used to hold a pointer to the header node.
 * The base from member idiom is used because index classes, which are
 * superclasses of multi_index_container, need this header in construction
 * time. The allocation is made by the allocator of the multi_index_container
 * class --hence, this allocator needs also be stored resorting
 * to the base from member trick.
 */

template<typename NodeTypePtr,typename Final>
struct header_holder:private noncopyable
{
  header_holder():member(final().allocate_node()){}
  ~header_holder(){final().deallocate_node(&*member);}

  NodeTypePtr member;

private:
  Final& final(){return *static_cast<Final*>(this);}
};

} /* namespace multi_index::detail */

} /* namespace multi_index */

} /* namespace boost */

#endif


code:
/* Copyright 2003-2014 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_INDEX_BASE_HPP
#define BOOST_MULTI_INDEX_DETAIL_INDEX_BASE_HPP

#if defined(_MSC_VER)
#pragma once
#endif

#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
#include <boost/detail/allocator_utilities.hpp>
#include <boost/detail/no_exceptions_support.hpp>
#include <boost/detail/workaround.hpp>
#include <boost/move/core.hpp>
#include <boost/move/utility.hpp>
#include <boost/mpl/vector.hpp>
#include <boost/multi_index/detail/copy_map.hpp>
#include <boost/multi_index/detail/do_not_copy_elements_tag.hpp>
#include <boost/multi_index/detail/node_type.hpp>
#include <boost/multi_index/detail/vartempl_support.hpp>
#include <boost/multi_index_container_fwd.hpp>
#include <boost/tuple/tuple.hpp>
#include <utility>

#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
#include <boost/multi_index/detail/index_loader.hpp>
#include <boost/multi_index/detail/index_saver.hpp>
#endif

namespace boost{

namespace multi_index{

namespace detail{

/* The role of this class is threefold:
 *   - tops the linear hierarchy of indices.
 *   - terminates some cascading backbone function calls (insert_, etc.),
 *   - grants access to the backbone functions of the final
 *     multi_index_container class (for access restriction reasons, these
 *     cannot be called directly from the index classes.)
 */

struct lvalue_tag{};
struct rvalue_tag{};
struct emplaced_tag{};

template<typename Value,typename IndexSpecifierList,typename Allocator>
class index_base
{
protected:
  typedef index_node_base<Value,Allocator>    node_type;
  typedef typename multi_index_node_type<
    Value,IndexSpecifierList,Allocator>::type final_node_type;
  typedef multi_index_container<
    Value,IndexSpecifierList,Allocator>       final_type;
  typedef tuples::null_type                   ctor_args_list;
  typedef typename
  boost::detail::allocator::rebind_to<
    Allocator,
    typename Allocator::value_type
  >::type                                     final_allocator_type;
  typedef mpl::vector0<>                      index_type_list;
  typedef mpl::vector0<>                      iterator_type_list;
  typedef mpl::vector0<>                      const_iterator_type_list;
  typedef copy_map<
    final_node_type,
    final_allocator_type>                     copy_map_type;

#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
  typedef index_saver<
    node_type,
    final_allocator_type>                     index_saver_type;
  typedef index_loader<
    node_type,
    final_node_type,
    final_allocator_type>                     index_loader_type;
#endif

private:
  typedef Value                               value_type;

protected:
  explicit index_base(const ctor_args_list&,const Allocator&){}

  index_base(
    const index_base<Value,IndexSpecifierList,Allocator>&,
    do_not_copy_elements_tag)
  {}

  void copy_(
    const index_base<Value,IndexSpecifierList,Allocator>&,const copy_map_type&)
  {}

  final_node_type* insert_(const value_type& v,final_node_type*& x,lvalue_tag)
  {
    x=final().allocate_node();
    BOOST_TRY{
      boost::detail::allocator::construct(&x->value(),v);
    }
    BOOST_CATCH(...){
      final().deallocate_node(x);
      BOOST_RETHROW;
    }
    BOOST_CATCH_END
    return x;
  }

  final_node_type* insert_(const value_type& v,final_node_type*& x,rvalue_tag)
  {
    x=final().allocate_node();
    BOOST_TRY{
      /* This shoud have used a modified, T&&-compatible version of
       * boost::detail::allocator::construct, but
       * <boost/detail/allocator_utilities.hpp> is too old and venerable to
       * mess with; besides, it is a general internal utility and the imperfect
       * perfect forwarding emulation of Boost.Move might break other libs.
       */

      new (&x->value()) value_type(boost::move(const_cast<value_type&>(v)));
    }
    BOOST_CATCH(...){
      final().deallocate_node(x);
      BOOST_RETHROW;
    }
    BOOST_CATCH_END
    return x;
  }

  final_node_type* insert_(const value_type&,final_node_type*& x,emplaced_tag)
  {
    return x;
  }

  final_node_type* insert_(
    const value_type& v,node_type*,final_node_type*& x,lvalue_tag)
  {
    return insert_(v,x,lvalue_tag());
  }

  final_node_type* insert_(
    const value_type& v,node_type*,final_node_type*& x,rvalue_tag)
  {
    return insert_(v,x,rvalue_tag());
  }

  final_node_type* insert_(
    const value_type&,node_type*,final_node_type*& x,emplaced_tag)
  {
    return x;
  }

  void erase_(node_type* x)
  {
    boost::detail::allocator::destroy(&x->value());
  }

  void delete_node_(node_type* x)
  {
    boost::detail::allocator::destroy(&x->value());
  }

  void clear_(){}

  void swap_(index_base<Value,IndexSpecifierList,Allocator>&){}

  void swap_elements_(index_base<Value,IndexSpecifierList,Allocator>&){}

  bool replace_(const value_type& v,node_type* x,lvalue_tag)
  {
    x->value()=v;
    return true;
  }

  bool replace_(const value_type& v,node_type* x,rvalue_tag)
  {
    x->value()=boost::move(const_cast<value_type&>(v));
    return true;
  }

  bool modify_(node_type*){return true;}

  bool modify_rollback_(node_type*){return true;}

#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
  /* serialization */

  template<typename Archive>
  void save_(Archive&,const unsigned int,const index_saver_type&)const{}

  template<typename Archive>
  void load_(Archive&,const unsigned int,const index_loader_type&){}
#endif

#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
  /* invariant stuff */

  bool invariant_()const{return true;}
#endif

  /* access to backbone memfuns of Final class */

  final_type&       final(){return *static_cast<final_type*>(this);}
  const final_type& final()const{return *static_cast<const final_type*>(this);}

  final_node_type* final_header()const{return final().header();}

  bool        final_empty_()const{return final().empty_();}
  std::size_t final_size_()const{return final().size_();}
  std::size_t final_max_size_()const{return final().max_size_();}

  std::pair<final_node_type*,bool> final_insert_(const value_type& x)
    {return final().insert_(x);}
  std::pair<final_node_type*,bool> final_insert_rv_(const value_type& x)
    {return final().insert_rv_(x);}
  template<typename T>
  std::pair<final_node_type*,bool> final_insert_ref_(const T& t)
    {return final().insert_ref_(t);}
  template<typename T>
  std::pair<final_node_type*,bool> final_insert_ref_(T& t)
    {return final().insert_ref_(t);}

  template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
  std::pair<final_node_type*,bool> final_emplace_(
    BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
  {
    return final().emplace_(BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
  }

  std::pair<final_node_type*,bool> final_insert_(
    const value_type& x,final_node_type* position)
    {return final().insert_(x,position);}
  std::pair<final_node_type*,bool> final_insert_rv_(
    const value_type& x,final_node_type* position)
    {return final().insert_rv_(x,position);}
  template<typename T>
  std::pair<final_node_type*,bool> final_insert_ref_(
    const T& t,final_node_type* position)
    {return final().insert_ref_(t,position);}
  template<typename T>
  std::pair<final_node_type*,bool> final_insert_ref_(
    T& t,final_node_type* position)
    {return final().insert_ref_(t,position);}

  template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
  std::pair<final_node_type*,bool> final_emplace_hint_(
    final_node_type* position,BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
  {
    return final().emplace_hint_(
      position,BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
  }

  void final_erase_(final_node_type* x){final().erase_(x);}

  void final_delete_node_(final_node_type* x){final().delete_node_(x);}
  void final_delete_all_nodes_(){final().delete_all_nodes_();}
  void final_clear_(){final().clear_();}

  void final_swap_(final_type& x){final().swap_(x);}

  bool final_replace_(
    const value_type& k,final_node_type* x)
    {return final().replace_(k,x);}
  bool final_replace_rv_(
    const value_type& k,final_node_type* x)
    {return final().replace_rv_(k,x);}

  template<typename Modifier>
  bool final_modify_(Modifier& mod,final_node_type* x)
    {return final().modify_(mod,x);}

  template<typename Modifier,typename Rollback>
  bool final_modify_(Modifier& mod,Rollback& back,final_node_type* x)
    {return final().modify_(mod,back,x);}

#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
  void final_check_invariant_()const{final().check_invariant_();}
#endif
};

} /* namespace multi_index::detail */

} /* namespace multi_index */

} /* namespace boost */

#endif


code:
/* Copyright 2003-2015 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_INDEX_LOADER_HPP
#define BOOST_MULTI_INDEX_DETAIL_INDEX_LOADER_HPP

#if defined(_MSC_VER)
#pragma once
#endif

#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
#include <algorithm>
#include <boost/archive/archive_exception.hpp>
#include <boost/noncopyable.hpp>
#include <boost/multi_index/detail/auto_space.hpp>
#include <boost/multi_index/detail/raw_ptr.hpp>
#include <boost/serialization/nvp.hpp>
#include <boost/throw_exception.hpp>
#include <cstddef>

namespace boost{

namespace multi_index{

namespace detail{

/* Counterpart of index_saver (check index_saver.hpp for serialization
 * details.)* multi_index_container is in charge of supplying the info about
 * the base sequence, and each index can subsequently load itself using the
 * const interface of index_loader.
 */

template<typename Node,typename FinalNode,typename Allocator>
class index_loader:private noncopyable
{
public:
  index_loader(const Allocator& al,std::size_t size):
    spc(al,size),size_(size),n(0),sorted(false)
  {
  }

  template<class Archive>
  void add(Node* node,Archive& ar,const unsigned int)
  {
    ar>>serialization::make_nvp("position",*node);
    entries()[n++]=node;
  }

  template<class Archive>
  void add_track(Node* node,Archive& ar,const unsigned int)
  {
    ar>>serialization::make_nvp("position",*node);
  }

  /* A rearranger is passed two nodes, and is expected to
   * reposition the second after the first.
   * If the first node is 0, then the second should be moved
   * to the beginning of the sequence.
   */

  template<typename Rearranger,class Archive>
  void load(Rearranger r,Archive& ar,const unsigned int)const
  {
    FinalNode* prev=unchecked_load_node(ar);
    if(!prev)return;

    if(!sorted){
      std::sort(entries(),entries()+size_);
      sorted=true;
    }

    check_node(prev);

    for(;;){
      for(;;){
        FinalNode* node=load_node(ar);
        if(!node)break;

        if(node==prev)prev=0;
        r(prev,node);

        prev=node;
      }
      prev=load_node(ar);
      if(!prev)break;
    }
  }

private:
  Node** entries()const{return raw_ptr<Node**>(spc.data());}

  /* We try to delay sorting as much as possible just in case it
   * is not necessary, hence this version of load_node.
   */

  template<class Archive>
  FinalNode* unchecked_load_node(Archive& ar)const
  {
    Node* node=0;
    ar>>serialization::make_nvp("pointer",node);
    return static_cast<FinalNode*>(node);
  }

  template<class Archive>
  FinalNode* load_node(Archive& ar)const
  {
    Node* node=0;
    ar>>serialization::make_nvp("pointer",node);
    check_node(node);
    return static_cast<FinalNode*>(node);
  }

  void check_node(Node* node)const
  {
    if(node!=0&&!std::binary_search(entries(),entries()+size_,node)){
      throw_exception(
        archive::archive_exception(
          archive::archive_exception::other_exception));
    }
  }

  auto_space<Node*,Allocator> spc;
  std::size_t                 size_;
  std::size_t                 n;
  mutable bool                sorted;
};

} /* namespace multi_index::detail */

} /* namespace multi_index */

} /* namespace boost */

#endif


code:
/* Copyright 2003-2015 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_INDEX_MATCHER_HPP
#define BOOST_MULTI_INDEX_DETAIL_INDEX_MATCHER_HPP

#if defined(_MSC_VER)
#pragma once
#endif

#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
#include <algorithm>
#include <boost/noncopyable.hpp>
#include <boost/multi_index/detail/auto_space.hpp>
#include <boost/multi_index/detail/raw_ptr.hpp>
#include <cstddef>
#include <functional>

namespace boost{

namespace multi_index{

namespace detail{

/* index_matcher compares a sequence of elements against a
 * base sequence, identifying those elements that belong to the
 * longest subsequence which is ordered with respect to the base.
 * For instance, if the base sequence is:
 *
 *   0 1 2 3 4 5 6 7 8 9
 *
 * and the compared sequence (not necesarilly the same length):
 *
 *   1 4 2 3 0 7 8 9
 *
 * the elements of the longest ordered subsequence are:
 *
 *   1 2 3 7 8 9
 *
 * The algorithm for obtaining such a subsequence is called
 * Patience Sorting, described in ch. 1 of:
 *   Aldous, D., Diaconis, P.: "Longest increasing subsequences: from
 *   patience sorting to the Baik-Deift-Johansson Theorem", Bulletin
 *   of the American Mathematical Society, vol. 36, no 4, pp. 413-432,
 *   July 1999.
 *   http://www.ams.org/bull/1999-36-04/S0273-0979-99-00796-X/
 *   S0273-0979-99-00796-X.pdf
 *
 * This implementation is not fully generic since it assumes that
 * the sequences given are pointed to by index iterators (having a
 * get_node() memfun.)
 */

namespace index_matcher{

/* The algorithm stores the nodes of the base sequence and a number
 * of "piles" that are dynamically updated during the calculation
 * stage. From a logical point of view, nodes form an independent
 * sequence from piles. They are stored together so as to minimize
 * allocated memory.
 */

struct entry
{
  entry(void* node_,std::size_t pos_=0):node(node_),pos(pos_){}

  /* node stuff */

  void*       node;
  std::size_t pos;
  entry*      previous;
  bool        ordered;

  struct less_by_node
  {
    bool operator()(
      const entry& x,const entry& y)const
    {
      return std::less<void*>()(x.node,y.node);
    }
  };

  /* pile stuff */

  std::size_t pile_top;
  entry*      pile_top_entry;

  struct less_by_pile_top
  {
    bool operator()(
      const entry& x,const entry& y)const
    {
      return x.pile_top<y.pile_top;
    }
  };
};

/* common code operating on void *'s */

template<typename Allocator>
class algorithm_base:private noncopyable
{
protected:
  algorithm_base(const Allocator& al,std::size_t size):
    spc(al,size),size_(size),n_(0),sorted(false)
  {
  }

  void add(void* node)
  {
    entries()[n_]=entry(node,n_);
    ++n_;
  }

  void begin_algorithm()const
  {
    if(!sorted){
      std::sort(entries(),entries()+size_,entry::less_by_node());
      sorted=true;
    }
    num_piles=0;
  }

  void add_node_to_algorithm(void* node)const
  {
    entry* ent=
      std::lower_bound(
        entries(),entries()+size_,
        entry(node),entry::less_by_node()); /* localize entry */
    ent->ordered=false;
    std::size_t n=ent->pos;                 /* get its position */

    entry dummy(0);
    dummy.pile_top=n;

    entry* pile_ent=                        /* find the first available pile */
      std::lower_bound(                     /* to stack the entry            */
        entries(),entries()+num_piles,
        dummy,entry::less_by_pile_top());

    pile_ent->pile_top=n;                   /* stack the entry */
    pile_ent->pile_top_entry=ent;

    /* if not the first pile, link entry to top of the preceding pile */
    if(pile_ent>&entries()[0]){
      ent->previous=(pile_ent-1)->pile_top_entry;
    }

    if(pile_ent==&entries()[num_piles]){    /* new pile? */
      ++num_piles;
    }
  }

  void finish_algorithm()const
  {
    if(num_piles>0){
      /* Mark those elements which are in their correct position, i.e. those
       * belonging to the longest increasing subsequence. These are those
       * elements linked from the top of the last pile.
       */

      entry* ent=entries()[num_piles-1].pile_top_entry;
      for(std::size_t n=num_piles;n--;){
        ent->ordered=true;
        ent=ent->previous;
      }
    }
  }

  bool is_ordered(void * node)const
  {
    return std::lower_bound(
      entries(),entries()+size_,
      entry(node),entry::less_by_node())->ordered;
  }

private:
  entry* entries()const{return raw_ptr<entry*>(spc.data());}

  auto_space<entry,Allocator> spc;
  std::size_t                 size_;
  std::size_t                 n_;
  mutable bool                sorted;
  mutable std::size_t         num_piles;
};

/* The algorithm has three phases:
 *   - Initialization, during which the nodes of the base sequence are added.
 *   - Execution.
 *   - Results querying, through the is_ordered memfun.
 */

template<typename Node,typename Allocator>
class algorithm:private algorithm_base<Allocator>
{
  typedef algorithm_base<Allocator> super;

public:
  algorithm(const Allocator& al,std::size_t size):super(al,size){}

  void add(Node* node)
  {
    super::add(node);
  }

  template<typename IndexIterator>
  void execute(IndexIterator first,IndexIterator last)const
  {
    super::begin_algorithm();

    for(IndexIterator it=first;it!=last;++it){
      add_node_to_algorithm(get_node(it));
    }

    super::finish_algorithm();
  }

  bool is_ordered(Node* node)const
  {
    return super::is_ordered(node);
  }

private:
  void add_node_to_algorithm(Node* node)const
  {
    super::add_node_to_algorithm(node);
  }

  template<typename IndexIterator>
  static Node* get_node(IndexIterator it)
  {
    return static_cast<Node*>(it.get_node());
  }
};

} /* namespace multi_index::detail::index_matcher */

} /* namespace multi_index::detail */

} /* namespace multi_index */

} /* namespace boost */

#endif


code:
/* Copyright 2003-2015 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_INDEX_NODE_BASE_HPP
#define BOOST_MULTI_INDEX_DETAIL_INDEX_NODE_BASE_HPP

#if defined(_MSC_VER)
#pragma once
#endif

#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
#include <boost/type_traits/aligned_storage.hpp>
#include <boost/type_traits/alignment_of.hpp>

#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
#include <boost/archive/archive_exception.hpp>
#include <boost/serialization/access.hpp>
#include <boost/throw_exception.hpp>
#endif

namespace boost{

namespace multi_index{

namespace detail{

/* index_node_base tops the node hierarchy of multi_index_container. It holds
 * the value of the element contained.
 */

template<typename Value>
struct pod_value_holder
{
  typename aligned_storage<
    sizeof(Value),
    alignment_of<Value>::value
  >::type                      space;
};

template<typename Value,typename Allocator>
struct index_node_base:private pod_value_holder<Value>
{
  typedef index_node_base base_type; /* used for serialization purposes */
  typedef Value           value_type;
  typedef Allocator       allocator_type;

  value_type& value()
  {
    return *reinterpret_cast<value_type*>(&this->space);
  }

  const value_type& value()const
  {
    return *reinterpret_cast<const value_type*>(&this->space);
  }

  static index_node_base* from_value(const value_type* p)
  {
    return static_cast<index_node_base *>(
      reinterpret_cast<pod_value_holder<Value>*>( /* std 9.2.17 */
        const_cast<value_type*>(p)));
  }

private:
#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
  friend class boost::serialization::access;

  /* nodes do not emit any kind of serialization info. They are
   * fed to Boost.Serialization so that pointers to nodes are
   * tracked correctly.
   */

  template<class Archive>
  void serialize(Archive&,const unsigned int)
  {
  }
#endif
};

template<typename Node,typename Value>
Node* node_from_value(const Value* p)
{
  typedef typename Node::allocator_type allocator_type;
  return static_cast<Node*>(
    index_node_base<Value,allocator_type>::from_value(p));
}

} /* namespace multi_index::detail */

} /* namespace multi_index */

#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
/* Index nodes never get constructed directly by Boost.Serialization,
 * as archives are always fed pointers to previously existent
 * nodes. So, if this is called it means we are dealing with a
 * somehow invalid archive.
 */

#if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
namespace serialization{
#else
namespace multi_index{
namespace detail{
#endif

template<class Archive,typename Value,typename Allocator>
inline void load_construct_data(
  Archive&,boost::multi_index::detail::index_node_base<Value,Allocator>*,
  const unsigned int)
{
  throw_exception(
    archive::archive_exception(archive::archive_exception::other_exception));
}

#if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
} /* namespace serialization */
#else
} /* namespace multi_index::detail */
} /* namespace multi_index */
#endif

#endif

} /* namespace boost */

#endif