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
constexpr bool	isSorted (Description const desc)

constexpr bool	isUnique (Description const desc)

template<typename RandomAccessIterator , typename Compare = less< typename std::iterator_traits< RandomAccessIterator >::value_type >>
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 >>
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 >>
bool	isSorted (ITER first, ITER const last, Compare &&comp=Compare())

template<typename ITER , typename Compare = less< typename std::iterator_traits< ITER >::value_type >>
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 >>
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 >>
bool	isSortedUnique (ITER first, ITER const last, Compare &&comp=Compare())

template<typename T , typename Compare = less< T >>
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 >>
bool	contains (T const *const LVARRAY_RESTRICT ptr, std::ptrdiff_t const size, T const &value, Compare &&comp=Compare())

template<typename T , typename CALLBACKS >
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 >>
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 >>
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 >>
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 >>

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).

Definition at line 451 of file sortedArrayManipulation.hpp.

◆ dualSort()

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

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.

Definition at line 241 of file sortedArrayManipulation.hpp.

◆ find()

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

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).

Definition at line 411 of file sortedArrayManipulation.hpp.

◆ insert() [1/2]

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

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.

Definition at line 620 of file sortedArrayManipulation.hpp.

◆ insert() [2/2]

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

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.

Definition at line 676 of file sortedArrayManipulation.hpp.

◆ isSorted() [1/2]

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.

Definition at line 55 of file sortedArrayManipulation.hpp.

◆ isSorted() [2/2]

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

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).

Definition at line 269 of file sortedArrayManipulation.hpp.

◆ isSortedUnique()

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

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.

Definition at line 374 of file sortedArrayManipulation.hpp.

◆ isUnique()

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.

Definition at line 63 of file sortedArrayManipulation.hpp.

◆ makeSorted()

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

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).

Definition at line 210 of file sortedArrayManipulation.hpp.

◆ makeSortedUnique()

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

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.

Definition at line 356 of file sortedArrayManipulation.hpp.

◆ remove() [1/2]

template<typename T , typename CALLBACKS >

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.

Definition at line 473 of file sortedArrayManipulation.hpp.

◆ remove() [2/2]

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

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.

Definition at line 513 of file sortedArrayManipulation.hpp.

◆ removeDuplicates()

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

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.

Definition at line 307 of file sortedArrayManipulation.hpp.

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()