1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/detail/binary_search.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,216 @@
1.4 +// Copyright (c) 2000 David Abrahams.
1.5 +// Distributed under the Boost Software License, Version 1.0.
1.6 +// (See accompanying file LICENSE_1_0.txt or copy at
1.7 +// http://www.boost.org/LICENSE_1_0.txt)
1.8 +//
1.9 +// Copyright (c) 1994
1.10 +// Hewlett-Packard Company
1.11 +//
1.12 +// Permission to use, copy, modify, distribute and sell this software
1.13 +// and its documentation for any purpose is hereby granted without fee,
1.14 +// provided that the above copyright notice appear in all copies and
1.15 +// that both that copyright notice and this permission notice appear
1.16 +// in supporting documentation. Hewlett-Packard Company makes no
1.17 +// representations about the suitability of this software for any
1.18 +// purpose. It is provided "as is" without express or implied warranty.
1.19 +//
1.20 +// Copyright (c) 1996
1.21 +// Silicon Graphics Computer Systems, Inc.
1.22 +//
1.23 +// Permission to use, copy, modify, distribute and sell this software
1.24 +// and its documentation for any purpose is hereby granted without fee,
1.25 +// provided that the above copyright notice appear in all copies and
1.26 +// that both that copyright notice and this permission notice appear
1.27 +// in supporting documentation. Silicon Graphics makes no
1.28 +// representations about the suitability of this software for any
1.29 +// purpose. It is provided "as is" without express or implied warranty.
1.30 +//
1.31 +#ifndef BINARY_SEARCH_DWA_122600_H_
1.32 +# define BINARY_SEARCH_DWA_122600_H_
1.33 +
1.34 +# include <boost/detail/iterator.hpp>
1.35 +# include <utility>
1.36 +
1.37 +namespace boost { namespace detail {
1.38 +
1.39 +template <class ForwardIter, class Tp>
1.40 +ForwardIter lower_bound(ForwardIter first, ForwardIter last,
1.41 + const Tp& val)
1.42 +{
1.43 + typedef detail::iterator_traits<ForwardIter> traits;
1.44 +
1.45 + typename traits::difference_type len = boost::detail::distance(first, last);
1.46 + typename traits::difference_type half;
1.47 + ForwardIter middle;
1.48 +
1.49 + while (len > 0) {
1.50 + half = len >> 1;
1.51 + middle = first;
1.52 + std::advance(middle, half);
1.53 + if (*middle < val) {
1.54 + first = middle;
1.55 + ++first;
1.56 + len = len - half - 1;
1.57 + }
1.58 + else
1.59 + len = half;
1.60 + }
1.61 + return first;
1.62 +}
1.63 +
1.64 +template <class ForwardIter, class Tp, class Compare>
1.65 +ForwardIter lower_bound(ForwardIter first, ForwardIter last,
1.66 + const Tp& val, Compare comp)
1.67 +{
1.68 + typedef detail::iterator_traits<ForwardIter> traits;
1.69 +
1.70 + typename traits::difference_type len = boost::detail::distance(first, last);
1.71 + typename traits::difference_type half;
1.72 + ForwardIter middle;
1.73 +
1.74 + while (len > 0) {
1.75 + half = len >> 1;
1.76 + middle = first;
1.77 + std::advance(middle, half);
1.78 + if (comp(*middle, val)) {
1.79 + first = middle;
1.80 + ++first;
1.81 + len = len - half - 1;
1.82 + }
1.83 + else
1.84 + len = half;
1.85 + }
1.86 + return first;
1.87 +}
1.88 +
1.89 +template <class ForwardIter, class Tp>
1.90 +ForwardIter upper_bound(ForwardIter first, ForwardIter last,
1.91 + const Tp& val)
1.92 +{
1.93 + typedef detail::iterator_traits<ForwardIter> traits;
1.94 +
1.95 + typename traits::difference_type len = boost::detail::distance(first, last);
1.96 + typename traits::difference_type half;
1.97 + ForwardIter middle;
1.98 +
1.99 + while (len > 0) {
1.100 + half = len >> 1;
1.101 + middle = first;
1.102 + std::advance(middle, half);
1.103 + if (val < *middle)
1.104 + len = half;
1.105 + else {
1.106 + first = middle;
1.107 + ++first;
1.108 + len = len - half - 1;
1.109 + }
1.110 + }
1.111 + return first;
1.112 +}
1.113 +
1.114 +template <class ForwardIter, class Tp, class Compare>
1.115 +ForwardIter upper_bound(ForwardIter first, ForwardIter last,
1.116 + const Tp& val, Compare comp)
1.117 +{
1.118 + typedef detail::iterator_traits<ForwardIter> traits;
1.119 +
1.120 + typename traits::difference_type len = boost::detail::distance(first, last);
1.121 + typename traits::difference_type half;
1.122 + ForwardIter middle;
1.123 +
1.124 + while (len > 0) {
1.125 + half = len >> 1;
1.126 + middle = first;
1.127 + std::advance(middle, half);
1.128 + if (comp(val, *middle))
1.129 + len = half;
1.130 + else {
1.131 + first = middle;
1.132 + ++first;
1.133 + len = len - half - 1;
1.134 + }
1.135 + }
1.136 + return first;
1.137 +}
1.138 +
1.139 +template <class ForwardIter, class Tp>
1.140 +std::pair<ForwardIter, ForwardIter>
1.141 +equal_range(ForwardIter first, ForwardIter last, const Tp& val)
1.142 +{
1.143 + typedef detail::iterator_traits<ForwardIter> traits;
1.144 +
1.145 + typename traits::difference_type len = boost::detail::distance(first, last);
1.146 + typename traits::difference_type half;
1.147 + ForwardIter middle, left, right;
1.148 +
1.149 + while (len > 0) {
1.150 + half = len >> 1;
1.151 + middle = first;
1.152 + std::advance(middle, half);
1.153 + if (*middle < val) {
1.154 + first = middle;
1.155 + ++first;
1.156 + len = len - half - 1;
1.157 + }
1.158 + else if (val < *middle)
1.159 + len = half;
1.160 + else {
1.161 + left = boost::detail::lower_bound(first, middle, val);
1.162 + std::advance(first, len);
1.163 + right = boost::detail::upper_bound(++middle, first, val);
1.164 + return std::pair<ForwardIter, ForwardIter>(left, right);
1.165 + }
1.166 + }
1.167 + return std::pair<ForwardIter, ForwardIter>(first, first);
1.168 +}
1.169 +
1.170 +template <class ForwardIter, class Tp, class Compare>
1.171 +std::pair<ForwardIter, ForwardIter>
1.172 +equal_range(ForwardIter first, ForwardIter last, const Tp& val,
1.173 + Compare comp)
1.174 +{
1.175 + typedef detail::iterator_traits<ForwardIter> traits;
1.176 +
1.177 + typename traits::difference_type len = boost::detail::distance(first, last);
1.178 + typename traits::difference_type half;
1.179 + ForwardIter middle, left, right;
1.180 +
1.181 + while (len > 0) {
1.182 + half = len >> 1;
1.183 + middle = first;
1.184 + std::advance(middle, half);
1.185 + if (comp(*middle, val)) {
1.186 + first = middle;
1.187 + ++first;
1.188 + len = len - half - 1;
1.189 + }
1.190 + else if (comp(val, *middle))
1.191 + len = half;
1.192 + else {
1.193 + left = boost::detail::lower_bound(first, middle, val, comp);
1.194 + std::advance(first, len);
1.195 + right = boost::detail::upper_bound(++middle, first, val, comp);
1.196 + return std::pair<ForwardIter, ForwardIter>(left, right);
1.197 + }
1.198 + }
1.199 + return std::pair<ForwardIter, ForwardIter>(first, first);
1.200 +}
1.201 +
1.202 +template <class ForwardIter, class Tp>
1.203 +bool binary_search(ForwardIter first, ForwardIter last,
1.204 + const Tp& val) {
1.205 + ForwardIter i = boost::detail::lower_bound(first, last, val);
1.206 + return i != last && !(val < *i);
1.207 +}
1.208 +
1.209 +template <class ForwardIter, class Tp, class Compare>
1.210 +bool binary_search(ForwardIter first, ForwardIter last,
1.211 + const Tp& val,
1.212 + Compare comp) {
1.213 + ForwardIter i = boost::detail::lower_bound(first, last, val, comp);
1.214 + return i != last && !comp(val, *i);
1.215 +}
1.216 +
1.217 +}} // namespace boost::detail
1.218 +
1.219 +#endif // BINARY_SEARCH_DWA_122600_H_