degate 0.1.1
Public Member Functions | Private Member Functions | Private Attributes | Static Private Attributes | Friends
degate::QuadTree< T > Class Template Reference

Quad tree to store objects and to accesss them with a two dimensional access path. More...

#include <QuadTree.h>

Inheritance diagram for degate::QuadTree< T >:
Inheritance graph
[legend]

List of all members.

Public Member Functions

const std::string get_name () const
 QuadTree (BoundingBox const &box, int max_entries=50)
 Create a new quadtree.
 ~QuadTree ()
 Destruct a quadtree.
bool is_leave () const
 Check if the quadtree or a quadtree node is a leaf node.
ret_t insert (T object)
 Insert an object into the quadtree.
ret_t remove (T object)
 Remove an object from the quadtree.
void notify_shape_change (T object)
 Notify that the bounding box of an object changed.
unsigned int total_size () const
 Get the number of objects that are stored in a quadtree node and in all child nodes.
unsigned int depth () const
 Get the number of layers, that quadtree has.
bool is_empty () const
unsigned int get_width () const
 Get the dimension of the quadtree.
unsigned int get_height () const
 Get the dimension of the quadtree.
region_iterator< T > region_iter_begin (int min_x, int max_x, int min_y, int max_y)
 Get an interator to iterate over quadtree nodes down to the leafes.
region_iterator< T > region_iter_begin (BoundingBox const &bbox)
 Get a region iterator to iterate over quatree objects.
region_iterator< T > region_iter_begin ()
 Get a region iterator to iterate over the complete quatree.
region_iterator< T > region_iter_end ()
 Get an end marker for the region iteration.
BoundingBox const & get_bounding_box () const
 Get the bounding box for a quad tree layer.
void print (std::ostream &os=std::cout, int tabs=0, bool recursive=false)
 Print the quadtree.

Private Member Functions

 QuadTree (BoundingBox const &box, QuadTree *parent, std::string node_name, int max_entries=50)
QuadTree< T > * traverse_downto_bounding_box (BoundingBox const &box)
ret_t split ()
ret_t reinsert_objects ()
bool is_splitable () const

Private Attributes

unsigned int max_entries
BoundingBox box
std::vector< QuadTree< T > > subtree_nodes
std::list< T > children
QuadTree * parent
std::string node_name

Static Private Attributes

static const int NW = 0
static const int NE = 1
static const int SW = 2
static const int SE = 3
static const unsigned int bbox_min_size = 10

Friends

class region_iterator< T >

Detailed Description

template<typename T>
class degate::QuadTree< T >

Quad tree to store objects and to accesss them with a two dimensional access path.

Definition at line 67 of file QuadTree.h.

Constructor & Destructor Documentation

template<typename T >
degate::QuadTree< T >::QuadTree ( BoundingBox const &  box,
QuadTree< T > *  parent,
std::string  node_name,
int  max_entries = 50 
) [private]

Definition at line 240 of file QuadTree.h.

References degate::QuadTree< T >::node_name.

                                                                                                         {
    this->box = box;
    this->max_entries = max_entries;
    this->parent = parent;

    node_name = parent->node_name + std::string("/") + _node_name;
  }
template<typename T >
degate::QuadTree< T >::QuadTree ( BoundingBox const &  box,
int  max_entries = 50 
)

Create a new quadtree.

Parameters:
boxThe bounding box defines the dimension of the quadtree.
max_entriesDefines how many objects should be stored in a quadtree node, before the node is splitted. This value is not a hard limit. The quadtree can ignore this parameter, if it has no choice.

Definition at line 232 of file QuadTree.h.

                                                                {
    this->box = box;
    this->max_entries = max_entries;
    parent = NULL;
    node_name = "/";
  }
template<typename T >
degate::QuadTree< T >::~QuadTree ( )

Destruct a quadtree.

Definition at line 249 of file QuadTree.h.

                         {
  }

Member Function Documentation

template<typename T >
unsigned int degate::QuadTree< T >::depth ( ) const

Get the number of layers, that quadtree has.

Definition at line 425 of file QuadTree.h.

                                        {

    unsigned int max_d = 0;
    if(!is_leave()) {
      for(typename std::vector< QuadTree<T> >::const_iterator it = subtree_nodes.begin();
          it != subtree_nodes.end();
          ++it) {

        unsigned int d = (*it).depth();
        max_d = std::max(max_d, d);
      }
    }
    return 1 + max_d;
  }
template<typename T >
BoundingBox const & degate::QuadTree< T >::get_bounding_box ( ) const

Get the bounding box for a quad tree layer.

Definition at line 477 of file QuadTree.h.

Referenced by degate::Layer::get_bounding_box().

                                                         {
    return box;
  }

Here is the caller graph for this function:

template<typename T >
unsigned int degate::QuadTree< T >::get_height ( ) const

Get the dimension of the quadtree.

Definition at line 258 of file QuadTree.h.

Referenced by degate::Layer::get_height().

                                             {
    return box.get_height();
  }

Here is the caller graph for this function:

template<typename T>
const std::string degate::QuadTree< T >::get_name ( ) const [inline]

Definition at line 102 of file QuadTree.h.

{ return node_name; }
template<typename T >
unsigned int degate::QuadTree< T >::get_width ( ) const

Get the dimension of the quadtree.

Definition at line 253 of file QuadTree.h.

Referenced by degate::Layer::get_width().

                                            {
    return box.get_width();
  }

Here is the caller graph for this function:

template<typename T>
ret_t degate::QuadTree< T >::insert ( T  object)

Insert an object into the quadtree.

Definition at line 329 of file QuadTree.h.

References degate::RET_ERR, RET_IS_NOT_OK, and degate::RET_OK.

Referenced by degate::Layer::add_object().

                                    {

    ret_t ret;
    const BoundingBox & bbox =
      get_bbox_trait_selector<is_pointer<T>::value>::get_bounding_box_for_object(object);

    QuadTree<T> * found = traverse_downto_bounding_box(bbox);
    assert(found != NULL);

    if(found != NULL) {

      if((found->children.size() >= max_entries) && found->is_splitable()) {

        if(RET_IS_NOT_OK(ret = found->split())) return ret;
        if(RET_IS_NOT_OK(ret = found->reinsert_objects())) return ret;
        if(RET_IS_NOT_OK(ret = found->insert(object))) return ret;
        return RET_OK;
      }
      else {
        found->children.push_back(object);
        return RET_OK;
      }
    }
    return RET_ERR;
  }

Here is the caller graph for this function:

template<typename T>
bool degate::QuadTree< T >::is_empty ( ) const [inline]

Definition at line 162 of file QuadTree.h.

Referenced by degate::Layer::is_empty().

{ return total_size() == 0; }

Here is the caller graph for this function:

template<typename T >
bool degate::QuadTree< T >::is_leave ( ) const

Check if the quadtree or a quadtree node is a leaf node.

Definition at line 386 of file QuadTree.h.

                                   {
    return subtree_nodes.size() == 4 ? false : true;
  }
template<typename T >
bool degate::QuadTree< T >::is_splitable ( ) const [private]

Definition at line 264 of file QuadTree.h.

                                       {
    return box.get_width() > bbox_min_size &&
      box.get_height() > bbox_min_size &&
      is_leave();
  }
template<typename T>
void degate::QuadTree< T >::notify_shape_change ( T  object)

Notify that the bounding box of an object changed.

It might be neccessary to adjust the objects position in the quadtree.

Definition at line 356 of file QuadTree.h.

Referenced by degate::Layer::notify_shape_change().

                                                {
    remove(object);
    insert(object);
  }

Here is the caller graph for this function:

template<typename T >
void degate::QuadTree< T >::print ( std::ostream &  os = std::cout,
int  tabs = 0,
bool  recursive = false 
)

Print the quadtree.

Definition at line 482 of file QuadTree.h.

References degate::gen_tabs(), degate::BoundingBox::get_max_x(), degate::BoundingBox::get_max_y(), degate::BoundingBox::get_min_x(), and degate::BoundingBox::get_min_y().

Referenced by degate::Layer::print().

                                                                   {

    os
      << gen_tabs(tabs) << "Node name                      : " << get_name() << std::endl
      << gen_tabs(tabs) << "Bounding box                   : x = "
      << box.get_min_x() << " .. " << box.get_max_x()
      << " / y = "
      << box.get_min_y() << " .. " << box.get_max_y()
      << std::endl

      << gen_tabs(tabs) << "Num elements in this node      : " << children.size() << std::endl
      << gen_tabs(tabs) << "Preferred max num of elements : " << max_entries << std::endl
      << std::endl
      ;

    if(parent == NULL /* || children.size() < 5 */ ) {

      for(typename std::list<T>::iterator c_iter = children.begin();
          c_iter != children.end(); ++c_iter) {

        const BoundingBox & e_bb =
          get_bbox_trait_selector<is_pointer<T>::value>::get_bounding_box_for_object(*c_iter);

        os
          << gen_tabs(tabs) << "    + Element bounding box           : x = "
          << e_bb.get_min_x() << " .. " << e_bb.get_max_x()
          << " / y = "
          << e_bb.get_min_y() << " .. " << e_bb.get_max_y()
          << std::endl;
      }

      os << std::endl;
    }

    if(recursive) {
      for(typename std::vector<QuadTree<T> >::iterator stn_iter = subtree_nodes.begin();
          stn_iter != subtree_nodes.end(); ++stn_iter) {
        (*stn_iter).print(os, tabs+1);
      }
    }


  }

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename T >
region_iterator< T > degate::QuadTree< T >::region_iter_begin ( BoundingBox const &  bbox)

Get a region iterator to iterate over quatree objects.

Definition at line 461 of file QuadTree.h.

                                                                            {
    return region_iterator<T>(this, bbox);
  }
template<typename T >
region_iterator< T > degate::QuadTree< T >::region_iter_begin ( )

Get a region iterator to iterate over the complete quatree.

Definition at line 466 of file QuadTree.h.

                                                    {
    return region_iterator<T>(this, box);
  }
template<typename T >
region_iterator< T > degate::QuadTree< T >::region_iter_begin ( int  min_x,
int  max_x,
int  min_y,
int  max_y 
)

Get an interator to iterate over quadtree nodes down to the leafes.

Get an end marker for the iteration

See also:
down_iter_begin() Get a region iterator to iterate over quatree objects.

Definition at line 454 of file QuadTree.h.

Referenced by degate::Layer::exists_type_in_region(), degate::Layer::get_distance_to_gate_boundary(), degate::Layer::get_object_at_position(), degate::Layer::objects_begin(), and degate::Layer::region_begin().

                                                                                              {

    BoundingBox bbox(min_x, max_x, min_y, max_y);
    return region_iter_begin(bbox);
  }

Here is the caller graph for this function:

template<typename T >
region_iterator< T > degate::QuadTree< T >::region_iter_end ( )

Get an end marker for the region iteration.

Definition at line 471 of file QuadTree.h.

Referenced by degate::Layer::exists_type_in_region(), degate::Layer::get_distance_to_gate_boundary(), degate::Layer::get_object_at_position(), degate::Layer::objects_end(), and degate::Layer::region_end().

                                                  {
    return region_iterator<T>();
  }

Here is the caller graph for this function:

template<typename T >
ret_t degate::QuadTree< T >::reinsert_objects ( ) [private]

Definition at line 313 of file QuadTree.h.

References degate::RET_OK.

                                      {

    typename std::list<T> children_copy = children;

    children.clear();

    for(typename std::list<T>::iterator it = children_copy.begin();
        it != children_copy.end();
        ++it) {
      insert(*it);
    }

    return RET_OK;
  }
template<typename T>
ret_t degate::QuadTree< T >::remove ( T  object)

Remove an object from the quadtree.

Definition at line 362 of file QuadTree.h.

References degate::RET_ERR, and degate::RET_OK.

Referenced by degate::Layer::remove_object().

                                    {
    const BoundingBox & bbox =
      get_bbox_trait_selector<is_pointer<T>::value>::get_bounding_box_for_object(object);

    QuadTree<T> * found = traverse_downto_bounding_box(bbox);
    assert(found != NULL);
    if(found != NULL) {
      found->children.remove(object);

      if(!found->is_leave() &&
         found->subtree_nodes[NW].children.size() == 0 &&
         found->subtree_nodes[NE].children.size() == 0 &&
         found->subtree_nodes[SW].children.size() == 0 &&
         found->subtree_nodes[SE].children.size() == 0) {
        found->subtree_nodes.clear();
      }

      return RET_OK;
    }
    return RET_ERR;
  }

Here is the caller graph for this function:

template<typename T >
ret_t degate::QuadTree< T >::split ( ) [private]

Definition at line 271 of file QuadTree.h.

References debug(), degate::RET_ERR, degate::RET_OK, and TM.

                           {
    if(is_splitable()) {

      BoundingBox nw(box.get_min_x(), box.get_center_x(),
                     box.get_min_y(), box.get_center_y());


      BoundingBox sw(box.get_min_x(), box.get_center_x(),
                     box.get_center_y() + 1, box.get_max_y());


      BoundingBox ne(box.get_center_x() + 1, box.get_max_x(),
                     box.get_min_y(), box.get_center_y());


      BoundingBox se(box.get_center_x() + 1, box.get_max_x(),
                     box.get_center_y() + 1,  box.get_max_y());


      QuadTree<T> node_nw(nw, this, "NW", max_entries);
      QuadTree<T> node_ne(ne, this, "NE", max_entries);
      QuadTree<T> node_sw(sw, this, "SW", max_entries);
      QuadTree<T> node_se(se, this, "SE", max_entries);


      subtree_nodes.push_back(node_nw);
      subtree_nodes.push_back(node_ne);
      subtree_nodes.push_back(node_sw);
      subtree_nodes.push_back(node_se);

      return RET_OK;
    }

    debug(TM, "Failed to split a quadtree node of width %d and height %d that is %sa leave",
          box.get_width(),
          box.get_height(),
          is_leave() ? "" : "not ");
    assert(1 == 0);
    return RET_ERR;
  }

Here is the call graph for this function:

template<typename T >
unsigned int degate::QuadTree< T >::total_size ( ) const

Get the number of objects that are stored in a quadtree node and in all child nodes.

Definition at line 411 of file QuadTree.h.

Referenced by degate::QuadTree< quadtree_element_type >::is_empty().

                                             {
    unsigned int this_node = children.size();
    unsigned int sub_nodes = 0;
    if(!is_leave()) {
      for(typename std::vector< QuadTree<T> >::const_iterator it = subtree_nodes.begin();
          it != subtree_nodes.end();
          ++it) {
        sub_nodes += (*it).total_size();
      }
    }
    return this_node + sub_nodes;
  }

Here is the caller graph for this function:

template<typename T >
QuadTree< T > * degate::QuadTree< T >::traverse_downto_bounding_box ( BoundingBox const &  box) [private]

Definition at line 391 of file QuadTree.h.

References degate::BoundingBox::get_bounding_box(), and degate::BoundingBox::in_bounding_box().

                                                                                 {

    if(is_leave()) return this;

    for(typename std::vector< QuadTree<T> >::iterator it = subtree_nodes.begin();
        it != subtree_nodes.end();
        ++it) {

      const BoundingBox & sub_bbox = (*it).box.get_bounding_box();

      //if(sub_bbox.in_bounding_box(box)) { // sub_bbox within box?
        if(box.in_bounding_box(sub_bbox)) { // box within sub_bbox?
        return (*it).traverse_downto_bounding_box(box);
      }
    }
    //    assert(1 == 0);
    return this;
  }

Here is the call graph for this function:

Friends And Related Function Documentation

template<typename T>
friend class region_iterator< T > [friend]

Definition at line 69 of file QuadTree.h.

Member Data Documentation

template<typename T>
const unsigned int degate::QuadTree< T >::bbox_min_size = 10 [static, private]

Definition at line 79 of file QuadTree.h.

template<typename T>
BoundingBox degate::QuadTree< T >::box [private]

Definition at line 83 of file QuadTree.h.

template<typename T>
std::list<T> degate::QuadTree< T >::children [private]

Definition at line 85 of file QuadTree.h.

template<typename T>
unsigned int degate::QuadTree< T >::max_entries [private]

Definition at line 81 of file QuadTree.h.

template<typename T>
const int degate::QuadTree< T >::NE = 1 [static, private]

Definition at line 75 of file QuadTree.h.

template<typename T>
std::string degate::QuadTree< T >::node_name [private]

Definition at line 89 of file QuadTree.h.

Referenced by degate::QuadTree< quadtree_element_type >::get_name(), and degate::QuadTree< T >::QuadTree().

template<typename T>
const int degate::QuadTree< T >::NW = 0 [static, private]

Definition at line 74 of file QuadTree.h.

template<typename T>
QuadTree* degate::QuadTree< T >::parent [private]

Definition at line 87 of file QuadTree.h.

template<typename T>
const int degate::QuadTree< T >::SE = 3 [static, private]

Definition at line 77 of file QuadTree.h.

template<typename T>
std::vector<QuadTree<T> > degate::QuadTree< T >::subtree_nodes [private]

Definition at line 84 of file QuadTree.h.

Referenced by degate::region_iterator< T >::next_node(), and degate::down_iterator< T >::next_node().

template<typename T>
const int degate::QuadTree< T >::SW = 2 [static, private]

Definition at line 76 of file QuadTree.h.

The documentation for this class was generated from the following file:
Generated on Mon Apr 23 2012 17:10:19 for degate by  doxygen 1.7.4