degate  0.1.2
QuadTree.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    Copyright 2012 Robert Nitsch
00007 
00008    Degate is free software: you can redistribute it and/or modify
00009    it under the terms of the GNU General Public License as published by
00010    the Free Software Foundation, either version 3 of the License, or
00011    any later version.
00012 
00013    Degate is distributed in the hope that it will be useful,
00014    but WITHOUT ANY WARRANTY; without even the implied warranty of
00015    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00016    GNU General Public License for more details.
00017 
00018    You should have received a copy of the GNU General Public License
00019    along with degate. If not, see <http://www.gnu.org/licenses/>.
00020 
00021 */
00022 
00023 
00024 #ifndef __QUADTREE_H__
00025 #define __QUADTREE_H__
00026 
00027 #include "Rectangle.h"
00028 #include "TypeTraits.h"
00029 
00030 #include <algorithm>
00031 #include <vector>
00032 #include <list>
00033 #include <assert.h>
00034 #include "globals.h"
00035 #include <iostream>
00036 
00037 namespace degate {
00038 
00039 
00040   template<bool b>
00041   struct get_bbox_trait_selector {
00042     template<typename T>
00043     static BoundingBox const & get_bounding_box_for_object(T object) {
00044       return object.get_bounding_box();
00045     }
00046   };
00047 
00048   template <>
00049   struct get_bbox_trait_selector<true> {
00050     template<typename T>
00051     static BoundingBox const & get_bounding_box_for_object(T object) {
00052       return object->get_bounding_box();
00053     }
00054   };
00055 
00056 
00057   template <typename T> class QuadTree;
00058 }
00059 
00060 //#include "QuadTreeDownIterator.h"
00061 #include "QuadTreeRegionIterator.h"
00062 
00063 namespace degate {
00064 
00065   /**
00066    * Quad tree to store objects and to accesss them with a two dimensional access path.
00067    */
00068   template <typename T>
00069   class QuadTree {
00070 
00071     friend class region_iterator<T>;
00072     //    friend class down_iterator<T>;
00073 
00074   private:
00075 
00076     const static int NW = 0;
00077     const static int NE = 1;
00078     const static int SW = 2;
00079     const static int SE = 3;
00080 
00081     const static unsigned int bbox_min_size = 10;
00082 
00083     unsigned int max_entries;
00084 
00085     BoundingBox box;
00086     std::vector<QuadTree<T> > subtree_nodes;
00087     std::list<T> children;
00088 
00089     QuadTree * parent;
00090 
00091     std::string node_name;
00092 
00093     QuadTree(BoundingBox const & box, QuadTree * parent, std::string node_name, int max_entries = 50);
00094 
00095     QuadTree<T> * traverse_downto_bounding_box(BoundingBox const & box);
00096 
00097     ret_t split();
00098     ret_t reinsert_objects();
00099 
00100     bool is_splitable() const;
00101 
00102   public:
00103 
00104     const std::string get_name() const { return node_name; }
00105 
00106     /**
00107      * Create a new quadtree.
00108      * @param box The bounding box defines the dimension of the quadtree.
00109      * @param max_entries Defines how many objects should be stored in a quadtree node, before
00110      *    the node is splitted. This value is not a hard limit. The quadtree can ignore this
00111      *    parameter, if it has no choice.
00112      */
00113 
00114     QuadTree(BoundingBox const & box, int max_entries = 50);
00115 
00116     /**
00117      * Destruct a quadtree.
00118      */
00119 
00120     ~QuadTree();
00121 
00122     void get_all_elements(std::vector<T> &vec) const;
00123     
00124     /**
00125      * Check if the quadtree or a quadtree node is a leaf node.
00126      */
00127 
00128     bool is_leave() const;
00129 
00130     /**
00131      * Insert an object into the quadtree.
00132      */
00133 
00134     ret_t insert(T object);
00135 
00136     /**
00137      * Remove an object from the quadtree.
00138      */
00139 
00140     ret_t remove(T object);
00141 
00142 
00143     /**
00144      * Notify that the bounding box of an object changed.
00145      * It might be neccessary to adjust the objects position in the quadtree.
00146      */
00147 
00148     void notify_shape_change(T object);
00149 
00150     /**
00151      * Get the number of objects that are stored in a quadtree node and in all child nodes.
00152      */
00153 
00154     unsigned int total_size() const;
00155 
00156     /**
00157      * Get the number of layers, that quadtree has.
00158      */
00159 
00160     unsigned int depth() const;
00161 
00162     /*
00163      * Check if there are objects stored in the quadtree.
00164      */
00165 
00166     bool is_empty() const { return total_size() == 0; }
00167 
00168     /**
00169      * Get the dimension of the quadtree.
00170      */
00171 
00172     unsigned int get_width() const;
00173 
00174     /**
00175      * Get the dimension of the quadtree.
00176      */
00177 
00178     unsigned int get_height() const;
00179 
00180 
00181     /**
00182      * Get an interator to iterate over quadtree nodes down to the leafes.
00183      */
00184 
00185     //    down_iterator<T> down_iter_begin();
00186 
00187     /**
00188      * Get an end marker for the iteration
00189      * @see down_iter_begin()
00190      */
00191 
00192     //    down_iterator<T> down_iter_end();
00193 
00194     /**
00195      * Get a region iterator to iterate over quatree objects.
00196      */
00197 
00198 
00199     region_iterator<T> region_iter_begin(int min_x, int max_x, int min_y, int max_y);
00200 
00201     /**
00202      * Get a region iterator to iterate over quatree objects.
00203      */
00204 
00205     region_iterator<T> region_iter_begin(BoundingBox const & bbox);
00206 
00207     /**
00208      * Get a region iterator to iterate over the complete quatree.
00209      */
00210 
00211     region_iterator<T> region_iter_begin();
00212 
00213     /**
00214      * Get an end marker for the region iteration.
00215      */
00216 
00217     region_iterator<T> region_iter_end();
00218 
00219 
00220     /**
00221      * Get the bounding box for a quad tree layer.
00222      */
00223     BoundingBox const& get_bounding_box() const;
00224       
00225     /**
00226      * Print the quadtree.
00227      */
00228     void print(std::ostream & os = std::cout, int tabs = 0, bool recursive = false);
00229 
00230   };
00231 
00232 
00233 
00234 
00235   template <typename T>
00236   QuadTree<T>::QuadTree(BoundingBox const & box, int max_entries) {
00237     this->box = box;
00238     this->max_entries = max_entries;
00239     parent = NULL;
00240     node_name = "/";
00241   }
00242 
00243   template <typename T>
00244   QuadTree<T>::QuadTree(BoundingBox const & box, QuadTree * parent, std::string _node_name, int max_entries) {
00245     this->box = box;
00246     this->max_entries = max_entries;
00247     this->parent = parent;
00248 
00249     node_name = parent->node_name + std::string("/") + _node_name;
00250   }
00251 
00252   template <typename T>
00253   QuadTree<T>::~QuadTree() {
00254   }
00255   
00256   template <typename T>
00257   void QuadTree<T>::get_all_elements(std::vector<T> &vec) const {
00258     std::copy(children.begin(), children.end(), back_inserter(vec));
00259     std::for_each(subtree_nodes.begin(), subtree_nodes.end(), [&vec](const QuadTree<T> &q) {
00260       q.get_all_elements(vec);
00261     });
00262   }
00263 
00264   template <typename T>
00265   unsigned int QuadTree<T>::get_width() const {
00266     return box.get_width();
00267   }
00268 
00269   template <typename T>
00270   unsigned int QuadTree<T>::get_height() const {
00271     return box.get_height();
00272   }
00273 
00274 
00275   template <typename T>
00276   bool QuadTree<T>::is_splitable() const {
00277     return box.get_width() > bbox_min_size &&
00278       box.get_height() > bbox_min_size &&
00279       is_leave();
00280   }
00281 
00282   template <typename T>
00283   ret_t QuadTree<T>::split() {
00284     if(is_splitable()) {
00285 
00286       BoundingBox nw(box.get_min_x(), box.get_center_x(),
00287                      box.get_min_y(), box.get_center_y());
00288 
00289 
00290       BoundingBox sw(box.get_min_x(), box.get_center_x(),
00291                      box.get_center_y() + 1, box.get_max_y());
00292 
00293 
00294       BoundingBox ne(box.get_center_x() + 1, box.get_max_x(),
00295                      box.get_min_y(), box.get_center_y());
00296 
00297 
00298       BoundingBox se(box.get_center_x() + 1, box.get_max_x(),
00299                      box.get_center_y() + 1,  box.get_max_y());
00300 
00301 
00302       QuadTree<T> node_nw(nw, this, "NW", max_entries);
00303       QuadTree<T> node_ne(ne, this, "NE", max_entries);
00304       QuadTree<T> node_sw(sw, this, "SW", max_entries);
00305       QuadTree<T> node_se(se, this, "SE", max_entries);
00306 
00307 
00308       subtree_nodes.push_back(node_nw);
00309       subtree_nodes.push_back(node_ne);
00310       subtree_nodes.push_back(node_sw);
00311       subtree_nodes.push_back(node_se);
00312 
00313       return RET_OK;
00314     }
00315 
00316     debug(TM, "Failed to split a quadtree node of width %d and height %d that is %sa leave",
00317           box.get_width(),
00318           box.get_height(),
00319           is_leave() ? "" : "not ");
00320     assert(1 == 0);
00321     return RET_ERR;
00322   }
00323 
00324   template <typename T>
00325   ret_t QuadTree<T>::reinsert_objects() {
00326 
00327     typename std::list<T> children_copy = children;
00328 
00329     children.clear();
00330 
00331     for(typename std::list<T>::iterator it = children_copy.begin();
00332         it != children_copy.end();
00333         ++it) {
00334       insert(*it);
00335     }
00336 
00337     return RET_OK;
00338   }
00339 
00340   template <typename T>
00341   ret_t QuadTree<T>::insert(T object) {
00342 
00343     ret_t ret;
00344     const BoundingBox & bbox =
00345       get_bbox_trait_selector<is_pointer<T>::value>::get_bounding_box_for_object(object);
00346 
00347     QuadTree<T> * found = traverse_downto_bounding_box(bbox);
00348     assert(found != NULL);
00349 
00350     if(found != NULL) {
00351 
00352       if((found->children.size() >= max_entries) && found->is_splitable()) {
00353 
00354         if(RET_IS_NOT_OK(ret = found->split())) return ret;
00355         if(RET_IS_NOT_OK(ret = found->reinsert_objects())) return ret;
00356         if(RET_IS_NOT_OK(ret = found->insert(object))) return ret;
00357         return RET_OK;
00358       }
00359       else {
00360         found->children.push_back(object);
00361         return RET_OK;
00362       }
00363     }
00364     return RET_ERR;
00365   }
00366 
00367   template <typename T>
00368   void QuadTree<T>::notify_shape_change(T object) {
00369     remove(object);
00370     insert(object);
00371   }
00372 
00373   template <typename T>
00374   ret_t QuadTree<T>::remove(T object) {
00375     const BoundingBox & bbox =
00376       get_bbox_trait_selector<is_pointer<T>::value>::get_bounding_box_for_object(object);
00377 
00378     QuadTree<T> * found = traverse_downto_bounding_box(bbox);
00379     assert(found != NULL);
00380     if(found != NULL) {
00381       found->children.remove(object);
00382 
00383       if(!found->is_leave() &&
00384          found->subtree_nodes[NW].children.size() == 0 &&
00385          found->subtree_nodes[NE].children.size() == 0 &&
00386          found->subtree_nodes[SW].children.size() == 0 &&
00387          found->subtree_nodes[SE].children.size() == 0) {
00388         found->subtree_nodes.clear();
00389       }
00390 
00391       return RET_OK;
00392     }
00393     return RET_ERR;
00394   }
00395 
00396 
00397   template <typename T>
00398   bool QuadTree<T>::is_leave() const {
00399     return subtree_nodes.size() == 4 ? false : true;
00400   }
00401 
00402   template <typename T>
00403   QuadTree<T> * QuadTree<T>::traverse_downto_bounding_box(BoundingBox const & box) {
00404 
00405     if(is_leave()) return this;
00406 
00407     for(typename std::vector< QuadTree<T> >::iterator it = subtree_nodes.begin();
00408         it != subtree_nodes.end();
00409         ++it) {
00410 
00411       const BoundingBox & sub_bbox = (*it).box.get_bounding_box();
00412 
00413       //if(sub_bbox.in_bounding_box(box)) { // sub_bbox within box?
00414         if(box.in_bounding_box(sub_bbox)) { // box within sub_bbox?
00415         return (*it).traverse_downto_bounding_box(box);
00416       }
00417     }
00418     //    assert(1 == 0);
00419     return this;
00420   }
00421 
00422   template <typename T>
00423   unsigned int QuadTree<T>::total_size() const {
00424     unsigned int this_node = children.size();
00425     unsigned int sub_nodes = 0;
00426     if(!is_leave()) {
00427       for(typename std::vector< QuadTree<T> >::const_iterator it = subtree_nodes.begin();
00428           it != subtree_nodes.end();
00429           ++it) {
00430         sub_nodes += (*it).total_size();
00431       }
00432     }
00433     return this_node + sub_nodes;
00434   }
00435 
00436   template <typename T>
00437   unsigned int QuadTree<T>::depth() const {
00438 
00439     unsigned int max_d = 0;
00440     if(!is_leave()) {
00441       for(typename std::vector< QuadTree<T> >::const_iterator it = subtree_nodes.begin();
00442           it != subtree_nodes.end();
00443           ++it) {
00444 
00445         unsigned int d = (*it).depth();
00446         max_d = std::max(max_d, d);
00447       }
00448     }
00449     return 1 + max_d;
00450   }
00451 
00452 
00453   /*
00454   template <typename T>
00455   down_iterator<T> QuadTree<T>::down_iter_begin() {
00456     return down_iterator<T>(this);
00457   }
00458 
00459   template <typename T>
00460   down_iterator<T> QuadTree<T>::down_iter_end() {
00461     return down_iterator<T>();
00462   }
00463   */
00464 
00465   template <typename T>
00466   region_iterator<T> QuadTree<T>::region_iter_begin(int min_x, int max_x, int min_y, int max_y) {
00467 
00468     BoundingBox bbox(min_x, max_x, min_y, max_y);
00469     return region_iter_begin(bbox);
00470   }
00471 
00472   template <typename T>
00473   region_iterator<T> QuadTree<T>::region_iter_begin(BoundingBox const & bbox) {
00474     return region_iterator<T>(this, bbox);
00475   }
00476 
00477   template <typename T>
00478   region_iterator<T> QuadTree<T>::region_iter_begin() {
00479     return region_iterator<T>(this, box);
00480   }
00481 
00482   template <typename T>
00483   region_iterator<T> QuadTree<T>::region_iter_end() {
00484     return region_iterator<T>();
00485   }
00486 
00487 
00488   template <typename T>
00489   BoundingBox const& QuadTree<T>::get_bounding_box() const {
00490     return box;
00491   }
00492 
00493   template <typename T>
00494   void QuadTree<T>::print(std::ostream & os, int tabs, bool recursive) {
00495 
00496     os
00497       << gen_tabs(tabs) << "Node name                      : " << get_name() << std::endl
00498       << gen_tabs(tabs) << "Bounding box                   : x = "
00499       << box.get_min_x() << " .. " << box.get_max_x()
00500       << " / y = "
00501       << box.get_min_y() << " .. " << box.get_max_y()
00502       << std::endl
00503 
00504       << gen_tabs(tabs) << "Num elements in this node      : " << children.size() << std::endl
00505       << gen_tabs(tabs) << "Preferred max num of elements : " << max_entries << std::endl
00506       << std::endl
00507       ;
00508 
00509     if(parent == NULL /* || children.size() < 5 */ ) {
00510 
00511       for(typename std::list<T>::iterator c_iter = children.begin();
00512           c_iter != children.end(); ++c_iter) {
00513 
00514         const BoundingBox & e_bb =
00515           get_bbox_trait_selector<is_pointer<T>::value>::get_bounding_box_for_object(*c_iter);
00516 
00517         os
00518           << gen_tabs(tabs) << "    + Element bounding box           : x = "
00519           << e_bb.get_min_x() << " .. " << e_bb.get_max_x()
00520           << " / y = "
00521           << e_bb.get_min_y() << " .. " << e_bb.get_max_y()
00522           << std::endl;
00523       }
00524 
00525       os << std::endl;
00526     }
00527 
00528     if(recursive) {
00529       for(typename std::vector<QuadTree<T> >::iterator stn_iter = subtree_nodes.begin();
00530           stn_iter != subtree_nodes.end(); ++stn_iter) {
00531         (*stn_iter).print(os, tabs+1);
00532       }
00533     }
00534 
00535 
00536   }
00537 
00538   /* missing:
00539      - get object(s) at
00540      - find object (?)
00541   */
00542 
00543 }
00544 
00545 #endif