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