seqan3::gap_decorator< inner_type > Class Template Reference

A gap decorator allows the annotation of sequences with gap symbols while leaving the underlying sequence unmodified. More...

#include <seqan3/alignment/decorator/gap_decorator.hpp>

Inheritance diagram for seqan3::gap_decorator< inner_type >:

Classes
class	basic_iterator
	The iterator type over a seqan3::gap_decorator. More...

Public Types
using	unaligned_sequence_type = inner_type
	The underlying ungapped range type.
Range-associated member types
using	value_type = gapped< std::ranges::range_value_t< inner_type > >
	The variant type of the alphabet type and gap symbol type (see seqan3::gapped).
using	reference = value_type
	Use the value type as reference type because the underlying sequence must not be modified.
using	const_reference = reference
	const_reference type equals reference type equals value type because the underlying sequence must not be modified.
using	size_type = std::ranges::range_size_t< inner_type >
	The size_type of the underlying sequence.
using	difference_type = std::ranges::range_difference_t< inner_type >
	The difference type of the underlying sequence.

Public Member Functions
Constructors, destructor and assignment
	gap_decorator ()=default
	Default constructor.
	gap_decorator (gap_decorator const &)=default
	Defaulted.
gap_decorator &	operator= (gap_decorator const &)=default
	Defaulted.
	gap_decorator (gap_decorator &&rhs)=default
	Defaulted.
gap_decorator &	operator= (gap_decorator &&rhs)=default
	Defaulted.
	~gap_decorator ()=default
	Defaulted.
template<typename other_range_t > requires (!std::same_as<other_range_t, gap_decorator>) && std::same_as<std::remove_cvref_t<other_range_t>, std::remove_cvref_t<inner_type>> && std::ranges::viewable_range<other_range_t>
	gap_decorator (other_range_t &&range)
	Construct with the ungapped range type.
size_type	size () const
	Returns the total length of the aligned sequence.
Iterators
const_iterator	begin () const noexcept
	Returns an iterator to the first element of the container.
const_iterator	cbegin () const noexcept
	Returns an iterator to the first element of the container.
const_iterator	end () const noexcept
	Returns an iterator pointing behind the last element of the decorator.
const_iterator	cend () const noexcept
	Returns an iterator pointing behind the last element of the decorator.
Element access
reference	at (size_type const i)
	Return the i-th element as a reference.
const_reference	at (size_type const i) const
	Return the i-th element as a reference.
reference	operator[] (size_type const i) const
	Return the i-th element as a reference.

Private Types
using	anchor_gap_t = typename std::pair< size_t, size_t >
	The gap type as a tuple storing position and accumulated gap lengths.
using	anchor_set_type = std::set< anchor_gap_t >
	The type of set to store the anchor gaps.
using	const_iterator = iterator
	The const_iterator equals the iterator type. Since no references are ever returned and thus the underlying sequence cannot be modified through the iterator there is no need for const.
using	iterator = basic_iterator< true >
	The iterator type of this container (a bidirectional iterator).
using	set_iterator_type = typename anchor_set_type::iterator
	The iterator type for an anchor set.
using	ungapped_view_type = decltype(views::type_reduce(std::declval< inner_type && >()))
	The type of the underlying view wrapped in seqan3::views::type_reduce.

Private Member Functions
size_type	gap_length (set_iterator_type it) const
	Helper function to compute the length of the gap indicated by the input iterator.
void	rupdate (size_type const pos, size_type const offset)
	Update all anchor gaps after the indicated position by adding an offset.
void	update (set_iterator_type it, size_type const offset)
	Update all anchor gaps after indicated position by substracting an offset.

Private Attributes
anchor_set_type	anchors {}
	Set storing the anchor gaps.
ungapped_view_type	ungapped_view {}
	Stores a (copy of a) view to the ungapped, underlying sequence.

Static Private Attributes
static constexpr size_t	bound_dummy {std::numeric_limits<size_t>::max()}
	The maximum value is needed for a correct search with upper_bound() in the anchor set.

Friends
Comparison operators
Compares two seqan3::gap_decorator 's by underlying sequence and gaps. Parameters [in] lhs The left-hand side gap decorator to compare. [in] rhs The right-hand side gap decorator to compare. Returns A boolean flag indicating (in)equality of the aligned sequences. Complexity Worst case: $O(n\ast \log k)$ Constant in case the decorators have not the same number of (consecutive) gaps. Exceptions Strong exception guarantee.
bool	operator== (gap_decorator const &lhs, gap_decorator const &rhs)
	Checks whether lhs is equal to rhs.
bool	operator!= (gap_decorator const &lhs, gap_decorator const &rhs)
	Checks whether lhs is not equal to rhs.
bool	operator< (gap_decorator const &lhs, gap_decorator const &rhs)
	Checks whether lhs is less than rhs.
bool	operator<= (gap_decorator const &lhs, gap_decorator const &rhs)
	Checks whether lhs is less than or equal to rhs.
bool	operator> (gap_decorator const &lhs, gap_decorator const &rhs)
	Checks whether lhs is greater than rhs.
bool	operator>= (gap_decorator const &lhs, gap_decorator const &rhs)
	Checks whether lhs is greater than or equal to rhs.

Aligned sequence modifications
iterator	insert_gap (const_iterator const it, size_type const count=1)
	Insert a gap of length count at the aligned sequence iterator position.
iterator	erase_gap (const_iterator const it)
	Erase one gap symbol at the indicated iterator postion.
iterator	erase_gap (const_iterator const first, const_iterator const last)
	Erase gap symbols at the iterator postions [first, last[.
template<typename unaligned_sequence_t > requires std::assignable_from<gap_decorator &, unaligned_sequence_t>
void	assign_unaligned (gap_decorator &dec, unaligned_sequence_t &&unaligned)
	Assigns a new sequence of type seqan3::gap_decorator::unaligned_sequence_type to the decorator.

Additional Inherited Members
Related Symbols inherited from writable_aligned_sequence
std::ranges::iterator_t< aligned_seq_t >	insert_gap (aligned_seq_t &aligned_seq, typename aligned_seq_t::const_iterator pos_it)
	Insert a seqan3::gap into an aligned sequence.
std::ranges::iterator_t< aligned_seq_t >	insert_gap (aligned_seq_t &aligned_seq, typename aligned_seq_t::const_iterator pos_it, typename aligned_seq_t::size_type size)
	Insert multiple seqan3::gap into an aligned sequence.
std::ranges::iterator_t< aligned_seq_t >	erase_gap (aligned_seq_t &aligned_seq, typename aligned_seq_t::const_iterator pos_it)
	Erase a seqan3::gap from an aligned sequence.
std::ranges::iterator_t< aligned_seq_t >	erase_gap (aligned_seq_t &aligned_seq, typename aligned_seq_t::const_iterator first, typename aligned_seq_t::const_iterator last)
	Erase multiple seqan3::gap from an aligned sequence.
void	assign_unaligned (aligned_seq_t &aligned_seq, unaligned_sequence_type &&unaligned_seq)
	Assign an ungapped sequence to a gapped sequence.
template<sequence_container aligned_seq_t>
aligned_seq_t::iterator	insert_gap (aligned_seq_t &aligned_seq, typename aligned_seq_t::const_iterator pos_it)
	An implementation of seqan3::writable_aligned_sequence::insert_gap for sequence containers.
template<sequence_container aligned_seq_t>
aligned_seq_t::iterator	insert_gap (aligned_seq_t &aligned_seq, typename aligned_seq_t::const_iterator pos_it, typename aligned_seq_t::size_type size)
	An implementation of seqan3::writable_aligned_sequence::insert_gap for sequence containers.
template<sequence_container aligned_seq_t>
aligned_seq_t::iterator	erase_gap (aligned_seq_t &aligned_seq, typename aligned_seq_t::const_iterator pos_it)
	An implementation of seqan3::writable_aligned_sequence::erase_gap for sequence containers.
template<sequence_container aligned_seq_t>
aligned_seq_t::iterator	erase_gap (aligned_seq_t &aligned_seq, typename aligned_seq_t::const_iterator first, typename aligned_seq_t::const_iterator last)
	An implementation of seqan3::writable_aligned_sequence::erase_gap for sequence containers.
template<sequence_container aligned_seq_t, std::ranges::forward_range unaligned_sequence_type>
void	assign_unaligned (aligned_seq_t &aligned_seq, unaligned_sequence_type &&unaligned_seq)
	An implementation of seqan3::writable_aligned_sequence::assign_unaligned_sequence for sequence containers.
template<typename range_type >
std::ranges::iterator_t< range_type >	insert_gap (range_type &rng, std::ranges::iterator_t< range_type > const pos_it, typename range_type::size_type const size=1)
	An implementation of seqan3::writable_aligned_sequence::insert_gap for ranges with the corresponding member function insert_gap(it, size).
template<typename range_type >
std::ranges::iterator_t< range_type >	erase_gap (range_type &rng, std::ranges::iterator_t< range_type > const pos_it)
	An implementation of seqan3::writable_aligned_sequence::erase_gap for ranges with the corresponding member function erase_gap(it).
template<typename range_type >
std::ranges::iterator_t< range_type >	erase_gap (range_type &rng, std::ranges::iterator_t< range_type > const first, std::ranges::iterator_t< range_type > const last)
	An implementation of seqan3::writable_aligned_sequence::erase_gap for ranges with the corresponding member function erase_gap(first, last).

Detailed Descriptionstable-api

template<std::ranges::viewable_range inner_type>
requires std::ranges::random_access_range<inner_type> && std::ranges::sized_range<inner_type> && (std::is_const_v<std::remove_reference_t<inner_type>> || std::ranges::view<inner_type>)
class seqan3::gap_decorator< inner_type >

A gap decorator allows the annotation of sequences with gap symbols while leaving the underlying sequence unmodified.

Template Parameters

inner_type

The type of range that will be decorated with gaps; must model std::ranges::random_access_range and std::ranges::sized_range.

This class may be used whenever you want to store or compute an alignment. The underlying (ungapped) sequence remains unmodified, and is augmented with gap information. The seqan3::gap_decorator behaves just like a vector over a gapped alphabet when iterating over it, inserting/erasing gaps or accessing a position. The only difference lies in the performance and size overhead (see below).

Performance

n The length of the underlying sequence. k The number of contiguous gaps (not gap symbols). l The total number of gap symbols.

	access next	random access	gap insert/erase at end	gap insert/erase random	size overhead
decorator	$O(1)$	$O(\log (k))$	$O(\log (k))$	$O(k)$	$O(k)$
vector	$O(1)$	$O(1)$	$O(1)$	$O(n)$	$O(n)$

The size overhead refers to the space that is needed when using each of the data structures in addition to an already existing ungapped sequence.

Implementation details

This decorator stores a std::set over tuples of (pos, cumulative_size) where every entry represents one contiguous stretch of gaps. pos is the (virtual) insert position in the underlying range and cumulative_size is the length of that contiguous stretch of gaps plus the length of all preceding elements. Resolving random access requires logarithmic access into the set and inserting or removing a gap symbol additionally entails updating all subsequent elements in the set to preserve correct cumulative sizes.

The seqan3::gap_decorator::iterator type

Attention

The iterator of the seqan3::gap_decorator does not model the Cpp17BidirectionalIterator requirements of the STL because dereferencing the iterator returns a proxy and no operator-> is provided. It does model the C++20 std::bidirectional_iterator.

This entity is stable. Since version 3.1.

Member Typedef Documentation

const_reference [stable-api]

using seqan3::gap_decorator< inner_type >::const_reference = reference

stable-api

const_reference type equals reference type equals value type because the underlying sequence must not be modified.

This entity is stable. Since version 3.1.

difference_type [stable-api]

using seqan3::gap_decorator< inner_type >::difference_type = std::ranges::range_difference_t<inner_type>

stable-api

The difference type of the underlying sequence.

This entity is stable. Since version 3.1.

reference [stable-api]

using seqan3::gap_decorator< inner_type >::reference = value_type

stable-api

Use the value type as reference type because the underlying sequence must not be modified.

This entity is stable. Since version 3.1.

size_type [stable-api]

using seqan3::gap_decorator< inner_type >::size_type = std::ranges::range_size_t<inner_type>

stable-api

The size_type of the underlying sequence.

This entity is stable. Since version 3.1.

unaligned_sequence_type [stable-api]

using seqan3::gap_decorator< inner_type >::unaligned_sequence_type = inner_type

stable-api

The underlying ungapped range type.

This entity is stable. Since version 3.1.

value_type [stable-api]

using seqan3::gap_decorator< inner_type >::value_type = gapped<std::ranges::range_value_t<inner_type> >

stable-api

The variant type of the alphabet type and gap symbol type (see seqan3::gapped).

This entity is stable. Since version 3.1.

Constructor & Destructor Documentation

gap_decorator() [1/2] [stable-api]

template<std::ranges::viewable_range inner_type>

seqan3::gap_decorator< inner_type >::gap_decorator ( )

stable-apidefault

Default constructor.

Attention

All operations on a default constructed decorator, except assigning a new range (e.g., seqan3::gap_decorator::assign_unaligned), are undefined behaviour.

This entity is stable. Since version 3.1.

gap_decorator() [2/2] [experimental-api]

template<std::ranges::viewable_range inner_type>

template<typename other_range_t >
requires (!std::same_as<other_range_t, gap_decorator>) && std::same_as<std::remove_cvref_t<other_range_t>, std::remove_cvref_t<inner_type>> && std::ranges::viewable_range<other_range_t>

seqan3::gap_decorator< inner_type >::gap_decorator ( other_range_t &&  range )

experimental-apiinline

Construct with the ungapped range type.

This entity is experimental and subject to change in the future. Experimental since version 3.1. This is a non-standard C++ extension.

Member Function Documentation

at() [1/2] [stable-api]

template<std::ranges::viewable_range inner_type>

reference seqan3::gap_decorator< inner_type >::at ( size_type const  i )

stable-apiinline

Return the i-th element as a reference.

Parameters

i	The element to retrieve.

Returns

A reference of the gapped alphabet type.

Complexity

$O(\log k)$ where $k$ is the number of gaps.

Exceptions

Throws std::out_of_range exception if i is out of range.

This entity is stable. Since version 3.1.

at() [2/2] [stable-api]

template<std::ranges::viewable_range inner_type>

const_reference seqan3::gap_decorator< inner_type >::at ( size_type const  i ) const

stable-apiinline

Return the i-th element as a reference.

Parameters

i	The element to retrieve.

Returns

A reference of the gapped alphabet type.

Complexity

$O(\log k)$ where $k$ is the number of gaps.

Exceptions

Throws std::out_of_range exception if i is out of range.

This entity is stable. Since version 3.1.

begin() [stable-api]

template<std::ranges::viewable_range inner_type>

const_iterator seqan3::gap_decorator< inner_type >::begin ( ) const

stable-apiinlinenoexcept

Returns an iterator to the first element of the container.

Returns

Iterator to the first element.

If the container is empty, the returned iterator will be equal to end().

Complexity

Constant.

Exceptions

No-throw guarantee.

This entity is stable. Since version 3.1.

cbegin() [stable-api]

template<std::ranges::viewable_range inner_type>

const_iterator seqan3::gap_decorator< inner_type >::cbegin ( ) const

stable-apiinlinenoexcept

Returns an iterator to the first element of the container.

Returns

Iterator to the first element.

If the container is empty, the returned iterator will be equal to end().

Complexity

Constant.

Exceptions

No-throw guarantee.

This entity is stable. Since version 3.1.

cend() [stable-api]

template<std::ranges::viewable_range inner_type>

const_iterator seqan3::gap_decorator< inner_type >::cend ( ) const

stable-apiinlinenoexcept

Returns an iterator pointing behind the last element of the decorator.

Returns

Iterator pointing behind the last element.

Attention

This element acts as a placeholder; attempting to dereference it results in undefined behaviour.

Complexity

Constant.

Exceptions

No-throw guarantee.

This entity is stable. Since version 3.1.

end() [stable-api]

template<std::ranges::viewable_range inner_type>

const_iterator seqan3::gap_decorator< inner_type >::end ( ) const

stable-apiinlinenoexcept

Returns an iterator pointing behind the last element of the decorator.

Returns

Iterator pointing behind the last element.

Attention

This element acts as a placeholder; attempting to dereference it results in undefined behaviour.

Complexity

Constant.

Exceptions

No-throw guarantee.

This entity is stable. Since version 3.1.

erase_gap() [1/2] [stable-api]

template<std::ranges::viewable_range inner_type>

iterator seqan3::gap_decorator< inner_type >::erase_gap ( const_iterator const  first, const_iterator const  last  )

stable-apiinline

Erase gap symbols at the iterator postions [first, last[.

Parameters

[in]	first	The iterator pointing to the position where to start inserting gaps.
[in]	last	The iterator pointing to the position where to stop erasing gaps.

Returns

Iterator following the last removed element.

Exceptions

seqan3::gap_erase_failure

if [first, last[ does not correspond to a consecutive range of seqan3::gap 's.

Complexity

$O(\log k)$

This entity is stable. Since version 3.1.

erase_gap() [2/2] [stable-api]

template<std::ranges::viewable_range inner_type>

iterator seqan3::gap_decorator< inner_type >::erase_gap ( const_iterator const  it )

stable-apiinline

Erase one gap symbol at the indicated iterator postion.

Parameters

it	Iterator indicating the gap to be erased.

Returns

Iterator following the last removed element.

Exceptions

seqan3::gap_erase_failure

if character is no seqan3::gap.

Complexity

$O(\log k)$

This entity is stable. Since version 3.1.

gap_length() [no-api]

template<std::ranges::viewable_range inner_type>

size_type seqan3::gap_decorator< inner_type >::gap_length ( set_iterator_type  it ) const

no-apiinlineprivate

Helper function to compute the length of the gap indicated by the input iterator.

Parameters

[in]

it

Iterator over the internal gap set.

Returns

The gap length corresponding to the gap pointed at by it.

The length of a gap pointed to by it is the difference of the current cumulative sum of gaps (second tuple position) and the one of its predecessor (if existing).

Exceptions

Strong exception guarantee.

insert_gap() [stable-api]

template<std::ranges::viewable_range inner_type>

iterator seqan3::gap_decorator< inner_type >::insert_gap ( const_iterator const  it, size_type const  count = 1  )

stable-apiinline

Insert a gap of length count at the aligned sequence iterator position.

Parameters

it	Iterator indicating the gap start position in the aligned sequence.
count	Number of gap symbols to be inserted.

Returns

An iterator pointing to the start position of the insertion.

Complexity

Average and worst case (insertion before last gap): $O(k)$, Best case (back insertion): $O(\log k)$.

This entity is stable. Since version 3.1.

operator[]() [stable-api]

template<std::ranges::viewable_range inner_type>

reference seqan3::gap_decorator< inner_type >::operator[] ( size_type const  i ) const

stable-apiinline

Return the i-th element as a reference.

Parameters

i	The element to retrieve.

Returns

A reference of the gapped alphabet type.

This function delegates to an iterator seqan3::gap_decorator.

Complexity

$O(\log k)$ where $k$ is the number of gaps.

This entity is stable. Since version 3.1.

rupdate() [no-api]

template<std::ranges::viewable_range inner_type>

void seqan3::gap_decorator< inner_type >::rupdate ( size_type const  pos, size_type const  offset  )

no-apiinlineprivate

Update all anchor gaps after the indicated position by adding an offset.

Parameters

[in]	pos	Gap index after which to perform the update.
[in]	offset	Offset to be added to the virtual gap positions and its accumulators.

In order to avoid key conflicts when inserting into anchors, the update is done in reverse manner excluding the indicated gap.

Complexity

Linear in the number of gaps.

size() [stable-api]

template<std::ranges::viewable_range inner_type>

size_type seqan3::gap_decorator< inner_type >::size ( ) const

stable-apiinline

Returns the total length of the aligned sequence.

Returns

The total length of the aligned sequence (gaps included).

Complexity

Constant.

Exceptions

Strong exception guarantee.

This entity is stable. Since version 3.1.

update() [no-api]

template<std::ranges::viewable_range inner_type>

void seqan3::gap_decorator< inner_type >::update ( set_iterator_type  it, size_type const  offset  )

no-apiinlineprivate

Update all anchor gaps after indicated position by substracting an offset.

Parameters

[in]	it	Iterator pointing to the first anchor node to update.
[in]	offset	Offset to be removed from the virtual gap positions and its accumulators.

In order to avoid key conflicts when inserting into anchors, the decreasing is done in a forward manner excluding the indicated gap.

Complexity

Linear in the number of gaps.

Friends And Related Symbol Documentation

assign_unaligned [experimental-api]

template<std::ranges::viewable_range inner_type>

template<typename unaligned_sequence_t >
requires std::assignable_from<gap_decorator &, unaligned_sequence_t>

void assign_unaligned ( gap_decorator< inner_type > &  dec, unaligned_sequence_t &&  unaligned  )

experimental-apifriend

Assigns a new sequence of type seqan3::gap_decorator::unaligned_sequence_type to the decorator.

Parameters

[in,out]	dec	The decorator to modify.
[in]	unaligned	The unaligned sequence to assign.

This entity is experimental and subject to change in the future. Experimental since version 3.1.

operator!= [stable-api]

template<std::ranges::viewable_range inner_type>

bool operator!= ( gap_decorator< inner_type > const &  lhs, gap_decorator< inner_type > const &  rhs  )

stable-apifriend

Checks whether lhs is not equal to rhs.

This entity is stable. Since version 3.1.

operator< [stable-api]

template<std::ranges::viewable_range inner_type>

bool operator< ( gap_decorator< inner_type > const &  lhs, gap_decorator< inner_type > const &  rhs  )

stable-apifriend

Checks whether lhs is less than rhs.

This entity is stable. Since version 3.1.

operator<= [stable-api]

template<std::ranges::viewable_range inner_type>

bool operator<= ( gap_decorator< inner_type > const &  lhs, gap_decorator< inner_type > const &  rhs  )

stable-apifriend

Checks whether lhs is less than or equal to rhs.

This entity is stable. Since version 3.1.

operator== [stable-api]

template<std::ranges::viewable_range inner_type>

bool operator== ( gap_decorator< inner_type > const &  lhs, gap_decorator< inner_type > const &  rhs  )

stable-apifriend

Checks whether lhs is equal to rhs.

This entity is stable. Since version 3.1.

operator> [stable-api]

template<std::ranges::viewable_range inner_type>

bool operator> ( gap_decorator< inner_type > const &  lhs, gap_decorator< inner_type > const &  rhs  )

stable-apifriend

Checks whether lhs is greater than rhs.

This entity is stable. Since version 3.1.

operator>= [stable-api]

template<std::ranges::viewable_range inner_type>

bool operator>= ( gap_decorator< inner_type > const &  lhs, gap_decorator< inner_type > const &  rhs  )

stable-apifriend

Checks whether lhs is greater than or equal to rhs.

This entity is stable. Since version 3.1.

---

The documentation for this class was generated from the following file:

• gap_decorator.hpp