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;
- Node* tempTail = other.m_tail;
- other.m_tail = m_tail;
- m_tail = tempTail;
- int tempSize = other.m_size;
- other.m_size = m_size;
- m_size = tempSize;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement