68 template <
typename ValueType =
long unsigned int,
69 typename DecompositionValueType =
unsigned int>
87 typedef typename decomposition_type::size_type
size_type;
203 template <
typename ValueType,
typename DecompositionValueType>
218 template <
typename ValueType,
typename DecompositionValueType>
224 if (_alphabet.
size() < 2)
232 _ertable.reserve(_alphabet.
size());
233 _ertable.assign(_alphabet.
size(), std::vector<value_type>(smallestMass, _infty));
241 _witnessVector.resize(smallestMass);
244 size_type it_inc = secondMass % smallestMass, witness = 1;
252 _ertable[1][it_i] = mass;
255 _witnessVector[it_i] = std::make_pair(witness, counter);
258 if (it_i >= _ertable[1].size())
260 it_i -= _ertable[1].size();
265 _lcms[1] = secondMass * smallestMass / tmp_d;
266 _mass_in_lcms[1] = smallestMass / tmp_d;
278 _lcms[i] = currentMass * smallestMass / d;
279 _mass_in_lcms[i] = smallestMass / d;
282 if (currentMass >= _ertable[i - 1][currentMass % smallestMass])
284 _ertable[i] = _ertable[i - 1];
297 size_type p_inc = currentMass % smallestMass;
306 for (
size_type m = smallestMass; m > 0; --m)
311 if (p >= smallestMass)
315 if (n > prev_column[p])
322 _witnessVector[p] = std::make_pair(i, local_counter);
334 size_type cur = currentMass % smallestMass;
338 std::vector<decomposition_value_type> counters(smallestMass);
343 cur_column[j] = prev_column[j];
347 for (
size_type m = smallestMass / d; m > 1; m--)
354 if (cur_column[prev] + currentMass > prev_column[cur])
356 cur_column[cur] = prev_column[cur];
361 cur_column[cur] = cur_column[prev] + currentMass;
362 _witnessVector[cur] = std::make_pair(i, counters[cur]);
373 if (cur >= smallestMass)
389 if (cur_column[prev] + currentMass < cur_column[cur])
391 cur_column[cur] = cur_column[prev] + currentMass;
393 _witnessVector[cur] = std::make_pair(i, counters[cur]);
406 if (cur >= smallestMass)
416 template <
typename ValueType,
typename DecompositionValueType>
421 value_type residue = ertable_.back().at(mass % alphabet_.getWeight(0));
422 return residue != infty_ && mass >= residue;
425 template <
typename ValueType,
typename DecompositionValueType>
431 if (!this->exist(mass))
433 return decomposition;
436 decomposition.reserve(alphabet_.size());
437 decomposition.resize(alphabet_.size());
444 ((mass - m) / alphabet_.getWeight(0));
448 size_type i = witness_vector_.at(r).first;
450 decomposition.at(i) += j;
451 if (m < j * alphabet_.getWeight(i))
455 m -= j * alphabet_.getWeight(i);
456 r = m % alphabet_.getWeight(0);
458 return decomposition;
461 template <
typename ValueType,
typename DecompositionValueType>
467 collectDecompositionsRecursively_(mass, alphabet_.size() - 1, decomposition, decompositionsStore);
468 return decompositionsStore;
471 template <
typename ValueType,
typename DecompositionValueType>
476 if (alphabetMassIndex == 0)
478 value_type numberOfMasses0 = mass / alphabet_.getWeight(0);
479 if (numberOfMasses0 * alphabet_.getWeight(0) == mass)
482 decompositionsStore.push_back(decomposition);
489 const value_type lcm = lcms_[alphabetMassIndex];
490 const value_type mass_in_lcm = mass_in_lcms_[alphabetMassIndex];
492 value_type mass_mod_alphabet0 = mass % alphabet_.getWeight(0);
493 const value_type mass_mod_decrement = alphabet_.getWeight(alphabetMassIndex) % alphabet_.getWeight(0);
502 if (mass < i * alphabet_.getWeight(alphabetMassIndex))
508 value_type r = ertable_[alphabetMassIndex - 1][mass_mod_alphabet0];
513 for (
value_type m = mass - i * alphabet_.getWeight(alphabetMassIndex); m >= r; m -= lcm)
518 collectDecompositionsRecursively_(m, alphabetMassIndex - 1, decomposition, decompositionsStore);
519 decomposition[alphabetMassIndex] += mass_in_lcm;
529 if (mass_mod_alphabet0 < mass_mod_decrement)
531 mass_mod_alphabet0 += alphabet_.getWeight(0) - mass_mod_decrement;
535 mass_mod_alphabet0 -= mass_mod_decrement;
549 template <
typename ValueType,
typename DecompositionValueType>
551 DecompositionValueType>::getNumberOfDecompositions(
value_type mass)
IntegerMassDecomposer(const Weights &alphabet)
Definition: IntegerMassDecomposer.h:204
std::vector< residues_table_row_type > residues_table_type
Definition: IntegerMassDecomposer.h:145
value_type infty_
Definition: IntegerMassDecomposer.h:175
ValueType value_type
Definition: MassDecomposer.h:73
Represents a set of weights (double values and scaled with a certain precision their integer counterp...
Definition: Weights.h:67
std::vector< decomposition_value_type > decomposition_type
Definition: MassDecomposer.h:83
residues_table_row_type lcms_
Definition: IntegerMassDecomposer.h:163
Main OpenMS namespace.
Definition: FeatureDeconvolution.h:46
std::vector< std::pair< size_type, decomposition_value_type > > witness_vector_type
Definition: IntegerMassDecomposer.h:135
Implements MassDecomposer interface using algorithm and data structures described in paper "Efficient...
Definition: IntegerMassDecomposer.h:70
decomposition_type::size_type size_type
Type of decomposition's size.
Definition: IntegerMassDecomposer.h:87
std::vector< decomposition_type > decompositions_type
Definition: MassDecomposer.h:88
decomposition_type getDecomposition(value_type mass) override
Definition: IntegerMassDecomposer.h:427
decompositions_type getAllDecompositions(value_type mass) override
Definition: IntegerMassDecomposer.h:463
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)
Definition: IntegerMassDecomposer.h:219
MassDecomposer< ValueType, DecompositionValueType >::decomposition_value_type decomposition_value_type
Type of decomposition value.
Definition: IntegerMassDecomposer.h:78
bool exist(value_type mass) override
Definition: IntegerMassDecomposer.h:418
weight_type getWeight(size_type i) const
Definition: Weights.h:135
T gcd(T a, T b)
Returns the greatest common divisor (gcd) of two numbers by applying the Euclidean algorithm...
Definition: MathFunctions.h:169
std::vector< value_type > residues_table_row_type
Definition: IntegerMassDecomposer.h:140
decomposition_value_type getNumberOfDecompositions(value_type mass) override
Definition: IntegerMassDecomposer.h:551
void collectDecompositionsRecursively_(value_type mass, size_type alphabetMassIndex, decomposition_type decomposition, decompositions_type &decompositionsStore)
Definition: IntegerMassDecomposer.h:473
An interface to handle decomposing of integer values/masses over a set of integer weights (alphabet)...
Definition: MassDecomposer.h:67
residues_table_type ertable_
Definition: IntegerMassDecomposer.h:157
residues_table_row_type mass_in_lcms_
Definition: IntegerMassDecomposer.h:170
size_type size() const
Definition: Weights.h:124
DecompositionValueType decomposition_value_type
Definition: MassDecomposer.h:78
Weights alphabet_
Definition: IntegerMassDecomposer.h:150
MassDecomposer< ValueType, DecompositionValueType >::decomposition_type decomposition_type
Type of decomposition.
Definition: IntegerMassDecomposer.h:81
MassDecomposer< ValueType, DecompositionValueType >::decompositions_type decompositions_type
Type of container for many decompositions.
Definition: IntegerMassDecomposer.h:84
witness_vector_type witness_vector_
Definition: IntegerMassDecomposer.h:181
MassDecomposer< ValueType, DecompositionValueType >::value_type value_type
Type of value to be decomposed.
Definition: IntegerMassDecomposer.h:75