summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat (limited to '3rdParty/Boost/src/boost/multi_index/detail/seq_index_ops.hpp')
-rw-r--r--3rdParty/Boost/src/boost/multi_index/detail/seq_index_ops.hpp200
1 files changed, 0 insertions, 200 deletions
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
deleted file mode 100644
index 8135074..0000000
--- a/3rdParty/Boost/src/boost/multi_index/detail/seq_index_ops.hpp
+++ /dev/null
@@ -1,200 +0,0 @@
-/* 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