stlab.adobe.com Adobe Systems Incorporated

find_closest.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_FIND_CLOSEST_HPP
00010 #define ADOBE_FIND_CLOSEST_HPP
00011 
00012 /*************************************************************************************************/
00013 
00014 #include <adobe/config.hpp>
00015 
00016 #include <iterator>
00017 
00018 #include <adobe/future/ternary_function.hpp>
00019 
00020 /*************************************************************************************************/
00021 
00022 namespace adobe {
00023 
00024 /*************************************************************************************************/
00025 
00026 /*
00027     find_closest takes a range and a value, and returns the closest value in the sequence to the
00028     value passed, for some definition of "closest". By default it compares the cardinal difference
00029     between the values to find the closest, though the client can pass their own TernaryPredicate
00030     to override this functionality.
00031 
00032     Preconditions:
00033         - The sequence to be searched must be sorted according to the comparison method used in
00034             the supplied TernaryPredicate.
00035 
00036     Postconditions:
00037         - As long as the size of the sequence is greater than 0, the result will always be a valid
00038             value inside the sequence. (i.e., the only time the end of the sequence is returned is
00039             when the sequence is empty).
00040 
00041     Additional Concepts:
00042         - Subtractable      :   Subtraction yields a difference type; T - T -> D
00043         - TernaryPredicate  :   A TernanyPredicate is called with three arguments
00044                                 and returns true or false.
00045 */
00046 
00047 /*************************************************************************************************/
00048 
00049 template <  typename T  // T models Subtractable
00050          >
00051 struct closer_predicate : ternary_function<T, T, T, bool>
00052 {
00053     typedef ternary_function<T, T, T, bool>         _super;
00054     typedef typename _super::first_argument_type    first_argument_type;
00055     typedef typename _super::second_argument_type   second_argument_type;
00056     typedef typename _super::third_argument_type    third_argument_type;
00057     typedef typename _super::result_type            result_type;
00058 
00059     result_type operator () (const first_argument_type& a, const second_argument_type& b, const third_argument_type& x) const
00060     {
00061         // precondition: a <= b
00062 
00063         return x - a < b - x;
00064     }
00065 };
00066 
00067 /*************************************************************************************************/
00068 
00069 namespace implementation {
00070 
00071 /*************************************************************************************************/
00072 
00073 template <  typename I, // I models ForwardIterator
00074             typename D, // D models LessThanComparable  
00075             typename T, // T models Subtractable
00076             typename C  // C models TernaryPredicate
00077          >
00078 I find_closest(I first, D n, const T& value, C pred, std::forward_iterator_tag)
00079 {
00080     if (n < D(2)) return first;
00081 
00082     while (n != D(2))
00083     {
00084         D third(n / D(3));
00085         D new_n(n - third);
00086         I first_third(first);
00087         I last_third(first);
00088 
00089         std::advance(first_third, third);
00090         std::advance(last_third, new_n);
00091 
00092         if (!pred(*first_third, *last_third, value))
00093             first = first_third;
00094 
00095         n = new_n;
00096     }
00097 
00098     I second(first);
00099 
00100     std::advance(second, 1);
00101 
00102     return pred(*first, *second, value) ? first : second;
00103 }
00104 
00105 /*************************************************************************************************/
00106 
00107 template <  typename I, // I models ForwardIterator
00108             typename D, // D models LessThanComparable  
00109             typename T, // T models Subtractable
00110             typename C  // C models TernaryPredicate
00111          >
00112 I find_closest(I first, D n, const T& value, C pred, std::random_access_iterator_tag)
00113 {
00114     if (n < D(2)) return first;
00115 
00116     while (n != D(2))
00117     {
00118         D third(n / D(3));
00119         D new_n(n - third);
00120 
00121         if (!pred(*(first + third), *(first + new_n), value))
00122             first += third;
00123 
00124         n = new_n;
00125     }
00126 
00127     I second(first + 1);
00128 
00129     return pred(*first, *second, value) ? first : second;
00130 }
00131 
00132 /*************************************************************************************************/
00133 
00134 } // namespace implementation
00135 
00136 /*************************************************************************************************/
00137 
00138 template <  typename I, // I models ForwardIterator
00139             typename D, // D models LessThanComparable  
00140             typename T, // T models Subtractable
00141             typename C  // C models TernaryPredicate
00142          >
00143 inline I find_closest(I first, D n, const T& value, C pred)
00144 {
00145     typedef typename std::iterator_traits<I>::iterator_category category;
00146 
00147     return implementation::find_closest(first, n, value, pred, category());
00148 }
00149 
00150 /*************************************************************************************************/
00151 
00152 template <  typename I, // I models ForwardIterator
00153             typename D, // D models LessThanComparable  
00154             typename T  // T models Subtractable
00155          >
00156 inline I find_closest(I first, D n, const T& value)
00157 {
00158     typedef typename std::iterator_traits<I>::iterator_category category;
00159 
00160     return implementation::find_closest(first, n, value, closer_predicate<T>(), category()); 
00161 }
00162 
00163 /*************************************************************************************************/
00164 
00165 template <  typename I, // I models ForwardIterator
00166             typename T, // T models Subtractable
00167             typename C  // C models TernaryPredicate
00168          >
00169 inline I find_closest(I first, I last, const T& value, C pred)
00170 {
00171     typedef typename std::iterator_traits<I>::iterator_category category;
00172 
00173     return implementation::find_closest(first, std::distance(first, last), value, pred, category());
00174 }
00175 
00176 /*************************************************************************************************/
00177 
00178 template <  typename I, // I models ForwardIterator
00179             typename T  // T models Subtractable
00180          >
00181 inline I find_closest(I first, I last, const T& value)
00182 {
00183     typedef typename std::iterator_traits<I>::iterator_category category;
00184 
00185     return implementation::find_closest(first, std::distance(first, last), value, closer_predicate<T>(), category());
00186 }
00187 
00188 /*************************************************************************************************/
00189 
00190 } // namespace adobe
00191 
00192 /*************************************************************************************************/
00193 
00194 #endif
00195 
00196 /*************************************************************************************************/

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