Wm4TMinHeap.h

Go to the documentation of this file.
00001 // Wild Magic Source Code
00002 // David Eberly
00003 // http://www.geometrictools.com
00004 // Copyright (c) 1998-2008
00005 //
00006 // This library is free software; you can redistribute it and/or modify it
00007 // under the terms of the GNU Lesser General Public License as published by
00008 // the Free Software Foundation; either version 2.1 of the License, or (at
00009 // your option) any later version.  The license is available for reading at
00010 // either of the locations:
00011 //     http://www.gnu.org/copyleft/lgpl.html
00012 //     http://www.geometrictools.com/License/WildMagicLicense.pdf
00013 //
00014 // Version: 4.0.2 (2006/10/15)
00015 
00016 #ifndef WM4TMINHEAP_H
00017 #define WM4TMINHEAP_H
00018 
00019 #include "Wm4System.h"
00020 
00021 namespace Wm4
00022 {
00023 
00024 template <typename Generator, typename Real> class TMinHeap;
00025 
00026 template <typename Generator, typename Real>
00027 class TMinHeapRecord
00028 {
00029 public:
00030     TMinHeapRecord ();
00031     ~TMinHeapRecord ();
00032 
00033     Generator GetGenerator () const;
00034     Real GetValue () const;
00035 
00036 private:
00037     friend class TMinHeap<Generator,Real>;
00038 
00039     Generator m_tGenerator;
00040     Real m_fValue;
00041     int m_iIndex;
00042 };
00043 
00044 template <typename Generator, typename Real>
00045 class TMinHeap
00046 {
00047 public:
00048     TMinHeap (int iMaxQuantity, int iGrowBy);
00049     ~TMinHeap ();
00050 
00051     // Member access.
00052     int GetMaxQuantity () const;
00053     int GetGrowBy () const;
00054     int GetQuantity () const;
00055     const TMinHeapRecord<Generator,Real>* GetRecord (int i) const;
00056 
00057     // Insert into the heap the number fValue that corresponds to the object
00058     // identified by iGenerator.  The return value is a pointer to the heap
00059     // record storing the information.
00060     const TMinHeapRecord<Generator,Real>* Insert (Generator tGenerator,
00061         Real fValue);
00062 
00063     // Remove the root of the heap.  The root contains the minimum value of
00064     // all heap elements.  The root information is returned by the function's
00065     // output parameters.
00066     void Remove (Generator& rtGenerator, Real& rfValue);
00067 
00068     // The value of a heap record must be modified through this function call.
00069     // The side effect is that the heap must be updated accordingly to
00070     // accommodate the new value.
00071     void Update (const TMinHeapRecord<Generator,Real>* pkConstRecord,
00072         Real fValue);
00073 
00074     // Support for debugging.  The first two functions check if the array of
00075     // records really do form a heap.  The last function prints the heap
00076     // to a file.
00077     bool IsValid (int iStart, int iFinal);
00078     bool IsValid ();
00079     void Print (const char* acFilename);
00080 
00081 private:
00082     // The actual record storage, allocated in one large chunk.
00083     int m_iMaxQuantity, m_iGrowBy, m_iQuantity;
00084     TMinHeapRecord<Generator,Real>* m_akRecords;
00085 
00086     // Pointers to the records in storage.  The two-level system avoids the
00087     // large number of allocations and deallocations that would occur if each
00088     // element of m_apkRecord were to be allocated/deallocated individually.
00089     TMinHeapRecord<Generator,Real>** m_apkRecords;
00090 };
00091 
00092 #include "Wm4TMinHeap.inl"
00093 
00094 }
00095 
00096 #endif

Generated on Fri Feb 13 13:58:10 2009 for meshmorph by  doxygen 1.5.1