stlab.adobe.com Adobe Systems Incorporated

upper_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_UPPER_BOUND_HPP
00010 #define ADOBE_ALGORITHM_UPPER_BOUND_HPP
00011 
00012 #include <adobe/config.hpp>
00013 
00014 #include <algorithm>
00015 #include <cassert>
00016 #include <iterator>
00017 
00018 #include <boost/bind.hpp>
00019 #include <boost/next_prior.hpp>
00020 #include <boost/range/begin.hpp>
00021 #include <boost/range/end.hpp>
00022 #include <boost/type_traits/is_same.hpp>
00023 #include <boost/utility/enable_if.hpp>
00024 
00025 #include <adobe/functional.hpp>
00026 
00027 /*************************************************************************************************/
00028 
00029 namespace adobe {
00030 namespace implementation {
00031 
00032 /*************************************************************************************************/
00033 
00034 template <  typename I, // I models ForwardIterator
00035             typename N, // N models IntegralType
00036             typename T, // T == result_type(P)
00037             typename C, // C models StrictWeakOrdering(T, T)
00038             typename P> // P models UnaryFunction(value_type(I)) -> T
00039 I upper_bound_n(I f, N n, const T& x, C c, P p)
00040 {
00041     assert(!(n < 0) && "FATAL (sparent) : n must be >= 0");
00042 
00043     while (n != 0)
00044     {
00045         N h = n >> 1;
00046         
00047         I m = boost::next(f, h);
00048 
00049         if (!c(x, p(*m))) { f = boost::next(m); n -= h + N(1); }
00050         else { n = h; }
00051     }
00052     return f;
00053 }
00054 
00055 /*************************************************************************************************/
00056 
00057 } // implementation
00058 
00059 /*************************************************************************************************/
00060 
00069 /*************************************************************************************************/
00070 
00071 template <  typename I, // I models ForwardIterator
00072             typename N, // N models IntegralType
00073             typename T> // T == value_type(I)
00074 inline I upper_bound_n(I f, N n, const T& x)
00075 {
00076     return implementation::upper_bound_n(f, n, x, less(), identity<T>());
00077 }
00078 
00079 /*************************************************************************************************/
00080 
00081 template <  typename I, // I models FowardIterator
00082             typename N, // N models IntegralType
00083             typename T, // T == value_type(I)
00084             typename C> // C models StrictWeakOrdering(T, T)
00085 inline I upper_bound_n(I f, N n, const T& x, C c)
00086 {
00087     return implementation::upper_bound_n(f, n, x, boost::bind(c, _1, _2), identity<T>());
00088 }
00089 
00090 /*************************************************************************************************/
00091 
00092 template <  typename I, // I models ForwardIterator
00093             typename N, // N models IntegralType
00094             typename T, // T == result_type(P)
00095             typename C, // C models StrictWeakOrdering(T, T)
00096             typename P> // P models UnaryFunction(value_type(I)) -> T
00097 inline I upper_bound_n(I f, N n, const T& x, C c, P p)
00098 {
00099     return implementation::upper_bound_n(f, n, x, boost::bind(c, _1, _2), boost::bind(p, _1));
00100 }
00101 
00102 /*************************************************************************************************/
00103 
00104 /*
00105     NOTE (sparent) : These functions collide with the std functions when called unqualified as
00106     is done by std::equal_range with VC++. We hide them from ADL by moving them into the
00107     fn namespace.
00108 */
00109 
00110 namespace fn { } using namespace fn;
00111 namespace fn {
00112 
00113 /*************************************************************************************************/
00114 
00115 template <  typename I, // I models ForwardIterator
00116             typename T> // T == value_type(I)
00117 inline I upper_bound(I f, I l, const T& x)
00118 {
00119     return std::upper_bound(f, l, x);
00120 }
00121 
00122 /*************************************************************************************************/
00123 
00124 template <  typename I, // I models FowardIterator
00125             typename T, // T == value_type(I)
00126             typename C> // C models StrictWeakOrdering(T, T)
00127 inline I upper_bound(I f, I l, const T& x, C c)
00128 {
00129     return std::upper_bound(f, l, x, boost::bind(c, _1, _2));
00130 }
00131 
00132 /*************************************************************************************************/
00133 
00134 template <  typename I, // I models ForwardIterator
00135             typename T, // T == result_type(P)
00136             typename C, // C models StrictWeakOrdering(T, T)
00137             typename P> // P models UnaryFunction(value_type(I)) -> T
00138 inline I upper_bound(I f, I l, const T& x, C c, P p)
00139 {
00140     return upper_bound_n(f, std::distance(f, l), x, c, p);
00141 }
00142 
00143 /*************************************************************************************************/
00144 
00145 template <  typename I, // I models ForwardRange
00146             typename T, // T == result_type(P)
00147             typename C, // C models StrictWeakOrdering(T, T)
00148             typename P> // P models UnaryFunction(value_type(I)) -> T
00149 inline
00150     typename boost::lazy_disable_if<boost::is_same<I, T>, boost::range_iterator<I> >::type
00151         upper_bound(I& r, const T& x, C c, P p)
00152 { return adobe::upper_bound(boost::begin(r), boost::end(r), x, c, p); }
00153 
00154 /*************************************************************************************************/
00155 
00156 template <  typename I, // I models ForwardRange
00157             typename T, // T == result_type(P)
00158             typename C, // C models StrictWeakOrdering(T, T)
00159             typename P> // P models UnaryFunction(value_type(I)) -> T
00160 inline
00161     typename boost::lazy_disable_if<boost::is_same<I, T>, boost::range_const_iterator<I> >::type
00162         upper_bound(const I& r, const T& x, C c, P p)
00163 { return adobe::upper_bound(boost::begin(r), boost::end(r), x, c, p); }
00164 
00165 /*************************************************************************************************/
00171 template <class ForwardRange, class T>
00172 inline typename boost::range_iterator<ForwardRange>::type upper_bound(ForwardRange& range, const T& value)
00173 {
00174     return std::upper_bound(boost::begin(range), boost::end(range), value);
00175 }
00176 
00182 template <class ForwardRange, class T>
00183 inline typename boost::range_const_iterator<ForwardRange>::type upper_bound(const ForwardRange& range, const T& value)
00184 {
00185     return std::upper_bound(boost::begin(range), boost::end(range), value);
00186 }
00187 
00198 template <typename I, class T, class Compare>
00199 inline typename boost::lazy_disable_if<boost::is_same<I, T>, boost::range_iterator<I> >::type
00200         upper_bound(I& range, const T& value, Compare comp)
00201 {
00202     return adobe::upper_bound(boost::begin(range), boost::end(range), value, comp);
00203 }
00204 
00210 template <class I, class T, class Compare>
00211 inline typename boost::lazy_disable_if<boost::is_same<I, T>, boost::range_const_iterator<I> >::type
00212         upper_bound(const I& range, const T& value, Compare comp)
00213 {
00214     return adobe::upper_bound(boost::begin(range), boost::end(range), value, comp);
00215 }
00216 
00217 /*************************************************************************************************/
00218 
00219 } // namespace fn
00220 } // namespace adobe
00221 
00222 /*************************************************************************************************/
00223 
00224 #endif
00225 
00226 /*************************************************************************************************/

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