stlab.adobe.com Adobe Systems Incorporated

equal_range.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_EQUAL_RANGE_HPP
00010 #define ADOBE_ALGORITHM_EQUAL_RANGE_HPP
00011 
00012 #include <adobe/config.hpp>
00013 
00014 #include <algorithm>
00015 #include <cassert>
00016 #include <utility>
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 
00023 #include <adobe/algorithm/lower_bound.hpp>
00024 #include <adobe/algorithm/upper_bound.hpp>
00025 #include <adobe/functional.hpp>
00026 
00027 /*************************************************************************************************/
00028 
00037 /*************************************************************************************************/
00038 
00039 namespace adobe {
00040 namespace implementation {
00041 
00042 /*************************************************************************************************/
00043 
00044 template <  typename I, // I models ForwardIterator
00045             typename N, // N models IntegralType
00046             typename T, // T == result_type(P)
00047             typename C, // C models StrictWeakOrdering(T, T)
00048             typename P> // P models UnaryFunction(value_type(I)) -> T
00049 std::pair<I, I> equal_range_n(I f, N n, const T& x, C c, P p)
00050 {
00051     assert(!(n < 0) && "FATAL (sparent) : n must be >= 0");
00052 
00053     while (n != 0) {
00054         N h = n >> 1;
00055         I m = boost::next(f, h);
00056 
00057         if (c(p(*m), x)) {
00058             f = boost::next(m);
00059             n -= h + 1;
00060         } else if (c(x, p(*m))) {
00061             n = h;
00062         } else {
00063             return std::make_pair(implementation::lower_bound_n_(f, h, x, c, p),
00064                 implementation::upper_bound_n(boost::next(m), n - (h + 1), x, c, p));
00065         }
00066     }
00067     return std::make_pair(f, f);
00068 }
00069 
00070 /*************************************************************************************************/
00071 
00072 template <typename I> // I models ForwardRange
00073 struct lazy_range
00074 {
00075     typedef std::pair<typename boost::range_iterator<I>::type,
00076         typename boost::range_iterator<I>::type>    type;
00077 };
00078 
00079 /*************************************************************************************************/
00080 
00081 template <typename I> // I models ForwardRange
00082 struct lazy_range_const
00083 {
00084     typedef std::pair<typename boost::range_const_iterator<I>::type,
00085         typename boost::range_const_iterator<I>::type>    type;
00086 };
00087 
00088 /*************************************************************************************************/
00089 
00090 } // namespace implementation
00091 
00092 /*************************************************************************************************/
00093 
00098 template <  typename I, // I models ForwardIterator
00099             typename N, // N models IntegralType
00100             typename T> // T == result_type(P)
00101 inline std::pair<I, I> equal_range_n(I f, N n, const T& x)
00102 {
00103     return implementation::equal_range_n(f, n, x, less(), identity<T>());
00104 }
00105 
00106 /*************************************************************************************************/
00107 
00112 template <  typename I, // I models ForwardIterator
00113             typename N, // N models IntegralType
00114             typename T, // T == result_type(P)
00115             typename C> // C models StrictWeakOrdering(T, T)
00116 inline std::pair<I, I> equal_range_n(I f, N n, const T& x, C c)
00117 {
00118     return implementation::equal_range_n(f, n, x, boost::bind(c, _1, _2), identity<T>());
00119 }
00120 
00121 /*************************************************************************************************/
00122 
00127 template <  typename I, // I models ForwardIterator
00128             typename N, // N models IntegralType
00129             typename T, // T == result_type(P)
00130             typename C, // C models StrictWeakOrdering(T, T)
00131             typename P> // P models UnaryFunction(value_type(I)) -> T
00132 inline std::pair<I, I> equal_range_n(I f, N n, const T& x, C c, P p)
00133 {
00134     return implementation::equal_range_n(f, n, x, boost::bind(c, _1, _2), boost::bind(p, _1));
00135 }
00136 
00137 /*************************************************************************************************/
00138 
00143 template <  typename I, // I models ForwardIterator
00144             typename T> // T == value_type(I)
00145 inline std::pair<I, I> equal_range(I f, I l, const T& x)
00146 {
00147     return std::equal_range(f, l, x);
00148 }
00149 
00150 /*************************************************************************************************/
00151 
00156 template <  typename I, // I models ForwardIterator
00157             typename T, // T == result_type(P)
00158             typename C> // C models StrictWeakOrdering(T, T)
00159 inline std::pair<I, I> equal_range(I f, I l, const T& x, C c)
00160 {
00161     return std::equal_range(f, l, x, boost::bind(c, _1, _2));
00162 }
00163 
00164 /*************************************************************************************************/
00165 
00170 template <  typename I, // I models ForwardIterator
00171             typename T, // T == result_type(P)
00172             typename C, // C models StrictWeakOrdering(T, T)
00173             typename P> // P models UnaryFunction(value_type(I)) -> T
00174 inline std::pair<I, I> equal_range(I f, I l, const T& x, C c, P p)
00175 {
00176     return equal_range_n(f, std::distance(f, l), x, c, p);
00177 }
00178 
00179 /*************************************************************************************************/
00180 
00185 template <  typename I, // I models ForwardRange
00186             typename T, // T == result_type(P)
00187             typename C, // C models StrictWeakOrdering(T, T)
00188             typename P> // P models UnaryFunction(value_type(I)) -> T
00189 inline
00190 typename boost::lazy_disable_if<boost::is_same<I, T>, implementation::lazy_range<I> >::type
00191         equal_range(I& r, const T& x, C c, P p)
00192 { return adobe::equal_range(boost::begin(r), boost::end(r), x, c, p); }
00193 
00194 /*************************************************************************************************/
00195 
00200 template <  typename I, // I models ForwardRange
00201             typename T, // T == result_type(P)
00202             typename C, // C models StrictWeakOrdering(T, T)
00203             typename P> // P models UnaryFunction(value_type(I)) -> T
00204 inline
00205 typename boost::lazy_disable_if<boost::is_same<I, T>, implementation::lazy_range_const<I> >::type
00206         equal_range(const I& r, const T& x, C c, P p)
00207 { return adobe::equal_range(boost::begin(r), boost::end(r), x, c, p); }
00208 
00209 /*************************************************************************************************/
00210 
00215 template <  typename I, // I models ForwardRange
00216             typename T> // T == result_type(P)
00217 inline std::pair<typename boost::range_iterator<I>::type,
00218                  typename boost::range_iterator<I>::type>
00219 equal_range(I& r, const T& x)
00220 {
00221     return std::equal_range(boost::begin(r), boost::end(r), x);
00222 }
00223 
00224 /*************************************************************************************************/
00225 
00230 template <  typename I, // I models ForwardRange
00231             typename T> // T == result_type(P)
00232 inline std::pair<typename boost::range_const_iterator<I>::type,
00233                  typename boost::range_const_iterator<I>::type>
00234 equal_range(const I& r, const T& x)
00235 {
00236     return std::equal_range(boost::begin(r), boost::end(r), x);
00237 }
00238 
00239 /*************************************************************************************************/
00240 
00245 template <  typename I, // I models ForwardRange
00246             typename T, // T == result_type(P)
00247             typename C> // C models StrictWeakOrdering(T, T)
00248 inline
00249 typename boost::lazy_disable_if<boost::is_same<I, T>, implementation::lazy_range<I> >::type
00250 equal_range(I& r, const T& x, C c)
00251 {
00252     return adobe::equal_range(boost::begin(r), boost::end(r), x, c);
00253 }
00254 
00255 /*************************************************************************************************/
00256 
00261 template <  typename I, // I models ForwardRange
00262             typename T, // T == result_type(P)
00263             typename C> // C models StrictWeakOrdering(T, T)
00264 inline
00265 typename boost::lazy_disable_if<boost::is_same<I, T>, implementation::lazy_range_const<I> >::type
00266 equal_range(const I& r, const T& x, C c)
00267 {
00268     return adobe::equal_range(boost::begin(r), boost::end(r), x, c);
00269 }
00270 
00271 /*************************************************************************************************/
00272 
00273 } // namespace adobe
00274 
00275 /*************************************************************************************************/
00276 
00277 #endif
00278 
00279 /*************************************************************************************************/

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