OpenMS
IntegerMassDecomposer< ValueType, DecompositionValueType > Class Template Reference

Implements MassDecomposer interface using algorithm and data structures described in paper "Efficient Mass Decomposition" S. Böcker, Z. Lipták, ACM SAC-BIO, 2004 doi:10.1145/1066677.1066715. More...

#include <OpenMS/CHEMISTRY/MASSDECOMPOSITION/IMS/IntegerMassDecomposer.h>

Inheritance diagram for IntegerMassDecomposer< ValueType, DecompositionValueType >:
[legend]
Collaboration diagram for IntegerMassDecomposer< ValueType, DecompositionValueType >:
[legend]

Public Types

typedef MassDecomposer< ValueType, DecompositionValueType >::value_type value_type
 Type of value to be decomposed. More...
 
typedef MassDecomposer< ValueType, DecompositionValueType >::decomposition_value_type decomposition_value_type
 Type of decomposition value. More...
 
typedef MassDecomposer< ValueType, DecompositionValueType >::decomposition_type decomposition_type
 Type of decomposition. More...
 
typedef MassDecomposer< ValueType, DecompositionValueType >::decompositions_type decompositions_type
 Type of container for many decompositions. More...
 
typedef decomposition_type::size_type size_type
 Type of decomposition's size. More...
 
- Public Types inherited from MassDecomposer< long unsigned int, unsigned int >
typedef long unsigned int value_type
 
typedef unsigned int decomposition_value_type
 
typedef std::vector< decomposition_value_typedecomposition_type
 
typedef std::vector< decomposition_typedecompositions_type
 

Public Member Functions

 IntegerMassDecomposer (const Weights &alphabet)
 
bool exist (value_type mass) override
 
decomposition_type getDecomposition (value_type mass) override
 
decompositions_type getAllDecompositions (value_type mass) override
 
decomposition_value_type getNumberOfDecompositions (value_type mass) override
 
- Public Member Functions inherited from MassDecomposer< long unsigned int, unsigned int >
virtual ~MassDecomposer ()
 
virtual bool exist (value_type mass)=0
 
virtual decomposition_type getDecomposition (value_type mass)=0
 
virtual decompositions_type getAllDecompositions (value_type mass)=0
 
virtual decomposition_value_type getNumberOfDecompositions (value_type mass)=0
 

Private Types

typedef std::vector< std::pair< size_type, decomposition_value_type > > witness_vector_type
 
typedef std::vector< value_typeresidues_table_row_type
 
typedef std::vector< residues_table_row_typeresidues_table_type
 

Private Member Functions

void fillExtendedResidueTable_ (const Weights &_alphabet, residues_table_row_type &_lcms, residues_table_row_type &_mass_in_lcms, const value_type _infty, witness_vector_type &_witness_vector, residues_table_type &_ertable)
 
void collectDecompositionsRecursively_ (value_type mass, size_type alphabetMassIndex, decomposition_type decomposition, decompositions_type &decompositionsStore)
 

Private Attributes

Weights alphabet_
 
residues_table_type ertable_
 
residues_table_row_type lcms_
 
residues_table_row_type mass_in_lcms_
 
value_type infty_
 
witness_vector_type witness_vector_
 

Detailed Description

template<typename ValueType = long unsigned int, typename DecompositionValueType = unsigned int>
class OpenMS::ims::IntegerMassDecomposer< ValueType, DecompositionValueType >

Implements MassDecomposer interface using algorithm and data structures described in paper "Efficient Mass Decomposition" S. Böcker, Z. Lipták, ACM SAC-BIO, 2004 doi:10.1145/1066677.1066715.

The main idea is instead of using the classical dynamic programming algorithm, store the residues of the smallest decomposable numbers for every modulo of the smallest alphabet mass.

Template Parameters
ValueTypeType of values to be decomposed.
DecompositionValueTypeType of decomposition elements.
Author
Anton Pervukhin Anton.nosp@m..Per.nosp@m.vukhi.nosp@m.n@Ce.nosp@m.BiTec.nosp@m..Uni.nosp@m.-Biel.nosp@m.efel.nosp@m.d.DE
Marcel Martin Marce.nosp@m.l.Ma.nosp@m.rtin@.nosp@m.CeBi.nosp@m.Tec.U.nosp@m.ni-B.nosp@m.ielef.nosp@m.eld..nosp@m.DE
Henner Sudek Henne.nosp@m.r.Su.nosp@m.dek@C.nosp@m.eBiT.nosp@m.ec.Un.nosp@m.i-Bi.nosp@m.elefe.nosp@m.ld.D.nosp@m.E

Member Typedef Documentation

◆ decomposition_type

typedef MassDecomposer<ValueType, DecompositionValueType>::decomposition_type decomposition_type

Type of decomposition.

◆ decomposition_value_type

typedef MassDecomposer<ValueType, DecompositionValueType>::decomposition_value_type decomposition_value_type

Type of decomposition value.

◆ decompositions_type

typedef MassDecomposer<ValueType, DecompositionValueType>::decompositions_type decompositions_type

Type of container for many decompositions.

◆ residues_table_row_type

typedef std::vector<value_type> residues_table_row_type
private

Type of rows of residues table.

◆ residues_table_type

typedef std::vector<residues_table_row_type> residues_table_type
private

Type of the residues table.

◆ size_type

typedef decomposition_type::size_type size_type

Type of decomposition's size.

◆ value_type

typedef MassDecomposer<ValueType, DecompositionValueType>::value_type value_type

Type of value to be decomposed.

◆ witness_vector_type

typedef std::vector<std::pair<size_type, decomposition_value_type> > witness_vector_type
private

Type of witness vector.

Constructor & Destructor Documentation

◆ IntegerMassDecomposer()

Member Function Documentation

◆ collectDecompositionsRecursively_()

void collectDecompositionsRecursively_ ( value_type  mass,
size_type  alphabetMassIndex,
decomposition_type  decomposition,
decompositions_type decompositionsStore 
)
private

Collects decompositions for mass by recursion.

Parameters
massMass to be decomposed.
alphabetMassIndexAn index of the mass in alphabet that is used on this step of recursion.
decompositionDecomposition which is calculated on this step of recursion.
decompositionsStoreContainer where decompositions are collected.

◆ exist()

bool exist ( value_type  mass)
override

Returns true if decomposition over the mass exists, otherwise - false.

Parameters
massMass to be decomposed.
Returns
true if decomposition over a given mass exists, otherwise - false.

◆ fillExtendedResidueTable_()

void fillExtendedResidueTable_ ( const Weights _alphabet,
residues_table_row_type _lcms,
residues_table_row_type _mass_in_lcms,
const value_type  _infty,
witness_vector_type _witness_vector,
residues_table_type _ertable 
)
private

◆ getAllDecompositions()

IntegerMassDecomposer< ValueType, DecompositionValueType >::decompositions_type getAllDecompositions ( value_type  mass)
override

Gets all possible decompositions for mass.

Parameters
massMass to be decomposed.
Returns
All possible decompositions for a given mass.

◆ getDecomposition()

IntegerMassDecomposer< ValueType, DecompositionValueType >::decomposition_type getDecomposition ( value_type  mass)
override

Gets one possible decomposition for mass.

Parameters
massMass to be decomposed.
Returns
One possible decomposition for a given mass.

◆ getNumberOfDecompositions()

IntegerMassDecomposer< ValueType, DecompositionValueType >::decomposition_value_type getNumberOfDecompositions ( value_type  mass)
override

Gets number of all possible decompositions for a given mass. Since using getAllDecomposition() the usage of this function could be consuming.

Parameters
massMass to be decomposed
Returns
number of decompositions for a given mass.

Gets number of all possible decompositions for a given mass. Since using getAllDecomposition() the usage of this function could be consuming.

Needs the mass to be decomposed and returns the number of decompositions for that mass.

Member Data Documentation

◆ alphabet_

Weights alphabet_
private

Weights over which the mass is to be decomposed.

◆ ertable_

residues_table_type ertable_
private

Table with the residues of the smallest decomposable numbers over every modulo of the smallest alphabet mass are stored. Corresponds to the Extended Residue Table in the paper.

Referenced by IntegerMassDecomposer< ValueType, DecompositionValueType >::IntegerMassDecomposer().

◆ infty_

value_type infty_
private

◆ lcms_

residues_table_row_type lcms_
private

List of the least common multiples. Corresponds to the lcm data structure in the paper.

Referenced by IntegerMassDecomposer< ValueType, DecompositionValueType >::IntegerMassDecomposer().

◆ mass_in_lcms_

residues_table_row_type mass_in_lcms_
private

List of the counters for the least common multiples that store the number how often the smallest alphabet mass fits into the corresponding least common multiple(lcm).

Referenced by IntegerMassDecomposer< ValueType, DecompositionValueType >::IntegerMassDecomposer().

◆ witness_vector_

witness_vector_type witness_vector_
private

List of the witnesses that is used to find one mass decomposition. Corresponds to the witness vector w in the paper.

Referenced by IntegerMassDecomposer< ValueType, DecompositionValueType >::IntegerMassDecomposer().