Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "Set.h"
- #include <iostream>
- void Set::initializeEmptySet()
- {
- m_size = 0;
- m_head = new Node;
- m_tail = m_head;
- m_head->m_next = nullptr;
- m_head->m_prev = nullptr;
- }
- Set::Set()
- {
- initializeEmptySet();
- }
- // Before we can actually insert the node, we need to implement the insert before function
- void Set::insertNewHead(const ItemType& value)
- {
- Node* new_head = new Node;
- new_head->m_value = value;
- m_head->m_prev = new_head;
- new_head->m_prev = nullptr;
- new_head->m_next = m_head;
- m_head = new_head;
- m_size++;
- }
- void Set::insertNewTail(const ItemType& value)
- {
- if (m_head == nullptr)
- insertNewHead(value);
- else
- {
- Node* traversal_node = m_head;
- while (traversal_node->m_next != nullptr)
- {
- traversal_node = traversal_node->m_next;
- }
- Node* new_tail = new Node;
- traversal_node->m_next = new_tail;
- new_tail->m_value = value;
- new_tail->m_prev = traversal_node;
- new_tail->m_next = nullptr;
- m_tail = new_tail;
- }
- m_size++;
- }
- void Set::insertBefore(Node* p, const ItemType& value)
- {
- //Create a new node
- Node* new_pointer = new Node;
- new_pointer->m_value = value;
- if (p == m_head)
- {
- insertNewHead(value);
- return;
- }
- // Set the new pointer's previous pointer equal to p's previous pointer
- // Then set the new pointer's next pointer equal to p
- new_pointer->m_prev = p->m_prev;
- new_pointer->m_next = p;
- // We must now make the previous nodes point to this new node
- // Then we must make the next node have its previous point to this node.
- new_pointer->m_prev->m_next = new_pointer;
- new_pointer->m_next->m_prev = new_pointer;
- m_size++;
- }
- // I have no idea how to write these function parameters
- // Why is there a Set:: before declaring a node pointer?
- // Is it because we can only define what a node pointer is after defining it's from the Set class?
- Set::Node* Set::findClosestLocation(const ItemType& value) const
- {
- Node* p = m_head;
- while (p->m_next != nullptr && p->m_value < value)
- {
- p = p->m_next;
- }
- return p;
- }
- bool Set::insert(const ItemType& value)
- {
- Node* closestNode = findClosestLocation(value);
- // When we are inserting a new head into an empty linkedList we should also initialize the tail.
- if (m_size == 0)
- {
- insertNewHead(value);
- m_tail = m_head;
- return true;
- }
- // First check if we already have that value in our linked list
- else if (closestNode->m_value == value)
- {
- return false;
- }
- // Then if it's closest node is the tail, we'll check if it should go before or after the tail
- // If we need to create a new tail, then we'll run that function
- // If not, we can actually just insert it before the tail (and run it like everything else)
- else if (closestNode == m_tail)
- {
- if (closestNode->m_value > m_tail->m_value)
- {
- insertNewTail(value);
- return true;
- }
- }
- // insertBefore command actually checks if it should be a new head
- insertBefore(closestNode, value);
- return true;
- }
- void Set::actualErase(Node* p)
- {
- if (m_size == 1)
- {
- p->m_next = p->m_prev = nullptr;
- }
- else if (p == m_head)
- {
- m_head = m_head->m_next;
- p->m_next->m_prev = nullptr;
- }
- else if (p == m_tail)
- {
- m_tail = m_tail->m_prev;
- p->m_prev->m_next = nullptr;
- }
- else
- {
- p->m_prev->m_next = p->m_next;
- p->m_next->m_prev = p->m_prev;
- }
- delete p;
- m_size--;
- }
- bool Set::erase(const ItemType& value)
- {
- Node* closestNode = findClosestLocation(value);
- if (closestNode->m_value != value)
- return false;
- actualErase(closestNode);
- return true;
- }
- Set::~Set()
- {
- while (m_size > 1)
- {
- actualErase(m_head->m_next);
- }
- delete m_head;
- }
- void Set::printLinkedList()
- {
- Node* traversalNode = m_head;
- while (traversalNode != nullptr)
- {
- std::cout << traversalNode->m_value << " ";
- traversalNode = traversalNode->m_next;
- }
- std::cout << "\n";
- }
- bool Set::contains(const ItemType& value) const
- {
- Node* closestNode = findClosestLocation(value);
- return (closestNode->m_value == value);
- }
- bool Set::get(int i, ItemType& value) const
- {
- if (i < 0 || i >= m_size)
- return false;
- Node* traversalNode;
- // Closer to head
- if (i < (m_size / 2))
- {
- traversalNode = m_head;
- for (int j = 0; j != i; j++)
- {
- traversalNode = traversalNode->m_next;
- }
- }
- // Closer to tail
- else
- {
- traversalNode = m_tail;
- for (int j = m_size - 1; j != i; j--)
- {
- traversalNode = traversalNode->m_prev;
- }
- }
- value = traversalNode->m_value;
- return true;
- }
- void Set::swap(Set& other)
- {
- Node* tempHead = other.m_head;
- other.m_head = m_head;
- m_head = tempHead;
- int tempSize = other.m_size;
- other.m_size = m_size;
- m_size = tempSize;
- // Ask Carey later about swapping tails
- // It makes sense that you can't really swap the tails after swapping the heads
- // Is there a more elegant solution though?
- Node* originalTraversalNode = m_head;
- for (int i = 1; i < m_size; i++)
- {
- originalTraversalNode = originalTraversalNode->m_next;
- }
- m_tail = originalTraversalNode;
- Node* swappedTraversalNode = other.m_head;
- for (int i = 1; i < other.m_size; i++)
- {
- swappedTraversalNode = swappedTraversalNode->m_next;
- }
- other.m_tail = swappedTraversalNode;
- }
- Set::Set(const Set& other)
- {
- initializeEmptySet();
- // Copy all non-dummy other Nodes. (This will set m_size.)
- // Inserting each new node before the dummy node that m_head points to
- // puts the new node at the end of the list.
- Node* traversalNode = other.m_head;
- for (int i = 1; i < other.m_size; i++)
- {
- insert(traversalNode->m_value);
- traversalNode = traversalNode->m_next;
- }
- }
- Set& Set::operator=(const Set& other)
- {
- // Trying to avoid aliasing, which is when we use two different pointers/ references to acess the same variable
- // This is a problem if we try to first delete the data of the original before reassigning it to itself
- // Our solution it see if the parameter has the same object address as the target object
- if (this == &other)
- {
- return *this;
- }
- // Typically, we could simply delete the elements inside the array now, but Carey doesn't want us to use a for loop
- // Thus, we will do the Smallberg method of using a copy constructor and a swap method
- // Call the copy constructor to recreate the other set and then swap elements between the original set and the copied set
- // Temporary array will actually deconstruct itself
- Set temp(other);
- swap(temp);
- Node* traversalNode = m_head;
- int i = 1;
- std::cout << "\n";
- // Return the dereferenced contents of the Sets
- // Now works for a = b = c as well
- return *this;
- }
- void unite(const Set& s1, const Set& s2, Set& result)
- {
- // We have to worry about aliasing, which is when we use two different pointers/ references to acess the same variable
- // The big worry here is if inputted result is actually s1 or s2
- // If s1, s2, and result are all the same-- then the result is already the union
- // If the result is s1, insert s2's elements into the result
- // If the result is s2, insert s1's elements into the result
- // 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
- // Naturally we will try to insert S2 into S1
- const Set* insertedNode = &s2;
- // First let's check if s1, s2, and result are all the same
- if (&result == &s1 && &result == &s2)
- {
- return;
- }
- // If result is the same as S2, we will make the insertedNode into s1
- else if (&result == &s2)
- insertedNode == &s1;
- // Now that we have determined that result is not s2 and that s1, s2, and result are not all the same
- // We will assign result to be equal to s1
- // Then we will check if s1 and s2 are the same
- // If they are, then we will simply return the set
- else
- {
- result = s1;
- if (&s1 == &s2)
- {
- return;
- }
- }
- // If s1 and s2 are not the same, then we will insert one into the other
- // If result was the same address as s2, then we will
- int size_of_insertedNode = insertedNode->size();
- ItemType x;
- for (int i = 0; i < size_of_insertedNode; i++)
- {
- insertedNode->get(i, x);
- result.insert(x);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement