blender::unique_sorted_indices Namespace Reference

Namespaces
namespace	tests

Functions
template<typename T >
bool	non_empty_is_range (const Span< T > indices)
template<typename T >
IndexRange	non_empty_as_range (const Span< T > indices)
template<typename T >
std::optional< IndexRange >	non_empty_as_range_try (const Span< T > indices)
template<typename T >
int64_t	find_size_of_next_range (const Span< T > indices)
template<typename T >
int64_t	find_size_until_next_range (const Span< T > indices, const int64_t min_range_size)
template<typename T , int64_t InlineBufferSize>
int64_t	split_to_ranges_and_spans (const Span< T > indices, const int64_t range_threshold, Vector< std::variant< IndexRange, Span< T > >, InlineBufferSize > &r_segments)

Function Documentation

find_size_of_next_range()

template<typename T >

int64_t blender::unique_sorted_indices::find_size_of_next_range ( const Span< T > indices )

inline

Returns

Amount of consecutive indices at the start of the span. This takes O(log #indices) time.

Example: [3, 4, 5, 6, 8, 9, 10] ^ Range ends here because 6 and 8 are not consecutive.

Definition at line 71 of file BLI_unique_sorted_indices.hh.

References BLI_assert, and blender::binary_search::find_predicate_begin().

Referenced by split_to_ranges_and_spans(), blender::unique_sorted_indices::tests::TEST(), and blender::unique_sorted_indices::tests::TEST().

find_size_until_next_range()

template<typename T >

int64_t blender::unique_sorted_indices::find_size_until_next_range ( const Span< T > indices, const int64_t min_range_size )

inline

Returns

Amount of non-consecutive indices until the next encoded range of at least #min_range_size elements starts. This takes O(size_until_next_range) time.

Example: [1, 2, 4, 6, 7, 8, 9, 10, 13]; ^ Range of at least size 4 starts here.

Definition at line 90 of file BLI_unique_sorted_indices.hh.

References BLI_assert.

Referenced by split_to_ranges_and_spans(), and blender::unique_sorted_indices::tests::TEST().

non_empty_as_range()

template<typename T >

IndexRange blender::unique_sorted_indices::non_empty_as_range ( const Span< T > indices )

inline

Returns

The range encoded by the indices. It is assumed that all indices are consecutive.

Definition at line 46 of file BLI_unique_sorted_indices.hh.

References BLI_assert, and non_empty_is_range().

Referenced by non_empty_as_range_try(), and blender::unique_sorted_indices::tests::TEST().

non_empty_as_range_try()

template<typename T >

std::optional< IndexRange > blender::unique_sorted_indices::non_empty_as_range_try ( const Span< T > indices )

inline

Returns

The range encoded by the indices if all indices are consecutive. Otherwise none.

Definition at line 56 of file BLI_unique_sorted_indices.hh.

References non_empty_as_range(), and non_empty_is_range().

Referenced by blender::index_mask::consolidate_index_mask_segments(), blender::index_mask::IndexMask::from_indices(), and split_to_ranges_and_spans().

non_empty_is_range()

template<typename T >

bool blender::unique_sorted_indices::non_empty_is_range ( const Span< T > indices )

inline

Returns

True when the indices are consecutive and can be encoded as #IndexRange.

Definition at line 37 of file BLI_unique_sorted_indices.hh.

References BLI_assert.

Referenced by blender::index_mask::consolidate_index_mask_segments(), blender::fn::multi_function::build::detail::execute_materialized(), blender::index_mask::IndexMask::foreach_segment_optimized(), blender::index_mask::from_bits_batch_predicate(), non_empty_as_range(), non_empty_as_range_try(), blender::index_mask::optimized_foreach_index(), blender::index_mask::optimized_foreach_index_with_pos(), blender::index_mask::segments_is_equal(), split_to_ranges_and_spans(), and blender::unique_sorted_indices::tests::TEST().

split_to_ranges_and_spans()

template<typename T , int64_t InlineBufferSize>

int64_t blender::unique_sorted_indices::split_to_ranges_and_spans ( const Span< T > indices, const int64_t range_threshold, Vector< std::variant< IndexRange, Span< T > >, InlineBufferSize > & r_segments )

inline

Split the indices up into segments, where each segment is either a range (because the indices are consecutive) or not. There are two opposing goals: The number of segments should be minimized while the amount of indices in a range should be maximized. The #range_threshold allows the caller to balance these goals.

Definition at line 118 of file BLI_unique_sorted_indices.hh.

References BLI_assert, blender::Span< T >::drop_front(), find_size_of_next_range(), find_size_until_next_range(), indices, blender::Span< T >::is_empty(), non_empty_as_range_try(), non_empty_is_range(), blender::Span< T >::size(), and blender::Span< T >::take_front().

Referenced by blender::index_mask::operator<<(), blender::index_mask::segments_from_indices(), blender::index_mask::detail::segments_from_predicate_filter(), and blender::unique_sorted_indices::tests::TEST().