BBoxTree.h

Go to the documentation of this file.

// -*- C++ -*-

#if !defined(__BBoxTree_h__)
#define __BBoxTree_h__

// If we are debugging the whole geom package.
#if defined(DEBUG_geom) && !defined(DEBUG_BBoxTree)
#define DEBUG_BBoxTree
#endif

#include "../kernel/BBox.h"
#include "../kernel/distance.h"

#include "../../ads/functor/compose.h"
#include "../../ads/functor/composite_compare.h"
#include "../../ads/functor/Dereference.h"

#include "../../numerical/random/uniform/ContinuousUniformGenerator.h"
#include "../../numerical/random/uniform/DiscreteUniformGeneratorMc32.h"

#include <vector>

BEGIN_NAMESPACE_GEOM

//
//---------------------------BBoxTreeTypes----------------------------------
//


template<int N, typename T>
class BBoxTreeTypes {
  //
  // Public types.
  //
      
public:

  typedef T Number;
  typedef ads::FixedArray<N,T> Point;
  typedef BBox<N,Number> BBox;
  typedef int SizeType;

  typedef std::vector<int> IndexContainer;
  typedef typename IndexContainer::iterator IndexIterator;
  typedef typename IndexContainer::const_iterator IndexConstIterator;
};


//
//---------------------------BBoxTreeNode----------------------------------
//

// Forward declaration.
template<int N, typename T>
class BBoxTreeLeaf;

template<int N, typename T>
class BBoxTreeNode {
  //
  // Private types.
  //

private:

  typedef BBoxTreeTypes<N,T> Types;
  typedef BBoxTreeLeaf<N,T> Leaf;


  //
  // Public types.
  //

public:
    
  typedef typename Types::Number Number;
  typedef typename Types::Point Point;
  typedef typename Types::BBox BBox;
  typedef typename Types::SizeType SizeType;

  //--------------------------------------------------------------------------


  virtual
  ~BBoxTreeNode()
  {}

  //--------------------------------------------------------------------------


  virtual
  void
  computePointQuery(std::vector<const Leaf*>& leaves, 
                    const Point& x) const = 0;

  virtual
  void
  computeWindowQuery(std::vector<const Leaf*>& leaves, 
                const BBox& window) const = 0;

  virtual
  void
  computeMinimumDistanceQuery(std::vector<const Leaf*>& leaves, 
                              const Point& x, Number* upperBound) const 
    = 0;
  
  //--------------------------------------------------------------------------


  virtual
  const BBox&
  getDomain() const = 0;

  //--------------------------------------------------------------------------


  virtual
  void
  computeDomain(const std::vector<BBox>& boxes) = 0;

  //--------------------------------------------------------------------------


  virtual 
  void 
  printAscii(std::ostream& out) const = 0;

  //--------------------------------------------------------------------------


  virtual 
  SizeType
  getMemoryUsage() const = 0;

  //--------------------------------------------------------------------------


  virtual
  void 
  checkValidity(const std::vector<BBox>& boxes) const = 0;

};



template<int N, typename T>
inline
std::ostream& 
operator<<(std::ostream& out, const BBoxTreeNode<N,T>& node) {
  node.printAscii(out);
  return out;
}



//
//---------------------------BBoxTreeLeaf----------------------------------
//

template<int N, typename T>
class BBoxTreeLeaf : 
  public BBoxTreeNode<N,T> {
  //
  // Private types.
  //

private:
  
  typedef BBoxTreeTypes<N,T> Types;
  typedef BBoxTreeLeaf Leaf;
  typedef typename Types::IndexContainer IndexContainer;
  typedef typename Types::IndexIterator IndexIterator;
  
  //
  // Public types.
  //

public:

  typedef typename Types::Number Number;
  typedef typename Types::Point Point;
  typedef typename Types::BBox BBox;
  typedef typename Types::SizeType SizeType;

  typedef typename Types::IndexConstIterator IndexConstIterator;

  //
  // Member data
  //
    
private:

  BBox _domain;
  IndexContainer _indices;

  //
  // Not implemented
  //

private:

  BBoxTreeLeaf(const BBoxTreeLeaf&);

  BBoxTreeLeaf& 
  operator=(const BBoxTreeLeaf&);


public:
    
  //--------------------------------------------------------------------------



  template<typename ObjectIter, typename ObjectIterIter>
  BBoxTreeLeaf(ObjectIter base, ObjectIterIter begin, ObjectIterIter end);
  
  virtual 
  ~BBoxTreeLeaf()
  {}

  //--------------------------------------------------------------------------


  const BBox& 
  getDomain() const {
    return _domain;
  }

  IndexConstIterator
  getIndicesBeginning() const {
    return _indices.begin();
  }
  
  IndexConstIterator
  getIndicesEnd() const {
    return _indices.end();
  }
  
  //--------------------------------------------------------------------------


  void
  computeDomain(const std::vector<BBox>& boxes);

  //--------------------------------------------------------------------------


  void
  computePointQuery(std::vector<const Leaf*>& leaves, const Point& x) const {
    if (_domain.isIn(x)) {
      leaves.push_back(this);
    }
  }

  void
  computeWindowQuery(std::vector<const Leaf*>& leaves, 
                     const BBox& window) const {
    if (doOverlap(window, _domain)) {
      leaves.push_back(this);
    }
  }

  void
  computeMinimumDistanceQuery(std::vector<const Leaf*>& leaves, 
                              const Point& x, Number* upperBound) const;

  //--------------------------------------------------------------------------


  // Print the domain and indices.
  void 
  printAscii(std::ostream& out) const;

  //--------------------------------------------------------------------------


  SizeType
  getMemoryUsage() const {
    return int(sizeof(BBoxTreeLeaf) + _indices.size() * sizeof(int));
  }

  //--------------------------------------------------------------------------



  void 
  checkValidity(const std::vector<BBox>& boxes) const;

};




//
//-------------------------BBoxTreeBranch------------------------------
//

template<int N, typename T>
class BBoxTreeBranch :
  public BBoxTreeNode<N,T> {
  //
  // Private types.
  //

private:
  
  typedef BBoxTreeTypes<N,T> Types;
  typedef BBoxTreeNode<N,T> Node;
  typedef BBoxTreeLeaf<N,T> Leaf;
  
  //
  // Public types.
  //

public:

  typedef typename Types::Number Number;
  typedef typename Types::Point Point;
  typedef typename Types::BBox BBox;
  typedef typename Types::SizeType SizeType;

  //
  // Member data
  //

private:

  BBox _domain;
  Node* _left;
  Node* _right;

  //
  // Not implemented
  //
    
private:

  // Default constructor not implemented.
  BBoxTreeBranch();

  // Copy constructor not implemented
  BBoxTreeBranch(const BBoxTreeBranch&);

  // Assignment operator not implemented
  BBoxTreeBranch& 
  operator=(const BBoxTreeBranch&);

public:

  //--------------------------------------------------------------------------


  BBoxTreeBranch(const Point* base,
                 const ads::FixedArray<N, std::vector<const Point*> >& sorted,
                 SizeType leafSize);

  virtual 
  ~BBoxTreeBranch() {
    delete _left;
    delete _right;
  }

  //--------------------------------------------------------------------------


  const BBox& 
  getDomain() const {
    return _domain;
  }

  //--------------------------------------------------------------------------


  void
  computeDomain(const std::vector<BBox>& boxes);

  //--------------------------------------------------------------------------


  void
  computePointQuery(std::vector<const Leaf*>& leaves, const Point& x) const;

  void
  computeWindowQuery(std::vector<const Leaf*>& leaves, 
                     const BBox& window) const;

  void
  computeMinimumDistanceQuery(std::vector<const Leaf*>& leaves, 
                              const Point& x, Number* upperBound) const;

  //--------------------------------------------------------------------------


  SizeType
  getMemoryUsage() const {
    return (sizeof(BBoxTreeBranch) + _left->getMemoryUsage() 
            + _right->getMemoryUsage());
  }

  //--------------------------------------------------------------------------


  void 
  checkValidity(const std::vector<BBox>& boxes) const;
    
  //--------------------------------------------------------------------------


  // Print the domain and the leaves.
  void 
  printAscii(std::ostream& out) const;

};




//-------------------------------------------------------------------------
//---------------------------BBoxTree--------------------------------------
//-------------------------------------------------------------------------


template<int N, typename T = double>
class BBoxTree {
  //
  // Private types.
  //

private:

  typedef BBoxTreeTypes<N,T> Types;

  //
  // Public types.
  //

public:

  typedef typename Types::Number Number;
  typedef typename Types::Point Point;
  typedef typename Types::BBox BBox;
  typedef typename Types::SizeType SizeType;


  //
  // Private types.
  //

private:

  typedef BBoxTreeNode<N,T> Node;
  typedef BBoxTreeBranch<N,T> Branch;
  typedef BBoxTreeLeaf<N,T> Leaf;
  typedef typename Types::IndexConstIterator IndexConstIterator;

  //
  // Member data
  //

private:

  Node* _root;

  std::vector<BBox> _boxes;

  mutable std::vector<const Leaf*> _leaves;

private:

  //
  // Not implemented
  //

private:

  BBoxTree(const BBoxTree&);

  BBoxTree& 
  operator=(const BBoxTree&);

public:

  //--------------------------------------------------------------------------


  BBoxTree() :
    _root(0),
    _boxes(),
    _leaves()
  {}


  template<class BBoxInputIter>
  BBoxTree(BBoxInputIter begin, BBoxInputIter end, 
           const SizeType leafSize = 8);


  template<class BBoxInputIter>
  void
  build(BBoxInputIter begin, BBoxInputIter end, 
        const SizeType leafSize = 8);

  ~BBoxTree() {
    if (_root) {
      delete _root;
    }
  }
  
  void
  destroy();
  
  // @}
  //--------------------------------------------------------------------------
  // @{

  SizeType 
  getSize() const { 
    return SizeType(_boxes.size());
  }

  bool 
  isEmpty() const { 
    return _boxes.empty();
  }

  // @}
  //--------------------------------------------------------------------------
  // @{

  template<typename IntegerOutputIter>
  void
  computePointQuery(IntegerOutputIter iter, const Point& x) const;

  template<typename IntegerOutputIter>
  void
  computeWindowQuery(IntegerOutputIter iter, const BBox& window) const;

  template<typename IntegerOutputIter>
  void
  computeMinimumDistanceQuery(IntegerOutputIter iter, const Point& x) const;

  // @}
  //--------------------------------------------------------------------------
  // @{

  void 
  printAscii(std::ostream& out) const;

  // @}
  //--------------------------------------------------------------------------
  // @{

  SizeType
  getMemoryUsage() const {
    if (_root) {
      return (sizeof(BBoxTree) + _root->getMemoryUsage());
    }
    return sizeof(BBoxTree);
  }

  // @}
  //--------------------------------------------------------------------------
  // @{

  void 
  checkValidity() const {
    if (_root) {
      _root->checkValidity(_boxes);
    }
  }

  // @}

  //
  // Private member functions.
  //

private:

  void
  build(SizeType leafSize);
};



template<int N, typename T>
inline
std::ostream& 
operator<<(std::ostream& out, const BBoxTree<N,T>& x) {
  x.printAscii(out);
  return out;
}


END_NAMESPACE_GEOM

#define __geom_BBoxTree_ipp__
#include "BBoxTree.ipp"
#undef __geom_BBoxTree_ipp__

#endif

---