#include <QuadTreeRegionIterator.h>

Public Member Functions
	region_iterator ()
	Construct an iterator end.
	region_iterator (QuadTree< T > *node, BoundingBox const &bbox)
virtual	~region_iterator ()
virtual region_iterator &	operator= (const region_iterator &other)
virtual region_iterator &	operator++ ()
virtual bool	operator== (const region_iterator &other) const
virtual bool	operator!= (const region_iterator &other) const
virtual T *	operator-> () const
virtual T	operator* () const
Private Member Functions
void	next_node ()
void	check_next_node ()
void	next_child ()
void	skip_non_matching_children ()
Private Attributes
QuadTree< T > *	node
bool	done
std::list< T >::iterator	children_iter
std::list< T >::iterator	children_iter_end
std::list< QuadTree< T > * >	open_list
BoundingBox	search_bb

Detailed Description

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

Definition at line 32 of file QuadTreeRegionIterator.h.

Constructor & Destructor Documentation

template<typename T >

degate::region_iterator< T >::region_iterator ( )

Construct an iterator end.

Definition at line 67 of file QuadTreeRegionIterator.h.

                                      :
    node(NULL), done(true) {
  }

template<typename T >

degate::region_iterator< T >::region_iterator	(	QuadTree< T > *	node,
		BoundingBox const &	bbox
	)

Definition at line 72 of file QuadTreeRegionIterator.h.

References degate::region_iterator< T >::check_next_node(), degate::region_iterator< T >::next_node(), degate::region_iterator< T >::open_list, and degate::region_iterator< T >::skip_non_matching_children().

                                                                                   :
    node(NULL),
    done(false),
    search_bb(bbox) {

    assert(_node != NULL);

    open_list.push_back(_node);
    next_node();
    check_next_node();
    skip_non_matching_children();
  }

Here is the call graph for this function:

template<typename T>

virtual degate::region_iterator< T >::~region_iterator ( ) [inline, virtual]

Definition at line 53 of file QuadTreeRegionIterator.h.

{}

Member Function Documentation

template<typename T >

void degate::region_iterator< T >::check_next_node ( ) [private]

Definition at line 137 of file QuadTreeRegionIterator.h.

Referenced by degate::region_iterator< T >::region_iterator().

                                           {

    while(!done && children_iter == children_iter_end) {
      node = NULL;
      next_node();
    }
  }

Here is the caller graph for this function:

template<typename T >

void degate::region_iterator< T >::next_child ( ) [private]

Definition at line 146 of file QuadTreeRegionIterator.h.

                                      {
    if(!done) {
      check_next_node();
      ++children_iter;
      check_next_node();
    }
  }

template<typename T >

void degate::region_iterator< T >::next_node ( ) [private]

Definition at line 86 of file QuadTreeRegionIterator.h.

References debug(), degate::QuadTree< T >::subtree_nodes, and TM.

Referenced by degate::region_iterator< T >::region_iterator().

                                     {

    assert(node == NULL);


    if(open_list.empty()) {
      done = true;
    }
    else {

      do {
#ifdef DEBUG_SHOW_ITER
        debug(TM, "get head from open list");
#endif
        node = open_list.front();
        open_list.pop_front();

        // add subtree nodes to open list
        for(typename std::vector<QuadTree<T> >::iterator it = node->subtree_nodes.begin();
            it != node->subtree_nodes.end();
            ++it) {

          if((*it).box.intersects(search_bb)) {
#ifdef DEBUG_SHOW_ITER
            debug(TM, "Put into open list: %s", (*it).get_name().c_str());
#endif
            open_list.push_back(&*it);
          }

        }
#ifdef DEBUG_SHOW_ITER
        debug(TM, "Current node is %s", node->get_name().c_str());
#endif
        // reset iterator for current quadtree node
        children_iter = node->children.begin();
        children_iter_end = node->children.end();

        // the quadtree might contain empty nodes
      } while(children_iter == children_iter_end &&
              !open_list.empty());

      if(children_iter == children_iter_end &&
         open_list.empty()) {
        done = true;
        node = NULL;
      }

    }
  }

Here is the call graph for this function:

Here is the caller graph for this function:

template<typename T >

bool degate::region_iterator< T >::operator!= ( const region_iterator< T > & other ) const [virtual]

Definition at line 208 of file QuadTreeRegionIterator.h.

                                                                        {
    return !(*this == other);
  }

template<typename T >

T degate::region_iterator< T >::operator* ( ) const [virtual]

Definition at line 218 of file QuadTreeRegionIterator.h.

                                        {
    return *children_iter;
  }

template<typename T >

region_iterator< T > & degate::region_iterator< T >::operator++ ( ) [virtual]

Definition at line 175 of file QuadTreeRegionIterator.h.

References debug(), and TM.

                                                     {
#ifdef DEBUG_SHOW_ITER
    debug(TM, "++ called");
#endif
    next_child(); // one step ahead
    skip_non_matching_children();
    return (*this);
  }

Here is the call graph for this function:

template<typename T >

T * degate::region_iterator< T >::operator-> ( ) const [virtual]

Definition at line 213 of file QuadTreeRegionIterator.h.

                                           {
    return &*children_iter;
  }

template<typename T >

region_iterator< T > & degate::region_iterator< T >::operator= ( const region_iterator< T > & other ) [virtual]

Definition at line 185 of file QuadTreeRegionIterator.h.

References degate::region_iterator< T >::children_iter, degate::region_iterator< T >::children_iter_end, degate::region_iterator< T >::done, degate::region_iterator< T >::node, and degate::region_iterator< T >::open_list.

                                                                                {
    node = other.node;
    done = other.done;
    open_list = other.open_list;
    children_iter = other.children_iter;
    children_iter_end = other.children_iter_end;
    return(*this);
  }

template<typename T >

bool degate::region_iterator< T >::operator== ( const region_iterator< T > & other ) const [virtual]

Definition at line 195 of file QuadTreeRegionIterator.h.

References degate::region_iterator< T >::children_iter, degate::region_iterator< T >::done, degate::region_iterator< T >::node, and degate::region_iterator< T >::open_list.

                                                                        {

    if(done == true && other.done == true)
      return true;
    else
      return (node == other.node &&
              children_iter == other.children_iter &&
              open_list == other.open_list &&
              done == other.done);
  }

template<typename T >

void degate::region_iterator< T >::skip_non_matching_children ( ) [private]

Definition at line 156 of file QuadTreeRegionIterator.h.

References debug(), and TM.

Referenced by degate::region_iterator< T >::region_iterator().

                                                      {
#ifdef DEBUG_SHOW_ITER
    debug(TM, "in increment() done = %d, node = %p", done ? 1 : 0, node);
#endif
    while(!done &&
          !search_bb.intersects(get_bbox_trait_selector<is_pointer<T>::value>::get_bounding_box_for_object(*children_iter))) {
#ifdef DEBUG_SHOW_ITER
      debug(TM, "iterating over children in %s", node->get_name().c_str());
#endif
      next_child();

    }
#ifdef DEBUG_SHOW_ITER
    debug(TM, "return from increment()");
#endif
  }