Statistics
| Revision:

root / tmp / org.txm.statsengine.r.core.win32 / res / win32 / library / BH / include / boost / algorithm / cxx11 / is_permutation.hpp @ 2486

History | View | Annotate | Download (8.1 kB)

1
/*
2
   Copyright (c) Marshall Clow 2011-2012.
3

4
   Distributed under the Boost Software License, Version 1.0. (See accompanying
5
   file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6
*/
7

    
8
/// \file  is_permutation.hpp
9
/// \brief Is a sequence a permutation of another sequence
10
/// \author Marshall Clow
11

    
12
#ifndef BOOST_ALGORITHM_IS_PERMUTATION11_HPP
13
#define BOOST_ALGORITHM_IS_PERMUTATION11_HPP
14

    
15
#include <algorithm>    // for std::less, tie, mismatch and is_permutation (if available)
16
#include <utility>      // for std::make_pair
17
#include <functional>   // for std::equal_to
18
#include <iterator>
19

    
20
#include <boost/range/begin.hpp>
21
#include <boost/range/end.hpp>
22
#include <boost/utility/enable_if.hpp>
23
#include <boost/type_traits/is_same.hpp>
24

    
25
namespace boost { namespace algorithm {
26

    
27
/// \cond DOXYGEN_HIDE
28
namespace detail {
29
    template <typename Predicate, typename Iterator>
30
    struct value_predicate {
31
        value_predicate ( Predicate p, Iterator it ) : p_ ( p ), it_ ( it ) {}
32

    
33
        template <typename T1>
34
        bool operator () ( const T1 &t1 ) const { return p_ ( *it_, t1 ); }
35
    private:
36
        Predicate p_;
37
        Iterator it_;
38
        };
39
        
40
//  Preconditions:
41
//  1. The sequences are the same length
42
//  2. Any common elements on the front have been removed (not necessary for correctness, just for performance)
43
    template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate >
44
    bool is_permutation_inner ( ForwardIterator1 first1, ForwardIterator1 last1,
45
                                ForwardIterator2 first2, ForwardIterator2 last2,
46
                                BinaryPredicate p ) {
47
        //  for each unique value in the sequence [first1,last1), count how many times
48
        //  it occurs, and make sure it occurs the same number of times in [first2, last2)
49
            for ( ForwardIterator1 iter = first1; iter != last1; ++iter ) {
50
                value_predicate<BinaryPredicate, ForwardIterator1> pred ( p, iter );
51

    
52
            /*  For each value we haven't seen yet... */
53
                if ( std::find_if ( first1, iter, pred ) == iter ) {
54
                    std::size_t dest_count = std::count_if ( first2, last2, pred );
55
                    if ( dest_count == 0 || dest_count != (std::size_t) std::count_if ( iter, last1, pred ))
56
                        return false;
57
                    }
58
                }
59

    
60
        return true;
61
        }                      
62

    
63
    template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate>
64
    bool is_permutation_tag ( ForwardIterator1 first1, ForwardIterator1 last1, 
65
                          ForwardIterator2 first2, ForwardIterator2 last2, 
66
                          BinaryPredicate p,
67
                          std::forward_iterator_tag, std::forward_iterator_tag ) {
68

    
69
    //  Skip the common prefix (if any)
70
        while ( first1 != last1 && first2 != last2 && p ( *first1, *first2 )) {
71
            ++first1;
72
            ++first2;
73
            }
74
        if ( first1 != last1 && first2 != last2 )
75
            return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2,
76
                std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> ());
77
        return first1 == last1 && first2 == last2;
78
        }
79

    
80
    template <class RandomAccessIterator1, class RandomAccessIterator2, class BinaryPredicate>
81
    bool is_permutation_tag ( RandomAccessIterator1 first1, RandomAccessIterator1 last1, 
82
                          RandomAccessIterator2 first2, RandomAccessIterator2 last2, 
83
                          BinaryPredicate p,
84
                          std::random_access_iterator_tag, std::random_access_iterator_tag ) {
85
    //  Cheap check
86
        if ( std::distance ( first1, last1 ) != std::distance ( first2, last2 ))
87
            return false;
88
    //  Skip the common prefix (if any)
89
        while ( first1 != last1 && first2 != last2 && p ( *first1, *first2 )) {
90
            ++first1;
91
            ++first2;
92
            }
93

    
94
        if ( first1 != last1 && first2 != last2 )
95
            return is_permutation_inner (first1, last1, first2, last2, p);
96
        return first1 == last1 && first2 == last2;
97
        }
98

    
99
}
100
/// \endcond
101

    
102
/// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2, BinaryPredicate p )
103
/// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
104
///
105
/// \param first1   The start of the input sequence
106
/// \param last1    One past the end of the input sequence
107
/// \param first2   The start of the second sequence
108
/// \param p        The predicate to compare elements with
109
///
110
/// \note           This function is part of the C++2011 standard library.
111
///  We will use the standard one if it is available,
112
///     otherwise we have our own implementation.
113
template< class ForwardIterator1, class ForwardIterator2, class BinaryPredicate >
114
bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1,
115
                      ForwardIterator2 first2, BinaryPredicate p )
116
{
117
//  Skip the common prefix (if any)
118
    std::pair<ForwardIterator1, ForwardIterator2> eq = std::mismatch (first1, last1, first2, p);
119
    first1 = eq.first;
120
    first2 = eq.second;
121
    if ( first1 != last1 ) {
122
    //  Create last2
123
        ForwardIterator2 last2 = first2;
124
        std::advance ( last2, std::distance (first1, last1));
125
        return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2, p );
126
        }
127

    
128
    return true;
129
}
130

    
131
/// \fn is_permutation ( ForwardIterator1 first, ForwardIterator1 last, ForwardIterator2 first2 )
132
/// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
133
///
134
/// \param first1   The start of the input sequence
135
/// \param last2    One past the end of the input sequence
136
/// \param first2   The start of the second sequence
137
/// \note           This function is part of the C++2011 standard library.
138
///  We will use the standard one if it is available,
139
///     otherwise we have our own implementation.
140
template< class ForwardIterator1, class ForwardIterator2 >
141
bool is_permutation ( ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2 )
142
{
143
//  How should I deal with the idea that ForwardIterator1::value_type
144
//  and ForwardIterator2::value_type could be different? Define my own comparison predicate?
145
//  Skip the common prefix (if any)
146
    std::pair<ForwardIterator1, ForwardIterator2> eq = std::mismatch (first1, last1, first2 );
147
    first1 = eq.first;
148
    first2 = eq.second;
149
    if ( first1 != last1 ) {
150
    //  Create last2
151
        ForwardIterator2 last2 = first2;
152
        std::advance ( last2, std::distance (first1, last1));
153
        return boost::algorithm::detail::is_permutation_inner ( first1, last1, first2, last2,
154
            std::equal_to<typename std::iterator_traits<ForwardIterator1>::value_type> ());
155
        }
156
    return true;
157
}
158

    
159

    
160
/// \fn is_permutation ( const Range &r, ForwardIterator first2 )
161
/// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
162
///
163
/// \param r        The input range
164
/// \param first2   The start of the second sequence
165
template <typename Range, typename ForwardIterator>
166
bool is_permutation ( const Range &r, ForwardIterator first2 )
167
{
168
    return boost::algorithm::is_permutation (boost::begin (r), boost::end (r), first2 );
169
}
170

    
171
/// \fn is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred )
172
/// \brief Tests to see if the sequence [first,last) is a permutation of the sequence starting at first2
173
///
174
/// \param r        The input range
175
/// \param first2   The start of the second sequence
176
/// \param pred     The predicate to compare elements with
177
///
178
//  Disable this template when the first two parameters are the same type
179
//  That way the non-range version will be chosen.
180
template <typename Range, typename ForwardIterator, typename BinaryPredicate>
181
typename boost::disable_if_c<boost::is_same<Range, ForwardIterator>::value, bool>::type
182
is_permutation ( const Range &r, ForwardIterator first2, BinaryPredicate pred )
183
{
184
    return boost::algorithm::is_permutation (boost::begin (r), boost::end (r), first2, pred );
185
}
186

    
187
}}
188

    
189
#endif  // BOOST_ALGORITHM_IS_PERMUTATION11_HPP