· 8 years ago · Jun 18, 2018, 09:16 PM
1#ifndef ADS_SET_H
2#define ADS_SET_H
3
4#include <functional>
5#include <algorithm>
6#include <iostream>
7#include <stdexcept>
8
9template <typename Key, size_t N=7> //N is size of the bucekt
10class ADS_set {
11public:
12 class Iterator;
13 using value_type = Key;
14 using key_type = Key;
15 using reference = key_type&;
16 using const_reference = const key_type&;
17 using size_type = size_t;
18 using difference_type = std::ptrdiff_t;
19 using iterator = Iterator;
20 using const_iterator = Iterator;
21 using key_compare = std::less<key_type>;
22 using key_equal = std::equal_to<key_type>;
23 using hasher = std::hash<key_type>;
24
25private:
26 size_type nextToSplit{0}, roundNum{1}, currTableSize{2};
27 unsigned int overalElementCount{0};
28
29 //each element can be taken or free
30 enum class State {free, taken};
31
32 //each element has its key and state (state can be seen as a value, as its true value is the exact same as the key in our case for simplicity purposes)
33 struct element {
34 key_type key;
35 State state {State::free};
36 };
37
38
39 struct Bucket {
40 unsigned int numOfElements = 0;
41 element bucket[N]; //array of elements
42 Bucket* overflowBucket{nullptr};
43
44 void createOverflow() {
45 //check if the overflow exists -> if it doesnt create one
46 if(overflowBucket == nullptr) {
47 overflowBucket = new Bucket();
48 }
49 }
50
51 element* findElement(const_reference key) {
52 //already know in which bucket in the table to look
53 //go trhough the bucket and search, if found return
54 //if not found go to its overflowbucket and search there, if found return
55 //if not return null pointer
56 for(unsigned i=0; i<N; ++i) {
57 if(bucket[i].state == State::taken) {
58 if(key_equal{}(bucket[i].key, key)) {
59 return &bucket[i];
60 }
61 }
62 }
63
64 if(overflowBucket == nullptr) {
65 return nullptr;
66 }
67
68 return overflowBucket->findElement(key);
69 }
70
71
72 element* insertElementInBucket(const_reference key) {
73 //go through the bucket (primary one) and if its state is free put an element in it
74 for(unsigned i=0; i<N; ++i) {
75 if(bucket[i].state == State::free) {
76 bucket[i].state = State::taken;
77 bucket[i].key = key;
78 ++numOfElements;
79 return &bucket[i];
80 }
81 }
82
83 //if the loop is not broken, it means that i=7, meaning i==N==> all 7 places in the bucket are taken
84 //insert element into the overflow bucket
85 return overflowBucket->insertElementInBucket(key);
86
87 ////TRIGGET THE DAMN SPLITTTTTTTT SOMEHOW
88 }
89
90 ~Bucket() {
91 if (overflowBucket != nullptr) {
92 if(overflowBucket->numOfElements == N) {
93 delete overflowBucket;
94 }
95 }
96 delete overflowBucket;
97 } //destructor called whenever the object goes out of scope
98
99 };
100
101 //table can be seen as a pointer to a list (an array) of pointers (each of those pointer is pointing at actual buckets)
102 Bucket** table{nullptr};
103
104 //hash function based on definition from the folien
105 size_type hashIndex(const_reference key) const {
106 size_type idx = hasher{}(key) % (2^roundNum);
107 size_type d{roundNum};
108
109 if(idx < nextToSplit) {
110 ++d;
111 idx = hasher{}(key) % (2^d);
112 }
113
114 return idx;
115 }
116
117 //create a table, initialize the array of pointers to buckets and assign a bucket to each pointer
118 void createTable() {
119 size_type size{2^roundNum};
120 table = new Bucket* [size]; //initialize array of pointers
121 for(unsigned i=0; i<size; ++i) { //assign a bucket to each pointer
122 table[i] = new Bucket();
123 }
124 }
125
126 //delete table
127 void deleteTable() {
128 delete[] table;
129 }
130
131 void splitTable() { //basically resizing the table (expanding it by one bucket)
132 size_type old_size = currTableSize;
133 size_type new_size = currTableSize + 1;
134 //declare new table of the new size
135 Bucket** new_table = new Bucket* [new_size];
136 //initialize the new table
137 for(unsigned i=0; i<new_size; ++i) {
138 new_table[i] = new Bucket();
139 }
140
141 Bucket** old_table{table};
142 table = new_table;
143 currTableSize = new_size;
144
145 //copy values from old table into new table
146 for(unsigned j=0; j<old_size; ++j) {
147 table[j] = old_table[j];
148 }
149
150 delete[] old_table; //free the memory of old table as that is the version of your table that you dont need anymore --> wont work with that anymore
151 }
152
153 void rehashAfterSplit() {
154 //create temporary bucket that holds the values of the next to split bucket that will be rehashed
155 Bucket* ntsBucketCopy = new Bucket();
156
157 for(unsigned i=0; i<N; ++i) {
158 ntsBucketCopy->bucket[i] = table[nextToSplit]->bucket[i];
159 table[nextToSplit]->bucket[i].state = State::free;
160 }
161
162 ++nextToSplit; //increase next to split to point to the next bucket in the table
163 //if new next to split is the same as 2^roundnum then the round number increases and next to split is reset to 0
164 if(nextToSplit == (2^roundNum)) {
165 ++roundNum;
166 nextToSplit = 0;
167 }
168
169 //add the elements from the helper bucket in the table again--->rehash the 'table'
170 for(unsigned j=0; j<N; ++j) {
171 //find new index since it changes because the table is bigger now
172 size_type idx = hashIndex(ntsBucketCopy->bucket[j].key);
173 table[idx]->insertElementInBucket(ntsBucketCopy->bucket[j].key);
174 }
175
176 }
177
178
179 void insertElementInTable(const_reference key) { //key is the element that has to be inserted
180 //find the appropriate bucket -> hash the key to find the index in the table that the appropriate bucket is under
181 size_type startIndex = hashIndex(key);
182
183 //check if the bucket under that index is full
184 if(table[startIndex]->numOfElements == N) {
185 //create overflow bucket
186 table[startIndex]->createOverflow();
187 //resize the table -->add one more bucket
188 splitTable(); //not dependant on individual buckets in the table hence you dont have to call it with specific pointer to the bucket like with overflow and rehash functions
189 //rehash the values in the splitted bucket and new bucket
190 rehashAfterSplit();
191 }
192
193 //find the index in the new 'after split' table
194 size_type finalIndex = hashIndex(key);
195 table[finalIndex]->insertElementInBucket(key);
196 ++overalElementCount;
197 }
198
199public:
200 ADS_set() {createTable();}
201 ADS_set(std::initializer_list<key_type> ilist): ADS_set{} {insert(ilist);}
202 template <typename InputIt> ADS_set(InputIt first, InputIt last): ADS_set{} {insert(first, last);}
203
204 ADS_set(const ADS_set&) {throw std::runtime_error{"Not implemented"};}
205 ~ADS_set() {}
206
207 ADS_set& operator=(const ADS_set&) {throw std::runtime_error{"Not implemented"};}
208 ADS_set& operator=(std::initializer_list<key_type> ilist) {throw std::runtime_error{"Not implemented"};}
209
210 size_type size() const { return overalElementCount; }
211 bool empty() const { return overalElementCount==0; }
212
213 size_type count(const_reference key) const {
214 size_type idx = hashIndex(key); //find the bucket that you need to search through
215 //find the element in the corresponding bucket and save result (also an element pointer) to ptr
216 element* ptr{table[idx]->findElement(key)};
217 //if element is not found ptr will be nullptr and you return 0, else return 1
218 if(ptr == nullptr) {return 0;}
219 return 1;
220 }
221
222 iterator find(const_reference) const {throw std::runtime_error{"Not implemented"};}
223
224 void clear() {throw std::runtime_error{"Not implemented"};}
225 void swap(ADS_set&) {throw std::runtime_error{"Not implemented"};}
226
227 void insert(std::initializer_list<key_type> ilist) {
228 for (const auto &key: ilist) {
229 size_type idx = hashIndex(key);
230 if(!(table[idx]->findElement(key))) {
231 insertElementInTable(key);
232 }
233 }
234 }
235
236 std::pair<iterator,bool> insert(const_reference) {throw std::runtime_error{"Not implemented"};}
237
238 template<typename InputIt> void insert(InputIt first, InputIt last) {
239 for (auto it=first; it != last; ++it) {
240 size_type idx = hashIndex(*it);
241 if(!(table[idx]->findElement(*it))) {
242 insertElementInTable(*it);
243 }
244 }
245 }
246
247 size_type erase(const key_type& ) { throw std::runtime_error{ "Not implemented!" }; }
248
249 const_iterator begin() const { throw std::runtime_error{ "Not implemented!" }; }
250 const_iterator end() const { throw std::runtime_error{ "Not implemented!" }; }
251
252 void dump(std::ostream& o = std::cerr) const {
253 for (unsigned i=0; i<currTableSize; ++i) {
254 o << "Bucket[" << i << "]";
255
256 for (unsigned j=0; j<N; ++j) {
257 o << " [" << table[i]->bucket[j].key << "] ";
258 }
259
260 if (table[i]->overflowBucket != nullptr) {
261 o << "Oveflow Bucket: ";
262 for (unsigned k=0; k<N; ++k) {
263 o << " [" << table[i]->overflowBucket->bucket[k].key << "] ";
264 }
265 }
266
267 o << '\n';
268 }
269 }
270
271 friend bool operator==(const ADS_set& lhs, const ADS_set& rhs) { throw std::runtime_error{ "Not implemented!" }; }
272 friend bool operator!=(const ADS_set& lhs, const ADS_set& rhs) { throw std::runtime_error{ "Not implemented!" }; }
273
274};
275
276
277template <typename Key, size_t N>
278class ADS_set<Key, N>::Iterator {
279public:
280 using value_type = Key;
281 using difference_type = std::ptrdiff_t;
282 using reference = const value_type&;
283 using pointer = const value_type*;
284 using iterator_category = std::forward_iterator_tag;
285
286 explicit Iterator(/* implementation-dependent */);
287 reference operator*() const { throw std::runtime_error{ "Not implemented!" }; }
288 pointer operator->() const { throw std::runtime_error{ "Not implemented!" }; }
289 Iterator& operator++() { throw std::runtime_error{ "Not implemented!" }; }
290 Iterator operator++(int) { throw std::runtime_error{ "Not implemented!" }; }
291 friend bool operator==(const Iterator&, const Iterator&) { throw std::runtime_error{ "Not implemented!" }; }
292 friend bool operator!=(const Iterator&, const Iterator&) { throw std::runtime_error{ "Not implemented!" }; }
293};
294
295template <typename Key, size_t N>
296void swap(ADS_set<Key,N>& lhs, ADS_set<Key,N>& rhs) {
297 lhs.swap(rhs);
298}
299
300
301#endif // ADS_SET_H