epoc32/include/stdapis/boost/detail/binary_search.hpp
author William Roberts <williamr@symbian.org>
Tue, 16 Mar 2010 16:12:26 +0000
branchSymbian2
changeset 2 2fe1408b6811
permissions -rw-r--r--
Final list of Symbian^2 public API header files
williamr@2
     1
// Copyright (c)  2000 David Abrahams. 
williamr@2
     2
// Distributed under the Boost Software License, Version 1.0. 
williamr@2
     3
// (See accompanying file LICENSE_1_0.txt or copy at 
williamr@2
     4
// http://www.boost.org/LICENSE_1_0.txt)
williamr@2
     5
// 
williamr@2
     6
// Copyright (c) 1994
williamr@2
     7
// Hewlett-Packard Company
williamr@2
     8
// 
williamr@2
     9
// Permission to use, copy, modify, distribute and sell this software
williamr@2
    10
// and its documentation for any purpose is hereby granted without fee,
williamr@2
    11
// provided that the above copyright notice appear in all copies and
williamr@2
    12
// that both that copyright notice and this permission notice appear
williamr@2
    13
// in supporting documentation.  Hewlett-Packard Company makes no
williamr@2
    14
// representations about the suitability of this software for any
williamr@2
    15
// purpose.  It is provided "as is" without express or implied warranty.
williamr@2
    16
// 
williamr@2
    17
// Copyright (c) 1996
williamr@2
    18
// Silicon Graphics Computer Systems, Inc.
williamr@2
    19
// 
williamr@2
    20
// Permission to use, copy, modify, distribute and sell this software
williamr@2
    21
// and its documentation for any purpose is hereby granted without fee,
williamr@2
    22
// provided that the above copyright notice appear in all copies and
williamr@2
    23
// that both that copyright notice and this permission notice appear
williamr@2
    24
// in supporting documentation.  Silicon Graphics makes no
williamr@2
    25
// representations about the suitability of this software for any
williamr@2
    26
// purpose.  It is provided "as is" without express or implied warranty.
williamr@2
    27
// 
williamr@2
    28
#ifndef BINARY_SEARCH_DWA_122600_H_
williamr@2
    29
# define BINARY_SEARCH_DWA_122600_H_
williamr@2
    30
williamr@2
    31
# include <boost/detail/iterator.hpp>
williamr@2
    32
# include <utility>
williamr@2
    33
williamr@2
    34
namespace boost { namespace detail {
williamr@2
    35
williamr@2
    36
template <class ForwardIter, class Tp>
williamr@2
    37
ForwardIter lower_bound(ForwardIter first, ForwardIter last,
williamr@2
    38
                             const Tp& val) 
williamr@2
    39
{
williamr@2
    40
    typedef detail::iterator_traits<ForwardIter> traits;
williamr@2
    41
    
williamr@2
    42
    typename traits::difference_type len = boost::detail::distance(first, last);
williamr@2
    43
    typename traits::difference_type half;
williamr@2
    44
    ForwardIter middle;
williamr@2
    45
williamr@2
    46
    while (len > 0) {
williamr@2
    47
      half = len >> 1;
williamr@2
    48
      middle = first;
williamr@2
    49
      std::advance(middle, half);
williamr@2
    50
      if (*middle < val) {
williamr@2
    51
        first = middle;
williamr@2
    52
        ++first;
williamr@2
    53
        len = len - half - 1;
williamr@2
    54
      }
williamr@2
    55
      else
williamr@2
    56
        len = half;
williamr@2
    57
    }
williamr@2
    58
    return first;
williamr@2
    59
}
williamr@2
    60
williamr@2
    61
template <class ForwardIter, class Tp, class Compare>
williamr@2
    62
ForwardIter lower_bound(ForwardIter first, ForwardIter last,
williamr@2
    63
                              const Tp& val, Compare comp)
williamr@2
    64
{
williamr@2
    65
  typedef detail::iterator_traits<ForwardIter> traits;
williamr@2
    66
williamr@2
    67
  typename traits::difference_type len = boost::detail::distance(first, last);
williamr@2
    68
  typename traits::difference_type half;
williamr@2
    69
  ForwardIter middle;
williamr@2
    70
williamr@2
    71
  while (len > 0) {
williamr@2
    72
    half = len >> 1;
williamr@2
    73
    middle = first;
williamr@2
    74
    std::advance(middle, half);
williamr@2
    75
    if (comp(*middle, val)) {
williamr@2
    76
      first = middle;
williamr@2
    77
      ++first;
williamr@2
    78
      len = len - half - 1;
williamr@2
    79
    }
williamr@2
    80
    else
williamr@2
    81
      len = half;
williamr@2
    82
  }
williamr@2
    83
  return first;
williamr@2
    84
}
williamr@2
    85
williamr@2
    86
template <class ForwardIter, class Tp>
williamr@2
    87
ForwardIter upper_bound(ForwardIter first, ForwardIter last,
williamr@2
    88
                           const Tp& val)
williamr@2
    89
{
williamr@2
    90
  typedef detail::iterator_traits<ForwardIter> traits;
williamr@2
    91
williamr@2
    92
  typename traits::difference_type len = boost::detail::distance(first, last);
williamr@2
    93
  typename traits::difference_type half;
williamr@2
    94
  ForwardIter middle;
williamr@2
    95
williamr@2
    96
  while (len > 0) {
williamr@2
    97
    half = len >> 1;
williamr@2
    98
    middle = first;
williamr@2
    99
    std::advance(middle, half);
williamr@2
   100
    if (val < *middle)
williamr@2
   101
      len = half;
williamr@2
   102
    else {
williamr@2
   103
      first = middle;
williamr@2
   104
      ++first;
williamr@2
   105
      len = len - half - 1;
williamr@2
   106
    }
williamr@2
   107
  }
williamr@2
   108
  return first;
williamr@2
   109
}
williamr@2
   110
williamr@2
   111
template <class ForwardIter, class Tp, class Compare>
williamr@2
   112
ForwardIter upper_bound(ForwardIter first, ForwardIter last,
williamr@2
   113
                           const Tp& val, Compare comp)
williamr@2
   114
{
williamr@2
   115
  typedef detail::iterator_traits<ForwardIter> traits;
williamr@2
   116
williamr@2
   117
  typename traits::difference_type len = boost::detail::distance(first, last);
williamr@2
   118
  typename traits::difference_type half;
williamr@2
   119
  ForwardIter middle;
williamr@2
   120
williamr@2
   121
  while (len > 0) {
williamr@2
   122
    half = len >> 1;
williamr@2
   123
    middle = first;
williamr@2
   124
    std::advance(middle, half);
williamr@2
   125
    if (comp(val, *middle))
williamr@2
   126
      len = half;
williamr@2
   127
    else {
williamr@2
   128
      first = middle;
williamr@2
   129
      ++first;
williamr@2
   130
      len = len - half - 1;
williamr@2
   131
    }
williamr@2
   132
  }
williamr@2
   133
  return first;
williamr@2
   134
}
williamr@2
   135
williamr@2
   136
template <class ForwardIter, class Tp>
williamr@2
   137
std::pair<ForwardIter, ForwardIter>
williamr@2
   138
equal_range(ForwardIter first, ForwardIter last, const Tp& val)
williamr@2
   139
{
williamr@2
   140
  typedef detail::iterator_traits<ForwardIter> traits;
williamr@2
   141
williamr@2
   142
  typename traits::difference_type len = boost::detail::distance(first, last);
williamr@2
   143
  typename traits::difference_type half;
williamr@2
   144
  ForwardIter middle, left, right;
williamr@2
   145
williamr@2
   146
  while (len > 0) {
williamr@2
   147
    half = len >> 1;
williamr@2
   148
    middle = first;
williamr@2
   149
    std::advance(middle, half);
williamr@2
   150
    if (*middle < val) {
williamr@2
   151
      first = middle;
williamr@2
   152
      ++first;
williamr@2
   153
      len = len - half - 1;
williamr@2
   154
    }
williamr@2
   155
    else if (val < *middle)
williamr@2
   156
      len = half;
williamr@2
   157
    else {
williamr@2
   158
      left = boost::detail::lower_bound(first, middle, val);
williamr@2
   159
      std::advance(first, len);
williamr@2
   160
      right = boost::detail::upper_bound(++middle, first, val);
williamr@2
   161
      return std::pair<ForwardIter, ForwardIter>(left, right);
williamr@2
   162
    }
williamr@2
   163
  }
williamr@2
   164
  return std::pair<ForwardIter, ForwardIter>(first, first);
williamr@2
   165
}
williamr@2
   166
williamr@2
   167
template <class ForwardIter, class Tp, class Compare>
williamr@2
   168
std::pair<ForwardIter, ForwardIter>
williamr@2
   169
equal_range(ForwardIter first, ForwardIter last, const Tp& val,
williamr@2
   170
              Compare comp)
williamr@2
   171
{
williamr@2
   172
  typedef detail::iterator_traits<ForwardIter> traits;
williamr@2
   173
williamr@2
   174
  typename traits::difference_type len = boost::detail::distance(first, last);
williamr@2
   175
  typename traits::difference_type half;
williamr@2
   176
  ForwardIter middle, left, right;
williamr@2
   177
williamr@2
   178
  while (len > 0) {
williamr@2
   179
    half = len >> 1;
williamr@2
   180
    middle = first;
williamr@2
   181
    std::advance(middle, half);
williamr@2
   182
    if (comp(*middle, val)) {
williamr@2
   183
      first = middle;
williamr@2
   184
      ++first;
williamr@2
   185
      len = len - half - 1;
williamr@2
   186
    }
williamr@2
   187
    else if (comp(val, *middle))
williamr@2
   188
      len = half;
williamr@2
   189
    else {
williamr@2
   190
      left = boost::detail::lower_bound(first, middle, val, comp);
williamr@2
   191
      std::advance(first, len);
williamr@2
   192
      right = boost::detail::upper_bound(++middle, first, val, comp);
williamr@2
   193
      return std::pair<ForwardIter, ForwardIter>(left, right);
williamr@2
   194
    }
williamr@2
   195
  }
williamr@2
   196
  return std::pair<ForwardIter, ForwardIter>(first, first);
williamr@2
   197
}           
williamr@2
   198
williamr@2
   199
template <class ForwardIter, class Tp>
williamr@2
   200
bool binary_search(ForwardIter first, ForwardIter last,
williamr@2
   201
                   const Tp& val) {
williamr@2
   202
  ForwardIter i = boost::detail::lower_bound(first, last, val);
williamr@2
   203
  return i != last && !(val < *i);
williamr@2
   204
}
williamr@2
   205
williamr@2
   206
template <class ForwardIter, class Tp, class Compare>
williamr@2
   207
bool binary_search(ForwardIter first, ForwardIter last,
williamr@2
   208
                   const Tp& val,
williamr@2
   209
                   Compare comp) {
williamr@2
   210
  ForwardIter i = boost::detail::lower_bound(first, last, val, comp);
williamr@2
   211
  return i != last && !comp(val, *i);
williamr@2
   212
}
williamr@2
   213
williamr@2
   214
}} // namespace boost::detail
williamr@2
   215
williamr@2
   216
#endif // BINARY_SEARCH_DWA_122600_H_