-
Notifications
You must be signed in to change notification settings - Fork 0
/
Heap.h
634 lines (556 loc) · 23.7 KB
/
Heap.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
#ifndef HEAP_H
#define HEAP_H
#include "BasicAlgorithms.h"
#include "HeapAdt.h"
#include <cmath>
/**
* @note The term `<<predicate-resulted>>` is a result of a predicate method
* that returns `bool`, and tells whether a `node` should be *swapped*
* with its `parent` or not. In this implementation,
* `<<predicate-resulted>>` is defined to be the result of the
* @link predicateIsSwapNeeded(E, E) @endlink method.
* @tparam E the type of each `element`.
* @see HeapAdt
*/
template<typename E> class Heap : public HeapAdt<E> {
protected:
static constexpr char *IS_EMPTY_MESSAGE = (char *) "Heap: heap is empty.";
protected:
static constexpr char *IS_FULL_MESSAGE = (char *) "Heap: array is full.";
protected:
static constexpr char *OUT_OF_RANGE_MESSAGE =
(char *) "Heap: out of range.";
protected:
/**
* @see fixHeap(unsigned long)
* @see fixHeapUpwards(unsigned long)
* @see fixHeapWhile(unsigned long, Direction)
*/
enum class Direction { UPWARDS, DOWNWARDS };
protected:
/**
* Array of pointers to **lvalue `E`** that serve as `elements`.
* Initialized to `nullptr`.
*/
E **_array = nullptr;
protected:
/// The *physical-size* of the `_array`. Initialized to `0`.
unsigned long _physicalSize = 0;
protected:
/// The *logical-size* of the `_array`. Initialized to `0`.
unsigned long _logicalSize = 0;
public:
unsigned long getLogicalSize() const override { return _logicalSize; }
public:
/**
* @brief Constructor, initializes the `_array`.
*
* Builds a **Heap** by giving an @p arrayToBuildFrom of
* **lvalue `E`** as a parameter. Done by invoking the
* @link buildHeap @endlink method.
* @param arrayToBuildFrom the given array of elements to build the
* heap from.
* @param sizeOfArrayToBuildFrom the size of the array to build the
* heap from.
* @see buildHeap
*/
Heap(E *arrayToBuildFrom, unsigned long sizeOfArrayToBuildFrom) {
buildHeap(arrayToBuildFrom, sizeOfArrayToBuildFrom);
}
public:
/**
* @brief Constructor, sets the `_physicalSize` of the `_array` to be @p
* _physicalSize.
*
* @note the content of the `_array` remains empty.
* @param physicalSize set the `_physicalSize` of the `_array` to be this size.
*/
explicit Heap(unsigned long physicalSize) {
this->_physicalSize = physicalSize;
this->_array = new E *[physicalSize];
for (unsigned long i = 0; i < _physicalSize; i++) {
_array[i] = nullptr;
}
}
public:
/**
* @brief Default constructor creates an arbitrary physicalSize of 100.
*/
Heap() : Heap(100) {}
public:
virtual ~Heap() { deleteThis(); }
private:
void deleteThis() { delete[] _array; }
public:
/**
* @return the root element, which is the top element in the heap.
* @throws std::runtime_error in case there are no elements in the heap,
* and the user requested to retrieve the root.
* @see getElement(unsigned long)
*/
E *getRoot() override { return getElement(0); }
public:
/**
* @return an element in the heap corresponds to the given @p index.
* @throws std::out_of_range in case the index provided is out of range.
* @throws std::runtime_error in case there are no elements in the heap,
* and the user requested to retrieve the root.
*/
E *getElement(unsigned long index) {
if (!_logicalSize) {
throw std::runtime_error(IS_EMPTY_MESSAGE);
} else {
assertOutOfRange(index);
return this->_array[index];
}
}
public:
/**
* @brief Deletes the *root element* from the heap, and returns it.
*
* @note After removing the *root element* from the heap, this method
* calls the *fixHeap(0)* method, in order to fix the heap afterwards.
* @attention in case the `_logicalSize` of the `_array` is `0`,
* this method returns `null_ptr`.
* @return the *root element* removed from the heap.
* @throws std::runtime_error in case the heap is already empty.
* @throws std::out_of_range in case the index provided is out of range.
* @see fixHeap(unsigned long)
* @see deleteElement(unsigned long)
*/
E *deleteRoot() override { return deleteElement(0); }
public:
/**
* @brief Deletes the *element* from the heap, and returns it.
*
* @note After removing the *element* from the heap, this method
* calls the @link fixHeap(index) @endlink method, in order to fix
* the heap afterwards.
* @attention in case the `_logicalSize` of the `_array` is `0`,
* this method returns `nullptr`.
* @return the *element* removed from the heap.
* @throws std::runtime_error in case the heap is already empty.
* @throws std::out_of_range in case the index provided is out of range.
* @see fixHeap(unsigned long)
* @see deleteElement(unsigned long, bool)
*/
E *deleteElement(unsigned long index) { return deleteElement(index, true); }
private:
/**
* @brief Deletes the *element* from the heap, and returns it.
* @deprecated Caution when setting @p fixHeapAfterDeletion to `false`.
*
* @note After removing the *element* from the heap, this method
* calls the @link fixHeap(index) @endlink method, in order to fix
* the heap afterwards - only if the @p fixHeapAfterDeletion
* parameter is `true`.
* @attention in case the `_logicalSize` of the `_array` is `0`,
* this method returns `nullptr`.
* @param fixHeapAfterDeletion determines if the method will call the
* @link fixHeap(index) @endlink method, after
* deletion, to ensure that the heap is still
* valid.
* @return the *element* removed from the heap.
* @throws std::runtime_error in case the heap is already empty.
* @throws std::out_of_range in case the index provided is out of range.
* @see fixHeap(unsigned long)
*/
E *deleteElement(unsigned long index, bool fixHeapAfterDeletion) {
/* Save the value of `element` to return in the end of the method. */
E *returnElement = getElement(index);
if ((this->_logicalSize - index) > 1) {
deleteElementWhenThereAreTwoOrMoreElementsSinceIndexGiven(
index, fixHeapAfterDeletion);
} else if ((this->_logicalSize - index) > 0) {
/* Delete `_array[index]` manually. */
this->_array[index] = nullptr;
/* Decrease the `_logicalSize` of the _array by `1`. */
this->_logicalSize--;
}
return returnElement;
}
private:
/**
* @brief This method is a *private* method, that represents the
* case when there are `2` or more elements in the heap.
*
* @note After removing the *root element* from the heap, this method
* calls the @link fixHeap(indexOfElementToDelete) @endlink method,
* in order to fix the heap afterwards - only if the @p
* fixHeapAfterDeletion parameter is `true`.
* @param fixHeapAfterDeletion determines if the method will call the
* @link fixHeap(indexOfElementToDelete)
* @endlink method, after deletion, to
* ensure that the heap is still valid.
* @see fixHeap(unsigned long)
*/
void deleteElementWhenThereAreTwoOrMoreElementsSinceIndexGiven(
unsigned long indexOfElementToDelete, bool fixHeapAfterDeletion) {
/*
* There are at least `2` elements in the heap,
* so we are able to delete an element.
*/
/* Set the `indexOfElementToDelete` element in the `_array` to be the `last` element. */
this->_array[indexOfElementToDelete] =
this->_array[this->_logicalSize - 1];
onUpdateElementWithIndex(_array[indexOfElementToDelete],
indexOfElementToDelete);
/* Set the `last` element to be `nullptr`. */
this->_array[this->_logicalSize - 1] = nullptr;
/*
* Decrease the `_logicalSize` of the `_array` by `1`,
* before invoking `fixHeap(indexOfElementToDelete)`.
*/
this->_logicalSize--;
/* After deletion, invoke `fixHeap(indexOfElementToDelete)` to fix the heap. */
if (fixHeapAfterDeletion) { fixHeap(indexOfElementToDelete); }
}
public:
/**
* @brief Builds a **Heap** by giving an @p arrayToBuildFrom of
* **lvalue `E`** as a parameter.
*
* Done by making an _array of pointers to the elements given in the @p
* arrayToBuildFrom.
* @param arrayToBuildFrom the given _array of elements to build the
* heap from.
* @param sizeOfArrayToBuildFrom the size of the _array to build the
* heap from.
* @note In case there is already an `allocated` `_array` in this heap,
* this method ensures to `delete []` it *before* handling the
* building process.
* @attention the `E` elements in the @p arrayToBuildFrom must be
* **lvalues**.
*/
void buildHeap(E * arrayToBuildFrom,
unsigned long sizeOfArrayToBuildFrom) override {
/* Delete the old _array if there is any. */
deleteThis();
/* Initialize a `new` empty _array of pointers to elements given. */
this->_physicalSize = sizeOfArrayToBuildFrom;
this->_logicalSize = sizeOfArrayToBuildFrom;
this->_array = new E *[sizeOfArrayToBuildFrom];
for (unsigned long i = 0; i < sizeOfArrayToBuildFrom; i++) {
this->_array[i] = &arrayToBuildFrom[i];
}
/*
* `currentIndex` should be in between `0` and `(_logicalSize / 2)`.
* Note: the almost last level has `(_logicalSize / 2)` `nodes`.
*/
unsigned long lastIndex = this->_logicalSize - 1;
for (unsigned long currentIndex = getParentIndex(lastIndex);
currentIndex >= 0; currentIndex--) {
fixHeap(currentIndex);
}
}
public:
/**
* @brief Fixes the heap from a given @p indexToFixFrom and **downwards**.
* @param indexToFixFrom an index of an element in the heap, that the
* user wishes to fix the heap from.
* @see fixHeap(unsigned long, Direction)
*/
void fixHeap(unsigned long indexToFixFrom) override {
fixHeap(indexToFixFrom, Direction::DOWNWARDS);
}
public:
/**
* @brief Fixes the heap from a given @p indexToFixFrom and **upwards**.
* @param indexToFixFrom an index of an element in the heap, that the
* user wishes to fix the heap from.
* @see fixHeap(unsigned long, Direction)
*/
void fixHeapUpwards(unsigned long indexToFixFrom) override {
fixHeap(indexToFixFrom, Direction::UPWARDS);
}
private:
/**
* @brief This method *fixes* the heap from a given @p indexToFixFrom till
* the *end* of the heap. The *end* of the heap could be either the
* *root* of the heap (the topmost element), or the rightmost leaf.
* The *end* of the heap is determined by the given @p direction that the
* user wishes to fix the heap to. This could be *downwards* or *upwards*.
*
* For example, if the user picks the `Direction::DOWNWARDS` direction
* then this method would handle a heap that is *valid* from the root
* downwards until the @p indexToFixFrom, and from there and on
* downwards the heap is *invalid* - means: that the `node` in the
* @p indexToFixFrom is no `<<predicate-resulted>>` than both of its
* children.
*
* The method ensures to *correct* the heap by *fixing* its
* validity - means, checking that each `node` is
* `NOT <<predicate-resulted>>` than
* both of its children.
*
* @param indexToFixFrom the method fixes the heap from this index
* downwards until the leaves of the heap.
* @note this method will continue to run until the root is no longer
* `<<predicate-resulted>>` than both of its children,
* or when the root is a leaf.
* @attention there is no use to give @p indexToFixFrom that is `<<predicate-resulted>>`
* than `(_logicalSize / 2)`, because indexes larger than
* `(_logicalSize / 2)` point to leaf `node`s, thus the method
* will have no effect, as explained earlier.
* @throws std::out_of_range in case the index provided is out of range.
* @see Direction
* @see fixHeap(unsigned long)
* @see fixHeapUpwards(unsigned long)
*/
void fixHeap(unsigned long indexToFixFrom, Direction direction) {
/* Check that `indexToFixFrom` is a legal index. */
assertOutOfRange(indexToFixFrom);
fixHeapLegalIndex(indexToFixFrom, direction);
}
private:
/**
* @param index the index to assert is *not* out of range of the heap's
* logical size.
* @throws std::out_of_range in case the index provided is out of range.
*/
void assertOutOfRange(unsigned long index) {
if ((index < 0) || (this->_logicalSize <= index)) {
// std::string message;
// message.append("The index provided is out of range. There are ");
// message.append(std::to_string(_logicalSize));
// message.append(" elements in the heap.\n");
throw std::out_of_range(OUT_OF_RANGE_MESSAGE);
}
}
private:
/**
* @brief This method is a *private* method, that represents the
* case when the provided @p currentIndex is a legal index.
* This method is being invoked by the @link fixHeap(unsigned long,
* Direction) @endlink method.
*
* @param currentIndex has been checked as a legal index. Should be
* in between `0` and `(_logicalSize / 2)`.
* Represents the index to *fixHeap* from.
* @param direction tells the `Direction` of which the `fixHeap` would
* iterate.
* @see fixHeap(unsigned long)
* @see fixHeapUpwards(unsigned long)
* @see Direction
*/
void fixHeapLegalIndex(unsigned long indexToFixFrom, Direction direction) {
/*
* `currentIndex` should be in between `0` and `(_logicalSize / 2)`.
*
* Note: the `almost last` level has `(_logicalSize / 2)` `nodes`.
* Attention: there is no use to give `indexToFixFrom` that is larger
* than `(_logicalSize / 2)`.
*/
unsigned long currentIndex = indexToFixFrom;
if (this->_array[currentIndex] == nullptr) {
/*
* The `indexToFixFrom` is out of range. Throw a message.
* Note: should not be happening here, thanks to already checked
* scenario.
*/
// std::string message;
// message.append(
// "The index provided is out of range. The element "
// "you have provided is `nullptr`. Thus, in-comparable.\n");
throw std::out_of_range(OUT_OF_RANGE_MESSAGE);
}
/* _array[currentIndex] is not `nullptr`. Thus, comparable. */
fixHeapWhile(currentIndex, direction);
}
protected:
/**
* @brief This method is a *protected* method, that represents a `while`
* that is being invoked by the @link fixHeap(unsigned long) @endlink method.
*
* The `while` loop has `2` stop conditions:
* @li there are no children to the `node` that is being iterated ( =
* the `node` that is being iterated is a `leaf`.
* @li the `node` that is being iterated is *not* `swappable` with each of
* its children.
* @param currentIndex should be in between `0` and `(_logicalSize / 2)`.
* Represents the index to *fixHeap* from.
* @see fixHeap(unsigned long)
* @see fixHeapUpwards(unsigned long)
* @see Direction
*/
void fixHeapWhile(unsigned long currentIndex, Direction direction) {
/* `_array[currentIndex]` is not `nullptr`. Thus, comparable. */
while ((0 <= currentIndex) && (currentIndex < (_logicalSize / 2))) {
/* Get the index that points to the `swappable` element. */
unsigned long indexOfSwappableChildOfCurrentRoot =
getIndexOfChildToSwapWithParent(_array, _logicalSize,
currentIndex * 2 + 1,
currentIndex * 2 + 2);
if (_array[indexOfSwappableChildOfCurrentRoot] != nullptr) {
/*
* There is a living element.
* Compare by keys.
* `swap` the elements if needed, to maintain the validity of
* the heap as a `Heap`.
*/
if (predicateIsSwapNeeded(
_array[currentIndex],
_array[indexOfSwappableChildOfCurrentRoot])) {
onSwapIsNeeded(currentIndex,
indexOfSwappableChildOfCurrentRoot);
/*
* Set the updated iterator index to the replaced index.
* Note: this enlarges the index.
*/
if (direction == Direction::DOWNWARDS) {
currentIndex = indexOfSwappableChildOfCurrentRoot;
} else if (direction == Direction::UPWARDS) {
currentIndex = getParentIndex(currentIndex);
}
} else {
/*
* Second stop condition:
* the parent is not smaller than its child. break.
*/
break;
}
} else {
/*
* There is no element to compare with.
* Thus, this `node` does not have children,
* and is actually a leaf.
*/
break;
}
}
}
protected:
virtual void onSwapIsNeeded(unsigned long index1,
unsigned long index2) const {
BasicAlgorithms::swap(_array, index1, index2);
}
protected:
/**
* @brief This method enables the sub-classes of `this` class,
* to add logic right after an update of an element to another index.
* @param element an element that was just changed its index.
*/
virtual void onUpdateElementWithIndex(E *& element,
unsigned long newIndex) const {}
protected:
/**
* @note in case @p currentIndex is `0`, then the result will be `-1`.
* @param currentIndex the index of the element to get its parent element
* index.
* @return the index of the parent element of the element which its index
* is the given @p currentIndex.
*/
static unsigned long getParentIndex(unsigned long currentIndex) {
return (unsigned long) (floor(((double) (currentIndex - 1)) / 2));
}
protected:
/**
* @see fixHeapWhile(unsigned long, Direction)
*/
virtual unsigned long
getIndexOfChildToSwapWithParent(E **array, unsigned long size,
unsigned long indexToElement1,
unsigned long indexToElement2) = 0;
protected:
/**
* @attention *must* pass by pointer, so that the elements won't destruct
* themselves.
* @see fixHeapWhile(unsigned long, Direction)
*/
virtual bool predicateIsSwapNeeded(E *&element1, E *&element2) = 0;
public:
/**
* @brief Inserts the @p elementToInsert to the heap.
*
* @param elementToInsert the element to insert to the heap.
* @throws std::logic_error in case the heap is already full.
*/
void insert(E *elementToInsert) override {
if (this->_physicalSize <= this->_logicalSize) {
/* The heap is already full. Throw a message. */
// std::string message;
// message.append("The heap is already full, and contains ");
// message.append(std::to_string(_physicalSize));
// message.append(" elements.\n");
throw std::logic_error(IS_FULL_MESSAGE);
}
/* If there is enough space in the _array. */
insertWhenThereIsEnoughSpace(elementToInsert);
}
protected:
/**
* @brief This method is a *private* method, that represents the
* case when there is enough space in the heap to insert an
* additional @p elementToInsert element.
*
* @param elementToInsert is the element required to be inserted to the
* heap.
* @see insert(E *)
*/
void insertWhenThereIsEnoughSpace(E *elementToInsert) {
/* Add the `elementToInsert` as the `last` element in the _array. */
this->_array[this->_logicalSize++] = elementToInsert;
unsigned long currentIndex = this->_logicalSize - 1;
onUpdateElementWithIndex(elementToInsert, currentIndex);
/*
* Check upwards the heap, whether there is a need to `swap` the
* elements according to the insertion, to ensure the heap is valid.
* While there is at least `1` child in the _array.
*/
while (0 < currentIndex) {
/*
* Beginning with the inserted element, compare each child to
* its parent, to check if there is a need to `swap` between
* them, in order to ensure validity of the heap, as a `Heap`.
*/
if (predicateIsSwapNeeded(
this->_array[getParentIndex(currentIndex)],
this->_array[currentIndex])) {
onSwapIsNeeded(getParentIndex(currentIndex), currentIndex);
/* Step upwards to the parent of the element. */
currentIndex = getParentIndex(currentIndex);
} else {
/* There is no need to `swap`. Thus, the heap is valid. */
break;
}
}
}
public:
/**
* @brief returns a boolean value that determines whether this heap is
* empty or not.
*
* @return boolean value of *true* if the heap is empty, or else, *false* if
* the heap is not empty.
*/
bool isEmpty() override { return !(this->_logicalSize); }
public:
void makeEmpty() override { this->_logicalSize = 0; }
public:
friend std::ostream &operator<<(std::ostream &os, const Heap &heap) {
return printThis(os, heap);
}
public:
std::ostream &print(std::ostream &os) const override {
return printThis(os, *this);
}
private:
static std::ostream &printThis(std::ostream &os, const Heap<E> &heap) {
os << "_array{\n";
/* In case the _array is empty, print a message instead of elements. */
if (heap._logicalSize == 0) {
os << "The _array is empty."
<< "\n";
}
for (unsigned long i = 0; i < heap._logicalSize; i++) {
os << *heap._array[i] << ";";
os << "\n";
}
os << "}; ";
os << "_logicalSize: " << heap._logicalSize
<< ", _physicalSize: " << heap._physicalSize << ";"
<< "\n";
return os;
}
};
#endif // HEAP_H