Header-only library for nested containment lists. More...

Classes
struct	Nclist
	Pre-built nested containment list. More...

struct	OverlapsAnyParameters
	Parameters for `overlaps_any()`. More...

struct	OverlapsAnyWorkspace
	Workspace for `overlaps_any()`. More...

struct	OverlapsEndParameters
	Parameters for `overlaps_end()`. More...

struct	OverlapsEndWorkspace
	Workspace for `overlaps_end()`. More...

struct	OverlapsEqualParameters
	Parameters for `overlaps_equal()`. More...

struct	OverlapsEqualWorkspace
	Workspace for `overlaps_equal()`. More...

struct	OverlapsExtendParameters
	Parameters for `overlaps_extend()`. More...

struct	OverlapsExtendWorkspace
	Workspace for `overlaps_extend()`. More...

struct	OverlapsStartParameters
	Parameters for `overlaps_start()`. More...

struct	OverlapsStartWorkspace
	Workspace for `overlaps_start()`. More...

struct	OverlapsWithinParameters
	Parameters for `overlaps_within()`. More...

struct	OverlapsWithinWorkspace
	Workspace for `overlaps_within()`. More...

Typedefs
template<class Array_ >
using	ArrayElement = typename std::remove_const<typename std::remove_reference<decltype(std::declval<Array_>()[0])>::type>::type

Functions
template<typename Index_ , class StartArray_ , class EndArray_ >
Nclist< Index_, ArrayElement< StartArray_ > >	build_custom (Index_ num_subset, const Index_ *subset, const StartArray_ &starts, const EndArray_ &ends)

template<typename Index_ , class StartArray_ , class EndArray_ >
Nclist< Index_, ArrayElement< StartArray_ > >	build_custom (Index_ num_intervals, const StartArray_ &starts, const EndArray_ &ends)

template<typename Index_ , typename Position_ >
Nclist< Index_, Position_ >	build (Index_ num_subset, const Index_ subset, const Position_ starts, const Position_ *ends)

template<typename Index_ , typename Position_ >
Nclist< Index_, Position_ >	build (Index_ num_intervals, const Position_ starts, const Position_ ends)

template<typename Index_ , typename Position_ >
void	overlaps_any (const Nclist< Index_, Position_ > &subject, Position_ query_start, Position_ query_end, const OverlapsAnyParameters< Position_ > &params, OverlapsAnyWorkspace< Index_ > &workspace, std::vector< Index_ > &matches)

template<typename Index_ , typename Position_ >
void	overlaps_end (const Nclist< Index_, Position_ > &subject, Position_ query_start, Position_ query_end, const OverlapsEndParameters< Position_ > &params, OverlapsEndWorkspace< Index_ > &workspace, std::vector< Index_ > &matches)

template<typename Index_ , typename Position_ >
void	overlaps_equal (const Nclist< Index_, Position_ > &subject, Position_ query_start, Position_ query_end, const OverlapsEqualParameters< Position_ > &params, OverlapsEqualWorkspace< Index_ > &workspace, std::vector< Index_ > &matches)

template<typename Index_ , typename Position_ >
void	overlaps_extend (const Nclist< Index_, Position_ > &subject, Position_ query_start, Position_ query_end, const OverlapsExtendParameters< Position_ > &params, OverlapsExtendWorkspace< Index_ > &workspace, std::vector< Index_ > &matches)

template<typename Index_ , typename Position_ >
void	overlaps_start (const Nclist< Index_, Position_ > &subject, Position_ query_start, Position_ query_end, const OverlapsStartParameters< Position_ > &params, OverlapsStartWorkspace< Index_ > &workspace, std::vector< Index_ > &matches)

template<typename Index_ , typename Position_ >
void	overlaps_within (const Nclist< Index_, Position_ > &subject, Position_ query_start, Position_ query_end, const OverlapsWithinParameters< Position_ > &params, OverlapsWithinWorkspace< Index_ > &workspace, std::vector< Index_ > &matches)

Detailed Description

Header-only library for nested containment lists.

Typedef Documentation

◆ ArrayElement

template<class Array_ >

using nclist::ArrayElement = typename std::remove_const<typename std::remove_reference<decltype(std::declval<Array_>()[0])>::type>::type

Convenient shorthand to get the type of element in an array or array-like object.

Template Parameters

Array_ Class with a [ method that accepts an Index_ and returns a value or reference.

Function Documentation

◆ build() [1/2]

template<typename Index_ , typename Position_ >

Nclist< Index_, Position_ > nclist::build	(	Index_	num_intervals,
		const Position_ *	starts,
		const Position_ *	ends )

Template Parameters

Index_	Integer type of the subject interval index.
Position_	Numeric type for the start/end position of each interval.

Parameters

	num_intervals	Number of subject intervals to include in the NCList.
[in]	starts	Pointer to an array of length `num_intervals`, containing the start positions of all subject intervals.
[in]	ends	Pointer to an array of length `num_intervals`, containing the end positions of all subject intervals. The `i`-th subject interval is defined as `[starts[i], ends[i])`. Note the non-inclusive nature of the end positions.

Returns: A Nclist containing all subject intervals.

◆ build() [2/2]

template<typename Index_ , typename Position_ >

Nclist< Index_, Position_ > nclist::build	(	Index_	num_subset,
		const Index_ *	subset,
		const Position_ *	starts,
		const Position_ *	ends )

Template Parameters

Index_	Integer type of the subject interval index.
Position_	Numeric type for the start/end positions of each interval.

Parameters

	num_subset	Number of subject intervals in the subset to include in the `Nclist`.
[in]	subset	Pointer to an array of length equal to `num_subset`, containing the subset of subject intervals to include in the NCList.
[in]	starts	Pointer to an array containing the start positions of all subject intervals. This should be long enough to be addressable by any element in `[subset, subset + num_subset)`.
[in]	ends	Pointer to an array containing the end positions of all subject intervals. This should be long enough to be addressable by any element in `[subset, subset + num_subset)`, where the `i`-th subject interval is defined as `[starts[i], ends[i])`. Note the non-inclusive nature of the end positions.

Returns: A Nclist containing the specified subset of subject intervals.

◆ build_custom() [1/2]

template<typename Index_ , class StartArray_ , class EndArray_ >

Nclist< Index_, ArrayElement< StartArray_ > > nclist::build_custom	(	Index_	num_intervals,
		const StartArray_ &	starts,
		const EndArray_ &	ends )

Template Parameters

Index_	Integer type of the subject interval index.
StartArray_	Class with a `[` method that accepts an `Index_` and returns the start position of the associated interval.
EndArray_	Class with a `[` method that accepts an `Index_` and returns the end position of the associated interval. The type of position (after removing references and `const`-ness) should be the same as that returned by `StartArray`'s `[` method`.
Position_	Numeric type for the start/end position of each interval.

Parameters

	num_intervals	Number of subject intervals to include in the NCList.
[in]	starts	Array-like object containing the start positions of all subject intervals. This should be addressable by any element in `[0, num_intervals)`.
[in]	ends	Array-like object containing the end positions of all subject intervals. This should be addressable by any element in `[0, num_intervals)`, where the `i`-th subject interval is defined as `[starts[i], ends[i])`. Note the non-inclusive nature of the end positions.

Returns: A Nclist containing the specified subset of subject intervals.

◆ build_custom() [2/2]

template<typename Index_ , class StartArray_ , class EndArray_ >

Nclist< Index_, ArrayElement< StartArray_ > > nclist::build_custom	(	Index_	num_subset,
		const Index_ *	subset,
		const StartArray_ &	starts,
		const EndArray_ &	ends )

Template Parameters

Index_	Integer type of the subject interval index.
StartArray_	Class with a `[` method that accepts an `Index_` and returns the start position of the associated interval.
EndArray_	Class with a `[` method that accepts an `Index_` and returns the end position of the associated interval. The type of position (after removing references) should be the same as that returned by `StartArray`'s `[` method`.

Parameters

	num_subset	Number of subject intervals in the subset to include in the `Nclist`.
[in]	subset	Pointer to an array of length equal to `num_subset`, containing the subset of subject intervals to include in the NCList.
[in]	starts	Array-like object containing the start positions of all subject intervals. This should be addressable by any element in `[subset, subset + num_subset)`.
[in]	ends	Array-like object containing the end positions of all subject intervals. This should be addressable by any element in `[subset, subset + num_subset)`, where the `i`-th subject interval is defined as `[starts[i], ends[i])`. Note the non-inclusive nature of the end positions.

Returns: A Nclist containing the specified subset of subject intervals.

◆ overlaps_any()

template<typename Index_ , typename Position_ >

void nclist::overlaps_any	(	const Nclist< Index_, Position_ > &	subject,
		Position_	query_start,
		Position_	query_end,
		const OverlapsAnyParameters< Position_ > &	params,
		OverlapsAnyWorkspace< Index_ > &	workspace,
		std::vector< Index_ > &	matches )

Find subject intervals that exhibit any overlap with the query interval.

Template Parameters

Index_	Integer type of the subject interval index.
Position_	Numeric type for the start/end positions of each interval.

Parameters

	subject	An `Nclist` of subject intervals, typically built with `build()`.
	query_start	Start of the query interval.
	query_end	Non-inclusive end of the query interval.
	params	Parameters for the search.
	workspace	Workspace for intermediate data structures. This can be default-constructed and re-used across `overlaps_any()` calls.
[out]	matches	On output, vector of subject interval indices that overlap with the query interval. Indices are reported in arbitrary order.

◆ overlaps_end()

template<typename Index_ , typename Position_ >

void nclist::overlaps_end	(	const Nclist< Index_, Position_ > &	subject,
		Position_	query_start,
		Position_	query_end,
		const OverlapsEndParameters< Position_ > &	params,
		OverlapsEndWorkspace< Index_ > &	workspace,
		std::vector< Index_ > &	matches )

Find subject intervals with the same end position as the query interval.

Template Parameters

Index_	Integer type of the subject interval index.
Position_	Numeric type for the start/end positions of each interval.

Parameters

	subject	An `Nclist` of subject intervals, typically built with `build()`.
	query_start	Start of the query interval.
	query_end	Non-inclusive end of the query interval.
	params	Parameters for the search.
	workspace	Workspace for intermediate data structures. This can be default-constructed and re-used across `overlaps_end()` calls.
[out]	matches	On output, vector of subject interval indices that overlap with the query interval. Indices are reported in arbitrary order.

◆ overlaps_equal()

template<typename Index_ , typename Position_ >

void nclist::overlaps_equal	(	const Nclist< Index_, Position_ > &	subject,
		Position_	query_start,
		Position_	query_end,
		const OverlapsEqualParameters< Position_ > &	params,
		OverlapsEqualWorkspace< Index_ > &	workspace,
		std::vector< Index_ > &	matches )

Find subject intervals with the same start and end positions as the query interval. By default, given a subject interval [subject_start, subject_end), an overlap is considered if subject_start == query_end and query_start == subject_end. This behavior can be tuned with parameters in params.

Template Parameters

Index_	Integer type of the subject interval index.
Position_	Numeric type for the start/end positions of each interval.

Parameters

	subject	An `Nclist` of subject intervals, typically built with `build()`.
	query_start	Start of the query interval.
	query_end	Non-inclusive end of the query interval.
	params	Parameters for the search.
	workspace	Workspace for intermediate data structures. This can be default-constructed and re-used across `overlaps_equal()` calls.
[out]	matches	On output, vector of subject interval indices that overlap with the query interval. Indices are reported in arbitrary order.

◆ overlaps_extend()

template<typename Index_ , typename Position_ >

void nclist::overlaps_extend	(	const Nclist< Index_, Position_ > &	subject,
		Position_	query_start,
		Position_	query_end,
		const OverlapsExtendParameters< Position_ > &	params,
		OverlapsExtendWorkspace< Index_ > &	workspace,
		std::vector< Index_ > &	matches )

Find subject ranges that are extended by the query range, i.e., each subject range is a subrange of the query.

Template Parameters

Index_	Integer type of the subject range index.
Position_	Numeric type for the start/end positions of each range.

Parameters

	subject	An `Nclist` of subject ranges, typically built with `build()`.
	query_start	Start of the query range.
	query_end	Non-inclusive end of the query range.
	params	Parameters for the search.
	workspace	Workspace for intermediate data structures. This can be default-constructed and re-used across `overlaps_extend()` calls.
[out]	matches	On output, vector of subject range indices that overlap with the query range. Indices are reported in arbitrary order.

◆ overlaps_start()

template<typename Index_ , typename Position_ >

void nclist::overlaps_start	(	const Nclist< Index_, Position_ > &	subject,
		Position_	query_start,
		Position_	query_end,
		const OverlapsStartParameters< Position_ > &	params,
		OverlapsStartWorkspace< Index_ > &	workspace,
		std::vector< Index_ > &	matches )

Find subject ranges that have the same start position as the query.

Template Parameters

Index_	Integer type of the subject range index.
Position_	Numeric type for the start/end positions of each range.

Parameters

	subject	An `Nclist` of subject ranges, typically built with `build()`.
	query_start	Start of the query range.
	query_end	Non-inclusive end of the query range.
	params	Parameters for the search.
	workspace	Workspace for intermediate data structures. This can be default-constructed and re-used across `overlaps_end()` calls.
[out]	matches	On output, vector of subject range indices that overlap with the query range. Indices are reported in arbitrary order.

◆ overlaps_within()

template<typename Index_ , typename Position_ >

void nclist::overlaps_within	(	const Nclist< Index_, Position_ > &	subject,
		Position_	query_start,
		Position_	query_end,
		const OverlapsWithinParameters< Position_ > &	params,
		OverlapsWithinWorkspace< Index_ > &	workspace,
		std::vector< Index_ > &	matches )

Find subject ranges where the query range lies within them, i.e., the query is a subrange of each subject range.

Template Parameters

Index_	Integer type of the subject range index.
Position_	Numeric type for the start/end positions of each range.

Parameters

	subject	An `Nclist` of subject ranges, typically built with `build()`.
	query_start	Start of the query range.
	query_end	Non-inclusive end of the query range.
	params	Parameters for the search.
	workspace	Workspace for intermediate data structures. This can be default-constructed and re-used across `overlaps_within()` calls.
[out]	matches	On output, vector of subject range indices that overlap with the query range. Indices are reported in arbitrary order.

Classes

Typedefs

Functions

Detailed Description

Typedef Documentation

◆ ArrayElement

Function Documentation

◆ build() [1/2]

◆ build() [2/2]

◆ build_custom() [1/2]

◆ build_custom() [2/2]

◆ overlaps_any()

◆ overlaps_end()

◆ overlaps_equal()

◆ overlaps_extend()

◆ overlaps_start()

◆ overlaps_within()