stlab.adobe.com Adobe Systems Incorporated

binary_search.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_BINARY_SEARCH_HPP
00010 #define ADOBE_ALGORITHM_BINARY_SEARCH_HPP
00011 
00012 #include <adobe/config.hpp>
00013 
00014 #include <boost/range/begin.hpp>
00015 #include <boost/range/const_iterator.hpp>
00016 #include <boost/range/end.hpp>
00017 #include <boost/range/iterator.hpp>
00018 
00019 #include <adobe/algorithm/lower_bound.hpp>
00020 #include <adobe/functional/operator.hpp>
00021 
00022 /*************************************************************************************************/
00023 
00024 namespace adobe {
00025 
00026 namespace implementation {
00027 
00028 template <typename I, // I models ForwardIterator
00029           typename T, // T models Regular
00030           typename C, // C models StrictWeakOrdering
00031           typename P> // P models UnaryFunction(value_type(I)) -> T
00032 inline I binary_search(I f, I l, const T& x, C c, P p)
00033 {
00034     I result = adobe::lower_bound(f, l, x, c, p);
00035     if (result != l && p(*result) == x) return result;
00036     return l;
00037 }
00038 
00039 }
00040 
00041 /*************************************************************************************************/
00095 /*************************************************************************************************/
00096 
00097 template <typename I, // I models ForwardIterator
00098           typename T, // T models Regular
00099           typename C, // C models StrictWeakOrdering
00100           typename P> // P models UnaryFunction(value_type(I)) -> T
00101 inline I binary_search(I f, I l, const T& x, C c, P p)
00102 {
00103     return implementation::binary_search(f, l, x, c, boost::bind(p, _1));
00104 }
00105 
00106 
00107 template <typename I, // I models ForwardIterator
00108           typename T, // T models Regular
00109           typename C> // C models StrictWeakOrdering
00110 inline I binary_search(I f, I l, const T& x, C c)
00111 {
00112     return adobe::binary_search(f, l, x, c, identity<T>());
00113 }
00114 
00115 template <typename I, // I models ForwardIterator
00116           typename T> // T models Regular
00117 inline I binary_search(I f, I l, const T& x)
00118 { return binary_search(f, l, x, less()); }
00119 
00120 template <typename I, typename T>
00121 inline typename boost::range_iterator<I>::type binary_search(I& range, const T& x)
00122 {
00123     return adobe::binary_search(boost::begin(range), boost::end(range), x);
00124 }
00125 
00126 template <typename I, typename T>
00127 inline typename boost::range_const_iterator<I>::type binary_search(const I& range, const T& x)
00128 {
00129     return adobe::binary_search(boost::begin(range), boost::end(range), x);
00130 }
00131 
00132 template <typename I, typename T, typename C>
00133 inline typename boost::range_iterator<I>::type binary_search(I& range, const T& x, C c)
00134 {
00135     return adobe::binary_search(boost::begin(range), boost::end(range), x, c);
00136 }
00137 
00138 template <typename I, typename T, typename C>
00139 inline typename boost::range_const_iterator<I>::type binary_search(const I& range, const T& x, C c)
00140 {
00141     return adobe::binary_search(boost::begin(range), boost::end(range), x, c);
00142 }
00143 
00144 /*************************************************************************************************/
00145 
00146 template <  typename I, // I models ForwardRange
00147             typename T, // T == result_type(P)
00148             typename C, // C models StrictWeakOrdering(T, T)
00149             typename P> // P models UnaryFunction(value_type(I)) -> T
00150 inline
00151     typename boost::lazy_disable_if<boost::is_same<I, T>, boost::range_iterator<I> >::type
00152         binary_search(I& r, const T& x, C c, P p)
00153 { return adobe::binary_search(boost::begin(r), boost::end(r), x, c, p); }
00154 
00155 /*************************************************************************************************/
00156 
00157 template <  typename I, // I models ForwardRange
00158             typename T, // T == result_type(P)
00159             typename C, // C models StrictWeakOrdering(T, T)
00160             typename P> // P models UnaryFunction(value_type(I)) -> T
00161 inline
00162     typename boost::lazy_disable_if<boost::is_same<I, T>, boost::range_const_iterator<I> >::type
00163         binary_search(const I& r, const T& x, C c, P p)
00164 { return adobe::binary_search(boost::begin(r), boost::end(r), x, c, p); }
00165 
00170 /*************************************************************************************************/
00171 
00172 } // namespace adobe
00173 
00174 /*************************************************************************************************/
00175 
00176 #endif
00177 
00178 /*************************************************************************************************/

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