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

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

docs: clarification and code example for Dereferencer

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