1 /*
2 * ===========================
3 * VDK Visual Development Kit
4 * Version 0.4
5 * October 1998
6 * ===========================
7 *
8 * Copyright (C) 1998, Mario Motta
9 * Developed by Mario Motta <mmotta@guest.net>
10 *
11 * This library is free software; you can redistribute it and/or
12 * modify it under the terms of the GNU Library General Public
13 * License as published by the Free Software Foundation; either
14 * version 2 of the License, or (at your option) any later version.
15 *
16 * This library is distributed in the hope that it will be useful,
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 * Library General Public License for more details.
20 *
21 * You should have received a copy of the GNU Library General Public
22 * License along with this library; if not, write to the Free Software
23 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
24 * 02111-130
25 */
26
27
28 #ifndef VDKHEAP_H
29 #define VDKHEAP_H
30
31 #include <vdk/container.h>
32
parent(int i)33 inline int parent(int i) { return ((i-1) >> 1); }
left(int i)34 inline int left(int i) { return ((i << 1) + 1); }
right(int i)35 inline int right(int i) { return ((i << 1) + 2); }
36 /*!
37 \class VDKHeap
38 \brief provide a templatized Heap
39
40 \par Description
41 VDKHeap<T> class has a value semantic, all objects are copied
42 from original values.
43 All managed type T objects should provide:
44 \arg a default constructor: T::T()
45 \arg a copy initializer: T::T(T& t)
46 \arg an assignement operator: T& T::operator=(T& t)
47 \arg an equality and less-than operators:
48 \arg bool T::operator==(T& t)
49 \arg bool T::operator<(T& t)
50 \par Implementation notes
51 I suggest to use typedef's like:
52 \code
53 typedef VDKHeap<someClass> SomeClassHeap;
54 \endcode
55 */
56 template <class T> class VDKHeap: public VDKContainer<T>
57 {
58 public:
59 /*!
60 Constructor
61 makes an empty heap
62 */
VDKHeap()63 VDKHeap(): VDKContainer<T>(0) {}
64 /*!
65 Constructor
66 \param source an array of type T obejcts
67 \param array size
68 */
69 VDKHeap(T* source, int size);
70 /*!
71 Destructor
72 */
~VDKHeap()73 virtual ~VDKHeap() {}
74 /*!
75 Sorts on nlog(n) time
76 */
77 void Sort(void);
78 protected:
79 void Heapify(int i,int heapsize);
80 void BuildHeap(void);
81 };
82
83 // make an heap copyng data from T type source vector
84 template <class T>
VDKHeap(T * source,int size)85 VDKHeap<T>::VDKHeap(T* source, int size): VDKContainer<T>(size)
86 {
87 for(int i = 0; i < size; i++)
88 this->data[i] = source[i];
89 BuildHeap();
90 }
91
92 // HEAPIFY
93 template <class T>
Heapify(int i,int heapsize)94 void VDKHeap<T>::Heapify(int i, int heapsize)
95 {
96 int l = left(i), r = right(i), largest = i;
97 if( (l < heapsize) && (this->data[l] > this->data[i])) largest = l;
98 if( (r < heapsize) && (this->data[r] > this->data[largest])) largest = r;
99 if(largest != i)
100 {
101 T temp = this->data[i];
102 this->data[i] = this->data[largest];
103 this->data[largest] = temp;
104 Heapify(largest,heapsize);
105 }
106 }
107
108 // BUILDHEAP
109 template <class T>
BuildHeap(void)110 void VDKHeap<T>::BuildHeap(void)
111 {
112 for (int i = (this->size()-1)/2 ; i >= 0; i--)
113 Heapify(i,this->size());
114 }
115
116 // HEAPSORT
117 template <class T>
Sort(void)118 void VDKHeap<T>::Sort(void)
119 {
120 int heapsize = this->size();
121 int i = heapsize-1;
122 for(; i > 0; i--)
123 {
124 T temp = this->data[0];
125 this->data[0] = this->data[i];
126 this->data[i] = temp;
127 heapsize--;
128 Heapify(0,heapsize);
129 }
130 }
131 #endif
132
133
134
135
136
137
138