Main Page   Modules   Namespace List   Class Hierarchy   Compound List   File List   Namespace Members   Compound Members   File Members   Related Pages  

HeapT.hh

Go to the documentation of this file.
00001 //=============================================================================
00002 //                                                                            
00003 //                               OpenMesh                                     
00004 //        Copyright (C) 2003 by Computer Graphics Group, RWTH Aachen          
00005 //                           www.openmesh.org                                 
00006 //                                                                            
00007 //-----------------------------------------------------------------------------
00008 //                                                                            
00009 //                                License                                     
00010 //                                                                            
00011 //   This library is free software; you can redistribute it and/or modify it 
00012 //   under the terms of the GNU Library General Public License as published  
00013 //   by the Free Software Foundation, version 2.                             
00014 //                                                                             
00015 //   This library is distributed in the hope that it will be useful, but       
00016 //   WITHOUT ANY WARRANTY; without even the implied warranty of                
00017 //   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU         
00018 //   Library General Public License for more details.                          
00019 //                                                                            
00020 //   You should have received a copy of the GNU Library General Public         
00021 //   License along with this library; if not, write to the Free Software       
00022 //   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.                 
00023 //                                                                            
00024 //-----------------------------------------------------------------------------
00025 //                                                                            
00026 //   $Revision: 1.4 $
00027 //   $Date: 2004/01/13 15:23:32 $
00028 //                                                                            
00029 //=============================================================================
00030 
00035 //=============================================================================
00036 //
00037 //  CLASS HeapT
00038 //
00039 //=============================================================================
00040 
00041 #ifndef OPENMESH_UTILS_HEAPT_HH
00042 #define OPENMESH_UTILS_HEAPT_HH
00043 
00044 
00045 //== INCLUDES =================================================================
00046 
00047 #include "Config.hh"
00048 #include <vector>
00049 #include <OpenMesh/Core/System/omstream.hh>
00050 
00051 //== NAMESPACE ================================================================
00052 
00053 namespace OpenMesh { // BEGIN_NS_OPENMESH
00054 namespace Utils { // BEGIN_NS_UTILS
00055 
00056 //== CLASS DEFINITION =========================================================
00057 
00058 
00067 template <class HeapEntry>
00068 struct HeapInterfaceT
00069 {
00071   bool less(const HeapEntry& _e1, const HeapEntry& _e2);
00072 
00074   bool greater(const HeapEntry& _e1, const HeapEntry& _e2);
00075 
00077   int  get_heap_position(const HeapEntry& _e);
00078 
00080   void set_heap_position(HeapEntry& _e, int _i);
00081 };
00082 
00083 
00084 
00106 template <class HeapEntry, class HeapInterface=HeapEntry>
00107 class HeapT : private std::vector<HeapEntry>
00108 {
00109 public:
00110 
00112   HeapT() : HeapVector() {}
00113   
00115   HeapT(const HeapInterface& _interface)
00116     : HeapVector(),  interface_(_interface)
00117   {}
00118   
00120   ~HeapT(){};
00121 
00122 
00124   void clear() { HeapVector::clear(); }
00125 
00127   bool empty() { return HeapVector::empty(); }
00128 
00130   unsigned int size() { return HeapVector::size(); }
00131 
00133   void reserve(unsigned int _n) { HeapVector::reserve(_n); }
00134 
00136   void reset_heap_position(HeapEntry _h)
00137   { interface_.set_heap_position(_h, -1); }
00138   
00140   bool is_stored(HeapEntry _h)
00141   { return interface_.get_heap_position(_h) != -1; }
00142   
00144   void insert(HeapEntry _h)  { push_back(_h); upheap(size()-1); }
00145 
00147   HeapEntry front() { assert(!empty()); return entry(0); }
00148 
00150   void pop_front()
00151   {    
00152     assert(!empty());
00153     interface_.set_heap_position(entry(0), -1);
00154     if (size() > 1)
00155     {
00156       entry(0, entry(size()-1));
00157       resize(size()-1);
00158       downheap(0);
00159     }
00160     else resize(size()-1);
00161   }
00162 
00164   void remove(HeapEntry _h)
00165   {
00166     int pos = interface_.get_heap_position(_h);
00167     interface_.set_heap_position(_h, -1);
00168 
00169     assert(pos != -1);
00170     assert((unsigned int) pos < size());
00171     
00172     // last item ?
00173     if ((unsigned int) pos == size()-1)
00174       resize(size()-1);
00175 
00176     else {
00177       entry(pos, entry(size()-1)); // move last elem to pos
00178       resize(size()-1);
00179       downheap(pos);
00180       upheap(pos);
00181     }
00182   }
00183 
00187   void update(HeapEntry _h)
00188   {
00189     int pos = interface_.get_heap_position(_h);
00190     assert(pos != -1);
00191     assert((unsigned int)pos < size());
00192     downheap(pos);
00193     upheap(pos);
00194   }
00195   
00197   bool check()
00198   {
00199     bool ok(true);
00200     unsigned int i, j;
00201     for (i=0; i<size(); ++i)
00202     {
00203       if (((j=left(i))<size()) && interface_.greater(entry(i), entry(j))) 
00204       {
00205         omerr << "Heap condition violated\n";
00206         ok=false;
00207       }
00208       if (((j=right(i))<size()) && interface_.greater(entry(i), entry(j)))
00209       {
00210         omerr << "Heap condition violated\n";
00211         ok=false;
00212       }
00213     }
00214     return ok;
00215   }
00216   
00217   
00218 private:
00219 
00220   // typedef
00221   typedef std::vector<HeapEntry> HeapVector;
00222 
00223   
00225   void upheap(unsigned int _idx);
00226 
00227   
00229   void downheap(unsigned int _idx);
00230 
00231   
00233   inline HeapEntry entry(unsigned int _idx) {
00234     assert(_idx < size());
00235     return (operator[](_idx));
00236   }
00237 
00238   
00240   inline void entry(unsigned int _idx, HeapEntry _h) {
00241     assert(_idx < size());
00242     operator[](_idx) = _h;
00243     interface_.set_heap_position(_h, _idx);
00244   }
00245 
00246   
00248   inline unsigned int parent(unsigned int _i) { return (_i-1)>>1; }
00250   inline unsigned int left(unsigned int _i)   { return (_i<<1)+1; }
00252   inline unsigned int right(unsigned int _i)  { return (_i<<1)+2; }
00253 
00254 
00256   HeapInterface  interface_;
00257 };
00258 
00259 
00260 
00261 
00262 //== IMPLEMENTATION ========================================================== 
00263 
00264 
00265 template <class HeapEntry, class HeapInterface>
00266 void
00267 HeapT<HeapEntry, HeapInterface>::
00268 upheap(unsigned int _idx)
00269 {
00270   HeapEntry     h = entry(_idx);
00271   unsigned int  parentIdx;
00272 
00273   while ((_idx>0) &&
00274          interface_.less(h, entry(parentIdx=parent(_idx))))
00275   {
00276     entry(_idx, entry(parentIdx));
00277     _idx = parentIdx;    
00278   }
00279   
00280   entry(_idx, h);
00281 }
00282   
00283 
00284 //-----------------------------------------------------------------------------
00285 
00286   
00287 template <class HeapEntry, class HeapInterface>
00288 void
00289 HeapT<HeapEntry, HeapInterface>::
00290 downheap(unsigned int _idx)
00291 {
00292   HeapEntry     h = entry(_idx);
00293   unsigned int  childIdx;
00294   unsigned int  s = size();
00295   
00296   while(_idx < s)
00297   {
00298     childIdx = left(_idx);
00299     if (childIdx >= s) break;
00300     
00301     if ((childIdx+1 < s) &&
00302         (interface_.less(entry(childIdx+1), entry(childIdx))))
00303       ++childIdx;
00304     
00305     if (interface_.less(h, entry(childIdx))) break;
00306 
00307     entry(_idx, entry(childIdx));
00308     _idx = childIdx;
00309   }  
00310 
00311   entry(_idx, h);
00312 }
00313 
00314 
00315 //=============================================================================
00316 } // END_NS_UTILS
00317 } // END_NS_OPENMESH
00318 //=============================================================================
00319 #endif // OSG_HEAP_HH defined
00320 //=============================================================================
00321 

acg pic Project OpenMesh, ©  Computer Graphics Group, RWTH Aachen. Documentation generated using doxygen .