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.

typedef MassDecomposer< ValueType, DecompositionValueType >::decomposition_value_type	decomposition_value_type
	Type of decomposition value.

typedef MassDecomposer< ValueType, DecompositionValueType >::decomposition_type	decomposition_type
	Type of decomposition.

typedef MassDecomposer< ValueType, DecompositionValueType >::decompositions_type	decompositions_type
	Type of container for many decompositions.

typedef decomposition_type::size_type	size_type
	Type of decomposition's size.

Public Types inherited from MassDecomposer< ValueType, DecompositionValueType >
typedef ValueType	value_type

typedef DecompositionValueType	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< ValueType, DecompositionValueType >
virtual	~MassDecomposer ()

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

template<typename ValueType = long unsigned int, typename DecompositionValueType = unsigned int>

typedef MassDecomposer<ValueType,DecompositionValueType>::decomposition_type decomposition_type

Type of decomposition.

◆ decomposition_value_type

template<typename ValueType = long unsigned int, typename DecompositionValueType = unsigned int>

typedef MassDecomposer<ValueType,DecompositionValueType>::decomposition_value_type decomposition_value_type

Type of decomposition value.

◆ decompositions_type

template<typename ValueType = long unsigned int, typename DecompositionValueType = unsigned int>

typedef MassDecomposer<ValueType,DecompositionValueType>::decompositions_type decompositions_type

Type of container for many decompositions.

◆ residues_table_row_type

template<typename ValueType = long unsigned int, typename DecompositionValueType = unsigned int>

typedef std::vector<value_type> residues_table_row_type

private

Type of rows of residues table.

◆ residues_table_type

template<typename ValueType = long unsigned int, typename DecompositionValueType = unsigned int>

typedef std::vector<residues_table_row_type> residues_table_type

private

Type of the residues table.

◆ size_type

template<typename ValueType = long unsigned int, typename DecompositionValueType = unsigned int>

typedef decomposition_type::size_type size_type

Type of decomposition's size.

◆ value_type

template<typename ValueType = long unsigned int, typename DecompositionValueType = unsigned int>

typedef MassDecomposer<ValueType,DecompositionValueType>::value_type value_type

Type of value to be decomposed.

◆ witness_vector_type

template<typename ValueType = long unsigned int, typename DecompositionValueType = unsigned int>

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

private

Type of witness vector.

Constructor & Destructor Documentation

◆ IntegerMassDecomposer()

template<typename ValueType , typename DecompositionValueType >

IntegerMassDecomposer ( const Weights & alphabet )

explicit

Constructor with weights.

Parameters

[in] 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_()

template<typename ValueType , typename DecompositionValueType >

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

private

Collects decompositions for mass by recursion.

Parameters

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

◆ exist()

template<typename ValueType , typename DecompositionValueType >

bool exist ( value_type mass )

overridevirtual

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

Parameters

[in] mass Mass to be decomposed.

Returns: true if decomposition over a given mass exists, otherwise - false.

Implements MassDecomposer< ValueType, DecompositionValueType >.

◆ fillExtendedResidueTable_()

template<typename ValueType , typename DecompositionValueType >

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

template<typename ValueType , typename DecompositionValueType >

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

overridevirtual

Gets all possible decompositions for mass.

Parameters

[in] mass Mass to be decomposed.

Returns: All possible decompositions for a given mass.

Implements MassDecomposer< ValueType, DecompositionValueType >.

◆ getDecomposition()

template<typename ValueType , typename DecompositionValueType >

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

overridevirtual

Gets one possible decomposition for mass.

Parameters

[in] mass Mass to be decomposed.

Returns: One possible decomposition for a given mass.

Implements MassDecomposer< ValueType, DecompositionValueType >.

◆ getNumberOfDecompositions()

template<typename ValueType , typename DecompositionValueType >

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

overridevirtual

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

Parameters

[in] 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.

Implements MassDecomposer< ValueType, DecompositionValueType >.

Member Data Documentation

◆ alphabet_

template<typename ValueType = long unsigned int, typename DecompositionValueType = unsigned int>

Weights alphabet_

private

Weights over which the mass is to be decomposed.

◆ ertable_

template<typename ValueType = long unsigned int, typename DecompositionValueType = unsigned int>

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_

template<typename ValueType = long unsigned int, typename DecompositionValueType = unsigned int>

value_type infty_

private

Represents an infinite value.

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

◆ lcms_

template<typename ValueType = long unsigned int, typename DecompositionValueType = unsigned int>

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_

template<typename ValueType = long unsigned int, typename DecompositionValueType = unsigned int>

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_

template<typename ValueType = long unsigned int, typename DecompositionValueType = unsigned int>

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

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_