
 // -*- C++ -*-


 namespace Hurricane {

 /*! \class        QuadTree
  *  \brief        QuadTree description (\b API)
  *
  *  \section      secQuadTreeIntro  Introduction
  *
  *                Quadtrees are efficient hierarchical data structures for the 
  *                geometrical access of gos. 
  *
  *  \important    You must not change the bounding box of an object already 
  *                present in the quadtree, because its localization within the 
  *                tree depends on it. Therefore, if an object is modified, you 
  *                must in a firts time remove it from the quadtree, apply the 
  *                changes then re-insert it in the quadtree, at the right place 
  *                which depends of its new bounding box. 
  */



 /*! \function     QuadTree::QuadTree();
  *                Default constructor : the quadtree is initially empty 
  *                (objects will be inserted or removed on demand). 
  */


 /*! \function     QuadTree::~QuadTree();
  *                Destroys the quadtree and its sub-quadtrees but doesn't touch 
  *                to the contained objects, they will ibe only detached from 
  *                their respective quadtree nodes. 
  */


 /*! \function     Box QuadTree::getBoundingBox() const;
  *  \Return       the quadtree bounding box, that is the minimal bounding box 
  *                including all objects of the quad tree (this bounding box is 
  *                updated dynamically). 
  */

 /*! \function     Gos QuadTree::getGos() const;
  *  \Return       the collection of graphical objects contained in the 
  *                quadtree. 
  */

 /*! \function     Gos QuadTree::getGosUnder(const Box& area) const;
  *  \Return       the collection of graphical objects contained in the quadtree 
  *                and whose bounding box intersects the rectangular region 
  *                defined by \c \<area\>. 
  */


 /*! \function     bool QuadTree::isEmpty() const;
  *  \Return       <b>true</b> if the quadtree doesn't contain any object, else 
  *                <b>false</b>. 
  */


 /*! \function     void QuadTree::insert(Go* go);
  *                inserts the graphic object within the quadtree (if not yet 
  *                inserted). 
  *
  *  \caution      If the graphic object pointer is NULL an exception is thrown. 
  *
  *  \remark       When the number of objects contained in a quadtree leaf is 
  *                greater than some threshold, this leaf is split into four 
  *                balanced sub-quadtrees. This recursive division provides a 
  *                faster access even for very large quadtrees (to the detriment 
  *                of some memory loss). 
  */

 /*! \function     void QuadTree::remove(Go* go);
  *                removes the object from the quadtree. 
  *
  *  \caution      If the graphic object is NULL an exception is thrown. 
  *
  *  \remark       When the number of objects included in the quadtree goes 
  *                below an other threshold, the inverse behaviour happens : the 
  *                sub-quadtrees are deleted and the contained objects are taken 
  *                in charge by this quadtree node (and memory is released to 
  *                the system). 
  */


 /*! \section      secQuadTreeRemark  Remark
  *
  *                In principle there is no need to call upon directly those 
  *                insertion and removal functions because graphic objects are 
  *                inserted within the quadtree by the method <b>Materialize</b> 
  *                and removed by the method <b>Unmaterialize</b>. 
  *
  *                Nevertheless it is necessary to know them if you need to 
  *                overload one of those methods. 
  *
  *                We give as an example the implementation of those methods for 
  *                the components : 
\code
void Component::Materialize()
// **************************
{
   // we get the cell and the layer of the component
   Cell* cell = getCell();
   Layer* layer = getLayer();
 
   // we get the slice within which the object must be inserted
   // (if necessary we create it)
   Slice* slice = cellGetSlice(layer);
   if (!slice) slice = Slice::_Create(cell, layer);
 
   // we get the quadtree associated to the slice
   QuadTree* quadTree = slice_getQuadTree();
 
   // we insert into the object
   quadTreeInsert(this);
 
   // we request to the cell to take into account the new bounding box
   // of the quadtree (does nothing if the envelope has not grown).
   cell_Fit(quadTreeGetBoundingBox());
}

\endcode
\code
void Component::Unmaterialize()
// ****************************
{
   // we get the cell and the layer of the component
   Cell* cell = getCell();
   Layer* layer = getLayer();
 
   // we get the associated slice 
   Slice* slice = cellGetSlice(layer);
 
   // if the slice doesn't exist : there is nothing to do
 
   if (slice) {
   
      // we inform the cell that an object with a given bounding
      // box will be removed (does something only if the bounding
      // box is tangent to the cell bounding box)
      cell_Unfit(getBoundingBox());
\endcode
  *                // we remove the object from its slice 
  *                slice-\>_getQuadTree()-\>remove(this); 
  *
  *                // if the slice becomes empty, it is destroyed if 
  *                (slice-\>isEmpty()) slice-\>_Delete(); } } 
  */

 }
