Swift
summaryrefslogtreecommitdiffstats
path: root/3rdParty/Boost/src/boost/detail/binary_search.hpp
diff options
context:
space:
mode:
authorTobias Markmann <tm@ayena.de>2016-04-05 13:17:19 (GMT)
committerTobias Markmann <tm@ayena.de>2016-04-05 19:42:39 (GMT)
commit2b560b129b7a31fc8cc07f618e763c95a22bf832 (patch)
tree73e72cdc758b79d01485dc28dcedd48b26859ae8 /3rdParty/Boost/src/boost/detail/binary_search.hpp
parent3c560e31b0f168da917e8d566db01fd1cd997d86 (diff)
downloadswift-2b560b129b7a31fc8cc07f618e763c95a22bf832.zip
swift-2b560b129b7a31fc8cc07f618e763c95a22bf832.tar.bz2
Migrate to Boost.Signals2 from Boost.Signals
Boost.Signals was deprecated and is not improved further. This patch removes Boost.Signals from 3rdParty and adds Boost.Signals2 and its dependencies. Also removed the Qt signals compatibility file Swiften/Base/boost_bsignals.h. Test-Information: Build and ran unit tests on OS X 10.11.4. Confirmed successful login using Swift client. Change-Id: Ie6e3b2d15aac2462cda95401582f5287a479fb54
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_