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

 * Distributed under the Boost Software License, Version 1.0.

 * (See accompanying file LICENSE_1_0.txt or copy at

 * http://www.boost.org/LICENSE_1_0.txt)

 *

 * See http://www.boost.org/libs/multi_index for library home page.

 */

#ifndef BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_NODE_HPP

#define BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_NODE_HPP

#if defined(_MSC_VER)&&(_MSC_VER>=1200)

#pragma once

#endif

#include <algorithm>

namespace boost{

namespace multi_index{

namespace detail{

/* doubly-linked node for use by sequenced_index */

struct sequenced_index_node_impl

{

  sequenced_index_node_impl*& prior(){return prior_;}

  sequenced_index_node_impl*  prior()const{return prior_;}

  sequenced_index_node_impl*& next(){return next_;}

  sequenced_index_node_impl*  next()const{return next_;}

  /* interoperability with bidir_node_iterator */

  static void increment(sequenced_index_node_impl*& x){x=x->next();}

  static void decrement(sequenced_index_node_impl*& x){x=x->prior();}

  /* algorithmic stuff */

  static void link(

    sequenced_index_node_impl* x,sequenced_index_node_impl* header)

  {

    x->prior()=header->prior();

    x->next()=header;

    x->prior()->next()=x->next()->prior()=x;

  };

  static void unlink(sequenced_index_node_impl* x)

  {

    x->prior()->next()=x->next();

    x->next()->prior()=x->prior();

  }

  static void relink(

    sequenced_index_node_impl* position,sequenced_index_node_impl* x)

  {

    unlink(x);

    x->prior()=position->prior();

    x->next()=position;

    x->prior()->next()=x->next()->prior()=x;

  }

  static void relink(

    sequenced_index_node_impl* position,

    sequenced_index_node_impl* x,sequenced_index_node_impl* y)

  {

    /* position is assumed not to be in [x,y) */

    if(x!=y){

      sequenced_index_node_impl* z=y->prior();

      x->prior()->next()=y;

      y->prior()=x->prior();

      x->prior()=position->prior();

      z->next()=position;

      x->prior()->next()=x;

      z->next()->prior()=z;

    }

  }

  static void reverse(sequenced_index_node_impl* header)

  {

    sequenced_index_node_impl* x=header;

    do{

      sequenced_index_node_impl* y=x->next();

      std::swap(x->prior(),x->next());

      x=y;

    }while(x!=header);

  }

  static void swap(sequenced_index_node_impl* x,sequenced_index_node_impl* y)

  {

    /* This swap function does not exchange the header nodes,

     * but rather their pointers. This is *not* used for implementing

     * sequenced_index::swap.

     */

    if(x->next()!=x){

      if(y->next()!=y){

        std::swap(x->next(),y->next());

        std::swap(x->prior(),y->prior());

        x->next()->prior()=x->prior()->next()=x;

        y->next()->prior()=y->prior()->next()=y;

      }

      else{

        y->next()=x->next();

        y->prior()=x->prior();

        x->next()=x->prior()=x;

        y->next()->prior()=y->prior()->next()=y;

      }

    }

    else if(y->next()!=y){

      x->next()=y->next();

      x->prior()=y->prior();

      y->next()=y->prior()=y;

      x->next()->prior()=x->prior()->next()=x;

    }

  }

private:

  sequenced_index_node_impl* prior_;

  sequenced_index_node_impl* next_;

};

template<typename Super>

struct sequenced_index_node_trampoline:sequenced_index_node_impl{};

template<typename Super>

struct sequenced_index_node:Super,sequenced_index_node_trampoline<Super>

{

  sequenced_index_node_impl*& prior(){return impl_type::prior();}

  sequenced_index_node_impl*  prior()const{return impl_type::prior();}

  sequenced_index_node_impl*& next(){return impl_type::next();}

  sequenced_index_node_impl*  next()const{return impl_type::next();}

  sequenced_index_node_impl*       impl()

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

  const sequenced_index_node_impl* impl()const

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

  static sequenced_index_node* from_impl(sequenced_index_node_impl *x)

    {return static_cast<sequenced_index_node*>(static_cast<impl_type*>(x));}

  static const sequenced_index_node* from_impl(

    const sequenced_index_node_impl* x)

  {

    return static_cast<const sequenced_index_node*>(

      static_cast<const impl_type*>(x));

  }

  /* interoperability with bidir_node_iterator */

  static void increment(sequenced_index_node*& x)

  {

    sequenced_index_node_impl* xi=x->impl();

    impl_type::increment(xi);

    x=from_impl(xi);

  }

  static void decrement(sequenced_index_node*& x)

  {

    sequenced_index_node_impl* xi=x->impl();

    impl_type::decrement(xi);

    x=from_impl(xi);

  }

private:

  typedef sequenced_index_node_trampoline<Super> impl_type;

};

} /* namespace multi_index::detail */

} /* namespace multi_index */

} /* namespace boost */

#endif