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

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

avoid obscure code example

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 20.1 KB
Line 
1#ifndef _theplu_yat_utility_stl_utility_
2#define _theplu_yat_utility_stl_utility_
3
4// $Id: stl_utility.h 2731 2012-04-30 05:58:27Z 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     \brief Functor that behaves like std::less with the exception
435     that it treates NaN as a number larger than infinity.
436
437     This functor is useful when sorting ranges with NaNs. The problem
438     with NaNs is that std::less always returns \c false when one of
439     the arguments is NaN. That together with the fact that std::sort
440     only guarantees that an element \c i is never less than previous
441     element \c --i. Therefore {10, NaN, 2} is sorted according to
442     this definition, but most often it is desired that the 2 is
443     located before the 10 in the range. Using this functor, less_nan,
444     this can easily be achieved as std::sort(first, last, less_nan)
445
446     The default implementation uses std::isnan(T), which consequently
447     must be supported.
448
449     There is a specialization less_nan<DataWeight>
450
451     \since New in yat 0.6
452  */
453  template<typename T>
454  struct less_nan : std::binary_function<T, T, bool>
455  {
456    /**
457       \return \c true if x is less than y. NaNs are treated as a number
458       larger than infinity, which implies \c true is returned if y is
459       NaN and x is not.
460     */
461    inline bool operator()(T x, T y) const
462    {
463      if (std::isnan(x))
464        return false;
465      if (std::isnan(y))
466        return true;
467      return x<y;
468    }
469  };
470
471
472  /**
473     \brief Specialization for DataWeight.
474   */
475  template<>
476  struct less_nan<DataWeight>
477    : std::binary_function<DataWeight, DataWeight, bool>
478  {
479    /**
480       \return less_nan<double>(x.data(), y.data())
481     */
482    inline bool operator()(const DataWeight& x, const DataWeight& y) const
483    {
484      less_nan<double> compare;
485      return compare(x.data(), y.data());
486    }
487  };
488
489
490  /**
491     Functor class to take logarithm
492
493     T should be either \c float, \c double, or \c long \c double
494
495     \since New in yat 0.5
496  */
497  template<typename T>
498  class Log : std::unary_function<T, T>
499  {
500  public:
501    /**
502       Default constructor using natural base \f$ e \f$
503     */
504    Log(void)
505      : log_base_(1.0) {}
506
507    /**
508       \param base Taking logarithm in which base, e.g. 2 or 10.
509    */
510    explicit Log(double base) : log_base_(std::log(base)) {}
511
512    /**
513       \return logarithm
514     */
515    inline T operator()(T x) const
516    { return std::log(x)/log_base_; }
517
518  private:
519    double log_base_;
520  };
521
522  /**
523     \return max of values
524   */
525  template <typename T>
526  T max(const T& a, const T& b, const T& c)
527  {
528    return std::max(std::max(a,b),c);
529  }
530
531
532  /**
533     \return max of values
534   */
535  template <typename T>
536  T max(const T& a, const T& b, const T& c, const T& d)
537  {
538    return std::max(std::max(a,b), std::max(c,d));
539  }
540
541
542  /**
543     \return max of values
544   */
545  template <typename T>
546  T max(const T& a, const T& b, const T& c, const T& d, const T& e)
547  {
548    return std::max(max(a,b,c,d), e);
549  }
550
551
552  /**
553     \return max of values
554   */
555  template <typename T>
556  T max(const T& a, const T& b, const T& c, const T& d, const T& e, const T& f)
557  {
558    return std::max(max(a,b,c,d), std::max(e,f));
559  }
560
561
562  ///
563  /// @brief Functor comparing pairs using second.
564  ///
565  /// STL provides operator< for the pair.first element, but none for
566  /// pair.second. This template provides this and can be used as the
567  /// comparison object in generic functions such as the STL sort.
568  ///
569  template <class T1,class T2>
570  struct pair_value_compare
571  {
572    ///
573    /// @return true if x.second<y.second or (!(y.second<y.second) and
574    /// x.first<y.first)
575    ///
576    inline bool operator()(const std::pair<T1,T2>& x,
577                           const std::pair<T1,T2>& y) {
578      return ((x.second<y.second) ||
579              (!(y.second<x.second) && (x.first<y.first)));
580    }
581  };
582
583  /**
584     \brief Functor that return std::pair.first
585
586     \see pair_first_iterator
587
588     \since New in yat 0.5
589   */
590  template <class Pair>
591  struct PairFirst
592  {
593    /**
594       The type returned is Pair::first_type& with the exception when
595       Pair is const and Pair::first_type is non-const, in which case
596       const Pair::first_type& is return type.
597     */
598    typedef typename boost::mpl::if_<
599                  typename boost::is_const<Pair>::type,
600                  typename boost::add_const<typename Pair::first_type>::type&,
601                  typename Pair::first_type&>::type result_type;
602
603    /**
604       The argument type is Pair&.
605     */
606    typedef Pair& argument_type;
607
608    /**
609       \return p.first
610     */
611    inline result_type operator()(argument_type p) const
612    { return p.first; }
613
614  };
615
616
617  /**
618     \brief Functor that return std::pair.second
619
620     \see pair_second_iterator
621
622     \since New in yat 0.5
623   */
624  template <class Pair>
625  struct PairSecond
626  {
627    /**
628       The type returned is Pair::second_type& with the exception when
629       Pair is const and Pair::second_type is non-const, in which case
630       const Pair::first_type& is return type.
631     */
632    typedef typename boost::mpl::if_<
633                  typename boost::is_const<Pair>::type,
634                  typename boost::add_const<typename Pair::second_type>::type&,
635                  typename Pair::second_type&>::type result_type;
636
637    /**
638       The argument type is Pair&.
639     */
640    typedef Pair& argument_type;
641
642    /**
643       \return p.first
644     */
645    inline result_type operator()(argument_type p) const
646    { return p.second; }
647
648  };
649
650
651  /**
652     Creates a transform_iterator that transforms an iterator with
653     value type std::pair to an iterator with value type
654     std::pair::first_type. This can be used, for example, to
655     communicate between a std::map and std::vector
656
657     \code
658     std::map<std::string, int> map;
659     ...
660     std::vector<std::string> vec;
661     vec.resize(map.size());
662     std::copy(pair_first_iterator(map.begin()), pair_first_iterator(map.end()),
663               vec.begin());
664     \endcode
665
666     \since New in yat 0.5
667   */
668  template<class Iter>
669  boost::transform_iterator<
670    PairFirst<typename boost::remove_reference<
671                 typename std::iterator_traits<Iter>::reference
672                 >::type>,
673    Iter> pair_first_iterator(Iter i)
674  {
675    // We are going via ::reference in order to remain const info;
676    // ::value_type does not contain const information.
677    typedef typename std::iterator_traits<Iter>::reference ref_type;
678    typedef typename boost::remove_reference<ref_type>::type val_type;
679    typedef PairFirst<val_type> PF;
680    return boost::transform_iterator<PF, Iter>(i, PF());
681  }
682
683
684  /**
685     Creates a transform_iterator that transforms an iterator with
686     value type std::pair to an iterator with value type
687     std::pair::second_type. This can be used, for example, to
688     communicate between a std::map and std::vector
689
690     \code
691     std::map<std::string, int> map;
692     ...
693     std::vector<int> vec(map.size(),0);
694     std::copy(vec.begin(), vec.end(), pair_second_iterator(map.begin()));
695     \endcode
696
697     \since New in yat 0.5
698   */
699  template<class Iter>
700  boost::transform_iterator<
701    PairSecond<typename boost::remove_reference<
702                 typename std::iterator_traits<Iter>::reference
703                 >::type>,
704    Iter> pair_second_iterator(Iter i)
705  {
706    // We are going via ::reference in order to remain const info;
707    // ::value_type does not contain const information.
708    typedef typename std::iterator_traits<Iter>::reference ref_type;
709    typedef typename boost::remove_reference<ref_type>::type val_type;
710    typedef PairSecond<val_type> PS;
711    return boost::transform_iterator<PS, Iter>(i, PS());
712  }
713
714
715  /**
716     Convenient function that creates a binary predicate that can be
717     used to compare pointers when you want to compare them with
718     respect to the objects they point to.
719
720     Example:
721     \code
722     std::vector<MyClass*> vec(18);
723     ...
724     std::sort(vec.begin(), vec.end(),
725               make_ptr_compare(vec[0], std::greater<MyClass>());
726     \endcode
727
728
729     Type Requirement:
730     - \a compare must be a <a
731     href="http://www.sgi.com/tech/stl/AdaptableBinaryPredicate.html">Adaptable
732     Binary Predicate</a>.
733     - value_type of Pointer must be convertible to argument_type of
734       compare
735
736     \return a compose_f_gx_hy in which \c F is defined by \a compare
737     and both \c G and \c H are \c Dereferencer functors.
738
739     \see compose_f_gx_hy
740
741     \since New in yat 0.7
742   */
743  template<typename Pointer, class Compare>
744  compose_f_gx_hy<Compare, Dereferencer<Pointer>, Dereferencer<Pointer> >
745  make_ptr_compare(Pointer p, Compare compare)
746  {
747    return make_compose_f_gx_hy(compare, Dereferencer<Pointer>(),
748                                Dereferencer<Pointer>());
749  }
750
751  /**
752     Same as make_ptr_compare(2) except that std::less is used to
753     compare pointers.
754
755     \since New in yat 0.7
756   */
757  template<typename Pointer>
758  compose_f_gx_hy<std::less<typename std::iterator_traits<Pointer>::value_type>,
759                  Dereferencer<Pointer>, Dereferencer<Pointer> >
760  make_ptr_compare(Pointer p)
761  {
762    typedef typename std::iterator_traits<Pointer>::value_type value_type;
763    BOOST_CONCEPT_ASSERT((boost::LessThanComparable<value_type>));
764    std::less<value_type> compare;
765    return make_ptr_compare(p, compare);
766  }
767
768
769  ///
770  /// @brief Function converting a string to lower case
771  ///
772  std::string& to_lower(std::string& s);
773
774  ///
775  /// @brief Function converting a string to upper case
776  ///
777  std::string& to_upper(std::string& s);
778
779
780  // template implementations
781
782  template <typename Key, typename Tp, typename Compare, typename Alloc>
783  const Tp& get(const std::map<Key, Tp, Compare, Alloc>& m, const Key& key)
784  {
785    typename std::map<Key, Tp, Compare,Alloc>::const_iterator iter(m.find(key));
786    if (iter==m.end()) {
787      std::stringstream ss;
788      ss << "utility::get(const Map&, const Key&): `"
789         << key << "' not found in map\n";
790      throw runtime_error(ss.str());
791    }
792    return iter->second;
793  }
794
795}}} // of namespace utility, yat, and theplu
796#endif
Note: See TracBrowser for help on using the repository browser.