Swiftdiff options
Diffstat (limited to '3rdParty/Boost/src/boost/multi_index')
46 files changed, 8185 insertions, 0 deletions
diff --git a/3rdParty/Boost/src/boost/multi_index/detail/access_specifier.hpp b/3rdParty/Boost/src/boost/multi_index/detail/access_specifier.hpp new file mode 100644 index 0000000..84c2f7d --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/access_specifier.hpp @@ -0,0 +1,55 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_ACCESS_SPECIFIER_HPP +#define BOOST_MULTI_INDEX_DETAIL_ACCESS_SPECIFIER_HPP + +#if defined(_MSC_VER)&&(_MSC_VER>=1200) +#pragma once +#endif + +#include <boost/config.hpp> +#include <boost/detail/workaround.hpp> + +/* In those compilers that do not accept the member template friend syntax, + * some protected and private sections might need to be specified as + * public. + */ + +#if defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) +#define BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS public +#define BOOST_MULTI_INDEX_PRIVATE_IF_MEMBER_TEMPLATE_FRIENDS public +#else +#define BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS protected +#define BOOST_MULTI_INDEX_PRIVATE_IF_MEMBER_TEMPLATE_FRIENDS private +#endif + +/* GCC does not correctly support in-class using declarations for template + * functions. See http://gcc.gnu.org/bugzilla/show_bug.cgi?id=9810 + * MSVC 7.1/8.0 seem to have a similar problem, though the conditions in + * which the error happens are not that simple. I have yet to isolate this + * into a snippet suitable for bug reporting. + * Sun Studio also has this problem, which might be related, from the + * information gathered at Sun forums, with a known issue notified at the + * internal bug report 6421933. The bug is present up to Studio Express 2, + * the latest preview version of the future Sun Studio 12. As of this writing + * (October 2006) it is not known whether a fix will finally make it into the + * official Sun Studio 12. + */ + +#if BOOST_WORKAROUND(__GNUC__, <3)||\ + BOOST_WORKAROUND(__GNUC__,==3)&&(__GNUC_MINOR__<4)||\ + BOOST_WORKAROUND(BOOST_MSVC,==1310)||\ + BOOST_WORKAROUND(BOOST_MSVC,==1400)||\ + BOOST_WORKAROUND(__SUNPRO_CC,BOOST_TESTED_AT(0x590)) +#define BOOST_MULTI_INDEX_PRIVATE_IF_USING_DECL_FOR_TEMPL_FUNCTIONS public +#else +#define BOOST_MULTI_INDEX_PRIVATE_IF_USING_DECL_FOR_TEMPL_FUNCTIONS private +#endif + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/adl_swap.hpp b/3rdParty/Boost/src/boost/multi_index/detail/adl_swap.hpp new file mode 100644 index 0000000..e78235d --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/adl_swap.hpp @@ -0,0 +1,44 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_ADL_SWAP_HPP +#define BOOST_MULTI_INDEX_DETAIL_ADL_SWAP_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> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +template<typename T> +void adl_swap(T& x,T& y) +{ + +#if !defined(BOOST_FUNCTION_SCOPE_USING_DECLARATION_BREAKS_ADL) + using std::swap; + swap(x,y); +#else + std::swap(x,y); +#endif + +} + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/archive_constructed.hpp b/3rdParty/Boost/src/boost/multi_index/detail/archive_constructed.hpp new file mode 100644 index 0000000..ee00dfa --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/archive_constructed.hpp @@ -0,0 +1,79 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_ARCHIVE_CONSTRUCTED_HPP +#define BOOST_MULTI_INDEX_DETAIL_ARCHIVE_CONSTRUCTED_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 <boost/detail/no_exceptions_support.hpp> +#include <boost/noncopyable.hpp> +#include <boost/serialization/serialization.hpp> +#include <boost/type_traits/aligned_storage.hpp> +#include <boost/type_traits/alignment_of.hpp> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* constructs a stack-based object from a serialization archive */ + +template<typename T> +struct archive_constructed:private noncopyable +{ + template<class Archive> + archive_constructed(Archive& ar,const unsigned int version) + { + serialization::load_construct_data_adl(ar,&get(),version); + BOOST_TRY{ + ar>>get(); + } + BOOST_CATCH(...){ + (&get())->~T(); + BOOST_RETHROW; + } + BOOST_CATCH_END + } + + template<class Archive> + archive_constructed(const char* name,Archive& ar,const unsigned int version) + { + serialization::load_construct_data_adl(ar,&get(),version); + BOOST_TRY{ + ar>>serialization::make_nvp(name,get()); + } + BOOST_CATCH(...){ + (&get())->~T(); + BOOST_RETHROW; + } + BOOST_CATCH_END + } + + ~archive_constructed() + { + (&get())->~T(); + } + + T& get(){return *static_cast<T*>(static_cast<void*>(&space));} + +private: + typename aligned_storage<sizeof(T),alignment_of<T>::value>::type space; +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/auto_space.hpp b/3rdParty/Boost/src/boost/multi_index/detail/auto_space.hpp new file mode 100644 index 0000000..9b0a0dc --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/auto_space.hpp @@ -0,0 +1,95 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_AUTO_SPACE_HPP +#define BOOST_MULTI_INDEX_DETAIL_AUTO_SPACE_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/detail/allocator_utilities.hpp> +#include <boost/multi_index/detail/adl_swap.hpp> +#include <boost/multi_index/detail/prevent_eti.hpp> +#include <boost/noncopyable.hpp> +#include <memory> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* auto_space provides uninitialized space suitably to store + * a given number of elements of a given type. + */ + +/* NB: it is not clear whether using an allocator to handle + * zero-sized arrays of elements is conformant or not. GCC 3.3.1 + * and prior fail here, other stdlibs handle the issue gracefully. + * To be on the safe side, the case n==0 is given special treatment. + * References: + * GCC Bugzilla, "standard allocator crashes when deallocating segment + * "of zero length", http://gcc.gnu.org/bugzilla/show_bug.cgi?id=14176 + * C++ Standard Library Defect Report List (Revision 28), issue 199 + * "What does allocate(0) return?", + * http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-defects.html#199 + */ + +template<typename T,typename Allocator=std::allocator<T> > +struct auto_space:private noncopyable +{ + typedef typename prevent_eti< + Allocator, + typename boost::detail::allocator::rebind_to< + Allocator,T + >::type + >::type::pointer pointer; + + explicit auto_space(const Allocator& al=Allocator(),std::size_t n=1): + al_(al),n_(n),data_(n_?al_.allocate(n_):pointer(0)) + {} + + ~auto_space() + { + if(n_)al_.deallocate(data_,n_); + } + + Allocator get_allocator()const{return al_;} + + pointer data()const{return data_;} + + void swap(auto_space& x) + { + if(al_!=x.al_)adl_swap(al_,x.al_); + std::swap(n_,x.n_); + std::swap(data_,x.data_); + } + +private: + typename boost::detail::allocator::rebind_to< + Allocator,T>::type al_; + std::size_t n_; + pointer data_; +}; + +template<typename T,typename Allocator> +void swap(auto_space<T,Allocator>& x,auto_space<T,Allocator>& y) +{ + x.swap(y); +} + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/base_type.hpp b/3rdParty/Boost/src/boost/multi_index/detail/base_type.hpp new file mode 100644 index 0000000..d25332e --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/base_type.hpp @@ -0,0 +1,87 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_BASE_TYPE_HPP +#define BOOST_MULTI_INDEX_DETAIL_BASE_TYPE_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 <boost/detail/workaround.hpp> +#include <boost/mpl/at.hpp> +#include <boost/mpl/apply.hpp> +#include <boost/mpl/size.hpp> +#include <boost/multi_index/detail/index_base.hpp> +#include <boost/multi_index/detail/is_index_list.hpp> +#include <boost/multi_index/detail/msvc_index_specifier.hpp> +#include <boost/static_assert.hpp> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* MPL machinery to construct a linear hierarchy of indices out of + * a index list. + */ + +#if BOOST_WORKAROUND(BOOST_MSVC,<1310) +struct index_applier +{ + template<typename IndexSpecifierMeta,typename SuperMeta> + struct apply: + msvc_index_specifier<IndexSpecifierMeta::type>:: + template result_index_class<SuperMeta> + { + }; +}; +#else +struct index_applier +{ + template<typename IndexSpecifierMeta,typename SuperMeta> + struct apply + { + typedef typename IndexSpecifierMeta::type index_specifier; + typedef typename index_specifier:: + BOOST_NESTED_TEMPLATE index_class<SuperMeta>::type type; + }; +}; +#endif + +template<int N,typename Value,typename IndexSpecifierList,typename Allocator> +struct nth_layer +{ + BOOST_STATIC_CONSTANT(int,length=mpl::size<IndexSpecifierList>::value); + + typedef typename mpl::eval_if_c< + N==length, + mpl::identity<index_base<Value,IndexSpecifierList,Allocator> >, + mpl::apply2< + index_applier, + mpl::at_c<IndexSpecifierList,N>, + nth_layer<N+1,Value,IndexSpecifierList,Allocator> + > + >::type type; +}; + +template<typename Value,typename IndexSpecifierList,typename Allocator> +struct multi_index_base_type:nth_layer<0,Value,IndexSpecifierList,Allocator> +{ + BOOST_STATIC_ASSERT(detail::is_index_list<IndexSpecifierList>::value); +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/bidir_node_iterator.hpp b/3rdParty/Boost/src/boost/multi_index/detail/bidir_node_iterator.hpp new file mode 100644 index 0000000..2155255 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/bidir_node_iterator.hpp @@ -0,0 +1,113 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_BIDIR_NODE_ITERATOR_HPP +#define BOOST_MULTI_INDEX_DETAIL_BIDIR_NODE_ITERATOR_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 <boost/operators.hpp> + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) +#include <boost/serialization/nvp.hpp> +#include <boost/serialization/split_member.hpp> +#endif + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* Iterator class for node-based indices with bidirectional + * iterators (ordered and sequenced indices.) + */ + +template<typename Node> +class bidir_node_iterator: + public bidirectional_iterator_helper< + bidir_node_iterator<Node>, + typename Node::value_type, + std::ptrdiff_t, + const typename Node::value_type*, + const typename Node::value_type&> +{ +public: + bidir_node_iterator(){} + explicit bidir_node_iterator(Node* node_):node(node_){} + + const typename Node::value_type& operator*()const + { + return node->value(); + } + + bidir_node_iterator& operator++() + { + Node::increment(node); + return *this; + } + + bidir_node_iterator& operator--() + { + Node::decrement(node); + return *this; + } + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) + /* Serialization. As for why the following is public, + * see explanation in safe_mode_iterator notes in safe_mode.hpp. + */ + + BOOST_SERIALIZATION_SPLIT_MEMBER() + + typedef typename Node::base_type node_base_type; + + template<class Archive> + void save(Archive& ar,const unsigned int)const + { + node_base_type* bnode=node; + ar<<serialization::make_nvp("pointer",bnode); + } + + template<class Archive> + void load(Archive& ar,const unsigned int) + { + node_base_type* bnode; + ar>>serialization::make_nvp("pointer",bnode); + node=static_cast<Node*>(bnode); + } +#endif + + /* get_node is not to be used by the user */ + + typedef Node node_type; + + Node* get_node()const{return node;} + +private: + Node* node; +}; + +template<typename Node> +bool operator==( + const bidir_node_iterator<Node>& x, + const bidir_node_iterator<Node>& y) +{ + return x.get_node()==y.get_node(); +} + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/converter.hpp b/3rdParty/Boost/src/boost/multi_index/detail/converter.hpp new file mode 100644 index 0000000..a46cff6 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/converter.hpp @@ -0,0 +1,52 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_CONVERTER_HPP +#define BOOST_MULTI_INDEX_DETAIL_CONVERTER_HPP + +#if defined(_MSC_VER)&&(_MSC_VER>=1200) +#pragma once +#endif + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* converter offers means to access indices of a given multi_index_container + * and for convertibilty between index iterators, so providing a + * localized access point for get() and project() functions. + */ + +template<typename MultiIndexContainer,typename Index> +struct converter +{ + static const Index& index(const MultiIndexContainer& x){return x;} + static Index& index(MultiIndexContainer& x){return x;} + + static typename Index::const_iterator const_iterator( + const MultiIndexContainer& x,typename MultiIndexContainer::node_type* node) + { + return x.Index::make_iterator(node); + } + + static typename Index::iterator iterator( + MultiIndexContainer& x,typename MultiIndexContainer::node_type* node) + { + return x.Index::make_iterator(node); + } +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/copy_map.hpp b/3rdParty/Boost/src/boost/multi_index/detail/copy_map.hpp new file mode 100644 index 0000000..4279a8d --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/copy_map.hpp @@ -0,0 +1,140 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_COPY_MAP_HPP +#define BOOST_MULTI_INDEX_DETAIL_COPY_MAP_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/detail/no_exceptions_support.hpp> +#include <boost/multi_index/detail/auto_space.hpp> +#include <boost/multi_index/detail/prevent_eti.hpp> +#include <boost/noncopyable.hpp> +#include <cstddef> +#include <functional> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* copy_map is used as an auxiliary structure during copy_() operations. + * When a container with n nodes is replicated, node_map holds the pairings + * between original and copied nodes, and provides a fast way to find a + * copied node from an original one. + * The semantics of the class are not simple, and no attempt has been made + * to enforce it: multi_index_container handles it right. On the other hand, + * the const interface, which is the one provided to index implementations, + * only allows for: + * - Enumeration of pairs of (original,copied) nodes (excluding the headers), + * - fast retrieval of copied nodes (including the headers.) + */ + +template <typename Node> +struct copy_map_entry +{ + copy_map_entry(Node* f,Node* s):first(f),second(s){} + + Node* first; + Node* second; + + bool operator<(const copy_map_entry<Node>& x)const + { + return std::less<Node*>()(first,x.first); + } +}; + +template <typename Node,typename Allocator> +class copy_map:private noncopyable +{ +public: + typedef const copy_map_entry<Node>* const_iterator; + + copy_map( + const Allocator& al,std::size_t size,Node* header_org,Node* header_cpy): + al_(al),size_(size),spc(al_,size_),n(0), + header_org_(header_org),header_cpy_(header_cpy),released(false) + {} + + ~copy_map() + { + if(!released){ + for(std::size_t i=0;i<n;++i){ + boost::detail::allocator::destroy(&(spc.data()+i)->second->value()); + deallocate((spc.data()+i)->second); + } + } + } + + const_iterator begin()const{return &*spc.data();} + const_iterator end()const{return &*(spc.data()+n);} + + void clone(Node* node) + { + (spc.data()+n)->first=node; + (spc.data()+n)->second=&*al_.allocate(1); + BOOST_TRY{ + boost::detail::allocator::construct( + &(spc.data()+n)->second->value(),node->value()); + } + BOOST_CATCH(...){ + deallocate((spc.data()+n)->second); + BOOST_RETHROW; + } + BOOST_CATCH_END + ++n; + + if(n==size_)std::sort(&*spc.data(),&*spc.data()+size_); + } + + Node* find(Node* node)const + { + if(node==header_org_)return header_cpy_; + return std::lower_bound( + begin(),end(),copy_map_entry<Node>(node,0))->second; + } + + void release() + { + released=true; + } + +private: + typedef typename prevent_eti< + Allocator, + typename boost::detail::allocator::rebind_to< + Allocator,Node>::type + >::type allocator_type; + typedef typename allocator_type::pointer allocator_pointer; + + allocator_type al_; + std::size_t size_; + auto_space<copy_map_entry<Node>,Allocator> spc; + std::size_t n; + Node* header_org_; + Node* header_cpy_; + bool released; + + void deallocate(Node* node) + { + al_.deallocate(static_cast<allocator_pointer>(node),1); + } +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/duplicates_iterator.hpp b/3rdParty/Boost/src/boost/multi_index/detail/duplicates_iterator.hpp new file mode 100644 index 0000000..027dabd --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/duplicates_iterator.hpp @@ -0,0 +1,120 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_DUPLICATES_ITERATOR_HPP +#define BOOST_MULTI_INDEX_DETAIL_DUPLICATES_ITERATOR_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 <iterator> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* duplicates_operator is given a range of ordered elements and + * passes only over those which are duplicated. + */ + +template<typename Node,typename Predicate> +class duplicates_iterator +{ +public: + typedef typename Node::value_type value_type; + typedef std::ptrdiff_t difference_type; + typedef const typename Node::value_type* pointer; + typedef const typename Node::value_type& reference; + typedef std::forward_iterator_tag iterator_category; + + duplicates_iterator(Node* node_,Node* end_,Predicate pred_): + node(node_),begin_chunk(0),end(end_),pred(pred_) + { + advance(); + } + + duplicates_iterator(Node* end_,Predicate pred_): + node(end_),begin_chunk(end_),end(end_),pred(pred_) + { + } + + reference operator*()const + { + return node->value(); + } + + pointer operator->()const + { + return &node->value(); + } + + duplicates_iterator& operator++() + { + Node::increment(node); + sync(); + return *this; + } + + duplicates_iterator operator++(int) + { + duplicates_iterator tmp(*this); + ++(*this); + return tmp; + } + + Node* get_node()const{return node;} + +private: + void sync() + { + if(node!=end&&pred(begin_chunk->value(),node->value()))advance(); + } + + void advance() + { + for(Node* node2=node;node!=end;node=node2){ + Node::increment(node2); + if(node2!=end&&!pred(node->value(),node2->value()))break; + } + begin_chunk=node; + } + + Node* node; + Node* begin_chunk; + Node* end; + Predicate pred; +}; + +template<typename Node,typename Predicate> +bool operator==( + const duplicates_iterator<Node,Predicate>& x, + const duplicates_iterator<Node,Predicate>& y) +{ + return x.get_node()==y.get_node(); +} + +template<typename Node,typename Predicate> +bool operator!=( + const duplicates_iterator<Node,Predicate>& x, + const duplicates_iterator<Node,Predicate>& y) +{ + return !(x==y); +} + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/has_tag.hpp b/3rdParty/Boost/src/boost/multi_index/detail/has_tag.hpp new file mode 100644 index 0000000..83b28cc --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/has_tag.hpp @@ -0,0 +1,42 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_HAS_TAG_HPP +#define BOOST_MULTI_INDEX_DETAIL_HAS_TAG_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 <boost/mpl/contains.hpp> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* determines whether an index type has a given tag in its tag list */ + +template<typename Tag> +struct has_tag +{ + template<typename Index> + struct apply:mpl::contains<BOOST_DEDUCED_TYPENAME Index::tag_list,Tag> + { + }; +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/header_holder.hpp b/3rdParty/Boost/src/boost/multi_index/detail/header_holder.hpp new file mode 100644 index 0000000..8716e83 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/header_holder.hpp @@ -0,0 +1,50 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_HEADER_HOLDER_HPP +#define BOOST_MULTI_INDEX_DETAIL_HEADER_HOLDER_HPP + +#if defined(_MSC_VER)&&(_MSC_VER>=1200) +#pragma once +#endif + +#include <boost/noncopyable.hpp> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* A utility class used to hold a pointer to the header node. + * The base from member idiom is used because index classes, which are + * superclasses of multi_index_container, need this header in construction + * time. The allocation is made by the allocator of the multi_index_container + * class --hence, this allocator needs also be stored resorting + * to the base from member trick. + */ + +template<typename NodeTypePtr,typename Final> +struct header_holder:private noncopyable +{ + header_holder():member(final().allocate_node()){} + ~header_holder(){final().deallocate_node(&*member);} + + NodeTypePtr member; + +private: + Final& final(){return *static_cast<Final*>(this);} +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/index_base.hpp b/3rdParty/Boost/src/boost/multi_index/detail/index_base.hpp new file mode 100644 index 0000000..9b73a4b --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/index_base.hpp @@ -0,0 +1,185 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_INDEX_BASE_HPP +#define BOOST_MULTI_INDEX_DETAIL_INDEX_BASE_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 <boost/call_traits.hpp> +#include <boost/detail/workaround.hpp> +#include <boost/mpl/vector.hpp> +#include <boost/multi_index/detail/copy_map.hpp> +#include <boost/multi_index/detail/node_type.hpp> +#include <boost/multi_index_container_fwd.hpp> +#include <boost/tuple/tuple.hpp> +#include <utility> + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) +#include <boost/multi_index/detail/index_loader.hpp> +#include <boost/multi_index/detail/index_saver.hpp> +#endif + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* The role of this class is threefold: + * - tops the linear hierarchy of indices. + * - terminates some cascading backbone function calls (insert_, etc.), + * - grants access to the backbone functions of the final + * multi_index_container class (for access restriction reasons, these + * cannot be called directly from the index classes.) + */ + +template<typename Value,typename IndexSpecifierList,typename Allocator> +class index_base +{ +protected: + typedef index_node_base<Value,Allocator> node_type; + typedef typename multi_index_node_type< + Value,IndexSpecifierList,Allocator>::type final_node_type; + typedef multi_index_container< + Value,IndexSpecifierList,Allocator> final_type; + typedef tuples::null_type ctor_args_list; + typedef typename + boost::detail::allocator::rebind_to< + Allocator, + typename Allocator::value_type>::type final_allocator_type; + typedef mpl::vector0<> index_type_list; + typedef mpl::vector0<> iterator_type_list; + typedef mpl::vector0<> const_iterator_type_list; + typedef copy_map< + final_node_type, + final_allocator_type> copy_map_type; + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) + typedef index_saver< + node_type, + final_allocator_type> index_saver_type; + typedef index_loader< + node_type, + final_node_type, + final_allocator_type> index_loader_type; +#endif + +private: + typedef typename call_traits<Value>::param_type value_param_type; + +protected: + explicit index_base(const ctor_args_list&,const Allocator&){} + + void copy_( + const index_base<Value,IndexSpecifierList,Allocator>&,const copy_map_type&) + {} + + node_type* insert_(value_param_type v,node_type* x) + { + boost::detail::allocator::construct(&x->value(),v); + return x; + } + + node_type* insert_(value_param_type v,node_type*,node_type* x) + { + boost::detail::allocator::construct(&x->value(),v); + return x; + } + + void erase_(node_type* x) + { + boost::detail::allocator::destroy(&x->value()); + } + + void delete_node_(node_type* x) + { + boost::detail::allocator::destroy(&x->value()); + } + + void clear_(){} + + void swap_(index_base<Value,IndexSpecifierList,Allocator>&){} + + bool replace_(value_param_type v,node_type* x) + { + x->value()=v; + return true; + } + + bool modify_(node_type*){return true;} + + bool modify_rollback_(node_type*){return true;} + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) + /* serialization */ + + template<typename Archive> + void save_(Archive&,const unsigned int,const index_saver_type&)const{} + + template<typename Archive> + void load_(Archive&,const unsigned int,const index_loader_type&){} +#endif + +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING) + /* invariant stuff */ + + bool invariant_()const{return true;} +#endif + + /* access to backbone memfuns of Final class */ + + final_type& final(){return *static_cast<final_type*>(this);} + const final_type& final()const{return *static_cast<const final_type*>(this);} + + final_node_type* final_header()const{return final().header();} + + bool final_empty_()const{return final().empty_();} + std::size_t final_size_()const{return final().size_();} + std::size_t final_max_size_()const{return final().max_size_();} + + std::pair<final_node_type*,bool> final_insert_(value_param_type x) + {return final().insert_(x);} + std::pair<final_node_type*,bool> final_insert_( + value_param_type x,final_node_type* position) + {return final().insert_(x,position);} + + void final_erase_(final_node_type* x){final().erase_(x);} + + void final_delete_node_(final_node_type* x){final().delete_node_(x);} + void final_delete_all_nodes_(){final().delete_all_nodes_();} + void final_clear_(){final().clear_();} + + void final_swap_(final_type& x){final().swap_(x);} + bool final_replace_( + value_param_type k,final_node_type* x) + {return final().replace_(k,x);} + + template<typename Modifier> + bool final_modify_(Modifier& mod,final_node_type* x) + {return final().modify_(mod,x);} + + template<typename Modifier,typename Rollback> + bool final_modify_(Modifier& mod,Rollback& back,final_node_type* x) + {return final().modify_(mod,back,x);} + +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING) + void final_check_invariant_()const{final().check_invariant_();} +#endif +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/index_loader.hpp b/3rdParty/Boost/src/boost/multi_index/detail/index_loader.hpp new file mode 100644 index 0000000..001c01b --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/index_loader.hpp @@ -0,0 +1,138 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_INDEX_LOADER_HPP +#define BOOST_MULTI_INDEX_DETAIL_INDEX_LOADER_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/archive/archive_exception.hpp> +#include <boost/noncopyable.hpp> +#include <boost/multi_index/detail/auto_space.hpp> +#include <boost/serialization/nvp.hpp> +#include <boost/throw_exception.hpp> +#include <cstddef> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* Counterpart of index_saver (check index_saver.hpp for serialization + * details.)* multi_index_container is in charge of supplying the info about + * the base sequence, and each index can subsequently load itself using the + * const interface of index_loader. + */ + +template<typename Node,typename FinalNode,typename Allocator> +class index_loader:private noncopyable +{ +public: + index_loader(const Allocator& al,std::size_t size): + spc(al,size),size_(size),n(0),sorted(false) + { + } + + template<class Archive> + void add(Node* node,Archive& ar,const unsigned int) + { + ar>>serialization::make_nvp("position",*node); + entries()[n++]=node; + } + + template<class Archive> + void add_track(Node* node,Archive& ar,const unsigned int) + { + ar>>serialization::make_nvp("position",*node); + } + + /* A rearranger is passed two nodes, and is expected to + * reposition the second after the first. + * If the first node is 0, then the second should be moved + * to the beginning of the sequence. + */ + + template<typename Rearranger,class Archive> + void load(Rearranger r,Archive& ar,const unsigned int)const + { + FinalNode* prev=unchecked_load_node(ar); + if(!prev)return; + + if(!sorted){ + std::sort(entries(),entries()+size_); + sorted=true; + } + + check_node(prev); + + for(;;){ + for(;;){ + FinalNode* node=load_node(ar); + if(!node)break; + + if(node==prev)prev=0; + r(prev,node); + + prev=node; + } + prev=load_node(ar); + if(!prev)break; + } + } + +private: + Node** entries()const{return &*spc.data();} + + /* We try to delay sorting as much as possible just in case it + * is not necessary, hence this version of load_node. + */ + + template<class Archive> + FinalNode* unchecked_load_node(Archive& ar)const + { + Node* node=0; + ar>>serialization::make_nvp("pointer",node); + return static_cast<FinalNode*>(node); + } + + template<class Archive> + FinalNode* load_node(Archive& ar)const + { + Node* node=0; + ar>>serialization::make_nvp("pointer",node); + check_node(node); + return static_cast<FinalNode*>(node); + } + + void check_node(Node* node)const + { + if(node!=0&&!std::binary_search(entries(),entries()+size_,node)){ + throw_exception( + archive::archive_exception( + archive::archive_exception::other_exception)); + } + } + + auto_space<Node*,Allocator> spc; + std::size_t size_; + std::size_t n; + mutable bool sorted; +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/index_matcher.hpp b/3rdParty/Boost/src/boost/multi_index/detail/index_matcher.hpp new file mode 100644 index 0000000..5828137 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/index_matcher.hpp @@ -0,0 +1,248 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_INDEX_MATCHER_HPP +#define BOOST_MULTI_INDEX_DETAIL_INDEX_MATCHER_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/noncopyable.hpp> +#include <boost/multi_index/detail/auto_space.hpp> +#include <cstddef> +#include <functional> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* index_matcher compares a sequence of elements against a + * base sequence, identifying those elements that belong to the + * longest subsequence which is ordered with respect to the base. + * For instance, if the base sequence is: + * + * 0 1 2 3 4 5 6 7 8 9 + * + * and the compared sequence (not necesarilly the same length): + * + * 1 4 2 3 0 7 8 9 + * + * the elements of the longest ordered subsequence are: + * + * 1 2 3 7 8 9 + * + * The algorithm for obtaining such a subsequence is called + * Patience Sorting, described in ch. 1 of: + * Aldous, D., Diaconis, P.: "Longest increasing subsequences: from + * patience sorting to the Baik-Deift-Johansson Theorem", Bulletin + * of the American Mathematical Society, vol. 36, no 4, pp. 413-432, + * July 1999. + * http://www.ams.org/bull/1999-36-04/S0273-0979-99-00796-X/ + * S0273-0979-99-00796-X.pdf + * + * This implementation is not fully generic since it assumes that + * the sequences given are pointed to by index iterators (having a + * get_node() memfun.) + */ + +namespace index_matcher{ + +/* The algorithm stores the nodes of the base sequence and a number + * of "piles" that are dynamically updated during the calculation + * stage. From a logical point of view, nodes form an independent + * sequence from piles. They are stored together so as to minimize + * allocated memory. + */ + +struct entry +{ + entry(void* node_,std::size_t pos_=0):node(node_),pos(pos_){} + + /* node stuff */ + + void* node; + std::size_t pos; + entry* previous; + bool ordered; + + struct less_by_node + { + bool operator()( + const entry& x,const entry& y)const + { + return std::less<void*>()(x.node,y.node); + } + }; + + /* pile stuff */ + + std::size_t pile_top; + entry* pile_top_entry; + + struct less_by_pile_top + { + bool operator()( + const entry& x,const entry& y)const + { + return x.pile_top<y.pile_top; + } + }; +}; + +/* common code operating on void *'s */ + +template<typename Allocator> +class algorithm_base:private noncopyable +{ +protected: + algorithm_base(const Allocator& al,std::size_t size): + spc(al,size),size_(size),n(0),sorted(false) + { + } + + void add(void* node) + { + entries()[n]=entry(node,n); + ++n; + } + + void begin_algorithm()const + { + if(!sorted){ + std::sort(entries(),entries()+size_,entry::less_by_node()); + sorted=true; + } + num_piles=0; + } + + void add_node_to_algorithm(void* node)const + { + entry* ent= + std::lower_bound( + entries(),entries()+size_, + entry(node),entry::less_by_node()); /* localize entry */ + ent->ordered=false; + std::size_t n=ent->pos; /* get its position */ + + entry dummy(0); + dummy.pile_top=n; + + entry* pile_ent= /* find the first available pile */ + std::lower_bound( /* to stack the entry */ + entries(),entries()+num_piles, + dummy,entry::less_by_pile_top()); + + pile_ent->pile_top=n; /* stack the entry */ + pile_ent->pile_top_entry=ent; + + /* if not the first pile, link entry to top of the preceding pile */ + if(pile_ent>&entries()[0]){ + ent->previous=(pile_ent-1)->pile_top_entry; + } + + if(pile_ent==&entries()[num_piles]){ /* new pile? */ + ++num_piles; + } + } + + void finish_algorithm()const + { + if(num_piles>0){ + /* Mark those elements which are in their correct position, i.e. those + * belonging to the longest increasing subsequence. These are those + * elements linked from the top of the last pile. + */ + + entry* ent=entries()[num_piles-1].pile_top_entry; + for(std::size_t n=num_piles;n--;){ + ent->ordered=true; + ent=ent->previous; + } + } + } + + bool is_ordered(void * node)const + { + return std::lower_bound( + entries(),entries()+size_, + entry(node),entry::less_by_node())->ordered; + } + +private: + entry* entries()const{return &*spc.data();} + + auto_space<entry,Allocator> spc; + std::size_t size_; + std::size_t n; + mutable bool sorted; + mutable std::size_t num_piles; +}; + +/* The algorithm has three phases: + * - Initialization, during which the nodes of the base sequence are added. + * - Execution. + * - Results querying, through the is_ordered memfun. + */ + +template<typename Node,typename Allocator> +class algorithm:private algorithm_base<Allocator> +{ + typedef algorithm_base<Allocator> super; + +public: + algorithm(const Allocator& al,std::size_t size):super(al,size){} + + void add(Node* node) + { + super::add(node); + } + + template<typename IndexIterator> + void execute(IndexIterator first,IndexIterator last)const + { + super::begin_algorithm(); + + for(IndexIterator it=first;it!=last;++it){ + add_node_to_algorithm(get_node(it)); + } + + super::finish_algorithm(); + } + + bool is_ordered(Node* node)const + { + return super::is_ordered(node); + } + +private: + void add_node_to_algorithm(Node* node)const + { + super::add_node_to_algorithm(node); + } + + template<typename IndexIterator> + static Node* get_node(IndexIterator it) + { + return static_cast<Node*>(it.get_node()); + } +}; + +} /* namespace multi_index::detail::index_matcher */ + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/index_node_base.hpp b/3rdParty/Boost/src/boost/multi_index/detail/index_node_base.hpp new file mode 100644 index 0000000..ee9f1c6 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/index_node_base.hpp @@ -0,0 +1,135 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_INDEX_NODE_BASE_HPP +#define BOOST_MULTI_INDEX_DETAIL_INDEX_NODE_BASE_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 <boost/type_traits/aligned_storage.hpp> +#include <boost/type_traits/alignment_of.hpp> + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) +#include <boost/archive/archive_exception.hpp> +#include <boost/serialization/access.hpp> +#include <boost/throw_exception.hpp> +#endif + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* index_node_base tops the node hierarchy of multi_index_container. It holds + * the value of the element contained. + */ + +template<typename Value> +struct pod_value_holder +{ + typename aligned_storage< + sizeof(Value), + alignment_of<Value>::value + >::type space; +}; + +template<typename Value,typename Allocator> +struct index_node_base:private pod_value_holder<Value> +{ + typedef index_node_base base_type; /* used for serialization purposes */ + typedef Value value_type; + typedef Allocator allocator_type; + + value_type& value() + { + return *static_cast<value_type*>( + static_cast<void*>(&this->space)); + } + + const value_type& value()const + { + return *static_cast<const value_type*>( + static_cast<const void*>(&this->space)); + } + + static index_node_base* from_value(const value_type* p) + { + return static_cast<index_node_base *>( + reinterpret_cast<pod_value_holder<Value>*>( /* std 9.2.17 */ + const_cast<value_type*>(p))); + } + +private: +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) + friend class boost::serialization::access; + + /* nodes do not emit any kind of serialization info. They are + * fed to Boost.Serialization so that pointers to nodes are + * tracked correctly. + */ + + template<class Archive> + void serialize(Archive&,const unsigned int) + { + } +#endif +}; + +template<typename Node,typename Value> +Node* node_from_value( + const Value* p + BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Node)) +{ + typedef typename Node::allocator_type allocator_type; + return static_cast<Node*>( + index_node_base<Value,allocator_type>::from_value(p)); +} + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) +/* Index nodes never get constructed directly by Boost.Serialization, + * as archives are always fed pointers to previously existent + * nodes. So, if this is called it means we are dealing with a + * somehow invalid archive. + */ + +#if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP) +namespace serialization{ +#else +namespace multi_index{ +namespace detail{ +#endif + +template<class Archive,typename Value,typename Allocator> +inline void load_construct_data( + Archive&,boost::multi_index::detail::index_node_base<Value,Allocator>*, + const unsigned int) +{ + throw_exception( + archive::archive_exception(archive::archive_exception::other_exception)); +} + +#if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP) +} /* namespace serialization */ +#else +} /* namespace multi_index::detail */ +} /* namespace multi_index */ +#endif + +#endif + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/index_saver.hpp b/3rdParty/Boost/src/boost/multi_index/detail/index_saver.hpp new file mode 100644 index 0000000..d9e6bc7 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/index_saver.hpp @@ -0,0 +1,135 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_INDEX_SAVER_HPP +#define BOOST_MULTI_INDEX_DETAIL_INDEX_SAVER_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 <boost/multi_index/detail/index_matcher.hpp> +#include <boost/noncopyable.hpp> +#include <boost/serialization/nvp.hpp> +#include <cstddef> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* index_saver accepts a base sequence of previously saved elements + * and saves a possibly reordered subsequence in an efficient manner, + * serializing only the information needed to rearrange the subsequence + * based on the original order of the base. + * multi_index_container is in charge of supplying the info about the + * base sequence, and each index can subsequently save itself using the + * const interface of index_saver. + */ + +template<typename Node,typename Allocator> +class index_saver:private noncopyable +{ +public: + index_saver(const Allocator& al,std::size_t size):alg(al,size){} + + template<class Archive> + void add(Node* node,Archive& ar,const unsigned int) + { + ar<<serialization::make_nvp("position",*node); + alg.add(node); + } + + template<class Archive> + void add_track(Node* node,Archive& ar,const unsigned int) + { + ar<<serialization::make_nvp("position",*node); + } + + template<typename IndexIterator,class Archive> + void save( + IndexIterator first,IndexIterator last,Archive& ar, + const unsigned int)const + { + /* calculate ordered positions */ + + alg.execute(first,last); + + /* Given a consecutive subsequence of displaced elements + * x1,...,xn, the following information is serialized: + * + * p0,p1,...,pn,0 + * + * where pi is a pointer to xi and p0 is a pointer to the element + * preceding x1. Crealy, from this information is possible to + * restore the original order on loading time. If x1 is the first + * element in the sequence, the following is serialized instead: + * + * p1,p1,...,pn,0 + * + * For each subsequence of n elements, n+2 pointers are serialized. + * An optimization policy is applied: consider for instance the + * sequence + * + * a,B,c,D + * + * where B and D are displaced, but c is in its correct position. + * Applying the schema described above we would serialize 6 pointers: + * + * p(a),p(B),0 + * p(c),p(D),0 + * + * but this can be reduced to 5 pointers by treating c as a displaced + * element: + * + * p(a),p(B),p(c),p(D),0 + */ + + std::size_t last_saved=3; /* distance to last pointer saved */ + for(IndexIterator it=first,prev=first;it!=last;prev=it++,++last_saved){ + if(!alg.is_ordered(get_node(it))){ + if(last_saved>1)save_node(get_node(prev),ar); + save_node(get_node(it),ar); + last_saved=0; + } + else if(last_saved==2)save_node(null_node(),ar); + } + if(last_saved<=2)save_node(null_node(),ar); + + /* marks the end of the serialization info for [first,last) */ + + save_node(null_node(),ar); + } + +private: + template<typename IndexIterator> + static Node* get_node(IndexIterator it) + { + return it.get_node(); + } + + static Node* null_node(){return 0;} + + template<typename Archive> + static void save_node(Node* node,Archive& ar) + { + ar<<serialization::make_nvp("pointer",node); + } + + index_matcher::algorithm<Node,Allocator> alg; +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/invariant_assert.hpp b/3rdParty/Boost/src/boost/multi_index/detail/invariant_assert.hpp new file mode 100644 index 0000000..d5fc256 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/invariant_assert.hpp @@ -0,0 +1,21 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_INVARIANT_ASSERT_HPP +#define BOOST_MULTI_INDEX_DETAIL_INVARIANT_ASSERT_HPP + +#if defined(_MSC_VER)&&(_MSC_VER>=1200) +#pragma once +#endif + +#if !defined(BOOST_MULTI_INDEX_INVARIANT_ASSERT) +#include <boost/assert.hpp> +#define BOOST_MULTI_INDEX_INVARIANT_ASSERT BOOST_ASSERT +#endif + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/is_index_list.hpp b/3rdParty/Boost/src/boost/multi_index/detail/is_index_list.hpp new file mode 100644 index 0000000..9ee30ba --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/is_index_list.hpp @@ -0,0 +1,40 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_IS_INDEX_LIST_HPP +#define BOOST_MULTI_INDEX_DETAIL_IS_INDEX_LIST_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 <boost/mpl/empty.hpp> +#include <boost/mpl/is_sequence.hpp> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +template<typename T> +struct is_index_list +{ + BOOST_STATIC_CONSTANT(bool,mpl_sequence=mpl::is_sequence<T>::value); + BOOST_STATIC_CONSTANT(bool,non_empty=!mpl::empty<T>::value); + BOOST_STATIC_CONSTANT(bool,value=mpl_sequence&&non_empty); +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/iter_adaptor.hpp b/3rdParty/Boost/src/boost/multi_index/detail/iter_adaptor.hpp new file mode 100644 index 0000000..0346184 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/iter_adaptor.hpp @@ -0,0 +1,325 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_ITER_ADAPTOR_HPP +#define BOOST_MULTI_INDEX_DETAIL_ITER_ADAPTOR_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 <boost/mpl/apply.hpp> +#include <boost/multi_index/detail/prevent_eti.hpp> +#include <boost/operators.hpp> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* Poor man's version of boost::iterator_adaptor. Used instead of the + * original as compile times for the latter are significantly higher. + * The interface is not replicated exactly, only to the extent necessary + * for internal consumption. + */ + +/* NB. The purpose of the (non-inclass) global operators ==, < and - defined + * above is to partially alleviate a problem of MSVC++ 6.0 by * which + * friend-injected operators on T are not visible if T is instantiated only + * in template code where T is a dependent type. + */ + +class iter_adaptor_access +{ +public: + template<class Class> + static typename Class::reference dereference(const Class& x) + { + return x.dereference(); + } + + template<class Class> + static bool equal(const Class& x,const Class& y) + { + return x.equal(y); + } + + template<class Class> + static void increment(Class& x) + { + x.increment(); + } + + template<class Class> + static void decrement(Class& x) + { + x.decrement(); + } + + template<class Class> + static void advance(Class& x,typename Class::difference_type n) + { + x.advance(n); + } + + template<class Class> + static typename Class::difference_type distance_to( + const Class& x,const Class& y) + { + return x.distance_to(y); + } +}; + +template<typename Category> +struct iter_adaptor_selector; + +template<class Derived,class Base> +class forward_iter_adaptor_base: + public forward_iterator_helper< + Derived, + typename Base::value_type, + typename Base::difference_type, + typename Base::pointer, + typename Base::reference> +{ +public: + typedef typename Base::reference reference; + + reference operator*()const + { + return iter_adaptor_access::dereference(final()); + } + + friend bool operator==(const Derived& x,const Derived& y) + { + return iter_adaptor_access::equal(x,y); + } + + Derived& operator++() + { + iter_adaptor_access::increment(final()); + return final(); + } + +private: + Derived& final(){return *static_cast<Derived*>(this);} + const Derived& final()const{return *static_cast<const Derived*>(this);} +}; + +template<class Derived,class Base> +bool operator==( + const forward_iter_adaptor_base<Derived,Base>& x, + const forward_iter_adaptor_base<Derived,Base>& y) +{ + return iter_adaptor_access::equal( + static_cast<const Derived&>(x),static_cast<const Derived&>(y)); +} + +template<> +struct iter_adaptor_selector<std::forward_iterator_tag> +{ + template<class Derived,class Base> + struct apply + { + typedef forward_iter_adaptor_base<Derived,Base> type; + }; +}; + +template<class Derived,class Base> +class bidirectional_iter_adaptor_base: + public bidirectional_iterator_helper< + Derived, + typename Base::value_type, + typename Base::difference_type, + typename Base::pointer, + typename Base::reference> +{ +public: + typedef typename Base::reference reference; + + reference operator*()const + { + return iter_adaptor_access::dereference(final()); + } + + friend bool operator==(const Derived& x,const Derived& y) + { + return iter_adaptor_access::equal(x,y); + } + + Derived& operator++() + { + iter_adaptor_access::increment(final()); + return final(); + } + + Derived& operator--() + { + iter_adaptor_access::decrement(final()); + return final(); + } + +private: + Derived& final(){return *static_cast<Derived*>(this);} + const Derived& final()const{return *static_cast<const Derived*>(this);} +}; + +template<class Derived,class Base> +bool operator==( + const bidirectional_iter_adaptor_base<Derived,Base>& x, + const bidirectional_iter_adaptor_base<Derived,Base>& y) +{ + return iter_adaptor_access::equal( + static_cast<const Derived&>(x),static_cast<const Derived&>(y)); +} + +template<> +struct iter_adaptor_selector<std::bidirectional_iterator_tag> +{ + template<class Derived,class Base> + struct apply + { + typedef bidirectional_iter_adaptor_base<Derived,Base> type; + }; +}; + +template<class Derived,class Base> +class random_access_iter_adaptor_base: + public random_access_iterator_helper< + Derived, + typename Base::value_type, + typename Base::difference_type, + typename Base::pointer, + typename Base::reference> +{ +public: + typedef typename Base::reference reference; + typedef typename Base::difference_type difference_type; + + reference operator*()const + { + return iter_adaptor_access::dereference(final()); + } + + friend bool operator==(const Derived& x,const Derived& y) + { + return iter_adaptor_access::equal(x,y); + } + + friend bool operator<(const Derived& x,const Derived& y) + { + return iter_adaptor_access::distance_to(x,y)>0; + } + + Derived& operator++() + { + iter_adaptor_access::increment(final()); + return final(); + } + + Derived& operator--() + { + iter_adaptor_access::decrement(final()); + return final(); + } + + Derived& operator+=(difference_type n) + { + iter_adaptor_access::advance(final(),n); + return final(); + } + + Derived& operator-=(difference_type n) + { + iter_adaptor_access::advance(final(),-n); + return final(); + } + + friend difference_type operator-(const Derived& x,const Derived& y) + { + return iter_adaptor_access::distance_to(y,x); + } + +private: + Derived& final(){return *static_cast<Derived*>(this);} + const Derived& final()const{return *static_cast<const Derived*>(this);} +}; + +template<class Derived,class Base> +bool operator==( + const random_access_iter_adaptor_base<Derived,Base>& x, + const random_access_iter_adaptor_base<Derived,Base>& y) +{ + return iter_adaptor_access::equal( + static_cast<const Derived&>(x),static_cast<const Derived&>(y)); +} + +template<class Derived,class Base> +bool operator<( + const random_access_iter_adaptor_base<Derived,Base>& x, + const random_access_iter_adaptor_base<Derived,Base>& y) +{ + return iter_adaptor_access::distance_to( + static_cast<const Derived&>(x),static_cast<const Derived&>(y))>0; +} + +template<class Derived,class Base> +typename random_access_iter_adaptor_base<Derived,Base>::difference_type +operator-( + const random_access_iter_adaptor_base<Derived,Base>& x, + const random_access_iter_adaptor_base<Derived,Base>& y) +{ + return iter_adaptor_access::distance_to( + static_cast<const Derived&>(y),static_cast<const Derived&>(x)); +} + +template<> +struct iter_adaptor_selector<std::random_access_iterator_tag> +{ + template<class Derived,class Base> + struct apply + { + typedef random_access_iter_adaptor_base<Derived,Base> type; + }; +}; + +template<class Derived,class Base> +struct iter_adaptor_base +{ + typedef iter_adaptor_selector< + typename Base::iterator_category> selector; + typedef typename prevent_eti< + selector, + typename mpl::apply2< + selector,Derived,Base>::type + >::type type; +}; + +template<class Derived,class Base> +class iter_adaptor:public iter_adaptor_base<Derived,Base>::type +{ +protected: + iter_adaptor(){} + explicit iter_adaptor(const Base& b_):b(b_){} + + const Base& base_reference()const{return b;} + Base& base_reference(){return b;} + +private: + Base b; +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/modify_key_adaptor.hpp b/3rdParty/Boost/src/boost/multi_index/detail/modify_key_adaptor.hpp new file mode 100644 index 0000000..8a93b96 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/modify_key_adaptor.hpp @@ -0,0 +1,49 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_MODIFY_KEY_ADAPTOR_HPP +#define BOOST_MULTI_INDEX_DETAIL_MODIFY_KEY_ADAPTOR_HPP + +#if defined(_MSC_VER)&&(_MSC_VER>=1200) +#pragma once +#endif + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* Functional adaptor to resolve modify_key as a call to modify. + * Preferred over compose_f_gx and stuff cause it eliminates problems + * with references to references, dealing with function pointers, etc. + */ + +template<typename Fun,typename Value,typename KeyFromValue> +struct modify_key_adaptor +{ + + modify_key_adaptor(Fun f_,KeyFromValue kfv_):f(f_),kfv(kfv_){} + + void operator()(Value& x) + { + f(kfv(x)); + } + +private: + Fun f; + KeyFromValue kfv; +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/msvc_index_specifier.hpp b/3rdParty/Boost/src/boost/multi_index/detail/msvc_index_specifier.hpp new file mode 100644 index 0000000..4766e53 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/msvc_index_specifier.hpp @@ -0,0 +1,69 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_MSVC_INDEX_SPECIFIER_HPP +#define BOOST_MULTI_INDEX_DETAIL_MSVC_INDEX_SPECIFIER_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 <boost/detail/workaround.hpp> + +#if BOOST_WORKAROUND(BOOST_MSVC,<1310) +/* Workaround for a problem in MSVC with dependent template typedefs + * when accesing index specifiers. + * Modeled after <boost/mpl/aux_/msvc_dtw.hpp> (thanks, Aleksey!) + */ + +#include <boost/mpl/aux_/msvc_never_true.hpp> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +template<typename IndexSpecifier> +struct msvc_index_specifier +{ + template<bool> struct fake_index_type:IndexSpecifier{}; + template<> struct fake_index_type<true> + { + template<typename Super> + struct node_class{}; + + template<typename Super> + struct index_class{}; + }; + + template<typename Super> + struct result_node_class: + fake_index_type<mpl::aux::msvc_never_true<IndexSpecifier>::value>:: + template node_class<Super> + { + }; + + template<typename Super> + struct result_index_class: + fake_index_type<mpl::aux::msvc_never_true<IndexSpecifier>::value>:: + template index_class<Super> + { + }; +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif /* workaround */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/no_duplicate_tags.hpp b/3rdParty/Boost/src/boost/multi_index/detail/no_duplicate_tags.hpp new file mode 100644 index 0000000..9b56e83 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/no_duplicate_tags.hpp @@ -0,0 +1,97 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_NO_DUPLICATE_TAGS_HPP +#define BOOST_MULTI_INDEX_DETAIL_NO_DUPLICATE_TAGS_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 <boost/mpl/fold.hpp> +#include <boost/mpl/set/set0.hpp> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* no_duplicate_tags check at compile-time that a tag list + * has no duplicate tags. + * The algorithm deserves some explanation: tags + * are sequentially inserted into a mpl::set if they were + * not already present. Due to the magic of mpl::set + * (mpl::has_key is contant time), this operation takes linear + * time, and even MSVC++ 6.5 handles it gracefully (other obvious + * solutions are quadratic.) + */ + +struct duplicate_tag_mark{}; + +struct duplicate_tag_marker +{ + template <typename MplSet,typename Tag> + struct apply + { + typedef mpl::s_item< + typename mpl::if_<mpl::has_key<MplSet,Tag>,duplicate_tag_mark,Tag>::type, + MplSet + > type; + }; +}; + +template<typename TagList> +struct no_duplicate_tags +{ + typedef typename mpl::fold< + TagList, + mpl::set0<>, + duplicate_tag_marker + >::type aux; + + BOOST_STATIC_CONSTANT( + bool,value=!(mpl::has_key<aux,duplicate_tag_mark>::value)); +}; + +/* Variant for an index list: duplication is checked + * across all the indices. + */ + +struct duplicate_tag_list_marker +{ + template <typename MplSet,typename Index> + struct apply:mpl::fold< + BOOST_DEDUCED_TYPENAME Index::tag_list, + MplSet, + duplicate_tag_marker> + { + }; +}; + +template<typename IndexList> +struct no_duplicate_tags_in_index_list +{ + typedef typename mpl::fold< + IndexList, + mpl::set0<>, + duplicate_tag_list_marker + >::type aux; + + BOOST_STATIC_CONSTANT( + bool,value=!(mpl::has_key<aux,duplicate_tag_mark>::value)); +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/node_type.hpp b/3rdParty/Boost/src/boost/multi_index/detail/node_type.hpp new file mode 100644 index 0000000..0e87261 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/node_type.hpp @@ -0,0 +1,79 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_NODE_TYPE_HPP +#define BOOST_MULTI_INDEX_DETAIL_NODE_TYPE_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 <boost/detail/workaround.hpp> +#include <boost/mpl/bind.hpp> +#include <boost/mpl/reverse_iter_fold.hpp> +#include <boost/mpl/deref.hpp> +#include <boost/multi_index_container_fwd.hpp> +#include <boost/multi_index/detail/header_holder.hpp> +#include <boost/multi_index/detail/index_node_base.hpp> +#include <boost/multi_index/detail/is_index_list.hpp> +#include <boost/multi_index/detail/msvc_index_specifier.hpp> +#include <boost/static_assert.hpp> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* MPL machinery to construct the internal node type associated to an + * index list. + */ + +#if BOOST_WORKAROUND(BOOST_MSVC,<1310) +struct index_node_applier +{ + template<typename IndexSpecifierIterator,typename Super> + struct apply: + msvc_index_specifier< mpl::deref<IndexSpecifierIterator>::type >:: + template result_node_class<Super> + { + }; +}; +#else +struct index_node_applier +{ + template<typename IndexSpecifierIterator,typename Super> + struct apply + { + typedef typename mpl::deref<IndexSpecifierIterator>::type index_specifier; + typedef typename index_specifier:: + BOOST_NESTED_TEMPLATE node_class<Super>::type type; + }; +}; +#endif + +template<typename Value,typename IndexSpecifierList,typename Allocator> +struct multi_index_node_type +{ + BOOST_STATIC_ASSERT(detail::is_index_list<IndexSpecifierList>::value); + + typedef typename mpl::reverse_iter_fold< + IndexSpecifierList, + index_node_base<Value,Allocator>, + mpl::bind2<index_node_applier,mpl::_2,mpl::_1> + >::type type; +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/ord_index_args.hpp b/3rdParty/Boost/src/boost/multi_index/detail/ord_index_args.hpp new file mode 100644 index 0000000..bb8eb41 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/ord_index_args.hpp @@ -0,0 +1,83 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_ARGS_HPP +#define BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_ARGS_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 <boost/mpl/aux_/na.hpp> +#include <boost/mpl/eval_if.hpp> +#include <boost/mpl/identity.hpp> +#include <boost/mpl/if.hpp> +#include <boost/multi_index/tag.hpp> +#include <boost/static_assert.hpp> +#include <boost/type_traits/is_same.hpp> +#include <functional> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* Oredered index specifiers can be instantiated in two forms: + * + * (ordered_unique|ordered_non_unique)< + * KeyFromValue,Compare=std::less<KeyFromValue::result_type> > + * (ordered_unique|ordered_non_unique)< + * TagList,KeyFromValue,Compare=std::less<KeyFromValue::result_type> > + * + * index_args implements the machinery to accept this argument-dependent + * polymorphism. + */ + +template<typename KeyFromValue> +struct index_args_default_compare +{ + typedef std::less<typename KeyFromValue::result_type> type; +}; + +template<typename Arg1,typename Arg2,typename Arg3> +struct ordered_index_args +{ + typedef is_tag<Arg1> full_form; + + typedef typename mpl::if_< + full_form, + Arg1, + tag< > >::type tag_list_type; + typedef typename mpl::if_< + full_form, + Arg2, + Arg1>::type key_from_value_type; + typedef typename mpl::if_< + full_form, + Arg3, + Arg2>::type supplied_compare_type; + typedef typename mpl::eval_if< + mpl::is_na<supplied_compare_type>, + index_args_default_compare<key_from_value_type>, + mpl::identity<supplied_compare_type> + >::type compare_type; + + BOOST_STATIC_ASSERT(is_tag<tag_list_type>::value); + BOOST_STATIC_ASSERT(!mpl::is_na<key_from_value_type>::value); + BOOST_STATIC_ASSERT(!mpl::is_na<compare_type>::value); +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/ord_index_node.hpp b/3rdParty/Boost/src/boost/multi_index/detail/ord_index_node.hpp new file mode 100644 index 0000000..edc4329 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/ord_index_node.hpp @@ -0,0 +1,650 @@ +/* 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 diff --git a/3rdParty/Boost/src/boost/multi_index/detail/ord_index_ops.hpp b/3rdParty/Boost/src/boost/multi_index/detail/ord_index_ops.hpp new file mode 100644 index 0000000..caa71aa --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/ord_index_ops.hpp @@ -0,0 +1,147 @@ +/* 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_OPS_HPP +#define BOOST_MULTI_INDEX_DETAIL_ORD_INDEX_OPS_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 <utility> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* Common code for index memfuns having templatized and + * non-templatized versions. + */ + +template< + typename Node,typename KeyFromValue, + typename CompatibleKey,typename CompatibleCompare +> +inline Node* ordered_index_find( + Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x, + const CompatibleCompare& comp) +{ + Node* y0=y; + + while (top){ + if(!comp(key(top->value()),x)){ + y=top; + top=Node::from_impl(top->left()); + } + else top=Node::from_impl(top->right()); + } + + return (y==y0||comp(x,key(y->value())))?y0:y; +} + +template< + typename Node,typename KeyFromValue, + typename CompatibleKey,typename CompatibleCompare +> +inline Node* ordered_index_lower_bound( + Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x, + const CompatibleCompare& comp) +{ + while(top){ + if(!comp(key(top->value()),x)){ + y=top; + top=Node::from_impl(top->left()); + } + else top=Node::from_impl(top->right()); + } + + return y; +} + +template< + typename Node,typename KeyFromValue, + typename CompatibleKey,typename CompatibleCompare +> +inline Node* ordered_index_upper_bound( + Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x, + const CompatibleCompare& comp) +{ + while(top){ + if(comp(x,key(top->value()))){ + y=top; + top=Node::from_impl(top->left()); + } + else top=Node::from_impl(top->right()); + } + + return y; +} + +template< + typename Node,typename KeyFromValue, + typename CompatibleKey,typename CompatibleCompare +> +inline std::pair<Node*,Node*> ordered_index_equal_range( + Node* top,Node* y,const KeyFromValue& key,const CompatibleKey& x, + const CompatibleCompare& comp) +{ + while(top){ + if(comp(key(top->value()),x)){ + top=Node::from_impl(top->right()); + } + else if(comp(x,key(top->value()))){ + y=top; + top=Node::from_impl(top->left()); + } + else{ + return std::pair<Node*,Node*>( + ordered_index_lower_bound(Node::from_impl(top->left()),top,key,x,comp), + ordered_index_upper_bound(Node::from_impl(top->right()),y,key,x,comp)); + } + } + + return std::pair<Node*,Node*>(y,y); +} + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/prevent_eti.hpp b/3rdParty/Boost/src/boost/multi_index/detail/prevent_eti.hpp new file mode 100644 index 0000000..56c067a --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/prevent_eti.hpp @@ -0,0 +1,60 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_PREVENT_ETI_HPP +#define BOOST_MULTI_INDEX_DETAIL_PREVENT_ETI_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 <boost/detail/workaround.hpp> + +#if BOOST_WORKAROUND(BOOST_MSVC,<1300) +#include <boost/mpl/if.hpp> +#include <boost/mpl/integral_c.hpp> +#include <boost/mpl/aux_/msvc_never_true.hpp> +#endif + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +#if BOOST_WORKAROUND(BOOST_MSVC,<1300) +/* See + * http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?Effective_MPL + * Item 5.6, Beware of the 'early template instantiation' trap. + */ + +template<typename Type,typename Construct> +struct prevent_eti +{ + typedef typename mpl::if_< + mpl::aux::msvc_never_true<Type>, + mpl::integral_c<int,0>, + Construct + >::type type; +}; +#else +template<typename Type,typename Construct> +struct prevent_eti +{ + typedef Construct type; +}; +#endif + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/safe_ctr_proxy.hpp b/3rdParty/Boost/src/boost/multi_index/detail/safe_ctr_proxy.hpp new file mode 100644 index 0000000..c733f96 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/safe_ctr_proxy.hpp @@ -0,0 +1,105 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_SAFE_CTR_PROXY_HPP +#define BOOST_MULTI_INDEX_DETAIL_SAFE_CTR_PROXY_HPP + +#if defined(_MSC_VER)&&(_MSC_VER>=1200) +#pragma once +#endif + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) +#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ +#include <boost/detail/workaround.hpp> + +#if BOOST_WORKAROUND(BOOST_MSVC,<1300) +#include <boost/multi_index/detail/safe_mode.hpp> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* A safe iterator is instantiated in the form + * safe_iterator<Iterator,Container>: MSVC++ 6.0 has serious troubles with + * the resulting symbols names, given that index names (which stand for + * Container) are fairly long themselves. safe_ctr_proxy does not statically + * depend on Container, and provides the necessary methods (begin and end) to + * the safe mode framework via an abstract interface. With safe_ctr_proxy, + * instead of deriving from safe_container<Container> the following base class + * must be used: + * + * safe_ctr_proxy_impl<Iterator,Container> + * + * where Iterator is the type of the *unsafe* iterator being wrapped. + * The corresponding safe iterator instantiation is then + * + * safe_iterator<Iterator,safe_ctr_proxy<Iterator> >, + * + * which does not include the name of Container. + */ + +template<typename Iterator> +class safe_ctr_proxy: + public safe_mode::safe_container<safe_ctr_proxy<Iterator> > +{ +public: + typedef safe_mode::safe_iterator<Iterator,safe_ctr_proxy> iterator; + typedef iterator const_iterator; + + iterator begin(){return begin_impl();} + const_iterator begin()const{return begin_impl();} + iterator end(){return end_impl();} + const_iterator end()const{return end_impl();} + +protected: + virtual iterator begin_impl()=0; + virtual const_iterator begin_impl()const=0; + virtual iterator end_impl()=0; + virtual const_iterator end_impl()const=0; +}; + +template<typename Iterator,typename Container> +class safe_ctr_proxy_impl:public safe_ctr_proxy<Iterator> +{ + typedef safe_ctr_proxy<Iterator> super; + typedef Container container_type; + +public: + typedef typename super::iterator iterator; + typedef typename super::const_iterator const_iterator; + + virtual iterator begin_impl(){return container().begin();} + virtual const_iterator begin_impl()const{return container().begin();} + virtual iterator end_impl(){return container().end();} + virtual const_iterator end_impl()const{return container().end();} + +private: + container_type& container() + { + return *static_cast<container_type*>(this); + } + + const container_type& container()const + { + return *static_cast<const container_type*>(this); + } +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif /* workaround */ + +#endif /* BOOST_MULTI_INDEX_ENABLE_SAFE_MODE */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/safe_mode.hpp b/3rdParty/Boost/src/boost/multi_index/detail/safe_mode.hpp new file mode 100644 index 0000000..dbfebd8 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/safe_mode.hpp @@ -0,0 +1,574 @@ +/* Copyright 2003-2009 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_SAFE_MODE_HPP +#define BOOST_MULTI_INDEX_DETAIL_SAFE_MODE_HPP + +#if defined(_MSC_VER)&&(_MSC_VER>=1200) +#pragma once +#endif + +/* Safe mode machinery, in the spirit of Cay Hortmann's "Safe STL" + * (http://www.horstmann.com/safestl.html). + * In this mode, containers of type Container are derived from + * safe_container<Container>, and their corresponding iterators + * are wrapped with safe_iterator. These classes provide + * an internal record of which iterators are at a given moment associated + * to a given container, and properly mark the iterators as invalid + * when the container gets destroyed. + * Iterators are chained in a single attached list, whose header is + * kept by the container. More elaborate data structures would yield better + * performance, but I decided to keep complexity to a minimum since + * speed is not an issue here. + * Safe mode iterators automatically check that only proper operations + * are performed on them: for instance, an invalid iterator cannot be + * dereferenced. Additionally, a set of utilty macros and functions are + * provided that serve to implement preconditions and cooperate with + * the framework within the container. + * Iterators can also be unchecked, i.e. they do not have info about + * which container they belong in. This situation arises when the iterator + * is restored from a serialization archive: only information on the node + * is available, and it is not possible to determine to which container + * the iterator is associated to. The only sensible policy is to assume + * unchecked iterators are valid, though this can certainly generate false + * positive safe mode checks. + * This is not a full-fledged safe mode framework, and is only intended + * for use within the limits of Boost.MultiIndex. + */ + +/* Assertion macros. These resolve to no-ops if + * !defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE). + */ + +#if !defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) +#undef BOOST_MULTI_INDEX_SAFE_MODE_ASSERT +#define BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(expr,error_code) ((void)0) +#else +#if !defined(BOOST_MULTI_INDEX_SAFE_MODE_ASSERT) +#include <boost/assert.hpp> +#define BOOST_MULTI_INDEX_SAFE_MODE_ASSERT(expr,error_code) BOOST_ASSERT(expr) +#endif +#endif + +#define BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(it) \ + BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ + safe_mode::check_valid_iterator(it), \ + safe_mode::invalid_iterator); + +#define BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(it) \ + BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ + safe_mode::check_dereferenceable_iterator(it), \ + safe_mode::not_dereferenceable_iterator); + +#define BOOST_MULTI_INDEX_CHECK_INCREMENTABLE_ITERATOR(it) \ + BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ + safe_mode::check_incrementable_iterator(it), \ + safe_mode::not_incrementable_iterator); + +#define BOOST_MULTI_INDEX_CHECK_DECREMENTABLE_ITERATOR(it) \ + BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ + safe_mode::check_decrementable_iterator(it), \ + safe_mode::not_decrementable_iterator); + +#define BOOST_MULTI_INDEX_CHECK_IS_OWNER(it,cont) \ + BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ + safe_mode::check_is_owner(it,cont), \ + safe_mode::not_owner); + +#define BOOST_MULTI_INDEX_CHECK_SAME_OWNER(it0,it1) \ + BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ + safe_mode::check_same_owner(it0,it1), \ + safe_mode::not_same_owner); + +#define BOOST_MULTI_INDEX_CHECK_VALID_RANGE(it0,it1) \ + BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ + safe_mode::check_valid_range(it0,it1), \ + safe_mode::invalid_range); + +#define BOOST_MULTI_INDEX_CHECK_OUTSIDE_RANGE(it,it0,it1) \ + BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ + safe_mode::check_outside_range(it,it0,it1), \ + safe_mode::inside_range); + +#define BOOST_MULTI_INDEX_CHECK_IN_BOUNDS(it,n) \ + BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ + safe_mode::check_in_bounds(it,n), \ + safe_mode::out_of_bounds); + +#define BOOST_MULTI_INDEX_CHECK_DIFFERENT_CONTAINER(cont0,cont1) \ + BOOST_MULTI_INDEX_SAFE_MODE_ASSERT( \ + safe_mode::check_different_container(cont0,cont1), \ + safe_mode::same_container); + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) +#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ +#include <algorithm> +#include <boost/detail/iterator.hpp> +#include <boost/multi_index/detail/access_specifier.hpp> +#include <boost/multi_index/detail/iter_adaptor.hpp> +#include <boost/multi_index/safe_mode_errors.hpp> +#include <boost/noncopyable.hpp> + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) +#include <boost/serialization/split_member.hpp> +#endif + +#if defined(BOOST_HAS_THREADS) +#include <boost/detail/lightweight_mutex.hpp> +#endif + +namespace boost{ + +namespace multi_index{ + +namespace safe_mode{ + +/* Checking routines. Assume the best for unchecked iterators + * (i.e. they pass the checking when there is not enough info + * to know.) + */ + +template<typename Iterator> +inline bool check_valid_iterator(const Iterator& it) +{ + return it.valid()||it.unchecked(); +} + +template<typename Iterator> +inline bool check_dereferenceable_iterator(const Iterator& it) +{ + return it.valid()&&it!=it.owner()->end()||it.unchecked(); +} + +template<typename Iterator> +inline bool check_incrementable_iterator(const Iterator& it) +{ + return it.valid()&&it!=it.owner()->end()||it.unchecked(); +} + +template<typename Iterator> +inline bool check_decrementable_iterator(const Iterator& it) +{ + return it.valid()&&it!=it.owner()->begin()||it.unchecked(); +} + +template<typename Iterator> +inline bool check_is_owner( + const Iterator& it,const typename Iterator::container_type& cont) +{ + return it.valid()&&it.owner()==&cont||it.unchecked(); +} + +template<typename Iterator> +inline bool check_same_owner(const Iterator& it0,const Iterator& it1) +{ + return it0.valid()&&it1.valid()&&it0.owner()==it1.owner()|| + it0.unchecked()||it1.unchecked(); +} + +template<typename Iterator> +inline bool check_valid_range(const Iterator& it0,const Iterator& it1) +{ + if(!check_same_owner(it0,it1))return false; + + if(it0.valid()){ + Iterator last=it0.owner()->end(); + if(it1==last)return true; + + for(Iterator first=it0;first!=last;++first){ + if(first==it1)return true; + } + return false; + } + return true; +} + +template<typename Iterator> +inline bool check_outside_range( + const Iterator& it,const Iterator& it0,const Iterator& it1) +{ + if(!check_same_owner(it0,it1))return false; + + if(it0.valid()){ + Iterator last=it0.owner()->end(); + bool found=false; + + Iterator first=it0; + for(;first!=last;++first){ + if(first==it1)break; + + /* crucial that this check goes after previous break */ + + if(first==it)found=true; + } + if(first!=it1)return false; + return !found; + } + return true; +} + +template<typename Iterator,typename Difference> +inline bool check_in_bounds(const Iterator& it,Difference n) +{ + if(it.unchecked())return true; + if(!it.valid()) return false; + if(n>0) return it.owner()->end()-it>=n; + else return it.owner()->begin()-it<=n; +} + +template<typename Container> +inline bool check_different_container( + const Container& cont0,const Container& cont1) +{ + return &cont0!=&cont1; +} + +/* Invalidates all iterators equivalent to that given. Safe containers + * must call this when deleting elements: the safe mode framework cannot + * perform this operation automatically without outside help. + */ + +template<typename Iterator> +inline void detach_equivalent_iterators(Iterator& it) +{ + if(it.valid()){ + { +#if defined(BOOST_HAS_THREADS) + boost::detail::lightweight_mutex::scoped_lock lock(it.cont->mutex); +#endif + + Iterator *prev_,*next_; + for( + prev_=static_cast<Iterator*>(&it.cont->header); + (next_=static_cast<Iterator*>(prev_->next))!=0;){ + if(next_!=&it&&*next_==it){ + prev_->next=next_->next; + next_->cont=0; + } + else prev_=next_; + } + } + it.detach(); + } +} + +template<typename Container> class safe_container; /* fwd decl. */ + +} /* namespace multi_index::safe_mode */ + +namespace detail{ + +class safe_container_base; /* fwd decl. */ + +class safe_iterator_base +{ +public: + bool valid()const{return cont!=0;} + bool unchecked()const{return unchecked_;} + + inline void detach(); + + void uncheck() + { + detach(); + unchecked_=true; + } + +protected: + safe_iterator_base():cont(0),next(0),unchecked_(false){} + + explicit safe_iterator_base(safe_container_base* cont_): + unchecked_(false) + { + attach(cont_); + } + + safe_iterator_base(const safe_iterator_base& it): + unchecked_(it.unchecked_) + { + attach(it.cont); + } + + safe_iterator_base& operator=(const safe_iterator_base& it) + { + unchecked_=it.unchecked_; + safe_container_base* new_cont=it.cont; + if(cont!=new_cont){ + detach(); + attach(new_cont); + } + return *this; + } + + ~safe_iterator_base() + { + detach(); + } + + const safe_container_base* owner()const{return cont;} + +BOOST_MULTI_INDEX_PRIVATE_IF_MEMBER_TEMPLATE_FRIENDS: + friend class safe_container_base; + +#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) + template<typename> friend class safe_mode::safe_container; + template<typename Iterator> friend + void safe_mode::detach_equivalent_iterators(Iterator&); +#endif + + inline void attach(safe_container_base* cont_); + + safe_container_base* cont; + safe_iterator_base* next; + bool unchecked_; +}; + +class safe_container_base:private noncopyable +{ +public: + safe_container_base(){} + +BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: + friend class safe_iterator_base; + +#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) + template<typename Iterator> friend + void safe_mode::detach_equivalent_iterators(Iterator&); +#endif + + ~safe_container_base() + { + /* Detaches all remaining iterators, which by now will + * be those pointing to the end of the container. + */ + + for(safe_iterator_base* it=header.next;it;it=it->next)it->cont=0; + header.next=0; + } + + void swap(safe_container_base& x) + { + for(safe_iterator_base* it0=header.next;it0;it0=it0->next)it0->cont=&x; + for(safe_iterator_base* it1=x.header.next;it1;it1=it1->next)it1->cont=this; + std::swap(header.cont,x.header.cont); + std::swap(header.next,x.header.next); + } + + safe_iterator_base header; + +#if defined(BOOST_HAS_THREADS) + boost::detail::lightweight_mutex mutex; +#endif +}; + +void safe_iterator_base::attach(safe_container_base* cont_) +{ + cont=cont_; + if(cont){ +#if defined(BOOST_HAS_THREADS) + boost::detail::lightweight_mutex::scoped_lock lock(cont->mutex); +#endif + + next=cont->header.next; + cont->header.next=this; + } +} + +void safe_iterator_base::detach() +{ + if(cont){ +#if defined(BOOST_HAS_THREADS) + boost::detail::lightweight_mutex::scoped_lock lock(cont->mutex); +#endif + + safe_iterator_base *prev_,*next_; + for(prev_=&cont->header;(next_=prev_->next)!=this;prev_=next_){} + prev_->next=next; + cont=0; + } +} + +} /* namespace multi_index::detail */ + +namespace safe_mode{ + +/* In order to enable safe mode on a container: + * - The container must derive from safe_container<container_type>, + * - iterators must be generated via safe_iterator, which adapts a + * preexistent unsafe iterator class. + */ + +template<typename Container> +class safe_container; + +template<typename Iterator,typename Container> +class safe_iterator: + public detail::iter_adaptor<safe_iterator<Iterator,Container>,Iterator>, + public detail::safe_iterator_base +{ + typedef detail::iter_adaptor<safe_iterator,Iterator> super; + typedef detail::safe_iterator_base safe_super; + +public: + typedef Container container_type; + typedef typename Iterator::reference reference; + typedef typename Iterator::difference_type difference_type; + + safe_iterator(){} + explicit safe_iterator(safe_container<container_type>* cont_): + safe_super(cont_){} + template<typename T0> + safe_iterator(const T0& t0,safe_container<container_type>* cont_): + super(Iterator(t0)),safe_super(cont_){} + template<typename T0,typename T1> + safe_iterator( + const T0& t0,const T1& t1,safe_container<container_type>* cont_): + super(Iterator(t0,t1)),safe_super(cont_){} + + safe_iterator& operator=(const safe_iterator& x) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(x); + this->base_reference()=x.base_reference(); + safe_super::operator=(x); + return *this; + } + + const container_type* owner()const + { + return + static_cast<const container_type*>( + static_cast<const safe_container<container_type>*>( + this->safe_super::owner())); + } + + /* get_node is not to be used by the user */ + + typedef typename Iterator::node_type node_type; + + node_type* get_node()const{return this->base_reference().get_node();} + +private: + friend class boost::multi_index::detail::iter_adaptor_access; + + reference dereference()const + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this); + BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(*this); + return *(this->base_reference()); + } + + bool equal(const safe_iterator& x)const + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this); + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(x); + BOOST_MULTI_INDEX_CHECK_SAME_OWNER(*this,x); + return this->base_reference()==x.base_reference(); + } + + void increment() + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this); + BOOST_MULTI_INDEX_CHECK_INCREMENTABLE_ITERATOR(*this); + ++(this->base_reference()); + } + + void decrement() + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this); + BOOST_MULTI_INDEX_CHECK_DECREMENTABLE_ITERATOR(*this); + --(this->base_reference()); + } + + void advance(difference_type n) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this); + BOOST_MULTI_INDEX_CHECK_IN_BOUNDS(*this,n); + this->base_reference()+=n; + } + + difference_type distance_to(const safe_iterator& x)const + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this); + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(x); + BOOST_MULTI_INDEX_CHECK_SAME_OWNER(*this,x); + return x.base_reference()-this->base_reference(); + } + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) + /* Serialization. Note that Iterator::save and Iterator:load + * are assumed to be defined and public: at first sight it seems + * like we could have resorted to the public serialization interface + * for doing the forwarding to the adapted iterator class: + * ar<<base_reference(); + * ar>>base_reference(); + * but this would cause incompatibilities if a saving + * program is in safe mode and the loading program is not, or + * viceversa --in safe mode, the archived iterator data is one layer + * deeper, this is especially relevant with XML archives. + * It'd be nice if Boost.Serialization provided some forwarding + * facility for use by adaptor classes. + */ + + friend class boost::serialization::access; + + BOOST_SERIALIZATION_SPLIT_MEMBER() + + template<class Archive> + void save(Archive& ar,const unsigned int version)const + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(*this); + this->base_reference().save(ar,version); + } + + template<class Archive> + void load(Archive& ar,const unsigned int version) + { + this->base_reference().load(ar,version); + safe_super::uncheck(); + } +#endif +}; + +template<typename Container> +class safe_container:public detail::safe_container_base +{ + typedef detail::safe_container_base super; + +public: + void detach_dereferenceable_iterators() + { + typedef typename Container::iterator iterator; + + iterator end_=static_cast<Container*>(this)->end(); + iterator *prev_,*next_; + for( + prev_=static_cast<iterator*>(&this->header); + (next_=static_cast<iterator*>(prev_->next))!=0;){ + if(*next_!=end_){ + prev_->next=next_->next; + next_->cont=0; + } + else prev_=next_; + } + } + + void swap(safe_container<Container>& x) + { + super::swap(x); + } +}; + +} /* namespace multi_index::safe_mode */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif /* BOOST_MULTI_INDEX_ENABLE_SAFE_MODE */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/scope_guard.hpp b/3rdParty/Boost/src/boost/multi_index/detail/scope_guard.hpp new file mode 100644 index 0000000..12624c5 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/scope_guard.hpp @@ -0,0 +1,277 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_SCOPE_GUARD_HPP +#define BOOST_MULTI_INDEX_DETAIL_SCOPE_GUARD_HPP + +#if defined(_MSC_VER)&&(_MSC_VER>=1200) +#pragma once +#endif + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* Until some official version of the ScopeGuard idiom makes it into Boost, + * we locally define our own. This is a merely reformated version of + * ScopeGuard.h as defined in: + * Alexandrescu, A., Marginean, P.:"Generic<Programming>: Change the Way You + * Write Exception-Safe Code - Forever", C/C++ Users Jornal, Dec 2000, + * http://www.cuj.com/documents/s=8000/cujcexp1812alexandr/ + * with the following modifications: + * - General pretty formatting (pretty to my taste at least.) + * - Naming style changed to standard C++ library requirements. + * - safe_execute does not feature a try-catch protection, so we can + * use this even if BOOST_NO_EXCEPTIONS is defined. + * - Added scope_guard_impl4 and obj_scope_guard_impl3, (Boost.MultiIndex + * needs them). A better design would provide guards for many more + * arguments through the Boost Preprocessor Library. + * - Added scope_guard_impl_base::touch (see below.) + * - Removed RefHolder and ByRef, whose functionality is provided + * already by Boost.Ref. + * - Removed static make_guard's and make_obj_guard's, so that the code + * will work even if BOOST_NO_MEMBER_TEMPLATES is defined. This forces + * us to move some private ctors to public, though. + * + * NB: CodeWarrior Pro 8 seems to have problems looking up safe_execute + * without an explicit qualification. + */ + +class scope_guard_impl_base +{ +public: + scope_guard_impl_base():dismissed_(false){} + void dismiss()const{dismissed_=true;} + + /* This helps prevent some "unused variable" warnings under, for instance, + * GCC 3.2. + */ + void touch()const{} + +protected: + ~scope_guard_impl_base(){} + + scope_guard_impl_base(const scope_guard_impl_base& other): + dismissed_(other.dismissed_) + { + other.dismiss(); + } + + template<typename J> + static void safe_execute(J& j){if(!j.dismissed_)j.execute();} + + mutable bool dismissed_; + +private: + scope_guard_impl_base& operator=(const scope_guard_impl_base&); +}; + +typedef const scope_guard_impl_base& scope_guard; + +template<typename F> +class scope_guard_impl0:public scope_guard_impl_base +{ +public: + scope_guard_impl0(F fun):fun_(fun){} + ~scope_guard_impl0(){scope_guard_impl_base::safe_execute(*this);} + void execute(){fun_();} + +protected: + + F fun_; +}; + +template<typename F> +inline scope_guard_impl0<F> make_guard(F fun) +{ + return scope_guard_impl0<F>(fun); +} + +template<typename F,typename P1> +class scope_guard_impl1:public scope_guard_impl_base +{ +public: + scope_guard_impl1(F fun,P1 p1):fun_(fun),p1_(p1){} + ~scope_guard_impl1(){scope_guard_impl_base::safe_execute(*this);} + void execute(){fun_(p1_);} + +protected: + F fun_; + const P1 p1_; +}; + +template<typename F,typename P1> +inline scope_guard_impl1<F,P1> make_guard(F fun,P1 p1) +{ + return scope_guard_impl1<F,P1>(fun,p1); +} + +template<typename F,typename P1,typename P2> +class scope_guard_impl2:public scope_guard_impl_base +{ +public: + scope_guard_impl2(F fun,P1 p1,P2 p2):fun_(fun),p1_(p1),p2_(p2){} + ~scope_guard_impl2(){scope_guard_impl_base::safe_execute(*this);} + void execute(){fun_(p1_,p2_);} + +protected: + F fun_; + const P1 p1_; + const P2 p2_; +}; + +template<typename F,typename P1,typename P2> +inline scope_guard_impl2<F,P1,P2> make_guard(F fun,P1 p1,P2 p2) +{ + return scope_guard_impl2<F,P1,P2>(fun,p1,p2); +} + +template<typename F,typename P1,typename P2,typename P3> +class scope_guard_impl3:public scope_guard_impl_base +{ +public: + scope_guard_impl3(F fun,P1 p1,P2 p2,P3 p3):fun_(fun),p1_(p1),p2_(p2),p3_(p3){} + ~scope_guard_impl3(){scope_guard_impl_base::safe_execute(*this);} + void execute(){fun_(p1_,p2_,p3_);} + +protected: + F fun_; + const P1 p1_; + const P2 p2_; + const P3 p3_; +}; + +template<typename F,typename P1,typename P2,typename P3> +inline scope_guard_impl3<F,P1,P2,P3> make_guard(F fun,P1 p1,P2 p2,P3 p3) +{ + return scope_guard_impl3<F,P1,P2,P3>(fun,p1,p2,p3); +} + +template<typename F,typename P1,typename P2,typename P3,typename P4> +class scope_guard_impl4:public scope_guard_impl_base +{ +public: + scope_guard_impl4(F fun,P1 p1,P2 p2,P3 p3,P4 p4): + fun_(fun),p1_(p1),p2_(p2),p3_(p3),p4_(p4){} + ~scope_guard_impl4(){scope_guard_impl_base::safe_execute(*this);} + void execute(){fun_(p1_,p2_,p3_,p4_);} + +protected: + F fun_; + const P1 p1_; + const P2 p2_; + const P3 p3_; + const P4 p4_; +}; + +template<typename F,typename P1,typename P2,typename P3,typename P4> +inline scope_guard_impl4<F,P1,P2,P3,P4> make_guard( + F fun,P1 p1,P2 p2,P3 p3,P4 p4) +{ + return scope_guard_impl4<F,P1,P2,P3,P4>(fun,p1,p2,p3,p4); +} + +template<class Obj,typename MemFun> +class obj_scope_guard_impl0:public scope_guard_impl_base +{ +public: + obj_scope_guard_impl0(Obj& obj,MemFun mem_fun):obj_(obj),mem_fun_(mem_fun){} + ~obj_scope_guard_impl0(){scope_guard_impl_base::safe_execute(*this);} + void execute(){(obj_.*mem_fun_)();} + +protected: + Obj& obj_; + MemFun mem_fun_; +}; + +template<class Obj,typename MemFun> +inline obj_scope_guard_impl0<Obj,MemFun> make_obj_guard(Obj& obj,MemFun mem_fun) +{ + return obj_scope_guard_impl0<Obj,MemFun>(obj,mem_fun); +} + +template<class Obj,typename MemFun,typename P1> +class obj_scope_guard_impl1:public scope_guard_impl_base +{ +public: + obj_scope_guard_impl1(Obj& obj,MemFun mem_fun,P1 p1): + obj_(obj),mem_fun_(mem_fun),p1_(p1){} + ~obj_scope_guard_impl1(){scope_guard_impl_base::safe_execute(*this);} + void execute(){(obj_.*mem_fun_)(p1_);} + +protected: + Obj& obj_; + MemFun mem_fun_; + const P1 p1_; +}; + +template<class Obj,typename MemFun,typename P1> +inline obj_scope_guard_impl1<Obj,MemFun,P1> make_obj_guard( + Obj& obj,MemFun mem_fun,P1 p1) +{ + return obj_scope_guard_impl1<Obj,MemFun,P1>(obj,mem_fun,p1); +} + +template<class Obj,typename MemFun,typename P1,typename P2> +class obj_scope_guard_impl2:public scope_guard_impl_base +{ +public: + obj_scope_guard_impl2(Obj& obj,MemFun mem_fun,P1 p1,P2 p2): + obj_(obj),mem_fun_(mem_fun),p1_(p1),p2_(p2) + {} + ~obj_scope_guard_impl2(){scope_guard_impl_base::safe_execute(*this);} + void execute(){(obj_.*mem_fun_)(p1_,p2_);} + +protected: + Obj& obj_; + MemFun mem_fun_; + const P1 p1_; + const P2 p2_; +}; + +template<class Obj,typename MemFun,typename P1,typename P2> +inline obj_scope_guard_impl2<Obj,MemFun,P1,P2> +make_obj_guard(Obj& obj,MemFun mem_fun,P1 p1,P2 p2) +{ + return obj_scope_guard_impl2<Obj,MemFun,P1,P2>(obj,mem_fun,p1,p2); +} + +template<class Obj,typename MemFun,typename P1,typename P2,typename P3> +class obj_scope_guard_impl3:public scope_guard_impl_base +{ +public: + obj_scope_guard_impl3(Obj& obj,MemFun mem_fun,P1 p1,P2 p2,P3 p3): + obj_(obj),mem_fun_(mem_fun),p1_(p1),p2_(p2),p3_(p3) + {} + ~obj_scope_guard_impl3(){scope_guard_impl_base::safe_execute(*this);} + void execute(){(obj_.*mem_fun_)(p1_,p2_,p3_);} + +protected: + Obj& obj_; + MemFun mem_fun_; + const P1 p1_; + const P2 p2_; + const P3 p3_; +}; + +template<class Obj,typename MemFun,typename P1,typename P2,typename P3> +inline obj_scope_guard_impl3<Obj,MemFun,P1,P2,P3> +make_obj_guard(Obj& obj,MemFun mem_fun,P1 p1,P2 p2,P3 p3) +{ + return obj_scope_guard_impl3<Obj,MemFun,P1,P2,P3>(obj,mem_fun,p1,p2,p3); +} + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/seq_index_node.hpp b/3rdParty/Boost/src/boost/multi_index/detail/seq_index_node.hpp new file mode 100644 index 0000000..cf409ed --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/seq_index_node.hpp @@ -0,0 +1,223 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_NODE_HPP +#define BOOST_MULTI_INDEX_DETAIL_SEQ_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 <algorithm> +#include <boost/detail/allocator_utilities.hpp> +#include <boost/multi_index/detail/prevent_eti.hpp> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* doubly-linked node for use by sequenced_index */ + +template<typename Allocator> +struct sequenced_index_node_impl +{ + typedef typename prevent_eti< + Allocator, + typename boost::detail::allocator::rebind_to< + Allocator,sequenced_index_node_impl + >::type + >::type::pointer pointer; + typedef typename prevent_eti< + Allocator, + typename boost::detail::allocator::rebind_to< + Allocator,sequenced_index_node_impl + >::type + >::type::const_pointer const_pointer; + + pointer& prior(){return prior_;} + pointer prior()const{return prior_;} + pointer& next(){return next_;} + pointer next()const{return next_;} + + /* interoperability with bidir_node_iterator */ + + static void increment(pointer& x){x=x->next();} + static void decrement(pointer& x){x=x->prior();} + + /* algorithmic stuff */ + + static void link(pointer x,pointer header) + { + x->prior()=header->prior(); + x->next()=header; + x->prior()->next()=x->next()->prior()=x; + }; + + static void unlink(pointer x) + { + x->prior()->next()=x->next(); + x->next()->prior()=x->prior(); + } + + static void relink(pointer position,pointer x) + { + unlink(x); + x->prior()=position->prior(); + x->next()=position; + x->prior()->next()=x->next()->prior()=x; + } + + static void relink(pointer position,pointer x,pointer y) + { + /* position is assumed not to be in [x,y) */ + + if(x!=y){ + pointer z=y->prior(); + x->prior()->next()=y; + y->prior()=x->prior(); + x->prior()=position->prior(); + z->next()=position; + x->prior()->next()=x; + z->next()->prior()=z; + } + } + + static void reverse(pointer header) + { + pointer x=header; + do{ + pointer y=x->next(); + std::swap(x->prior(),x->next()); + x=y; + }while(x!=header); + } + + static void swap(pointer x,pointer y) + { + /* This swap function does not exchange the header nodes, + * but rather their pointers. This is *not* used for implementing + * sequenced_index::swap. + */ + + if(x->next()!=x){ + if(y->next()!=y){ + std::swap(x->next(),y->next()); + std::swap(x->prior(),y->prior()); + x->next()->prior()=x->prior()->next()=x; + y->next()->prior()=y->prior()->next()=y; + } + else{ + y->next()=x->next(); + y->prior()=x->prior(); + x->next()=x->prior()=x; + y->next()->prior()=y->prior()->next()=y; + } + } + else if(y->next()!=y){ + x->next()=y->next(); + x->prior()=y->prior(); + y->next()=y->prior()=y; + x->next()->prior()=x->prior()->next()=x; + } + } + +private: + pointer prior_; + pointer next_; +}; + +template<typename Super> +struct sequenced_index_node_trampoline: + prevent_eti< + Super, + sequenced_index_node_impl< + typename boost::detail::allocator::rebind_to< + typename Super::allocator_type, + char + >::type + > + >::type +{ + typedef typename prevent_eti< + Super, + sequenced_index_node_impl< + typename boost::detail::allocator::rebind_to< + typename Super::allocator_type, + char + >::type + > + >::type impl_type; +}; + +template<typename Super> +struct sequenced_index_node:Super,sequenced_index_node_trampoline<Super> +{ +private: + typedef sequenced_index_node_trampoline<Super> trampoline; + +public: + typedef typename trampoline::impl_type impl_type; + typedef typename trampoline::pointer impl_pointer; + typedef typename trampoline::const_pointer const_impl_pointer; + + impl_pointer& prior(){return trampoline::prior();} + impl_pointer prior()const{return trampoline::prior();} + impl_pointer& next(){return trampoline::next();} + impl_pointer next()const{return trampoline::next();} + + impl_pointer impl() + { + return static_cast<impl_pointer>( + static_cast<impl_type*>(static_cast<trampoline*>(this))); + } + + const_impl_pointer impl()const + { + return static_cast<const_impl_pointer>( + static_cast<const impl_type*>(static_cast<const trampoline*>(this))); + } + + static sequenced_index_node* from_impl(impl_pointer x) + { + return static_cast<sequenced_index_node*>( + static_cast<trampoline*>(&*x)); + } + + static const sequenced_index_node* from_impl(const_impl_pointer x) + { + return static_cast<const sequenced_index_node*>( + static_cast<const trampoline*>(&*x)); + } + + /* interoperability with bidir_node_iterator */ + + static void increment(sequenced_index_node*& x) + { + impl_pointer xi=x->impl(); + trampoline::increment(xi); + x=from_impl(xi); + } + + static void decrement(sequenced_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 diff --git a/3rdParty/Boost/src/boost/multi_index/detail/seq_index_ops.hpp b/3rdParty/Boost/src/boost/multi_index/detail/seq_index_ops.hpp new file mode 100644 index 0000000..8135074 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/seq_index_ops.hpp @@ -0,0 +1,200 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_OPS_HPP +#define BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_OPS_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 <boost/detail/no_exceptions_support.hpp> +#include <boost/multi_index/detail/seq_index_node.hpp> +#include <boost/limits.hpp> +#include <boost/type_traits/aligned_storage.hpp> +#include <boost/type_traits/alignment_of.hpp> +#include <cstddef> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* Common code for sequenced_index memfuns having templatized and + * non-templatized versions. + */ + +template <typename SequencedIndex,typename Predicate> +void sequenced_index_remove(SequencedIndex& x,Predicate pred) +{ + typedef typename SequencedIndex::iterator iterator; + iterator first=x.begin(),last=x.end(); + while(first!=last){ + if(pred(*first))x.erase(first++); + else ++first; + } +} + +template <typename SequencedIndex,class BinaryPredicate> +void sequenced_index_unique(SequencedIndex& x,BinaryPredicate binary_pred) +{ + typedef typename SequencedIndex::iterator iterator; + iterator first=x.begin(); + iterator last=x.end(); + if(first!=last){ + for(iterator middle=first;++middle!=last;middle=first){ + if(binary_pred(*middle,*first))x.erase(middle); + else first=middle; + } + } +} + +template <typename SequencedIndex,typename Compare> +void sequenced_index_merge(SequencedIndex& x,SequencedIndex& y,Compare comp) +{ + typedef typename SequencedIndex::iterator iterator; + if(&x!=&y){ + iterator first0=x.begin(),last0=x.end(); + iterator first1=y.begin(),last1=y.end(); + while(first0!=last0&&first1!=last1){ + if(comp(*first1,*first0))x.splice(first0,y,first1++); + else ++first0; + } + x.splice(last0,y,first1,last1); + } +} + +/* sorting */ + +/* auxiliary stuff */ + +template<typename Node,typename Compare> +void sequenced_index_collate( + BOOST_DEDUCED_TYPENAME Node::impl_type* x, + BOOST_DEDUCED_TYPENAME Node::impl_type* y, + Compare comp + BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Node)) +{ + typedef typename Node::impl_type impl_type; + typedef typename Node::impl_pointer impl_pointer; + + impl_pointer first0=x->next(); + impl_pointer last0=x; + impl_pointer first1=y->next(); + impl_pointer last1=y; + while(first0!=last0&&first1!=last1){ + if(comp( + Node::from_impl(first1)->value(),Node::from_impl(first0)->value())){ + impl_pointer tmp=first1->next(); + impl_type::relink(first0,first1); + first1=tmp; + } + else first0=first0->next(); + } + impl_type::relink(last0,first1,last1); +} + +/* Some versions of CGG require a bogus typename in counter_spc + * inside sequenced_index_sort if the following is defined + * also inside sequenced_index_sort. + */ + +BOOST_STATIC_CONSTANT( + std::size_t, + sequenced_index_sort_max_fill= + (std::size_t)std::numeric_limits<std::size_t>::digits+1); + +template<typename Node,typename Compare> +void sequenced_index_sort(Node* header,Compare comp) +{ + /* Musser's mergesort, see http://www.cs.rpi.edu/~musser/gp/List/lists1.html. + * The implementation is a little convoluted: in the original code + * counter elements and carry are std::lists: here we do not want + * to use multi_index instead, so we do things at a lower level, managing + * directly the internal node representation. + * Incidentally, the implementations I've seen of this algorithm (SGI, + * Dinkumware, STLPort) are not exception-safe: this is. Moreover, we do not + * use any dynamic storage. + */ + + if(header->next()==header->impl()|| + header->next()->next()==header->impl())return; + + typedef typename Node::impl_type impl_type; + typedef typename Node::impl_pointer impl_pointer; + + typedef typename aligned_storage< + sizeof(impl_type), + alignment_of<impl_type>::value + >::type carry_spc_type; + carry_spc_type carry_spc; + impl_type& carry= + *static_cast<impl_type*>(static_cast<void*>(&carry_spc)); + typedef typename aligned_storage< + sizeof( + impl_type + [sequenced_index_sort_max_fill]), + alignment_of< + impl_type + [sequenced_index_sort_max_fill] + >::value + >::type counter_spc_type; + counter_spc_type counter_spc; + impl_type* counter= + static_cast<impl_type*>(static_cast<void*>(&counter_spc)); + std::size_t fill=0; + + carry.prior()=carry.next()=static_cast<impl_pointer>(&carry); + counter[0].prior()=counter[0].next()=static_cast<impl_pointer>(&counter[0]); + + BOOST_TRY{ + while(header->next()!=header->impl()){ + impl_type::relink(carry.next(),header->next()); + std::size_t i=0; + while(i<fill&&counter[i].next()!=static_cast<impl_pointer>(&counter[i])){ + sequenced_index_collate<Node>(&carry,&counter[i++],comp); + } + impl_type::swap( + static_cast<impl_pointer>(&carry), + static_cast<impl_pointer>(&counter[i])); + if(i==fill){ + ++fill; + counter[fill].prior()=counter[fill].next()= + static_cast<impl_pointer>(&counter[fill]); + } + } + + for(std::size_t i=1;i<fill;++i){ + sequenced_index_collate<Node>(&counter[i],&counter[i-1],comp); + } + impl_type::swap( + header->impl(),static_cast<impl_pointer>(&counter[fill-1])); + } + BOOST_CATCH(...) + { + impl_type::relink( + header->impl(),carry.next(),static_cast<impl_pointer>(&carry)); + for(std::size_t i=0;i<=fill;++i){ + impl_type::relink( + header->impl(),counter[i].next(), + static_cast<impl_pointer>(&counter[i])); + } + BOOST_RETHROW; + } + BOOST_CATCH_END +} + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/serialization_version.hpp b/3rdParty/Boost/src/boost/multi_index/detail/serialization_version.hpp new file mode 100644 index 0000000..cced78c --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/serialization_version.hpp @@ -0,0 +1,75 @@ +/* Copyright 2003-2010 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_SERIALIZATION_VERSION_HPP +#define BOOST_MULTI_INDEX_DETAIL_SERIALIZATION_VERSION_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 <boost/serialization/split_member.hpp> +#include <boost/serialization/version.hpp> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* Helper class for storing and retrieving a given type serialization class + * version while avoiding saving the number multiple times in the same + * archive. + * Behavior undefined if template partial specialization is not supported. + */ + +template<typename T> +struct serialization_version +{ + serialization_version(): + value(boost::serialization::version<serialization_version>::value){} + + serialization_version& operator=(unsigned int x){value=x;return *this;}; + + operator unsigned int()const{return value;} + +private: + friend class boost::serialization::access; + + BOOST_SERIALIZATION_SPLIT_MEMBER() + + template<class Archive> + void save(Archive&,const unsigned int)const{} + + template<class Archive> + void load(Archive&,const unsigned int version) + { + this->value=version; + } + + unsigned int value; +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +#if !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) +namespace serialization { +template<typename T> +struct version<boost::multi_index::detail::serialization_version<T> > +{ + BOOST_STATIC_CONSTANT(int,value=version<T>::value); +}; +} /* namespace serialization */ +#endif + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/uintptr_type.hpp b/3rdParty/Boost/src/boost/multi_index/detail/uintptr_type.hpp new file mode 100644 index 0000000..529c623 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/uintptr_type.hpp @@ -0,0 +1,76 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_UINTPTR_TYPE_HPP +#define BOOST_MULTI_INDEX_DETAIL_UINTPTR_TYPE_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 <boost/mpl/bool.hpp> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* has_uintptr_type is an MPL integral constant determining whether + * there exists an unsigned integral type with the same size as + * void *. + * uintptr_type is such a type if has_uintptr is true, or unsigned int + * otherwise. + * Note that uintptr_type is more restrictive than C99 uintptr_t, + * where an integral type with size greater than that of void * + * would be conformant. + */ + +template<int N>struct uintptr_candidates; +template<>struct uintptr_candidates<-1>{typedef unsigned int type;}; +template<>struct uintptr_candidates<0> {typedef unsigned int type;}; +template<>struct uintptr_candidates<1> {typedef unsigned short type;}; +template<>struct uintptr_candidates<2> {typedef unsigned long type;}; + +#if defined(BOOST_HAS_LONG_LONG) +template<>struct uintptr_candidates<3> {typedef boost::ulong_long_type type;}; +#else +template<>struct uintptr_candidates<3> {typedef unsigned int type;}; +#endif + +#if defined(BOOST_HAS_MS_INT64) +template<>struct uintptr_candidates<4> {typedef unsigned __int64 type;}; +#else +template<>struct uintptr_candidates<4> {typedef unsigned int type;}; +#endif + +struct uintptr_aux +{ + BOOST_STATIC_CONSTANT(int,index= + sizeof(void*)==sizeof(uintptr_candidates<0>::type)?0: + sizeof(void*)==sizeof(uintptr_candidates<1>::type)?1: + sizeof(void*)==sizeof(uintptr_candidates<2>::type)?2: + sizeof(void*)==sizeof(uintptr_candidates<3>::type)?3: + sizeof(void*)==sizeof(uintptr_candidates<4>::type)?4:-1); + + BOOST_STATIC_CONSTANT(bool,has_uintptr_type=(index>=0)); + + typedef uintptr_candidates<index>::type type; +}; + +typedef mpl::bool_<uintptr_aux::has_uintptr_type> has_uintptr_type; +typedef uintptr_aux::type uintptr_type; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/unbounded.hpp b/3rdParty/Boost/src/boost/multi_index/detail/unbounded.hpp new file mode 100644 index 0000000..40c3034 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/unbounded.hpp @@ -0,0 +1,83 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_UNBOUNDED_HPP +#define BOOST_MULTI_INDEX_DETAIL_UNBOUNDED_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 <boost/detail/workaround.hpp> + +namespace boost{ + +namespace multi_index{ + +/* dummy type and variable for use in ordered_index::range() */ + +#if BOOST_WORKAROUND(BOOST_MSVC,<1300) +/* The default branch actually works for MSVC 6.0, but seems like + * this implementation of unbounded improves the performance of ordered + * indices! This behavior is hard to explain and probably a test artifact, + * but it does not hurt to have the workaround anyway. + */ + +namespace detail{struct unbounded_type{};} + +namespace{ + +static detail::unbounded_type unbounded_obj=detail::unbounded_type(); +static detail::unbounded_type& unbounded=unbounded_obj; + +} /* unnamed */ +#else +/* ODR-abiding technique shown at the example attached to + * http://lists.boost.org/Archives/boost/2006/07/108355.php + */ + +namespace detail{class unbounded_helper;} + +detail::unbounded_helper unbounded(detail::unbounded_helper); + +namespace detail{ + +class unbounded_helper +{ + unbounded_helper(){} + unbounded_helper(const unbounded_helper&){} + friend unbounded_helper multi_index::unbounded(unbounded_helper); +}; + +typedef unbounded_helper (*unbounded_type)(unbounded_helper); + +} /* namespace multi_index::detail */ + +inline detail::unbounded_helper unbounded(detail::unbounded_helper) +{ + return detail::unbounded_helper(); +} +#endif + +/* tags used in the implementation of range */ + +namespace detail{ + +struct none_unbounded_tag{}; +struct lower_unbounded_tag{}; +struct upper_unbounded_tag{}; +struct both_unbounded_tag{}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/detail/value_compare.hpp b/3rdParty/Boost/src/boost/multi_index/detail/value_compare.hpp new file mode 100644 index 0000000..0bd7b4f --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/detail/value_compare.hpp @@ -0,0 +1,53 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_DETAIL_VALUE_COMPARE_HPP +#define BOOST_MULTI_INDEX_DETAIL_VALUE_COMPARE_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 <boost/call_traits.hpp> +#include <functional> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +template<typename Value,typename KeyFromValue,typename Compare> +struct value_comparison:std::binary_function<Value,Value,bool> +{ + value_comparison( + const KeyFromValue& key_=KeyFromValue(),const Compare& comp_=Compare()): + key(key_),comp(comp_) + { + } + + bool operator()( + typename call_traits<Value>::param_type x, + typename call_traits<Value>::param_type y)const + { + return comp(key(x),key(y)); + } + +private: + KeyFromValue key; + Compare comp; +}; + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/identity.hpp b/3rdParty/Boost/src/boost/multi_index/identity.hpp new file mode 100644 index 0000000..b402ad7 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/identity.hpp @@ -0,0 +1,147 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_IDENTITY_HPP +#define BOOST_MULTI_INDEX_IDENTITY_HPP + +#if defined(_MSC_VER)&&(_MSC_VER>=1200) +#pragma once +#endif + +#include <boost/config.hpp> +#include <boost/mpl/if.hpp> +#include <boost/multi_index/identity_fwd.hpp> +#include <boost/type_traits/is_const.hpp> +#include <boost/type_traits/remove_const.hpp> +#include <boost/utility/enable_if.hpp> + +#if !defined(BOOST_NO_SFINAE) +#include <boost/type_traits/is_convertible.hpp> +#endif + +namespace boost{ + +template<class Type> class reference_wrapper; /* fwd decl. */ + +namespace multi_index{ + +namespace detail{ + +/* identity is a do-nothing key extractor that returns the [const] Type& + * object passed. + * Additionally, identity is overloaded to support referece_wrappers + * of Type and "chained pointers" to Type's. By chained pointer to Type we + * mean a type P such that, given a p of type P + * *...n...*x is convertible to Type&, for some n>=1. + * Examples of chained pointers are raw and smart pointers, iterators and + * arbitrary combinations of these (vg. Type** or auto_ptr<Type*>.) + */ + +/* NB. Some overloads of operator() have an extra dummy parameter int=0. + * This disambiguator serves several purposes: + * - Without it, MSVC++ 6.0 incorrectly regards some overloads as + * specializations of a previous member function template. + * - MSVC++ 6.0/7.0 seem to incorrectly treat some different memfuns + * as if they have the same signature. + * - If remove_const is broken due to lack of PTS, int=0 avoids the + * declaration of memfuns with identical signature. + */ + +template<typename Type> +struct const_identity_base +{ + typedef Type result_type; + + template<typename ChainedPtr> + +#if !defined(BOOST_NO_SFINAE) + typename disable_if<is_convertible<const ChainedPtr&,Type&>,Type&>::type +#else + Type& +#endif + + operator()(const ChainedPtr& x)const + { + return operator()(*x); + } + + Type& operator()(Type& x)const + { + return x; + } + + Type& operator()(const reference_wrapper<Type>& x)const + { + return x.get(); + } + + Type& operator()( + const reference_wrapper<typename remove_const<Type>::type>& x,int=0)const + { + return x.get(); + } +}; + +template<typename Type> +struct non_const_identity_base +{ + typedef Type result_type; + + /* templatized for pointer-like types */ + + template<typename ChainedPtr> + +#if !defined(BOOST_NO_SFINAE) + typename disable_if< + is_convertible<const ChainedPtr&,const Type&>,Type&>::type +#else + Type& +#endif + + operator()(const ChainedPtr& x)const + { + return operator()(*x); + } + + const Type& operator()(const Type& x,int=0)const + { + return x; + } + + Type& operator()(Type& x)const + { + return x; + } + + const Type& operator()(const reference_wrapper<const Type>& x,int=0)const + { + return x.get(); + } + + Type& operator()(const reference_wrapper<Type>& x)const + { + return x.get(); + } +}; + +} /* namespace multi_index::detail */ + +template<class Type> +struct identity: + mpl::if_c< + is_const<Type>::value, + detail::const_identity_base<Type>,detail::non_const_identity_base<Type> + >::type +{ +}; + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/identity_fwd.hpp b/3rdParty/Boost/src/boost/multi_index/identity_fwd.hpp new file mode 100644 index 0000000..baafa43 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/identity_fwd.hpp @@ -0,0 +1,26 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_IDENTITY_FWD_HPP +#define BOOST_MULTI_INDEX_IDENTITY_FWD_HPP + +#if defined(_MSC_VER)&&(_MSC_VER>=1200) +#pragma once +#endif + +namespace boost{ + +namespace multi_index{ + +template<class Type> struct identity; + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/indexed_by.hpp b/3rdParty/Boost/src/boost/multi_index/indexed_by.hpp new file mode 100644 index 0000000..94a8dcb --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/indexed_by.hpp @@ -0,0 +1,72 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_INDEXED_BY_HPP +#define BOOST_MULTI_INDEX_INDEXED_BY_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 <boost/mpl/vector.hpp> +#include <boost/preprocessor/cat.hpp> +#include <boost/preprocessor/control/expr_if.hpp> +#include <boost/preprocessor/repetition/enum.hpp> +#include <boost/preprocessor/repetition/enum_params.hpp> + +/* An alias to mpl::vector used to hide MPL from the user. + * indexed_by contains the index specifiers for instantiation + * of a multi_index_container. + */ + +/* This user_definable macro limits the number of elements of an index list; + * useful for shortening resulting symbol names (MSVC++ 6.0, for instance, + * has problems coping with very long symbol names.) + */ + +#if !defined(BOOST_MULTI_INDEX_LIMIT_INDEXED_BY_SIZE) +#if defined(BOOST_MSVC)&&(BOOST_MSVC<1300) +#define BOOST_MULTI_INDEX_LIMIT_INDEXED_BY_SIZE 5 +#else +#define BOOST_MULTI_INDEX_LIMIT_INDEXED_BY_SIZE BOOST_MPL_LIMIT_VECTOR_SIZE +#endif +#endif + +#if BOOST_MULTI_INDEX_LIMIT_INDEXED_BY_SIZE<BOOST_MPL_LIMIT_VECTOR_SIZE +#define BOOST_MULTI_INDEX_INDEXED_BY_SIZE \ + BOOST_MULTI_INDEX_LIMIT_INDEXED_BY_SIZE +#else +#define BOOST_MULTI_INDEX_INDEXED_BY_SIZE BOOST_MPL_LIMIT_VECTOR_SIZE +#endif + +#define BOOST_MULTI_INDEX_INDEXED_BY_TEMPLATE_PARM(z,n,var) \ + typename BOOST_PP_CAT(var,n) BOOST_PP_EXPR_IF(n,=mpl::na) + +namespace boost{ + +namespace multi_index{ + +template< + BOOST_PP_ENUM( + BOOST_MULTI_INDEX_INDEXED_BY_SIZE, + BOOST_MULTI_INDEX_INDEXED_BY_TEMPLATE_PARM,T) +> +struct indexed_by: + mpl::vector<BOOST_PP_ENUM_PARAMS(BOOST_MULTI_INDEX_INDEXED_BY_SIZE,T)> +{ +}; + +} /* namespace multi_index */ + +} /* namespace boost */ + +#undef BOOST_MULTI_INDEX_INDEXED_BY_TEMPLATE_PARM +#undef BOOST_MULTI_INDEX_INDEXED_BY_SIZE + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/member.hpp b/3rdParty/Boost/src/boost/multi_index/member.hpp new file mode 100644 index 0000000..848e9b2 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/member.hpp @@ -0,0 +1,269 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_MEMBER_HPP +#define BOOST_MULTI_INDEX_MEMBER_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 <boost/mpl/if.hpp> +#include <boost/type_traits/is_const.hpp> +#include <boost/utility/enable_if.hpp> +#include <cstddef> + +#if !defined(BOOST_NO_SFINAE) +#include <boost/type_traits/is_convertible.hpp> +#endif + +namespace boost{ + +template<class T> class reference_wrapper; /* fwd decl. */ + +namespace multi_index{ + +namespace detail{ + +/* member is a read/write key extractor for accessing a given + * member of a class. + * Additionally, member is overloaded to support referece_wrappers + * of T and "chained pointers" to T's. By chained pointer to T we mean + * a type P such that, given a p of Type P + * *...n...*x is convertible to T&, for some n>=1. + * Examples of chained pointers are raw and smart pointers, iterators and + * arbitrary combinations of these (vg. T** or auto_ptr<T*>.) + */ + +/* NB. Some overloads of operator() have an extra dummy parameter int=0. + * This disambiguator serves several purposes: + * - Without it, MSVC++ 6.0 incorrectly regards some overloads as + * specializations of a previous member function template. + * - MSVC++ 6.0/7.0 seem to incorrectly treat some different memfuns + * as if they have the same signature. + * - If remove_const is broken due to lack of PTS, int=0 avoids the + * declaration of memfuns with identical signature. + */ + +template<class Class,typename Type,Type Class::*PtrToMember> +struct const_member_base +{ + typedef Type result_type; + + template<typename ChainedPtr> + +#if !defined(BOOST_NO_SFINAE) + typename disable_if< + is_convertible<const ChainedPtr&,const Class&>,Type&>::type +#else + Type& +#endif + + operator()(const ChainedPtr& x)const + { + return operator()(*x); + } + + Type& operator()(const Class& x)const + { + return x.*PtrToMember; + } + + Type& operator()(const reference_wrapper<const Class>& x)const + { + return operator()(x.get()); + } + + Type& operator()(const reference_wrapper<Class>& x,int=0)const + { + return operator()(x.get()); + } +}; + +template<class Class,typename Type,Type Class::*PtrToMember> +struct non_const_member_base +{ + typedef Type result_type; + + template<typename ChainedPtr> + +#if !defined(BOOST_NO_SFINAE) + typename disable_if< + is_convertible<const ChainedPtr&,const Class&>,Type&>::type +#else + Type& +#endif + + operator()(const ChainedPtr& x)const + { + return operator()(*x); + } + + const Type& operator()(const Class& x,int=0)const + { + return x.*PtrToMember; + } + + Type& operator()(Class& x)const + { + return x.*PtrToMember; + } + + const Type& operator()(const reference_wrapper<const Class>& x,int=0)const + { + return operator()(x.get()); + } + + Type& operator()(const reference_wrapper<Class>& x)const + { + return operator()(x.get()); + } +}; + +} /* namespace multi_index::detail */ + +template<class Class,typename Type,Type Class::*PtrToMember> +struct member: + mpl::if_c< + is_const<Type>::value, + detail::const_member_base<Class,Type,PtrToMember>, + detail::non_const_member_base<Class,Type,PtrToMember> + >::type +{ +}; + +namespace detail{ + +/* MSVC++ 6.0 does not support properly pointers to members as + * non-type template arguments, as reported in + * http://support.microsoft.com/default.aspx?scid=kb;EN-US;249045 + * A similar problem (though not identical) is shown by MSVC++ 7.0. + * We provide an alternative to member<> accepting offsets instead + * of pointers to members. This happens to work even for non-POD + * types (although the standard forbids use of offsetof on these), + * so it serves as a workaround in this compiler for all practical + * purposes. + * Surprisingly enough, other compilers, like Intel C++ 7.0/7.1 and + * Visual Age 6.0, have similar bugs. This replacement of member<> + * can be used for them too. + */ + +template<class Class,typename Type,std::size_t OffsetOfMember> +struct const_member_offset_base +{ + typedef Type result_type; + + template<typename ChainedPtr> + +#if !defined(BOOST_NO_SFINAE) + typename disable_if< + is_convertible<const ChainedPtr&,const Class&>,Type&>::type +#else + Type& +#endif + + operator()(const ChainedPtr& x)const + { + return operator()(*x); + } + + Type& operator()(const Class& x)const + { + return *static_cast<const Type*>( + static_cast<const void*>( + static_cast<const char*>( + static_cast<const void *>(&x))+OffsetOfMember)); + } + + Type& operator()(const reference_wrapper<const Class>& x)const + { + return operator()(x.get()); + } + + Type& operator()(const reference_wrapper<Class>& x,int=0)const + { + return operator()(x.get()); + } +}; + +template<class Class,typename Type,std::size_t OffsetOfMember> +struct non_const_member_offset_base +{ + typedef Type result_type; + + template<typename ChainedPtr> + +#if !defined(BOOST_NO_SFINAE) + typename disable_if< + is_convertible<const ChainedPtr&,const Class&>,Type&>::type +#else + Type& +#endif + + operator()(const ChainedPtr& x)const + { + return operator()(*x); + } + + const Type& operator()(const Class& x,int=0)const + { + return *static_cast<const Type*>( + static_cast<const void*>( + static_cast<const char*>( + static_cast<const void *>(&x))+OffsetOfMember)); + } + + Type& operator()(Class& x)const + { + return *static_cast<Type*>( + static_cast<void*>( + static_cast<char*>(static_cast<void *>(&x))+OffsetOfMember)); + } + + const Type& operator()(const reference_wrapper<const Class>& x,int=0)const + { + return operator()(x.get()); + } + + Type& operator()(const reference_wrapper<Class>& x)const + { + return operator()(x.get()); + } +}; + +} /* namespace multi_index::detail */ + +template<class Class,typename Type,std::size_t OffsetOfMember> +struct member_offset: + mpl::if_c< + is_const<Type>::value, + detail::const_member_offset_base<Class,Type,OffsetOfMember>, + detail::non_const_member_offset_base<Class,Type,OffsetOfMember> + >::type +{ +}; + +/* BOOST_MULTI_INDEX_MEMBER resolves to member in the normal cases, + * and to member_offset as a workaround in those defective compilers for + * which BOOST_NO_POINTER_TO_MEMBER_TEMPLATE_PARAMETERS is defined. + */ + +#if defined(BOOST_NO_POINTER_TO_MEMBER_TEMPLATE_PARAMETERS) +#define BOOST_MULTI_INDEX_MEMBER(Class,Type,MemberName) \ +::boost::multi_index::member_offset< Class,Type,offsetof(Class,MemberName) > +#else +#define BOOST_MULTI_INDEX_MEMBER(Class,Type,MemberName) \ +::boost::multi_index::member< Class,Type,&Class::MemberName > +#endif + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/ordered_index.hpp b/3rdParty/Boost/src/boost/multi_index/ordered_index.hpp new file mode 100644 index 0000000..a49e4cf --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/ordered_index.hpp @@ -0,0 +1,1390 @@ +/* Copyright 2003-2010 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/iterator/reverse_iterator.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 */ + +#undef BOOST_MULTI_INDEX_ORD_INDEX_CHECK_INVARIANT + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/ordered_index_fwd.hpp b/3rdParty/Boost/src/boost/multi_index/ordered_index_fwd.hpp new file mode 100644 index 0000000..6288a71 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/ordered_index_fwd.hpp @@ -0,0 +1,124 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_ORDERED_INDEX_FWD_HPP +#define BOOST_MULTI_INDEX_ORDERED_INDEX_FWD_HPP + +#if defined(_MSC_VER)&&(_MSC_VER>=1200) +#pragma once +#endif + +#include <boost/multi_index/detail/ord_index_args.hpp> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +template< + typename KeyFromValue,typename Compare, + typename SuperMeta,typename TagList,typename Category +> +class ordered_index; + +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); + +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); + +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); + +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); + +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); + +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); + +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); + +} /* namespace multi_index::detail */ + +/* ordered_index specifiers */ + +template<typename Arg1,typename Arg2=mpl::na,typename Arg3=mpl::na> +struct ordered_unique; + +template<typename Arg1,typename Arg2=mpl::na,typename Arg3=mpl::na> +struct ordered_non_unique; + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/safe_mode_errors.hpp b/3rdParty/Boost/src/boost/multi_index/safe_mode_errors.hpp new file mode 100644 index 0000000..ff6f960 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/safe_mode_errors.hpp @@ -0,0 +1,48 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_SAFE_MODE_ERRORS_HPP +#define BOOST_MULTI_INDEX_SAFE_MODE_ERRORS_HPP + +#if defined(_MSC_VER)&&(_MSC_VER>=1200) +#pragma once +#endif + +namespace boost{ + +namespace multi_index{ + +namespace safe_mode{ + +/* Error codes for Boost.MultiIndex safe mode. These go in a separate + * header so that the user can include it when redefining + * BOOST_MULTI_INDEX_SAFE_MODE_ASSERT prior to the inclusion of + * any other header of Boost.MultiIndex. + */ + +enum error_code +{ + invalid_iterator=0, + not_dereferenceable_iterator, + not_incrementable_iterator, + not_decrementable_iterator, + not_owner, + not_same_owner, + invalid_range, + inside_range, + out_of_bounds, + same_container +}; + +} /* namespace multi_index::safe_mode */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/sequenced_index.hpp b/3rdParty/Boost/src/boost/multi_index/sequenced_index.hpp new file mode 100644 index 0000000..8e09115 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/sequenced_index.hpp @@ -0,0 +1,922 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_SEQUENCED_INDEX_HPP +#define BOOST_MULTI_INDEX_SEQUENCED_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 <boost/call_traits.hpp> +#include <boost/detail/allocator_utilities.hpp> +#include <boost/detail/no_exceptions_support.hpp> +#include <boost/detail/workaround.hpp> +#include <boost/iterator/reverse_iterator.hpp> +#include <boost/mpl/bool.hpp> +#include <boost/mpl/not.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/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/seq_index_node.hpp> +#include <boost/multi_index/detail/seq_index_ops.hpp> +#include <boost/multi_index/sequenced_index_fwd.hpp> +#include <boost/tuple/tuple.hpp> +#include <boost/type_traits/is_integral.hpp> +#include <cstddef> +#include <functional> +#include <utility> + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) +#include <boost/bind.hpp> +#endif + +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING) +#define BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT \ + detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)= \ + detail::make_obj_guard(*this,&sequenced_index::check_invariant_); \ + BOOST_JOIN(check_invariant_,__LINE__).touch(); +#else +#define BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT +#endif + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* sequenced_index adds a layer of sequenced indexing to a given Super */ + +template<typename SuperMeta,typename TagList> +class sequenced_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< + sequenced_index_node<typename SuperMeta::type::node_type> >, + sequenced_index<SuperMeta,TagList> > +#else + ,public safe_mode::safe_container< + sequenced_index<SuperMeta,TagList> > +#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 sequenced_index_node< + typename super::node_type> node_type; + +private: + typedef typename node_type::impl_type node_impl_type; + +public: + /* types */ + + typedef typename node_type::value_type value_type; + typedef tuples::null_type 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>, + sequenced_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, + sequenced_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>, + sequenced_index> safe_super; +#else + typedef safe_mode::safe_container< + sequenced_index> safe_super; +#endif +#endif + + typedef typename call_traits<value_type>::param_type value_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. + */ + + sequenced_index<SuperMeta,TagList>& operator=( + const sequenced_index<SuperMeta,TagList>& x) + { + this->final()=x.final(); + return *this; + } + + template <class InputIterator> + void assign(InputIterator first,InputIterator last) + { + assign_iter(first,last,mpl::not_<is_integral<InputIterator> >()); + } + + void assign(size_type n,value_param_type value) + { + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + clear(); + for(size_type i=0;i<n;++i)push_back(value); + } + + allocator_type get_allocator()const + { + return this->final().get_allocator(); + } + + /* iterators */ + + iterator begin() + {return make_iterator(node_type::from_impl(header()->next()));} + const_iterator begin()const + {return make_iterator(node_type::from_impl(header()->next()));} + 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_();} + + void resize(size_type n,value_param_type x=value_type()) + { + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + if(n>size())insert(end(),n-size(),x); + else if(n<size()){ + iterator it; + if(n<=size()/2){ + it=begin(); + std::advance(it,n); + } + else{ + it=end(); + for(size_type m=size()-n;m--;--it){} + } + erase(it,end()); + } + } + + /* access: no non-const versions provided as sequenced_index + * handles const elements. + */ + + const_reference front()const{return *begin();} + const_reference back()const{return *--end();} + + /* modifiers */ + + std::pair<iterator,bool> push_front(value_param_type x) + {return insert(begin(),x);} + void pop_front(){erase(begin());} + std::pair<iterator,bool> push_back(value_param_type x) + {return insert(end(),x);} + void pop_back(){erase(--end());} + + std::pair<iterator,bool> 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_SEQ_INDEX_CHECK_INVARIANT; + std::pair<final_node_type*,bool> p=this->final_insert_(x); + if(p.second&&position.get_node()!=header()){ + relink(position.get_node(),p.first); + } + return std::pair<iterator,bool>(make_iterator(p.first),p.second); + } + + void insert(iterator position,size_type n,value_param_type x) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + for(size_type i=0;i<n;++i)insert(position,x); + } + + template<typename InputIterator> + void insert(iterator position,InputIterator first,InputIterator last) + { + insert_iter(position,first,last,mpl::not_<is_integral<InputIterator> >()); + } + + 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_SEQ_INDEX_CHECK_INVARIANT; + this->final_erase_(static_cast<final_node_type*>(position++.get_node())); + return position; + } + + 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_SEQ_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_SEQ_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_SEQ_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_SEQ_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())); + } + + void swap(sequenced_index<SuperMeta,TagList>& x) + { + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + this->final_swap_(x.final()); + } + + void clear() + { + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + this->final_clear_(); + } + + /* list operations */ + + void splice(iterator position,sequenced_index<SuperMeta,TagList>& x) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); + BOOST_MULTI_INDEX_CHECK_DIFFERENT_CONTAINER(*this,x); + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + iterator first=x.begin(),last=x.end(); + while(first!=last){ + if(insert(position,*first).second)first=x.erase(first); + else ++first; + } + } + + void splice(iterator position,sequenced_index<SuperMeta,TagList>& x,iterator i) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(i); + BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(i); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(i,x); + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + if(&x==this){ + if(position!=i)relink(position.get_node(),i.get_node()); + } + else{ + if(insert(position,*i).second){ + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + /* MSVC++ 6.0 optimizer has a hard time with safe mode, and the following + * workaround is needed. Left it for all compilers as it does no + * harm. + */ + i.detach(); + x.erase(x.make_iterator(i.get_node())); +#else + x.erase(i); +#endif + + } + } + } + + void splice( + iterator position,sequenced_index<SuperMeta,TagList>& x, + iterator first,iterator last) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first); + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,x); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,x); + BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last); + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + if(&x==this){ + BOOST_MULTI_INDEX_CHECK_OUTSIDE_RANGE(position,first,last); + if(position!=last)relink( + position.get_node(),first.get_node(),last.get_node()); + } + else{ + while(first!=last){ + if(insert(position,*first).second)first=x.erase(first); + else ++first; + } + } + } + + void remove(value_param_type value) + { + sequenced_index_remove( + *this,std::bind2nd(std::equal_to<value_type>(),value)); + } + + template<typename Predicate> + void remove_if(Predicate pred) + { + sequenced_index_remove(*this,pred); + } + + void unique() + { + sequenced_index_unique(*this,std::equal_to<value_type>()); + } + + template <class BinaryPredicate> + void unique(BinaryPredicate binary_pred) + { + sequenced_index_unique(*this,binary_pred); + } + + void merge(sequenced_index<SuperMeta,TagList>& x) + { + sequenced_index_merge(*this,x,std::less<value_type>()); + } + + template <typename Compare> + void merge(sequenced_index<SuperMeta,TagList>& x,Compare comp) + { + sequenced_index_merge(*this,x,comp); + } + + void sort() + { + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + sequenced_index_sort(header(),std::less<value_type>()); + } + + template <typename Compare> + void sort(Compare comp) + { + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + sequenced_index_sort(header(),comp); + } + + void reverse() + { + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + node_impl_type::reverse(header()->impl()); + } + + /* rearrange operations */ + + void relocate(iterator position,iterator i) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(i); + BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(i); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(i,*this); + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + if(position!=i)relink(position.get_node(),i.get_node()); + } + + void relocate(iterator position,iterator first,iterator last) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); + 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_CHECK_OUTSIDE_RANGE(position,first,last); + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + if(position!=last)relink( + position.get_node(),first.get_node(),last.get_node()); + } + + template<typename InputIterator> + void rearrange(InputIterator first) + { + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + node_type* pos=header(); + for(size_type s=size();s--;){ + const value_type& v=*first++; + relink(pos,node_from_value<node_type>(&v)); + } + } + +BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: + sequenced_index(const ctor_args_list& args_list,const allocator_type& al): + super(args_list.get_tail(),al) + { + empty_initialize(); + } + + sequenced_index(const sequenced_index<SuperMeta,TagList>& x): + super(x) + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + ,safe_super() +#endif + + { + /* The actual copying takes place in subsequent call to copy_(). + */ + } + + ~sequenced_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<sequenced_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 sequenced_index<SuperMeta,TagList>& x,const copy_map_type& map) + { + node_type* org=x.header(); + node_type* cpy=header(); + do{ + node_type* next_org=node_type::from_impl(org->next()); + node_type* next_cpy=map.find(static_cast<final_node_type*>(next_org)); + cpy->next()=next_cpy->impl(); + next_cpy->prior()=cpy->impl(); + org=next_org; + cpy=next_cpy; + }while(org!=x.header()); + + super::copy_(x,map); + } + + node_type* insert_(value_param_type v,node_type* x) + { + node_type* res=static_cast<node_type*>(super::insert_(v,x)); + if(res==x)link(x); + return res; + } + + node_type* insert_(value_param_type v,node_type* position,node_type* x) + { + node_type* res=static_cast<node_type*>(super::insert_(v,position,x)); + if(res==x)link(x); + return res; + } + + void erase_(node_type* x) + { + unlink(x); + super::erase_(x); + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + detach_iterators(x); +#endif + } + + void delete_all_nodes_() + { + for(node_type* x=node_type::from_impl(header()->next());x!=header();){ + node_type* y=node_type::from_impl(x->next()); + this->final_delete_node_(static_cast<final_node_type*>(x)); + x=y; + } + } + + void clear_() + { + super::clear_(); + empty_initialize(); + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + safe_super::detach_dereferenceable_iterators(); +#endif + } + + void swap_(sequenced_index<SuperMeta,TagList>& x) + { +#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) + { + return super::replace_(v,x); + } + + bool modify_(node_type* x) + { + BOOST_TRY{ + if(!super::modify_(x)){ + unlink(x); + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + detach_iterators(x); +#endif + + return false; + } + else return true; + } + BOOST_CATCH(...){ + unlink(x); + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + detach_iterators(x); +#endif + + BOOST_RETHROW; + } + BOOST_CATCH_END + } + + bool modify_rollback_(node_type* x) + { + return super::modify_rollback_(x); + } + +#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 + { + sm.save(begin(),end(),ar,version); + super::save_(ar,version,sm); + } + + template<typename Archive> + void load_( + Archive& ar,const unsigned int version,const index_loader_type& lm) + { + lm.load( + ::boost::bind(&sequenced_index::rearranger,this,_1,_2), + ar,version); + super::load_(ar,version,lm); + } +#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()->next()!=header()->impl()|| + header()->prior()!=header()->impl())return false; + } + else{ + size_type s=0; + for(const_iterator it=begin(),it_end=end();it!=it_end;++it,++s){ + if(it.get_node()->next()->prior()!=it.get_node()->impl())return false; + if(it.get_node()->prior()->next()!=it.get_node()->impl())return false; + } + if(s!=size())return false; + } + + return super::invariant_(); + } + + /* This forwarding function eases things for the boost::mem_fn construct + * in BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT. Actually, + * final_check_invariant is already an inherited member function of index. + */ + void check_invariant_()const{this->final_check_invariant_();} +#endif + +private: + node_type* header()const{return this->final_header();} + + void empty_initialize() + { + header()->prior()=header()->next()=header()->impl(); + } + + void link(node_type* x) + { + node_impl_type::link(x->impl(),header()->impl()); + }; + + static void unlink(node_type* x) + { + node_impl_type::unlink(x->impl()); + } + + static void relink(node_type* position,node_type* x) + { + node_impl_type::relink(position->impl(),x->impl()); + } + + static void relink(node_type* position,node_type* first,node_type* last) + { + node_impl_type::relink( + position->impl(),first->impl(),last->impl()); + } + +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) + void rearranger(node_type* position,node_type *x) + { + if(!position)position=header(); + node_type::increment(position); + if(position!=x)relink(position,x); + } +#endif + +#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 <class InputIterator> + void assign_iter(InputIterator first,InputIterator last,mpl::true_) + { + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + clear(); + for(;first!=last;++first)push_back(*first); + } + + void assign_iter(size_type n,value_param_type value,mpl::false_) + { + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + clear(); + for(size_type i=0;i<n;++i)push_back(value); + } + + template<typename InputIterator> + void insert_iter( + iterator position,InputIterator first,InputIterator last,mpl::true_) + { + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + for(;first!=last;++first)insert(position,*first); + } + + void insert_iter( + iterator position,size_type n,value_param_type x,mpl::false_) + { + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); + BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT; + for(size_type i=0;i<n;++i)insert(position,x); + } + +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\ + BOOST_WORKAROUND(__MWERKS__,<=0x3003) +#pragma parse_mfunc_templ reset +#endif +}; + +/* comparison */ + +template< + typename SuperMeta1,typename TagList1, + typename SuperMeta2,typename TagList2 +> +bool operator==( + const sequenced_index<SuperMeta1,TagList1>& x, + const sequenced_index<SuperMeta2,TagList2>& y) +{ + return x.size()==y.size()&&std::equal(x.begin(),x.end(),y.begin()); +} + +template< + typename SuperMeta1,typename TagList1, + typename SuperMeta2,typename TagList2 +> +bool operator<( + const sequenced_index<SuperMeta1,TagList1>& x, + const sequenced_index<SuperMeta2,TagList2>& y) +{ + return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end()); +} + +template< + typename SuperMeta1,typename TagList1, + typename SuperMeta2,typename TagList2 +> +bool operator!=( + const sequenced_index<SuperMeta1,TagList1>& x, + const sequenced_index<SuperMeta2,TagList2>& y) +{ + return !(x==y); +} + +template< + typename SuperMeta1,typename TagList1, + typename SuperMeta2,typename TagList2 +> +bool operator>( + const sequenced_index<SuperMeta1,TagList1>& x, + const sequenced_index<SuperMeta2,TagList2>& y) +{ + return y<x; +} + +template< + typename SuperMeta1,typename TagList1, + typename SuperMeta2,typename TagList2 +> +bool operator>=( + const sequenced_index<SuperMeta1,TagList1>& x, + const sequenced_index<SuperMeta2,TagList2>& y) +{ + return !(x<y); +} + +template< + typename SuperMeta1,typename TagList1, + typename SuperMeta2,typename TagList2 +> +bool operator<=( + const sequenced_index<SuperMeta1,TagList1>& x, + const sequenced_index<SuperMeta2,TagList2>& y) +{ + return !(x>y); +} + +/* specialized algorithms */ + +template<typename SuperMeta,typename TagList> +void swap( + sequenced_index<SuperMeta,TagList>& x, + sequenced_index<SuperMeta,TagList>& y) +{ + x.swap(y); +} + +} /* namespace multi_index::detail */ + +/* sequenced index specifier */ + +template <typename TagList> +struct sequenced +{ + BOOST_STATIC_ASSERT(detail::is_tag<TagList>::value); + + template<typename Super> + struct node_class + { + typedef detail::sequenced_index_node<Super> type; + }; + + template<typename SuperMeta> + struct index_class + { + typedef detail::sequenced_index<SuperMeta,typename TagList::type> type; + }; +}; + +} /* namespace multi_index */ + +} /* namespace boost */ + +#undef BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/sequenced_index_fwd.hpp b/3rdParty/Boost/src/boost/multi_index/sequenced_index_fwd.hpp new file mode 100644 index 0000000..5211390 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/sequenced_index_fwd.hpp @@ -0,0 +1,91 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_SEQUENCED_INDEX_FWD_HPP +#define BOOST_MULTI_INDEX_SEQUENCED_INDEX_FWD_HPP + +#if defined(_MSC_VER)&&(_MSC_VER>=1200) +#pragma once +#endif + +#include <boost/multi_index/tag.hpp> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +template<typename SuperMeta,typename TagList> +class sequenced_index; + +template< + typename SuperMeta1,typename TagList1, + typename SuperMeta2,typename TagList2 +> +bool operator==( + const sequenced_index<SuperMeta1,TagList1>& x, + const sequenced_index<SuperMeta2,TagList2>& y); + +template< + typename SuperMeta1,typename TagList1, + typename SuperMeta2,typename TagList2 +> +bool operator<( + const sequenced_index<SuperMeta1,TagList1>& x, + const sequenced_index<SuperMeta2,TagList2>& y); + +template< + typename SuperMeta1,typename TagList1, + typename SuperMeta2,typename TagList2 +> +bool operator!=( + const sequenced_index<SuperMeta1,TagList1>& x, + const sequenced_index<SuperMeta2,TagList2>& y); + +template< + typename SuperMeta1,typename TagList1, + typename SuperMeta2,typename TagList2 +> +bool operator>( + const sequenced_index<SuperMeta1,TagList1>& x, + const sequenced_index<SuperMeta2,TagList2>& y); + +template< + typename SuperMeta1,typename TagList1, + typename SuperMeta2,typename TagList2 +> +bool operator>=( + const sequenced_index<SuperMeta1,TagList1>& x, + const sequenced_index<SuperMeta2,TagList2>& y); + +template< + typename SuperMeta1,typename TagList1, + typename SuperMeta2,typename TagList2 +> +bool operator<=( + const sequenced_index<SuperMeta1,TagList1>& x, + const sequenced_index<SuperMeta2,TagList2>& y); + +template<typename SuperMeta,typename TagList> +void swap( + sequenced_index<SuperMeta,TagList>& x, + sequenced_index<SuperMeta,TagList>& y); + +} /* namespace multi_index::detail */ + +/* index specifiers */ + +template <typename TagList=tag<> > +struct sequenced; + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif diff --git a/3rdParty/Boost/src/boost/multi_index/tag.hpp b/3rdParty/Boost/src/boost/multi_index/tag.hpp new file mode 100644 index 0000000..ba7cab4 --- /dev/null +++ b/3rdParty/Boost/src/boost/multi_index/tag.hpp @@ -0,0 +1,92 @@ +/* Copyright 2003-2008 Joaquin M Lopez Munoz. + * Distributed under the Boost Software License, Version 1.0. + * (See accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org/libs/multi_index for library home page. + */ + +#ifndef BOOST_MULTI_INDEX_TAG_HPP +#define BOOST_MULTI_INDEX_TAG_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 <boost/multi_index/detail/no_duplicate_tags.hpp> +#include <boost/mpl/identity.hpp> +#include <boost/mpl/transform.hpp> +#include <boost/mpl/vector.hpp> +#include <boost/preprocessor/facilities/intercept.hpp> +#include <boost/preprocessor/repetition/enum_binary_params.hpp> +#include <boost/preprocessor/repetition/enum_params.hpp> +#include <boost/static_assert.hpp> +#include <boost/type_traits/is_base_and_derived.hpp> + +/* A wrapper of mpl::vector used to hide MPL from the user. + * tag contains types used as tag names for indices in get() functions. + */ + +/* This user_definable macro limits the number of elements of a tag; + * useful for shortening resulting symbol names (MSVC++ 6.0, for instance, + * has problems coping with very long symbol names.) + */ + +#if !defined(BOOST_MULTI_INDEX_LIMIT_TAG_SIZE) +#if defined(BOOST_MSVC)&&(BOOST_MSVC<1300) +#define BOOST_MULTI_INDEX_LIMIT_TAG_SIZE 3 +#else +#define BOOST_MULTI_INDEX_LIMIT_TAG_SIZE BOOST_MPL_LIMIT_VECTOR_SIZE +#endif +#endif + +#if BOOST_MULTI_INDEX_LIMIT_TAG_SIZE<BOOST_MPL_LIMIT_VECTOR_SIZE +#define BOOST_MULTI_INDEX_TAG_SIZE BOOST_MULTI_INDEX_LIMIT_TAG_SIZE +#else +#define BOOST_MULTI_INDEX_TAG_SIZE BOOST_MPL_LIMIT_VECTOR_SIZE +#endif + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +struct tag_marker{}; + +template<typename T> +struct is_tag +{ + BOOST_STATIC_CONSTANT(bool,value=(is_base_and_derived<tag_marker,T>::value)); +}; + +} /* namespace multi_index::detail */ + +template< + BOOST_PP_ENUM_BINARY_PARAMS( + BOOST_MULTI_INDEX_TAG_SIZE, + typename T, + =mpl::na BOOST_PP_INTERCEPT) +> +struct tag:private detail::tag_marker +{ + /* The mpl::transform pass produces shorter symbols (without + * trailing mpl::na's.) + */ + + typedef typename mpl::transform< + mpl::vector<BOOST_PP_ENUM_PARAMS(BOOST_MULTI_INDEX_TAG_SIZE,T)>, + mpl::identity<mpl::_1> + >::type type; + + BOOST_STATIC_ASSERT(detail::no_duplicate_tags<type>::value); +}; + +} /* namespace multi_index */ + +} /* namespace boost */ + +#undef BOOST_MULTI_INDEX_TAG_SIZE + +#endif |