source: trunk/yat/stl_utility.h @ 1463

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

set svncopyright:ignore property

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