-
Notifications
You must be signed in to change notification settings - Fork 0
/
HeapAdt.h
173 lines (157 loc) · 5.22 KB
/
HeapAdt.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
#ifndef HEAP_ADT_H
#define HEAP_ADT_H
/**
* @brief This class represents an *abstract* **Heap**,
* which its elements are *comparable* to each other.
*
* The heap compares its elements to each other, by a comparable `key`
* located in each element.
* @tparam E the type of each `element`.
* @note The terms `element`, `node` are synonyms.
* @note The terms `heap` and `tree` are synonyms.
* @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.
*/
template<typename E> class HeapAdt {
public:
HeapAdt() = default;
public:
virtual ~HeapAdt() = default;
public:
/**
* @brief Returns the *root element* of the heap, without removing it
* from the heap.
*
* @return the *root element* of the heap.
*/
virtual E *getRoot() = 0;
public:
/**
* @brief Deletes the *root element* from the heap, and returns it.
*
* @return the *root element* removed from the heap.
*/
virtual E *deleteRoot() = 0;
public:
/**
* @brief Inserts the @p elementToInsert to the heap.
*
* @param elementToInsert the element to insert to the heap.
*/
virtual void insert(E *elementToInsert) = 0;
public:
/**
* @brief Fixes the heap from a given @p indexToFixFrom and **downwards**.
*
* @param indexToFixFrom 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 one of his children,
* or when the root is a leaf.
* @see fixHeapUpwards(unsigned long)
*/
virtual void fixHeap(unsigned long indexToFixFrom) = 0;
public:
/**
* @brief Fixes the heap from a given @p indexToFixFrom and **upwards**.
*
* @param indexToFixFrom fixes the heap from this index **upwards** until
* the root of the heap.
* @note this method will continue to run until the root is no longer
* `predicated` than one of his children, or when the root is a leaf.
* @see fixHeap(unsigned long)
*/
virtual void fixHeapUpwards(unsigned long indexToFixFrom) = 0;
public:
/**
* @brief Builds a **Heap** by giving an arrayToBuildFrom of
* elements as a parameter.
*
* @param arrayToBuildFrom the given array of elements to build the
* heap from.
*/
virtual void buildHeap(E * arrayToBuildFrom,
unsigned long sizeOfArrayToBuildFrom) = 0;
public:
/**
* @brief boolean value whether this heap empty or not.
*
* @return boolean value. *true* if the heap is empty, *false* if the
* heap is not empty.
*/
virtual bool isEmpty() = 0;
public:
/**
* @brief clears the heap from elements.
*/
virtual void makeEmpty() = 0;
public:
/**
* @note This is an extension method - made for convenience.
* @return The logicalSize of the data-structure.
*/
virtual unsigned long getLogicalSize() const = 0;
public:
/**
* @brief Force the sub-classes of this class to implement the `print`
* method, so others could print this class' sub-classes
* polymorphically.
*
* @note This is an extension method - made for convenience.
*
* For example, you could print this class like so:
* @code
* heapAdt->print(std::cout);
* @endcode
*
* Tip:
*
* Define the `print` method like so (for example):
*
* @code
* public:
* friend std::ostream &operator<<(std::ostream &os, const HeapAdtSubClass &heap) {
* return printThis(os, heap);
* }
*
* private:
* std::ostream &print(std::ostream & os,
* const HeapAdt<K, V> &heapAdt) const override {
* return printThis(os, *this);
* }
*
* private:
* static std::ostream &printThis(std::ostream &os, const HeapAdtSubClass<K, V>
* &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";
* }
* @endcode
*
* @param os output-stream.
* @param heapAdt a `HeapAdt`.
* @return the given @p os.
*/
virtual std::ostream &print(std::ostream &os) const = 0;
public:
friend std::ostream &operator<<(std::ostream &os, const HeapAdt &adt) {
adt.print(os);
return os;
}
};
#endif // HEAP_ADT_H