TumbleTree.hpp

Go to the documentation of this file.

//
// Created by patrick on 4/4/19.
//
 
#ifndef LAS_VEGAS_TUMBLETREE_HPP
#define LAS_VEGAS_TUMBLETREE_HPP
 
#include "lvr2/attrmaps/HashMap.hpp"
#include "lvr2/geometry/Handles.hpp"
 
namespace lvr2
{
 
typedef struct Cell
{
    double alpha = 1;
    double signal_counter;
    HashMap<VertexHandle, double> duplicateMap;
    Cell* left;  // left subtree
    Cell* right; // right subtree
    Cell* parent;
} Cell;
 
class TumbleTree
{
 
    Cell* root;
 
    Cell* makeEmpty(Cell* c);
 
    Cell* remove(double sc, VertexHandle vH, Cell* c, bool removeWhole = false);
    // Cell* removeTwo(double sc, VertexHandle vH, Cell* c, bool removeWhole = false, double alpha =
    // 1);
 
    Cell* insert(Cell* c, double sc, VertexHandle vH);
    Cell* findMin(Cell* c);
    Cell* findMax(Cell* c);
    Cell* find(double sc, VertexHandle vH, Cell* c, double alpha = 1);
    int size(Cell* c);
    int maxDepth(Cell* cell);
    int minDepth(Cell* cell);
    int sumDepth(Cell* c, int currentDepth = 1);
    int numLeafes(Cell* c);
    Cell* buildTree(vector<Cell*>& cells, int start, int end);
    void getCellsAsVector(Cell* c, vector<Cell*>& cells);
 
    void update(double alpha);
 
    void inorder(Cell* c);
 
  public:
    TumbleTree();
    ~TumbleTree();
 
    // Cell* insertIterative(double sc, VertexHandle vH);
    Cell* insert(double sc, VertexHandle vH);
    double remove(Cell* c, VertexHandle vH); // returns the real sc
 
    int maxDepth();
    int minDepth();
    int avgDepth();
    Cell* find(double sc, VertexHandle vH);
 
    void display();
    void balance();
 
    Cell* min();
    Cell* max();
 
    Cell* makeCell(double sc,
                   VertexHandle vH,
                   Cell* left = NULL,
                   Cell* right = NULL,
                   Cell* parent = NULL,
                   double alpha = 1);
 
    int size();
 
    void updateSC(double alpha);
    int notDeleted = 0;
};
 
} // namespace lvr2
 
#include "TumbleTree.tcc"
 
#endif // LAS_VEGAS_TUMBLETREE_HPP