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;
        }
    }
}

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;
}

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

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

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

staticconstexprprivate

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