OOFEM  2.4
OOFEM.org - Object Oriented Finite Element Solver
heap.C
Go to the documentation of this file.
1 #include "heap.h"
2 #include <stdlib.h>
3 #include <stdio.h>
4 #include <math.h>
5 
6 namespace oofem {
7 #define MIN(a, b) ( ( a ) > ( b ) ? ( b ) : ( a ) )
8 
9 Heap :: Heap(int N) {
10  // Heuristic estimation of heap size
11  Initial_Heap_Alloc_Size = N / 4 + 1;
12 
13  heapCount = 0;
15 
16  // Initialize Heap and H2T which are the same size.
17  Keys = ( double * ) calloc( Initial_Heap_Alloc_Size,
18  sizeof( double ) );
19  H2T = ( int * ) calloc( Initial_Heap_Alloc_Size,
20  sizeof( int ) );
21 
22  T2H = ( int * ) calloc( N, sizeof( int ) );
23  // Initialize T2H by setting all values to -1, signifying that
24  // there are no heap elements corresponding to the pixels.
25  for ( int i = 0; i < N; i++ ) {
26  T2H [ i ] = -1;
27  }
28 }
29 
31  // Destructor
32  free(Keys);
33  free(H2T);
34  free(T2H);
35 }
36 
37 void Heap :: setToEmpty(int N) {
38  heapCount = 0;
39  for ( int i = 0; i < N; i++ ) {
40  T2H [ i ] = -1;
41  }
42 }
43 
44 int Heap :: parentInd(int inInd) {
45  return ( inInd - 1 ) / 2;
46 }
47 
48 int Heap :: leftChildInd(int inInd) {
49  return inInd * 2 + 1;
50 }
51 
52 int Heap :: rightChildInd(int inInd) {
53  return inInd * 2 + 2;
54 }
55 
57  return ( heapCount - 2 ) / 2;
58 }
59 
60 
61 
62 
63 void Heap :: swapElements(int Ind1, int Ind2) {
64  double tmpKey;
65  int tmpInd;
66 
67  if ( Ind1 == Ind2 ) {
68  return;
69  }
70 
71  // Swap keys
72  tmpKey = Keys [ Ind1 ];
73  Keys [ Ind1 ] = Keys [ Ind2 ];
74  Keys [ Ind2 ] = tmpKey;
75 
76  // Swap T2H values
77  // NB: Must be done before the H2T swaps
78  T2H [ H2T [ Ind1 ] ] = Ind2;
79  T2H [ H2T [ Ind2 ] ] = Ind1;
80 
81  // Swap H2T elems
82  tmpInd = H2T [ Ind1 ];
83  H2T [ Ind1 ] = H2T [ Ind2 ];
84  H2T [ Ind2 ] = tmpInd;
85 }
86 
87 void Heap :: upHeap(int Ind) {
88  // Index of parent of Ind
89  int parent;
90 
91  while ( Ind > 0 ) {
92  parent = ( Ind - 1 ) / 2;
93  if ( Keys [ Ind ] < Keys [ parent ] ) {
94  swapElements(Ind, parent);
95  Ind = parent;
96  } else {
97  break;
98  }
99  }
100 }
101 
102 void Heap :: downHeap(int Ind) {
103  // Index of first child. Add one to get second child.
104  int child1, child2, minChild;
105 
106  // Special case (not more than 1 element in the heap)
107  if ( heapCount < 2 ) {
108  return;
109  }
110 
111  // Loop until the biggest parent node
112  while ( Ind <= ( ( heapCount - 2 ) / 2 ) ) {
113  child1 = 2 * Ind + 1;
114  child2 = child1 + 1;
115  minChild = Ind;
116 
117  // Determine the child with the minimal value
118  if ( Keys [ child1 ] < Keys [ Ind ] ) {
119  minChild = child1;
120  }
121  if ( ( child2 < heapCount ) && ( Keys [ child2 ] < Keys [ minChild ] ) ) {
122  minChild = child2;
123  }
124 
125  // If there was a smaller child, swap with Ind
126  if ( minChild != Ind ) {
127  swapElements(Ind, minChild);
128  Ind = minChild;
129  } else {
130  break;
131  }
132  }
133 }
134 
135 
136 bool Heap :: isInHeap(int Ind) {
137  // Since T2H is initialized to -1 for all elements,
138  // any element that is not -1 (i.e. >= 0) is already in the heap.
139  return ( T2H [ Ind ] >= 0 );
140 }
141 
143  return heapCount;
144 }
145 
146 void Heap :: insert(double time, int Ind) {
147  // Reallocate more memory if necessary
148  if ( heapCount == ( allocatedSize - 1 ) ) {
149  Keys = ( double * ) realloc( Keys,
150  ( allocatedSize + Initial_Heap_Alloc_Size ) * sizeof( double ) );
151  H2T = ( int * ) realloc( H2T,
152  ( allocatedSize + Initial_Heap_Alloc_Size ) * sizeof( int ) );
153  }
154 
155  // Insert element at the end of the heap
156  Keys [ heapCount ] = time;
157  H2T [ heapCount ] = Ind;
158  T2H [ Ind ] = heapCount;
159 
160  heapCount++;
161 
162  // Ensure the heap is maintained by moving the
163  // new element as necessary upwards in the heap.
164  upHeap(heapCount - 1);
165 }
166 
167 void Heap :: update(double time, int Ind) {
168  Keys [ T2H [ Ind ] ] = time;
169 
170  // Must do one upHead run because maybe this new, lower, time
171  // is lower than those of the parents. By design of Fast-Marching
172  // it should never be larger though.
173  upHeap(T2H [ Ind ]);
174 }
175 
176 double Heap :: getSmallest(int *Ind) {
177  // Smallest element is the first of the heap
178  double heapRoot = Keys [ 0 ];
179 
180  // Set 'pointer' to the Ind in T of the min heap element
181  * Ind = H2T [ 0 ];
182 
183  // Replace root by the last heap element
184  swapElements(0, heapCount - 1);
185 
186  // Decrement heapCount.
187  // NB: Important to do this before downHeap is run!
188  heapCount--;
189 
190  // Run downHeap from root.
191  downHeap(0);
192 
193  return heapRoot;
194 }
195 
197  int lChild = leftChildInd(pInd);
198  int rChild = lChild + 1;
199 
200  if ( ( lChild < heapCount ) && ( Keys [ lChild ] < Keys [ pInd ] ) ) {
201  return pInd;
202  }
203  if ( ( rChild < heapCount ) && ( Keys [ rChild ] < Keys [ pInd ] ) ) {
204  return pInd;
205  }
206 
207  if ( ( lChild <= lastParentInd() ) ) {
208  return checkHeapProperty(lChild);
209  }
210  if ( ( rChild <= lastParentInd() ) ) {
211  return checkHeapProperty(rChild);
212  }
213 
214  return -1;
215 }
216 
218  printf("\nHeap: ");
219  for ( int iter = 0; iter < heapCount; iter++ ) {
220  printf("%.3g ", Keys [ iter ]);
221  }
222 }
223 
224 void Heap :: recurse(int row, int pad, int spacing, int S) {
225  // If not the first row, recursivly call itself
226  if ( row > 1 ) {
227  int newSpacing = ( ( int ) ceil( 2.0 * ( ( double ) spacing ) +
228  ( ( double ) S ) ) );
229  int newPad = ( ( int ) ceil( ( ( double ) pad ) + ( ( double ) spacing ) / 2.0
230  + ( ( double ) S ) / 2.0 ) );
231  recurse(row - 1, newPad, newSpacing, S);
232  }
233 
234  // Calculate the first and last elements on the row
235  int beg = ( pow( 2, ( row - 1 ) ) - 1 );
236  int end = MIN( ( heapCount - 1 ), ( pow(2, row) - 2 ) );
237 
238  // Newline and padding
239  printf("\n");
240  for ( int i = 0; i < pad; i++ ) {
241  printf(" ");
242  }
243 
244  // Print elements
245  for ( int elem = beg; elem <= end; elem++ ) {
246  printf("%-*.*g", S + spacing, S, Keys [ elem ]);
247  }
248 }
249 
251  if ( heapCount == 0 ) {
252  return;
253  }
254 
255  // Constants
256  int S = 3;
257  int B = 4;
258 
259  int nRows = 1 + floor( log2(heapCount) );
260 
261  // Call recurse from the last row
262  printf("\n");
263  recurse(nRows, 0, B, S);
264  printf("\n\n");
265 }
266 
267 // Insert narrowBand pixels into a m x n matrix.
268 // Unused?
269 double *Heap :: formMatrix(int m, int n) {
270  double *mat = ( double * ) calloc( m * n, sizeof( double ) );
271  for ( int iter = 0; iter < heapCount; iter++ ) {
272  mat [ H2T [ iter ] ] = Keys [ iter ];
273  }
274  return mat;
275 }
276 } // end namespace oofem
double getSmallest(int *Ind)
Definition: heap.C:176
void swapElements(int Ind1, int Ind2)
Definition: heap.C:63
#define MIN(a, b)
Definition: heap.C:7
void print()
Definition: heap.C:217
int * T2H
Definition: heap.h:25
~Heap()
Definition: heap.C:30
void recurse(int row, int pad, int spacing, int S)
Used by printTree. Does the actual printing, top-down.
Definition: heap.C:224
#define S(p)
Definition: mdm.C:481
int checkHeapProperty(int pInd)
Debugging tools.
Definition: heap.C:196
void insert(double time, int Ind)
Definition: heap.C:146
void upHeap(int Ind)
Elementary heap operations.
Definition: heap.C:87
int * H2T
Definition: heap.h:24
int lastParentInd()
Definition: heap.C:56
int heapCount
Keeps track of the number of elements in heap.
Definition: heap.h:46
#define N(p, q)
Definition: mdm.C:367
double * Keys
Heap arrays: Keys contains certain real values that need to be sorted.
Definition: heap.h:23
void downHeap(int Ind)
Definition: heap.C:102
void setToEmpty(int N)
Interface with external algorithms (such as fast marching)
Definition: heap.C:37
int leftChildInd(int inInd)
Definition: heap.C:48
int parentInd(int inInd)
Index calculations.
Definition: heap.C:44
bool isInHeap(int Ind)
Definition: heap.C:136
int rightChildInd(int inInd)
Definition: heap.C:52
int allocatedSize
Definition: heap.h:43
int nElems()
Definition: heap.C:142
void update(double time, int Ind)
Definition: heap.C:167
double * formMatrix(int m, int n)
Definition: heap.C:269
int Initial_Heap_Alloc_Size
Variables that control the memory allocation for the heap.
Definition: heap.h:43
void printTree()
Definition: heap.C:250
the oofem namespace is to define a context or scope in which all oofem names are defined.
Heap(int N)
Constructor and destructor.
Definition: heap.C:9

This page is part of the OOFEM documentation. Copyright (c) 2011 Borek Patzak
Project e-mail: info@oofem.org
Generated at Tue Jan 2 2018 20:07:29 for OOFEM by doxygen 1.8.11 written by Dimitri van Heesch, © 1997-2011