source: trunk/yat/utility/stl_utility.h @ 2275

Last change on this file since 2275 was 2275, checked in by Peter, 12 years ago

improve docs for compose_functors

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 18.5 KB
Line 
1#ifndef _theplu_yat_utility_stl_utility_
2#define _theplu_yat_utility_stl_utility_
3
4// $Id: stl_utility.h 2275 2010-06-22 22:29:28Z peter $
5
6/*
7  Copyright (C) 2004 Jari Häkkinen
8  Copyright (C) 2005 Jari Häkkinen, Peter Johansson, Markus Ringnér
9  Copyright (C) 2006 Jari Häkkinen
10  Copyright (C) 2007, 2008 Jari Häkkinen, Peter Johansson
11  Copyright (C) 2009, 2010 Peter Johansson
12
13  This file is part of the yat library, http://dev.thep.lu.se/yat
14
15  The yat library is free software; you can redistribute it and/or
16  modify it under the terms of the GNU General Public License as
17  published by the Free Software Foundation; either version 3 of the
18  License, or (at your option) any later version.
19
20  The yat library is distributed in the hope that it will be useful,
21  but WITHOUT ANY WARRANTY; without even the implied warranty of
22  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
23  General Public License for more details.
24
25  You should have received a copy of the GNU General Public License
26  along with yat. If not, see <http://www.gnu.org/licenses/>.
27*/
28
29///
30/// \file stl_utility.h
31///
32/// There are a number of useful functionality missing in the Standard
33/// Template Library, STL. This file is an effort to provide
34/// extensions to STL functionality.
35///
36
37#include "DataWeight.h"
38#include "Exception.h"
39
40#include <boost/concept_check.hpp>
41#include <boost/iterator/transform_iterator.hpp>
42#include <boost/mpl/if.hpp>
43#include <boost/type_traits/add_const.hpp>
44#include <boost/type_traits/is_const.hpp>
45#include <boost/type_traits/remove_reference.hpp>
46
47#include <algorithm>
48#include <cmath>
49#include <exception>
50#include <functional>
51#include <map>
52#include <ostream>
53#include <sstream>
54#include <string>
55#include <utility>
56#include <vector>
57
58// We are intruding standard namespace, which might cause
59// conflicts. Let the user turn off these declarations by defining
60// YAT_STD_DISABE
61#ifndef YAT_STD_DISABLE
62namespace std {
63
64  ///
65  /// Print out a pair
66  ///
67  // This is in namespace std because we have not figured out how to have
68  // pair and its operator<< in different namespaces
69  template <class T1, class T2> 
70  std::ostream& operator<<(std::ostream& out, const std::pair<T1,T2>& p) 
71  { out << p.first << "\t" << p.second; return out; }
72
73}
74#endif
75
76namespace theplu {
77namespace yat {
78namespace utility {
79
80  /**
81     Functor class taking absolute value
82  */
83  template<typename T>
84  struct abs : std::unary_function<T, T>
85  {
86    /**
87       \return absolute value
88     */
89    inline T operator()(T x) const
90    { return std::abs(x); }
91  };
92
93
94  /**
95     See The C++ Standard Library - A Tutorial and Reference by
96     Nicolai M. Josuttis
97
98     If f is a binary functor, both g and h are unary functors, and
99     return type of g (and h) is convertible to F's argument type,
100     then compose_f_gx_hy can be used to create a functor equivalent
101     to \f$ f(g(x), h(y)) \f$
102
103     - F must be an <a
104     href="http://www.sgi.com/tech/stl/AdaptableBinaryFunction.html">
105     AdaptableBinaryFunction</a>
106     - G must be an <a
107     href="http://www.sgi.com/tech/stl/AdaptableUnaryFunction.html">
108     AdaptableUnaryFunction</a>
109     - H must be an <a
110     href="http://www.sgi.com/tech/stl/AdaptableUnaryFunction.html">
111     AdaptableUnaryFunction</a>
112     - \c G::result_type is convertible to \c F::first_argument_type
113     - \c H::result_type is convertible to \c F::second_argument_type
114
115     \see compose_f_gxy and compose_f_gx
116   */
117  template<class F, class G, class H>
118  class compose_f_gx_hy : 
119    public std::binary_function<typename G::argument_type,
120                                typename H::argument_type,
121                                typename F::result_type>
122  {
123  public:
124    /**
125       \brief Constructor
126     */
127    compose_f_gx_hy(F f, G g, H h)
128      : f_(f), g_(g), h_(h) 
129    {
130      BOOST_CONCEPT_ASSERT((boost::Convertible<typename G::result_type
131                            , typename F::first_argument_type>));
132      BOOST_CONCEPT_ASSERT((boost::Convertible<typename H::result_type
133                            , typename F::second_argument_type>));
134
135    }
136
137    /**
138       \brief Does the work
139     */
140    typename F::result_type
141    operator()(typename G::argument_type x, 
142               typename H::argument_type y) const
143    {
144      return f_(g_(x), h_(y));
145    }
146
147  private:
148    F f_;
149    G g_;
150    H h_;
151  };
152
153  /**
154     Convenient function to create a compose_f_gx_hy.
155
156     \relates compose_f_gx_hy
157
158     \see std::make_pair
159  */
160  template<class F, class G, class H>
161  compose_f_gx_hy<F, G, H> make_compose_f_gx_hy(F f, G g, H h)
162  {
163    return compose_f_gx_hy<F,G,H>(f,g,h);
164  } 
165
166
167  /**
168     See The C++ Standard Library - A Tutorial and Reference by
169     Nicolai M. Josuttis
170
171     If f is a unary functor, g is a binary functor, and return type
172     of g is convertible to F's argument type, then
173     compose_f_gxy can be used to create a functor equivalent to
174     \f$ f(g(x,y)) \f$
175
176     - F must be an <a
177     href="http://www.sgi.com/tech/stl/AdaptableUnaryFunction.html">
178     AdaptableUnaryFunction</a>
179     - G must be an <a
180     href="http://www.sgi.com/tech/stl/AdaptableBinaryFunction.html">
181     AdaptableBinaryFunction</a>
182     - \c G::result_type is convertible to \c F::argument_type
183
184     \see compose_f_gx_hy and compose_f_gx
185
186     \since New in yat 0.7
187   */
188  template<class F, class G>
189  class compose_f_gxy : 
190    public std::binary_function<typename G::first_argument_type,
191                                typename G::second_argument_type,
192                                typename F::result_type>
193  {
194  public:
195    /**
196       \brief Constructor
197     */
198    compose_f_gxy(F f, G g)
199      : f_(f), g_(g) 
200    {
201      BOOST_CONCEPT_ASSERT((boost::Convertible<typename G::result_type
202                            , typename F::argument_type>));
203    }
204
205    /**
206       \brief Does the work
207     */
208    typename F::result_type
209    operator()(typename G::first_argument_type x, 
210               typename G::second_argument_type y) const
211    {
212      return f_(g_(x,y));
213    }
214
215  private:
216    F f_;
217    G g_;
218  };
219
220  /**
221     Convenient function to create a compose_f_gxy.
222
223     \relates compose_f_gxy
224
225     \see std::make_pair
226
227     \since New in yat 0.7
228  */
229  template<class F, class G>
230  compose_f_gxy<F, G> make_compose_f_gxy(F f, G g)
231  {
232    return compose_f_gxy<F,G>(f,g);
233  } 
234
235
236  /**
237     See The C++ Standard Library - A Tutorial and Reference by
238     Nicolai M. Josuttis
239
240     If f is a unary functor, g is a unary functor, and return type of
241     g is convertible to F's argument type, then compose_f_gx can be
242     used to create a functor equivalent to \f$ f(g(x)) \f$
243
244     - F must be an <a
245     href="http://www.sgi.com/tech/stl/AdaptableBinaryFunction.html">
246     AdaptableBinaryFunction</a>
247     - G must be an <a
248     href="http://www.sgi.com/tech/stl/AdaptableUnaryFunction.html">
249     AdaptableUnaryFunction</a>
250     - \c G::result_type is convertible to \c F::argument_type
251
252     \see compose_f_gx_hy and compose_f_gxy
253
254     \since New in yat 0.7
255   */
256  template<class F, class G>
257  class compose_f_gx : public std::unary_function<typename G::argument_type,
258                                                  typename F::result_type>
259  {
260  public:
261    /**
262       \brief Constructor
263     */
264    compose_f_gx(F f, G g)
265      : f_(f), g_(g) 
266    {
267      BOOST_CONCEPT_ASSERT((boost::Convertible<typename G::result_type
268                            , typename F::argument_type>));
269    }
270
271    /**
272       \brief Does the work
273     */
274    typename F::result_type
275    operator()(typename G::argument_type x) const
276    {
277      return f_(g_(x));
278    }
279
280  private:
281    F f_;
282    G g_;
283  };
284
285  /**
286     Convenient function to create a compose_f_gx.
287
288     \relates compose_f_gx
289
290     \see std::make_pair
291
292     \since New in yat 0.7
293  */
294  template<class F, class G>
295  compose_f_gx<F, G> make_compose_f_gx(F f, G g)
296  {
297    return compose_f_gx<F,G>(f,g);
298  } 
299
300
301  /**
302     Functor class to exponentiate values using std::exp
303
304     T should be either \c float, \c double, or \c long \c double
305
306     \since New in yat 0.5
307  */
308  template<typename T>
309  struct Exp : std::unary_function<T, T>
310  {
311    /**
312       \return exponentiated value
313     */
314    inline T operator()(T x) const
315    { return std::exp(x); }
316  };
317
318  /**
319     Same functionality as map::operator[] but the function does not
320     modify the map and the function throws if key does not exist in
321     the map.
322
323     \return const reference to m[k]
324
325     \since New in yat 0.7
326   */
327  template <typename Key, typename Tp, typename Compare, typename Alloc>
328  const Tp& get(const std::map<Key, Tp, Compare, Alloc>& m, const Key& k);
329
330
331  /**
332     Creating a map from a range [first, last) such that m[key]
333     returns a vector with indices of which element in [first, last)
334     that is equal to \a key, or more technically: m[element].size()
335     returns number of elements equal to \a element, and
336     m[*element][i] = distance(first, element) for every \a element in
337     [first, last) and \a i smaller than m[element].size().
338
339     Requirement: InputIterator's value type is assignable to Key
340
341     \since New in yat 0.5
342   */
343  template<typename InputIterator, typename Key, typename Comp>
344  void inverse(InputIterator first, InputIterator last,
345               std::map<Key, std::vector<size_t>, Comp >& m)
346  {
347    BOOST_CONCEPT_ASSERT((boost::InputIterator<InputIterator>));
348    BOOST_CONCEPT_ASSERT((boost::Convertible<typename std::iterator_traits<InputIterator>::value_type, Key>));
349    m.clear();
350    for (size_t i=0; first!=last; ++i, ++first)
351      m[*first].push_back(i);
352  }
353
354  /**
355     In the created multimap each element e will fulfill: \f$ *(first
356     + e->second) == e->first \f$
357
358     Requirement: InputIterator's value type is assignable to Key
359
360     \since New in yat 0.5
361   */
362  template<typename Key, typename InputIterator, typename Comp>
363  void inverse(InputIterator first, InputIterator last, 
364               std::multimap<Key, size_t, Comp>& m)
365  {
366    BOOST_CONCEPT_ASSERT((boost::InputIterator<InputIterator>));
367    BOOST_CONCEPT_ASSERT((boost::Convertible<typename std::iterator_traits<InputIterator>::value_type, Key>));
368    m.clear();
369    for (size_t i=0; first!=last; ++i, ++first)
370      m.insert(std::make_pair(*first, i));
371  }
372
373
374  /**
375     \brief Functor that behaves like std::less with the exception
376     that it treates NaN as a number larger than infinity.
377
378     This functor is useful when sorting ranges with NaNs. The problem
379     with NaNs is that std::less always returns \c false when one of
380     the arguments is NaN. That together with the fact that std::sort
381     only guarantees that an element \c i is never less than previous
382     element \c --i. Therefore {10, NaN, 2} is sorted according to
383     this definition, but most often it is desired that the 2 is
384     located before the 10 in the range. Using this functor, less_nan,
385     this can easily be achieved as std::sort(first, last, less_nan)
386
387     The default implementation uses std::isnan(T), which consequently
388     must be supported.
389
390     There is a specialization less_nan<DataWeight>
391
392     \since New in yat 0.6
393  */
394  template<typename T>
395  struct less_nan : std::binary_function<T, T, bool>
396  {
397    /**
398       \return \c true if x is less than y. NaNs are treated as a number
399       larger than infinity, which implies \c true is returned if y is
400       NaN and x is not.
401     */
402    inline bool operator()(T x, T y) const
403    { 
404      if (std::isnan(x))
405        return false;
406      if (std::isnan(y))
407        return true;
408      return x<y;
409    }
410  };
411
412
413  /**
414     \brief Specialization for DataWeight.
415   */
416  template<>
417  struct less_nan<DataWeight> 
418    : std::binary_function<DataWeight, DataWeight, bool>
419  {
420    /**
421       \return less_nan<double>(x.data(), y.data())
422     */
423    inline bool operator()(const DataWeight& x, const DataWeight& y) const
424    { 
425      less_nan<double> compare;
426      return compare(x.data(), y.data());
427    }
428  };
429
430
431  /**
432     Functor class to take logarithm
433
434     T should be either \c float, \c double, or \c long \c double
435
436     \since New in yat 0.5
437  */
438  template<typename T>
439  class Log : std::unary_function<T, T>
440  {
441  public:
442    /**
443       Default constructor using natural base \f$ e \f$
444     */
445    Log(void)
446      : log_base_(1.0) {}
447
448    /**
449       \param base Taking logarithm in which base, e.g. 2 or 10.
450    */
451    explicit Log(double base) : log_base_(std::log(base)) {}
452
453    /**
454       \return logarithm
455     */
456    inline T operator()(T x) const
457    { return std::log(x)/log_base_; }
458
459  private:
460    double log_base_;
461  };
462
463  /**
464     \return max of values
465   */
466  template <typename T>
467  T max(const T& a, const T& b, const T& c)
468  {
469    return std::max(std::max(a,b),c);
470  }
471
472
473  /**
474     \return max of values
475   */
476  template <typename T>
477  T max(const T& a, const T& b, const T& c, const T& d)
478  {
479    return std::max(std::max(a,b), std::max(c,d));
480  }
481
482
483  /**
484     \return max of values
485   */
486  template <typename T>
487  T max(const T& a, const T& b, const T& c, const T& d, const T& e)
488  {
489    return std::max(max(a,b,c,d), e);
490  }
491
492
493  /**
494     \return max of values
495   */
496  template <typename T>
497  T max(const T& a, const T& b, const T& c, const T& d, const T& e, const T& f)
498  {
499    return std::max(max(a,b,c,d), std::max(e,f));
500  }
501
502
503  ///
504  /// @brief Functor comparing pairs using second.
505  ///
506  /// STL provides operator< for the pair.first element, but none for
507  /// pair.second. This template provides this and can be used as the
508  /// comparison object in generic functions such as the STL sort.
509  ///
510  template <class T1,class T2>
511  struct pair_value_compare
512  {
513    ///
514    /// @return true if x.second<y.second or (!(y.second<y.second) and
515    /// x.first<y.first)
516    ///
517    inline bool operator()(const std::pair<T1,T2>& x,
518                           const std::pair<T1,T2>& y) {
519      return ((x.second<y.second) ||
520              (!(y.second<x.second) && (x.first<y.first))); 
521    }
522  };
523
524  /**
525     \brief Functor that return std::pair.first
526
527     \see pair_first_iterator
528
529     \since New in yat 0.5
530   */
531  template <class Pair>
532  struct PairFirst
533  {
534    /**
535       The type returned is Pair::first_type& with the exception when
536       Pair is const and Pair::first_type is non-const, in which case
537       const Pair::first_type& is return type.
538     */
539    typedef typename boost::mpl::if_<
540                  typename boost::is_const<Pair>::type, 
541                  typename boost::add_const<typename Pair::first_type>::type&,
542                  typename Pair::first_type&>::type result_type;
543   
544    /**
545       The argument type is Pair&.
546     */
547    typedef Pair& argument_type;
548
549    /**
550       \return p.first
551     */
552    inline result_type operator()(argument_type p) const
553    { return p.first; }
554
555  };
556
557
558  /**
559     \brief Functor that return std::pair.second
560
561     \see pair_second_iterator
562
563     \since New in yat 0.5
564   */
565  template <class Pair>
566  struct PairSecond
567  {
568    /**
569       The type returned is Pair::second_type& with the exception when
570       Pair is const and Pair::second_type is non-const, in which case
571       const Pair::first_type& is return type.
572     */
573    typedef typename boost::mpl::if_<
574                  typename boost::is_const<Pair>::type, 
575                  typename boost::add_const<typename Pair::second_type>::type&,
576                  typename Pair::second_type&>::type result_type;
577   
578    /**
579       The argument type is Pair&.
580     */
581    typedef Pair& argument_type;
582
583    /**
584       \return p.first
585     */
586    inline result_type operator()(argument_type p) const
587    { return p.second; }
588
589  };
590
591
592  /**
593     Creates a transform_iterator that transforms an iterator with
594     value type std::pair to an iterator with value type
595     std::pair::first_type. This can be used, for example, to
596     communicate between a std::map and std::vector
597
598     \code
599     std::map<std::string, int> map;
600     ...
601     std::vector<std::string> vec;
602     vec.resize(map.size());
603     std::copy(pair_first_iterator(map.begin()), pair_first_iterator(map.end()),
604               vec.begin());
605     \endcode
606
607     \since New in yat 0.5
608   */
609  template<class Iter>
610  boost::transform_iterator<
611    PairFirst<typename boost::remove_reference<
612                 typename std::iterator_traits<Iter>::reference
613                 >::type>,
614    Iter> pair_first_iterator(Iter i)
615  {
616    // We are going via ::reference in order to remain const info;
617    // ::value_type does not contain const information.
618    typedef typename std::iterator_traits<Iter>::reference ref_type;
619    typedef typename boost::remove_reference<ref_type>::type val_type;
620    typedef PairFirst<val_type> PF; 
621    return boost::transform_iterator<PF, Iter>(i, PF());
622  }
623
624
625  /**
626     Creates a transform_iterator that transforms an iterator with
627     value type std::pair to an iterator with value type
628     std::pair::second_type. This can be used, for example, to
629     communicate between a std::map and std::vector
630
631     \code
632     std::map<std::string, int> map;
633     ...
634     std::vector<int> vec(map.size(),0);
635     std::copy(vec.begin(), vec.end(), pair_second_iterator(map.begin()));
636     \endcode
637
638     \since New in yat 0.5
639   */
640  template<class Iter>
641  boost::transform_iterator<
642    PairSecond<typename boost::remove_reference<
643                 typename std::iterator_traits<Iter>::reference
644                 >::type>,
645    Iter> pair_second_iterator(Iter i)
646  {
647    // We are going via ::reference in order to remain const info;
648    // ::value_type does not contain const information.
649    typedef typename std::iterator_traits<Iter>::reference ref_type;
650    typedef typename boost::remove_reference<ref_type>::type val_type;
651    typedef PairSecond<val_type> PS; 
652    return boost::transform_iterator<PS, Iter>(i, PS());
653  }
654
655
656  /**
657     Adaptor class that can be used to compare pointers, T*, when you
658     want to compare them with respect to the objects they point to.
659
660     Example:
661     \code
662     std::vector<MyClass*> vec(18);
663     ...
664     PtrCompare<MyClass, std::greater<MyClass> > ptr_compare;
665     std::sort(vec.begin(), vec.end(), ptr_compare);
666     \endcode
667
668     The class Compare must be a <a
669     href="http://www.sgi.com/tech/stl/BinaryFunction.html">binary
670     functor</a> that takes two \c const \c T& and returns \c bool.
671
672     \since New in yat 0.7
673   */
674  template<typename T, class Compare = std::less<T> >
675  class PtrCompare : std::binary_function<T const* const, T const* const, bool>
676  {
677  public:
678    /**
679       \brief Constructor.
680
681       Creates an instance of Compare using its default constructor.
682     */
683    PtrCompare(void)
684    {
685      BOOST_CONCEPT_ASSERT((boost::BinaryFunction<Compare, bool, const T&, 
686                            const T&>));
687    }
688
689    /**
690       \brief Constructor.
691
692       Creates a copy of \a c that will be used later.
693     */
694    PtrCompare(Compare c)
695      : compare_(c) 
696    {
697      BOOST_CONCEPT_ASSERT((boost::BinaryFunction<Compare, bool, const T&, 
698                            const T&>));
699    }
700
701    /**
702       \return true iff Compare(* \a lhs, * \a rhs ) is true.
703     */
704    bool operator()(T const* const lhs, T const* const rhs) const
705    { 
706      return compare_(*lhs, *rhs); 
707    }
708  private:
709    Compare compare_;
710
711    // using compiler generated copy
712    // PtrCompare(const PtrCompare&)
713    // PtrCompare& operator=(const PtrCompare&)
714  };
715
716  ///
717  /// @brief Function converting a string to lower case
718  ///
719  std::string& to_lower(std::string& s);
720
721  ///
722  /// @brief Function converting a string to upper case
723  ///
724  std::string& to_upper(std::string& s);
725
726
727  // template implementations
728
729  template <typename Key, typename Tp, typename Compare, typename Alloc>
730  const Tp& get(const std::map<Key, Tp, Compare, Alloc>& m, const Key& key)
731  {
732    typename std::map<Key, Tp, Compare, Alloc>::const_iterator iter(m.find(key));
733    if (iter==m.end()) {
734      std::stringstream ss;
735      ss << "yat: get(const Map&, const Key&): Key not found in Map\n";
736      throw runtime_error(ss.str());
737    }
738    return iter->second;
739  }
740
741
742
743}}} // of namespace utility, yat, and theplu
744
745#endif
Note: See TracBrowser for help on using the repository browser.