degate  0.1.2
QuadTreeDownIterator.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 __QUADTREEDOWNITERATOR_H__
00023 #define __QUADTREEDOWNITERATOR_H__
00024 
00025 #include "QuadTree.h"
00026 
00027 namespace degate {
00028 
00029 template<typename T>
00030 class down_iterator : public std::iterator<std::forward_iterator_tag, T> {
00031 
00032  private:
00033   QuadTree<T> * node;
00034   bool done;
00035 
00036   typename std::list<T>::iterator children_iter;
00037   typename std::list<T>::iterator children_iter_end;
00038 
00039   std::list<QuadTree<T> *> open_list;
00040 
00041   void next_node();
00042 
00043  public:
00044   down_iterator();
00045   down_iterator(QuadTree<T> * node);
00046   virtual ~down_iterator() {}
00047   virtual down_iterator& operator=(const down_iterator& other);
00048   virtual down_iterator& operator++();
00049   virtual bool operator==(const down_iterator& other) const;
00050   virtual bool operator!=(const down_iterator& other) const;
00051   virtual T * operator->() const;
00052   virtual T operator*() const;
00053 };
00054 
00055 
00056 template<typename T>
00057 down_iterator<T>::down_iterator() : node(NULL), done(true) {
00058 }
00059 
00060 template<typename T>
00061 down_iterator<T>::down_iterator(QuadTree<T> * _node) :
00062   node(NULL),
00063   done(false) {
00064 
00065   assert(_node != NULL);
00066 
00067   open_list.push_back(_node);
00068   next_node();
00069 }
00070 
00071 template<typename T>
00072 void down_iterator<T>::next_node() {
00073   if(node == NULL) {
00074     if(open_list.size() > 0) {
00075       node = open_list.front();
00076       open_list.pop_front();
00077 
00078       // add subtree nodes to open list
00079       for(typename std::vector<QuadTree<T> >::iterator it = node->subtree_nodes.begin();
00080           it != node->subtree_nodes.end();
00081           ++it)
00082         open_list.push_back(&*it);
00083 
00084       // reset iterator for current
00085       children_iter = node->children.begin();
00086       children_iter_end = node->children.end();
00087 
00088       if(children_iter == children_iter_end) {
00089         done = true;
00090       }
00091 
00092     }
00093     else {
00094       done = true;
00095     }
00096   }
00097 
00098 }
00099 
00100 template<typename T>
00101 down_iterator<T>& down_iterator<T>::operator++() {
00102 
00103   if(!done) {
00104     ++children_iter;
00105   }
00106 
00107   if(!done && children_iter == children_iter_end) {
00108     node = NULL;
00109     next_node();
00110   }
00111 
00112 
00113   return (*this);
00114 }
00115 
00116 template<typename T>
00117 down_iterator<T>& down_iterator<T>::operator=(const down_iterator& other) {
00118   node = other.node;
00119   done = other.done;
00120   open_list = other.open_list;
00121   children_iter = other.children_iter;
00122   children_iter_end = other.children_iter_end;
00123   return(*this);
00124 }
00125 
00126 template<typename T>
00127 bool down_iterator<T>::operator==(const down_iterator& other) const {
00128 
00129   if(done == true && other.done == true)
00130     return true;
00131   else
00132     return (node == other.node &&
00133             children_iter == other.children_iter &&
00134             open_list == other.open_list &&
00135             done == other.done);
00136 }
00137 
00138 
00139 template<typename T>
00140 bool down_iterator<T>::operator!=(const down_iterator& other) const {
00141   return !(*this == other);
00142 }
00143 
00144 template<typename T>
00145 T * down_iterator<T>::operator->() const {
00146   return &*children_iter;
00147 }
00148 
00149 template<typename T>
00150 T down_iterator<T>::operator*() const {
00151   return *children_iter;
00152 }
00153 
00154 }
00155 
00156 #endif
00157