BeachLine.h

Go to the documentation of this file.

#ifndef BeachLine_h
#define BeachLine_h

#include "larreco/RecoAlg/Cluster3DAlgs/Voronoi/IEvent.h"
#include "larreco/RecoAlg/Cluster3DAlgs/Voronoi/EventUtilities.h"

// std includes
#include <vector>
#include <list>
#include <algorithm>
//------------------------------------------------------------------------------------------------------------------------------------------

namespace voronoi2d
{
class BSTNode
{
public:
    BSTNode() :
        m_depth(0),
        m_event(NULL),
        m_parent(NULL),
        m_leftChild(NULL),
        m_rightChild(NULL),
        m_predecessor(NULL),
        m_successor(NULL),
        m_associated(NULL),
        m_halfEdge(NULL),
        m_face(NULL)
    {}
    
    BSTNode(IEvent* event) :
        m_depth(0),
        m_event(event),
        m_parent(NULL),
        m_leftChild(NULL),
        m_rightChild(NULL),
        m_predecessor(NULL),
        m_successor(NULL),
        m_associated(NULL),
        m_halfEdge(NULL),
        m_face(NULL)
    {
        if (m_event) m_event->setBSTNode(this);
    }
    
    BSTNode(IEvent*, BSTNode*, BSTNode*, BSTNode*);

    ~BSTNode() {}

    int               getDepth()       const {return m_depth;}
    IEvent*           getEvent()       const {return m_event;}
    BSTNode*          getParent()      const {return m_parent;}
    BSTNode*          getLeftChild()   const {return m_leftChild;}
    BSTNode*          getRightChild()  const {return m_rightChild;}
    BSTNode*          getPredecessor() const {return m_predecessor;}
    BSTNode*          getSuccessor()   const {return m_successor;}
    BSTNode*          getAssociated()  const {return m_associated;}
    
    dcel2d::HalfEdge* getHalfEdge()    const {return m_halfEdge;}
    dcel2d::Face*     getFace()        const {return m_face;}
    
    void setParent(BSTNode* node)              {m_parent      = node;}
    void setLeftChild(BSTNode* node)           {m_leftChild   = node;}
    void setRightChild(BSTNode* node)          {m_rightChild  = node;}
    void setPredecessor(BSTNode* node)         {m_predecessor = node;}
    void setSuccessor(BSTNode* node)           {m_successor   = node;}
    void setAssociated(BSTNode* node)          {m_associated  = node;}
    
    void setHalfEdge(dcel2d::HalfEdge* half)   {m_halfEdge    = half;}
    void setFace(dcel2d::Face* face)           {m_face        = face;}
    
    void setDepth(int depth)                   {m_depth       = depth;}
    void setDepth();
    
    bool operator<(const BSTNode&) const;

private:
    int               m_depth;        // Keep track of depth of nodes to this one
    IEvent*           m_event;        // Pointer to the event object
    BSTNode*          m_parent;       // Tree traversal - parent node
    BSTNode*          m_leftChild;    // Tree traversal - left child node
    BSTNode*          m_rightChild;   // Tree traversal - right child node
    BSTNode*          m_predecessor;  // Beachline traversal - predecessor
    BSTNode*          m_successor;    // Beachline traversal - successor
    BSTNode*          m_associated;   // This allows handling of circle events
    dcel2d::HalfEdge* m_halfEdge;     // If a breakpoint then we associate halfedges
    dcel2d::Face*     m_face;         // If a leaf then we associated faces
};
    
using BSTNodeList = std::list<BSTNode>;

class BeachLine
{
public:
    BeachLine() : m_root(NULL) {m_nodeVec.clear();}
    
    bool           isEmpty()                         const {return m_root == NULL;}
    void           setEmpty()                              {m_root = NULL;}
    const BSTNode* getTopNode()                      const {return m_root;}
    BSTNode*       findBestLeaf(const IEvent* event) const {return findBestLeaf(event, m_root);}
    BSTNode*       insertNewLeaf(IEvent*);
    BSTNode*       removeLeaf(BSTNode*);
    int            getHeight()                       const {return getTreeDepth(m_root);}
    int            countNodes()                      const;
    int            countLeaves()                     const;
    int            traverseBeach()                   const;
    
private:
    BSTNode* insertNewLeaf(IEvent*, BSTNode*);
    
    BSTNode* findBestLeaf(const IEvent*, BSTNode*) const;
    
    void countNodes(const BSTNode*, int&) const;
    void countLeaves(const BSTNode*, int&) const;
    
    int traverseBeachLeft(BSTNode*) const;
    int traverseBeachRight(BSTNode*) const;
    
    void checkBeachLine(double) const;
    
    int getTreeDepth(const BSTNode*) const;
    
    void     rebalance(BSTNode*);
    BSTNode* rotateWithLeftChild(BSTNode*);
    BSTNode* rotateWithRightChild(BSTNode*);

    BSTNode*       m_root;      // the root of all evil, er, the top node
    BSTNodeList    m_nodeVec;   // Use this to keep track of the nodes
    
    EventUtilities m_utilities;
};
    
} // namespace lar_cluster3d
#endif