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

Last change on this file since 2857 was 2857, checked in by Peter, 10 years ago

closes #726

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