sorted.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_SORTED_HPP 00010 #define ADOBE_ALGORITHM_SORTED_HPP 00011 00012 #include <algorithm> 00013 #include <functional> 00014 #include <iterator> 00015 00016 #include <boost/range/begin.hpp> 00017 #include <boost/range/end.hpp> 00018 #include <boost/bind.hpp> 00019 00020 #include <adobe/functional/operator.hpp> 00021 00022 /*************************************************************************************************/ 00023 00024 namespace adobe { 00025 00026 /*************************************************************************************************/ 00035 template < typename I, // I models InputIterator 00036 typename O> // O models StrictWeakOrdering on value_type(I) 00037 I sorted(I f, I l, O o) 00038 { 00039 00040 f = std::adjacent_find(f, l, !boost::bind(o, _1, _2)); 00041 if (f != l) ++f; 00042 } 00043 00044 /*************************************************************************************************/ 00045 00049 template <typename I> // I models InputIterator, value_type(I) models LessThanComparable 00050 I sorted(I f, I l) 00051 { 00052 return sorted(f, l, less()); 00053 } 00054 00055 /*************************************************************************************************/ 00056 00060 template < typename I, // I models InputIterator 00061 typename O> // O models StrictWeakOrdering on value_type(I) 00062 inline bool is_sorted(I f, I l, O o) 00063 { 00064 return std::adjacent_find(f, l, !boost::bind(o, _1, _2)) == l; 00065 } 00066 00067 /*************************************************************************************************/ 00068 00072 template <typename I> // I models InputIterator, value_type(I) models LessThanComparable 00073 inline bool is_sorted(I f, I l) 00074 { return is_sorted(f, l, less()); } 00075 00076 /*************************************************************************************************/ 00077 00081 template < typename I, // I models ForwardIterator 00082 typename C, // C models StrictWeakOrdering(T, T) 00083 typename P> // P models UnaryFunction(value_type(I)) -> T 00084 inline bool is_sorted(I f, I l, C c, P p) 00085 { 00086 return std::adjacent_find(f, l, 00087 !boost::bind(c, boost::bind(p, _1), boost::bind(p, _2))) == l; 00088 } 00089 00090 /*************************************************************************************************/ 00091 00095 template < typename I, // I models ForwardRange 00096 typename C, // C models StrictWeakOrdering(T, T) 00097 typename P> // P models UnaryFunction(value_type(I)) -> T 00098 inline bool is_sorted(const I& r, C c, P p) 00099 { return is_sorted(boost::begin(r), boost::end(r), c, p); } 00100 00101 /*************************************************************************************************/ 00102 00106 template < typename I, // I models ForwardRange 00107 typename C> // C models StrictWeakOrdering(T, T) 00108 inline bool is_sorted(const I& r, C c) 00109 { return is_sorted(boost::begin(r), boost::end(r), c, identity<typename std::iterator_traits<I>::value_type>()); } 00110 00111 /*************************************************************************************************/ 00112 00116 template < typename I> // I models ForwardRange 00117 inline bool is_sorted(const I& r) 00118 { return is_sorted(boost::begin(r), boost::end(r), less()); } 00119 00120 /*************************************************************************************************/ 00121 00122 } // namespace adobe 00123 00124 /*************************************************************************************************/ 00125 00126 #endif 00127 00128 /*************************************************************************************************/ |