Contains functions for operating on a contiguous sorted unique array of values. More...

Classes
class	CallBacks
	This class provides a no-op callbacks interface for the ArrayManipulation sorted routines. More...

class	greater
	This class operates as functor similar to std::greater. More...

class	less
	This class operates as functor similar to std::less. More...

Enumerations
enum	Description { SORTED_UNIQUE, UNSORTED_NO_DUPLICATES, SORTED_WITH_DUPLICATES, UNSORTED_WITH_DUPLICATES }
	Describes an as some combination of sorted/unsorted and unique/with duplicates.

Functions
LVARRAY_HOST_DEVICE constexpr bool	isSorted (Description const desc)

LVARRAY_HOST_DEVICE constexpr bool	isUnique (Description const desc)

template<typename RandomAccessIterator , typename Compare = less< typename std::iterator_traits< RandomAccessIterator >::value_type >>
DISABLE_HD_WARNING LVARRAY_HOST_DEVICE void	makeSorted (RandomAccessIterator const first, RandomAccessIterator const last, Compare &&comp=Compare())
	Sort the given values in place using the given comparator. More...

template<typename RandomAccessIteratorA , typename RandomAccessIteratorB , typename Compare = less< typename std::iterator_traits< RandomAccessIteratorA >::value_type >>
DISABLE_HD_WARNING LVARRAY_HOST_DEVICE void	dualSort (RandomAccessIteratorA valueFirst, RandomAccessIteratorA valueLast, RandomAccessIteratorB dataFirst, Compare &&comp=Compare())
	Sort the given values in place using the given comparator and perform the same operations on the data array thus preserving the mapping between values[i] and data[i]. More...

template<typename ITER , typename Compare = less< typename std::iterator_traits< ITER >::value_type >>
DISABLE_HD_WARNING LVARRAY_HOST_DEVICE bool	isSorted (ITER first, ITER const last, Compare &&comp=Compare())

template<typename ITER , typename Compare = less< typename std::iterator_traits< ITER >::value_type >>
DISABLE_HD_WARNING LVARRAY_HOST_DEVICE std::ptrdiff_t	removeDuplicates (ITER first, ITER const last, Compare &&comp=Compare())
	Remove duplicates from the array, duplicates aren't destroyed but they're moved out of. More...

template<typename ITER , typename Compare = less< typename std::iterator_traits< ITER >::value_type >>
DISABLE_HD_WARNING LVARRAY_HOST_DEVICE std::ptrdiff_t	makeSortedUnique (ITER const first, ITER const last, Compare &&comp=Compare())
	Sort and remove duplicates from the array, duplicates aren't destroyed but they're moved out of. More...

template<typename ITER , typename Compare = less< typename std::iterator_traits< ITER >::value_type >>
DISABLE_HD_WARNING LVARRAY_HOST_DEVICE bool	isSortedUnique (ITER first, ITER const last, Compare &&comp=Compare())

template<typename T , typename Compare = less< T >>
DISABLE_HD_WARNING LVARRAY_HOST_DEVICE std::ptrdiff_t	find (T const *const LVARRAY_RESTRICT ptr, std::ptrdiff_t const size, T const &value, Compare &&comp=Compare())

template<typename T , typename Compare = less< T >>
DISABLE_HD_WARNING LVARRAY_HOST_DEVICE bool	contains (T const *const LVARRAY_RESTRICT ptr, std::ptrdiff_t const size, T const &value, Compare &&comp=Compare())

template<typename T , typename CALLBACKS >
DISABLE_HD_WARNING LVARRAY_HOST_DEVICE bool	remove (T *const LVARRAY_RESTRICT ptr, std::ptrdiff_t const size, T const &value, CALLBACKS &&callBacks)
	Remove the given value from the array if it exists. More...

template<typename T , typename ITER , typename CALLBACKS = CallBacks< T >>
DISABLE_HD_WARNING LVARRAY_HOST_DEVICE std::ptrdiff_t	remove (T *const LVARRAY_RESTRICT ptr, std::ptrdiff_t const size, ITER const first, ITER const last, CALLBACKS &&callBacks=CALLBACKS())
	Remove the given values from the array if they exist. More...

template<typename T , typename CALLBACKS = CallBacks< T >>
DISABLE_HD_WARNING LVARRAY_HOST_DEVICE bool	insert (T *const LVARRAY_RESTRICT ptr, std::ptrdiff_t const size, T const &value, CALLBACKS &&callBacks=CALLBACKS())
	Insert the given value into the array if it doesn't already exist. More...

template<typename T , typename ITER , typename CALLBACKS = CallBacks< T >>
DISABLE_HD_WARNING LVARRAY_HOST_DEVICE std::ptrdiff_t	insert (T *const LVARRAY_RESTRICT ptr, std::ptrdiff_t const size, ITER const first, ITER const last, CALLBACKS &&callBacks=CALLBACKS())
	Insert the given values into the array if they don't already exist. More...

Detailed Description

Contains functions for operating on a contiguous sorted unique array of values.

Most functions accept a pointer and a size as the first two arguments. Values in this range are expected to be in a valid state and sorted unique. Values past the end of the array are expected to be uninitialized.

Function Documentation

◆ contains()

template<typename T , typename Compare = less< T >>

DISABLE_HD_WARNING LVARRAY_HOST_DEVICE bool LvArray::sortedArrayManipulation::contains	(	T const *const LVARRAY_RESTRICT	ptr,
		std::ptrdiff_t const	size,
		T const &	value,
		Compare &&	comp = `Compare()`
	)

inline

Template Parameters

T	the type of values in the array.
Compare	the type of the comparison function, defaults to less<T>.

Returns: Return true if value is contained in the array.

Parameters

ptr	Pointer to the array, must be sorted under comp.
size	The size of the array.
value	The value to find.
comp	The comparison method to use.

Note: Should be equivalent to std::lower_bound(ptr, ptr + size, value, comp).

◆ dualSort()

template<typename RandomAccessIteratorA , typename RandomAccessIteratorB , typename Compare = less< typename std::iterator_traits< RandomAccessIteratorA >::value_type >>

DISABLE_HD_WARNING LVARRAY_HOST_DEVICE void LvArray::sortedArrayManipulation::dualSort	(	RandomAccessIteratorA	valueFirst,
		RandomAccessIteratorA	valueLast,
		RandomAccessIteratorB	dataFirst,
		Compare &&	comp = `Compare()`
	)

inline

Sort the given values in place using the given comparator and perform the same operations on the data array thus preserving the mapping between values[i] and data[i].

Template Parameters

RandomAccessIteratorA	an iterator type that provides random access.
RandomAccessIteratorB	an iterator type that provides random access.
Compare	the type of the comparison function.

Parameters

valueFirst	An iterator to the beginning of the values to sort.
valueLast	An iterator to the end of the values to sort.
dataFirst	An iterator to the beginning of the data.
comp	a function that does the comparison between two objects.

◆ find()

template<typename T , typename Compare = less< T >>

DISABLE_HD_WARNING LVARRAY_HOST_DEVICE std::ptrdiff_t LvArray::sortedArrayManipulation::find	(	T const *const LVARRAY_RESTRICT	ptr,
		std::ptrdiff_t const	size,
		T const &	value,
		Compare &&	comp = `Compare()`
	)

inline

Template Parameters

T	the type of values in the array.
Compare	the type of the comparison function, defaults to less<T>.

Returns: Return the index of the first value in the array that compares not less than value or size if no such element can be found.

Parameters

ptr	Pointer to the array, must be sorted under comp.
size	The size of the array.
value	The value to find.
comp	The comparison method to use.

Note: Should be equivalent to std::lower_bound(ptr, ptr + size, value, comp).

◆ insert() [1/2]

template<typename T , typename CALLBACKS = CallBacks< T >>

DISABLE_HD_WARNING LVARRAY_HOST_DEVICE bool LvArray::sortedArrayManipulation::insert	(	T *const LVARRAY_RESTRICT	ptr,
		std::ptrdiff_t const	size,
		T const &	value,
		CALLBACKS &&	callBacks = `CALLBACKS()`
	)

inline

Insert the given value into the array if it doesn't already exist.

Template Parameters

T	the type of values in the array.
CALLBACKS	the type of the callBacks class.

Parameters

ptr	pointer to the array, must be sorted under less<T>.
size	the size of the array.
value	the value to insert.
callBacks	class which must define methods similar to CallBacks::incrementSize(std::ptrdiff_t) and CallBacks::insert(std::ptrdiff_t).

Returns: True iff the value was inserted.

◆ insert() [2/2]

template<typename T , typename ITER , typename CALLBACKS = CallBacks< T >>

DISABLE_HD_WARNING LVARRAY_HOST_DEVICE std::ptrdiff_t LvArray::sortedArrayManipulation::insert	(	T *const LVARRAY_RESTRICT	ptr,
		std::ptrdiff_t const	size,
		ITER const	first,
		ITER const	last,
		CALLBACKS &&	callBacks = `CALLBACKS()`
	)

inline

Insert the given values into the array if they don't already exist.

Template Parameters

T	the type of values in the array.
ITER	An iterator class.
CALLBACKS	the type of the callBacks class.

Parameters

ptr	pointer to the array, must be sorted under less<T>.
size	the size of the array.
first	An iterator to the first value to insert.
last	An iterator to the end of the values to insert.
callBacks	class which must define methods similar to CallBacks::incrementSize(std::ptrdiff_t), CallBacks::set(std::ptrdiff_t, std::ptrdiff_t) and CallBacks::insert(std::ptrdiff_t, std::ptrdiff_t, std::ptrdiff_t, * std::ptrdiff_t).

Note: The values to insert [ first, last ) must be sorted and contain no duplicates.

Returns: The number of values inserted.

◆ isSorted() [1/2]

LVARRAY_HOST_DEVICE constexpr bool LvArray::sortedArrayManipulation::isSorted ( Description const desc )

inline

Returns: True if desc describes an array that is sorted.

Parameters

desc	The Description to query.

◆ isSorted() [2/2]

template<typename ITER , typename Compare = less< typename std::iterator_traits< ITER >::value_type >>

DISABLE_HD_WARNING LVARRAY_HOST_DEVICE bool LvArray::sortedArrayManipulation::isSorted	(	ITER	first,
		ITER const	last,
		Compare &&	comp = `Compare()`
	)

inline

Template Parameters

ITER	The type of the iterator to the values to check.
Compare	The type of the comparison function, defaults to less.

Returns: Return true if the given array is sorted using comp.

Parameters

first	Iterator to the beginning of the values to check.
last	Iterator to the end of the values to check.
comp	The comparison method to use.

Note: Should be equivalent to std::is_sorted(first, last, comp).

◆ isSortedUnique()

template<typename ITER , typename Compare = less< typename std::iterator_traits< ITER >::value_type >>

DISABLE_HD_WARNING LVARRAY_HOST_DEVICE bool LvArray::sortedArrayManipulation::isSortedUnique	(	ITER	first,
		ITER const	last,
		Compare &&	comp = `Compare()`
	)

inline

Template Parameters

ITER	An iterator type.
Compare	The type of the comparison function, defaults to less.

Returns: Return true iff [ first, last ) is sorted under comp and contains no values which compare equal.

Parameters

first	Iterator to the beginning of the values.
last	Iterator to the end of the values.
comp	The comparison method to use.

◆ isUnique()

LVARRAY_HOST_DEVICE constexpr bool LvArray::sortedArrayManipulation::isUnique ( Description const desc )

inline

Returns: True if desc describes an array that contains no duplicates.

Parameters

desc	the Description to query.

◆ makeSorted()

template<typename RandomAccessIterator , typename Compare = less< typename std::iterator_traits< RandomAccessIterator >::value_type >>

DISABLE_HD_WARNING LVARRAY_HOST_DEVICE void LvArray::sortedArrayManipulation::makeSorted	(	RandomAccessIterator const	first,
		RandomAccessIterator const	last,
		Compare &&	comp = `Compare()`
	)

inline

Sort the given values in place using the given comparator.

Template Parameters

RandomAccessIterator	an iterator type that provides random access.
Compare	the type of the comparison function.

Parameters

first	An iterator to the beginning of the values to sort.
last	An iterator to the end of the values to sort.
comp	A function that does the comparison between two objects.

Note: should be equivalent to std::sort(first, last, comp).

◆ makeSortedUnique()

template<typename ITER , typename Compare = less< typename std::iterator_traits< ITER >::value_type >>

DISABLE_HD_WARNING LVARRAY_HOST_DEVICE std::ptrdiff_t LvArray::sortedArrayManipulation::makeSortedUnique	(	ITER const	first,
		ITER const	last,
		Compare &&	comp = `Compare()`
	)

inline

Sort and remove duplicates from the array, duplicates aren't destroyed but they're moved out of.

Template Parameters

ITER	An iterator type.
Compare	The type of the comparison function, defaults to less.

Parameters

first	Iterator to the beginning of the values.
last	Iterator to the end of the values.
comp	The comparison method to use.

Returns: The number of unique elements, such that [first, first + returnValue) contains the unique elements.

◆ remove() [1/2]

template<typename T , typename CALLBACKS >

DISABLE_HD_WARNING LVARRAY_HOST_DEVICE bool LvArray::sortedArrayManipulation::remove	(	T *const LVARRAY_RESTRICT	ptr,
		std::ptrdiff_t const	size,
		T const &	value,
		CALLBACKS &&	callBacks
	)

inline

Remove the given value from the array if it exists.

Template Parameters

T	the type of values in the array.
CALLBACKS	the type of the callBacks class.

Parameters

ptr	pointer to the array, must be sorted under less<T>.
size	the size of the array.
value	the value to remove.
callBacks	class which must define a method equivalent to CallBacks::remove(std::ptrdiff_t).

Returns: True iff the value was removed.

◆ remove() [2/2]

template<typename T , typename ITER , typename CALLBACKS = CallBacks< T >>

DISABLE_HD_WARNING LVARRAY_HOST_DEVICE std::ptrdiff_t LvArray::sortedArrayManipulation::remove	(	T *const LVARRAY_RESTRICT	ptr,
		std::ptrdiff_t const	size,
		ITER const	first,
		ITER const	last,
		CALLBACKS &&	callBacks = `CALLBACKS()`
	)

inline

Remove the given values from the array if they exist.

Template Parameters

T	the type of values in the array.
ITER	An iterator type.
CALLBACKS	the type of the callBacks class.

Parameters

ptr	pointer to the array, must be sorted under less<T>.
size	the size of the array.
first	An iterator to the first value to insert.
last	An iterator to the end of the values to insert.
callBacks	class which must define methods equivalent to CallBacks::remove(std::ptrdiff_t, std::ptrdiff_t, std::ptrdiff_t).

Note: The values to insert [ first, last ) must be sorted and contain no duplicates.

Returns: The number of values removed.

◆ removeDuplicates()

template<typename ITER , typename Compare = less< typename std::iterator_traits< ITER >::value_type >>

DISABLE_HD_WARNING LVARRAY_HOST_DEVICE std::ptrdiff_t LvArray::sortedArrayManipulation::removeDuplicates	(	ITER	first,
		ITER const	last,
		Compare &&	comp = `Compare()`
	)

inline

Remove duplicates from the array, duplicates aren't destroyed but they're moved out of.

Template Parameters

ITER	An iterator type.
Compare	The type of the comparison function, defaults to less.

Parameters

first	Iterator to the beginning of the values.
last	Iterator to the end of the values.
comp	The comparison method to use.

Returns: The number of unique elements, such that [first, first + returnValue) contains the unique elements.

Note: The range [ first, last ) must be sorted under comp.; If you are using this and would like the duplicates to remain intact at the end of the array change the std::move to a portable implementation of std::swap.

The following statement should be ITER next = first; ++next; This works host only however with some host compilers (clang 10.0.1 and XL) it breaks on device in release. It does some really strange things, for example last - next == 0 and they can have identical values but next != last. If you print out the array each iteration it works as expected. It's not a big deal since it amounts to just a single extra iteration, but very strange.

Classes

Enumerations

Functions

Detailed Description

Function Documentation

◆ contains()

◆ dualSort()

◆ find()

◆ insert() [1/2]

◆ insert() [2/2]

◆ isSorted() [1/2]

◆ isSorted() [2/2]

◆ isSortedUnique()

◆ isUnique()

◆ makeSorted()

◆ makeSortedUnique()

◆ remove() [1/2]

◆ remove() [2/2]

◆ removeDuplicates()