Loading...
Searching...
No Matches
pappso::spectree::SpecTree Class Reference

`#include <spectree.h>`

## Classes

struct | SpecTreeNode
struct | MapSimilarityCountElement
struct | MapSimilarityCount

## Public Member Functions

| SpecTree (const BucketClustering &bucket_clustering)
virtual | ~SpecTree ()
QString | toString () const
const std::vector< std::size_t > & | getSpectrumFirstNodeIndex () const
| get the adress map of sepctrum index and their first node index
void | xtract (UiMonitorInterface &monitor, SpecXtractInterface &spec_xtract, std::size_t minimum_count, std::size_t cart_id_range_max, std::size_t cart_id_range_min, std::size_t target_cart_id_max, std::size_t target_cart_id_min) const
std::size_t | extractSpectrumPairSimilarityCount (std::size_t spectrum_a_index, std::size_t spectrum_b_index) const
| get the number of common component for a pair of spectrum

## Private Member Functions

void | addNewNode (const SpecTreeNode &node)
void | manageSideAccess (std::vector< std::size_t > &spectrumLastNodeIndex)
void | walkBackInBranchFromNode (const SpecTree::SpecTreeNode &start_node, MapSimilarityCount &map_count, std::size_t minimum_count, std::size_t target_cart_id_max, std::size_t target_cart_id_min) const
std::size_t | walkBackInBranchFromNodeToTarget (const SpecTree::SpecTreeNode &start_node, std::size_t spectrum_index_target) const
void | extractSpectrumSimilarityCount (MapSimilarityCount &map_count, std::size_t minimum_count, std::size_t spectrum_index, std::size_t target_cart_id_max, std::size_t target_cart_id_min) const
| get a map of similarities for a given spectrum index

## Private Attributes

std::vector< SpecTreeNode > | m_nodeList
std::vector< std::size_t > | m_spectrumFirstNodeIndex

## Static Private Attributes

static constexpr std::size_t | index_not_defined {std::numeric_limits<std::size_t>::max()}

## Detailed Description

Todo
  write docs

Definition at line 52 of file spectree.h.

## Constructor & Destructor Documentation

## SpecTree()

pappso::spectree::SpecTree::SpecTree | ( | const BucketClustering & | bucket_clustering | ) |

Build a SpecTree with BucketClustering

Definition at line 48 of file spectree.cpp.

{
std::vector<Bucket> bins = bucket_clustering.asSortedList();
SpecTreeNode node;
node.value = bins[0].getCartList().at(0);
node.count = 1;
qDebug() << node.value;
// Specific processing for the first bucket : the first node and all its
// children are added in SpecTrees and the transversal accessor is updated
// accordingly
std::vector<std::size_t> spectrumLastNodeIndex;
spectrumLastNodeIndex.resize(bucket_clustering.getItemCartCount(), index_not_defined);
m_spectrumFirstNodeIndex.resize(bucket_clustering.getItemCartCount(), index_not_defined);
m_spectrumFirstNodeIndex[node.value] = m_nodeList.size() - 1;
m_nodeList.push_back(node);
manageSideAccess(spectrumLastNodeIndex);
for(std::size_t cpt = 1; cpt < bins[0].size(); ++cpt)
{
node.parentIndex = m_nodeList.size() - 1;
node.nextIndex = index_not_defined;
node.value = bins[0].getCartList().at(cpt);
node.count = 1;
m_nodeList.push_back(node);
manageSideAccess(spectrumLastNodeIndex);
}
qDebug();
// For the rest of the buckets, we increment the node counter in prefix
// common parts without creating new nodes. Once out of the prefix common
// part, new nodes are created similarily as they were for the first bucket.
for(std::size_t bins_index = 1; bins_index < bins.size(); ++bins_index)
{
qDebug() << "bins_index=" << bins_index;
std::size_t pos = 0;
bool common = false;
std::size_t parentNode = index_not_defined;
std::size_t previous_bin_size = bins[bins_index - 1].size();
// detection of a common first element
if(pos < previous_bin_size)
{
if(bins[bins_index].getCartList().at(pos) == bins[bins_index - 1].getCartList().at(pos))
{
common = true;
}
}
// insertion procedure for a common prefix part insertion : we go
// through existing nodes and increment their counter value by one
while(common)
{
qDebug() << "common pos=" << pos;
std::size_t spectrum_index = bins[bins_index].getCartList().at(pos);
qDebug() << "common spectrum_index=" << spectrum_index;
std::size_t tempNodeIndex = spectrumLastNodeIndex[spectrum_index];
qDebug() << "common tempNodeIndex=" << tempNodeIndex;
m_nodeList[tempNodeIndex].count++;
// checking on the prefix common part persistence conditions ; if
// not valid, we are not in a common prefix part anymore for the
// currently inserted bucket
if((previous_bin_size - 1 == pos) || (bins[bins_index].size() - 1 == pos))
{
qDebug() << "last one";
common = false;
}
else
{
qDebug() << "bins[bins_index - 1].getSpectrumIndex(pos + 1)="
<< bins[bins_index - 1].getCartList().at(pos + 1);
qDebug() << "bins[bins_index].getSpectrumIndex(pos + 1)="
<< bins[bins_index].getCartList().at(pos + 1);
if(bins[bins_index - 1].getCartList().at(pos + 1) !=
bins[bins_index].getCartList().at(pos + 1))
{
common = false;
}
}
parentNode = tempNodeIndex;
++pos;
qDebug() << "common=" << common;
}
qDebug();
// insertion procedure for all the remaining nodes not in the prefix
// common part : we create new nodes with a counter value of 1 and
// update the transversal accessor and last inserted node list
while(pos < bins[bins_index].size())
{
std::size_t spectrum_index = bins[bins_index].getCartList().at(pos);
node.parentIndex = parentNode;
node.nextIndex = index_not_defined;
node.value = spectrum_index;
node.count = 1;
m_nodeList.push_back(node);
manageSideAccess(spectrumLastNodeIndex);
parentNode = m_nodeList.size() - 1;
++pos;
}
}
}
pappso::spectree::SpecTree::m_nodeList
std::vector< SpecTreeNode > m_nodeList
Definition spectree.h:169
pappso::spectree::SpecTree::index_not_defined
static constexpr std::size_t index_not_defined
Definition spectree.h:117
pappso::spectree::SpecTree::m_spectrumFirstNodeIndex
std::vector< std::size_t > m_spectrumFirstNodeIndex
Definition spectree.h:170
pappso::spectree::SpecTree::manageSideAccess
void manageSideAccess(std::vector< std::size_t > &spectrumLastNodeIndex)
Definition spectree.cpp:170
pappso::spectree::SpecTree::SpecTreeNode
Definition spectree.h:119
pappso::spectree::SpecTree::SpecTreeNode::value
std::size_t value
Definition spectree.h:122

References pappso::spectree::BucketClustering::asSortedList(), pappso::spectree::SpecTree::SpecTreeNode::count, pappso::spectree::BucketClustering::getItemCartCount(), index_not_defined, m_nodeList, m_spectrumFirstNodeIndex, manageSideAccess(), pappso::spectree::SpecTree::SpecTreeNode::nextIndex, pappso::spectree::SpecTree::SpecTreeNode::parentIndex, and pappso::spectree::SpecTree::SpecTreeNode::value.

## ~SpecTree()

pappso::spectree::SpecTree::~SpecTree | ( |  | ) |

virtual

Destructor

Definition at line 159 of file spectree.cpp.

{
}

## Member Function Documentation

## addNewNode()

void pappso::spectree::SpecTree::addNewNode | ( | const SpecTreeNode & | node | ) |

private

Definition at line 164 of file spectree.cpp.

{
m_nodeList.push_back(node);
}

References m_nodeList.

## extractSpectrumPairSimilarityCount()

std::size_t pappso::spectree::SpecTree::extractSpectrumPairSimilarityCount | ( | std::size_t | spectrum_a_index,
|  | std::size_t | spectrum_b_index ) const

get the number of common component for a pair of spectrum

Parameters

  spectrum_a_index | the first spectrum index
  spectrum_b_index | the second spectrum index

Returns
  integer the number of common component between spectrum

Definition at line 418 of file spectree.cpp.

{
if(spectrum_a_index > spectrum_b_index)
std::swap(spectrum_a_index, spectrum_b_index);
std::size_t count_target = 0;
if(spectrum_b_index < m_spectrumFirstNodeIndex.size())
{
std::size_t node_index = m_spectrumFirstNodeIndex[spectrum_b_index];
while(node_index != index_not_defined)
{
qDebug() << "node_index=" << node_index;
const SpecTreeNode &current_node = m_nodeList[node_index];
// go back in the tree branch from the current_node
count_target += walkBackInBranchFromNodeToTarget(current_node, spectrum_a_index);
node_index = current_node.nextIndex;
}
}
else
{
throw pappso::ExceptionOutOfRange(
QObject::tr("spectrum_index %1 out of range (spectrum_index max size=%2)")
.arg(spectrum_b_index)
.arg(m_spectrumFirstNodeIndex.size()));
}
return count_target;
}
pappso::spectree::SpecTree::walkBackInBranchFromNodeToTarget
std::size_t walkBackInBranchFromNodeToTarget(const SpecTree::SpecTreeNode &start_node, std::size_t spectrum_index_target) const
Definition spectree.cpp:361

References index_not_defined, m_nodeList, m_spectrumFirstNodeIndex, pappso::spectree::SpecTree::SpecTreeNode::nextIndex, and walkBackInBranchFromNodeToTarget().

## extractSpectrumSimilarityCount()

void pappso::spectree::SpecTree::extractSpectrumSimilarityCount | ( | MapSimilarityCount & | map_count,
|  | std::size_t | minimum_count,
|  | std::size_t | spectrum_index,
|  | std::size_t | target_cart_id_max,
|  | std::size_t | target_cart_id_min ) const

private

get a map of similarities for a given spectrum index

this function can only retrieve spectrum index map lower than the spectrum index given in the parameters (check original publication for details)

Parameters

  spectrum_index | the spectrum index to retrieve similarities
  spectrum_index_lower_limit | lower spectrum index limit to save CPU (do not use it if you want a full similarity map)

Returns
  map of spectrum_index keys containing the corresponding count value (similarity) for the targeted spectrum index

Extraction of the similarities above a given threshold between a given spectrum and all other spectra higher located in SpecTrees.

Parameters

  tree_indices | SpecTrees the data has to be extracted from
  spectrum_index | The spectrum with ated in SpecTrees.
  tree_indices | SpecTrees the data has to be extracted from
  spectrum_index | The spectrum with which we want to extract similarities
  minimum_count | The threshold to use for the extraction

Since
  0.1

Definition at line 393 of file spectree.cpp.

{
qDebug() << " spectrum_index=" << spectrum_index;
// sOne;
// we position the current node at the first occurence of the spectrum in
// the transversal accessor and initialise variablethresholds accordingly
std::size_t node_index = m_spectrumFirstNodeIndex[spectrum_index];
while(node_index != index_not_defined)
{
qDebug() << "node_index=" << node_index;
const SpecTreeNode &current_node = m_nodeList[node_index];
// go back in the tree branch from the current_node
walkBackInBranchFromNode(
current_node, map_count, minimum_count, target_cart_id_max, target_cart_id_min);
node_index = current_node.nextIndex;
}
qDebug();
}
pappso::spectree::SpecTree::walkBackInBranchFromNode
void walkBackInBranchFromNode(const SpecTree::SpecTreeNode &start_node, MapSimilarityCount &map_count, std::size_t minimum_count, std::size_t target_cart_id_max, std::size_t target_cart_id_min) const
Definition spectree.cpp:307

References index_not_defined, m_nodeList, m_spectrumFirstNodeIndex, pappso::spectree::SpecTree::SpecTreeNode::nextIndex, and walkBackInBranchFromNode().

Referenced by xtract().

## getSpectrumFirstNodeIndex()

const std::vector< std::size_t > & pappso::spectree::SpecTree::getSpectrumFirstNodeIndex | ( |  | ) | const

get the adress map of sepctrum index and their first node index

convenience function intended for testing

Returns
  vector of the size of max spectrum index containing list of first node index

Definition at line 219 of file spectree.cpp.

{
return m_spectrumFirstNodeIndex;
}

References m_spectrumFirstNodeIndex.

## manageSideAccess()

void pappso::spectree::SpecTree::manageSideAccess | ( | std::vector< std::size_t > & | spectrumLastNodeIndex | ) |

private

Definition at line 170 of file spectree.cpp.

{
auto spectrum_index = m_nodeList.back().value;
auto node_position = m_nodeList.size() - 1;
if(m_spectrumFirstNodeIndex[spectrum_index] == index_not_defined)
{
// first occurence of this spectrum
m_spectrumFirstNodeIndex[spectrum_index] = node_position;
spectrumLastNodeIndex[spectrum_index] = node_position;
}
else
{
if(spectrumLastNodeIndex[spectrum_index] == node_position)
{
}
else
{
m_nodeList[spectrumLastNodeIndex[spectrum_index]].nextIndex = node_position;
spectrumLastNodeIndex[spectrum_index] = node_position;
}
}
}

References index_not_defined, m_nodeList, and m_spectrumFirstNodeIndex.

Referenced by SpecTree().

## toString()

QString pappso::spectree::SpecTree::toString | ( |  | ) | const

Definition at line 194 of file spectree.cpp.

{
QString node_str("node|spectrum|parent|next|count|\n");
std::size_t i = 0;
for(auto node : m_nodeList)
{
int parent = -1;
if(node.parentIndex < index_not_defined)
parent = node.parentIndex;
int next = -1;
if(node.nextIndex < index_not_defined)
next = node.nextIndex;
node_str.append(QString("node_%1|%2|%3|%4|%5end\n")
.arg(i)
.arg(node.value)
.arg(parent)
.arg(next)
.arg(node.count));
i++;
}
return node_str;
}

References index_not_defined, and m_nodeList.

## walkBackInBranchFromNode()

void pappso::spectree::SpecTree::walkBackInBranchFromNode | ( | const SpecTree::SpecTreeNode & | start_node,
|  | MapSimilarityCount & | map_count,
|  | std::size_t | minimum_count,
|  | std::size_t | target_cart_id_max,
|  | std::size_t | target_cart_id_min ) const

private

Definition at line 307 of file spectree.cpp.

{
std::size_t parent_id = start_node.parentIndex;
qDebug() << " start node spectrum=" << start_node.value << " parent_id=" << parent_id
<< " init_count=" << start_node.count << " minimum_count=" << minimum_count
<< " target_cart_id_min=" << target_cart_id_min;
while(parent_id != index_not_defined)
{
// next_node :
const SpecTree::SpecTreeNode &current_node = m_nodeList[parent_id];
if(current_node.value < target_cart_id_min)
break;
if(current_node.value <= target_cart_id_max)
{
auto &map_id_count = map_count.map_id_count[current_node.value];
if(map_id_count.lastWitness == start_node.value)
{
map_id_count.count += start_node.count;
// if at one time, a similarity exceeds the threshold value for
// the first time, it is written into the proper stack
if((map_id_count.count >= minimum_count) && (map_id_count.aboveThreshold == false))
{
map_id_count.aboveThreshold = true;
map_count.aboveThreshold.push_back(current_node.value);
}
}
else
{
map_id_count.lastWitness = start_node.value;
map_id_count.count = start_node.count;
map_id_count.aboveThreshold = false;
// if at one time, a similarity exceeds the threshold value for
// the first time, it is written into the proper stack
if(map_id_count.count >= minimum_count)
{
map_id_count.aboveThreshold = true;
map_count.aboveThreshold.push_back(current_node.value);
}
map_count.keys.push_back(current_node.value);
}
}
parent_id = current_node.parentIndex;
}
}

References pappso::spectree::SpecTree::MapSimilarityCount::aboveThreshold, pappso::spectree::SpecTree::SpecTreeNode::count, index_not_defined, pappso::spectree::SpecTree::MapSimilarityCount::keys, m_nodeList, pappso::spectree::SpecTree::MapSimilarityCount::map_id_count, pappso::spectree::SpecTree::SpecTreeNode::parentIndex, and pappso::spectree::SpecTree::SpecTreeNode::value.

Referenced by extractSpectrumSimilarityCount().

## walkBackInBranchFromNodeToTarget()

std::size_t pappso::spectree::SpecTree::walkBackInBranchFromNodeToTarget | ( | const SpecTree::SpecTreeNode & | start_node,
|  | std::size_t | spectrum_index_target ) const

private

Definition at line 361 of file spectree.cpp.

{
std::size_t parent_id = start_node.parentIndex;
while(parent_id != index_not_defined)
{
// next_node :
const SpecTree::SpecTreeNode &current_node = m_nodeList[parent_id];
if(current_node.value < spectrum_index_target)
return 0;
if(current_node.value == spectrum_index_target)
return start_node.count;
parent_id = current_node.parentIndex;
}
return 0;
}

References pappso::spectree::SpecTree::SpecTreeNode::count, index_not_defined, m_nodeList, pappso::spectree::SpecTree::SpecTreeNode::parentIndex, and pappso::spectree::SpecTree::SpecTreeNode::value.

Referenced by extractSpectrumPairSimilarityCount().

## xtract()

void pappso::spectree::SpecTree::xtract | ( | UiMonitorInterface & | monitor,
|  | SpecXtractInterface & | spec_xtract,
|  | std::size_t | minimum_count,
|  | std::size_t | cart_id_range_max,
|  | std::size_t | cart_id_range_min,
|  | std::size_t | target_cart_id_max,
|  | std::size_t | target_cart_id_min ) const

Extract all similarities above a threshold value between all spectra from the deepest one up to the given limit using the predefined extraction algorithm. The results are stored in the mentionned reporter.

Performs the extraction of the similarities above a given threshold for all spectra between the deepest one and a given index in the transversal accessor. The extracted pairs are feed to a shifter to try to improve the spectrum identification. Afterwards, the retained results are written to the given reporter. This extraction step represents most of SpecOMS execution time. Note: This function heavily evolved through the development process to match new needs, it became clumsy and heavy. A clean refactor might be appropriate.

Parameters

  monitor | progress monitor, indicates progression in spectree
  spec_xtract | report results of similarities to the user (write in file or consolidate)
  cart_id_range_max | The position in the transversal accessor from which the similarities must be reported (item cart id)
  cart_id_range_min | The position in the transversal accessor up to which the similarities must be reported (item cart id)
  target_cart_id_max | targeted item cart id relevant for comparison
  target_cart_id_min | targeted item cart id relevant for comparison

Definition at line 225 of file spectree.cpp.

{
if(cart_id_range_max < cart_id_range_min)
{
std::swap(cart_id_range_max, cart_id_range_min);
}
if(cart_id_range_max < m_spectrumFirstNodeIndex.size())
{
monitor.setStatus(QObject::tr("starting SpecXtract operation"));
MapSimilarityCount map_count;
map_count.map_id_count.resize(cart_id_range_max);
// initialisation of the structure to store the compared pairs
// int[][] results = new int[m_count][3];
// int count = 0;
// iteration on the transversal accessor starting from the deepest spetrum
// and climbing up to limit
std::size_t spectra1 = cart_id_range_max;
monitor.setTotalSteps(cart_id_range_max - cart_id_range_min);
while(true)
{
if(monitor.shouldIstop())
{
throw pappso::ExceptionInterrupted(QObject::tr("SpecXtract job stopped"));
}
qDebug() << "spectra1=" << spectra1;
spec_xtract.beginItemCartExtraction(spectra1);
monitor.count();
// System.out.println(start);
map_count.keys.clear();
map_count.aboveThreshold.clear();
extractSpectrumSimilarityCount(
map_count, minimum_count, spectra1, target_cart_id_max, target_cart_id_min);
qDebug() << "spectra1=" << spectra1
<< " map_count.aboveThreshold.size()=" << map_count.aboveThreshold.size()
<< " map_count.keys.size()=" << map_count.keys.size();
for(std::size_t spectra2 : map_count.aboveThreshold)
{
// std::size_t spectra2 = *it;
qDebug() << "spectra2=" << spectra2;
// std::size_t total_extracted_count =
// map_count.map_id_count.at(spectra2);
spec_xtract.reportSimilarity(
spectra1, spectra2, map_count.map_id_count.at(spectra2).count);
}
spec_xtract.endItemCartExtraction(spectra1);
// monitor.count();
if(spectra1 == cart_id_range_min)
break;
spectra1--;
}
}
else
{
throw pappso::ExceptionOutOfRange(
QObject::tr("item cart index %1 out of range (item cart id max size=%2)")
.arg(cart_id_range_max)
.arg(m_spectrumFirstNodeIndex.size()));
}
qDebug();
}
pappso::spectree::SpecTree::extractSpectrumSimilarityCount
void extractSpectrumSimilarityCount(MapSimilarityCount &map_count, std::size_t minimum_count, std::size_t spectrum_index, std::size_t target_cart_id_max, std::size_t target_cart_id_min) const
get a map of similarities for a given spectrum index
Definition spectree.cpp:393
pappso::spectree::SpecTree::MapSimilarityCount
Definition spectree.h:133
pappso::spectree::SpecTree::MapSimilarityCount::map_id_count
std::vector< MapSimilarityCountElement > map_id_count
Definition spectree.h:136

References pappso::spectree::SpecTree::MapSimilarityCount::aboveThreshold, pappso::spectree::SpecXtractInterface::beginItemCartExtraction(), pappso::UiMonitorInterface::count(), pappso::spectree::SpecXtractInterface::endItemCartExtraction(), extractSpectrumSimilarityCount(), pappso::spectree::SpecTree::MapSimilarityCount::keys, m_spectrumFirstNodeIndex, pappso::spectree::SpecTree::MapSimilarityCount::map_id_count, pappso::spectree::SpecXtractInterface::reportSimilarity(), pappso::UiMonitorInterface::setStatus(), pappso::UiMonitorInterface::setTotalSteps(), and pappso::UiMonitorInterface::shouldIstop().

## Member Data Documentation

## index_not_defined

std::size_t pappso::spectree::SpecTree::index_not_defined {std::numeric_limits<std::size_t>::max()}

static constexpr private

Definition at line 117 of file spectree.h.

{std::numeric_limits<std::size_t>::max()};

Referenced by SpecTree(), extractSpectrumPairSimilarityCount(), extractSpectrumSimilarityCount(), manageSideAccess(), toString(), walkBackInBranchFromNode(), and walkBackInBranchFromNodeToTarget().

## m_nodeList

std::vector<SpecTreeNode> pappso::spectree::SpecTree::m_nodeList

private

Definition at line 169 of file spectree.h.

Referenced by SpecTree(), addNewNode(), extractSpectrumPairSimilarityCount(), extractSpectrumSimilarityCount(), manageSideAccess(), toString(), walkBackInBranchFromNode(), and walkBackInBranchFromNodeToTarget().

## m_spectrumFirstNodeIndex

std::vector<std::size_t> pappso::spectree::SpecTree::m_spectrumFirstNodeIndex

private

Definition at line 170 of file spectree.h.

Referenced by SpecTree(), extractSpectrumPairSimilarityCount(), extractSpectrumSimilarityCount(), getSpectrumFirstNodeIndex(), manageSideAccess(), and xtract().

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

- pappsomspp/core/processing/spectree/spectree.h
- pappsomspp/core/processing/spectree/spectree.cpp