SeqAn3  3.0.2
The Modern C++ library for sequence analysis.
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/range/decorator/gap_decorator.hpp>

+ Inheritance diagram for seqan3::gap_decorator< inner_type >:

Classes

class  gap_decorator_iterator
 The iterator type over a seqan3::gap_decorator. More...
 

Public Types

using unaligned_seq_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. Attention: all operations on a solely default constructed decorator, except assigning a new range, are UB.
 
 gap_decorator (gap_decorator const &)=default
 Defaulted.
 
gap_decoratoroperator= (gap_decorator const &)=default
 Defaulted.
 
 gap_decorator (gap_decorator &&rhs)=default
 Defaulted.
 
gap_decoratoroperator= (gap_decorator &&rhs)=default
 Defaulted.
 
 ~gap_decorator ()=default
 Defaulted.
 
template<typename 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. More...
 
Iterators
const_iterator begin () const noexcept
 Returns an iterator to the first element of the container. More...
 
const_iterator cbegin () const noexcept
 Returns an iterator to the first element of the container. More...
 
const_iterator end () const noexcept
 Returns an iterator pointing behind the last element of the decorator. More...
 
const_iterator cend () const noexcept
 Returns an iterator pointing behind the last element of the decorator. More...
 
Element access
reference at (size_type const i)
 Return the i-th element as a reference. More...
 
const_reference at (size_type const i) const
 Return the i-th element as a reference. More...
 
reference operator[] (size_type const i) const
 Return the i-th element as a reference. More...
 

Friends

Comparison operators

Compares two seqan3::gap_decorator 's by underlying sequence and gaps.

Parameters
[in]lhsThe left-hand side gap decorator to compare.
[in]rhsThe right-hand side gap decorator to compare.
Returns
A boolean flag indicating (in)equality of the aligned sequences.

Complexity

Worst case: $O(n*\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.
 

Related Functions

(Note that these are not member functions.)

Requirements for seqan3::writable_aligned_sequence

You can expect these functions on all types that model seqan3::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. More...
 
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. More...
 
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. More...
 
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. More...
 
void assign_unaligned (aligned_seq_t &aligned_seq, unaligned_sequence_type &&unaligned_seq)
 Assign an ungapped sequence to a gapped sequence. More...
 
Aligned sequence interface for ranges that have the corresponding member functions.

Enables ranges to model seqan3::aligned_sequence if they have the member functions insert_gap() and erase_gap().

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). More...
 
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). More...
 
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). More...
 
Requirements for seqan3::writable_aligned_sequence

You can expect these functions on all types that model seqan3::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. More...
 
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. More...
 
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. More...
 
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. More...
 
void assign_unaligned (aligned_seq_t &aligned_seq, unaligned_sequence_type &&unaligned_seq)
 Assign an ungapped sequence to a gapped sequence. More...
 
Aligned sequence interface for ranges that have the corresponding member functions.

Enables ranges to model seqan3::aligned_sequence if they have the member functions insert_gap() and erase_gap().

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). More...
 
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). More...
 
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). More...
 

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. More...
 
iterator erase_gap (const_iterator const it)
 Erase one gap symbol at the indicated iterator postion. More...
 
iterator erase_gap (const_iterator const first, const_iterator const last)
 Erase gap symbols at the iterator postions [first, last[. More...
 
template<typename unaligned_seq_t >
void assign_unaligned (gap_decorator &dec, unaligned_seq_t &&unaligned)
 Assigns a new sequence of type seqan3::gap_decorator::unaligned_seq_type to the decorator. More...
 

Detailed Description

template<std::ranges::viewable_range 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_typeThe 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.

Member Function Documentation

◆ at() [1/2]

template<std::ranges::viewable_range inner_type>
reference seqan3::gap_decorator< inner_type >::at ( size_type const  i)
inline

Return the i-th element as a reference.

Parameters
iThe 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.

◆ at() [2/2]

template<std::ranges::viewable_range inner_type>
const_reference seqan3::gap_decorator< inner_type >::at ( size_type const  i) const
inline

Return the i-th element as a reference.

Parameters
iThe 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.

◆ begin()

template<std::ranges::viewable_range inner_type>
const_iterator seqan3::gap_decorator< inner_type >::begin ( ) const
inlinenoexcept

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.

◆ cbegin()

template<std::ranges::viewable_range inner_type>
const_iterator seqan3::gap_decorator< inner_type >::cbegin ( ) const
inlinenoexcept

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.

◆ cend()

template<std::ranges::viewable_range inner_type>
const_iterator seqan3::gap_decorator< inner_type >::cend ( ) const
inlinenoexcept

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.

◆ end()

template<std::ranges::viewable_range inner_type>
const_iterator seqan3::gap_decorator< inner_type >::end ( ) const
inlinenoexcept

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.

◆ erase_gap() [1/2]

template<std::ranges::viewable_range inner_type>
iterator seqan3::gap_decorator< inner_type >::erase_gap ( const_iterator const  first,
const_iterator const  last 
)
inline

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

Parameters
[in]firstThe iterator pointing to the position where to start inserting gaps.
[in]lastThe iterator pointing to the position where to stop erasing gaps.
Returns
Iterator following the last removed element.
Exceptions
seqan3::gap_erase_failureif [first, last[ does not correspond to a consecutive range of seqan3::gap 's.

Complexity

$O(\log k)$

◆ erase_gap() [2/2]

template<std::ranges::viewable_range inner_type>
iterator seqan3::gap_decorator< inner_type >::erase_gap ( const_iterator const  it)
inline

Erase one gap symbol at the indicated iterator postion.

Parameters
itIterator indicating the gap to be erased.
Returns
Iterator following the last removed element.
Exceptions
seqan3::gap_erase_failureif character is no seqan3::gap.

Complexity

$O(\log k)$

◆ insert_gap()

template<std::ranges::viewable_range inner_type>
iterator seqan3::gap_decorator< inner_type >::insert_gap ( const_iterator const  it,
size_type const  count = 1 
)
inline

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

Parameters
itIterator indicating the gap start position in the aligned sequence.
countNumber 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)$.

◆ operator[]()

template<std::ranges::viewable_range inner_type>
reference seqan3::gap_decorator< inner_type >::operator[] ( size_type const  i) const
inline

Return the i-th element as a reference.

Parameters
iThe 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.

◆ size()

template<std::ranges::viewable_range inner_type>
size_type seqan3::gap_decorator< inner_type >::size ( ) const
inline

Returns the total length of the aligned sequence.

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

Complexity

Constant.

Exceptions

Strong exception guarantee.

Friends And Related Function Documentation

◆ assign_unaligned() [1/2]

void assign_unaligned ( aligned_seq_t &  aligned_seq,
unaligned_sequence_type &&  unaligned_seq 
)
related

Assign an ungapped sequence to a gapped sequence.

Template Parameters
aligned_seq_tType of the container to reassign; must model seqan3::writable_aligned_sequence.
unaligned_seq_tType of the container to assign from; must correspond to the aligned type without gap information (see details.)
Parameters
[in,out]aligned_seqThe gapped sequence container to assign to.
[in,out]unaligned_seqThe unaligned sequence container to assign from.

An aligned sequence has to be assignable from its unaligned counter part. For example a std::vector<seqan3::gapped<seqan3::dna4>> as well as a seqan3::gap_decorator<std::vector<seqan3::dna4>> can be assigned from s std::vector<seqan3::dna4> via seqan3::assign_unaligned.

Attention
This is a concept requirement, not an actual function (however types modelling this concept will provide an implementation).

◆ assign_unaligned [2/2]

template<std::ranges::viewable_range inner_type>
template<typename unaligned_seq_t >
void assign_unaligned ( gap_decorator< inner_type > &  dec,
unaligned_seq_t &&  unaligned 
)
friend

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

Parameters
[in,out]decThe decorator to modify.
[in]unalignedThe unaligned sequence to assign.

◆ erase_gap() [1/2]

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 
)
related

Erase multiple seqan3::gap from an aligned sequence.

Template Parameters
aligned_seq_tType of the range to modify; must model seqan3::writable_aligned_sequence.
Parameters
[in,out]aligned_seqThe aligned sequence to modify.
[in]firstThe iterator pointing to the position where to start erasing gaps.
[in]lastThe iterator pointing to the position where to stop erasing gaps.
Returns
An iterator following the last removed element. If the iterator last refers to the last element, the std::ranges::end() iterator is returned.
Exceptions
seqan3::gap_erase_failureif one of the characters in [first, last) no seqan3::gap.
Note
This may cause reallocations and thus invalidates all iterators and references. Use the returned iterator.
Attention
This is a concept requirement, not an actual function (however types modelling this concept will provide an implementation).

◆ erase_gap() [2/2]

std::ranges::iterator_t< aligned_seq_t > erase_gap ( aligned_seq_t &  aligned_seq,
typename aligned_seq_t::const_iterator  pos_it 
)
related

Erase a seqan3::gap from an aligned sequence.

Template Parameters
aligned_seq_tType of the range to modify; must model seqan3::writable_aligned_sequence.
Parameters
[in,out]aligned_seqThe aligned sequence to modify.
[in]pos_itThe iterator pointing to the position where to erase a gap.
Returns
An iterator following the removed element. If the iterator pos_it refers to the last element, the std::ranges::end() iterator is returned.
Exceptions
seqan3::gap_erase_failureif there is no seqan3::gap at pos_it.
Note
This may cause reallocations and thus invalidates all iterators and references. Use the returned iterator.
Attention
This is a concept requirement, not an actual function (however types modelling this concept will provide an implementation).

◆ insert_gap() [1/2]

std::ranges::iterator_t< aligned_seq_t > insert_gap ( aligned_seq_t &  aligned_seq,
typename aligned_seq_t::const_iterator  pos_it 
)
related

Insert a seqan3::gap into an aligned sequence.

Template Parameters
aligned_seq_tType of the range to modify; must model seqan3::writable_aligned_sequence.
Parameters
[in,out]aligned_seqThe aligned sequence to modify.
[in]pos_itThe iterator pointing to the position where to insert a gap.
Returns
An iterator pointing to the inserted gap.
Note
This may cause reallocations and thus invalidates all iterators and references. Use the returned iterator.
Attention
This is a concept requirement, not an actual function (however types modeling this concept will provide an implementation).

◆ insert_gap() [2/2]

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 
)
related

Insert multiple seqan3::gap into an aligned sequence.

Template Parameters
aligned_seq_tType of the range to modify; must model seqan3::writable_aligned_sequence.
Parameters
[in,out]aligned_seqThe aligned sequence to modify.
[in]pos_itThe iterator pointing to the position where to insert a gaps.
[in]sizeThe number of gap symbols to insert (will result in a gap of length size).
Returns
An iterator pointing to the first inserted gap or pos_it if size == 0.
Note
This may cause reallocations and thus invalidates all iterators and references. Use the returned iterator.
Attention
This is a concept requirement, not an actual function (however types modelling this concept will provide an implementation).

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