This abstract class serves as a base class for all implementations of track processors. More...

#include <QuadTreeProcessor.h>

Public Types
using	Item = QuadTreeItem<AData>
	The QuadTree will only see items of this type.

using	QuadTree = QuadTreeNode<AX, AY, Item>
	The used QuadTree.

using	XSpan = typename QuadTree::XSpan
	This pair describes the span in X for a node.

using	YSpan = typename QuadTree::YSpan
	This pair describes the span in Y for a node.

using	XYSpans = std::pair<XSpan, YSpan>
	This pair of spans describes the span of a node.

using	QuadTreeChildren = typename QuadTree::Children
	Alias for the QuadTree Children.

using	CandidateReceiver = std::function<void(const std::vector<AData>&, QuadTree)>
	This lambda function can be used for postprocessing.

Public Member Functions
	QuadTreeProcessor (int lastLevel, int seedLevel, const XYSpans &xySpans, bool debugOutput=false)
	Constructor is very simple.

virtual	~QuadTreeProcessor ()
	Destructor deletes the quad tree.

void	clear ()
	Delete all the QuadTreeItems in the tree and clear the tree.

void	seed (const std::vector< AData * > &datas)
	Fill in the items in the given vector.

std::vector< AData * >	getAssignedItems ()
	Get items that have been assigned to the seed level The returned elements are unique even if items are assigned multiple times.

void	fill (const CandidateReceiver &candidateReceiver, int nHitsThreshold)
	Start filling the already created tree.

void	fill (const CandidateReceiver &candidateReceiver, int nHitsThreshold, float yLimit)
	Fill vector of QuadTree instances with hits.

virtual void	afterFillDebugHook (QuadTreeChildren &children)
	Override that function if you want to receive debug output whenever the children of a node are filled the first time Maybe you want to make some nice plots or statistics.

const std::map< std::pair< AX, AY >, std::vector< Item * > > &	getDebugInformation () const
	Return the debug information if collected.

Protected Member Functions
virtual XYSpans	createChild (QuadTree *node, int iX, int iY) const
	Implement that function if you want to provide a new processor.

virtual bool	isInNode (QuadTree node, AData item) const =0
	Implement that function if you want to provide a new processor.

virtual void	insertItemsInNodes (const std::vector< QuadTree * > &nodes, const std::vector< Item * > &items)
	Insert each of the given items into every one of the given nodes it belongs to.

virtual bool	isLeaf (QuadTree *node) const
	Function which checks if given node is leaf Implemented as virtual to keep possibility of changing lastLevel values depending on region is phase-space (i.e.

int	getLastLevel () const
	Return the parameter last level.

Protected Attributes
std::unique_ptr< QuadTree >	m_quadTree
	The quad tree we work with.

std::deque< Item >	m_items
	Storage space for the items that are referenced by the quad tree nodes.

std::vector< Item * >	m_itemPtrs
	Reusable buffer with pointers to all items - used to seed the tree.

std::vector< QuadTree * >	m_childPtrs
	Reusable buffer with pointers to the children of the node currently being filled.

std::vector< QuadTree * >	m_seededTrees
	Vector of QuadTrees QuadTree instances (which are filled in the vector) cover the whole Legendre phase-space; each instance is processes independently.

Private Member Functions
void	fillGivenTree (QuadTree *node, const CandidateReceiver &candidateReceiver, int nItemsThreshold, AY yLimit)
	Internal function to do the real quad tree search: fill the nodes, check which of the n*m bins we need to process further and go one level deeper.

void	createChildren (QuadTree *node, QuadTreeChildren &m_children) const
	Creates the sub node of a given node.

void	fillChildren (QuadTree node, const std::vector< Item > &items)
	This function is called by fillGivenTree and fills the items into the corresponding children.

Static Private Member Functions
static void	callResultFunction (QuadTree *node, const CandidateReceiver &candidateReceiver)
	When a node is accepted as a result, we extract a vector with the items (back transformed to AData*) and pass it together with the result node to the candidate receiver function.

Private Attributes
int	m_lastLevel
	The last level to be filled.

int	m_seedLevel
	The first level to be filled, effectively skip forward to this higher granularity level.

bool	m_debugOutput
	A flag to control the creation of the debug output.

std::map< std::pair< AX, AY >, std::vector< Item * > >	m_debugOutputMap
	The calculated debug map.

Static Private Attributes
static const int	c_maxNChildren = 16
	Upper bound on the number of children of a node - they are kept on the stack.

Detailed Description

template<typename AX, typename AY, class AData>
class Belle2::TrackFindingCDC::QuadTreeProcessor< AX, AY, AData >

This abstract class serves as a base class for all implementations of track processors.

It provides some functions to create, fill, clear and postprocess a quad tree. If you want to use your own class as a quad tree item, you have to overload this processor. You have provide only the two functions isInNode and createChild.

Definition at line 43 of file QuadTreeProcessor.h.

Member Typedef Documentation

◆ CandidateReceiver

template<typename AX, typename AY, class AData>

using CandidateReceiver = std::function<void(const std::vector<AData*>&, QuadTree*)>

This lambda function can be used for postprocessing.

Definition at line 69 of file QuadTreeProcessor.h.

◆ Item

template<typename AX, typename AY, class AData>

using Item = QuadTreeItem<AData>

The QuadTree will only see items of this type.

Definition at line 51 of file QuadTreeProcessor.h.

◆ QuadTree

template<typename AX, typename AY, class AData>

using QuadTree = QuadTreeNode<AX, AY, Item>

The used QuadTree.

Definition at line 54 of file QuadTreeProcessor.h.

◆ QuadTreeChildren

template<typename AX, typename AY, class AData>

using QuadTreeChildren = typename QuadTree::Children

Alias for the QuadTree Children.

Definition at line 66 of file QuadTreeProcessor.h.

◆ XSpan

template<typename AX, typename AY, class AData>

using XSpan = typename QuadTree::XSpan

This pair describes the span in X for a node.

Definition at line 57 of file QuadTreeProcessor.h.

◆ XYSpans

template<typename AX, typename AY, class AData>

using XYSpans = std::pair<XSpan, YSpan>

This pair of spans describes the span of a node.

Definition at line 63 of file QuadTreeProcessor.h.

◆ YSpan

template<typename AX, typename AY, class AData>

using YSpan = typename QuadTree::YSpan

This pair describes the span in Y for a node.

Definition at line 60 of file QuadTreeProcessor.h.

Constructor & Destructor Documentation

◆ QuadTreeProcessor()

template<typename AX, typename AY, class AData>

QuadTreeProcessor	(	int	lastLevel,
		int	seedLevel,
		const XYSpans &	xySpans,
		bool	debugOutput = false )

inline

Constructor is very simple.

The QuadTree has to be constructed elsewhere.

Parameters

lastLevel	describing the last search level for the quad tree creation
seedLevel	first level to be filled, effectively skip forward to this higher granularity level
xySpans	pair of spans describing the span of a node
debugOutput	enable debug output

Definition at line 79 of file QuadTreeProcessor.h.

        : m_quadTree{std::make_unique<QuadTree>(xySpans.first, xySpans.second, 0, nullptr)}
        , m_lastLevel(lastLevel)
        , m_seedLevel(seedLevel)
        , m_debugOutput(debugOutput)
        , m_debugOutputMap()
      {
      }

◆ ~QuadTreeProcessor()

template<typename AX, typename AY, class AData>

virtual ~QuadTreeProcessor ( )

inlinevirtual

Destructor deletes the quad tree.

Definition at line 94 of file QuadTreeProcessor.h.

      {
        clear();
      }

Member Function Documentation

◆ afterFillDebugHook()

template<typename AX, typename AY, class AData>

virtual void afterFillDebugHook ( QuadTreeChildren & children )

inlinevirtual

Override that function if you want to receive debug output whenever the children of a node are filled the first time Maybe you want to make some nice plots or statistics.

Definition at line 392 of file QuadTreeProcessor.h.

      {
        if (not m_debugOutput) return;
        for (const QuadTree& childNode : children) {
          if (childNode.getLevel() != getLastLevel()) continue; // Only write the lowest level
          //m_debugOutputMap[ {childNode.getXMean(), childNode.getYMean()}] = childNode.getItems();
        }
      }

◆ callResultFunction()

template<typename AX, typename AY, class AData>

static void callResultFunction	(	QuadTree *	node,
		const CandidateReceiver &	candidateReceiver )

inlinestaticprivate

When a node is accepted as a result, we extract a vector with the items (back transformed to AData*) and pass it together with the result node to the candidate receiver function.

Definition at line 301 of file QuadTreeProcessor.h.

      {
        const std::vector<Item*>& foundItems = node->getItems();
        std::vector<AData*> candidate;
        candidate.reserve(foundItems.size());
 
        for (Item* item : foundItems) {
          item->setUsedFlag();
          candidate.push_back(item->getPointer());
        }
 
        candidateReceiver(candidate, node);
      }

◆ clear()

template<typename AX, typename AY, class AData>

void clear ( )

inline

Delete all the QuadTreeItems in the tree and clear the tree.

Definition at line 102 of file QuadTreeProcessor.h.

      {
        m_seededTrees.clear();
        m_quadTree->clearChildren();
        m_quadTree->clearItems();
        m_items.clear();
      }

◆ createChild()

template<typename AX, typename AY, class AData>

virtual XYSpans createChild	(	QuadTree *	node,
		int	iX,
		int	iY ) const

inlineprotectedvirtual

Implement that function if you want to provide a new processor.

It decides which node-spans the n * m children of the node should have. It is called when creating the nodes. The two indices iX and iY tell you where the new node will be created (as node.children[iX][iY]). You can check some information on the level or the x- or y-values by using the methods implemented for node.

Returns: a XYSpan pair of a x- and a y-span that the new child should have. If you don nt want to provide custom spans, just return XYSpans(XSpan(node->getXBinBound(iX), node->getXBinBound(iX + 1)), YSpan(node->getYBinBound(iY), node->getYBinBound(iY + 1)));

Definition at line 324 of file QuadTreeProcessor.h.

      {
        AX xMin = node->getXLowerBound(iX);
        AX xMax = node->getXUpperBound(iX);
        AY yMin = node->getYLowerBound(iY);
        AY yMax = node->getYUpperBound(iY);
        return XYSpans({xMin, xMax}, {yMin, yMax});
      }

◆ createChildren()

template<typename AX, typename AY, class AData>

void createChildren	(	QuadTree *	node,
		QuadTreeChildren &	m_children ) const

inlineprivate

Creates the sub node of a given node.

This function is called by fillGivenTree. To calculate the spans of the children nodes the user-defined function createChiildWithParent is used.

Definition at line 264 of file QuadTreeProcessor.h.

      {
        m_children.reserve(node->getXNbins() * node->getYNbins());
        for (int i = 0; i < node->getXNbins(); ++i) {
          for (int j = 0; j < node->getYNbins(); ++j) {
            const XYSpans& xySpans = createChild(node, i, j);
            const XSpan& xSpan = xySpans.first;
            const YSpan& ySpan = xySpans.second;
            m_children.push_back(QuadTree(xSpan, ySpan, node->getLevel() + 1, node));
          }
        }
      }

◆ fill() [1/2]

template<typename AX, typename AY, class AData>

void fill	(	const CandidateReceiver &	candidateReceiver,
		int	nHitsThreshold )

inline

Start filling the already created tree.

Parameters

candidateReceiver	the lambda function to call after a node was selected
nHitsThreshold	the threshold on the number of items

Definition at line 179 of file QuadTreeProcessor.h.

      {
        fill(candidateReceiver, nHitsThreshold, std::numeric_limits<AY>::max());
      }

◆ fill() [2/2]

template<typename AX, typename AY, class AData>

void fill	(	const CandidateReceiver &	candidateReceiver,
		int	nHitsThreshold,
		float	yLimit )

inline

Fill vector of QuadTree instances with hits.

Parameters

candidateReceiver	the lambda function to call after a node was selected
nHitsThreshold	the threshold on the number of items
yLimit	the threshold in the rho (curvature) variable

Definition at line 190 of file QuadTreeProcessor.h.

      {
        std::vector<QuadTree*> quadTrees = m_seededTrees;
        std::sort(quadTrees.begin(), quadTrees.end(), [](const QuadTree * quadTree1, const QuadTree * quadTree2) {
          return quadTree1->getNItems() > quadTree2->getNItems();
        });
 
        for (QuadTree* tree : quadTrees) {
          erase_remove_if(tree->getItems(), [](Item * hit) { return hit->isUsed(); });
          fillGivenTree(tree, candidateReceiver, nHitsThreshold, yLimit);
        }
      }

◆ fillChildren()

template<typename AX, typename AY, class AData>

void fillChildren	(	QuadTree *	node,
		const std::vector< Item * > &	items )

inlineprivate

This function is called by fillGivenTree and fills the items into the corresponding children.

For this the user-defined method isInNode is called.

Definition at line 281 of file QuadTreeProcessor.h.

      {
        // An item can be inserted into each child at most once
        const size_t neededSize = items.size();
        m_childPtrs.clear();
        m_childPtrs.reserve(node->getChildren().size());
        for (QuadTree& child : node->getChildren()) {
          child.reserveItems(neededSize);
          m_childPtrs.push_back(&child);
        }
 
        this->insertItemsInNodes(m_childPtrs, items);
 
        afterFillDebugHook(node->getChildren());
      }

◆ fillGivenTree()

template<typename AX, typename AY, class AData>

void fillGivenTree	(	QuadTree *	node,
		const CandidateReceiver &	candidateReceiver,
		int	nItemsThreshold,
		AY	yLimit )

inlineprivate

Internal function to do the real quad tree search: fill the nodes, check which of the n*m bins we need to process further and go one level deeper.

Definition at line 208 of file QuadTreeProcessor.h.

      {
        if (node->getNItems() < nItemsThreshold) {
          return;
        }
 
        if ((node->getYMin() > yLimit) or (-node->getYMax() > yLimit)) {
          return;
        }
 
        if (isLeaf(node)) {
          callResultFunction(node, candidateReceiver);
          return;
        }
 
        if (node->getChildren().empty()) {
          this->createChildren(node, node->getChildren());
        }
 
        if (!node->checkFilled()) {
          fillChildren(node, node->getItems());
          node->setFilled();
        }
 
        // Kept on the stack - this function is called millions of times per event
        std::array<QuadTree*, c_maxNChildren> children;
        int nChildren = 0;
        for (QuadTree& child : node->getChildren()) {
          B2ASSERT("More children than the quad tree processor supports", nChildren < c_maxNChildren);
          children[nChildren++] = &child;
        }
        const auto compareNItems = [](const QuadTree * lhs, const QuadTree * rhs) {
          return lhs->getNItems() < rhs->getNItems();
        };
 
        // Explicitly count down the children
        for (int nRemaining = nChildren; nRemaining > 0; --nRemaining) {
          auto itHeaviestChild =
            std::max_element(children.begin(), children.begin() + nRemaining, compareNItems);
          QuadTree* heaviestChild = *itHeaviestChild;
          // Drop the heaviest child from the list keeping the order of the remaining ones
          std::move(itHeaviestChild + 1, children.begin() + nRemaining, itHeaviestChild);
          // After we have processed some children we need to get rid of the already used hits in all the children,
          // because this can change the number of items drastically
          erase_remove_if(heaviestChild->getItems(), [&](Item * hit) { return hit->isUsed(); });
          this->fillGivenTree(heaviestChild, candidateReceiver, nItemsThreshold, yLimit);
        }
      }

◆ getAssignedItems()

template<typename AX, typename AY, class AData>

std::vector< AData * > getAssignedItems ( )

inline

Get items that have been assigned to the seed level The returned elements are unique even if items are assigned multiple times.

Definition at line 160 of file QuadTreeProcessor.h.

      {
        std::vector<const TrackingUtilities::CDCWireHit*> result;
        for (QuadTree* seededTree : m_seededTrees) {
          for (Item* item : seededTree->getItems()) {
            result.push_back(item->getPointer());
          }
        }
        std::sort(result.begin(), result.end());
        result.erase(std::unique(result.begin(), result.end()), result.end());
        return result;
      }

◆ getDebugInformation()

template<typename AX, typename AY, class AData>

const std::map< std::pair< AX, AY >, std::vector< Item * > > & getDebugInformation ( ) const

inline

Return the debug information if collected.

Definition at line 404 of file QuadTreeProcessor.h.

      {
        return m_debugOutputMap;
      }

◆ getLastLevel()

template<typename AX, typename AY, class AData>

int getLastLevel ( ) const

inlineprotected

Return the parameter last level.

Definition at line 382 of file QuadTreeProcessor.h.

      {
        return m_lastLevel;
      }

◆ insertItemsInNodes()

template<typename AX, typename AY, class AData>

virtual void insertItemsInNodes	(	const std::vector< QuadTree * > &	nodes,
		const std::vector< Item * > &	items )

inlineprotectedvirtual

Insert each of the given items into every one of the given nodes it belongs to.

The default implementation simply asks isInNode for each item and node pair. Processors may override it to share the parts of the containment check that only depend on the item or on a part of the node geometry over the given set of nodes. Any implementation has to insert the items into each node in the order in which they appear in the given item range.

Definition at line 351 of file QuadTreeProcessor.h.

      {
        for (Item* item : items) {
          if (item->isUsed()) continue;
 
          for (QuadTree* node : nodes) {
            if (isInNode(node, item->getPointer())) {
              node->insertItem(item);
            }
          }
        }
      }

◆ isInNode()

template<typename AX, typename AY, class AData>

virtual bool isInNode	(	QuadTree *	node,
		AData *	item ) const

protectedpure virtual

Implement that function if you want to provide a new processor.

It is called when filling the quad tree after creation. For every item in a node and every child node this function gets called and should decide, if the item should go into this child node or not.

Parameters

node	child node
item	item to be filled into the child node or not

Returns: true if this item belongs into this node.

◆ isLeaf()

template<typename AX, typename AY, class AData>

virtual bool isLeaf ( QuadTree * node ) const

inlineprotectedvirtual

Function which checks if given node is leaf Implemented as virtual to keep possibility of changing lastLevel values depending on region is phase-space (i.e.

setting lastLevel as a function of Y-variable)

Definition at line 370 of file QuadTreeProcessor.h.

      {
        if (node->getLevel() >= m_lastLevel) {
          return true;
        } else {
          return false;
        }
      }

◆ seed()

template<typename AX, typename AY, class AData>

void seed ( const std::vector< AData * > & datas )

inline

Fill in the items in the given vector.

They are transformed to QuadTreeItems internally.

Definition at line 113 of file QuadTreeProcessor.h.

      {
        // Create the items
        for (AData* data : datas) {
          m_items.emplace_back(data);
        }
 
        // Creating the seed level
        long nSeedBins = pow(2, m_seedLevel);
        m_seededTrees.reserve(nSeedBins * nSeedBins);
 
        // Expand the first levels to the seed sectors
        m_seededTrees.push_back(m_quadTree.get());
        std::vector<QuadTree*> nextSeededTrees;
 
        for (int level = 0; level < m_seedLevel; ++level) {
          for (QuadTree* node : m_seededTrees) {
            if (node->getChildren().empty()) {
              this->createChildren(node, node->getChildren());
            }
            for (QuadTree& child :  node->getChildren()) {
              nextSeededTrees.push_back(&child);
            }
          }
          std::swap(nextSeededTrees, m_seededTrees);
          nextSeededTrees.clear();
        }
 
        // Fill the seed level with the items
        m_itemPtrs.clear();
        m_itemPtrs.reserve(m_items.size());
        for (Item& item : m_items) {
          m_itemPtrs.push_back(&item);
        }
 
        for (QuadTree* seededTree : m_seededTrees) {
          seededTree->reserveItems(m_items.size());
        }
 
        this->insertItemsInNodes(m_seededTrees, m_itemPtrs);
      }

Definition at line 434 of file QuadTreeProcessor.h.

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

tracking/trackFindingCDC/legendre/quadtree/include/QuadTreeProcessor.h

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ CandidateReceiver

◆ Item

◆ QuadTree

◆ QuadTreeChildren

◆ XSpan

◆ XYSpans

◆ YSpan

Constructor & Destructor Documentation

◆ QuadTreeProcessor()

◆ ~QuadTreeProcessor()

Member Function Documentation

◆ afterFillDebugHook()

◆ callResultFunction()

◆ clear()

◆ createChild()

◆ createChildren()

◆ fill() [1/2]

◆ fill() [2/2]

◆ fillChildren()

◆ fillGivenTree()

◆ getAssignedItems()

◆ getDebugInformation()

◆ getLastLevel()

◆ insertItemsInNodes()

◆ isInNode()

◆ isLeaf()

◆ seed()

Member Data Documentation

◆ c_maxNChildren

◆ m_childPtrs

◆ m_debugOutput

◆ m_debugOutputMap

◆ m_itemPtrs

◆ m_items

◆ m_lastLevel

◆ m_quadTree

◆ m_seededTrees

◆ m_seedLevel