diff options
Diffstat (limited to 'src/third_party/boost/boost/detail/binary_search.hpp')
-rw-r--r-- | src/third_party/boost/boost/detail/binary_search.hpp | 216 |
1 files changed, 0 insertions, 216 deletions
diff --git a/src/third_party/boost/boost/detail/binary_search.hpp b/src/third_party/boost/boost/detail/binary_search.hpp deleted file mode 100644 index 3dca9b65092..00000000000 --- a/src/third_party/boost/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_ |