stlab.adobe.com Adobe Systems Incorporated

lower_bound.hpp

Go to the documentation of this file.
00001 /*
00002     Copyright 2005-2007 Adobe Systems Incorporated
00003     Distributed under the MIT License (see accompanying file LICENSE_1_0_0.txt
00004     or a copy at http://stlab.adobe.com/licenses.html)
00005 */
00006 
00007 /*************************************************************************************************/
00008 
00009 #ifndef ADOBE_ALGORITHM_LOWER_BOUND_HPP
00010 #define ADOBE_ALGORITHM_LOWER_BOUND_HPP
00011 
00012 #include <adobe/config.hpp>
00013 
00014 #include <algorithm>
00015 #include <iterator>
00016 
00017 #include <boost/range/begin.hpp>
00018 #include <boost/range/end.hpp>
00019 #include <boost/bind.hpp>
00020 #include <boost/next_prior.hpp>
00021 #include <boost/type_traits/is_same.hpp>
00022 #include <boost/utility/enable_if.hpp>
00023 
00024 #include <adobe/functional/operator.hpp>
00025 
00026 /*************************************************************************************************/
00027 
00028 namespace adobe {
00029 namespace implementation {
00030 
00031 /*************************************************************************************************/
00032 
00033 template <  typename I, // I models ForwardIterator
00034             typename N, // N models IntegralType
00035             typename T, // T == result_type(P)
00036             typename C, // C models StrictWeakOrdering(T, T)
00037             typename P> // P models UnaryFunction(value_type(I)) -> T
00038 I lower_bound_n_(I f, N n, const T& x, C c, P p)
00039 {
00040     while (n != 0)
00041     {
00042         N h = n >> 1;
00043         I m = boost::next(f, h);
00044 
00045         if (c(p(*m), x)) { f = boost::next(m); n -= h + N(1); }
00046         else { n = h; }
00047     }
00048     return f;
00049 }
00050 
00051 /*************************************************************************************************/
00052 
00053 } // implementation
00054 
00055 /*************************************************************************************************/
00056 
00065 /*************************************************************************************************/
00066 
00067 template <  typename I, // I models ForwardIterator
00068             typename N, // N models IntegralType
00069             typename T> // T == value_type(I)
00070 inline I lower_bound_n(I f, N n, const T& x)
00071 {
00072     return implementation::lower_bound_n_(f, n, x, less(), identity<T>());
00073 }
00074 
00075 /*************************************************************************************************/
00076 
00077 template <  typename I, // I models FowardIterator
00078             typename N, // N models IntegralType
00079             typename T, // T == value_type(I)
00080             typename C> // C models StrictWeakOrdering(T, T)
00081 inline I lower_bound_n(I f, N n, const T& x, C c)
00082 {
00083     return implementation::lower_bound_n_(f, n, x, boost::bind(c, _1, _2), identity<T>());
00084 }
00085 
00086 /*************************************************************************************************/
00087 
00088 template <  typename I, // I models ForwardIterator
00089             typename N, // N models IntegralType
00090             typename T, // T == result_type(P)
00091             typename C, // C models StrictWeakOrdering(T, T)
00092             typename P> // P models UnaryFunction(value_type(I)) -> T
00093 inline I lower_bound_n(I f, N n, const T& x, C c, P p)
00094 {
00095     return implementation::lower_bound_n_(f, n, x, boost::bind(c, _1, _2), boost::bind(p, _1));
00096 }
00097 
00098 /*************************************************************************************************/
00099 
00100 /*
00101     NOTE (sparent) : These functions collide with the std functions when called unqualified as
00102     is done by std::equal_range with VC++. We hide them from ADL by moving them into the
00103     fn namespace.
00104 */
00105 
00106 namespace fn { } using namespace fn;
00107 namespace fn {
00108 
00109 /*************************************************************************************************/
00110 
00111 template <  typename I, // I models ForwardIterator
00112             typename T> // T == value_type(I)
00113 inline I lower_bound(I f, I l, const T& x)
00114 {
00115     return std::lower_bound(f, l, x);
00116 }
00117 
00118 /*************************************************************************************************/
00119 
00120 template <  typename I, // I models FowardIterator
00121             typename T, // T == value_type(I)
00122             typename C> // C models StrictWeakOrdering(T, T)
00123 inline I lower_bound(I f, I l, const T& x, C c)
00124 {
00125     return std::lower_bound(f, l, x, boost::bind(c, _1, _2));
00126 }
00127 
00128 /*************************************************************************************************/
00129 
00130 template <  typename I, // I models ForwardIterator
00131             typename T, // T == result_type(P)
00132             typename C, // C models StrictWeakOrdering(T, T)
00133             typename P> // P models UnaryFunction(value_type(I)) -> T
00134 inline I lower_bound(I f, I l, const T& x, C c, P p)
00135 {
00136     return lower_bound_n(f, std::distance(f, l), x, c, p);
00137 }
00138 
00139 /*************************************************************************************************/
00140 
00141 template <  typename I, // I models ForwardRange
00142             typename T, // T == result_type(P)
00143             typename C, // C models StrictWeakOrdering(T, T)
00144             typename P> // P models UnaryFunction(value_type(I)) -> T
00145 inline
00146     typename boost::lazy_disable_if<boost::is_same<I, T>, boost::range_iterator<I> >::type
00147         lower_bound(I& r, const T& x, C c, P p)
00148 { return adobe::lower_bound(boost::begin(r), boost::end(r), x, c, p); }
00149 
00150 /*************************************************************************************************/
00151 
00152 template <  typename I, // I models ForwardRange
00153             typename T, // T == result_type(P)
00154             typename C, // C models StrictWeakOrdering(T, T)
00155             typename P> // P models UnaryFunction(value_type(I)) -> T
00156 inline
00157     typename boost::lazy_disable_if<boost::is_same<I, T>, boost::range_const_iterator<I> >::type
00158         lower_bound(const I& r, const T& x, C c, P p)
00159 { return adobe::lower_bound(boost::begin(r), boost::end(r), x, c, p); }
00160 
00161 /*************************************************************************************************/
00167 template <class ForwardRange, class T>
00168 inline typename boost::range_iterator<ForwardRange>::type lower_bound(ForwardRange& range, const T& value)
00169 {
00170     return std::lower_bound(boost::begin(range), boost::end(range), value);
00171 }
00172 
00178 template <class ForwardRange, class T>
00179 inline typename boost::range_const_iterator<ForwardRange>::type lower_bound(const ForwardRange& range, const T& value)
00180 {
00181     return std::lower_bound(boost::begin(range), boost::end(range), value);
00182 }
00183 
00194 template <typename I, class T, class Compare>
00195 inline typename boost::lazy_disable_if<boost::is_same<I, T>, boost::range_iterator<I> >::type
00196         lower_bound(I& range, const T& value, Compare comp)
00197 {
00198     return adobe::lower_bound(boost::begin(range), boost::end(range), value, comp);
00199 }
00200 
00206 template <class I, class T, class Compare>
00207 inline typename boost::lazy_disable_if<boost::is_same<I, T>, boost::range_const_iterator<I> >::type
00208         lower_bound(const I& range, const T& value, Compare comp)
00209 {
00210     return adobe::lower_bound(boost::begin(range), boost::end(range), value, comp);
00211 }
00212 
00213 /*************************************************************************************************/
00214 
00215 } // namespace fn
00216 } // namespace adobe
00217 
00218 /*************************************************************************************************/
00219 
00220 #endif
00221 
00222 /*************************************************************************************************/

Copyright © 2006-2007 Adobe Systems Incorporated.

Use of this website signifies your agreement to the Terms of Use and Online Privacy Policy.

Search powered by Google