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

Last change on this file since 2530 was 2530, checked in by Peter, 11 years ago

avoid long line and remove empty lines

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