LoSTL.H

Go to the documentation of this file.
00001 /**
00002    \file  Robots/LoBot/util/LoSTL.H
00003    \brief STL helpers.
00004 */
00005 
00006 // //////////////////////////////////////////////////////////////////// //
00007 // The iLab Neuromorphic Vision C++ Toolkit - Copyright (C) 2000-2005   //
00008 // by the University of Southern California (USC) and the iLab at USC.  //
00009 // See http://iLab.usc.edu for information about this project.          //
00010 // //////////////////////////////////////////////////////////////////// //
00011 // Major portions of the iLab Neuromorphic Vision Toolkit are protected //
00012 // under the U.S. patent ``Computation of Intrinsic Perceptual Saliency //
00013 // in Visual Environments, and Applications'' by Christof Koch and      //
00014 // Laurent Itti, California Institute of Technology, 2001 (patent       //
00015 // pending; application number 09/912,225 filed July 23, 2001; see      //
00016 // http://pair.uspto.gov/cgi-bin/final/home.pl for current status).     //
00017 // //////////////////////////////////////////////////////////////////// //
00018 // This file is part of the iLab Neuromorphic Vision C++ Toolkit.       //
00019 //                                                                      //
00020 // The iLab Neuromorphic Vision C++ Toolkit is free software; you can   //
00021 // redistribute it and/or modify it under the terms of the GNU General  //
00022 // Public License as published by the Free Software Foundation; either  //
00023 // version 2 of the License, or (at your option) any later version.     //
00024 //                                                                      //
00025 // The iLab Neuromorphic Vision C++ Toolkit is distributed in the hope  //
00026 // that it will be useful, but WITHOUT ANY WARRANTY; without even the   //
00027 // implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR      //
00028 // PURPOSE.  See the GNU General Public License for more details.       //
00029 //                                                                      //
00030 // You should have received a copy of the GNU General Public License    //
00031 // along with the iLab Neuromorphic Vision C++ Toolkit; if not, write   //
00032 // to the Free Software Foundation, Inc., 59 Temple Place, Suite 330,   //
00033 // Boston, MA 02111-1307 USA.                                           //
00034 // //////////////////////////////////////////////////////////////////// //
00035 //
00036 // Primary maintainer for this file: mviswana usc edu
00037 // $HeadURL: svn://isvn.usc.edu/software/invt/trunk/saliency/src/Robots/LoBot/util/LoSTL.H $
00038 // $Id: LoSTL.H 13922 2010-09-11 03:46:14Z mviswana $
00039 //
00040 
00041 #ifndef LOBOT_STL_UTILITIES_DOT_H
00042 #define LOBOT_STL_UTILITIES_DOT_H
00043 
00044 //------------------------------ HEADERS --------------------------------
00045 
00046 // lobot headers
00047 #include "Robots/LoBot/util/range.hh"
00048 
00049 // Standard C++ headers
00050 #include <algorithm>
00051 #include <functional>
00052 #include <iterator>
00053 #include <utility>
00054 
00055 //----------------------------- NAMESPACE -------------------------------
00056 
00057 namespace lobot {
00058 
00059 //-------------------------- PAIR FUNCTIONS -----------------------------
00060 
00061 /// Functions to retrieve the individual elements of a pair.
00062 //@{
00063 template<typename P>
00064 typename P::first_type  get_first(const P& p)  {return p.first ;}
00065 
00066 template<typename P>
00067 typename P::second_type get_second(const P& p) {return p.second ;}
00068 //@}
00069 
00070 //------------------------- DELETE FUNCTIONS ----------------------------
00071 
00072 /// Pointer deletion (useful in conjunction with STL algorithms and
00073 /// containers).
00074 ///
00075 /// WARNING: P must be a pointer type (e.g., int* rather than int).
00076 template<typename P> void delete_ptr(P p) {delete p ;}
00077 
00078 /// Pointer deletion when the pointer is part of an std::pair
00079 //@{
00080 template<typename P> void delete_first (P& p) {delete p.first ;}
00081 template<typename P> void delete_second(P& p) {delete p.second ;}
00082 //@}
00083 
00084 //------------------------ CONTAINER CLEAN-UP ---------------------------
00085 
00086 /// Releasing an STL container of pointers using a specific delete
00087 /// function (useful in cases of std::maps).
00088 ///
00089 /// C: container type
00090 /// D: delete function object type
00091 ///
00092 /// WARNING: C *must* be an STL container or *must* provide an equivalent
00093 /// begin/end iterator interface.
00094 ///
00095 /// This function would typically be used to clean-up maps. For example,
00096 /// an std::map<int, int*>. In this case, we cannot use delete_ptr<int*>
00097 /// directly because the map iterators point to std::pair objects whose
00098 /// first member is the key (int in this case) and whose second member is
00099 /// the value (int* in this case).
00100 ///
00101 /// Thus, we need to supply an appropriate delete function. In this case,
00102 /// that function would be delete_second<std::pair<int, int*>>.
00103 template<typename C, typename D>
00104 void purge_container(C& c, D delete_fn)
00105 {
00106    std::for_each(c.begin(), c.end(), delete_fn) ;
00107 }
00108 
00109 /// Releasing an STL container of pointers using the delete_ptr function.
00110 /// C: container type
00111 ///
00112 /// WARNING: C *must* be an STL container or provide an equivalent
00113 /// begin/end iterator interface and value_type typedef.
00114 ///
00115 /// This function would typically be used to clean-up a containers such as
00116 /// std::vector<int*> or other such containers of pointers. In this case,
00117 /// value_type would be int*.
00118 template<typename C>
00119 void purge_container(C& c)
00120 {
00121    typedef typename C::value_type P ;
00122    purge_container(c, delete_ptr<P>) ;
00123 }
00124 
00125 //------------------------- FUNCTION OBJECTS ----------------------------
00126 
00127 /// The STL already provides canned function objects for relational
00128 /// operators. These two are for the min and max functions. They can be
00129 /// used in conjunction with binders to quickly write calls to
00130 /// std::transform(), etc. without having to create custom function
00131 /// objects.
00132 //@{
00133 template<typename T>
00134 struct min : std::binary_function<T, T, T> {
00135    T operator()(const T& a, const T& b) const {
00136       return std::min(a, b) ;
00137    }
00138 } ;
00139 
00140 template<typename T>
00141 struct max : std::binary_function<T, T, T> {
00142    T operator()(const T& a, const T& b) const {
00143       return std::max(a, b) ;
00144    }
00145 } ;
00146 //@}
00147 
00148 /// This function object is meant to be used in conjunction with the
00149 /// std::accumulate algorithm and returns the sum of the squares of the
00150 /// sequence to which the accumulate algorithm is applied.
00151 template<typename T>
00152 struct sum_of_squares : std::binary_function<T, T, T> {
00153    T operator()(const T& a, const T& b) const {
00154       return T(a + b*b) ;
00155    }
00156 } ;
00157 
00158 /// This function object is a predicate that returns true if the number
00159 /// passed to its function call operator is out of the specified range.
00160 template<typename T>
00161 class out_of_range : public std::unary_function<T, bool> {
00162    range<T> m_range ;
00163 public:
00164    out_of_range(const range<T>& R) : m_range(R) {}
00165    bool operator()(const T& t) const {return ! m_range.in(t) ;}
00166 } ;
00167 
00168 /// This object acts as an iterator that can be passed to algorithms such
00169 /// as std::transform. However, instead of iterating across a container,
00170 /// this iterator accumulates the source values passed to it. Typical
00171 /// usage of this is shown below:
00172 ///
00173 ///    accumulator<int> acc =
00174 ///        std::transform(begin, end, accumulator<int>(0), f) ;
00175 ///    std::cout << "accumulated value is: " << acc.value() << '\n' ;
00176 ///
00177 /// In the above example, f is a function or object that takes arguments
00178 /// of the type contained between begin and end and returns an int.
00179 ///
00180 /// Naturally, the std::accumulate algorithm would do the exact same
00181 /// thing as the above algorithm with a lot less fuss. However,
00182 /// accumulate cannot work with two different sequences. For instance, if
00183 /// we have two sequences and we would like to determine a least squares
00184 /// error between the two sequences using an STL algorithm and without
00185 /// having to write a custom function or function object to take care of
00186 /// the whole thing, this accumulator type along with boost::bind,
00187 /// std::minus and a squaring function is just the ticket:
00188 ///
00189 ///    accumulator<float> acc =
00190 ///        std::transform(begin1, end1, begin2, accumulator<float>(0),
00191 ///                       boost::bind(sqr<float>,
00192 ///                                   boost::bind(std::minus<float>, _1, _2)));
00193 ///    std::cout << "square error is: " << acc.value() << '\n' ;
00194 ///
00195 /// NOTE: The sqr used above is defined in util/LoMath.H.
00196 template<typename T>
00197 class accumulator :
00198       public std::iterator<std::output_iterator_tag, T, void, void, void> {
00199    T acc ;
00200 public:
00201    accumulator(T init = T()) : acc(init) {}
00202    accumulator& operator=(T t)  {acc += t ; return *this ;}
00203    accumulator& operator*()     {return *this ;}
00204    accumulator& operator++()    {return *this ;}
00205    accumulator  operator++(int) {return *this ;}
00206    T value() const {return acc ;}
00207 } ;
00208 
00209 //---------------------------- MAP HELPERS ------------------------------
00210 
00211 /// By default, STL maps compare keys when used with various STL
00212 /// algorithms such as min_element and max_element. This function object
00213 /// performs the comparison by comparing the values stored in the map
00214 /// rather than its keys. It uses the < operator for comparisons.
00215 ///
00216 /// NOTE: The type M is expected to be an std::map.
00217 template<typename M>
00218 class map_value_comp_less {
00219    typedef typename M::value_type value_type ;
00220 public:
00221    map_value_comp_less(){}
00222    bool operator()(const value_type& A, const value_type& B) const {
00223       return A.second < B.second ;
00224    }
00225 } ;
00226 
00227 /// By default, STL maps compare keys when used with various STL
00228 /// algorithms such as min_element and max_element. This function object
00229 /// performs the comparison by comparing the values stored in the map
00230 /// rather than its keys. It uses the supplied comparator function or
00231 /// function object rather than the < operator to perform comparisons.
00232 ///
00233 /// NOTE: The type M is expected to be an std::map. The type C should be
00234 /// a comparator function object such as std::less or std::greater.
00235 template<typename M, typename C>
00236 class map_value_comp {
00237    C comp ;
00238    typedef typename M::value_type value_type ;
00239 public:
00240    map_value_comp(const C& c) : comp(c) {}
00241    bool operator()(const value_type& A, const value_type& B) const {
00242       return comp(A.second, B.second) ;
00243    }
00244 } ;
00245 
00246 /// Helper function to return a map_value_compare_less object. This
00247 /// helper exists to take advantage of the compiler's automatic type
00248 /// deduction facility so as to alleviate users from having to explicitly
00249 /// supply a type when instantiating the map_value_compare_less object.
00250 /// Instead, at the call site, calling this function with the std::map
00251 /// object is enough.
00252 template<typename M>
00253 map_value_comp_less<M>
00254 map_value_compare(const M&)
00255 {
00256    return map_value_comp_less<M>() ;
00257 }
00258 
00259 /// Helper function to return a map_value_comp object. This helper exists
00260 /// to take advantage of the compiler's automatic type deduction facility
00261 /// so as to alleviate users from having to explicitly supply the
00262 /// necessary types when instantiating the comparator object. Instead,
00263 /// users only need to pass this function an std::map object and a
00264 /// comparator such std::greater.
00265 template<typename M, typename C>
00266 map_value_comp<M,C>
00267 map_value_compare(const M&, const C& c)
00268 {
00269    return map_value_comp<M,C>(c) ;
00270 }
00271 
00272 /// Unfortunately, the STL transform algorithm cannot be applied to STL
00273 /// maps because std::map::iterator is not mutable, meaning that *i = p
00274 /// is not a valid expression (where i is an std::map::iterator and p is
00275 /// of type std::map::value_type). However, i->second = p is a valid
00276 /// expression.
00277 ///
00278 /// This function uses the above workaround to implement the transform
00279 /// algorithm for maps.
00280 ///
00281 /// Like the STL transform algorithm, it expects two input iterators
00282 /// (type I), one output iterator (type O) and a unary function or
00283 /// function object (type F). Unlike the standard transform algorithm,
00284 /// however, the input and output iterator types are expected to be for a
00285 /// pair associative container, i.e., a container whose value_type is an
00286 /// std::pair.
00287 ///
00288 /// The functional of type F will be passed the second member of the
00289 /// iterator, which, for an std::map, is the contained data or value
00290 /// (while the first member of the iterator is the key).
00291 template<typename I, typename O, typename F>
00292 O transform_map(I i, I end, O out, F f)
00293 {
00294    for (; i != end; ++i, ++out)
00295       out->second = f(i->second) ;
00296    return out ;
00297 }
00298 
00299 /// Unfortunately, the STL transform algorithm cannot be applied to STL
00300 /// maps because std::map::iterator is not mutable, meaning that *i = p
00301 /// is not a valid expression (where i is an std::map::iterator and p is
00302 /// of type std::map::value_type). However, i->second = p is a valid
00303 /// expression.
00304 ///
00305 /// This function uses the above workaround to implement the transform
00306 /// algorithm for maps.
00307 ///
00308 /// Like the STL transform algorithm, it expects two input iterators
00309 /// (type I), one output iterator (type O) and a function or function
00310 /// object (type F). Unlike the standard transform algorithm, however,
00311 /// the input and output iterator types are expected to be for a pair
00312 /// associative container, i.e., a container whose value_type is an
00313 /// std::pair. Furthermore, the function or function object (type F) that
00314 /// performs the transformation is expected to be a binary function
00315 /// rather than a unary function.
00316 ///
00317 /// The functional of type F will be passed both the first and second
00318 /// members of the input iterator, i.e., both the map's key and value.
00319 /// This is useful in cases where the transformation requires both the
00320 /// key and the value (see the gaussian_weight function object for an
00321 /// example).
00322 template<typename I, typename O, typename F>
00323 O transform_map2(I i, I end, O out, F f)
00324 {
00325    for (; i != end; ++i, ++out)
00326       out->second = f(i->first, i->second) ;
00327    return out ;
00328 }
00329 
00330 /// Since STL map iterators point to STL pair objects, they can be a
00331 /// little inconvenient to use with the STL for_each algorithm,
00332 /// especially when the function to be performed on each element of the
00333 /// map expects the map's contents as a parameter rather than a key-value
00334 /// pair. This function implements the for_each algorithm assuming that
00335 /// it is iterating over a map.
00336 template<typename I, typename F>
00337 F for_each_map(I i, I last, F f)
00338 {
00339    for (; i != last; ++i)
00340       f(i->second) ;
00341    return f ;
00342 }
00343 
00344 //---------------------------- ALGORITHMS -------------------------------
00345 
00346 /// The STL does not provide an algorithm for copying one sequence to
00347 /// another based on some arbitrary test involving the contents of the
00348 /// source sequence. This quick function rectifies that problem.
00349 template<typename I, typename O, typename P>
00350 void copy_if(I i, I last, O o, P pred)
00351 {
00352    for (; i != last; ++i, ++o)
00353       if (pred(*i))
00354          *o = *i ;
00355 }
00356 
00357 /// This algorithm is performs a conditional copy from one sequence to
00358 /// another. In addition to the predicate function, it takes a
00359 /// "transformer" function that can be used to transform/convert the
00360 /// object type pointed to by the input iterator into the object type for
00361 /// the destination sequence.
00362 ///
00363 /// For example, if we want to copy a vector of strings to a vector of
00364 /// ints, we can supply a suitable function or function object that will
00365 /// convert the source vector's strings into ints. This function will
00366 /// then pass the source vector's contents through the supplied converter
00367 /// function and copying this function's return value to the destination
00368 /// int vector.
00369 template<typename I, typename O, typename P, typename F>
00370 void copy_if(I i, I last, O o, P pred, F func)
00371 {
00372    for (; i != last; ++i, ++o)
00373       if (pred(*i))
00374          *o = func(*i) ;
00375 }
00376 
00377 /// Quick helper to connect whatever is in the supplied container to the
00378 /// specified target object using push_back(). (Thus, the target object
00379 /// must supply a push_back() method and other necessary STL glue to make
00380 /// this work.)
00381 template<typename C, typename T>
00382 inline void connect(const C& container, T& target)
00383 {
00384    std::copy(container.begin(), container.end(), std::back_inserter(target)) ;
00385 }
00386 
00387 /// Quick helper to connect whatever is in the supplied container to the
00388 /// specified target object using push_back(). (Thus, the target object
00389 /// must supply a push_back() method and other necessary STL glue to make
00390 /// this work.)
00391 template<typename C, typename T, typename F>
00392 inline void connect_if(const C& src, T& dst, F pred)
00393 {
00394    copy_if(src.begin(), src.end(), std::back_inserter(dst), pred) ;
00395 }
00396 
00397 //-----------------------------------------------------------------------
00398 
00399 } // end of namespace encapsulating this file's definitions
00400 
00401 #endif
00402 
00403 /* So things look consistent in everyone's emacs... */
00404 /* Local Variables: */
00405 /* indent-tabs-mode: nil */
00406 /* End: */
Generated on Sun May 8 08:41:31 2011 for iLab Neuromorphic Vision Toolkit by  doxygen 1.6.3