Advertisement
Cinestra

Error when trying to perfect project 2

Mar 1st, 2023
45
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.50 KB | None | 0 0
  1. #include "Set.h"
  2. #include <iostream>
  3.  
  4. void Set::initializeEmptySet()
  5. {
  6. m_size = 0;
  7.  
  8. m_head = new Node;
  9. m_tail = m_head;
  10. m_head->m_next = nullptr;
  11. m_head->m_prev = nullptr;
  12. }
  13.  
  14. Set::Set()
  15. {
  16. initializeEmptySet();
  17. }
  18.  
  19. // Before we can actually insert the node, we need to implement the insert before function
  20. void Set::insertNewHead(const ItemType& value)
  21. {
  22. Node* new_head = new Node;
  23. new_head->m_value = value;
  24.  
  25. m_head->m_prev = new_head;
  26. new_head->m_prev = nullptr;
  27. new_head->m_next = m_head;
  28. m_head = new_head;
  29.  
  30. m_size++;
  31. }
  32.  
  33. void Set::insertNewTail(const ItemType& value)
  34. {
  35. if (m_head == nullptr)
  36. insertNewHead(value);
  37.  
  38. else
  39. {
  40. Node* old_tail = m_tail;
  41.  
  42. Node* new_tail = new Node;
  43. old_tail->m_next = new_tail;
  44. new_tail->m_value = value;
  45. new_tail->m_prev = old_tail;
  46. new_tail->m_next = nullptr;
  47. m_tail = new_tail;
  48. }
  49.  
  50. m_size++;
  51. }
  52.  
  53. void Set::insertBefore(Node* p, const ItemType& value)
  54. {
  55. //Create a new node
  56.  
  57. Node* new_pointer = new Node;
  58. new_pointer->m_value = value;
  59.  
  60. if (p == m_head)
  61. {
  62. insertNewHead(value);
  63. return;
  64. }
  65.  
  66. // Set the new pointer's previous pointer equal to p's previous pointer
  67. // Then set the new pointer's next pointer equal to p
  68. new_pointer->m_prev = p->m_prev;
  69. new_pointer->m_next = p;
  70.  
  71. // We must now make the previous nodes point to this new node
  72. // Then we must make the next node have its previous point to this node.
  73. new_pointer->m_prev->m_next = new_pointer;
  74. new_pointer->m_next->m_prev = new_pointer;
  75.  
  76. m_size++;
  77. }
  78.  
  79. // I have no idea how to write these function parameters
  80. // Why is there a Set:: before declaring a node pointer?
  81. // Is it because we can only define what a node pointer is after defining it's from the Set class?
  82. Set::Node* Set::findClosestLocation(const ItemType& value) const
  83. {
  84. Node* p = m_head;
  85.  
  86. while (p->m_next != nullptr && p->m_value < value)
  87. {
  88. p = p->m_next;
  89. }
  90.  
  91. return p;
  92. }
  93.  
  94. bool Set::insert(const ItemType& value)
  95. {
  96. Node* closestNode = findClosestLocation(value);
  97.  
  98. // When we are inserting a new head into an empty linkedList we should also initialize the tail.
  99. if (m_size == 0)
  100. {
  101. insertNewHead(value);
  102. m_tail = m_head;
  103. return true;
  104. }
  105.  
  106. // First check if we already have that value in our linked list
  107. else if (closestNode->m_value == value)
  108. {
  109. return false;
  110. }
  111.  
  112. // Then if it's closest node is the tail, we'll check if it should go before or after the tail
  113. // If we need to create a new tail, then we'll run that function
  114. // If not, we can actually just insert it before the tail (and run it like everything else)
  115. else if (closestNode == m_tail)
  116. {
  117. if (closestNode->m_value > m_tail->m_value)
  118. {
  119. insertNewTail(value);
  120. return true;
  121. }
  122. }
  123.  
  124. // insertBefore command actually checks if it should be a new head
  125. insertBefore(closestNode, value);
  126. return true;
  127. }
  128.  
  129. void Set::actualErase(Node* p)
  130. {
  131. // There are 4 cases to consider
  132. // If there is only a single node, then we will delete it and set its next and prev to nullptr
  133. // This is different from deleting a node in the middle because we don't have to link surrounding nodes together after deletion
  134. if (m_size == 1)
  135. {
  136. p->m_next = p->m_prev = nullptr;
  137. }
  138.  
  139. // If we are deleting the head, then we must allocate a new head
  140. else if (p == m_head)
  141. {
  142. m_head = m_head->m_next;
  143. p->m_next->m_prev = nullptr;
  144. }
  145.  
  146. // If we are deleting the tail, then we must allocate a new tail
  147. else if (p == m_tail)
  148. {
  149. m_tail = m_tail->m_prev;
  150. p->m_prev->m_next = nullptr;
  151. }
  152.  
  153. // Because we are deleting a node in the middle, we need to make sure that we are linking the surrounding nodes together
  154. else
  155. {
  156. p->m_prev->m_next = p->m_next;
  157. p->m_next->m_prev = p->m_prev;
  158. }
  159.  
  160. delete p;
  161. m_size--;
  162. }
  163.  
  164. bool Set::erase(const ItemType& value)
  165. {
  166. Node* closestNode = findClosestLocation(value);
  167.  
  168. if (closestNode->m_value != value)
  169. return false;
  170.  
  171. actualErase(closestNode);
  172. return true;
  173. }
  174.  
  175. Set::~Set()
  176. {
  177. while (m_size > 0)
  178. actualErase(m_head);
  179. }
  180.  
  181. void Set::printLinkedList()
  182. {
  183. Node* traversalNode = m_head;
  184.  
  185. while (traversalNode != nullptr)
  186. {
  187. std::cout << traversalNode->m_value << " ";
  188. traversalNode = traversalNode->m_next;
  189. }
  190.  
  191. std::cout << "\n";
  192. }
  193.  
  194. bool Set::contains(const ItemType& value) const
  195. {
  196. Node* closestNode = findClosestLocation(value);
  197. return (closestNode->m_value == value);
  198. }
  199.  
  200. bool Set::get(int i, ItemType& value) const
  201. {
  202. if (i < 0 || i >= m_size)
  203. return false;
  204.  
  205. Node* traversalNode;
  206.  
  207. // Closer to head
  208. if (i < (m_size / 2))
  209. {
  210. traversalNode = m_head;
  211. for (int j = 0; j != i; j++)
  212. {
  213. traversalNode = traversalNode->m_next;
  214. }
  215. }
  216.  
  217. // Closer to tail
  218. else
  219. {
  220. traversalNode = m_tail;
  221. for (int j = m_size - 1; j != i; j--)
  222. traversalNode = traversalNode->m_prev;
  223. }
  224.  
  225. value = traversalNode->m_value;
  226. return true;
  227. }
  228.  
  229. void Set::swap(Set& other)
  230. {
  231. Node* tempHead = other.m_head;
  232. other.m_head = m_head;
  233. m_head = tempHead;
  234.  
  235. int tempSize = other.m_size;
  236. other.m_size = m_size;
  237. m_size = tempSize;
  238.  
  239. // Ask Carey later about swapping tails
  240. // It makes sense that you can't really swap the tails after swapping the heads
  241. // Is there a more elegant solution though?
  242.  
  243. Node* originalTraversalNode = m_head;
  244. for (int i = 1; i < m_size; i++)
  245. originalTraversalNode = originalTraversalNode->m_next;
  246. m_tail = originalTraversalNode;
  247.  
  248. Node* swappedTraversalNode = other.m_head;
  249. for (int i = 1; i < other.m_size; i++)
  250. swappedTraversalNode = swappedTraversalNode->m_next;
  251. other.m_tail = swappedTraversalNode;
  252. }
  253.  
  254. Set::Set(const Set& other)
  255. {
  256. initializeEmptySet();
  257.  
  258. // Copy all non-dummy other Nodes. (This will set m_size.)
  259. // Inserting each new node before the dummy node that m_head points to
  260. // puts the new node at the end of the list.
  261.  
  262. Node* traversalNode = other.m_head;
  263.  
  264. for (int i = 1; i < other.m_size; i++)
  265. {
  266. insert(traversalNode->m_value);
  267. traversalNode = traversalNode->m_next;
  268. }
  269. }
  270.  
  271. Set& Set::operator=(const Set& other)
  272. {
  273. // Trying to avoid aliasing, which is when we use two different pointers/ references to acess the same variable
  274. // This is a problem if we try to first delete the data of the original before reassigning it to itself
  275. // Our solution it see if the parameter has the same object address as the target object
  276. if (this == &other)
  277. {
  278. return *this;
  279. }
  280.  
  281. // Typically, we could simply delete the elements inside the array now, but Carey doesn't want us to use a for loop
  282. // Thus, we will do the Smallberg method of using a copy constructor and a swap method
  283.  
  284. // Call the copy constructor to recreate the other set and then swap elements between the original set and the copied set
  285. // Temporary array will actually deconstruct itself
  286. Set temp(other);
  287. swap(temp);
  288.  
  289. Node* traversalNode = m_head;
  290. int i = 1;
  291.  
  292. std::cout << "\n";
  293.  
  294. // Return the dereferenced contents of the Sets
  295. // Now works for a = b = c as well
  296. return *this;
  297. }
  298.  
  299. void unite(const Set& s1, const Set& s2, Set& result)
  300. {
  301. // We have to worry about aliasing, which is when we use two different pointers/ references to acess the same variable
  302. // The big worry here is if inputted result is actually s1 or s2
  303.  
  304. // If s1, s2, and result are all the same-- then the result is already the union
  305. // If the result is s1, insert s2's elements into the result
  306. // If the result is s2, insert s1's elements into the result
  307. // If the result is its own distinct set, we will first assign it s1's contents, then check if s2 is the same as s1, and if they are different then we will insert s2 into s1
  308.  
  309. // Naturally we will try to insert S2 into S1
  310. const Set* insertedNode = &s2;
  311.  
  312. // First let's check if s1, s2, and result are all the same
  313. if (&result == &s1 && &result == &s2)
  314. {
  315. return;
  316. }
  317.  
  318. // If result is the same as S2, we will make the insertedNode into s1
  319. else if (&result == &s2)
  320. insertedNode == &s1;
  321.  
  322. // Now that we have determined that result is not s2 and that s1, s2, and result are not all the same
  323. // We will assign result to be equal to s1
  324. // Then we will check if s1 and s2 are the same
  325. // If they are, then we will simply return the set
  326. else
  327. {
  328. result = s1;
  329. if (&s1 == &s2)
  330. {
  331. return;
  332. }
  333. }
  334.  
  335. // If s1 and s2 are not the same, then we will insert one into the other
  336. // If result was the same address as s2, then we will
  337.  
  338. int size_of_insertedNode = insertedNode->size();
  339. ItemType x;
  340.  
  341. for (int i = 0; i < size_of_insertedNode; i++)
  342. {
  343. insertedNode->get(i, x);
  344. result.insert(x);
  345. }
  346. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement