1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/multi_index/ordered_index.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,1239 @@
1.4 +/* Copyright 2003-2007 Joaquín M López Muñoz.
1.5 + * Distributed under the Boost Software License, Version 1.0.
1.6 + * (See accompanying file LICENSE_1_0.txt or copy at
1.7 + * http://www.boost.org/LICENSE_1_0.txt)
1.8 + *
1.9 + * See http://www.boost.org/libs/multi_index for library home page.
1.10 + *
1.11 + * The internal implementation of red-black trees is based on that of SGI STL
1.12 + * stl_tree.h file:
1.13 + *
1.14 + * Copyright (c) 1996,1997
1.15 + * Silicon Graphics Computer Systems, Inc.
1.16 + *
1.17 + * Permission to use, copy, modify, distribute and sell this software
1.18 + * and its documentation for any purpose is hereby granted without fee,
1.19 + * provided that the above copyright notice appear in all copies and
1.20 + * that both that copyright notice and this permission notice appear
1.21 + * in supporting documentation. Silicon Graphics makes no
1.22 + * representations about the suitability of this software for any
1.23 + * purpose. It is provided "as is" without express or implied warranty.
1.24 + *
1.25 + *
1.26 + * Copyright (c) 1994
1.27 + * Hewlett-Packard Company
1.28 + *
1.29 + * Permission to use, copy, modify, distribute and sell this software
1.30 + * and its documentation for any purpose is hereby granted without fee,
1.31 + * provided that the above copyright notice appear in all copies and
1.32 + * that both that copyright notice and this permission notice appear
1.33 + * in supporting documentation. Hewlett-Packard Company makes no
1.34 + * representations about the suitability of this software for any
1.35 + * purpose. It is provided "as is" without express or implied warranty.
1.36 + *
1.37 + */
1.38 +
1.39 +#ifndef BOOST_MULTI_INDEX_ORDERED_INDEX_HPP
1.40 +#define BOOST_MULTI_INDEX_ORDERED_INDEX_HPP
1.41 +
1.42 +#if defined(_MSC_VER)&&(_MSC_VER>=1200)
1.43 +#pragma once
1.44 +#endif
1.45 +
1.46 +#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
1.47 +#include <algorithm>
1.48 +#include <boost/call_traits.hpp>
1.49 +#include <boost/detail/no_exceptions_support.hpp>
1.50 +#include <boost/detail/workaround.hpp>
1.51 +#include <boost/iterator/reverse_iterator.hpp>
1.52 +#include <boost/mpl/push_front.hpp>
1.53 +#include <boost/multi_index/detail/access_specifier.hpp>
1.54 +#include <boost/multi_index/detail/bidir_node_iterator.hpp>
1.55 +#include <boost/multi_index/detail/modify_key_adaptor.hpp>
1.56 +#include <boost/multi_index/detail/ord_index_node.hpp>
1.57 +#include <boost/multi_index/detail/ord_index_ops.hpp>
1.58 +#include <boost/multi_index/detail/safe_ctr_proxy.hpp>
1.59 +#include <boost/multi_index/detail/safe_mode.hpp>
1.60 +#include <boost/multi_index/detail/scope_guard.hpp>
1.61 +#include <boost/multi_index/detail/unbounded.hpp>
1.62 +#include <boost/multi_index/detail/value_compare.hpp>
1.63 +#include <boost/multi_index/ordered_index_fwd.hpp>
1.64 +#include <boost/ref.hpp>
1.65 +#include <boost/tuple/tuple.hpp>
1.66 +#include <utility>
1.67 +
1.68 +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
1.69 +#include <boost/archive/archive_exception.hpp>
1.70 +#include <boost/bind.hpp>
1.71 +#include <boost/multi_index/detail/duplicates_iterator.hpp>
1.72 +#include <boost/throw_exception.hpp>
1.73 +#endif
1.74 +
1.75 +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
1.76 +#define BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT \
1.77 + detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)= \
1.78 + detail::make_obj_guard(*this,&ordered_index::check_invariant_); \
1.79 + BOOST_JOIN(check_invariant_,__LINE__).touch();
1.80 +#else
1.81 +#define BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT
1.82 +#endif
1.83 +
1.84 +namespace boost{
1.85 +
1.86 +namespace multi_index{
1.87 +
1.88 +namespace detail{
1.89 +
1.90 +/* ordered_index adds a layer of ordered indexing to a given Super */
1.91 +
1.92 +/* Most of the implementation of unique and non-unique indices is
1.93 + * shared. We tell from one another on instantiation time by using
1.94 + * these tags.
1.95 + */
1.96 +
1.97 +struct ordered_unique_tag{};
1.98 +struct ordered_non_unique_tag{};
1.99 +
1.100 +template<
1.101 + typename KeyFromValue,typename Compare,
1.102 + typename SuperMeta,typename TagList,typename Category
1.103 +>
1.104 +class ordered_index:
1.105 + BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type
1.106 +
1.107 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.108 +#if BOOST_WORKAROUND(BOOST_MSVC,<1300)
1.109 + ,public safe_ctr_proxy_impl<
1.110 + bidir_node_iterator<
1.111 + ordered_index_node<typename SuperMeta::type::node_type> >,
1.112 + ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category> >
1.113 +#else
1.114 + ,public safe_mode::safe_container<
1.115 + ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category> >
1.116 +#endif
1.117 +#endif
1.118 +
1.119 +{
1.120 +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
1.121 + BOOST_WORKAROUND(__MWERKS__,<=0x3003)
1.122 +/* The "ISO C++ Template Parser" option in CW8.3 has a problem with the
1.123 + * lifetime of const references bound to temporaries --precisely what
1.124 + * scopeguards are.
1.125 + */
1.126 +
1.127 +#pragma parse_mfunc_templ off
1.128 +#endif
1.129 +
1.130 + typedef typename SuperMeta::type super;
1.131 +
1.132 +protected:
1.133 + typedef ordered_index_node<
1.134 + typename super::node_type> node_type;
1.135 +
1.136 +public:
1.137 + /* types */
1.138 +
1.139 + typedef typename KeyFromValue::result_type key_type;
1.140 + typedef typename node_type::value_type value_type;
1.141 + typedef KeyFromValue key_from_value;
1.142 + typedef Compare key_compare;
1.143 + typedef value_comparison<
1.144 + value_type,KeyFromValue,Compare> value_compare;
1.145 + typedef tuple<key_from_value,key_compare> ctor_args;
1.146 + typedef typename super::final_allocator_type allocator_type;
1.147 + typedef typename allocator_type::reference reference;
1.148 + typedef typename allocator_type::const_reference const_reference;
1.149 +
1.150 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.151 +#if BOOST_WORKAROUND(BOOST_MSVC,<1300)
1.152 + typedef safe_mode::safe_iterator<
1.153 + bidir_node_iterator<node_type>,
1.154 + safe_ctr_proxy<
1.155 + bidir_node_iterator<node_type> > > iterator;
1.156 +#else
1.157 + typedef safe_mode::safe_iterator<
1.158 + bidir_node_iterator<node_type>,
1.159 + ordered_index> iterator;
1.160 +#endif
1.161 +#else
1.162 + typedef bidir_node_iterator<node_type> iterator;
1.163 +#endif
1.164 +
1.165 + typedef iterator const_iterator;
1.166 +
1.167 + typedef std::size_t size_type;
1.168 + typedef std::ptrdiff_t difference_type;
1.169 + typedef typename allocator_type::pointer pointer;
1.170 + typedef typename allocator_type::const_pointer const_pointer;
1.171 + typedef typename
1.172 + boost::reverse_iterator<iterator> reverse_iterator;
1.173 + typedef typename
1.174 + boost::reverse_iterator<const_iterator> const_reverse_iterator;
1.175 + typedef TagList tag_list;
1.176 +
1.177 +protected:
1.178 + typedef typename super::final_node_type final_node_type;
1.179 + typedef tuples::cons<
1.180 + ctor_args,
1.181 + typename super::ctor_args_list> ctor_args_list;
1.182 + typedef typename mpl::push_front<
1.183 + typename super::index_type_list,
1.184 + ordered_index>::type index_type_list;
1.185 + typedef typename mpl::push_front<
1.186 + typename super::iterator_type_list,
1.187 + iterator>::type iterator_type_list;
1.188 + typedef typename mpl::push_front<
1.189 + typename super::const_iterator_type_list,
1.190 + const_iterator>::type const_iterator_type_list;
1.191 + typedef typename super::copy_map_type copy_map_type;
1.192 +
1.193 +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
1.194 + typedef typename super::index_saver_type index_saver_type;
1.195 + typedef typename super::index_loader_type index_loader_type;
1.196 +#endif
1.197 +
1.198 +private:
1.199 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.200 +#if BOOST_WORKAROUND(BOOST_MSVC,<1300)
1.201 + typedef safe_ctr_proxy_impl<
1.202 + bidir_node_iterator<node_type>,
1.203 + ordered_index> safe_super;
1.204 +#else
1.205 + typedef safe_mode::safe_container<ordered_index> safe_super;
1.206 +#endif
1.207 +#endif
1.208 +
1.209 + typedef typename call_traits<
1.210 + value_type>::param_type value_param_type;
1.211 + typedef typename call_traits<
1.212 + key_type>::param_type key_param_type;
1.213 +
1.214 +public:
1.215 +
1.216 + /* construct/copy/destroy
1.217 + * Default and copy ctors are in the protected section as indices are
1.218 + * not supposed to be created on their own. No range ctor either.
1.219 + */
1.220 +
1.221 + ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& operator=(
1.222 + const ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& x)
1.223 + {
1.224 + this->final()=x.final();
1.225 + return *this;
1.226 + }
1.227 +
1.228 + allocator_type get_allocator()const
1.229 + {
1.230 + return this->final().get_allocator();
1.231 + }
1.232 +
1.233 + /* iterators */
1.234 +
1.235 + iterator begin(){return make_iterator(leftmost());}
1.236 + const_iterator begin()const{return make_iterator(leftmost());}
1.237 + iterator end(){return make_iterator(header());}
1.238 + const_iterator end()const{return make_iterator(header());}
1.239 + reverse_iterator rbegin(){return make_reverse_iterator(end());}
1.240 + const_reverse_iterator rbegin()const{return make_reverse_iterator(end());}
1.241 + reverse_iterator rend(){return make_reverse_iterator(begin());}
1.242 + const_reverse_iterator rend()const{return make_reverse_iterator(begin());}
1.243 +
1.244 + /* capacity */
1.245 +
1.246 + bool empty()const{return this->final_empty_();}
1.247 + size_type size()const{return this->final_size_();}
1.248 + size_type max_size()const{return this->final_max_size_();}
1.249 +
1.250 + /* modifiers */
1.251 +
1.252 + std::pair<iterator,bool> insert(value_param_type x)
1.253 + {
1.254 + BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
1.255 + std::pair<final_node_type*,bool> p=this->final_insert_(x);
1.256 + return std::pair<iterator,bool>(make_iterator(p.first),p.second);
1.257 + }
1.258 +
1.259 + iterator insert(iterator position,value_param_type x)
1.260 + {
1.261 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1.262 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1.263 + BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
1.264 + std::pair<final_node_type*,bool> p=this->final_insert_(
1.265 + x,static_cast<final_node_type*>(position.get_node()));
1.266 + return make_iterator(p.first);
1.267 + }
1.268 +
1.269 + template<typename InputIterator>
1.270 + void insert(InputIterator first,InputIterator last)
1.271 + {
1.272 + BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
1.273 + iterator hint=end();
1.274 + for(;first!=last;++first)hint=insert(hint,*first);
1.275 + }
1.276 +
1.277 + iterator erase(iterator position)
1.278 + {
1.279 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1.280 + BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
1.281 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1.282 + BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
1.283 + this->final_erase_(static_cast<final_node_type*>(position++.get_node()));
1.284 + return position;
1.285 + }
1.286 +
1.287 + size_type erase(key_param_type x)
1.288 + {
1.289 + BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
1.290 + std::pair<iterator,iterator> p=equal_range(x);
1.291 + size_type s=0;
1.292 + while(p.first!=p.second){
1.293 + p.first=erase(p.first);
1.294 + ++s;
1.295 + }
1.296 + return s;
1.297 + }
1.298 +
1.299 + iterator erase(iterator first,iterator last)
1.300 + {
1.301 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
1.302 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
1.303 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
1.304 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
1.305 + BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
1.306 + BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
1.307 + while(first!=last){
1.308 + first=erase(first);
1.309 + }
1.310 + return first;
1.311 + }
1.312 +
1.313 + bool replace(iterator position,value_param_type x)
1.314 + {
1.315 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1.316 + BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
1.317 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1.318 + BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
1.319 + return this->final_replace_(
1.320 + x,static_cast<final_node_type*>(position.get_node()));
1.321 + }
1.322 +
1.323 + template<typename Modifier>
1.324 + bool modify(iterator position,Modifier mod)
1.325 + {
1.326 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1.327 + BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
1.328 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1.329 + BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
1.330 +
1.331 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.332 + /* MSVC++ 6.0 optimizer on safe mode code chokes if this
1.333 + * this is not added. Left it for all compilers as it does no
1.334 + * harm.
1.335 + */
1.336 +
1.337 + position.detach();
1.338 +#endif
1.339 +
1.340 + return this->final_modify_(
1.341 + mod,static_cast<final_node_type*>(position.get_node()));
1.342 + }
1.343 +
1.344 + template<typename Modifier>
1.345 + bool modify_key(iterator position,Modifier mod)
1.346 + {
1.347 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1.348 + BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
1.349 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1.350 + BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
1.351 + return modify(
1.352 + position,modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key));
1.353 + }
1.354 +
1.355 + void swap(ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& x)
1.356 + {
1.357 + BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
1.358 + this->final_swap_(x.final());
1.359 + }
1.360 +
1.361 + void clear()
1.362 + {
1.363 + BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT;
1.364 + this->final_clear_();
1.365 + }
1.366 +
1.367 + /* observers */
1.368 +
1.369 + key_from_value key_extractor()const{return key;}
1.370 + key_compare key_comp()const{return comp;}
1.371 + value_compare value_comp()const{return value_compare(key,comp);}
1.372 +
1.373 + /* set operations */
1.374 +
1.375 + /* Internally, these ops rely on const_iterator being the same
1.376 + * type as iterator.
1.377 + */
1.378 +
1.379 + template<typename CompatibleKey>
1.380 + iterator find(const CompatibleKey& x)const
1.381 + {
1.382 + return make_iterator(ordered_index_find(header(),key,x,comp));
1.383 + }
1.384 +
1.385 + template<typename CompatibleKey,typename CompatibleCompare>
1.386 + iterator find(
1.387 + const CompatibleKey& x,const CompatibleCompare& comp)const
1.388 + {
1.389 + return make_iterator(ordered_index_find(header(),key,x,comp));
1.390 + }
1.391 +
1.392 + template<typename CompatibleKey>
1.393 + size_type count(const CompatibleKey& x)const
1.394 + {
1.395 + return count(x,comp);
1.396 + }
1.397 +
1.398 + template<typename CompatibleKey,typename CompatibleCompare>
1.399 + size_type count(const CompatibleKey& x,const CompatibleCompare& comp)const
1.400 + {
1.401 + std::pair<iterator,iterator> p=equal_range(x,comp);
1.402 + size_type n=std::distance(p.first,p.second);
1.403 + return n;
1.404 + }
1.405 +
1.406 + template<typename CompatibleKey>
1.407 + iterator lower_bound(const CompatibleKey& x)const
1.408 + {
1.409 + return make_iterator(ordered_index_lower_bound(header(),key,x,comp));
1.410 + }
1.411 +
1.412 + template<typename CompatibleKey,typename CompatibleCompare>
1.413 + iterator lower_bound(
1.414 + const CompatibleKey& x,const CompatibleCompare& comp)const
1.415 + {
1.416 + return make_iterator(ordered_index_lower_bound(header(),key,x,comp));
1.417 + }
1.418 +
1.419 + template<typename CompatibleKey>
1.420 + iterator upper_bound(const CompatibleKey& x)const
1.421 + {
1.422 + return make_iterator(ordered_index_upper_bound(header(),key,x,comp));
1.423 + }
1.424 +
1.425 + template<typename CompatibleKey,typename CompatibleCompare>
1.426 + iterator upper_bound(
1.427 + const CompatibleKey& x,const CompatibleCompare& comp)const
1.428 + {
1.429 + return make_iterator(ordered_index_upper_bound(header(),key,x,comp));
1.430 + }
1.431 +
1.432 + template<typename CompatibleKey>
1.433 + std::pair<iterator,iterator> equal_range(
1.434 + const CompatibleKey& x)const
1.435 + {
1.436 + return equal_range(x,comp);
1.437 + }
1.438 +
1.439 + template<typename CompatibleKey,typename CompatibleCompare>
1.440 + std::pair<iterator,iterator> equal_range(
1.441 + const CompatibleKey& x,const CompatibleCompare& comp)const
1.442 + {
1.443 + return std::pair<iterator,iterator>(
1.444 + lower_bound(x,comp),upper_bound(x,comp));
1.445 + }
1.446 +
1.447 + /* range */
1.448 +
1.449 + template<typename LowerBounder,typename UpperBounder>
1.450 + std::pair<iterator,iterator>
1.451 + range(LowerBounder lower,UpperBounder upper)const
1.452 + {
1.453 + std::pair<iterator,iterator> p(
1.454 + lower_range(lower),upper_range(upper));
1.455 + if(p.second!=end()&&(p.first==end()||comp(key(*p.second),key(*p.first)))){
1.456 + p.second=p.first;
1.457 + }
1.458 + return p;
1.459 + }
1.460 +
1.461 +BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
1.462 + ordered_index(const ctor_args_list& args_list,const allocator_type& al):
1.463 + super(args_list.get_tail(),al),
1.464 + key(tuples::get<0>(args_list.get_head())),
1.465 + comp(tuples::get<1>(args_list.get_head()))
1.466 + {
1.467 + empty_initialize();
1.468 + }
1.469 +
1.470 + ordered_index(
1.471 + const ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& x):
1.472 + super(x),
1.473 +
1.474 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.475 + safe_super(),
1.476 +#endif
1.477 +
1.478 + key(x.key),
1.479 + comp(x.comp)
1.480 + {
1.481 + /* Copy ctor just takes the key and compare objects from x. The rest is
1.482 + * done in subsequent call to copy_().
1.483 + */
1.484 + }
1.485 +
1.486 + ~ordered_index()
1.487 + {
1.488 + /* the container is guaranteed to be empty by now */
1.489 + }
1.490 +
1.491 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.492 + iterator make_iterator(node_type* node){return iterator(node,this);}
1.493 + const_iterator make_iterator(node_type* node)const
1.494 + {return const_iterator(node,const_cast<ordered_index*>(this));}
1.495 +#else
1.496 + iterator make_iterator(node_type* node){return iterator(node);}
1.497 + const_iterator make_iterator(node_type* node)const
1.498 + {return const_iterator(node);}
1.499 +#endif
1.500 +
1.501 + void copy_(
1.502 + const ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& x,
1.503 + const copy_map_type& map)
1.504 + {
1.505 + if(!x.root()){
1.506 + empty_initialize();
1.507 + }
1.508 + else{
1.509 + header()->color()=x.header()->color();
1.510 +
1.511 + node_type* root_cpy=map.find(static_cast<final_node_type*>(x.root()));
1.512 + header()->parent()=root_cpy->impl();
1.513 +
1.514 + node_type* leftmost_cpy=map.find(
1.515 + static_cast<final_node_type*>(x.leftmost()));
1.516 + header()->left()=leftmost_cpy->impl();
1.517 +
1.518 + node_type* rightmost_cpy=map.find(
1.519 + static_cast<final_node_type*>(x.rightmost()));
1.520 + header()->right()=rightmost_cpy->impl();
1.521 +
1.522 + typedef typename copy_map_type::const_iterator copy_map_iterator;
1.523 + for(copy_map_iterator it=map.begin(),it_end=map.end();it!=it_end;++it){
1.524 + node_type* org=it->first;
1.525 + node_type* cpy=it->second;
1.526 +
1.527 + cpy->color()=org->color();
1.528 +
1.529 + ordered_index_node_impl* parent_org=org->parent();
1.530 + if(!parent_org)cpy->parent()=0;
1.531 + else{
1.532 + node_type* parent_cpy=map.find(
1.533 + static_cast<final_node_type*>(node_type::from_impl(parent_org)));
1.534 + cpy->parent()=parent_cpy->impl();
1.535 + if(parent_org->left()==org->impl()){
1.536 + parent_cpy->left()=cpy->impl();
1.537 + }
1.538 + else if(parent_org->right()==org->impl()){
1.539 + /* header() does not satisfy this nor the previous check */
1.540 + parent_cpy->right()=cpy->impl();
1.541 + }
1.542 + }
1.543 +
1.544 + if(!org->left())cpy->left()=0;
1.545 + if(!org->right())cpy->right()=0;
1.546 + }
1.547 + }
1.548 +
1.549 + super::copy_(x,map);
1.550 + }
1.551 +
1.552 + node_type* insert_(value_param_type v,node_type* x)
1.553 + {
1.554 + link_info inf;
1.555 + if(!link_point(key(v),inf,Category())){
1.556 + return node_type::from_impl(inf.pos);
1.557 + }
1.558 +
1.559 + node_type* res=static_cast<node_type*>(super::insert_(v,x));
1.560 + if(res==x){
1.561 + ordered_index_node_impl::link(
1.562 + x->impl(),inf.side,inf.pos,header()->impl());
1.563 + }
1.564 + return res;
1.565 + }
1.566 +
1.567 + node_type* insert_(value_param_type v,node_type* position,node_type* x)
1.568 + {
1.569 + link_info inf;
1.570 + if(!hinted_link_point(key(v),position,inf,Category())){
1.571 + return node_type::from_impl(inf.pos);
1.572 + }
1.573 +
1.574 + node_type* res=static_cast<node_type*>(super::insert_(v,position,x));
1.575 + if(res==x){
1.576 + ordered_index_node_impl::link(
1.577 + x->impl(),inf.side,inf.pos,header()->impl());
1.578 + }
1.579 + return res;
1.580 + }
1.581 +
1.582 + void erase_(node_type* x)
1.583 + {
1.584 + ordered_index_node_impl::rebalance_for_erase(
1.585 + x->impl(),header()->parent(),header()->left(),header()->right());
1.586 + super::erase_(x);
1.587 +
1.588 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.589 + detach_iterators(x);
1.590 +#endif
1.591 + }
1.592 +
1.593 + void delete_all_nodes_()
1.594 + {
1.595 + delete_all_nodes(root());
1.596 + }
1.597 +
1.598 + void clear_()
1.599 + {
1.600 + super::clear_();
1.601 + empty_initialize();
1.602 +
1.603 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.604 + safe_super::detach_dereferenceable_iterators();
1.605 +#endif
1.606 + }
1.607 +
1.608 + void swap_(ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& x)
1.609 + {
1.610 + std::swap(key,x.key);
1.611 + std::swap(comp,x.comp);
1.612 +
1.613 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.614 + safe_super::swap(x);
1.615 +#endif
1.616 +
1.617 + super::swap_(x);
1.618 + }
1.619 +
1.620 + bool replace_(value_param_type v,node_type* x)
1.621 + {
1.622 + if(in_place(v,x,Category())){
1.623 + return super::replace_(v,x);
1.624 + }
1.625 +
1.626 + node_type* next=x;
1.627 + node_type::increment(next);
1.628 +
1.629 + ordered_index_node_impl::rebalance_for_erase(
1.630 + x->impl(),header()->parent(),header()->left(),header()->right());
1.631 +
1.632 + BOOST_TRY{
1.633 + link_info inf;
1.634 + if(link_point(key(v),inf,Category())&&super::replace_(v,x)){
1.635 + ordered_index_node_impl::link(
1.636 + x->impl(),inf.side,inf.pos,header()->impl());
1.637 + return true;
1.638 + }
1.639 + ordered_index_node_impl::restore(
1.640 + x->impl(),next->impl(),header()->impl());
1.641 + return false;
1.642 + }
1.643 + BOOST_CATCH(...){
1.644 + ordered_index_node_impl::restore(
1.645 + x->impl(),next->impl(),header()->impl());
1.646 + BOOST_RETHROW;
1.647 + }
1.648 + BOOST_CATCH_END
1.649 + }
1.650 +
1.651 + bool modify_(node_type* x)
1.652 + {
1.653 + bool b;
1.654 + BOOST_TRY{
1.655 + b=in_place(x->value(),x,Category());
1.656 + }
1.657 + BOOST_CATCH(...){
1.658 + erase_(x);
1.659 + BOOST_RETHROW;
1.660 + }
1.661 + BOOST_CATCH_END
1.662 + if(!b){
1.663 + ordered_index_node_impl::rebalance_for_erase(
1.664 + x->impl(),header()->parent(),header()->left(),header()->right());
1.665 + BOOST_TRY{
1.666 + link_info inf;
1.667 + if(!link_point(key(x->value()),inf,Category())){
1.668 + super::erase_(x);
1.669 +
1.670 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.671 + detach_iterators(x);
1.672 +#endif
1.673 + return false;
1.674 + }
1.675 + ordered_index_node_impl::link(
1.676 + x->impl(),inf.side,inf.pos,header()->impl());
1.677 + }
1.678 + BOOST_CATCH(...){
1.679 + super::erase_(x);
1.680 +
1.681 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.682 + detach_iterators(x);
1.683 +#endif
1.684 +
1.685 + BOOST_RETHROW;
1.686 + }
1.687 + BOOST_CATCH_END
1.688 + }
1.689 +
1.690 + BOOST_TRY{
1.691 + if(!super::modify_(x)){
1.692 + ordered_index_node_impl::rebalance_for_erase(
1.693 + x->impl(),header()->parent(),header()->left(),header()->right());
1.694 +
1.695 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.696 + detach_iterators(x);
1.697 +#endif
1.698 +
1.699 + return false;
1.700 + }
1.701 + else return true;
1.702 + }
1.703 + BOOST_CATCH(...){
1.704 + ordered_index_node_impl::rebalance_for_erase(
1.705 + x->impl(),header()->parent(),header()->left(),header()->right());
1.706 +
1.707 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.708 + detach_iterators(x);
1.709 +#endif
1.710 +
1.711 + BOOST_RETHROW;
1.712 + }
1.713 + BOOST_CATCH_END
1.714 + }
1.715 +
1.716 +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
1.717 + /* serialization */
1.718 +
1.719 + template<typename Archive>
1.720 + void save_(
1.721 + Archive& ar,const unsigned int version,const index_saver_type& sm)const
1.722 + {
1.723 + save_(ar,version,sm,Category());
1.724 + }
1.725 +
1.726 + template<typename Archive>
1.727 + void load_(Archive& ar,const unsigned int version,const index_loader_type& lm)
1.728 + {
1.729 + load_(ar,version,lm,Category());
1.730 + }
1.731 +#endif
1.732 +
1.733 +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
1.734 + /* invariant stuff */
1.735 +
1.736 + bool invariant_()const
1.737 + {
1.738 + if(size()==0||begin()==end()){
1.739 + if(size()!=0||begin()!=end()||
1.740 + header()->left()!=header()->impl()||
1.741 + header()->right()!=header()->impl())return false;
1.742 + }
1.743 + else{
1.744 + if((size_type)std::distance(begin(),end())!=size())return false;
1.745 +
1.746 + std::size_t len=ordered_index_node_impl::black_count(
1.747 + leftmost()->impl(),root()->impl());
1.748 + for(const_iterator it=begin(),it_end=end();it!=it_end;++it){
1.749 + node_type* x=it.get_node();
1.750 + node_type* left_x=node_type::from_impl(x->left());
1.751 + node_type* right_x=node_type::from_impl(x->right());
1.752 +
1.753 + if(x->color()==red){
1.754 + if((left_x&&left_x->color()==red)||
1.755 + (right_x&&right_x->color()==red))return false;
1.756 + }
1.757 + if(left_x&&comp(key(x->value()),key(left_x->value())))return false;
1.758 + if(right_x&&comp(key(right_x->value()),key(x->value())))return false;
1.759 + if(!left_x&&!right_x&&
1.760 + ordered_index_node_impl::black_count(
1.761 + x->impl(),root()->impl())!=len)
1.762 + return false;
1.763 + }
1.764 +
1.765 + if(leftmost()->impl()!=
1.766 + ordered_index_node_impl::minimum(root()->impl()))
1.767 + return false;
1.768 + if(rightmost()->impl()!=
1.769 + ordered_index_node_impl::maximum(root()->impl()))
1.770 + return false;
1.771 + }
1.772 +
1.773 + return super::invariant_();
1.774 + }
1.775 +
1.776 +
1.777 + /* This forwarding function eases things for the boost::mem_fn construct
1.778 + * in BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT. Actually,
1.779 + * final_check_invariant is already an inherited member function of
1.780 + * ordered_index.
1.781 + */
1.782 + void check_invariant_()const{this->final_check_invariant_();}
1.783 +#endif
1.784 +
1.785 +private:
1.786 + node_type* header()const{return this->final_header();}
1.787 + node_type* root()const{return node_type::from_impl(header()->parent());}
1.788 + node_type* leftmost()const{return node_type::from_impl(header()->left());}
1.789 + node_type* rightmost()const{return node_type::from_impl(header()->right());}
1.790 +
1.791 + void empty_initialize()
1.792 + {
1.793 + header()->color()=red;
1.794 + /* used to distinguish header() from root, in iterator.operator++ */
1.795 +
1.796 + header()->parent()=0;
1.797 + header()->left()=header()->impl();
1.798 + header()->right()=header()->impl();
1.799 + }
1.800 +
1.801 + struct link_info
1.802 + {
1.803 + ordered_index_side side;
1.804 + ordered_index_node_impl* pos;
1.805 + };
1.806 +
1.807 + bool link_point(key_param_type k,link_info& inf,ordered_unique_tag)
1.808 + {
1.809 + node_type* y=header();
1.810 + node_type* x=root();
1.811 + bool c=true;
1.812 + while(x){
1.813 + y=x;
1.814 + c=comp(k,key(x->value()));
1.815 + x=node_type::from_impl(c?x->left():x->right());
1.816 + }
1.817 + node_type* yy=y;
1.818 + if(c){
1.819 + if(yy==leftmost()){
1.820 + inf.side=to_left;
1.821 + inf.pos=y->impl();
1.822 + return true;
1.823 + }
1.824 + else node_type::decrement(yy);
1.825 + }
1.826 +
1.827 + if(comp(key(yy->value()),k)){
1.828 + inf.side=c?to_left:to_right;
1.829 + inf.pos=y->impl();
1.830 + return true;
1.831 + }
1.832 + else{
1.833 + inf.pos=yy->impl();
1.834 + return false;
1.835 + }
1.836 + }
1.837 +
1.838 + bool link_point(key_param_type k,link_info& inf,ordered_non_unique_tag)
1.839 + {
1.840 + node_type* y=header();
1.841 + node_type* x=root();
1.842 + bool c=true;
1.843 + while (x){
1.844 + y=x;
1.845 + c=comp(k,key(x->value()));
1.846 + x=node_type::from_impl(c?x->left():x->right());
1.847 + }
1.848 + inf.side=c?to_left:to_right;
1.849 + inf.pos=y->impl();
1.850 + return true;
1.851 + }
1.852 +
1.853 + bool hinted_link_point(
1.854 + key_param_type k,node_type* position,link_info& inf,ordered_unique_tag)
1.855 + {
1.856 + if(position->impl()==header()->left()){
1.857 + if(size()>0&&comp(k,key(position->value()))){
1.858 + inf.side=to_left;
1.859 + inf.pos=position->impl();
1.860 + return true;
1.861 + }
1.862 + else return link_point(k,inf,ordered_unique_tag());
1.863 + }
1.864 + else if(position==header()){
1.865 + if(comp(key(rightmost()->value()),k)){
1.866 + inf.side=to_right;
1.867 + inf.pos=rightmost()->impl();
1.868 + return true;
1.869 + }
1.870 + else return link_point(k,inf,ordered_unique_tag());
1.871 + }
1.872 + else{
1.873 + node_type* before=position;
1.874 + node_type::decrement(before);
1.875 + if(comp(key(before->value()),k)&&comp(k,key(position->value()))){
1.876 + if(before->right()==0){
1.877 + inf.side=to_right;
1.878 + inf.pos=before->impl();
1.879 + return true;
1.880 + }
1.881 + else{
1.882 + inf.side=to_left;
1.883 + inf.pos=position->impl();
1.884 + return true;
1.885 + }
1.886 + }
1.887 + else return link_point(k,inf,ordered_unique_tag());
1.888 + }
1.889 + }
1.890 +
1.891 + bool hinted_link_point(
1.892 + key_param_type k,node_type* position,link_info& inf,ordered_non_unique_tag)
1.893 + {
1.894 + if(position->impl()==header()->left()){
1.895 + if(size()>0&&!comp(key(position->value()),k)){
1.896 + inf.side=to_left;
1.897 + inf.pos=position->impl();
1.898 + return true;
1.899 + }
1.900 + else return link_point(k,inf,ordered_non_unique_tag());
1.901 + }
1.902 + else if(position==header()){
1.903 + if(!comp(k,key(rightmost()->value()))){
1.904 + inf.side=to_right;
1.905 + inf.pos=rightmost()->impl();
1.906 + return true;
1.907 + }
1.908 + else return link_point(k,inf,ordered_non_unique_tag());
1.909 + }
1.910 + else{
1.911 + node_type* before=position;
1.912 + node_type::decrement(before);
1.913 + if (!comp(k,key(before->value()))&&!comp(key(position->value()),k)){
1.914 + if(before->right()==0){
1.915 + inf.side=to_right;
1.916 + inf.pos=before->impl();
1.917 + return true;
1.918 + }
1.919 + else{
1.920 + inf.side=to_left;
1.921 + inf.pos=position->impl();
1.922 + return true;
1.923 + }
1.924 + }
1.925 + else return link_point(k,inf,ordered_non_unique_tag());
1.926 + }
1.927 + }
1.928 +
1.929 + void delete_all_nodes(node_type* x)
1.930 + {
1.931 + if(!x)return;
1.932 +
1.933 + delete_all_nodes(node_type::from_impl(x->left()));
1.934 + delete_all_nodes(node_type::from_impl(x->right()));
1.935 + this->final_delete_node_(static_cast<final_node_type*>(x));
1.936 + }
1.937 +
1.938 + bool in_place(value_param_type v,node_type* x,ordered_unique_tag)
1.939 + {
1.940 + node_type* y;
1.941 + if(x!=leftmost()){
1.942 + y=x;
1.943 + node_type::decrement(y);
1.944 + if(!comp(key(y->value()),key(v)))return false;
1.945 + }
1.946 +
1.947 + y=x;
1.948 + node_type::increment(y);
1.949 + return y==header()||comp(key(v),key(y->value()));
1.950 + }
1.951 +
1.952 + bool in_place(value_param_type v,node_type* x,ordered_non_unique_tag)
1.953 + {
1.954 + node_type* y;
1.955 + if(x!=leftmost()){
1.956 + y=x;
1.957 + node_type::decrement(y);
1.958 + if(comp(key(v),key(y->value())))return false;
1.959 + }
1.960 +
1.961 + y=x;
1.962 + node_type::increment(y);
1.963 + return y==header()||!comp(key(y->value()),key(v));
1.964 + }
1.965 +
1.966 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.967 + void detach_iterators(node_type* x)
1.968 + {
1.969 + iterator it=make_iterator(x);
1.970 + safe_mode::detach_equivalent_iterators(it);
1.971 + }
1.972 +#endif
1.973 +
1.974 + template<typename LowerBounder>
1.975 + iterator lower_range(LowerBounder lower)const
1.976 + {
1.977 + node_type* y=header();
1.978 + node_type* z=root();
1.979 +
1.980 + while(z){
1.981 + if(lower(key(z->value()))){
1.982 + y=z;
1.983 + z=node_type::from_impl(z->left());
1.984 + }
1.985 + else z=node_type::from_impl(z->right());
1.986 + }
1.987 +
1.988 + return make_iterator(y);
1.989 + }
1.990 +
1.991 + iterator lower_range(unbounded_type)const
1.992 + {
1.993 + return begin();
1.994 + }
1.995 +
1.996 + template<typename UpperBounder>
1.997 + iterator upper_range(UpperBounder upper)const
1.998 + {
1.999 + node_type* y=header();
1.1000 + node_type* z=root();
1.1001 +
1.1002 + while(z){
1.1003 + if(!upper(key(z->value()))){
1.1004 + y=z;
1.1005 + z=node_type::from_impl(z->left());
1.1006 + }
1.1007 + else z=node_type::from_impl(z->right());
1.1008 + }
1.1009 +
1.1010 + return make_iterator(y);
1.1011 + }
1.1012 +
1.1013 + iterator upper_range(unbounded_type)const
1.1014 + {
1.1015 + return end();
1.1016 + }
1.1017 +
1.1018 +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
1.1019 + template<typename Archive>
1.1020 + void save_(
1.1021 + Archive& ar,const unsigned int version,const index_saver_type& sm,
1.1022 + ordered_unique_tag)const
1.1023 + {
1.1024 + super::save_(ar,version,sm);
1.1025 + }
1.1026 +
1.1027 + template<typename Archive>
1.1028 + void load_(
1.1029 + Archive& ar,const unsigned int version,const index_loader_type& lm,
1.1030 + ordered_unique_tag)
1.1031 + {
1.1032 + super::load_(ar,version,lm);
1.1033 + }
1.1034 +
1.1035 + template<typename Archive>
1.1036 + void save_(
1.1037 + Archive& ar,const unsigned int version,const index_saver_type& sm,
1.1038 + ordered_non_unique_tag)const
1.1039 + {
1.1040 + typedef duplicates_iterator<node_type,value_compare> dup_iterator;
1.1041 +
1.1042 + sm.save(
1.1043 + dup_iterator(begin().get_node(),end().get_node(),value_comp()),
1.1044 + dup_iterator(end().get_node(),value_comp()),
1.1045 + ar,version);
1.1046 + super::save_(ar,version,sm);
1.1047 + }
1.1048 +
1.1049 + template<typename Archive>
1.1050 + void load_(
1.1051 + Archive& ar,const unsigned int version,const index_loader_type& lm,
1.1052 + ordered_non_unique_tag)
1.1053 + {
1.1054 + lm.load(
1.1055 + ::boost::bind(&ordered_index::rearranger,this,_1,_2),
1.1056 + ar,version);
1.1057 + super::load_(ar,version,lm);
1.1058 + }
1.1059 +
1.1060 + void rearranger(node_type* position,node_type *x)
1.1061 + {
1.1062 + if(!position||comp(key(position->value()),key(x->value()))){
1.1063 + position=lower_bound(key(x->value())).get_node();
1.1064 + }
1.1065 + else if(comp(key(x->value()),key(position->value()))){
1.1066 + /* inconsistent rearrangement */
1.1067 + throw_exception(
1.1068 + archive::archive_exception(
1.1069 + archive::archive_exception::other_exception));
1.1070 + }
1.1071 + else node_type::increment(position);
1.1072 +
1.1073 + if(position!=x){
1.1074 + ordered_index_node_impl::rebalance_for_erase(
1.1075 + x->impl(),header()->parent(),header()->left(),header()->right());
1.1076 + ordered_index_node_impl::restore(
1.1077 + x->impl(),position->impl(),header()->impl());
1.1078 + }
1.1079 + }
1.1080 +#endif /* serialization */
1.1081 +
1.1082 + key_from_value key;
1.1083 + key_compare comp;
1.1084 +
1.1085 +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
1.1086 + BOOST_WORKAROUND(__MWERKS__,<=0x3003)
1.1087 +#pragma parse_mfunc_templ reset
1.1088 +#endif
1.1089 +};
1.1090 +
1.1091 +/* comparison */
1.1092 +
1.1093 +template<
1.1094 + typename KeyFromValue1,typename Compare1,
1.1095 + typename SuperMeta1,typename TagList1,typename Category1,
1.1096 + typename KeyFromValue2,typename Compare2,
1.1097 + typename SuperMeta2,typename TagList2,typename Category2
1.1098 +>
1.1099 +bool operator==(
1.1100 + const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x,
1.1101 + const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y)
1.1102 +{
1.1103 + return x.size()==y.size()&&std::equal(x.begin(),x.end(),y.begin());
1.1104 +}
1.1105 +
1.1106 +template<
1.1107 + typename KeyFromValue1,typename Compare1,
1.1108 + typename SuperMeta1,typename TagList1,typename Category1,
1.1109 + typename KeyFromValue2,typename Compare2,
1.1110 + typename SuperMeta2,typename TagList2,typename Category2
1.1111 +>
1.1112 +bool operator<(
1.1113 + const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x,
1.1114 + const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y)
1.1115 +{
1.1116 + return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end());
1.1117 +}
1.1118 +
1.1119 +template<
1.1120 + typename KeyFromValue1,typename Compare1,
1.1121 + typename SuperMeta1,typename TagList1,typename Category1,
1.1122 + typename KeyFromValue2,typename Compare2,
1.1123 + typename SuperMeta2,typename TagList2,typename Category2
1.1124 +>
1.1125 +bool operator!=(
1.1126 + const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x,
1.1127 + const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y)
1.1128 +{
1.1129 + return !(x==y);
1.1130 +}
1.1131 +
1.1132 +template<
1.1133 + typename KeyFromValue1,typename Compare1,
1.1134 + typename SuperMeta1,typename TagList1,typename Category1,
1.1135 + typename KeyFromValue2,typename Compare2,
1.1136 + typename SuperMeta2,typename TagList2,typename Category2
1.1137 +>
1.1138 +bool operator>(
1.1139 + const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x,
1.1140 + const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y)
1.1141 +{
1.1142 + return y<x;
1.1143 +}
1.1144 +
1.1145 +template<
1.1146 + typename KeyFromValue1,typename Compare1,
1.1147 + typename SuperMeta1,typename TagList1,typename Category1,
1.1148 + typename KeyFromValue2,typename Compare2,
1.1149 + typename SuperMeta2,typename TagList2,typename Category2
1.1150 +>
1.1151 +bool operator>=(
1.1152 + const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x,
1.1153 + const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y)
1.1154 +{
1.1155 + return !(x<y);
1.1156 +}
1.1157 +
1.1158 +template<
1.1159 + typename KeyFromValue1,typename Compare1,
1.1160 + typename SuperMeta1,typename TagList1,typename Category1,
1.1161 + typename KeyFromValue2,typename Compare2,
1.1162 + typename SuperMeta2,typename TagList2,typename Category2
1.1163 +>
1.1164 +bool operator<=(
1.1165 + const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x,
1.1166 + const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y)
1.1167 +{
1.1168 + return !(x>y);
1.1169 +}
1.1170 +
1.1171 +/* specialized algorithms */
1.1172 +
1.1173 +template<
1.1174 + typename KeyFromValue,typename Compare,
1.1175 + typename SuperMeta,typename TagList,typename Category
1.1176 +>
1.1177 +void swap(
1.1178 + ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& x,
1.1179 + ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& y)
1.1180 +{
1.1181 + x.swap(y);
1.1182 +}
1.1183 +
1.1184 +} /* namespace multi_index::detail */
1.1185 +
1.1186 +/* ordered_index specifiers */
1.1187 +
1.1188 +template<typename Arg1,typename Arg2,typename Arg3>
1.1189 +struct ordered_unique
1.1190 +{
1.1191 + typedef typename detail::ordered_index_args<
1.1192 + Arg1,Arg2,Arg3> index_args;
1.1193 + typedef typename index_args::tag_list_type::type tag_list_type;
1.1194 + typedef typename index_args::key_from_value_type key_from_value_type;
1.1195 + typedef typename index_args::compare_type compare_type;
1.1196 +
1.1197 + template<typename Super>
1.1198 + struct node_class
1.1199 + {
1.1200 + typedef detail::ordered_index_node<Super> type;
1.1201 + };
1.1202 +
1.1203 + template<typename SuperMeta>
1.1204 + struct index_class
1.1205 + {
1.1206 + typedef detail::ordered_index<
1.1207 + key_from_value_type,compare_type,
1.1208 + SuperMeta,tag_list_type,detail::ordered_unique_tag> type;
1.1209 + };
1.1210 +};
1.1211 +
1.1212 +template<typename Arg1,typename Arg2,typename Arg3>
1.1213 +struct ordered_non_unique
1.1214 +{
1.1215 + typedef detail::ordered_index_args<
1.1216 + Arg1,Arg2,Arg3> index_args;
1.1217 + typedef typename index_args::tag_list_type::type tag_list_type;
1.1218 + typedef typename index_args::key_from_value_type key_from_value_type;
1.1219 + typedef typename index_args::compare_type compare_type;
1.1220 +
1.1221 + template<typename Super>
1.1222 + struct node_class
1.1223 + {
1.1224 + typedef detail::ordered_index_node<Super> type;
1.1225 + };
1.1226 +
1.1227 + template<typename SuperMeta>
1.1228 + struct index_class
1.1229 + {
1.1230 + typedef detail::ordered_index<
1.1231 + key_from_value_type,compare_type,
1.1232 + SuperMeta,tag_list_type,detail::ordered_non_unique_tag> type;
1.1233 + };
1.1234 +};
1.1235 +
1.1236 +} /* namespace multi_index */
1.1237 +
1.1238 +} /* namespace boost */
1.1239 +
1.1240 +#undef BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT
1.1241 +
1.1242 +#endif