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

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

struct	NearestParameters
	Parameters for `nearest()`. More...

struct	NearestWorkspace
	Workspace for `nearest()`. 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	nearest (const Nclist< Index_, Position_ > &subject, const Position_ query_start, const Position_ query_end, const NearestParameters< Position_ > &params, NearestWorkspace< Index_ > &workspace, std::vector< Index_ > &matches)

template<typename Index_ , typename Position_ >
void	overlaps_any (const Nclist< Index_, Position_ > &subject, const Position_ query_start, const 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, const Position_ query_start, const 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, const Position_ query_start, const 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, const Position_ query_start, const 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, const Position_ query_start, const 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.

◆ nearest()

template<typename Index_ , typename Position_ >

void nclist::nearest	(	const Nclist< Index_, Position_ > &	subject,
		const Position_	query_start,
		const Position_	query_end,
		const NearestParameters< Position_ > &	params,
		NearestWorkspace< Index_ > &	workspace,
		std::vector< Index_ > &	matches )

Find subject intervals that are nearest to the query interval. If any overlaps are present, all overlapping intervals are reported. If no overlaps are present, the subject interval with the smallest gap to the query is reported. A gap is defined as the distance between the query start and subject end (for queries after the subject) or the subject start and the query end (otherwise). If multiple subjects have the same gap, all ties are reported.

This function is based on its counterpart of the same name in the IRanges R/Bioconductor package. Users should set NearestParameters::adjacent_equals_overlap = true to obtain the same results as the R package,

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 `nearest()` calls.
[out]	matches	On output, vector of indices of the nearest subject intervals to the query interval. Indices are reported in arbitrary order.

◆ overlaps_any()

template<typename Index_ , typename Position_ >

void nclist::overlaps_any	(	const Nclist< Index_, Position_ > &	subject,
		const Position_	query_start,
		const 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,
		const Position_	query_start,
		const 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,
		const Position_	query_start,
		const 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,
		const Position_	query_start,
		const 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,
		const Position_	query_start,
		const 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]

◆ nearest()

◆ overlaps_any()

◆ overlaps_end()

◆ overlaps_equal()

◆ overlaps_extend()

◆ overlaps_start()

◆ overlaps_within()