diff options
Diffstat (limited to 'src/third_party/boost-1.60.0/boost/multi_index/detail/ord_index_ops.hpp')
-rw-r--r-- | src/third_party/boost-1.60.0/boost/multi_index/detail/ord_index_ops.hpp | 266 |
1 files changed, 266 insertions, 0 deletions
diff --git a/src/third_party/boost-1.60.0/boost/multi_index/detail/ord_index_ops.hpp b/src/third_party/boost-1.60.0/boost/multi_index/detail/ord_index_ops.hpp new file mode 100644 index 00000000000..84d5cacae19 --- /dev/null +++ b/src/third_party/boost-1.60.0/boost/multi_index/detail/ord_index_ops.hpp @@ -0,0 +1,266 @@ +/* Copyright 2003-2014 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) +#pragma once +#endif + +#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ +#include <boost/mpl/and.hpp> +#include <boost/multi_index/detail/promotes_arg.hpp> +#include <utility> + +namespace boost{ + +namespace multi_index{ + +namespace detail{ + +/* Common code for index memfuns having templatized and + * non-templatized versions. + * Implementation note: When CompatibleKey is consistently promoted to + * KeyFromValue::result_type for comparison, the promotion is made once in + * advance to increase efficiency. + */ + +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) +{ + typedef typename KeyFromValue::result_type key_type; + + return ordered_index_find( + top,y,key,x,comp, + mpl::and_< + promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>, + promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey> >()); +} + +template< + typename Node,typename KeyFromValue, + typename CompatibleCompare +> +inline Node* ordered_index_find( + Node* top,Node* y,const KeyFromValue& key, + const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x, + const CompatibleCompare& comp,mpl::true_) +{ + return ordered_index_find(top,y,key,x,comp,mpl::false_()); +} + +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,mpl::false_) +{ + 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) +{ + typedef typename KeyFromValue::result_type key_type; + + return ordered_index_lower_bound( + top,y,key,x,comp, + promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey>()); +} + +template< + typename Node,typename KeyFromValue, + typename CompatibleCompare +> +inline Node* ordered_index_lower_bound( + Node* top,Node* y,const KeyFromValue& key, + const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x, + const CompatibleCompare& comp,mpl::true_) +{ + return ordered_index_lower_bound(top,y,key,x,comp,mpl::false_()); +} + +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,mpl::false_) +{ + 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) +{ + typedef typename KeyFromValue::result_type key_type; + + return ordered_index_upper_bound( + top,y,key,x,comp, + promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>()); +} + +template< + typename Node,typename KeyFromValue, + typename CompatibleCompare +> +inline Node* ordered_index_upper_bound( + Node* top,Node* y,const KeyFromValue& key, + const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x, + const CompatibleCompare& comp,mpl::true_) +{ + return ordered_index_upper_bound(top,y,key,x,comp,mpl::false_()); +} + +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,mpl::false_) +{ + 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) +{ + typedef typename KeyFromValue::result_type key_type; + + return ordered_index_equal_range( + top,y,key,x,comp, + mpl::and_< + promotes_1st_arg<CompatibleCompare,CompatibleKey,key_type>, + promotes_2nd_arg<CompatibleCompare,key_type,CompatibleKey> >()); +} + +template< + typename Node,typename KeyFromValue, + typename CompatibleCompare +> +inline std::pair<Node*,Node*> ordered_index_equal_range( + Node* top,Node* y,const KeyFromValue& key, + const BOOST_DEDUCED_TYPENAME KeyFromValue::result_type& x, + const CompatibleCompare& comp,mpl::true_) +{ + return ordered_index_equal_range(top,y,key,x,comp,mpl::false_()); +} + +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,mpl::false_) +{ + 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,mpl::false_()), + ordered_index_upper_bound( + Node::from_impl(top->right()),y,key,x,comp,mpl::false_())); + } + } + + return std::pair<Node*,Node*>(y,y); +} + +} /* namespace multi_index::detail */ + +} /* namespace multi_index */ + +} /* namespace boost */ + +#endif |