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

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

adding functor f_gxy and f_gx (similar to f_gx_hy) and adding some tests for all three classes above.

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