third_party/boost/include/boost/multi_index/detail/ord_index_node.hpp - webm/webmlive - Git at Google

 /* 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.
  *
  * The internal implementation of red-black trees is based on that of SGI STL
  * stl_tree.h file:
  *
  * Copyright (c) 1996,1997
  * Silicon Graphics Computer Systems, Inc.
  *
  * Permission to use, copy, modify, distribute and sell this software
  * and its documentation for any purpose is hereby granted without fee,
  * provided that the above copyright notice appear in all copies and
  * that both that copyright notice and this permission notice appear
  * in supporting documentation.  Silicon Graphics makes no
  * representations about the suitability of this software for any
  * purpose.  It is provided "as is" without express or implied warranty.
  *
  *
  * Copyright (c) 1994
  * Hewlett-Packard Company
  *
  * Permission to use, copy, modify, distribute and sell this software
  * and its documentation for any purpose is hereby granted without fee,
  * provided that the above copyright notice appear in all copies and
  * that both that copyright notice and this permission notice appear
  * in supporting documentation.  Hewlett-Packard Company makes no
  * representations about the suitability of this software for any
  * purpose.  It is provided "as is" without express or implied warranty.
  *
  */

 #ifndef BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_NODE_HPP
 #define BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_NODE_HPP

 #if defined(_MSC_VER)&&(_MSC_VER>=1200)
 #pragma once
 #endif

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

 #if !defined(BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES)
 #include <boost/mpl/and.hpp>
 #include <boost/mpl/if.hpp>
 #include <boost/multi_index/detail/uintptr_type.hpp>
 #include <boost/type_traits/alignment_of.hpp>
 #include <boost/type_traits/is_same.hpp>
 #endif

 namespace boost{

 namespace multi_index{

 namespace detail{

 /* definition of red-black nodes for ordered_index */

 enum ordered_index_color{red=false,black=true};
 enum ordered_index_side{to_left=false,to_right=true};

 template<typename Allocator>
 struct ordered_index_node_impl; /* fwd decl. */

 template<typename Allocator>
 struct ordered_index_node_std_base
 {
   typedef typename prevent_eti<
     Allocator,
     typename boost::detail::allocator::rebind_to<
       Allocator,
       ordered_index_node_impl<Allocator>
     >::type
   >::type::pointer                                pointer;
   typedef typename prevent_eti<
     Allocator,
     typename boost::detail::allocator::rebind_to<
       Allocator,
       ordered_index_node_impl<Allocator>
     >::type
   >::type::const_pointer                          const_pointer;
   typedef ordered_index_color&                    color_ref;
   typedef pointer&                                parent_ref;

   ordered_index_color& color(){return color_;}
   ordered_index_color  color()const{return color_;}
   pointer&             parent(){return parent_;}
   pointer              parent()const{return parent_;}
   pointer&             left(){return left_;}
   pointer              left()const{return left_;}
   pointer&             right(){return right_;}
   pointer              right()const{return right_;}

 private:
   ordered_index_color color_;
   pointer             parent_;
   pointer             left_;
   pointer             right_;
 };

 #if !defined(BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES)
 /* If ordered_index_node_impl has even alignment, we can use the least
  * significant bit of one of the ordered_index_node_impl pointers to
  * store color information. This typically reduces the size of
  * ordered_index_node_impl by 25%.
  */

 #if defined(BOOST_MSVC)
 /* This code casts pointers to an integer type that has been computed
  * to be large enough to hold the pointer, however the metaprogramming
  * logic is not always spotted by the VC++ code analyser that issues a
  * long list of warnings.
  */

 #pragma warning(push)
 #pragma warning(disable:4312 4311)
 #endif

 template<typename Allocator>
 struct ordered_index_node_compressed_base
 {
   typedef ordered_index_node_impl<Allocator>*       pointer;
   typedef const ordered_index_node_impl<Allocator>* const_pointer;

   struct color_ref
   {
     color_ref(uintptr_type* r_):r(r_){}

     operator ordered_index_color()const
     {
       return ordered_index_color(*r&uintptr_type(1));
     }

     color_ref& operator=(ordered_index_color c)
     {
       *r&=~uintptr_type(1);
       *r|=uintptr_type(c);
       return *this;
     }

     color_ref& operator=(const color_ref& x)
     {
       return operator=(x.operator ordered_index_color());
     }

   private:
     uintptr_type* r;
   };

   struct parent_ref
   {
     parent_ref(uintptr_type* r_):r(r_){}

     operator pointer()const
     {
       return (pointer)(void*)(*r&~uintptr_type(1));
     }

     parent_ref& operator=(pointer p)
     {
       *r=((uintptr_type)(void*)p)|(*r&uintptr_type(1));
       return *this;
     }

     parent_ref& operator=(const parent_ref& x)
     {
       return operator=(x.operator pointer());
     }

     pointer operator->()const
     {
       return operator pointer();
     }

   private:
     uintptr_type* r;
   };

   color_ref           color(){return color_ref(&parentcolor_);}
   ordered_index_color color()const
   {
     return ordered_index_color(parentcolor_&std::size_t(1ul));
   }

   parent_ref parent(){return parent_ref(&parentcolor_);}
   pointer    parent()const
   {
     return (pointer)(void*)(parentcolor_&~uintptr_type(1));
   }

   pointer& left(){return left_;}
   pointer  left()const{return left_;}
   pointer& right(){return right_;}
   pointer  right()const{return right_;}

 private:
   uintptr_type parentcolor_;
   pointer      left_;
   pointer      right_;
 };
 #if defined(BOOST_MSVC)
 #pragma warning(pop)
 #endif
 #endif

 template<typename Allocator>
 struct ordered_index_node_impl_base:

 #if !defined(BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES)
   mpl::if_c<
     !(has_uintptr_type::value)||
     (alignment_of<ordered_index_node_compressed_base<Allocator> >::value%2)||
     !(is_same<
       typename prevent_eti<
         Allocator,
         typename boost::detail::allocator::rebind_to<
           Allocator,
           ordered_index_node_impl<Allocator>
         >::type
       >::type::pointer,
       ordered_index_node_impl<Allocator>*>::value),
     ordered_index_node_std_base<Allocator>,
     ordered_index_node_compressed_base<Allocator>
   >::type
 #else
   ordered_index_node_std_base<Allocator>
 #endif

 {};

 template<typename Allocator>
 struct ordered_index_node_impl:ordered_index_node_impl_base<Allocator>
 {
 private:
   typedef ordered_index_node_impl_base<Allocator> super;

 public:
   typedef typename super::color_ref               color_ref;
   typedef typename super::parent_ref              parent_ref;
   typedef typename super::pointer                 pointer;
   typedef typename super::const_pointer           const_pointer;

   /* interoperability with bidir_node_iterator */

   static void increment(pointer& x)
   {
     if(x->right()!=pointer(0)){
       x=x->right();
       while(x->left()!=pointer(0))x=x->left();
     }
     else{
       pointer y=x->parent();
       while(x==y->right()){
         x=y;
         y=y->parent();
       }
       if(x->right()!=y)x=y;
     }
   }

   static void decrement(pointer& x)
   {
     if(x->color()==red&&x->parent()->parent()==x){
       x=x->right();
     }
     else if(x->left()!=pointer(0)){
       pointer y=x->left();
       while(y->right()!=pointer(0))y=y->right();
       x=y;
     }else{
       pointer y=x->parent();
       while(x==y->left()){
         x=y;
         y=y->parent();
       }
       x=y;
     }
   }

   /* algorithmic stuff */

   static void rotate_left(pointer x,parent_ref root)
   {
     pointer y=x->right();
     x->right()=y->left();
     if(y->left()!=pointer(0))y->left()->parent()=x;
     y->parent()=x->parent();

     if(x==root)                    root=y;
     else if(x==x->parent()->left())x->parent()->left()=y;
     else                           x->parent()->right()=y;
     y->left()=x;
     x->parent()=y;
   }

   static pointer minimum(pointer x)
   {
     while(x->left()!=pointer(0))x=x->left();
     return x;
   }

   static pointer maximum(pointer x)
   {
     while(x->right()!=pointer(0))x=x->right();
     return x;
   }

   static void rotate_right(pointer x,parent_ref root)
   {
     pointer y=x->left();
     x->left()=y->right();
     if(y->right()!=pointer(0))y->right()->parent()=x;
     y->parent()=x->parent();

     if(x==root)                     root=y;
     else if(x==x->parent()->right())x->parent()->right()=y;
     else                            x->parent()->left()=y;
     y->right()=x;
     x->parent()=y;
   }

   static void rebalance(pointer x,parent_ref root)
   {
     x->color()=red;
     while(x!=root&&x->parent()->color()==red){
       if(x->parent()==x->parent()->parent()->left()){
         pointer y=x->parent()->parent()->right();
         if(y!=pointer(0)&&y->color()==red){
           x->parent()->color()=black;
           y->color()=black;
           x->parent()->parent()->color()=red;
           x=x->parent()->parent();
         }
         else{
           if(x==x->parent()->right()){
             x=x->parent();
             rotate_left(x,root);
           }
           x->parent()->color()=black;
           x->parent()->parent()->color()=red;
           rotate_right(x->parent()->parent(),root);
         }
       }
       else{
         pointer y=x->parent()->parent()->left();
         if(y!=pointer(0)&&y->color()==red){
           x->parent()->color()=black;
           y->color()=black;
           x->parent()->parent()->color()=red;
           x=x->parent()->parent();
         }
         else{
           if(x==x->parent()->left()){
             x=x->parent();
             rotate_right(x,root);
           }
           x->parent()->color()=black;
           x->parent()->parent()->color()=red;
           rotate_left(x->parent()->parent(),root);
         }
       }
     }
     root->color()=black;
   }

   static void link(
     pointer x,ordered_index_side side,pointer position,pointer header)
   {
     if(side==to_left){
       position->left()=x;  /* also makes leftmost=x when parent==header */
       if(position==header){
         header->parent()=x;
         header->right()=x;
       }
       else if(position==header->left()){
         header->left()=x;  /* maintain leftmost pointing to min node */
       }
     }
     else{
       position->right()=x;
       if(position==header->right()){
         header->right()=x; /* maintain rightmost pointing to max node */
       }
     }
     x->parent()=position;
     x->left()=pointer(0);
     x->right()=pointer(0);
     ordered_index_node_impl::rebalance(x,header->parent());
   }

   static pointer rebalance_for_erase(
     pointer z,parent_ref root,pointer& leftmost,pointer& rightmost)
   {
     pointer y=z;
     pointer x=pointer(0);
     pointer x_parent=pointer(0);
     if(y->left()==pointer(0)){    /* z has at most one non-null child. y==z. */
       x=y->right();               /* x might be null */
     }
     else{
       if(y->right()==pointer(0)){ /* z has exactly one non-null child. y==z. */
         x=y->left();              /* x is not null */
       }
       else{                       /* z has two non-null children.  Set y to */
         y=y->right();             /* z's successor. x might be null.        */
         while(y->left()!=pointer(0))y=y->left();
         x=y->right();
       }
     }
     if(y!=z){
       z->left()->parent()=y;   /* relink y in place of z. y is z's successor */
       y->left()=z->left();
       if(y!=z->right()){
         x_parent=y->parent();
         if(x!=pointer(0))x->parent()=y->parent();
         y->parent()->left()=x; /* y must be a child of left */
         y->right()=z->right();
         z->right()->parent()=y;
       }
       else{
         x_parent=y;
       }

       if(root==z)                    root=y;
       else if(z->parent()->left()==z)z->parent()->left()=y;
       else                           z->parent()->right()=y;
       y->parent()=z->parent();
       ordered_index_color c=y->color();
       y->color()=z->color();
       z->color()=c;
       y=z;                    /* y now points to node to be actually deleted */
     }
     else{                     /* y==z */
       x_parent=y->parent();
       if(x!=pointer(0))x->parent()=y->parent();
       if(root==z){
         root=x;
       }
       else{
         if(z->parent()->left()==z)z->parent()->left()=x;
         else                      z->parent()->right()=x;
       }
       if(leftmost==z){
         if(z->right()==pointer(0)){ /* z->left() must be null also */
           leftmost=z->parent();
         }
         else{
           leftmost=minimum(x);      /* makes leftmost==header if z==root */
         }
       }
       if(rightmost==z){
         if(z->left()==pointer(0)){  /* z->right() must be null also */
           rightmost=z->parent();
         }
         else{                   /* x==z->left() */
           rightmost=maximum(x); /* makes rightmost==header if z==root */
         }
       }
     }
     if(y->color()!=red){
       while(x!=root&&(x==pointer(0)|| x->color()==black)){
         if(x==x_parent->left()){
           pointer w=x_parent->right();
           if(w->color()==red){
             w->color()=black;
             x_parent->color()=red;
             rotate_left(x_parent,root);
             w=x_parent->right();
           }
           if((w->left()==pointer(0)||w->left()->color()==black) &&
              (w->right()==pointer(0)||w->right()->color()==black)){
             w->color()=red;
             x=x_parent;
             x_parent=x_parent->parent();
           }
           else{
             if(w->right()==pointer(0 )
                 || w->right()->color()==black){
               if(w->left()!=pointer(0)) w->left()->color()=black;
               w->color()=red;
               rotate_right(w,root);
               w=x_parent->right();
             }
             w->color()=x_parent->color();
             x_parent->color()=black;
             if(w->right()!=pointer(0))w->right()->color()=black;
             rotate_left(x_parent,root);
             break;
           }
         }
         else{                   /* same as above,with right <-> left */
           pointer w=x_parent->left();
           if(w->color()==red){
             w->color()=black;
             x_parent->color()=red;
             rotate_right(x_parent,root);
             w=x_parent->left();
           }
           if((w->right()==pointer(0)||w->right()->color()==black) &&
              (w->left()==pointer(0)||w->left()->color()==black)){
             w->color()=red;
             x=x_parent;
             x_parent=x_parent->parent();
           }
           else{
             if(w->left()==pointer(0)||w->left()->color()==black){
               if(w->right()!=pointer(0))w->right()->color()=black;
               w->color()=red;
               rotate_left(w,root);
               w=x_parent->left();
             }
             w->color()=x_parent->color();
             x_parent->color()=black;
             if(w->left()!=pointer(0))w->left()->color()=black;
             rotate_right(x_parent,root);
             break;
           }
         }
       }
       if(x!=pointer(0))x->color()=black;
     }
     return y;
   }

   static void restore(pointer x,pointer position,pointer header)
   {
     if(position->left()==pointer(0)||position->left()==header){
       link(x,to_left,position,header);
     }
     else{
       decrement(position);
       link(x,to_right,position,header);
     }
   }

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

   static std::size_t black_count(pointer node,pointer root)
   {
     if(node==pointer(0))return 0;
     std::size_t sum=0;
     for(;;){
       if(node->color()==black)++sum;
       if(node==root)break;
       node=node->parent();
     }
     return sum;
   }
 #endif
 };

 template<typename Super>
 struct ordered_index_node_trampoline:
   prevent_eti<
     Super,
     ordered_index_node_impl<
       typename boost::detail::allocator::rebind_to<
         typename Super::allocator_type,
         char
       >::type
     >
   >::type
 {
   typedef typename prevent_eti<
     Super,
     ordered_index_node_impl<
       typename boost::detail::allocator::rebind_to<
         typename Super::allocator_type,
         char
       >::type
     >
   >::type impl_type;
 };

 template<typename Super>
 struct ordered_index_node:Super,ordered_index_node_trampoline<Super>
 {
 private:
   typedef ordered_index_node_trampoline<Super> trampoline;

 public:
   typedef typename trampoline::impl_type     impl_type;
   typedef typename trampoline::color_ref     impl_color_ref;
   typedef typename trampoline::parent_ref    impl_parent_ref;
   typedef typename trampoline::pointer       impl_pointer;
   typedef typename trampoline::const_pointer const_impl_pointer;

   impl_color_ref      color(){return trampoline::color();}
   ordered_index_color color()const{return trampoline::color();}
   impl_parent_ref     parent(){return trampoline::parent();}
   impl_pointer        parent()const{return trampoline::parent();}
   impl_pointer&       left(){return trampoline::left();}
   impl_pointer        left()const{return trampoline::left();}
   impl_pointer&       right(){return trampoline::right();}
   impl_pointer        right()const{return trampoline::right();}

   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 ordered_index_node* from_impl(impl_pointer x)
   {
     return static_cast<ordered_index_node*>(
       static_cast<trampoline*>(&*x));
   }

   static const ordered_index_node* from_impl(const_impl_pointer x)
   {
     return static_cast<const ordered_index_node*>(
       static_cast<const trampoline*>(&*x));
   }

   /* interoperability with bidir_node_iterator */

   static void increment(ordered_index_node*& x)
   {
     impl_pointer xi=x->impl();
     trampoline::increment(xi);
     x=from_impl(xi);
   }

   static void decrement(ordered_index_node*& x)
   {
     impl_pointer xi=x->impl();
     trampoline::decrement(xi);
     x=from_impl(xi);
   }
 };

 } /* namespace multi_index::detail */

 } /* namespace multi_index */

 } /* namespace boost */

 #endif
	/* 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.
	*
	* The internal implementation of red-black trees is based on that of SGI STL
	* stl_tree.h file:
	*
	* Copyright (c) 1996,1997
	* Silicon Graphics Computer Systems, Inc.
	*
	* Permission to use, copy, modify, distribute and sell this software
	* and its documentation for any purpose is hereby granted without fee,
	* provided that the above copyright notice appear in all copies and
	* that both that copyright notice and this permission notice appear
	* in supporting documentation. Silicon Graphics makes no
	* representations about the suitability of this software for any
	* purpose. It is provided "as is" without express or implied warranty.
	*
	*
	* Copyright (c) 1994
	* Hewlett-Packard Company
	*
	* Permission to use, copy, modify, distribute and sell this software
	* and its documentation for any purpose is hereby granted without fee,
	* provided that the above copyright notice appear in all copies and
	* that both that copyright notice and this permission notice appear
	* in supporting documentation. Hewlett-Packard Company makes no
	* representations about the suitability of this software for any
	* purpose. It is provided "as is" without express or implied warranty.
	*
	*/

	#ifndef BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_NODE_HPP
	#define BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_NODE_HPP

	#if defined(_MSC_VER)&&(_MSC_VER>=1200)
	#pragma once
	#endif

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

	#if !defined(BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES)
	#include <boost/mpl/and.hpp>
	#include <boost/mpl/if.hpp>
	#include <boost/multi_index/detail/uintptr_type.hpp>
	#include <boost/type_traits/alignment_of.hpp>
	#include <boost/type_traits/is_same.hpp>
	#endif

	namespace boost{

	namespace multi_index{

	namespace detail{

	/* definition of red-black nodes for ordered_index */

	enum ordered_index_color{red=false,black=true};
	enum ordered_index_side{to_left=false,to_right=true};

	template<typename Allocator>
	struct ordered_index_node_impl; /* fwd decl. */

	template<typename Allocator>
	struct ordered_index_node_std_base
	{
	typedef typename prevent_eti<
	Allocator,
	typename boost::detail::allocator::rebind_to<
	Allocator,
	ordered_index_node_impl<Allocator>
	>::type
	>::type::pointer pointer;
	typedef typename prevent_eti<
	Allocator,
	typename boost::detail::allocator::rebind_to<
	Allocator,
	ordered_index_node_impl<Allocator>
	>::type
	>::type::const_pointer const_pointer;
	typedef ordered_index_color& color_ref;
	typedef pointer& parent_ref;

	ordered_index_color& color(){return color_;}
	ordered_index_color color()const{return color_;}
	pointer& parent(){return parent_;}
	pointer parent()const{return parent_;}
	pointer& left(){return left_;}
	pointer left()const{return left_;}
	pointer& right(){return right_;}
	pointer right()const{return right_;}

	private:
	ordered_index_color color_;
	pointer parent_;
	pointer left_;
	pointer right_;
	};

	#if !defined(BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES)
	/* If ordered_index_node_impl has even alignment, we can use the least
	* significant bit of one of the ordered_index_node_impl pointers to
	* store color information. This typically reduces the size of
	* ordered_index_node_impl by 25%.
	*/

	#if defined(BOOST_MSVC)
	/* This code casts pointers to an integer type that has been computed
	* to be large enough to hold the pointer, however the metaprogramming
	* logic is not always spotted by the VC++ code analyser that issues a
	* long list of warnings.
	*/

	#pragma warning(push)
	#pragma warning(disable:4312 4311)
	#endif

	template<typename Allocator>
	struct ordered_index_node_compressed_base
	{
	typedef ordered_index_node_impl<Allocator>* pointer;
	typedef const ordered_index_node_impl<Allocator>* const_pointer;

	struct color_ref
	{
	color_ref(uintptr_type* r_):r(r_){}

	operator ordered_index_color()const
	{
	return ordered_index_color(*r&uintptr_type(1));
	}

	color_ref& operator=(ordered_index_color c)
	{
	*r&=~uintptr_type(1);
	*r\|=uintptr_type(c);
	return *this;
	}

	color_ref& operator=(const color_ref& x)
	{
	return operator=(x.operator ordered_index_color());
	}

	private:
	uintptr_type* r;
	};

	struct parent_ref
	{
	parent_ref(uintptr_type* r_):r(r_){}

	operator pointer()const
	{
	return (pointer)(void)(r&~uintptr_type(1));
	}

	parent_ref& operator=(pointer p)
	{
	r=((uintptr_type)(void)p)\|(*r&uintptr_type(1));
	return *this;
	}

	parent_ref& operator=(const parent_ref& x)
	{
	return operator=(x.operator pointer());
	}

	pointer operator->()const
	{
	return operator pointer();
	}

	private:
	uintptr_type* r;
	};

	color_ref color(){return color_ref(&parentcolor_);}
	ordered_index_color color()const
	{
	return ordered_index_color(parentcolor_&std::size_t(1ul));
	}

	parent_ref parent(){return parent_ref(&parentcolor_);}
	pointer parent()const
	{
	return (pointer)(void*)(parentcolor_&~uintptr_type(1));
	}

	pointer& left(){return left_;}
	pointer left()const{return left_;}
	pointer& right(){return right_;}
	pointer right()const{return right_;}

	private:
	uintptr_type parentcolor_;
	pointer left_;
	pointer right_;
	};
	#if defined(BOOST_MSVC)
	#pragma warning(pop)
	#endif
	#endif

	template<typename Allocator>
	struct ordered_index_node_impl_base:

	#if !defined(BOOST_MULTI_INDEX_DISABLE_COMPRESSED_ORDERED_INDEX_NODES)
	mpl::if_c<
	!(has_uintptr_type::value)\|\|
	(alignment_of<ordered_index_node_compressed_base<Allocator> >::value%2)\|\|
	!(is_same<
	typename prevent_eti<
	Allocator,
	typename boost::detail::allocator::rebind_to<
	Allocator,
	ordered_index_node_impl<Allocator>
	>::type
	>::type::pointer,
	ordered_index_node_impl<Allocator>*>::value),
	ordered_index_node_std_base<Allocator>,
	ordered_index_node_compressed_base<Allocator>
	>::type
	#else
	ordered_index_node_std_base<Allocator>
	#endif

	{};

	template<typename Allocator>
	struct ordered_index_node_impl:ordered_index_node_impl_base<Allocator>
	{
	private:
	typedef ordered_index_node_impl_base<Allocator> super;

	public:
	typedef typename super::color_ref color_ref;
	typedef typename super::parent_ref parent_ref;
	typedef typename super::pointer pointer;
	typedef typename super::const_pointer const_pointer;

	/* interoperability with bidir_node_iterator */

	static void increment(pointer& x)
	{
	if(x->right()!=pointer(0)){
	x=x->right();
	while(x->left()!=pointer(0))x=x->left();
	}
	else{
	pointer y=x->parent();
	while(x==y->right()){
	x=y;
	y=y->parent();
	}
	if(x->right()!=y)x=y;
	}
	}

	static void decrement(pointer& x)
	{
	if(x->color()==red&&x->parent()->parent()==x){
	x=x->right();
	}
	else if(x->left()!=pointer(0)){
	pointer y=x->left();
	while(y->right()!=pointer(0))y=y->right();
	x=y;
	}else{
	pointer y=x->parent();
	while(x==y->left()){
	x=y;
	y=y->parent();
	}
	x=y;
	}
	}

	/* algorithmic stuff */

	static void rotate_left(pointer x,parent_ref root)
	{
	pointer y=x->right();
	x->right()=y->left();
	if(y->left()!=pointer(0))y->left()->parent()=x;
	y->parent()=x->parent();

	if(x==root) root=y;
	else if(x==x->parent()->left())x->parent()->left()=y;
	else x->parent()->right()=y;
	y->left()=x;
	x->parent()=y;
	}

	static pointer minimum(pointer x)
	{
	while(x->left()!=pointer(0))x=x->left();
	return x;
	}

	static pointer maximum(pointer x)
	{
	while(x->right()!=pointer(0))x=x->right();
	return x;
	}

	static void rotate_right(pointer x,parent_ref root)
	{
	pointer y=x->left();
	x->left()=y->right();
	if(y->right()!=pointer(0))y->right()->parent()=x;
	y->parent()=x->parent();

	if(x==root) root=y;
	else if(x==x->parent()->right())x->parent()->right()=y;
	else x->parent()->left()=y;
	y->right()=x;
	x->parent()=y;
	}

	static void rebalance(pointer x,parent_ref root)
	{
	x->color()=red;
	while(x!=root&&x->parent()->color()==red){
	if(x->parent()==x->parent()->parent()->left()){
	pointer y=x->parent()->parent()->right();
	if(y!=pointer(0)&&y->color()==red){
	x->parent()->color()=black;
	y->color()=black;
	x->parent()->parent()->color()=red;
	x=x->parent()->parent();
	}
	else{
	if(x==x->parent()->right()){
	x=x->parent();
	rotate_left(x,root);
	}
	x->parent()->color()=black;
	x->parent()->parent()->color()=red;
	rotate_right(x->parent()->parent(),root);
	}
	}
	else{
	pointer y=x->parent()->parent()->left();
	if(y!=pointer(0)&&y->color()==red){
	x->parent()->color()=black;
	y->color()=black;
	x->parent()->parent()->color()=red;
	x=x->parent()->parent();
	}
	else{
	if(x==x->parent()->left()){
	x=x->parent();
	rotate_right(x,root);
	}
	x->parent()->color()=black;
	x->parent()->parent()->color()=red;
	rotate_left(x->parent()->parent(),root);
	}
	}
	}
	root->color()=black;
	}

	static void link(
	pointer x,ordered_index_side side,pointer position,pointer header)
	{
	if(side==to_left){
	position->left()=x; /* also makes leftmost=x when parent==header */
	if(position==header){
	header->parent()=x;
	header->right()=x;
	}
	else if(position==header->left()){
	header->left()=x; /* maintain leftmost pointing to min node */
	}
	}
	else{
	position->right()=x;
	if(position==header->right()){
	header->right()=x; /* maintain rightmost pointing to max node */
	}
	}
	x->parent()=position;
	x->left()=pointer(0);
	x->right()=pointer(0);
	ordered_index_node_impl::rebalance(x,header->parent());
	}

	static pointer rebalance_for_erase(
	pointer z,parent_ref root,pointer& leftmost,pointer& rightmost)
	{
	pointer y=z;
	pointer x=pointer(0);
	pointer x_parent=pointer(0);
	if(y->left()==pointer(0)){ /* z has at most one non-null child. y==z. */
	x=y->right(); /* x might be null */
	}
	else{
	if(y->right()==pointer(0)){ /* z has exactly one non-null child. y==z. */
	x=y->left(); /* x is not null */
	}
	else{ /* z has two non-null children. Set y to */
	y=y->right(); /* z's successor. x might be null. */
	while(y->left()!=pointer(0))y=y->left();
	x=y->right();
	}
	}
	if(y!=z){
	z->left()->parent()=y; /* relink y in place of z. y is z's successor */
	y->left()=z->left();
	if(y!=z->right()){
	x_parent=y->parent();
	if(x!=pointer(0))x->parent()=y->parent();
	y->parent()->left()=x; /* y must be a child of left */
	y->right()=z->right();
	z->right()->parent()=y;
	}
	else{
	x_parent=y;
	}

	if(root==z) root=y;
	else if(z->parent()->left()==z)z->parent()->left()=y;
	else z->parent()->right()=y;
	y->parent()=z->parent();
	ordered_index_color c=y->color();
	y->color()=z->color();
	z->color()=c;
	y=z; /* y now points to node to be actually deleted */
	}
	else{ /* y==z */
	x_parent=y->parent();
	if(x!=pointer(0))x->parent()=y->parent();
	if(root==z){
	root=x;
	}
	else{
	if(z->parent()->left()==z)z->parent()->left()=x;
	else z->parent()->right()=x;
	}
	if(leftmost==z){
	if(z->right()==pointer(0)){ /* z->left() must be null also */
	leftmost=z->parent();
	}
	else{
	leftmost=minimum(x); /* makes leftmost==header if z==root */
	}
	}
	if(rightmost==z){
	if(z->left()==pointer(0)){ /* z->right() must be null also */
	rightmost=z->parent();
	}
	else{ /* x==z->left() */
	rightmost=maximum(x); /* makes rightmost==header if z==root */
	}
	}
	}
	if(y->color()!=red){
	while(x!=root&&(x==pointer(0)\|\| x->color()==black)){
	if(x==x_parent->left()){
	pointer w=x_parent->right();
	if(w->color()==red){
	w->color()=black;
	x_parent->color()=red;
	rotate_left(x_parent,root);
	w=x_parent->right();
	}
	if((w->left()==pointer(0)\|\|w->left()->color()==black) &&
	(w->right()==pointer(0)\|\|w->right()->color()==black)){
	w->color()=red;
	x=x_parent;
	x_parent=x_parent->parent();
	}
	else{
	if(w->right()==pointer(0 )
	\|\| w->right()->color()==black){
	if(w->left()!=pointer(0)) w->left()->color()=black;
	w->color()=red;
	rotate_right(w,root);
	w=x_parent->right();
	}
	w->color()=x_parent->color();
	x_parent->color()=black;
	if(w->right()!=pointer(0))w->right()->color()=black;
	rotate_left(x_parent,root);
	break;
	}
	}
	else{ /* same as above,with right <-> left */
	pointer w=x_parent->left();
	if(w->color()==red){
	w->color()=black;
	x_parent->color()=red;
	rotate_right(x_parent,root);
	w=x_parent->left();
	}
	if((w->right()==pointer(0)\|\|w->right()->color()==black) &&
	(w->left()==pointer(0)\|\|w->left()->color()==black)){
	w->color()=red;
	x=x_parent;
	x_parent=x_parent->parent();
	}
	else{
	if(w->left()==pointer(0)\|\|w->left()->color()==black){
	if(w->right()!=pointer(0))w->right()->color()=black;
	w->color()=red;
	rotate_left(w,root);
	w=x_parent->left();
	}
	w->color()=x_parent->color();
	x_parent->color()=black;
	if(w->left()!=pointer(0))w->left()->color()=black;
	rotate_right(x_parent,root);
	break;
	}
	}
	}
	if(x!=pointer(0))x->color()=black;
	}
	return y;
	}

	static void restore(pointer x,pointer position,pointer header)
	{
	if(position->left()==pointer(0)\|\|position->left()==header){
	link(x,to_left,position,header);
	}
	else{
	decrement(position);
	link(x,to_right,position,header);
	}
	}

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

	static std::size_t black_count(pointer node,pointer root)
	{
	if(node==pointer(0))return 0;
	std::size_t sum=0;
	for(;;){
	if(node->color()==black)++sum;
	if(node==root)break;
	node=node->parent();
	}
	return sum;
	}
	#endif
	};

	template<typename Super>
	struct ordered_index_node_trampoline:
	prevent_eti<
	Super,
	ordered_index_node_impl<
	typename boost::detail::allocator::rebind_to<
	typename Super::allocator_type,
	char
	>::type
	>
	>::type
	{
	typedef typename prevent_eti<
	Super,
	ordered_index_node_impl<
	typename boost::detail::allocator::rebind_to<
	typename Super::allocator_type,
	char
	>::type
	>
	>::type impl_type;
	};

	template<typename Super>
	struct ordered_index_node:Super,ordered_index_node_trampoline<Super>
	{
	private:
	typedef ordered_index_node_trampoline<Super> trampoline;

	public:
	typedef typename trampoline::impl_type impl_type;
	typedef typename trampoline::color_ref impl_color_ref;
	typedef typename trampoline::parent_ref impl_parent_ref;
	typedef typename trampoline::pointer impl_pointer;
	typedef typename trampoline::const_pointer const_impl_pointer;

	impl_color_ref color(){return trampoline::color();}
	ordered_index_color color()const{return trampoline::color();}
	impl_parent_ref parent(){return trampoline::parent();}
	impl_pointer parent()const{return trampoline::parent();}
	impl_pointer& left(){return trampoline::left();}
	impl_pointer left()const{return trampoline::left();}
	impl_pointer& right(){return trampoline::right();}
	impl_pointer right()const{return trampoline::right();}

	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 ordered_index_node* from_impl(impl_pointer x)
	{
	return static_cast<ordered_index_node*>(
	static_cast<trampoline>(&x));
	}

	static const ordered_index_node* from_impl(const_impl_pointer x)
	{
	return static_cast<const ordered_index_node*>(
	static_cast<const trampoline>(&x));
	}

	/* interoperability with bidir_node_iterator */

	static void increment(ordered_index_node*& x)
	{
	impl_pointer xi=x->impl();
	trampoline::increment(xi);
	x=from_impl(xi);
	}

	static void decrement(ordered_index_node*& x)
	{
	impl_pointer xi=x->impl();
	trampoline::decrement(xi);
	x=from_impl(xi);
	}
	};

	} /* namespace multi_index::detail */

	} /* namespace multi_index */

	} /* namespace boost */

	#endif