1. #include "MultiSet.h"
2. #pragma warning (disable : 4996)
3.  
4. // Homework 2
5. // Zad 1
6. // Vasilena Stanoyska
7. // fn: 4MI0600290
8.  
9. // Big 4
10.  
11. MultiSet::MultiSet()
12. {
13.  N = 0;
14.  bucketsCount = 0;
15.  maxNumOccurencesInBucket = 0;
16.  maxBitsCount = 0;
17.  buckets = nullptr;
18. }
19.  
20. MultiSet::MultiSet(unsigned N, unsigned maxBitsCount)
21. {
22.  if (maxBitsCount < GlobalConstants::MIN_BITS_COUNT || maxBitsCount > GlobalConstants::MAX_BITS_IN_BUCKET)
23.  {
24.   maxBitsCount = GlobalConstants::DEFAULT_BITS_COUNT_VALUE;
25.  }
26.  
27.  this->N = N;
28.  this->maxBitsCount = maxBitsCount;
29.  maxNumOccurencesInBucket = std::pow(2, maxBitsCount) - 1;
30.  
31.  int totalBitsNeeded = N * maxBitsCount;
32.  bucketsCount = (totalBitsNeeded + (GlobalConstants::MAX_BITS_IN_BUCKET - 1)) / GlobalConstants::MAX_BITS_IN_BUCKET;
33.  buckets = new uint8_t[bucketsCount]{ 0 };
34. }
35.  
36. MultiSet::MultiSet(const MultiSet& other)
37. {
38.  copyFrom(other);
39. }
40.  
41. MultiSet& MultiSet::operator=(const MultiSet& other)
42. {
43.  if (this != &other;)
44.  {
45.   free();
46.   copyFrom(other);
47.  }
48.  return *this;
49. }
50.  
51. MultiSet::~MultiSet()
52. {
53.  free();
54. }
55.  
56. void MultiSet::copyFrom(const MultiSet& other)
57. {
58.  buckets = new uint8_t[other.bucketsCount];
59.  bucketsCount = other.bucketsCount;
60.  
61.  for (int i = 0; i < bucketsCount; i++)
62.   buckets[i] = other.buckets[i];
63.  
64.  maxNumOccurencesInBucket = other.maxNumOccurencesInBucket;
65.  N = other.N;
66. }
67.  
68. void MultiSet::free()
69. {
70.  delete[] buckets;
71.  buckets = nullptr;
72.  bucketsCount = 0;
73.  maxNumOccurencesInBucket = 0;
74.  N = 0;
75. }
76.  
77. // Additional functions
78. unsigned MultiSet::getBucketIndex(unsigned number) const
79. {
80.  return (number * maxBitsCount) / GlobalConstants::MAX_BITS_IN_BUCKET;
81. }
82.  
83. unsigned MultiSet::getEndIndexInBucket(unsigned number) const
84. {
85.  return ((number * maxBitsCount) % GlobalConstants::MAX_BITS_IN_BUCKET);
86. }
87.  
88. unsigned MultiSet::getStartIndexInBucket(unsigned endIndexInBucket) const
89. {
90.  return endIndexInBucket - (maxBitsCount - 1);
91. }
92.  
93. unsigned MultiSet::getNumberOccurences(unsigned number) const
94. {
95.  if (number > N)
96.  {
97.   throw std::out_of_range("Number is out of the valid range!");
98.  }
99.  
100.  int bucketIndex = getBucketIndex(number);
101.  int endIndexInBucket;
102.  int startIndexInBucket;
103.  
104.  if (number == 0)
105.  {
106.   endIndexInBucket = maxBitsCount - 1;
107.   startIndexInBucket = 1;
108.  }
109.  else
110.  {
111.   endIndexInBucket = getEndIndexInBucket(number);
112.   startIndexInBucket = getStartIndexInBucket(endIndexInBucket);
113.  }
114.  
115.  // Reasigning the startIndex when our number's bits are in two buckets
116.  if (startIndexInBucket <= 0) {
117.   startIndexInBucket += GlobalConstants::MAX_BITS_IN_BUCKET;
118.   bucketIndex -= 1; // This adjusts the bucket index when bits are split across two buckets
119.  }
120.  
121.  // Calculating carry - the amount of bits that go into the next bucket
122.  int carry = (startIndexInBucket + maxBitsCount - 1) - GlobalConstants::MAX_BITS_IN_BUCKET;
123.  
124.  unsigned occurences = 0;
125.  
126.  if (carry > 0)
127.  {
128.   // Case when we need to count the num occurences splitted in 2 buckets
129.   int countOfBitsInFirstBucket = maxBitsCount - carry;
130.   int firstBucketMask = (1 << countOfBitsInFirstBucket) - 1;
131.   firstBucketMask <<= (startIndexInBucket - 1);
132.   int firstBucketValue = (buckets[bucketIndex] & firstBucketMask) >> (startIndexInBucket - 1);
133.  
134.   int secondBucketMask = (1 << carry) - 1;
135.    int sec + 1] & secondBucketMask;
136.  
137.   secondBucketValue <<= (maxBitsCount - carry);
138.   occurences = secondBucketValue | firstBucketValue;
139.  }
140.  else
141.  {
142.   // Default case (only working in one bucket)
143.   int mask = maxNumOccurencesInBucket;
144.   mask <<= (startIndexInBucket - 1);
145.  
146.   occurences = (buckets[bucketIndex] & mask) >> (startIndexInBucket - 1);
147.  }
148.  
149.  return occurences;
150. }
151.  
152. void MultiSet::addToMultiSet(unsigned number, unsigned times)
153. {
154.  if (number > N)
155.  {
156.   throw std::out_of_range("Number is out of the valid range!");
157.  }
158.  
159.  int currentNumOccurences = getNumberOccurences(number);
160.  if (currentNumOccurences + times >= maxNumOccurencesInBucket)
161.   times = maxNumOccurencesInBucket - currentNumOccurences;
162.  
163.  int bucketIndex = getBucketIndex(number);
164.  int endIndexInBucket;
165.  int startIndexInBucket;
166.  
167.  if (number == 0)
168.  {
169.   endIndexInBucket = maxBitsCount - 1;
170.   startIndexInBucket = 1;
171.  }
172.  else
173.  {
174.   endIndexInBucket = getEndIndexInBucket(number);
175.   startIndexInBucket = getStartIndexInBucket(endIndexInBucket);
176.  }
177.  
178.  // Reasigning the startIndex when our number's bits are in two buckets
179.  if (startIndexInBucket <= 0) {
180.   startIndexInBucket += GlobalConstants::MAX_BITS_IN_BUCKET;
181.   bucketIndex -= 1;
182.  }
183.  
184.  // Calculating carry - the amount of bits that go into the next bucket
185.  int carry = (startIndexInBucket + maxBitsCount - 1) - GlobalConstants::MAX_BITS_IN_BUCKET + 1;
186.  
187.  if (carry > 0)
188.  {
189.   // Case when the bits are splitted in 2 buckets
190.   int firstBucketMask = (1 << (GlobalConstants::MAX_BITS_IN_BUCKET - (startIndexInBucket - 1))) - 1;
191.   int firstBucketValue = (buckets[bucketIndex] >> (startIndexInBucket - 1)) & firstBucketMask;
192.  
193.   int secondBucketMask = (1 << carry) - 1;
194.    int sec + 1] & secondBucketMask;
195.  
196.   int newValue = firstBucketValue + times;
197.   if (newValue >= (1 << (GlobalConstants::MAX_BITS_IN_BUCKET - (startIndexInBucket - 1))))
198.   {
199.    newValue -= (1 << (GlobalConstants::MAX_BITS_IN_BUCKET - (startIndexInBucket - 1)));
200.    secondBucketValue++; // Going to the next bucket
201.   }
202.  
203.   buckets[bucketIndex] &= ~(firstBucketMask << (startIndexInBucket - 1));
204.   newValue <<= (startIndexInBucket - 1);
205.   buckets[bucketIndex] |= newValue;
206.  
207.   buckets[bucketIndex + 1] &= ~secondBucketMask;
208.   buckets[bucketIndex + 1] |= secondBucketValue;
209.  }
210.  else
211.  {
212.   // Default case (bits are only in 1 bucket)
213.  
214.   int mask = maxNumOccurencesInBucket;
215.   int currentValue = (buckets[bucketIndex] >> (startIndexInBucket - 1)) & mask;
216.   currentValue += times;
217.  
218.   // Keeping the same value if it exceeds the maximum number of occurrences
219.   if (currentValue >= maxNumOccurencesInBucket) {
220.    currentValue--;
221.   }
222.  
223.   buckets[bucketIndex] &= ~(mask << (startIndexInBucket - 1));
224.   currentValue <<= (startIndexInBucket - 1);
225.   buckets[bucketIndex] |= currentValue;
226.  }
227. }
228.  
229. void MultiSet::printMultiSet() const
230. {
231.  std::cout << '{' << std::endl;
232.  for (int i = 0; i <= N; i++)
233.  {
234.   int bucketIndex = getBucketIndex(i);
235.   int occurencesOfI = getNumberOccurences(i);
236.   if (occurencesOfI != 0)
237.   {
238.    std::cout << "The number " << i << " is in bucket " << bucketIndex << " and appears " << occurencesOfI << " times" << std::endl;
239.   }
240.  }
241.  std::cout << '}' << std::endl;
242. }
243.  
244. void MultiSet::printMultiSetBits() const
245. {
246.  std::cout << "MultiSet Memory Representation: " << std::endl;
247.  
248.  for (unsigned i = 0; i < bucketsCount; ++i) {
249.   std::cout << "Bucket " << i << ": ";
250.   uint8_t bucket = buckets[i];
251.  
252.   for (int bit = 7; bit >= 0; bit--) {
253.    std::cout << ((bucket >> bit) & 1) << " ";  // Shift and mask to get each bit
254.   }
255.   std::cout << std::endl;
256.  }
257.  std::cout << std::endl;
258. }
259.  
260. void MultiSet::serializeInBinaryFile(const char* fileName)
261. {
262.  std::ofstream file(fileName, std::ios::binary | std::ios::out);
263.  if (!file.is_open())
264.   throw std::runtime_error("Failed to open file to write to!");
265.  
266.  file.write((const char*)&N, sizeof(N));
267.  
268.  file.write((const char*)&maxBitsCount;, sizeof(maxBitsCount));
269.  
270.  file.write((const char*)buckets, bucketsCount * sizeof(uint8_t));
271. }
272.  
273. MultiSet deserializeFromBinaryFile(const char* fileName)
274. {
275.  std::ifstream file(fileName, std::ios::binary | std::ios::in);
276.  
277.  if (!file.is_open())
278.   throw std::runtime_error("Failed to open file to write to!");
279.  
280.  unsigned newN;
281.  unsigned newMaxBitsCount;
282.  
283.  file.read((char*)&newN;, sizeof(newN));
284.  
285.  file.read((char*)&newMaxBitsCount;, sizeof(newMaxBitsCount));
286.  
287.  MultiSet deserializedSet(newN, newMaxBitsCount);
288.  
289.  file.read((char*)deserializedSet.buckets, deserializedSet.bucketsCount * sizeof(uint8_t));
290.  
291.  std::cout << "DESERIALIZED: " << std::endl;
292.  deserializedSet.printMultiSet();
293.  
294.  return deserializedSet;
295. }
296.  
297. MultiSet operator^(const MultiSet& set1, const MultiSet& set2)
298. {
299.  int resultSize = std::min(set1.N, set2.N);
300.  int resultBitsCount = std::min(set1.maxBitsCount, set2.maxBitsCount);
301.  
302.  MultiSet resultMultiSet(resultSize, resultBitsCount);
303.  
304.  for (int i = 0; i <= resultMultiSet.N; i++)
305.  {
306.   int occurencesInSet1 = set1.getNumberOccurences(i);
307.   int occurencesInSet2 = set2.getNumberOccurences(i);
308.  
309.   if (occurencesInSet1 > 0 && occurencesInSet2 > 0)
310.   {
311.    int minOccurencesCount = std::min(occurencesInSet1, occurencesInSet2);
312.    resultMultiSet.addToMultiSet(i, minOccurencesCount);
313.   }
314.  }
315.  
316.  return resultMultiSet;
317. }
318.  
319. MultiSet operator/(const MultiSet& set1, const MultiSet& set2)
320. {
321.  int resultSize = set1.N;
322.  int resultBitsCount = set1.maxBitsCount;
323.  
324.  MultiSet resultMultiSet(resultSize, resultBitsCount);
325.  for (int i = 0; i <= resultSize; i++)
326.  {
327.   int occurencesInSet1 = set1.getNumberOccurences(i);
328.   int occurencesInSet2 = set2.getNumberOccurences(i);
329.   if (occurencesInSet1 > occurencesInSet2)
330.   {
331.    int occurencesToAdd = occurencesInSet1 - occurencesInSet2;
332.    resultMultiSet.addToMultiSet(i, occurencesToAdd);
333.   }
334.  }
335.  return resultMultiSet;
336. }
337.  
338. MultiSet operator!(const MultiSet& set)
339. {
340.  MultiSet resultMultiSet(set.N, set.maxBitsCount);
341.  
342.  for (int i = 0; i < resultMultiSet.bucketsCount; i++)
343.  {
344.   resultMultiSet.buckets[i] = ~set.buckets[i];
345.  }
346.  
347.  return resultMultiSet;
348. }
349.  
350. int main()
351. {
352.  MultiSet multiset1(11, 3);
353.  MultiSet multiset2(15, 5);
354.  MultiSet deserializedSet;
355.  
356.  try {
357.   //multiset1.addToMultiSet(0, 1);
358.   multiset1.addToMultiSet(1, 1);
359.   multiset1.addToMultiSet(2, 2);
360.   multiset1.addToMultiSet(11, 4);
361.  
362.   multiset2.addToMultiSet(1, 2);
363.   multiset2.addToMultiSet(2, 1);
364.   multiset2.addToMultiSet(5, 3);
365.   multiset2.addToMultiSet(11, 3);
366.  
367.  
368.   //multiset1.serializeInBinaryFile("multiset.txt");
369.   deserializedSet = deserializeFromBinaryFile("multiset.txt");
370.  }
371.  catch (const std::out_of_range& e) {
372.   std::cerr << "Exception caught: " << e.what() << std::endl;
373.  }
374.  catch (const std::runtime_error& e)
375.  {
376.   std::cerr << "An error occured: " << e.what() << std::endl;
377.  }
378.  catch (const std::exception& e) {  // To catch other types of exceptions
379.   std::cerr << "An exception occurred: " << e.what() << std::endl;
380.  }
381.  
382.  std::cout << "First Set: " << std::endl;
383.  multiset1.printMultiSet();
384.  multiset1.printMultiSetBits();
385.  
386.  std::cout << "Second Set: " << std::endl;
387.  multiset2.printMultiSet();
388.  multiset2.printMultiSetBits();
389.  
390.  std::cout << "Intersection: " << std::endl;
391.  MultiSet intersectSet = operator^(multiset1, multiset2);
392.  intersectSet.printMultiSet();
393.  intersectSet.printMultiSetBits();
394.  
395.  std::cout << "Difference: " << std::endl;
396.  MultiSet differenceSet = operator/(multiset1, multiset2);
397.  differenceSet.printMultiSet();
398.  differenceSet.printMultiSetBits();
399.  
400.  std::cout << "Complement set: " << std::endl;
401.  MultiSet complementSet = operator!(multiset1);
402.  complementSet.printMultiSet();
403.  complementSet.printMultiSetBits();
404.  
405.  std::cout << "Deserialized set: " << std::endl;
406.  deserializedSet.printMultiSet();
407.  deserializedSet.printMultiSetBits();
408. }
409.