degate  0.1.2
QuadTreeRegionIterator.h
Go to the documentation of this file.
00001 /* -*-c++-*-
00002 
00003  This file is part of the IC reverse engineering tool degate.
00004 
00005  Copyright 2008, 2009, 2010 by Martin Schobert
00006 
00007  Degate is free software: you can redistribute it and/or modify
00008  it under the terms of the GNU General Public License as published by
00009  the Free Software Foundation, either version 3 of the License, or
00010  any later version.
00011 
00012  Degate is distributed in the hope that it will be useful,
00013  but WITHOUT ANY WARRANTY; without even the implied warranty of
00014  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015  GNU General Public License for more details.
00016 
00017  You should have received a copy of the GNU General Public License
00018  along with degate. If not, see <http://www.gnu.org/licenses/>.
00019 
00020 */
00021 
00022 #ifndef __QUADTREEREGIONITERATOR_H__
00023 #define __QUADTREEREGIONITERATOR_H__
00024 
00025 // #define DEBUG_SHOW_ITER 1
00026 
00027 #include "QuadTree.h"
00028 
00029 namespace degate {
00030 
00031   template<typename T>
00032   class region_iterator : public std::iterator<std::forward_iterator_tag, T> {
00033 
00034   private:
00035     QuadTree<T> * node;
00036     bool done;
00037 
00038     typename std::list<T>::iterator children_iter;
00039     typename std::list<T>::iterator children_iter_end;
00040 
00041     std::list<QuadTree<T> *> open_list;
00042 
00043     BoundingBox search_bb;
00044 
00045     void next_node();
00046     void check_next_node();
00047     void next_child();
00048     void skip_non_matching_children();
00049 
00050   public:
00051     region_iterator();
00052     region_iterator(QuadTree<T> * node, BoundingBox const & bbox);
00053     virtual ~region_iterator() {}
00054     virtual region_iterator& operator=(const region_iterator& other);
00055     virtual region_iterator& operator++();
00056     virtual bool operator==(const region_iterator& other) const;
00057     virtual bool operator!=(const region_iterator& other) const;
00058     virtual T * operator->() const;
00059     virtual T operator*() const;
00060   };
00061 
00062 
00063   /**
00064    * Construct an iterator end.
00065    */
00066   template<typename T>
00067   region_iterator<T>::region_iterator() :
00068     node(NULL), done(true) {
00069   }
00070 
00071   template<typename T>
00072   region_iterator<T>::region_iterator(QuadTree<T> * _node, BoundingBox const & bbox) :
00073     node(NULL),
00074     done(false),
00075     search_bb(bbox) {
00076 
00077     assert(_node != NULL);
00078 
00079     open_list.push_back(_node);
00080     next_node();
00081     check_next_node();
00082     skip_non_matching_children();
00083   }
00084 
00085   template<typename T>
00086   void region_iterator<T>::next_node() {
00087 
00088     assert(node == NULL);
00089 
00090 
00091     if(open_list.empty()) {
00092       done = true;
00093     }
00094     else {
00095 
00096       do {
00097 #ifdef DEBUG_SHOW_ITER
00098         debug(TM, "get head from open list");
00099 #endif
00100         node = open_list.front();
00101         open_list.pop_front();
00102 
00103         // add subtree nodes to open list
00104         for(typename std::vector<QuadTree<T> >::iterator it = node->subtree_nodes.begin();
00105             it != node->subtree_nodes.end();
00106             ++it) {
00107 
00108           if((*it).box.intersects(search_bb)) {
00109 #ifdef DEBUG_SHOW_ITER
00110             debug(TM, "Put into open list: %s", (*it).get_name().c_str());
00111 #endif
00112             open_list.push_back(&*it);
00113           }
00114 
00115         }
00116 #ifdef DEBUG_SHOW_ITER
00117         debug(TM, "Current node is %s", node->get_name().c_str());
00118 #endif
00119         // reset iterator for current quadtree node
00120         children_iter = node->children.begin();
00121         children_iter_end = node->children.end();
00122 
00123         // the quadtree might contain empty nodes
00124       } while(children_iter == children_iter_end &&
00125               !open_list.empty());
00126 
00127       if(children_iter == children_iter_end &&
00128          open_list.empty()) {
00129         done = true;
00130         node = NULL;
00131       }
00132 
00133     }
00134   }
00135 
00136   template<typename T>
00137   void region_iterator<T>::check_next_node() {
00138 
00139     while(!done && children_iter == children_iter_end) {
00140       node = NULL;
00141       next_node();
00142     }
00143   }
00144 
00145   template<typename T>
00146   void region_iterator<T>::next_child() {
00147     if(!done) {
00148       check_next_node();
00149       ++children_iter;
00150       check_next_node();
00151     }
00152   }
00153 
00154   // if the precond is stay on a bounding-box matching child, then postcond is stay on it, too
00155   template<typename T>
00156   void region_iterator<T>::skip_non_matching_children() {
00157 #ifdef DEBUG_SHOW_ITER
00158     debug(TM, "in increment() done = %d, node = %p", done ? 1 : 0, node);
00159 #endif
00160     while(!done &&
00161           !search_bb.intersects(get_bbox_trait_selector<is_pointer<T>::value>::get_bounding_box_for_object(*children_iter))) {
00162 #ifdef DEBUG_SHOW_ITER
00163       debug(TM, "iterating over children in %s", node->get_name().c_str());
00164 #endif
00165       next_child();
00166 
00167     }
00168 #ifdef DEBUG_SHOW_ITER
00169     debug(TM, "return from increment()");
00170 #endif
00171   }
00172 
00173 
00174   template<typename T>
00175   region_iterator<T>& region_iterator<T>::operator++() {
00176 #ifdef DEBUG_SHOW_ITER
00177     debug(TM, "++ called");
00178 #endif
00179     next_child(); // one step ahead
00180     skip_non_matching_children();
00181     return (*this);
00182   }
00183 
00184   template<typename T>
00185   region_iterator<T>& region_iterator<T>::operator=(const region_iterator& other) {
00186     node = other.node;
00187     done = other.done;
00188     open_list = other.open_list;
00189     children_iter = other.children_iter;
00190     children_iter_end = other.children_iter_end;
00191     return(*this);
00192   }
00193 
00194   template<typename T>
00195   bool region_iterator<T>::operator==(const region_iterator& other) const {
00196 
00197     if(done == true && other.done == true)
00198       return true;
00199     else
00200       return (node == other.node &&
00201               children_iter == other.children_iter &&
00202               open_list == other.open_list &&
00203               done == other.done);
00204   }
00205 
00206 
00207   template<typename T>
00208   bool region_iterator<T>::operator!=(const region_iterator& other) const {
00209     return !(*this == other);
00210   }
00211 
00212   template<typename T>
00213   T * region_iterator<T>::operator->() const {
00214     return &*children_iter;
00215   }
00216 
00217   template<typename T>
00218   T region_iterator<T>::operator*() const {
00219     return *children_iter;
00220   }
00221 
00222 }
00223 
00224 #endif
00225