source: trunk/yat/stl_utility.h @ 1498

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

latest yat and update make rule to fetch from yat repo

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