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

Last change on this file since 2239 was 2239, checked in by Peter, 12 years ago

closes #612

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 14.9 KB
Line 
1#ifndef _theplu_yat_utility_stl_utility_
2#define _theplu_yat_utility_stl_utility_
3
4// $Id: stl_utility.h 2239 2010-04-10 23:05:12Z 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 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 "DataWeight.h"
38#include "Exception.h"
39
40#include <boost/concept_check.hpp>
41#include <boost/iterator/transform_iterator.hpp>
42#include <boost/mpl/if.hpp>
43#include <boost/type_traits/add_const.hpp>
44#include <boost/type_traits/is_const.hpp>
45#include <boost/type_traits/remove_reference.hpp>
46
47#include <algorithm>
48#include <cmath>
49#include <exception>
50#include <functional>
51#include <map>
52#include <ostream>
53#include <sstream>
54#include <string>
55#include <utility>
56#include <vector>
57
58// We are intruding standard namespace, which might cause
59// conflicts. Let the user turn off these declarations by defining
60// YAT_STD_DISABE
61#ifndef YAT_STD_DISABLE
62namespace std {
63
64  ///
65  /// Print out a pair
66  ///
67  // This is in namespace std because we have not figured out how to have
68  // pair and its operator<< in different namespaces
69  template <class T1, class T2> 
70  std::ostream& operator<<(std::ostream& out, const std::pair<T1,T2>& p) 
71  { out << p.first << "\t" << p.second; return out; }
72
73}
74#endif
75
76namespace theplu {
77namespace yat {
78namespace utility {
79
80  /**
81     Functor class taking absolute value
82  */
83  template<typename T>
84  struct abs : std::unary_function<T, T>
85  {
86    /**
87       \return absolute value
88     */
89    inline T operator()(T x) const
90    { return std::abs(x); }
91  };
92
93
94  /**
95     See The C++ Standard Library - A Tutorial and Reference by
96     Nicolai M. Josuttis
97
98     If f is a binary functor, both g and h are unary functors, and
99     return type of g (and h) is convertible to F's argument type,
100     then compose_f_gx_hy can be used to create a functor equivalent
101     to \f$ f(g(x), h(y)) \f$
102
103     F must be an adaptable binary functor
104     G must be an adaptable unary functor
105     H must be an adaptable unary functor
106   */
107  template<class F, class G, class H>
108  class compose_f_gx_hy : std::binary_function<typename G::argument_type,
109                                               typename H::argument_type,
110                                               typename F::result_type>
111  {
112  public:
113    /**
114       \brief Constructor
115     */
116    compose_f_gx_hy(F f, G g, H h)
117      : f_(f), g_(g), h_(h) {}
118
119    /**
120       \brief Does the work
121     */
122    typename F::result_type
123    operator()(typename G::argument_type x, 
124               typename H::argument_type y) const
125    {
126      return f_(g_(x), h_(y));
127    }
128
129  private:
130    F f_;
131    G g_;
132    H h_;
133  };
134
135  /**
136     Convenient function to create a compose_f_gx_hy.
137
138     \see std::make_pair
139  */
140  template<class F, class G, class H>
141  compose_f_gx_hy<F, G, H> make_compose_f_gx_hy(F f, G g, H h)
142  {
143    return compose_f_gx_hy<F,G,H>(f,g,h);
144  } 
145
146  /**
147     Functor class to exponentiate values using std::exp
148
149     T should be either \c float, \c double, or \c long \c double
150
151     \since New in yat 0.5
152  */
153  template<typename T>
154  struct Exp : std::unary_function<T, T>
155  {
156    /**
157       \return exponentiated value
158     */
159    inline T operator()(T x) const
160    { return std::exp(x); }
161  };
162
163  /**
164     Same functionality as map::operator[] but the function does not
165     modify the map and the function throws if key does not exist in
166     the map.
167
168     \return const reference to m[k]
169
170     \since New in yat 0.7
171   */
172  template <typename Key, typename Tp, typename Compare, typename Alloc>
173  const Tp& get(const std::map<Key, Tp, Compare, Alloc>& m, const Key& k);
174
175
176  /**
177     Creating a map from a range [first, last) such that m[key]
178     returns a vector with indices of which element in [first, last)
179     that is equal to \a key, or more technically: m[element].size()
180     returns number of elements equal to \a element, and
181     m[*element][i] = distance(first, element) for every \a element in
182     [first, last) and \a i smaller than m[element].size().
183
184     Requirement: InputIterator's value type is assignable to Key
185
186     \since New in yat 0.5
187   */
188  template<typename InputIterator, typename Key, typename Comp>
189  void inverse(InputIterator first, InputIterator last,
190               std::map<Key, std::vector<size_t>, Comp >& m)
191  {
192    BOOST_CONCEPT_ASSERT((boost::InputIterator<InputIterator>));
193    BOOST_CONCEPT_ASSERT((boost::Convertible<typename std::iterator_traits<InputIterator>::value_type, Key>));
194    m.clear();
195    for (size_t i=0; first!=last; ++i, ++first)
196      m[*first].push_back(i);
197  }
198
199  /**
200     In the created multimap each element e will fulfill: \f$ *(first
201     + e->second) == e->first \f$
202
203     Requirement: InputIterator's value type is assignable to Key
204
205     \since New in yat 0.5
206   */
207  template<typename Key, typename InputIterator, typename Comp>
208  void inverse(InputIterator first, InputIterator last, 
209               std::multimap<Key, size_t, Comp>& m)
210  {
211    BOOST_CONCEPT_ASSERT((boost::InputIterator<InputIterator>));
212    BOOST_CONCEPT_ASSERT((boost::Convertible<typename std::iterator_traits<InputIterator>::value_type, Key>));
213    m.clear();
214    for (size_t i=0; first!=last; ++i, ++first)
215      m.insert(std::make_pair(*first, i));
216  }
217
218
219  /**
220     \brief Functor that behaves like std::less with the exception
221     that it treates NaN as a number larger than infinity.
222
223     This functor is useful when sorting ranges with NaNs. The problem
224     with NaNs is that std::less always returns \c false when one of
225     the arguments is NaN. That together with the fact that std::sort
226     only guarantees that an element \c i is never less than previous
227     element \c --i. Therefore {10, NaN, 2} is sorted according to
228     this definition, but most often it is desired that the 2 is
229     located before the 10 in the range. Using this functor, less_nan,
230     this can easily be achieved as std::sort(first, last, less_nan)
231
232     The default implementation uses std::isnan(T), which consequently
233     must be supported.
234
235     There is a specialization less_nan<DataWeight>
236
237     \since New in yat 0.6
238  */
239  template<typename T>
240  struct less_nan : std::binary_function<T, T, bool>
241  {
242    /**
243       \return \c true if x is less than y. NaNs are treated as a number
244       larger than infinity, which implies \c true is returned if y is
245       NaN and x is not.
246     */
247    inline bool operator()(T x, T y) const
248    { 
249      if (std::isnan(x))
250        return false;
251      if (std::isnan(y))
252        return true;
253      return x<y;
254    }
255  };
256
257
258  /**
259     \brief Specialization for DataWeight.
260   */
261  template<>
262  struct less_nan<DataWeight> 
263    : std::binary_function<DataWeight, DataWeight, bool>
264  {
265    /**
266       \return less_nan<double>(x.data(), y.data())
267     */
268    inline bool operator()(const DataWeight& x, const DataWeight& y) const
269    { 
270      less_nan<double> compare;
271      return compare(x.data(), y.data());
272    }
273  };
274
275
276  /**
277     Functor class to take logarithm
278
279     T should be either \c float, \c double, or \c long \c double
280
281     \since New in yat 0.5
282  */
283  template<typename T>
284  class Log : std::unary_function<T, T>
285  {
286  public:
287    /**
288       Default constructor using natural base \f$ e \f$
289     */
290    Log(void)
291      : log_base_(1.0) {}
292
293    /**
294       \param base Taking logarithm in which base, e.g. 2 or 10.
295    */
296    explicit Log(double base) : log_base_(std::log(base)) {}
297
298    /**
299       \return logarithm
300     */
301    inline T operator()(T x) const
302    { return std::log(x)/log_base_; }
303
304  private:
305    double log_base_;
306  };
307
308  /**
309     \return max of values
310   */
311  template <typename T>
312  T max(const T& a, const T& b, const T& c)
313  {
314    return std::max(std::max(a,b),c);
315  }
316
317
318  /**
319     \return max of values
320   */
321  template <typename T>
322  T max(const T& a, const T& b, const T& c, const T& d)
323  {
324    return std::max(std::max(a,b), std::max(c,d));
325  }
326
327
328  /**
329     \return max of values
330   */
331  template <typename T>
332  T max(const T& a, const T& b, const T& c, const T& d, const T& e)
333  {
334    return std::max(max(a,b,c,d), e);
335  }
336
337
338  /**
339     \return max of values
340   */
341  template <typename T>
342  T max(const T& a, const T& b, const T& c, const T& d, const T& e, const T& f)
343  {
344    return std::max(max(a,b,c,d), std::max(e,f));
345  }
346
347
348  ///
349  /// @brief Functor comparing pairs using second.
350  ///
351  /// STL provides operator< for the pair.first element, but none for
352  /// pair.second. This template provides this and can be used as the
353  /// comparison object in generic functions such as the STL sort.
354  ///
355  template <class T1,class T2>
356  struct pair_value_compare
357  {
358    ///
359    /// @return true if x.second<y.second or (!(y.second<y.second) and
360    /// x.first<y.first)
361    ///
362    inline bool operator()(const std::pair<T1,T2>& x,
363                           const std::pair<T1,T2>& y) {
364      return ((x.second<y.second) ||
365              (!(y.second<x.second) && (x.first<y.first))); 
366    }
367  };
368
369  /**
370     \brief Functor that return std::pair.first
371
372     \see pair_first_iterator
373
374     \since New in yat 0.5
375   */
376  template <class Pair>
377  struct PairFirst
378  {
379    /**
380       The type returned is Pair::first_type& with the exception when
381       Pair is const and Pair::first_type is non-const, in which case
382       const Pair::first_type& is return type.
383     */
384    typedef typename boost::mpl::if_<
385                  typename boost::is_const<Pair>::type, 
386                  typename boost::add_const<typename Pair::first_type>::type&,
387                  typename Pair::first_type&>::type result_type;
388   
389    /**
390       The argument type is Pair&.
391     */
392    typedef Pair& argument_type;
393
394    /**
395       \return p.first
396     */
397    inline result_type operator()(argument_type p) const
398    { return p.first; }
399
400  };
401
402
403  /**
404     \brief Functor that return std::pair.second
405
406     \see pair_second_iterator
407
408     \since New in yat 0.5
409   */
410  template <class Pair>
411  struct PairSecond
412  {
413    /**
414       The type returned is Pair::second_type& with the exception when
415       Pair is const and Pair::second_type is non-const, in which case
416       const Pair::first_type& is return type.
417     */
418    typedef typename boost::mpl::if_<
419                  typename boost::is_const<Pair>::type, 
420                  typename boost::add_const<typename Pair::second_type>::type&,
421                  typename Pair::second_type&>::type result_type;
422   
423    /**
424       The argument type is Pair&.
425     */
426    typedef Pair& argument_type;
427
428    /**
429       \return p.first
430     */
431    inline result_type operator()(argument_type p) const
432    { return p.second; }
433
434  };
435
436
437  /**
438     Creates a transform_iterator that transforms an iterator with
439     value type std::pair to an iterator with value type
440     std::pair::first_type. This can be used, for example, to
441     communicate between a std::map and std::vector
442
443     \code
444     std::map<std::string, int> map;
445     ...
446     std::vector<std::string> vec;
447     vec.resize(map.size());
448     std::copy(pair_first_iterator(map.begin()), pair_first_iterator(map.end()),
449               vec.begin());
450     \endcode
451
452     \since New in yat 0.5
453   */
454  template<class Iter>
455  boost::transform_iterator<
456    PairFirst<typename boost::remove_reference<
457                 typename std::iterator_traits<Iter>::reference
458                 >::type>,
459    Iter> pair_first_iterator(Iter i)
460  {
461    // We are going via ::reference in order to remain const info;
462    // ::value_type does not contain const information.
463    typedef typename std::iterator_traits<Iter>::reference ref_type;
464    typedef typename boost::remove_reference<ref_type>::type val_type;
465    typedef PairFirst<val_type> PF; 
466    return boost::transform_iterator<PF, Iter>(i, PF());
467  }
468
469
470  /**
471     Creates a transform_iterator that transforms an iterator with
472     value type std::pair to an iterator with value type
473     std::pair::second_type. This can be used, for example, to
474     communicate between a std::map and std::vector
475
476     \code
477     std::map<std::string, int> map;
478     ...
479     std::vector<int> vec(map.size(),0);
480     std::copy(vec.begin(), vec.end(), pair_second_iterator(map.begin()));
481     \endcode
482
483     \since New in yat 0.5
484   */
485  template<class Iter>
486  boost::transform_iterator<
487    PairSecond<typename boost::remove_reference<
488                 typename std::iterator_traits<Iter>::reference
489                 >::type>,
490    Iter> pair_second_iterator(Iter i)
491  {
492    // We are going via ::reference in order to remain const info;
493    // ::value_type does not contain const information.
494    typedef typename std::iterator_traits<Iter>::reference ref_type;
495    typedef typename boost::remove_reference<ref_type>::type val_type;
496    typedef PairSecond<val_type> PS; 
497    return boost::transform_iterator<PS, Iter>(i, PS());
498  }
499
500
501  /**
502     Adaptor class that can be used to compare pointers, T*, when you
503     want to compare them with respect to the objects they point to.
504
505     Example:
506     \code
507     std::vector<MyClass*> vec(18);
508     ...
509     PtrCompare<MyClass, std::greater<MyClass> > ptr_compare;
510     std::sort(vec.begin(), vec.end(), ptr_compare);
511     \endcode
512
513     The class Compare must be a <a
514     href="http://www.sgi.com/tech/stl/BinaryFunction.html">binary
515     functor</a> that takes two \c const \c T& and returns \c bool.
516
517     \since New in yat 0.7
518   */
519  template<typename T, class Compare = std::less<T> >
520  class PtrCompare : std::binary_function<T const* const, T const* const, bool>
521  {
522  public:
523    /**
524       \brief Constructor.
525
526       Creates an instance of Compare using its default constructor.
527     */
528    PtrCompare(void)
529    {
530      BOOST_CONCEPT_ASSERT((boost::BinaryFunction<Compare, bool, const T&, 
531                            const T&>));
532    }
533
534    /**
535       \brief Constructor.
536
537       Creates a copy of \a c that will be used later.
538     */
539    PtrCompare(Compare c)
540      : compare_(c) 
541    {
542      BOOST_CONCEPT_ASSERT((boost::BinaryFunction<Compare, bool, const T&, 
543                            const T&>));
544    }
545
546    /**
547       \return true iff Compare(* \a lhs, * \a rhs ) is true.
548     */
549    bool operator()(T const* const lhs, T const* const rhs) const
550    { 
551      return compare_(*lhs, *rhs); 
552    }
553  private:
554    Compare compare_;
555
556    // using compiler generated copy
557    // PtrCompare(const PtrCompare&)
558    // PtrCompare& operator=(const PtrCompare&)
559  };
560
561  ///
562  /// @brief Function converting a string to lower case
563  ///
564  std::string& to_lower(std::string& s);
565
566  ///
567  /// @brief Function converting a string to upper case
568  ///
569  std::string& to_upper(std::string& s);
570
571
572  // template implementations
573
574  template <typename Key, typename Tp, typename Compare, typename Alloc>
575  const Tp& get(const std::map<Key, Tp, Compare, Alloc>& m, const Key& key)
576  {
577    typename std::map<Key, Tp, Compare, Alloc>::const_iterator iter(m.find(key));
578    if (iter==m.end()) {
579      std::stringstream ss;
580      ss << "yat: get(const Map&, const Key&): Key not found in Map\n";
581      throw runtime_error(ss.str());
582    }
583    return iter->second;
584  }
585
586
587
588}}} // of namespace utility, yat, and theplu
589
590#endif
Note: See TracBrowser for help on using the repository browser.