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_type >	decomposition_type

typedef std::vector< decomposition_type >	decompositions_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_type >	residues_table_row_type

typedef std::vector< residues_table_row_type >	residues_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

ValueType	Type of values to be decomposed.
DecompositionValueType	Type 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()

IntegerMassDecomposer ( const Weights & alphabet )

explicit

Constructor with weights.

Parameters

alphabet Weights over which masses to be decomposed.

References IntegerMassDecomposer< ValueType, DecompositionValueType >::ertable_, IntegerMassDecomposer< ValueType, DecompositionValueType >::fillExtendedResidueTable_(), Weights::getWeight(), IntegerMassDecomposer< ValueType, DecompositionValueType >::infty_, IntegerMassDecomposer< ValueType, DecompositionValueType >::lcms_, IntegerMassDecomposer< ValueType, DecompositionValueType >::mass_in_lcms_, Weights::size(), and IntegerMassDecomposer< ValueType, DecompositionValueType >::witness_vector_.

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

mass	Mass to be decomposed.
alphabetMassIndex	An index of the mass in alphabet that is used on this step of recursion.
decomposition	Decomposition which is calculated on this step of recursion.
decompositionsStore	Container where decompositions are collected.

◆ exist()

bool exist ( value_type mass )

override

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

Parameters

mass	Mass 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

Fills the extended residues table.

References OpenMS::Math::gcd(), Weights::getWeight(), and Weights::size().

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

◆ getAllDecompositions()

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

override

Gets all possible decompositions for mass.

Parameters

mass	Mass 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

mass	Mass 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

mass	Mass 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

Represents an infinite value.

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

◆ 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().

Public Types

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

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

Member Typedef Documentation

◆ decomposition_type

◆ decomposition_value_type

◆ decompositions_type

◆ residues_table_row_type

◆ residues_table_type

◆ size_type

◆ value_type

◆ witness_vector_type

Constructor & Destructor Documentation

◆ IntegerMassDecomposer()

Member Function Documentation

◆ collectDecompositionsRecursively_()

◆ exist()

◆ fillExtendedResidueTable_()

◆ getAllDecompositions()

◆ getDecomposition()

◆ getNumberOfDecompositions()

Member Data Documentation

◆ alphabet_

◆ ertable_

◆ infty_

◆ lcms_

◆ mass_in_lcms_

◆ witness_vector_

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