# equal_range.hpp

Go to the documentation of this file.
```00001 /*
00005 */
00006
00007 /*************************************************************************************************/
00008
00011
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
00026
00027 /*************************************************************************************************/
00028
00037 /*************************************************************************************************/
00038
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