/*
* 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 remove.h
* \brief Defines the interface to functions for removing elements
* from a sequence.
*/
#pragma once
#include
namespace thrust
{
/*! \addtogroup stream_compaction Stream Compaction
* \ingroup reordering
* \{
*
*/
/*! \p remove removes from the range `[first, last)` all elements that are
* equal to \p value. That is, \p remove returns an iterator \p new_last such
* that the range `[first, new_last)` contains no elements equal to
* \p value. The iterators in the range `[new_first,last)` are all still
* dereferenceable, but the elements that they point to are unspecified. \p remove
* is stable, meaning that the relative order of elements that are not equal to
* \p value is unchanged.
*
* \param first The beginning of the range of interest.
* \param last The end of the range of interest.
* \param value The value to remove from the range `[first, last)`.
* Elements which are equal to value are removed from the sequence.
* \return A \p ForwardIterator pointing to the end of the resulting range of
* elements which are not equal to \p value.
*
* \tparam ForwardIterator is a model of Forward Iterator,
* and \p ForwardIterator is mutable.
* \tparam T is a model of Equality Comparable,
* and objects of type \p T can be compared for equality with objects of \p ForwardIterator's \c value_type.
*
* The following code snippet demonstrates how to use \p remove to remove a number
* of interest from a range.
*
* \code
* #include
* ...
* const int N = 6;
* int A[N] = {3, 1, 4, 1, 5, 9};
* int *new_end = thrust::remove(A, A + N, 1);
* // The first four values of A are now {3, 4, 5, 9}
* // Values beyond new_end are unspecified
* \endcode
*
* \note The meaning of "removal" is somewhat subtle. \p remove does not destroy any
* iterators, and does not change the distance between \p first and \p last.
* (There's no way that it could do anything of the sort.) So, for example, if
* \c V is a device_vector, `remove(V.begin(), V.end(), 0)` does not
* change `V.size()`: \c V will contain just as many elements as it did
* before. \p remove returns an iterator that points to the end of the resulting
* range after elements have been removed from it; it follows that the elements
* after that iterator are of no interest, and may be discarded. If you are
* removing elements from a
* Sequence, you may
* simply erase them. That is, a reasonable way of removing elements from a
* Sequence is
* `S.erase(remove(S.begin(), S.end(), x), S.end())`.
*
* \see http://www.sgi.com/tech/stl/remove.html
* \see remove_if
* \see remove_copy
* \see remove_copy_if
*/
template
ForwardIterator remove(ForwardIterator first,
ForwardIterator last,
const T &value);
/*! \p remove_copy copies elements that are not equal to \p value from the range
* `[first, last)` to a range beginning at \p result. The return value is
* the end of the resulting range. This operation is stable, meaning that the
* relative order of the elements that are copied is the same as in
* the range `[first, last)`.
*
* \param first The beginning of the range of interest.
* \param last The end of the range of interest.
* \param result The resulting range is copied to the sequence beginning at this
* location.
* \param value The value to omit from the copied range.
* \return An OutputIterator pointing to the end of the resulting range of elements
* which are not equal to \p value.
*
* \tparam InputIterator is a model of Input Iterator,
* and \p InputIterator's \c value_type is convertible to a type in \p OutputIterator's set of \c value_types.
* \tparam OutputIterator is a model of Output Iterator.
* \tparam T is a model of Equality Comparable,
* and objects of type \p T can be compared for equality with objects of \p InputIterator's \c value_type.
*
* The following code snippet demonstrates how to use \p remove_copy to copy
* a sequence of numbers to an output range while omitting a value of interest.
*
* \code
* #include
* ...
* const int N = 6;
* int V[N] = {-2, 0, -1, 0, 1, 2};
* int result[N-2];
* thrust::remove_copy(V, V + N, result, 0);
* // V remains {-2, 0, -1, 0, 1, 2}
* // result is now {-2, -1, 1, 2}
* \endcode
*
* \see http://www.sgi.com/tech/stl/remove_copy.html
* \see remove
* \see remove_if
* \see remove_copy_if
*/
template
OutputIterator remove_copy(InputIterator first,
InputIterator last,
OutputIterator result,
const T &value);
/*! \p remove_if removes from the range `[first, last)` every element \p x
* such that `pred(x)` is \c true. That is, \p remove_if returns an
* iterator \c new_last such that the range `[first,new_last)` contains
* no elements for which \p pred is \c true. The iterators in the range
* `[new_last,last)` are all still dereferenceable, but the elements that
* they point to are unspecified. \p remove_if is stable, meaning that the
* relative order of elements that are not removed is unchanged.
*
* \param first The beginning of the range of interest.
* \param last The end of the range of interest.
* \param pred A predicate to evaluate for each element of the range
* `[first,last)`. Elements for which \p pred evaluates to
* \c false are removed from the sequence.
* \return A ForwardIterator pointing to the end of the resulting range of
* elements for which \p pred evaluated to \c true.
*
* \tparam ForwardIterator is a model of Forward Iterator,
* \p ForwardIterator is mutable,
* and \p ForwardIterator's \c value_type is convertible to \p Predicate's \c argument_type.
* \tparam Predicate is a model of Predicate.
*
* The following code snippet demonstrates how to use \p remove_if to remove
* all even numbers from an array of integers.
*
* \code
* #include
* ...
* struct is_even
* {
* __host__ __device__
* bool operator()(const int x)
* {
* return (x % 2) == 0;
* }
* };
* ...
* const int N = 6;
* int A[N] = {1, 4, 2, 8, 5, 7};
* int *new_end = thrust::remove(A, A + N, is_even());
* // The first three values of A are now {1, 5, 7}
* // Values beyond new_end are unspecified
* \endcode
*
* \note The meaning of "removal" is somewhat subtle. \p remove_if does not
* destroy any iterators, and does not change the distance between \p first and
* \p last. (There's no way that it could do anything of the sort.) So, for
* example, if \c V is a device_vector,
* `remove_if(V.begin(), V.end(), pred)` does not change
* `V.size()`: \c V will contain just as many elements as it did before.
* \p remove_if returns an iterator that points to the end of the resulting
* range after elements have been removed from it; it follows that the elements
* after that iterator are of no interest, and may be discarded. If you are
* removing elements from a
* Sequence, you may
* simply erase them. That is, a reasonable way of removing elements from a
* Sequence is
* `S.erase(remove_if(S.begin(), S.end(), pred), S.end())`.
*
* \see http://www.sgi.com/tech/stl/remove_if.html
* \see remove
* \see remove_copy
* \see remove_copy_if
*/
template
ForwardIterator remove_if(ForwardIterator first,
ForwardIterator last,
Predicate pred);
/*! \p remove_copy_if copies elements from the range `[first,last)` to a
* range beginning at \p result, except that elements for which \p pred is
* \c true are not copied. The return value is the end of the resulting range.
* This operation is stable, meaning that the relative order of the elements that
* are copied is the same as the range `[first,last)`.
*
* \param first The beginning of the range of interest.
* \param last The end of the range of interest.
* \param result The resulting range is copied to the sequence beginning at this
* location.
* \param pred A predicate to evaluate for each element of the range `[first,last)`.
* Elements for which \p pred evaluates to \c false are not copied
* to the resulting sequence.
* \return An OutputIterator pointing to the end of the resulting range.
*
* \tparam InputIterator is a model of Input Iterator,
* \p InputIterator's \c value_type is convertible to a type in \p OutputIterator's set of \c value_types,
* and \p InputIterator's \c value_type is convertible to \p Predicate's \c argument_type.
* \tparam OutputIterator is a model of Output Iterator.
* \tparam Predicate is a model of Predicate.
*
* The following code snippet demonstrates how to use \p remove_copy_if to copy
* a sequence of numbers to an output range while omitting even numbers.
*
* \code
* #include
* ...
* struct is_even
* {
* __host__ __device__
* bool operator()(const int x)
* {
* return (x % 2) == 0;
* }
* };
* ...
* const int N = 6;
* int V[N] = {-2, 0, -1, 0, 1, 2};
* int result[2];
* thrust::remove_copy_if(V, V + N, result, is_even());
* // V remains {-2, 0, -1, 0, 1, 2}
* // result is now {-1, 1}
* \endcode
*
* \see http://www.sgi.com/tech/stl/remove_copy_if.html
* \see remove
* \see remove_copy
* \see remove_if
*/
template
OutputIterator remove_copy_if(InputIterator first,
InputIterator last,
OutputIterator result,
Predicate pred);
/*! \p remove_if removes from the range `[first, last)` every element \p x
* such that `pred(x)` is \c true. That is, \p remove_if returns an
* iterator \c new_last such that the range `[first, new_last)` contains
* no elements for which \p pred of the corresponding stencil value is \c true.
* The iterators in the range `[new_last,last)` are all still dereferenceable,
* but the elements that they point to are unspecified. \p remove_if is stable,
* meaning that the relative order of elements that are not removed is unchanged.
*
* \param first The beginning of the range of interest.
* \param last The end of the range of interest.
* \param stencil The beginning of the stencil sequence.
* \param pred A predicate to evaluate for each element of the range
* `[stencil, stencil + (last - first))`. Elements for which \p pred evaluates to
* \c false are removed from the sequence `[first, last)`
* \return A ForwardIterator pointing to the end of the resulting range of
* elements for which \p pred evaluated to \c true.
*
* \tparam ForwardIterator is a model of Forward Iterator
* and \p ForwardIterator is mutable.
* \tparam InputIterator is a model of Input Iterator,
* and \p InputIterator's \c value_type is convertible to \p Predicate's \c argument_type.
* \tparam Predicate is a model of Predicate.
*
* The following code snippet demonstrates how to use \p remove_if to remove
* specific elements from an array of integers.
*
* \code
* #include
* ...
* const int N = 6;
* int A[N] = {1, 4, 2, 8, 5, 7};
* int S[N] = {0, 1, 1, 1, 0, 0};
*
* int *new_end = thrust::remove(A, A + N, S, thrust::identity());
* // The first three values of A are now {1, 5, 7}
* // Values beyond new_end are unspecified
* \endcode
*
* \see http://www.sgi.com/tech/stl/remove_if.html
* \see remove
* \see remove_copy
* \see remove_copy_if
*/
template
ForwardIterator remove_if(ForwardIterator first,
ForwardIterator last,
InputIterator stencil,
Predicate pred);
/*! \p remove_copy_if copies elements from the range `[first,last)` to a
* range beginning at \p result, except that elements for which \p pred of the
* corresponding stencil value is \c true are not copied. The return value is
* the end of the resulting range. This operation is stable, meaning that the
* relative order of the elements that are copied is the same as the
* range `[first,last)`.
*
* \param first The beginning of the range of interest.
* \param last The end of the range of interest.
* \param stencil The beginning of the stencil sequence.
* \param result The resulting range is copied to the sequence beginning at this
* location.
* \param pred A predicate to evaluate for each element of the range `[first,last)`.
* Elements for which \p pred evaluates to \c false are not copied
* to the resulting sequence.
* \return An OutputIterator pointing to the end of the resulting range.
*
* \tparam InputIterator1 is a model of Input Iterator,
* \p InputIterator1's \c value_type is convertible to a type in \p OutputIterator's set of \c value_types.
* \tparam InputIterator2 is a model of Input Iterator,
* and \p InputIterator2's \c value_type is convertible to \p Predicate's \c argument_type.
* \tparam OutputIterator is a model of Output Iterator.
* \tparam Predicate is a model of Predicate.
*
* The following code snippet demonstrates how to use \p remove_copy_if to copy
* a sequence of numbers to an output range while omitting specific elements.
*
* \code
* #include
* ...
* const int N = 6;
* int V[N] = {-2, 0, -1, 0, 1, 2};
* int S[N] = { 1, 1, 0, 1, 0, 1};
* int result[2];
* thrust::remove_copy_if(V, V + N, result, thrust::identity());
* // V remains {-2, 0, -1, 0, 1, 2}
* // result is now {-1, 1}
* \endcode
*
* \see http://www.sgi.com/tech/stl/remove_copy_if.html
* \see remove
* \see remove_copy
* \see remove_if
* \see copy_if
*/
template
OutputIterator remove_copy_if(InputIterator1 first,
InputIterator1 last,
InputIterator2 stencil,
OutputIterator result,
Predicate pred);
/*! \} // end stream_compaction
*/
} // end thrust
#include