diff options
author | Remko Tronçon <git@el-tramo.be> | 2010-05-06 17:44:27 (GMT) |
---|---|---|
committer | Remko Tronçon <git@el-tramo.be> | 2010-05-06 17:44:27 (GMT) |
commit | d76ada0ab59634e3333f9eb5a92d0e850f60d7bf (patch) | |
tree | 5eaae441173fad2ec19ba67d6589f28ecd740991 /3rdParty/Boost/src/boost/detail/binary_search.hpp | |
parent | 6f49e5abee37d37b351d68c01374232eccdac458 (diff) | |
download | swift-contrib-d76ada0ab59634e3333f9eb5a92d0e850f60d7bf.zip swift-contrib-d76ada0ab59634e3333f9eb5a92d0e850f60d7bf.tar.bz2 |
Updated Boost to 1.43.0.
Diffstat (limited to '3rdParty/Boost/src/boost/detail/binary_search.hpp')
-rw-r--r-- | 3rdParty/Boost/src/boost/detail/binary_search.hpp | 216 |
1 files changed, 0 insertions, 216 deletions
diff --git a/3rdParty/Boost/src/boost/detail/binary_search.hpp b/3rdParty/Boost/src/boost/detail/binary_search.hpp deleted file mode 100644 index 3dca9b6..0000000 --- a/3rdParty/Boost/src/boost/detail/binary_search.hpp +++ /dev/null @@ -1,216 +0,0 @@ -// Copyright (c) 2000 David Abrahams. -// 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) -// -// 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. -// -// Copyright (c) 1996 -// 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. -// -#ifndef BINARY_SEARCH_DWA_122600_H_ -# define BINARY_SEARCH_DWA_122600_H_ - -# include <boost/detail/iterator.hpp> -# include <utility> - -namespace boost { namespace detail { - -template <class ForwardIter, class Tp> -ForwardIter lower_bound(ForwardIter first, ForwardIter last, - const Tp& val) -{ - typedef detail::iterator_traits<ForwardIter> traits; - - typename traits::difference_type len = boost::detail::distance(first, last); - typename traits::difference_type half; - ForwardIter middle; - - while (len > 0) { - half = len >> 1; - middle = first; - std::advance(middle, half); - if (*middle < val) { - first = middle; - ++first; - len = len - half - 1; - } - else - len = half; - } - return first; -} - -template <class ForwardIter, class Tp, class Compare> -ForwardIter lower_bound(ForwardIter first, ForwardIter last, - const Tp& val, Compare comp) -{ - typedef detail::iterator_traits<ForwardIter> traits; - - typename traits::difference_type len = boost::detail::distance(first, last); - typename traits::difference_type half; - ForwardIter middle; - - while (len > 0) { - half = len >> 1; - middle = first; - std::advance(middle, half); - if (comp(*middle, val)) { - first = middle; - ++first; - len = len - half - 1; - } - else - len = half; - } - return first; -} - -template <class ForwardIter, class Tp> -ForwardIter upper_bound(ForwardIter first, ForwardIter last, - const Tp& val) -{ - typedef detail::iterator_traits<ForwardIter> traits; - - typename traits::difference_type len = boost::detail::distance(first, last); - typename traits::difference_type half; - ForwardIter middle; - - while (len > 0) { - half = len >> 1; - middle = first; - std::advance(middle, half); - if (val < *middle) - len = half; - else { - first = middle; - ++first; - len = len - half - 1; - } - } - return first; -} - -template <class ForwardIter, class Tp, class Compare> -ForwardIter upper_bound(ForwardIter first, ForwardIter last, - const Tp& val, Compare comp) -{ - typedef detail::iterator_traits<ForwardIter> traits; - - typename traits::difference_type len = boost::detail::distance(first, last); - typename traits::difference_type half; - ForwardIter middle; - - while (len > 0) { - half = len >> 1; - middle = first; - std::advance(middle, half); - if (comp(val, *middle)) - len = half; - else { - first = middle; - ++first; - len = len - half - 1; - } - } - return first; -} - -template <class ForwardIter, class Tp> -std::pair<ForwardIter, ForwardIter> -equal_range(ForwardIter first, ForwardIter last, const Tp& val) -{ - typedef detail::iterator_traits<ForwardIter> traits; - - typename traits::difference_type len = boost::detail::distance(first, last); - typename traits::difference_type half; - ForwardIter middle, left, right; - - while (len > 0) { - half = len >> 1; - middle = first; - std::advance(middle, half); - if (*middle < val) { - first = middle; - ++first; - len = len - half - 1; - } - else if (val < *middle) - len = half; - else { - left = boost::detail::lower_bound(first, middle, val); - std::advance(first, len); - right = boost::detail::upper_bound(++middle, first, val); - return std::pair<ForwardIter, ForwardIter>(left, right); - } - } - return std::pair<ForwardIter, ForwardIter>(first, first); -} - -template <class ForwardIter, class Tp, class Compare> -std::pair<ForwardIter, ForwardIter> -equal_range(ForwardIter first, ForwardIter last, const Tp& val, - Compare comp) -{ - typedef detail::iterator_traits<ForwardIter> traits; - - typename traits::difference_type len = boost::detail::distance(first, last); - typename traits::difference_type half; - ForwardIter middle, left, right; - - while (len > 0) { - half = len >> 1; - middle = first; - std::advance(middle, half); - if (comp(*middle, val)) { - first = middle; - ++first; - len = len - half - 1; - } - else if (comp(val, *middle)) - len = half; - else { - left = boost::detail::lower_bound(first, middle, val, comp); - std::advance(first, len); - right = boost::detail::upper_bound(++middle, first, val, comp); - return std::pair<ForwardIter, ForwardIter>(left, right); - } - } - return std::pair<ForwardIter, ForwardIter>(first, first); -} - -template <class ForwardIter, class Tp> -bool binary_search(ForwardIter first, ForwardIter last, - const Tp& val) { - ForwardIter i = boost::detail::lower_bound(first, last, val); - return i != last && !(val < *i); -} - -template <class ForwardIter, class Tp, class Compare> -bool binary_search(ForwardIter first, ForwardIter last, - const Tp& val, - Compare comp) { - ForwardIter i = boost::detail::lower_bound(first, last, val, comp); - return i != last && !comp(val, *i); -} - -}} // namespace boost::detail - -#endif // BINARY_SEARCH_DWA_122600_H_ |