Contains helper functions for the sortedArrayManipulation routines. Much of this was adapted from stl_heap.h and stl_algo.h of the gcc standard library See https://gcc.gnu.org/svn/gcc/trunk/libstdc++-v3/include/bits/. More...
Include dependency graph for sortedArrayManipulationHelpers.hpp:
This graph shows which files directly or indirectly include this file:
Go to the source code of this file.
Classes | |
| class | LvArray::sortedArrayManipulation::internal::DualIteratorAccessor< A, B > |
| This class is the type returned by the DualIterator operator* and holds a reference to a value in both underlying arrays. More... | |
| class | LvArray::sortedArrayManipulation::internal::DualIteratorAccessor< A, B >::Temporary |
| A helper class that holds a copy of the values. More... | |
| class | LvArray::sortedArrayManipulation::internal::DualIteratorComparator< A, B, Compare > |
| This class is used to make a comparison method that takes in DualIteratorAccessor<A, B> from a comparison method that takes in objects of type A. More... | |
| class | LvArray::sortedArrayManipulation::internal::DualIterator< RandomAccessIteratorA, RandomAccessIteratorB > |
| This class acts as a single iterator while wrapping two iterators. More... | |
Namespaces | |
| LvArray | |
| The top level namespace. | |
| LvArray::sortedArrayManipulation | |
| Contains functions for operating on a contiguous sorted unique array of values. | |
Functions | |
| template<class T > | |
| DISABLE_HD_WARNING LVARRAY_HOST_DEVICE T && | LvArray::sortedArrayManipulation::internal::createTemporary (T &a) |
| Return a temporary object holding the value of a. More... | |
| template<class A , class B > | |
| DISABLE_HD_WARNING LVARRAY_HOST_DEVICE DualIteratorAccessor< A, B >::Temporary | LvArray::sortedArrayManipulation::internal::createTemporary (DualIteratorAccessor< A, B > &&it) |
| Return a temporary object holding the values held in the DualIteratorAccessor. More... | |
| template<class Iterator > | |
| DISABLE_HD_WARNING LVARRAY_HOST_DEVICE void | LvArray::sortedArrayManipulation::internal::exchange (Iterator a, Iterator b) |
| Exchange the values pointed at by the two iterators. More... | |
| template<class BidirIt1 , class BidirIt2 > | |
| DISABLE_HD_WARNING LVARRAY_HOST_DEVICE void | LvArray::sortedArrayManipulation::internal::moveBackward (BidirIt1 first, BidirIt1 last, BidirIt2 d_last) |
| Move the elements in [first, last) to another range ending in d_last. The elements are moved in reverse order. More... | |
| template<typename Iterator , typename Compare > | |
| DISABLE_HD_WARNING LVARRAY_HOST_DEVICE void | LvArray::sortedArrayManipulation::internal::computeMedian (Iterator result, Iterator a, Iterator b, Iterator c, Compare &&comp) |
| Compute the median of *a, *b and *c and place it in *result. More... | |
| template<typename RandomAccessIterator , typename Compare > | |
| DISABLE_HD_WARNING LVARRAY_HOST_DEVICE RandomAccessIterator | LvArray::sortedArrayManipulation::internal::unguardedPartition (RandomAccessIterator first, RandomAccessIterator last, RandomAccessIterator pivot, Compare &&comp) |
| Partition the range [first, last) with regards to *pivot. More... | |
| template<typename RandomAccessIterator , typename Compare > | |
| DISABLE_HD_WARNING LVARRAY_HOST_DEVICE RandomAccessIterator | LvArray::sortedArrayManipulation::internal::unguardedPartitionPivot (RandomAccessIterator first, RandomAccessIterator last, Compare &&comp) |
| Partition the range [first, last). More... | |
| template<typename RandomAccessIterator , typename Compare > | |
| DISABLE_HD_WARNING LVARRAY_HOST_DEVICE void | LvArray::sortedArrayManipulation::internal::unguardedLinearInsert (RandomAccessIterator last, Compare comp) |
| template<class RandomAccessIterator , class Compare > | |
| DISABLE_HD_WARNING LVARRAY_HOST_DEVICE void | LvArray::sortedArrayManipulation::internal::insertionSort (RandomAccessIterator first, std::ptrdiff_t const n, Compare comp) |
| sort the range [first, first + n) under comp using insertions sort. More... | |
| template<typename RandomAccessIterator , typename Compare > | |
| DISABLE_HD_WARNING LVARRAY_HOST_DEVICE void | LvArray::sortedArrayManipulation::internal::introsortLoop (RandomAccessIterator first, RandomAccessIterator last, Compare &&comp) |
| Partially sort the range [first, last) under comp. More... | |
Variables | |
| constexpr int | LvArray::sortedArrayManipulation::internal::INTROSORT_THRESHOLD = 64 |
| The size above which we continue with the introsortLoop. | |
Detailed Description
Contains helper functions for the sortedArrayManipulation routines. Much of this was adapted from stl_heap.h and stl_algo.h of the gcc standard library See https://gcc.gnu.org/svn/gcc/trunk/libstdc++-v3/include/bits/.
Function Documentation
◆ computeMedian()
template<typename Iterator , typename Compare >
|
inline |
Compute the median of *a, *b and *c and place it in *result.
- Template Parameters
-
Iterator an iterator type. Compare the type of the comparison method.
- Parameters
-
result iterator to the place to store the result. a iterator to the first value to compare b iterator to the first value to compare. c iterator to the first value to compare. comp the comparison method to use.
- Note
- This method was adapted from the gcc standard libarary header stl_algo.h which can be found at https://gcc.gnu.org/svn/gcc/trunk/libstdc++-v3/include/bits/.
◆ createTemporary() [1/2]
template<class T >
|
inline |
Return a temporary object holding the value of a.
- Template Parameters
-
T the type of the value to create.
- Parameters
-
a the value to move.
- Returns
- Return a temporary object holding the value of a.
◆ createTemporary() [2/2]
template<class A , class B >
|
inline |
Return a temporary object holding the values held in the DualIteratorAccessor.
- Template Parameters
-
A the type of the first value in the DualIteratorAccessor. B the type of the second value in the DualIteratorAccessor.
- Parameters
-
it the DualIteratorAccessor to move from.
- Returns
- Return a temporary object holding the values held in the DualIteratorAccessor.
◆ exchange()
template<class Iterator >
|
inline |
Exchange the values pointed at by the two iterators.
- Template Parameters
-
Iterator an iterator type.
- Parameters
-
a the first iterator. b the second iterator.
◆ insertionSort()
template<class RandomAccessIterator , class Compare >
|
inline |
sort the range [first, first + n) under comp using insertions sort.
- Template Parameters
-
RandomAccessIterator a random access iterator type. Compare the type of the comparison method.
- Parameters
-
first iterator to the beginning of the range. n the size of the range. comp the comparison method to use.
- Note
- This method was adapted from the gcc standard libarary header stl_algo.h which can be found at https://gcc.gnu.org/svn/gcc/trunk/libstdc++-v3/include/bits/.
◆ introsortLoop()
template<typename RandomAccessIterator , typename Compare >
|
inline |
Partially sort the range [first, last) under comp.
- Template Parameters
-
RandomAccessIterator a random access iterator type. Compare the type of the comparison method.
- Parameters
-
first iterator to the beginning of the range. last iterator to the end of the range. comp the comparison method to use.
- Note
- This method was heavily modified to get rid of recursion. As a result it no-longer does a heap-sort when the recursion depth reaches a limit. On randomly generated datasets it performs as well or better than std::sort. However because it no longer does heap-sort there may be certain cases where std::sort performs better. If this becomes an issue try adding heap-sort back in.
- This method was adapted from the gcc standard libarary header stl_algo.h which can be found at https://gcc.gnu.org/svn/gcc/trunk/libstdc++-v3/include/bits/.
◆ moveBackward()
template<class BidirIt1 , class BidirIt2 >
|
inline |
Move the elements in [first, last) to another range ending in d_last. The elements are moved in reverse order.
- Template Parameters
-
BidirIt1 a bidirectional iterator type. BidirIt2 a bidirectional iterator type.
- Parameters
-
first iterator to the beginning of the values to move. last iterator to the end of the values to move. d_last iterator to the end of the values to move to.
- Note
- This should be equivalent to std::move_backward and this implementation was gotten from https://en.cppreference.com/w/cpp/algorithm/move_backward.
◆ unguardedLinearInsert()
template<typename RandomAccessIterator , typename Compare >
|
inline |
- Template Parameters
-
RandomAccessIterator a random access iterator type. Compare the type of the comparison method.
- Parameters
-
last iterator to the end of the range. comp the comparison method to use.
- Note
- This method was adapted from the gcc standard libarary header stl_algo.h which can be found at https://gcc.gnu.org/svn/gcc/trunk/libstdc++-v3/include/bits/.
◆ unguardedPartition()
template<typename RandomAccessIterator , typename Compare >
|
inline |
Partition the range [first, last) with regards to *pivot.
- Template Parameters
-
RandomAccessIterator a random access iterator type. Compare the type of the comparison method.
- Parameters
-
first iterator to the beginning of the range to partition. last iterator to the end of the range to partition. pivot iterator to the value to use as a pivot. comp the comparison method to use.
- Returns
- An iterator to pivot.
- Note
- This method was adapted from the gcc standard libarary header stl_algo.h which can be found at https://gcc.gnu.org/svn/gcc/trunk/libstdc++-v3/include/bits/.
◆ unguardedPartitionPivot()
template<typename RandomAccessIterator , typename Compare >
|
inline |
Partition the range [first, last).
- Template Parameters
-
RandomAccessIterator a random access iterator type. Compare the type of the comparison method.
- Parameters
-
first iterator to the beginning of the range to partition. last iterator to the end of the range to partition. comp the comparison method to use.
- Returns
- An iterator to pivot.
- Note
- This method was adapted from the gcc standard libarary header stl_algo.h which can be found at https://gcc.gnu.org/svn/gcc/trunk/libstdc++-v3/include/bits/.
