boost/multi_index/ordered_index.hpp
/* Copyright 2003-2011 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_ORDERED_INDEX_HPP #define BOOST_MULTI_INDEX_ORDERED_INDEX_HPP #if defined(_MSC_VER)&&(_MSC_VER>=1200) #pragma once #endif #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ #include <algorithm> #include <boost/call_traits.hpp> #include <boost/detail/no_exceptions_support.hpp> #include <boost/detail/workaround.hpp> #include <boost/foreach_fwd.hpp> #include <boost/iterator/reverse_iterator.hpp> #include <boost/mpl/bool.hpp> #include <boost/mpl/if.hpp> #include <boost/mpl/push_front.hpp> #include <boost/multi_index/detail/access_specifier.hpp> #include <boost/multi_index/detail/bidir_node_iterator.hpp> #include <boost/multi_index/detail/index_node_base.hpp> #include <boost/multi_index/detail/modify_key_adaptor.hpp> #include <boost/multi_index/detail/ord_index_node.hpp> #include <boost/multi_index/detail/ord_index_ops.hpp> #include <boost/multi_index/detail/safe_ctr_proxy.hpp> #include <boost/multi_index/detail/safe_mode.hpp> #include <boost/multi_index/detail/scope_guard.hpp> #include <boost/multi_index/detail/unbounded.hpp> #include <boost/multi_index/detail/value_compare.hpp> #include <boost/multi_index/ordered_index_fwd.hpp> #include <boost/ref.hpp> #include <boost/tuple/tuple.hpp> #include <boost/type_traits/is_same.hpp> #include <utility> #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) #include <boost/archive/archive_exception.hpp> #include <boost/bind.hpp> #include <boost/multi_index/detail/duplicates_iterator.hpp> #include <boost/throw_exception.hpp> #endif #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING) #define BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT \ detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)= \ detail::make_obj_guard(*this,&ordered_index::check_invariant_); \ BOOST_JOIN(check_invariant_,__LINE__).touch(); #else #define BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT #endif namespace boost{ namespace multi_index{ namespace detail{ /* ordered_index adds a layer of ordered indexing to a given Super */ /* Most of the implementation of unique and non-unique indices is * shared. We tell from one another on instantiation time by using * these tags. */ struct ordered_unique_tag{}; struct ordered_non_unique_tag{}; template< typename KeyFromValue,typename Compare, typename SuperMeta,typename TagList,typename Category > class ordered_index: BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) #if BOOST_WORKAROUND(BOOST_MSVC,<1300) ,public safe_ctr_proxy_impl< bidir_node_iterator< ordered_index_node<typename SuperMeta::type::node_type> >, ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category> > #else ,public safe_mode::safe_container< ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category> > #endif #endif { #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\ BOOST_WORKAROUND(__MWERKS__,<=0x3003) /* The "ISO C++ Template Parser" option in CW8.3 has a problem with the * lifetime of const references bound to temporaries --precisely what * scopeguards are. */ #pragma parse_mfunc_templ off #endif typedef typename SuperMeta::type super; protected: typedef ordered_index_node< typename super::node_type> node_type; private: typedef typename node_type::impl_type node_impl_type; typedef typename node_impl_type::pointer node_impl_pointer; public: /* types */ typedef typename KeyFromValue::result_type key_type; typedef typename node_type::value_type value_type; typedef KeyFromValue key_from_value; typedef Compare key_compare; typedef value_comparison< value_type,KeyFromValue,Compare> value_compare; typedef tuple<key_from_value,key_compare> ctor_args; typedef typename super::final_allocator_type allocator_type; typedef typename allocator_type::reference reference; typedef typename allocator_type::const_reference const_reference; #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) #if BOOST_WORKAROUND(BOOST_MSVC,<1300) typedef safe_mode::safe_iterator< bidir_node_iterator<node_type>, safe_ctr_proxy< bidir_node_iterator<node_type> > > iterator; #else typedef safe_mode::safe_iterator< bidir_node_iterator<node_type>, ordered_index> iterator; #endif #else typedef bidir_node_iterator<node_type> iterator; #endif typedef iterator const_iterator; typedef std::size_t size_type; typedef std::ptrdiff_t difference_type; typedef typename allocator_type::pointer pointer; typedef typename allocator_type::const_pointer const_pointer; typedef typename boost::reverse_iterator<iterator> reverse_iterator; typedef typename boost::reverse_iterator<const_iterator> const_reverse_iterator; typedef TagList tag_list; protected: typedef typename super::final_node_type final_node_type; typedef tuples::cons< ctor_args, typename super::ctor_args_list> ctor_args_list; typedef typename mpl::push_front< typename super::index_type_list, ordered_index>::type index_type_list; typedef typename mpl::push_front< typename super::iterator_type_list, iterator>::type iterator_type_list; typedef typename mpl::push_front< typename super::const_iterator_type_list, const_iterator>::type const_iterator_type_list; typedef typename super::copy_map_type copy_map_type; #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) typedef typename super::index_saver_type index_saver_type; typedef typename super::index_loader_type index_loader_type; #endif private: #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) #if BOOST_WORKAROUND(BOOST_MSVC,<1300) typedef safe_ctr_proxy_impl< bidir_node_iterator<node_type>, ordered_index> safe_super; #else typedef safe_mode::safe_container<ordered_index> safe_super; #endif #endif typedef typename call_traits< value_type>::param_type value_param_type; typedef typename call_traits< key_type>::param_type key_param_type; public: /* construct/copy/destroy * Default and copy ctors are in the protected section as indices are * not supposed to be created on their own. No range ctor either. */ ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& operator=( const ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& x) { this->final()=x.final(); return *this; } allocator_type get_allocator()const { return this->final().get_allocator(); } /* iterators */ iterator begin(){return make_iterator(leftmost());} const_iterator begin()const{return make_iterator(leftmost());} iterator end(){return make_iterator(header());} const_iterator end()const{return make_iterator(header());} reverse_iterator rbegin(){return make_reverse_iterator(end());} const_reverse_iterator rbegin()const{return make_reverse_iterator(end());} reverse_iterator rend(){return make_reverse_iterator(begin());} const_reverse_iterator rend()const{return make_reverse_iterator(begin());} const_iterator cbegin()const{return begin();} const_iterator cend()const{return end();} const_reverse_iterator crbegin()const{return rbegin();} const_reverse_iterator crend()const{return rend();} iterator iterator_to(const value_type& x) { return make_iterator(node_from_value<node_type>(&x)); } const_iterator iterator_to(const value_type& x)const { return make_iterator(node_from_value<node_type>(&x)); } /* capacity */ bool empty()const{return this->final_empty_();} size_type size()const{return this->final_size_();} size_type max_size()const{return this->final_max_size_();} /* modifiers */ std::pair<iterator,bool> insert(value_param_type x) { BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; std::pair<final_node_type*,bool> p=this->final_insert_(x); return std::pair<iterator,bool>(make_iterator(p.first),p.second); } iterator insert(iterator position,value_param_type x) { BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; std::pair<final_node_type*,bool> p=this->final_insert_( x,static_cast<final_node_type*>(position.get_node())); return make_iterator(p.first); } template<typename InputIterator> void insert(InputIterator first,InputIterator last) { BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; iterator hint=end(); for(;first!=last;++first)hint=insert(hint,*first); } iterator erase(iterator position) { BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position); BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; this->final_erase_(static_cast<final_node_type*>(position++.get_node())); return position; } size_type erase(key_param_type x) { BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; std::pair<iterator,iterator> p=equal_range(x); size_type s=0; while(p.first!=p.second){ p.first=erase(p.first); ++s; } return s; } iterator erase(iterator first,iterator last) { BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first); BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last); BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this); BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this); BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last); BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; while(first!=last){ first=erase(first); } return first; } bool replace(iterator position,value_param_type x) { BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position); BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; return this->final_replace_( x,static_cast<final_node_type*>(position.get_node())); } template<typename Modifier> bool modify(iterator position,Modifier mod) { BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position); BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) /* MSVC++ 6.0 optimizer on safe mode code chokes if this * this is not added. Left it for all compilers as it does no * harm. */ position.detach(); #endif return this->final_modify_( mod,static_cast<final_node_type*>(position.get_node())); } template<typename Modifier,typename Rollback> bool modify(iterator position,Modifier mod,Rollback back) { BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position); BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) /* MSVC++ 6.0 optimizer on safe mode code chokes if this * this is not added. Left it for all compilers as it does no * harm. */ position.detach(); #endif return this->final_modify_( mod,back,static_cast<final_node_type*>(position.get_node())); } template<typename Modifier> bool modify_key(iterator position,Modifier mod) { BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position); BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; return modify( position,modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key)); } template<typename Modifier,typename Rollback> bool modify_key(iterator position,Modifier mod,Rollback back) { BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position); BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; return modify( position, modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key), modify_key_adaptor<Rollback,value_type,KeyFromValue>(back,key)); } void swap(ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& x) { BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; this->final_swap_(x.final()); } void clear() { BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT; this->final_clear_(); } /* observers */ key_from_value key_extractor()const{return key;} key_compare key_comp()const{return comp;} value_compare value_comp()const{return value_compare(key,comp);} /* set operations */ /* Internally, these ops rely on const_iterator being the same * type as iterator. */ template<typename CompatibleKey> iterator find(const CompatibleKey& x)const { return make_iterator(ordered_index_find(root(),header(),key,x,comp)); } template<typename CompatibleKey,typename CompatibleCompare> iterator find( const CompatibleKey& x,const CompatibleCompare& comp)const { return make_iterator(ordered_index_find(root(),header(),key,x,comp)); } template<typename CompatibleKey> size_type count(const CompatibleKey& x)const { return count(x,comp); } template<typename CompatibleKey,typename CompatibleCompare> size_type count(const CompatibleKey& x,const CompatibleCompare& comp)const { std::pair<iterator,iterator> p=equal_range(x,comp); size_type n=std::distance(p.first,p.second); return n; } template<typename CompatibleKey> iterator lower_bound(const CompatibleKey& x)const { return make_iterator( ordered_index_lower_bound(root(),header(),key,x,comp)); } template<typename CompatibleKey,typename CompatibleCompare> iterator lower_bound( const CompatibleKey& x,const CompatibleCompare& comp)const { return make_iterator( ordered_index_lower_bound(root(),header(),key,x,comp)); } template<typename CompatibleKey> iterator upper_bound(const CompatibleKey& x)const { return make_iterator( ordered_index_upper_bound(root(),header(),key,x,comp)); } template<typename CompatibleKey,typename CompatibleCompare> iterator upper_bound( const CompatibleKey& x,const CompatibleCompare& comp)const { return make_iterator( ordered_index_upper_bound(root(),header(),key,x,comp)); } template<typename CompatibleKey> std::pair<iterator,iterator> equal_range( const CompatibleKey& x)const { std::pair<node_type*,node_type*> p= ordered_index_equal_range(root(),header(),key,x,comp); return std::pair<iterator,iterator>( make_iterator(p.first),make_iterator(p.second)); } template<typename CompatibleKey,typename CompatibleCompare> std::pair<iterator,iterator> equal_range( const CompatibleKey& x,const CompatibleCompare& comp)const { std::pair<node_type*,node_type*> p= ordered_index_equal_range(root(),header(),key,x,comp); return std::pair<iterator,iterator>( make_iterator(p.first),make_iterator(p.second)); } /* range */ template<typename LowerBounder,typename UpperBounder> std::pair<iterator,iterator> range(LowerBounder lower,UpperBounder upper)const { typedef typename mpl::if_< is_same<LowerBounder,unbounded_type>, BOOST_DEDUCED_TYPENAME mpl::if_< is_same<UpperBounder,unbounded_type>, both_unbounded_tag, lower_unbounded_tag >::type, BOOST_DEDUCED_TYPENAME mpl::if_< is_same<UpperBounder,unbounded_type>, upper_unbounded_tag, none_unbounded_tag >::type >::type dispatch; return range(lower,upper,dispatch()); } BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: ordered_index(const ctor_args_list& args_list,const allocator_type& al): super(args_list.get_tail(),al), key(tuples::get<0>(args_list.get_head())), comp(tuples::get<1>(args_list.get_head())) { empty_initialize(); } ordered_index( const ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& x): super(x), #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) safe_super(), #endif key(x.key), comp(x.comp) { /* Copy ctor just takes the key and compare objects from x. The rest is * done in subsequent call to copy_(). */ } ~ordered_index() { /* the container is guaranteed to be empty by now */ } #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) iterator make_iterator(node_type* node){return iterator(node,this);} const_iterator make_iterator(node_type* node)const {return const_iterator(node,const_cast<ordered_index*>(this));} #else iterator make_iterator(node_type* node){return iterator(node);} const_iterator make_iterator(node_type* node)const {return const_iterator(node);} #endif void copy_( const ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& x, const copy_map_type& map) { if(!x.root()){ empty_initialize(); } else{ header()->color()=x.header()->color(); node_type* root_cpy=map.find(static_cast<final_node_type*>(x.root())); header()->parent()=root_cpy->impl(); node_type* leftmost_cpy=map.find( static_cast<final_node_type*>(x.leftmost())); header()->left()=leftmost_cpy->impl(); node_type* rightmost_cpy=map.find( static_cast<final_node_type*>(x.rightmost())); header()->right()=rightmost_cpy->impl(); typedef typename copy_map_type::const_iterator copy_map_iterator; for(copy_map_iterator it=map.begin(),it_end=map.end();it!=it_end;++it){ node_type* org=it->first; node_type* cpy=it->second; cpy->color()=org->color(); node_impl_pointer parent_org=org->parent(); if(parent_org==node_impl_pointer(0))cpy->parent()=node_impl_pointer(0); else{ node_type* parent_cpy=map.find( static_cast<final_node_type*>(node_type::from_impl(parent_org))); cpy->parent()=parent_cpy->impl(); if(parent_org->left()==org->impl()){ parent_cpy->left()=cpy->impl(); } else if(parent_org->right()==org->impl()){ /* header() does not satisfy this nor the previous check */ parent_cpy->right()=cpy->impl(); } } if(org->left()==node_impl_pointer(0)) cpy->left()=node_impl_pointer(0); if(org->right()==node_impl_pointer(0)) cpy->right()=node_impl_pointer(0); } } super::copy_(x,map); } node_type* insert_(value_param_type v,node_type* x) { link_info inf; if(!link_point(key(v),inf,Category())){ return node_type::from_impl(inf.pos); } node_type* res=static_cast<node_type*>(super::insert_(v,x)); if(res==x){ node_impl_type::link(x->impl(),inf.side,inf.pos,header()->impl()); } return res; } node_type* insert_(value_param_type v,node_type* position,node_type* x) { link_info inf; if(!hinted_link_point(key(v),position,inf,Category())){ return node_type::from_impl(inf.pos); } node_type* res=static_cast<node_type*>(super::insert_(v,position,x)); if(res==x){ node_impl_type::link(x->impl(),inf.side,inf.pos,header()->impl()); } return res; } void erase_(node_type* x) { node_impl_type::rebalance_for_erase( x->impl(),header()->parent(),header()->left(),header()->right()); super::erase_(x); #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) detach_iterators(x); #endif } void delete_all_nodes_() { delete_all_nodes(root()); } void clear_() { super::clear_(); empty_initialize(); #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) safe_super::detach_dereferenceable_iterators(); #endif } void swap_(ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& x) { std::swap(key,x.key); std::swap(comp,x.comp); #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) safe_super::swap(x); #endif super::swap_(x); } bool replace_(value_param_type v,node_type* x) { if(in_place(v,x,Category())){ return super::replace_(v,x); } node_type* next=x; node_type::increment(next); node_impl_type::rebalance_for_erase( x->impl(),header()->parent(),header()->left(),header()->right()); BOOST_TRY{ link_info inf; if(link_point(key(v),inf,Category())&&super::replace_(v,x)){ node_impl_type::link(x->impl(),inf.side,inf.pos,header()->impl()); return true; } node_impl_type::restore(x->impl(),next->impl(),header()->impl()); return false; } BOOST_CATCH(...){ node_impl_type::restore(x->impl(),next->impl(),header()->impl()); BOOST_RETHROW; } BOOST_CATCH_END } bool modify_(node_type* x) { bool b; BOOST_TRY{ b=in_place(x->value(),x,Category()); } BOOST_CATCH(...){ erase_(x); BOOST_RETHROW; } BOOST_CATCH_END if(!b){ node_impl_type::rebalance_for_erase( x->impl(),header()->parent(),header()->left(),header()->right()); BOOST_TRY{ link_info inf; if(!link_point(key(x->value()),inf,Category())){ super::erase_(x); #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) detach_iterators(x); #endif return false; } node_impl_type::link(x->impl(),inf.side,inf.pos,header()->impl()); } BOOST_CATCH(...){ super::erase_(x); #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) detach_iterators(x); #endif BOOST_RETHROW; } BOOST_CATCH_END } BOOST_TRY{ if(!super::modify_(x)){ node_impl_type::rebalance_for_erase( x->impl(),header()->parent(),header()->left(),header()->right()); #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) detach_iterators(x); #endif return false; } else return true; } BOOST_CATCH(...){ node_impl_type::rebalance_for_erase( x->impl(),header()->parent(),header()->left(),header()->right()); #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) detach_iterators(x); #endif BOOST_RETHROW; } BOOST_CATCH_END } bool modify_rollback_(node_type* x) { if(in_place(x->value(),x,Category())){ return super::modify_rollback_(x); } node_type* next=x; node_type::increment(next); node_impl_type::rebalance_for_erase( x->impl(),header()->parent(),header()->left(),header()->right()); BOOST_TRY{ link_info inf; if(link_point(key(x->value()),inf,Category())&& super::modify_rollback_(x)){ node_impl_type::link(x->impl(),inf.side,inf.pos,header()->impl()); return true; } node_impl_type::restore(x->impl(),next->impl(),header()->impl()); return false; } BOOST_CATCH(...){ node_impl_type::restore(x->impl(),next->impl(),header()->impl()); BOOST_RETHROW; } BOOST_CATCH_END } #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) /* serialization */ template<typename Archive> void save_( Archive& ar,const unsigned int version,const index_saver_type& sm)const { save_(ar,version,sm,Category()); } template<typename Archive> void load_(Archive& ar,const unsigned int version,const index_loader_type& lm) { load_(ar,version,lm,Category()); } #endif #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING) /* invariant stuff */ bool invariant_()const { if(size()==0||begin()==end()){ if(size()!=0||begin()!=end()|| header()->left()!=header()->impl()|| header()->right()!=header()->impl())return false; } else{ if((size_type)std::distance(begin(),end())!=size())return false; std::size_t len=node_impl_type::black_count( leftmost()->impl(),root()->impl()); for(const_iterator it=begin(),it_end=end();it!=it_end;++it){ node_type* x=it.get_node(); node_type* left_x=node_type::from_impl(x->left()); node_type* right_x=node_type::from_impl(x->right()); if(x->color()==red){ if((left_x&&left_x->color()==red)|| (right_x&&right_x->color()==red))return false; } if(left_x&&comp(key(x->value()),key(left_x->value())))return false; if(right_x&&comp(key(right_x->value()),key(x->value())))return false; if(!left_x&&!right_x&& node_impl_type::black_count(x->impl(),root()->impl())!=len) return false; } if(leftmost()->impl()!=node_impl_type::minimum(root()->impl())) return false; if(rightmost()->impl()!=node_impl_type::maximum(root()->impl())) return false; } return super::invariant_(); } /* This forwarding function eases things for the boost::mem_fn construct * in BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT. Actually, * final_check_invariant is already an inherited member function of * ordered_index. */ void check_invariant_()const{this->final_check_invariant_();} #endif private: node_type* header()const{return this->final_header();} node_type* root()const{return node_type::from_impl(header()->parent());} node_type* leftmost()const{return node_type::from_impl(header()->left());} node_type* rightmost()const{return node_type::from_impl(header()->right());} void empty_initialize() { header()->color()=red; /* used to distinguish header() from root, in iterator.operator++ */ header()->parent()=node_impl_pointer(0); header()->left()=header()->impl(); header()->right()=header()->impl(); } struct link_info { link_info():side(to_left){} ordered_index_side side; node_impl_pointer pos; }; bool link_point(key_param_type k,link_info& inf,ordered_unique_tag) { node_type* y=header(); node_type* x=root(); bool c=true; while(x){ y=x; c=comp(k,key(x->value())); x=node_type::from_impl(c?x->left():x->right()); } node_type* yy=y; if(c){ if(yy==leftmost()){ inf.side=to_left; inf.pos=y->impl(); return true; } else node_type::decrement(yy); } if(comp(key(yy->value()),k)){ inf.side=c?to_left:to_right; inf.pos=y->impl(); return true; } else{ inf.pos=yy->impl(); return false; } } bool link_point(key_param_type k,link_info& inf,ordered_non_unique_tag) { node_type* y=header(); node_type* x=root(); bool c=true; while (x){ y=x; c=comp(k,key(x->value())); x=node_type::from_impl(c?x->left():x->right()); } inf.side=c?to_left:to_right; inf.pos=y->impl(); return true; } bool lower_link_point(key_param_type k,link_info& inf,ordered_non_unique_tag) { node_type* y=header(); node_type* x=root(); bool c=false; while (x){ y=x; c=comp(key(x->value()),k); x=node_type::from_impl(c?x->right():x->left()); } inf.side=c?to_right:to_left; inf.pos=y->impl(); return true; } bool hinted_link_point( key_param_type k,node_type* position,link_info& inf,ordered_unique_tag) { if(position->impl()==header()->left()){ if(size()>0&&comp(k,key(position->value()))){ inf.side=to_left; inf.pos=position->impl(); return true; } else return link_point(k,inf,ordered_unique_tag()); } else if(position==header()){ if(comp(key(rightmost()->value()),k)){ inf.side=to_right; inf.pos=rightmost()->impl(); return true; } else return link_point(k,inf,ordered_unique_tag()); } else{ node_type* before=position; node_type::decrement(before); if(comp(key(before->value()),k)&&comp(k,key(position->value()))){ if(before->right()==node_impl_pointer(0)){ inf.side=to_right; inf.pos=before->impl(); return true; } else{ inf.side=to_left; inf.pos=position->impl(); return true; } } else return link_point(k,inf,ordered_unique_tag()); } } bool hinted_link_point( key_param_type k,node_type* position,link_info& inf,ordered_non_unique_tag) { if(position->impl()==header()->left()){ if(size()>0&&!comp(key(position->value()),k)){ inf.side=to_left; inf.pos=position->impl(); return true; } else return lower_link_point(k,inf,ordered_non_unique_tag()); } else if(position==header()){ if(!comp(k,key(rightmost()->value()))){ inf.side=to_right; inf.pos=rightmost()->impl(); return true; } else return link_point(k,inf,ordered_non_unique_tag()); } else{ node_type* before=position; node_type::decrement(before); if(!comp(k,key(before->value()))){ if(!comp(key(position->value()),k)){ if(before->right()==node_impl_pointer(0)){ inf.side=to_right; inf.pos=before->impl(); return true; } else{ inf.side=to_left; inf.pos=position->impl(); return true; } } else return lower_link_point(k,inf,ordered_non_unique_tag()); } else return link_point(k,inf,ordered_non_unique_tag()); } } void delete_all_nodes(node_type* x) { if(!x)return; delete_all_nodes(node_type::from_impl(x->left())); delete_all_nodes(node_type::from_impl(x->right())); this->final_delete_node_(static_cast<final_node_type*>(x)); } bool in_place(value_param_type v,node_type* x,ordered_unique_tag) { node_type* y; if(x!=leftmost()){ y=x; node_type::decrement(y); if(!comp(key(y->value()),key(v)))return false; } y=x; node_type::increment(y); return y==header()||comp(key(v),key(y->value())); } bool in_place(value_param_type v,node_type* x,ordered_non_unique_tag) { node_type* y; if(x!=leftmost()){ y=x; node_type::decrement(y); if(comp(key(v),key(y->value())))return false; } y=x; node_type::increment(y); return y==header()||!comp(key(y->value()),key(v)); } #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) void detach_iterators(node_type* x) { iterator it=make_iterator(x); safe_mode::detach_equivalent_iterators(it); } #endif template<typename LowerBounder,typename UpperBounder> std::pair<iterator,iterator> range(LowerBounder lower,UpperBounder upper,none_unbounded_tag)const { node_type* y=header(); node_type* z=root(); while(z){ if(!lower(key(z->value()))){ z=node_type::from_impl(z->right()); } else if(!upper(key(z->value()))){ y=z; z=node_type::from_impl(z->left()); } else{ return std::pair<iterator,iterator>( make_iterator( lower_range(node_type::from_impl(z->left()),z,lower)), make_iterator( upper_range(node_type::from_impl(z->right()),y,upper))); } } return std::pair<iterator,iterator>(make_iterator(y),make_iterator(y)); } template<typename LowerBounder,typename UpperBounder> std::pair<iterator,iterator> range(LowerBounder,UpperBounder upper,lower_unbounded_tag)const { return std::pair<iterator,iterator>( begin(), make_iterator(upper_range(root(),header(),upper))); } template<typename LowerBounder,typename UpperBounder> std::pair<iterator,iterator> range(LowerBounder lower,UpperBounder,upper_unbounded_tag)const { return std::pair<iterator,iterator>( make_iterator(lower_range(root(),header(),lower)), end()); } template<typename LowerBounder,typename UpperBounder> std::pair<iterator,iterator> range(LowerBounder,UpperBounder,both_unbounded_tag)const { return std::pair<iterator,iterator>(begin(),end()); } template<typename LowerBounder> node_type * lower_range(node_type* top,node_type* y,LowerBounder lower)const { while(top){ if(lower(key(top->value()))){ y=top; top=node_type::from_impl(top->left()); } else top=node_type::from_impl(top->right()); } return y; } template<typename UpperBounder> node_type * upper_range(node_type* top,node_type* y,UpperBounder upper)const { while(top){ if(!upper(key(top->value()))){ y=top; top=node_type::from_impl(top->left()); } else top=node_type::from_impl(top->right()); } return y; } #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) template<typename Archive> void save_( Archive& ar,const unsigned int version,const index_saver_type& sm, ordered_unique_tag)const { super::save_(ar,version,sm); } template<typename Archive> void load_( Archive& ar,const unsigned int version,const index_loader_type& lm, ordered_unique_tag) { super::load_(ar,version,lm); } template<typename Archive> void save_( Archive& ar,const unsigned int version,const index_saver_type& sm, ordered_non_unique_tag)const { typedef duplicates_iterator<node_type,value_compare> dup_iterator; sm.save( dup_iterator(begin().get_node(),end().get_node(),value_comp()), dup_iterator(end().get_node(),value_comp()), ar,version); super::save_(ar,version,sm); } template<typename Archive> void load_( Archive& ar,const unsigned int version,const index_loader_type& lm, ordered_non_unique_tag) { lm.load( ::boost::bind(&ordered_index::rearranger,this,_1,_2), ar,version); super::load_(ar,version,lm); } void rearranger(node_type* position,node_type *x) { if(!position||comp(key(position->value()),key(x->value()))){ position=lower_bound(key(x->value())).get_node(); } else if(comp(key(x->value()),key(position->value()))){ /* inconsistent rearrangement */ throw_exception( archive::archive_exception( archive::archive_exception::other_exception)); } else node_type::increment(position); if(position!=x){ node_impl_type::rebalance_for_erase( x->impl(),header()->parent(),header()->left(),header()->right()); node_impl_type::restore( x->impl(),position->impl(),header()->impl()); } } #endif /* serialization */ key_from_value key; key_compare comp; #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\ BOOST_WORKAROUND(__MWERKS__,<=0x3003) #pragma parse_mfunc_templ reset #endif }; /* comparison */ template< typename KeyFromValue1,typename Compare1, typename SuperMeta1,typename TagList1,typename Category1, typename KeyFromValue2,typename Compare2, typename SuperMeta2,typename TagList2,typename Category2 > bool operator==( const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x, const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y) { return x.size()==y.size()&&std::equal(x.begin(),x.end(),y.begin()); } template< typename KeyFromValue1,typename Compare1, typename SuperMeta1,typename TagList1,typename Category1, typename KeyFromValue2,typename Compare2, typename SuperMeta2,typename TagList2,typename Category2 > bool operator<( const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x, const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y) { return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end()); } template< typename KeyFromValue1,typename Compare1, typename SuperMeta1,typename TagList1,typename Category1, typename KeyFromValue2,typename Compare2, typename SuperMeta2,typename TagList2,typename Category2 > bool operator!=( const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x, const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y) { return !(x==y); } template< typename KeyFromValue1,typename Compare1, typename SuperMeta1,typename TagList1,typename Category1, typename KeyFromValue2,typename Compare2, typename SuperMeta2,typename TagList2,typename Category2 > bool operator>( const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x, const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y) { return y<x; } template< typename KeyFromValue1,typename Compare1, typename SuperMeta1,typename TagList1,typename Category1, typename KeyFromValue2,typename Compare2, typename SuperMeta2,typename TagList2,typename Category2 > bool operator>=( const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x, const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y) { return !(x<y); } template< typename KeyFromValue1,typename Compare1, typename SuperMeta1,typename TagList1,typename Category1, typename KeyFromValue2,typename Compare2, typename SuperMeta2,typename TagList2,typename Category2 > bool operator<=( const ordered_index<KeyFromValue1,Compare1,SuperMeta1,TagList1,Category1>& x, const ordered_index<KeyFromValue2,Compare2,SuperMeta2,TagList2,Category2>& y) { return !(x>y); } /* specialized algorithms */ template< typename KeyFromValue,typename Compare, typename SuperMeta,typename TagList,typename Category > void swap( ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& x, ordered_index<KeyFromValue,Compare,SuperMeta,TagList,Category>& y) { x.swap(y); } } /* namespace multi_index::detail */ /* ordered_index specifiers */ template<typename Arg1,typename Arg2,typename Arg3> struct ordered_unique { typedef typename detail::ordered_index_args< Arg1,Arg2,Arg3> index_args; typedef typename index_args::tag_list_type::type tag_list_type; typedef typename index_args::key_from_value_type key_from_value_type; typedef typename index_args::compare_type compare_type; template<typename Super> struct node_class { typedef detail::ordered_index_node<Super> type; }; template<typename SuperMeta> struct index_class { typedef detail::ordered_index< key_from_value_type,compare_type, SuperMeta,tag_list_type,detail::ordered_unique_tag> type; }; }; template<typename Arg1,typename Arg2,typename Arg3> struct ordered_non_unique { typedef detail::ordered_index_args< Arg1,Arg2,Arg3> index_args; typedef typename index_args::tag_list_type::type tag_list_type; typedef typename index_args::key_from_value_type key_from_value_type; typedef typename index_args::compare_type compare_type; template<typename Super> struct node_class { typedef detail::ordered_index_node<Super> type; }; template<typename SuperMeta> struct index_class { typedef detail::ordered_index< key_from_value_type,compare_type, SuperMeta,tag_list_type,detail::ordered_non_unique_tag> type; }; }; } /* namespace multi_index */ } /* namespace boost */ /* Boost.Foreach compatibility */ template< typename KeyFromValue,typename Compare, typename SuperMeta,typename TagList,typename Category > inline boost::mpl::true_* boost_foreach_is_noncopyable( boost::multi_index::detail::ordered_index< KeyFromValue,Compare,SuperMeta,TagList,Category>*&, boost::foreach::tag) { return 0; } #undef BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT #endif