← Back to branch summary

~ubuntu-branches/ubuntu/maverick/freecad/maverick

« back to all changes in this revision

Viewing changes to src/Mod/Mesh/App/WildMagic4/Wm4TMinHeap.h

  • Committer: Bazaar Package Importer
  • Author(s): Teemu Ikonen
  • Date: 2009-07-16 18:37:41 UTC
  • Revision ID: james.westby@ubuntu.com-20090716183741-oww9kcxqrk991i1n
Tags: upstream-0.8.2237
Import upstream version 0.8.2237

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/Mod/Mesh/App/WildMagic4/Wm4TMinHeap.h
 
1
// Wild Magic Source Code
 
2
// David Eberly
 
3
// http://www.geometrictools.com
 
4
// Copyright (c) 1998-2007
 
5
//
 
6
// This library is free software; you can redistribute it and/or modify it
 
7
// under the terms of the GNU Lesser General Public License as published by
 
8
// the Free Software Foundation; either version 2.1 of the License, or (at
 
9
// your option) any later version.  The license is available for reading at
 
10
// either of the locations:
 
11
//     http://www.gnu.org/copyleft/lgpl.html
 
12
//     http://www.geometrictools.com/License/WildMagicLicense.pdf
 
13
// The license applies to versions 0 through 4 of Wild Magic.
 
14
//
 
15
// Version: 4.0.2 (2006/10/15)
 
16
 
 
17
#ifndef WM4TMINHEAP_H
 
18
#define WM4TMINHEAP_H
 
19
 
 
20
#include "Wm4System.h"
 
21
 
 
22
namespace Wm4
 
23
{
 
24
 
 
25
template <typename Generator, typename Real> class TMinHeap;
 
26
 
 
27
template <typename Generator, typename Real>
 
28
class TMinHeapRecord
 
29
{
 
30
public:
 
31
    TMinHeapRecord ();
 
32
    ~TMinHeapRecord ();
 
33
 
 
34
    Generator GetGenerator () const;
 
35
    Real GetValue () const;
 
36
 
 
37
private:
 
38
    friend class TMinHeap<Generator,Real>;
 
39
 
 
40
    Generator m_tGenerator;
 
41
    Real m_fValue;
 
42
    int m_iIndex;
 
43
};
 
44
 
 
45
template <typename Generator, typename Real>
 
46
class TMinHeap
 
47
{
 
48
public:
 
49
    TMinHeap (int iMaxQuantity, int iGrowBy);
 
50
    ~TMinHeap ();
 
51
 
 
52
    // Member access.
 
53
    int GetMaxQuantity () const;
 
54
    int GetGrowBy () const;
 
55
    int GetQuantity () const;
 
56
    const TMinHeapRecord<Generator,Real>* GetRecord (int i) const;
 
57
 
 
58
    // Insert into the heap the number fValue that corresponds to the object
 
59
    // identified by iGenerator.  The return value is a pointer to the heap
 
60
    // record storing the information.
 
61
    const TMinHeapRecord<Generator,Real>* Insert (Generator tGenerator,
 
62
        Real fValue);
 
63
 
 
64
    // Remove the root of the heap.  The root contains the minimum value of
 
65
    // all heap elements.  The root information is returned by the function's
 
66
    // output parameters.
 
67
    void Remove (Generator& rtGenerator, Real& rfValue);
 
68
 
 
69
    // The value of a heap record must be modified through this function call.
 
70
    // The side effect is that the heap must be updated accordingly to
 
71
    // accommodate the new value.
 
72
    void Update (const TMinHeapRecord<Generator,Real>* pkConstRecord,
 
73
        Real fValue);
 
74
 
 
75
    // Support for debugging.  The first two functions check if the array of
 
76
    // records really do form a heap.  The last function prints the heap
 
77
    // to a file.
 
78
    bool IsValid (int iStart, int iFinal);
 
79
    bool IsValid ();
 
80
    void Print (const char* acFilename);
 
81
 
 
82
private:
 
83
    // The actual record storage, allocated in one large chunk.
 
84
    int m_iMaxQuantity, m_iGrowBy, m_iQuantity;
 
85
    TMinHeapRecord<Generator,Real>* m_akRecords;
 
86
 
 
87
    // Pointers to the records in storage.  The two-level system avoids the
 
88
    // large number of allocations and deallocations that would occur if each
 
89
    // element of m_apkRecord were to be allocated/deallocated individually.
 
90
    TMinHeapRecord<Generator,Real>** m_apkRecords;
 
91
};
 
92
 
 
93
#include "Wm4TMinHeap.inl"
 
94
 
 
95
}
 
96
 
 
97
#endif