source: trunk/yat/utility/stl_utility.h

Last change on this file was 3792, checked in by Peter, 19 months ago

update copyright years

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 24.6 KB
Line 
1#ifndef _theplu_yat_utility_stl_utility_
2#define _theplu_yat_utility_stl_utility_
3
4// $Id: stl_utility.h 3792 2019-04-12 07:15:09Z 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, 2013, 2014, 2015, 2016, 2018 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, compose_f_gx, and compose_f_gx_hx
162
163     Here is an example using the class to construct a functor that
164     compares std::pairs ignoring \c second.
165
166     \code
167     vector<pair<string, foo> > data;
168     data.push_back(make_pair("Orange", foo(2));
169     data.push_back(make_pair("Orange", foo(1));
170     data.push_back(make_pair("Apple", foo(10));
171     typedef PairFirst<const pair<string, foo> > PF;
172     compose_f_gx_hy<less<string>, PF, PF> compare;
173     sort(data.begin(), data.end(), compare);
174     \endcode
175
176   */
177  template<class F, class G, class H>
178  class compose_f_gx_hy :
179    public std::binary_function<typename G::argument_type,
180                                typename H::argument_type,
181                                typename F::result_type>
182  {
183  public:
184    /**
185       \brief default constructor
186
187       Requires that F, G, and H have default constructors
188    */
189    compose_f_gx_hy(void) {}
190
191    /**
192       \brief Constructor
193     */
194    compose_f_gx_hy(F f, G g, H h)
195      : f_(f), g_(g), h_(h)
196    {
197    }
198
199    /**
200       \brief Does the work
201     */
202    typename F::result_type operator()(typename G::argument_type x,
203                                       typename H::argument_type y) const
204    {
205      return f_(g_(x), h_(y));
206    }
207
208  private:
209    F f_;
210    G g_;
211    H h_;
212  };
213
214  /**
215     Convenient function to create a compose_f_gx_hy.
216
217     \relates compose_f_gx_hy
218
219     \see std::make_pair
220  */
221  template<class F, class G, class H>
222  compose_f_gx_hy<F, G, H> make_compose_f_gx_hy(F f, G g, H h)
223  {
224    return compose_f_gx_hy<F,G,H>(f,g,h);
225  }
226
227
228  /**
229     See The C++ Standard Library - A Tutorial and Reference by
230     Nicolai M. Josuttis
231
232     If f is a unary functor, g is a binary functor, and return type
233     of g is convertible to F's argument type, then
234     compose_f_gxy can be used to create a functor equivalent to
235     \f$ f(g(x,y)) \f$
236
237     - F must be an <a
238     href="http://www.sgi.com/tech/stl/AdaptableUnaryFunction.html">
239     AdaptableUnaryFunction</a>
240     - G must be an <a
241     href="http://www.sgi.com/tech/stl/AdaptableBinaryFunction.html">
242     AdaptableBinaryFunction</a>
243     - \c G::result_type is convertible to \c F::argument_type
244
245     \see compose_f_gx_hy, compose_f_gx, and compose_f_gx_hx
246
247     \since New in yat 0.7
248   */
249  template<class F, class G>
250  class compose_f_gxy :
251    public std::binary_function<typename G::first_argument_type,
252                                typename G::second_argument_type,
253                                typename F::result_type>
254  {
255  public:
256    /**
257       \brief default constructor
258
259       Requires that F, G, and H have default constructors
260    */
261    compose_f_gxy(void) {}
262
263    /**
264       \brief Constructor
265     */
266    compose_f_gxy(F f, G g)
267      : f_(f), g_(g)
268    {
269    }
270
271    /**
272       \brief Does the work
273     */
274    typename F::result_type
275    operator()(typename G::first_argument_type x,
276               typename G::second_argument_type y) const
277    {
278      return f_(g_(x,y));
279    }
280
281  private:
282    F f_;
283    G g_;
284  };
285
286  /**
287     Convenient function to create a compose_f_gxy.
288
289     \relates compose_f_gxy
290
291     \see std::make_pair
292
293     \since New in yat 0.7
294  */
295  template<class F, class G>
296  compose_f_gxy<F, G> make_compose_f_gxy(F f, G g)
297  {
298    return compose_f_gxy<F,G>(f,g);
299  }
300
301
302  /**
303     See The C++ Standard Library - A Tutorial and Reference by
304     Nicolai M. Josuttis
305
306     If f is a unary functor, g is a unary functor, and return type of
307     g is convertible to F's argument type, then compose_f_gx can be
308     used to create a functor equivalent to \f$ f(g(x)) \f$
309
310     - F must be an <a
311     href="http://www.sgi.com/tech/stl/AdaptableBinaryFunction.html">
312     AdaptableBinaryFunction</a>
313     - G must be an <a
314     href="http://www.sgi.com/tech/stl/AdaptableUnaryFunction.html">
315     AdaptableUnaryFunction</a>
316     - \c G::result_type is convertible to \c F::argument_type
317
318     \see compose_f_gx_hy, compose_f_gxy, and compose_f_gx_hx
319
320     \see <a href="http://www.sgi.com/tech/stl/unary_compose.html">
321     unary_compose</a> (SGI extension)
322
323     \since New in yat 0.7
324   */
325  template<class F, class G>
326  class compose_f_gx : public std::unary_function<typename G::argument_type,
327                                                  typename F::result_type>
328  {
329  public:
330    /**
331       \brief default constructor
332
333       Requires that F and G have default constructors
334    */
335    compose_f_gx(void) {}
336
337    /**
338       \brief Constructor
339     */
340    compose_f_gx(F f, G g)
341      : f_(f), g_(g)
342    {
343    }
344
345    /**
346       \brief Does the work
347     */
348    typename F::result_type
349    operator()(typename G::argument_type x) const
350    {
351      return f_(g_(x));
352    }
353
354  private:
355    F f_;
356    G g_;
357  };
358
359  /**
360     Convenient function to create a compose_f_gx.
361
362     \relates compose_f_gx
363
364     \see std::make_pair
365
366     \since New in yat 0.7
367  */
368  template<class F, class G>
369  compose_f_gx<F, G> make_compose_f_gx(F f, G g)
370  {
371    return compose_f_gx<F,G>(f,g);
372  }
373
374
375  /**
376     If f is a binary functor, g and h a unary functors, return
377     type of g is convertible to F's first argument type, and return
378     type of h is convertible to F's second argument type, then
379     compose_f_gx_hx can be used to create a functor equivalent to \f$
380     f(g(x), h(x)) \f$
381
382     - F must be an <a
383     href="http://www.sgi.com/tech/stl/AdaptableBinaryFunction.html">
384     AdaptableBinaryFunction</a>
385     - G must be an <a
386     href="http://www.sgi.com/tech/stl/AdaptableUnaryFunction.html">
387     AdaptableUnaryFunction</a>
388     - H must be an <a
389     href="http://www.sgi.com/tech/stl/AdaptableUnaryFunction.html">
390     AdaptableUnaryFunction</a>
391     - \c G::result_type is convertible to \c F::first_argument_type
392     - \c H::result_type is convertible to \c F::second_argument_type
393
394     \see compose_f_gx_hy, compose_f_gxy, and compose_f_gx
395
396     \see <a href="http://www.sgi.com/tech/stl/binary_compose.html">
397     binary_compose</a> (SGI extension)
398
399     \since New in yat 0.11
400   */
401  template<class F, class G, class H>
402  class compose_f_gx_hx : public std::unary_function<typename G::argument_type,
403                                                     typename F::result_type>
404  {
405  public:
406    /**
407       \brief default constructor
408
409       Requires that F, G, and H have default constructors
410    */
411    compose_f_gx_hx(void) {}
412
413    /**
414       \brief Constructor
415     */
416    compose_f_gx_hx(F f, G g, H h)
417      : f_(f), g_(g), h_(h)
418    {
419    }
420
421    /**
422       \brief Does the work
423     */
424    typename F::result_type operator()(typename G::argument_type x) const
425    {
426      return f_(g_(x), h_(x));
427    }
428
429  private:
430    F f_;
431    G g_;
432    H h_;
433  };
434
435  /**
436     Convenient function to create a compose_f_gx_hx.
437
438     \relates compose_f_gx_hx
439
440     \see std::make_pair
441
442     \since New in yat 0.11
443  */
444  template<class F, class G, class H>
445  compose_f_gx_hx<F, G, H> make_compose_f_gx_hx(F f, G g, H h)
446  {
447    return compose_f_gx_hx<F,G,H>(f,g,h);
448  }
449
450
451  /**
452     Functor class to exponentiate values using std::exp
453
454     T should be either \c float, \c double, or \c long \c double
455
456     \since New in yat 0.5
457  */
458  template<typename T>
459  struct Exp : std::unary_function<T, T>
460  {
461    /**
462       \return exponentiated value
463     */
464    inline T operator()(T x) const
465    { return std::exp(x); }
466  };
467
468  /**
469     \brief Identity functor that returns its argument
470
471     \since New in yat 0.7
472   */
473  template<typename T>
474  struct Identity : public std::unary_function<T, T>
475  {
476    /// \return \a arg
477    T operator()(T arg) const { return arg; }
478  };
479
480
481  /**
482     \brief reduce size and capacity to zero
483
484     The standard provides a member function clear(void), which clears
485     the contents of the vector i.e. sets the size to zero. However,
486     the member function might leave the capacity unchanged and
487     sometimes, when it's desiribale to save memory usage e.g., it
488     preferable to use this function, which reduces the capacity to zero.
489
490     \since new in yat 0.13
491   */
492  template<typename T>
493  void clear(std::vector<T>& vec)
494  {
495    std::vector<T> other;
496    vec.swap(other);
497  }
498
499
500  /**
501     Same functionality as map::operator[] but the function does not
502     modify the map and the function throws if key does not exist in
503     the map.
504
505     Type Requirment:
506     - \a Key2 is convertible to Key
507
508     \return const reference to m[k]
509
510     \throw get_error if key \a k does not exist in map \a m
511
512     Similar to std::map::at(const Key& ) in c++11.
513
514     \since New in yat 0.7
515   */
516  template <typename Key, typename Tp, typename Compare, typename Alloc,
517            typename Key2>
518  const Tp& get(const std::map<Key, Tp, Compare, Alloc>& m, const Key2& k);
519
520  /**
521     \brief error class used in
522     get(const std::map<Key, Tp, Compare, Alloc>& m, const Key& k)
523
524     \since yat 0.13
525   */
526  template<typename Key>
527  class get_error : public runtime_error
528  {
529  public:
530    /// \brief constructor
531    get_error(const std::string& msg, const Key& key)
532      : runtime_error(msg), key_(key) {}
533    /// \brief destructor
534    virtual ~get_error(void) throw () {}
535    /// access the key object
536    const Key& key(void) const { return key_; }
537  private:
538    Key key_;
539  };
540
541  /**
542     Creating a map from a range [first, last) such that m[key]
543     returns a vector with indices of which element in [first, last)
544     that is equal to \a key, or more technically: m[element].size()
545     returns number of elements equal to \a element, and
546     m[*element][i] = distance(first, element) for every \a element in
547     [first, last) and \a i smaller than m[element].size().
548
549     Requirement: InputIterator's value type is assignable to Key
550
551     \since New in yat 0.5
552   */
553  template<typename InputIterator, typename Key, typename Comp>
554  void inverse(InputIterator first, InputIterator last,
555               std::map<Key, std::vector<size_t>, Comp >& m)
556  {
557    BOOST_CONCEPT_ASSERT((boost::InputIterator<InputIterator>));
558    BOOST_CONCEPT_ASSERT((boost::Convertible<typename std::iterator_traits<InputIterator>::value_type, Key>));
559    m.clear();
560    for (size_t i=0; first!=last; ++i, ++first)
561      m[*first].push_back(i);
562  }
563
564  /**
565     In the created multimap each element e will fulfill: \f$ *(first
566     + e->second) == e->first \f$
567
568     Requirement: InputIterator's value type is assignable to Key
569
570     \since New in yat 0.5
571   */
572  template<typename Key, typename InputIterator, typename Comp>
573  void inverse(InputIterator first, InputIterator last,
574               std::multimap<Key, size_t, Comp>& m)
575  {
576    BOOST_CONCEPT_ASSERT((boost::InputIterator<InputIterator>));
577    BOOST_CONCEPT_ASSERT((boost::Convertible<typename std::iterator_traits<InputIterator>::value_type, Key>));
578    m.clear();
579    for (size_t i=0; first!=last; ++i, ++first)
580      m.insert(std::make_pair(*first, i));
581  }
582
583
584  /**
585     Create a map mapping from values in range [first, last) to the
586     distance from first.
587
588     Post-condition: m[first[i]] == i (for all i that correspond to a
589     unique element). For non-unique element behaviour is undefined.
590
591     Requirement: InputIterator's value type is assignable to Key
592
593     \since New in yat 0.10
594   */
595  template<typename InputIterator, typename Key, typename Comp>
596  void inverse(InputIterator first, InputIterator last,
597               std::map<Key, size_t, Comp >& m)
598  {
599    BOOST_CONCEPT_ASSERT((boost::InputIterator<InputIterator>));
600    BOOST_CONCEPT_ASSERT((boost::Convertible<typename std::iterator_traits<InputIterator>::value_type, Key>));
601    m.clear();
602    for (size_t i=0; first!=last; ++i, ++first)
603      m[*first] = i;
604  }
605
606  /**
607     \brief Functor that behaves like std::less with the exception
608     that it treats NaN as a number larger than infinity.
609
610     This functor is useful when sorting ranges with NaNs. The problem
611     with NaNs is that std::less always returns \c false when one of
612     the arguments is NaN. That together with the fact that std::sort
613     only guarantees that an element \c i is never less than previous
614     element \c --i. Therefore {10, NaN, 2} is sorted according to
615     this definition, but most often it is desired that the 2 is
616     located before the 10 in the range. Using this functor, less_nan,
617     this can easily be achieved as std::sort(first, last, less_nan)
618
619     The default implementation uses std::isnan(T), which consequently
620     must be supported.
621
622     There is a specialization less_nan<DataWeight>
623
624     \since New in yat 0.6
625  */
626  template<typename T>
627  struct less_nan : std::binary_function<T, T, bool>
628  {
629    /**
630       \return \c true if x is less than y. NaNs are treated as a number
631       larger than infinity, which implies \c true is returned if y is
632       NaN and x is not.
633     */
634    inline bool operator()(T x, T y) const
635    {
636      if (std::isnan(x))
637        return false;
638      if (std::isnan(y))
639        return true;
640      return x<y;
641    }
642  };
643
644
645  /**
646     \brief Specialization for DataWeight.
647   */
648  template<>
649  struct less_nan<DataWeight>
650    : std::binary_function<DataWeight, DataWeight, bool>
651  {
652    /**
653       \return less_nan<double>(x.data(), y.data())
654     */
655    inline bool operator()(const DataWeight& x, const DataWeight& y) const
656    {
657      less_nan<double> compare;
658      return compare(x.data(), y.data());
659    }
660  };
661
662
663  /**
664     Functor class to take logarithm
665
666     T should be either \c float, \c double, or \c long \c double
667
668     \since New in yat 0.5
669  */
670  template<typename T>
671  class Log : std::unary_function<T, T>
672  {
673  public:
674    /**
675       Default constructor using natural base \f$ e \f$
676     */
677    Log(void)
678      : log_base_(1.0) {}
679
680    /**
681       \param base Taking logarithm in which base, e.g. 2 or 10.
682    */
683    explicit Log(double base) : log_base_(std::log(base)) {}
684
685    /**
686       \return logarithm
687     */
688    inline T operator()(T x) const
689    { return std::log(x)/log_base_; }
690
691  private:
692    double log_base_;
693  };
694
695  /**
696     \return max of values
697   */
698  template <typename T>
699  T max(const T& a, const T& b, const T& c)
700  {
701    return std::max(std::max(a,b),c);
702  }
703
704
705  /**
706     \return max of values
707   */
708  template <typename T>
709  T max(const T& a, const T& b, const T& c, const T& d)
710  {
711    return std::max(std::max(a,b), std::max(c,d));
712  }
713
714
715  /**
716     \return max of values
717   */
718  template <typename T>
719  T max(const T& a, const T& b, const T& c, const T& d, const T& e)
720  {
721    return std::max(max(a,b,c,d), e);
722  }
723
724
725  /**
726     \return max of values
727   */
728  template <typename T>
729  T max(const T& a, const T& b, const T& c, const T& d, const T& e, const T& f)
730  {
731    return std::max(max(a,b,c,d), std::max(e,f));
732  }
733
734
735  ///
736  /// @brief Functor comparing pairs using second.
737  ///
738  /// STL provides operator< for the pair.first element, but none for
739  /// pair.second. This template provides this and can be used as the
740  /// comparison object in generic functions such as the STL sort.
741  ///
742  template <class T1,class T2>
743  struct pair_value_compare
744  {
745    ///
746    /// @return true if x.second<y.second or (!(y.second<y.second) and
747    /// x.first<y.first)
748    ///
749    inline bool operator()(const std::pair<T1,T2>& x,
750                           const std::pair<T1,T2>& y) {
751      return ((x.second<y.second) ||
752              (!(y.second<x.second) && (x.first<y.first)));
753    }
754  };
755
756  /**
757     \brief Functor that return std::pair.first
758
759     \see pair_first_iterator
760
761     \since New in yat 0.5
762   */
763  template <class Pair>
764  struct PairFirst
765  {
766    /**
767       The type returned is Pair::first_type& with the exception when
768       Pair is const and Pair::first_type is non-const, in which case
769       const Pair::first_type& is return type.
770     */
771    typedef typename boost::mpl::if_<
772                  typename boost::is_const<Pair>::type,
773                  typename boost::add_const<typename Pair::first_type>::type&,
774                  typename Pair::first_type&>::type result_type;
775
776    /**
777       The argument type is Pair&.
778     */
779    typedef Pair& argument_type;
780
781    /**
782       \return p.first
783     */
784    inline result_type operator()(argument_type p) const
785    { return p.first; }
786
787  };
788
789
790  /**
791     \brief Functor that return std::pair.second
792
793     \see pair_second_iterator
794
795     \since New in yat 0.5
796   */
797  template <class Pair>
798  struct PairSecond
799  {
800    /**
801       The type returned is Pair::second_type& with the exception when
802       Pair is const and Pair::second_type is non-const, in which case
803       const Pair::first_type& is return type.
804     */
805    typedef typename boost::mpl::if_<
806                  typename boost::is_const<Pair>::type,
807                  typename boost::add_const<typename Pair::second_type>::type&,
808                  typename Pair::second_type&>::type result_type;
809
810    /**
811       The argument type is Pair&.
812     */
813    typedef Pair& argument_type;
814
815    /**
816       \return p.first
817     */
818    inline result_type operator()(argument_type p) const
819    { return p.second; }
820
821  };
822
823
824  /**
825     Creates a transform_iterator that transforms an iterator with
826     value type std::pair to an iterator with value type
827     std::pair::first_type. This can be used, for example, to
828     communicate between a std::map and std::vector
829
830     \code
831     std::map<std::string, int> map;
832     ...
833     std::vector<std::string> vec;
834     vec.resize(map.size());
835     std::copy(pair_first_iterator(map.begin()), pair_first_iterator(map.end()),
836               vec.begin());
837     \endcode
838
839     \since New in yat 0.5
840   */
841  template<class Iter>
842  boost::transform_iterator<
843    PairFirst<typename boost::remove_reference<
844                 typename std::iterator_traits<Iter>::reference
845                 >::type>,
846    Iter> pair_first_iterator(Iter i)
847  {
848    // We are going via ::reference in order to remain const info;
849    // ::value_type does not contain const information.
850    typedef typename std::iterator_traits<Iter>::reference ref_type;
851    typedef typename boost::remove_reference<ref_type>::type val_type;
852    typedef PairFirst<val_type> PF;
853    return boost::transform_iterator<PF, Iter>(i, PF());
854  }
855
856
857  /**
858     Creates a transform_iterator that transforms an iterator with
859     value type std::pair to an iterator with value type
860     std::pair::second_type. This can be used, for example, to
861     communicate between a std::map and std::vector
862
863     \code
864     std::map<std::string, int> map;
865     ...
866     std::vector<int> vec(map.size(),0);
867     std::copy(vec.begin(), vec.end(), pair_second_iterator(map.begin()));
868     \endcode
869
870     \since New in yat 0.5
871   */
872  template<class Iter>
873  boost::transform_iterator<
874    PairSecond<typename boost::remove_reference<
875                 typename std::iterator_traits<Iter>::reference
876                 >::type>,
877    Iter> pair_second_iterator(Iter i)
878  {
879    // We are going via ::reference in order to remain const info;
880    // ::value_type does not contain const information.
881    typedef typename std::iterator_traits<Iter>::reference ref_type;
882    typedef typename boost::remove_reference<ref_type>::type val_type;
883    typedef PairSecond<val_type> PS;
884    return boost::transform_iterator<PS, Iter>(i, PS());
885  }
886
887
888  /**
889     Convenient function that creates a binary predicate that can be
890     used to compare pointers when you want to compare them with
891     respect to the objects they point to.
892
893     Example:
894     \code
895     std::vector<MyClass*> vec(18);
896     ...
897     std::sort(vec.begin(), vec.end(),
898               make_ptr_compare(vec[0], std::greater<MyClass>()));
899     \endcode
900
901
902     Type Requirement:
903     - \a compare must be a <a
904     href="http://www.sgi.com/tech/stl/AdaptableBinaryPredicate.html">Adaptable
905     Binary Predicate</a>.
906     - value_type of Pointer must be convertible to argument_type of
907       compare
908
909     \return a compose_f_gx_hy in which \c F is defined by \a compare
910     and both \c G and \c H are \c Dereferencer functors.
911
912     \see compose_f_gx_hy
913
914     \since New in yat 0.7
915   */
916  template<typename Pointer, class Compare>
917  compose_f_gx_hy<Compare, Dereferencer<Pointer>, Dereferencer<Pointer> >
918  make_ptr_compare(Pointer p, Compare compare)
919  {
920    return make_compose_f_gx_hy(compare, Dereferencer<Pointer>(),
921                                Dereferencer<Pointer>());
922  }
923
924  /**
925     Same as make_ptr_compare(2) except that std::less is used to
926     compare pointers.
927
928     \since New in yat 0.7
929   */
930  template<typename Pointer>
931  compose_f_gx_hy<std::less<typename std::iterator_traits<Pointer>::value_type>,
932                  Dereferencer<Pointer>, Dereferencer<Pointer> >
933  make_ptr_compare(Pointer p)
934  {
935    typedef typename std::iterator_traits<Pointer>::value_type value_type;
936    BOOST_CONCEPT_ASSERT((boost::LessThanComparable<value_type>));
937    std::less<value_type> compare;
938    return make_ptr_compare(p, compare);
939  }
940
941
942  ///
943  /// @brief Function converting a string to lower case
944  ///
945  std::string& to_lower(std::string& s);
946
947  ///
948  /// @brief Function converting a string to upper case
949  ///
950  std::string& to_upper(std::string& s);
951
952
953  // template implementations
954
955  template <typename Key, typename Tp, typename Compare, typename Alloc,
956            typename Key2>
957  const Tp& get(const std::map<Key, Tp, Compare, Alloc>& m, const Key2& key)
958  {
959    BOOST_CONCEPT_ASSERT((boost::Convertible<Key2, Key>));
960    typename std::map<Key, Tp, Compare,Alloc>::const_iterator iter(m.find(key));
961    if (iter==m.end()) {
962      // Avoid throw exception with Key2 because we do not want to
963      // require that Key2 is copy constructible. We know that Key is
964      // copy constructible from std::map requirement.
965      throw
966        get_error<Key>("utility::get(const Map&, const Key&): key not found",
967                       key);
968    }
969    return iter->second;
970  }
971
972}}} // of namespace utility, yat, and theplu
973#endif
Note: See TracBrowser for help on using the repository browser.