/*
* Copyright 2008-2010 NVIDIA Corporation
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
/*! \file unique.h
* \brief Move unique elements to the front of a sequence.
*/
#pragma once
#include
#include
namespace thrust
{
/*! \addtogroup stream_compaction
* \{
*/
/*! For each group of consecutive elements in the range `[first, last)`
* with the same value, \p unique removes all but the first element of
* the group. The return value is an iterator \c new_last such that
* no two consecutive elements in the range `[first, new_last)` are
* equal. The iterators in the range `[new_last, last)` are all still
* dereferenceable, but the elements that they point to are unspecified.
* \p unique is stable, meaning that the relative order of elements that are
* not removed is unchanged.
*
* This version of \p unique uses \c operator== to test for equality.
*
* \param first The beginning of the input range.
* \param last The end of the input range.
* \return The end of the unique range `[first, new_last)`.
*
* \tparam ForwardIterator is a model of Forward Iterator,
* and \p ForwardIterator is mutable,
* and \p ForwardIterator's \c value_type is a model of Equality Comparable.
*
* The following code snippet demonstrates how to use \p unique to
* compact a sequence of numbers to remove consecutive duplicates.
*
* \code
* #include
* ...
* const int N = 7;
* int A[N] = {1, 3, 3, 3, 2, 2, 1};
* int *new_end = thrust::unique(A, A + N);
* // The first four values of A are now {1, 3, 2, 1}
* // Values beyond new_end are unspecified.
* \endcode
*
* \see http://www.sgi.com/tech/stl/unique.html
* \see unique_copy
*/
template
ForwardIterator unique(ForwardIterator first,
ForwardIterator last);
/*! For each group of consecutive elements in the range `[first, last)`
* with the same value, \p unique removes all but the first element of
* the group. The return value is an iterator \c new_last such that
* no two consecutive elements in the range `[first, new_last)` are
* equal. The iterators in the range `[new_last, last)` are all still
* dereferenceable, but the elements that they point to are unspecified.
* \p unique is stable, meaning that the relative order of elements that are
* not removed is unchanged.
*
* This version of \p unique uses the function object \p binary_pred to test
* for equality.
*
* \param first The beginning of the input range.
* \param last The end of the input range.
* \param binary_pred The binary predicate used to determine equality.
* \return The end of the unique range `[first, new_last)`
*
* \tparam ForwardIterator is a model of Forward Iterator,
* and \p ForwardIterator is mutable,
* and \p ForwardIterator's \c value_type is convertible to \p BinaryPredicate's \c first_argument_type and to \p BinaryPredicate's \c second_argument_type.
* \tparam BinaryPredicate is a model of Binary Predicate.
*
* The following code snippet demonstrates how to use \p unique to
* compact a sequence of numbers to remove consecutive duplicates.
*
* \code
* #include
* ...
* const int N = 7;
* int A[N] = {1, 3, 3, 3, 2, 2, 1};
* int *new_end = thrust::unique(A, A + N, thrust::equal_to());
* // The first four values of A are now {1, 3, 2, 1}
* // Values beyond new_end are unspecified.
* \endcode
*
* \see http://www.sgi.com/tech/stl/unique.html
* \see unique_copy
*/
template
ForwardIterator unique(ForwardIterator first,
ForwardIterator last,
BinaryPredicate binary_pred);
/*! \p unique_copy copies elements from the range `[first, last)`
* to a range beginning with \p output, except that in a consecutive group
* of duplicate elements only the first one is copied. The return value
* is the end of the range to which the elements are copied.
*
* The reason there are two different versions of unique_copy is that there
* are two different definitions of what it means for a consecutive group of
* elements to be duplicates. In the first version, the test is simple
* equality: the elements in a range `[f, l)` are duplicates if,
* for every iterator \p i in the range, either `i == f` or else
* `*i == *(i-1)`. In the second, the test is an arbitrary
* \p BinaryPredicate \p binary_pred: the elements in `[f, l)` are
* duplicates if, for every iterator \p i in the range, either `i == f`
* or else `binary_pred(*i, *(i-1))` is \p true.
*
* This version of \p unique_copy uses \c operator== to test for equality.
*
* \param first The beginning of the input range.
* \param last The end of the input range.
* \param output The beginning of the output range.
* \return The end of the unique range `[output, output_end)`.
*
* \tparam InputIterator is a model of Input Iterator,
* and \p InputIterator's \c value_type is a model of Equality Comparable.
* \tparam OutputIterator is a model of Output Iterator and
* and \p InputIterator's \c value_type is convertible to \c OutputIterator's \c value_type.
*
* The following code snippet demonstrates how to use \p unique_copy to
* compact a sequence of numbers to remove consecutive duplicates.
*
* \code
* #include
* ...
* const int N = 7;
* int A[N] = {1, 3, 3, 3, 2, 2, 1};
* int B[N];
* int * output_end = thrust::unique_copy(A, A + N, B);
* // The first four values of B are now {1, 3, 2, 1} and (output_end - B) is 4
* // Values beyond output_end are unspecified
* \endcode
*
* \see unique
* \see http://www.sgi.com/tech/stl/unique_copy.html
*/
template
OutputIterator unique_copy(InputIterator first,
InputIterator last,
OutputIterator output);
/*! \p unique_copy copies elements from the range `[first, last)`
* to a range beginning with \p output, except that in a consecutive group
* of duplicate elements only the first one is copied. The return value
* is the end of the range to which the elements are copied.
*
* This version of \p unique_copy uses the function object \c binary_pred
* to test for equality.
*
* \param first The beginning of the input range.
* \param last The end of the input range.
* \param output The beginning of the output range.
* \param binary_pred The binary predicate used to determine equality.
* \return The end of the unique range `[output, output_end)`.
*
* \tparam InputIterator is a model of Input Iterator,
* and \p InputIterator's \c value_type is a model of Equality Comparable.
* \tparam OutputIterator is a model of Output Iterator and
* and \p InputIterator's \c value_type is convertible to \c OutputIterator's \c value_type.
* \tparam BinaryPredicate is a model of Binary Predicate.
*
* The following code snippet demonstrates how to use \p unique_copy to
* compact a sequence of numbers to remove consecutive duplicates.
*
* \code
* #include
* ...
* const int N = 7;
* int A[N] = {1, 3, 3, 3, 2, 2, 1};
* int B[N];
* int *output_end = thrust::unique_copy(A, A + N, B, thrust::equal_to());
* // The first four values of B are now {1, 3, 2, 1} and (output_end - B) is 4
* // Values beyond output_end are unspecified.
* \endcode
*
* \see unique
* \see http://www.sgi.com/tech/stl/unique_copy.html
*/
template
OutputIterator unique_copy(InputIterator first,
InputIterator last,
OutputIterator output,
BinaryPredicate binary_pred);
/*! \p unique_by_key is a generalization of \p unique to key-value pairs.
* For each group of consecutive keys in the range `[keys_first, keys_last)`
* that are equal, \p unique_by_key removes all but the first element of
* the group. Similarly, the corresponding values in the range
* `[values_first, values_first + (keys_last - keys_first))`
* are also removed.
*
* The return value is a \p pair of iterators `(new_keys_last,new_values_last)`
* such that no two consecutive elements in the range `[keys_first, new_keys_last)`
* are equal.
*
* This version of \p unique_by_key uses \c operator== to test for equality and
* \c project1st to reduce values with equal keys.
*
* \param keys_first The beginning of the key range.
* \param keys_last The end of the key range.
* \param values_first The beginning of the value range.
* \return A pair of iterators at end of the ranges `[key_first, keys_new_last)` and `[values_first, values_new_last)`.
*
* \tparam ForwardIterator1 is a model of Forward Iterator,
* and \p ForwardIterator1 is mutable,
* and \p ForwardIterator's \c value_type is a model of Equality Comparable.
* \tparam ForwardIterator2 is a model of Forward Iterator,
* and \p ForwardIterator2 is mutable.
*
* The following code snippet demonstrates how to use \p unique_by_key to
* compact a sequence of key/value pairs to remove consecutive duplicates.
*
* \code
* #include
* ...
* const int N = 7;
* int A[N] = {1, 3, 3, 3, 2, 2, 1}; // keys
* int B[N] = {9, 8, 7, 6, 5, 4, 3}; // values
*
* thrust::pair new_end;
* new_end = thrust::unique_by_key(A, A + N, B);
*
* // The first four keys in A are now {1, 3, 2, 1} and new_end.first - A is 4.
* // The first four values in B are now {9, 8, 5, 3} and new_end.second - B is 4.
* \endcode
*
* \see unique
* \see unique_copy_by_key
* \see reduce_by_key
*/
template
thrust::pair
unique_by_key(ForwardIterator1 keys_first,
ForwardIterator1 keys_last,
ForwardIterator2 values_first);
/*! \p unique_by_key is a generalization of \p unique to key-value pairs.
* For each group of consecutive keys in the range `[keys_first, keys_last)`
* that are equal, \p unique_by_key removes all but the first element of
* the group. Similarly, the corresponding values in the range
* `[values_first, values_first + (keys_last - keys_first))`
* are also removed.
*
* This version of \p unique_by_key uses the function object \c binary_pred
* to test for equality and \c project1st to reduce values with equal keys.
*
* \param keys_first The beginning of the key range.
* \param keys_last The end of the key range.
* \param values_first The beginning of the value range.
* \param binary_pred The binary predicate used to determine equality.
* \return The end of the unique range `[first, new_last)`.
*
* \tparam ForwardIterator1 is a model of Forward Iterator,
* and \p ForwardIterator1 is mutable,
* and \p ForwardIterator's \c value_type is a model of Equality Comparable.
* \tparam ForwardIterator2 is a model of Forward Iterator,
* and \p ForwardIterator2 is mutable.
* \tparam BinaryPredicate is a model of Binary Predicate.
*
* The following code snippet demonstrates how to use \p unique_by_key to
* compact a sequence of key/value pairs to remove consecutive duplicates.
*
* \code
* #include
* ...
* const int N = 7;
* int A[N] = {1, 3, 3, 3, 2, 2, 1}; // keys
* int B[N] = {9, 8, 7, 6, 5, 4, 3}; // values
*
* thrust::pair new_end;
* thrust::equal_to binary_pred;
* new_end = thrust::unique_by_key(keys, keys + N, values, binary_pred);
*
* // The first four keys in A are now {1, 3, 2, 1} and new_end.first - A is 4.
* // The first four values in B are now {9, 8, 5, 3} and new_end.second - B is 4.
* \endcode
*
* \see unique
* \see unique_copy_by_key
* \see reduce_by_key
*/
template
thrust::pair
unique_by_key(ForwardIterator1 keys_first,
ForwardIterator1 keys_last,
ForwardIterator2 values_first,
BinaryPredicate binary_pred);
/*! \p unique_copy_by_key is a generalization of \p unique_copy to key-value pairs.
* For each group of consecutive keys in the range `[keys_first, keys_last)`
* that are equal, \p unique_copy_by_key copies the first element of the group to
* a range beginning with \c keys_output and the corresponding values from the range
* `[values_first, values_first + (keys_last - keys_first))` are copied to a range
* beginning with \c values_output.
*
* This version of \p unique_copy_by_key uses \c operator== to test for equality and
* \c project1st to reduce values with equal keys.
*
* \param keys_first The beginning of the input key range.
* \param keys_last The end of the input key range.
* \param values_first The beginning of the input value range.
* \param keys_output The beginning of the output key range.
* \param values_output The beginning of the output value range.
* \return A pair of iterators at end of the ranges `[keys_output, keys_output_last)` and `[values_output, values_output_last)`.
*
* \tparam InputIterator1 is a model of Input Iterator,
* \tparam InputIterator2 is a model of Input Iterator,
* \tparam OutputIterator1 is a model of Output Iterator and
* and \p InputIterator1's \c value_type is convertible to \c OutputIterator1's \c value_type.
* \tparam OutputIterator2 is a model of Output Iterator and
* and \p InputIterator2's \c value_type is convertible to \c OutputIterator2's \c value_type.
*
* The following code snippet demonstrates how to use \p unique_copy_by_key to
* compact a sequence of key/value pairs and with equal keys.
*
* \code
* #include
* ...
* const int N = 7;
* int A[N] = {1, 3, 3, 3, 2, 2, 1}; // input keys
* int B[N] = {9, 8, 7, 6, 5, 4, 3}; // input values
* int C[N]; // output keys
* int D[N]; // output values
*
* thrust::pair new_end;
* new_end = thrust::unique_copy_by_key(A, A + N, B, C, D);
*
* // The first four keys in C are now {1, 3, 2, 1} and new_end.first - C is 4.
* // The first four values in D are now {9, 8, 5, 3} and new_end.second - D is 4.
* \endcode
*
* \see unique_copy
* \see unique_by_key
* \see reduce_by_key
*/
template
thrust::pair
unique_copy_by_key(InputIterator1 keys_first,
InputIterator1 keys_last,
InputIterator2 values_first,
OutputIterator1 keys_output,
OutputIterator2 values_output);
/*! \p unique_copy_by_key is a generalization of \p unique_copy to key-value pairs.
* For each group of consecutive keys in the range `[keys_first, keys_last)`
* that are equal, \p unique_copy_by_key copies the first element of the group to
* a range beginning with \c keys_output and the corresponding values from the range
* `[values_first, values_first + (keys_last - keys_first))` are copied to a range
* beginning with \c values_output.
*
* This version of \p unique_copy_by_key uses the function object \c binary_pred
* to test for equality and \c project1st to reduce values with equal keys.
*
* \param keys_first The beginning of the input key range.
* \param keys_last The end of the input key range.
* \param values_first The beginning of the input value range.
* \param keys_output The beginning of the output key range.
* \param values_output The beginning of the output value range.
* \param binary_pred The binary predicate used to determine equality.
* \return A pair of iterators at end of the ranges `[keys_output, keys_output_last)` and `[values_output, values_output_last)`.
*
* \tparam InputIterator1 is a model of Input Iterator,
* \tparam InputIterator2 is a model of Input Iterator,
* \tparam OutputIterator1 is a model of Output Iterator and
* and \p InputIterator1's \c value_type is convertible to \c OutputIterator1's \c value_type.
* \tparam OutputIterator2 is a model of Output Iterator and
* and \p InputIterator2's \c value_type is convertible to \c OutputIterator2's \c value_type.
* \tparam BinaryPredicate is a model of Binary Predicate.
*
* The following code snippet demonstrates how to use \p unique_copy_by_key to
* compact a sequence of key/value pairs and with equal keys.
*
* \code
* #include
* ...
* const int N = 7;
* int A[N] = {1, 3, 3, 3, 2, 2, 1}; // input keys
* int B[N] = {9, 8, 7, 6, 5, 4, 3}; // input values
* int C[N]; // output keys
* int D[N]; // output values
*
* thrust::pair new_end;
* thrust::equal_to binary_pred;
* new_end = thrust::unique_copy_by_key(A, A + N, B, C, D, binary_pred);
*
* // The first four keys in C are now {1, 3, 2, 1} and new_end.first - C is 4.
* // The first four values in D are now {9, 8, 5, 3} and new_end.second - D is 4.
* \endcode
*
* \see unique_copy
* \see unique_by_key
* \see reduce_by_key
*/
template
thrust::pair
unique_copy_by_key(InputIterator1 keys_first,
InputIterator1 keys_last,
InputIterator2 values_first,
OutputIterator1 keys_output,
OutputIterator2 values_output,
BinaryPredicate binary_pred);
/*! \} // end stream_compaction
*/
}; // end namespace thrust
#include