Swift
summaryrefslogtreecommitdiffstats
path: root/3rdParty/Boost/src/boost/detail/binary_search.hpp
diff options
context:
space:
mode:
authorRemko Tronçon <git@el-tramo.be>2010-03-28 15:46:49 (GMT)
committerRemko Tronçon <git@el-tramo.be>2010-03-28 15:46:49 (GMT)
commitf53a1ef582494458301b97bf6e546be52d7ff7e8 (patch)
tree7571b5cbcbd8a8f1dd1c966c9045b6cb69f0e295 /3rdParty/Boost/src/boost/detail/binary_search.hpp
parent638345680d72ca6acaf123f2c8c1c391f696e371 (diff)
downloadswift-contrib-f53a1ef582494458301b97bf6e546be52d7ff7e8.zip
swift-contrib-f53a1ef582494458301b97bf6e546be52d7ff7e8.tar.bz2
Moving submodule contents back.
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, 216 insertions, 0 deletions
diff --git a/3rdParty/Boost/src/boost/detail/binary_search.hpp b/3rdParty/Boost/src/boost/detail/binary_search.hpp
new file mode 100644
index 0000000..3dca9b6
--- /dev/null
+++ b/3rdParty/Boost/src/boost/detail/binary_search.hpp
@@ -0,0 +1,216 @@
+// 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_