summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat (limited to '3rdParty/Boost/src/boost/detail/binary_search.hpp')
-rw-r--r--3rdParty/Boost/src/boost/detail/binary_search.hpp216
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_