AbstractDataTypes.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1><center>COMP20230: Data Structures & Algorithms</center></h1>\n",
    "<h2><center>Assignment 2</center></h2>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "import timeit\n",
    "import unittest"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 1\n",
    "### Q1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Please see class myLinkedList below with the following methods:\n",
    "\n",
    "- add_first\n",
    "- add_last\n",
    "- remove_first\n",
    "- list_traversal\n",
    "\n",
    "Additional methods were also implemented which include:\n",
    "\n",
    "- size\n",
    "- insert_after\n",
    "- insert_before\n",
    "- insert_at_index\n",
    "- search_item\n",
    "- remove_at_end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Objects of this class will be the nodes that we insert into myLinkedList\n",
    "class Node:\n",
    "    def __init__(self, inputData):\n",
    "        self.item = inputData\n",
    "        self.ref = None\n",
    "\n",
    "# myLinkedList will contain methods to manipulate Linked Lists\n",
    "class myLinkedList:\n",
    "    def __init__(self):\n",
    "        self.createNode = None\n",
    "    \n",
    "    # Inserts item at the start of the list\n",
    "    def add_first(self, inputData):\n",
    "        newNode = Node(inputData)\n",
    "        newNode.ref = self.createNode\n",
    "        self.createNode = newNode\n",
    "    \n",
    "    # Inserts item at the end of a list\n",
    "    def add_last(self, inputData):\n",
    "        newNode = Node(inputData)\n",
    "        if self.createNode is None:\n",
    "            self.createNode = newNode\n",
    "            return\n",
    "        n = self.createNode\n",
    "        while n.ref is not None:\n",
    "            n = n.ref\n",
    "        n.ref = newNode;\n",
    "    \n",
    "    # Removes a node at the front of a list\n",
    "    def remove_first(self):\n",
    "        if self.createNode is None:\n",
    "            print(\"There are no elements to delete\")\n",
    "            return \n",
    "        self.createNode = self.createNode.ref\n",
    "\n",
    "    # Traversing the list\n",
    "    def list_traversal(self):\n",
    "        if self.createNode is None:\n",
    "            print(\"The list has no elements\")\n",
    "            return\n",
    "        else:\n",
    "            n = self.createNode\n",
    "            while n is not None:\n",
    "                print(n.item, \" \")\n",
    "                n = n.ref\n",
    "              \n",
    "    # The following counts the toal number of elements        \n",
    "    def size(self):\n",
    "        if self.createNode is None:\n",
    "            return 0;\n",
    "        n = self.createNode\n",
    "        count = 0;\n",
    "        while n is not None:\n",
    "            count = count + 1\n",
    "            n = n.ref\n",
    "        return count\n",
    "    \n",
    "    # Adds item after another specified item\n",
    "    def insert_after(self, x, inputData):\n",
    "        n = self.createNode\n",
    "        print(n.ref)\n",
    "        while n is not None:\n",
    "            if n.item == x:\n",
    "                break\n",
    "            n = n.ref\n",
    "        if n is None:\n",
    "            print(\"The item does not appear in the list\")\n",
    "        else:\n",
    "            newNode = Node(inputData)\n",
    "            newNode.ref = n.ref\n",
    "            n.ref = newNode\n",
    "    \n",
    "    # Adds item before another specified item\n",
    "    def insert_before(self, x, inputData):\n",
    "        if self.createNode is None:\n",
    "            print(\"There are no elements in the list\")\n",
    "            return\n",
    "\n",
    "        if x == self.createNode.item:\n",
    "            newNode = Node(inputData)\n",
    "            newNode.ref = self.createNode\n",
    "            self.createNode = newNode\n",
    "            return\n",
    "\n",
    "        n = self.createNode\n",
    "        print(n.ref)\n",
    "        while n.ref is not None:\n",
    "            if n.ref.item == x:\n",
    "                break\n",
    "            n = n.ref\n",
    "        if n.ref is None:\n",
    "            print(\"The item does not appear in the list\")\n",
    "        else:\n",
    "            newNode = Node(inputData)\n",
    "            newNode.ref = n.ref\n",
    "            n.ref = newNode\n",
    "    \n",
    "    # Insert item at specified index\n",
    "    def insert_at_index (self, index, inputData):\n",
    "        if index == 1:\n",
    "            newNode = Node(inputData)\n",
    "            newNode.ref = self.createNode\n",
    "            self.createNode = newNode\n",
    "        i = 1\n",
    "        n = self.createNode\n",
    "        while i < index-1 and n is not None:\n",
    "            n = n.ref\n",
    "            i = i+1\n",
    "        if n is None:\n",
    "            print(\"That index does not exist\")\n",
    "        else: \n",
    "            newNode = Node(inputData)\n",
    "            newNode.ref = n.ref\n",
    "            n.ref = newNode\n",
    "\n",
    "    # Searches for a specified element        \n",
    "    def search_item(self, x):\n",
    "        if self.createNode is None:\n",
    "            print(\"List has no elements\")\n",
    "            return\n",
    "        n = self.createNode\n",
    "        while n is not None:\n",
    "            if n.item == x:\n",
    "                print(\"The item was found!\")\n",
    "                return True\n",
    "            n = n.ref\n",
    "        print(\"The item was not found\")\n",
    "        return False\n",
    "    \n",
    "    # Removes element at the end of the list\n",
    "    def remove_at_end(self):\n",
    "        if self.createNode is None:\n",
    "            print(\"The list has no elements to remove\")\n",
    "            return\n",
    "\n",
    "        n = self.createNode\n",
    "        while n.ref.ref is not None:\n",
    "            n = n.ref\n",
    "        n.ref = None \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Giving Examples to test the operation of myLinkedList which include:\n",
    "- Adding new elements\n",
    "- Removing elements from the list\n",
    "- Printing the content of the list after each operation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Initialising the linked list\n",
    "Linkedlist = myLinkedList()\n",
    "\n",
    "# Demonstrating adding new elements\n",
    "Linkedlist.add_last(10)\n",
    "Linkedlist.add_last(15)\n",
    "Linkedlist.add_first(5)\n",
    "Linkedlist.add_first(20)\n",
    "\n",
    "# Printing the list after each operation\n",
    "print(\"After adding elements, the list now contains: \")\n",
    "Linkedlist.list_traversal()\n",
    "\n",
    "# Removing elements from the list\n",
    "Linkedlist.remove_first()\n",
    "\n",
    "# Demonstrating the printing of the content\n",
    "print(\"\\nAfter removing the first element, the list now contains: \")\n",
    "Linkedlist.list_traversal()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q2."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Stack ADT:\n",
    "\n",
    "A stack ADT (Abstract Data Type) behaves how a real-world stack would; for example, a deck of card. You can place or take a card from the top of a stack only. Similarly with a stack ADT, it only allows data operations at one end only.\n",
    "\n",
    "This feature implements a LIFO data structure. LIFO stands for Last-in-first out. The element that is inserted or added last is accessed first. The insertion operation is called <b>Push</b> and the removal operation is called <b>Pop</b>.\n",
    "\n",
    "A Stack contains elements of the same type arranged in sequential order. All operations take place at a single end that is top of the stack and we will now discuss the operations can be performed.\n",
    "\n",
    "##### Operations\n",
    "\n",
    "The key operations for the stack ADT include:\n",
    "- <b>push</b>: Insert an element at one end of the stack called top.\n",
    "- <b>pop</b>: Remove and return the element at the top of the stack, if it is not empty.\n",
    "\n",
    "The support operations for the stack ADT include:\n",
    "- <b>peek</b>: Return the element at the top of the stack without removing it, if the stack is not empty.\n",
    "- <b>size</b>: Return the number of elements in the stack.\n",
    "- <b>isEmpty</b>: Return true if the stack is empty, otherwise return false.\n",
    "- <b>isFull</b>: Return true if the stack is full, otherwise return false.\n",
    "\n",
    "\n",
    "##### Examples\n",
    "\n",
    "One real world data example of a stack ADT is for the back button on a web browser or similarly the undo/redo option within Excel or Word. This operation is accomplished by keeping all text changes in a stack. Each action in your editor generates a new undo command that goes into the undo stack. Each undo action generates the corresponding redo command that goes into the redo stack.\n",
    "\n",
    "Another real world data example is for language processing. Space for parameters and local variables is created internally using a stack. As well as this, the compiler's syntax for matching braces is implemented by using a stack.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Queue ADT:\n",
    "\n",
    "The queue ADT (Abstract Data Type) is analogous to how queues function in real-life. We impose an order on a list of objects based on the order in which the objects have been added to the list. Queues work on a First-In First-Out <b>(FIFO)</b> basis. Items are inserted at the rear <b>(enqueued)</b> and removed from the front <b>(dequeued)</b>. The item that has been in the queue for the longest time, gets served first. The only accessible item in the queue is the one at the front. This item must be dequeued before the item behind it is available for access. Items added to the queue are added at the rear and are not accessible until after all preceding items have been dequeued.\n",
    "\n",
    "This data structure has many useful applications in computer science. Any application where only one request is processed at a time but the rate of receiving requests may be faster than the rate of processing would be a candidate for using a queue data structure. In such cases a queue may act as a buffer with an imposed order which ensures requests are processed in the order they arrived.\n",
    "\n",
    "A queue contains elements of the same type arranged in sequential order. Operations take place at both ends, insertion is done at the end and deletion is done at the front. We will now the disccuss the operations that can be performed:\n",
    "\n",
    "##### Operations\n",
    "\n",
    "As we touched on briefly, the key operations for the queue ADT include:\n",
    "\n",
    "- <b>enqueue</b>: This operation takes an object and adds it to the rear of a queue.\n",
    "- <b>dequeue</b>: This operation removes an object at the head of the queue.\n",
    "\n",
    "As well as the key operations, there is also support operations, which include:\n",
    "\n",
    "- <b>size</b>: This operation returns the number of objects contained in the queue.\n",
    "- <b>is_empty</b>: This operation returns true if the queue is empty, false otherwise.\n",
    "- <b>front</b>: This operation returns the object at the front of the queue. This can also be called \"Peek\".\n",
    "\n",
    "##### Examples\n",
    "\n",
    "One real world data example of a Queue can be seen in Operating systems for job scheduling. The OS maintains a separate queue for each of the process states and PCBs of all processes in the same execution state are placed in the same queue. When the state of a process is changed, its PCB is unlinked from its current queue and moved to its new state queue.\n",
    "\n",
    "The second real world data example can be seen in Disk scheduling or I/O scheduling. Multiple requests may arrive by different processes, however only one request can be handled at a time by the disk controller. Therefore, other I/O requests need to be put into the queue and need to be scheduled. \n",
    "\n",
    "The final real world data example we will look at is Breadth First Search (BFS), which is an algorithm for traversing graph data strcutures. BFS leans on the queue data structure and works by traversing all the nodes in the graph and drops them when they are completed. BFS visits an adjacent unvisited node, marks it as done, and inserts it into a queue."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 2\n",
    "### Q1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Stack ADT Implementation \n",
    "\n",
    "Please see the Stack ADT implementation below with the following methods:\n",
    "\n",
    "- push()\n",
    "- pop()\n",
    "- isEmpty()\n",
    "- peek()\n",
    "\n",
    "All methods take O(1) time. We do not run any loop in any of these operations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class StackNode:\n",
    " \n",
    "    # Constructor to initialize a node\n",
    "    def __init__(self, inputData):\n",
    "        self.inputData = inputData\n",
    "        self.next = None\n",
    "\n",
    "class Stack:\n",
    " \n",
    "    # Constructor to initialize the root of linked list\n",
    "    def __init__(self):\n",
    "        self.root = None#\n",
    "        \n",
    "    # Adds an items to the stack\n",
    "    def push(self, inputData):\n",
    "        newNode = StackNode(inputData)\n",
    "        newNode.next = self.root\n",
    "        self.root = newNode\n",
    "        print(inputData, \"was pushed to the stack\")\n",
    "        \n",
    "    # Removes an item from the stack    \n",
    "    def pop(self):\n",
    "        if (self.isEmpty()):\n",
    "            return float(\"-inf\")\n",
    "        temp = self.root\n",
    "        self.root = self.root.next\n",
    "        popped = temp.inputData\n",
    "        print(popped, \"was popped from the stack\")\n",
    "    \n",
    "    # Returns true if the stack is empty, else false\n",
    "    def isEmpty(self):\n",
    "        return True if self.root is None else False\n",
    "     \n",
    "    # Returns the top element of the stack\n",
    "    def peek(self):\n",
    "        if self.isEmpty():\n",
    "            return float(\"-inf\")\n",
    "        return self.root.inputData\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q2."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Executing Stack ADT operations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Initialising the stack\n",
    "stack = Stack()\n",
    "\n",
    "# Push & Pop Operations\n",
    "stack.push(5) \n",
    "stack.push(3)\n",
    "stack.pop()\n",
    "stack.push(2)\n",
    "stack.push(8)\n",
    "stack.pop()\n",
    "stack.pop()\n",
    "stack.push(9)\n",
    "stack.push(1)\n",
    "stack.pop()\n",
    "stack.push(7)\n",
    "stack.push(6)\n",
    "stack.pop()\n",
    "stack.pop()\n",
    "stack.push(4)\n",
    "stack.pop()\n",
    "stack.pop()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q3."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Data Structure Question Related to Stacks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- A total of 35 elements were pushed to the stack (S).\n",
    "- 10 pop operations were carried out, 3 of which raised errors (10 - 3 = 7).\n",
    "- 15 top operations were carried out. Top operations do not change the state and size of the stack and can be ignored."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- The order of operations does not matter, only the amount of successful pops()s and push()s\n",
    "- 35 successful pushes\n",
    "- 7 successful pops\n",
    "\n",
    "#### Current size of the stack (S)\n",
    "- (35 - 7 = 28)\n",
    "- The current size of the stack is <b>28</b>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 3\n",
    "### Q1."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Queue ADT Implementation \n",
    "\n",
    "Please see the queue ADT implementation below with the following methods:\n",
    "\n",
    "- dequeue()\n",
    "- enqueue()\n",
    "- peek()\n",
    "- size()\n",
    "- isEmpty()\n",
    "- isFull()\n",
    "\n",
    "\n",
    "All methods take O(1) time. We do not run any loop in any of these operations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Custom queue implementation in Python\n",
    "class Queue:\n",
    "\n",
    "    # Initialise queue\n",
    "    def __init__(self, size):\n",
    "        self.q = [None] * size    # list to store queue elements\n",
    "        self.capacity = size      # maximum capacity of the initialised queue\n",
    "        self.front = 0            # front points to the front element in the queue\n",
    "        self.rear = -1            # rear points to the last element in the queue\n",
    "        self.count = 0            # current size of the queue\n",
    "\n",
    "\n",
    "    # Function to dequeue the front element\n",
    "    def dequeue(self):\n",
    "        # check for queue underflow\n",
    "        if self.isEmpty():\n",
    "            print(\"Underflow has occured. The process will now be terminated.\")\n",
    "            exit(1)\n",
    "\n",
    "        print(\"Removing element \", self.q[self.front])\n",
    "\n",
    "        self.front = (self.front + 1) % self.capacity\n",
    "        self.count = self.count - 1\n",
    "\n",
    "\n",
    "    # Function to add an element to the queue\n",
    "    def enqueue(self, inputData):\n",
    "        # check for queue overflow\n",
    "        if self.isFull():\n",
    "            print(\"Overflow has occured. The process will now be terminated.\")\n",
    "            exit(1)\n",
    "\n",
    "        print(\"Inserting element \", inputData)\n",
    "\n",
    "        self.rear = (self.rear + 1) % self.capacity\n",
    "        self.q[self.rear] = inputData\n",
    "        self.count = self.count + 1\n",
    "\n",
    "\n",
    "    # Function to return the front element of the queue\n",
    "    def peek(self):\n",
    "        if self.isEmpty():\n",
    "            print(\"Underflow has occured. The process will now be terminated.\")\n",
    "            exit(1)\n",
    "\n",
    "        return self.q[self.front]\n",
    "\n",
    "\n",
    "    # Function to return the size of the queue\n",
    "    def size(self):\n",
    "        return self.count\n",
    "\n",
    "\n",
    "    # Function to check if the queue is empty or not\n",
    "    def isEmpty(self):\n",
    "        return self.size() == 0\n",
    "\n",
    "\n",
    "    # Function to check if the queue is full or not\n",
    "    def isFull(self):\n",
    "        return self.size() == self.capacity"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q2."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Executing Queue ADT operations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Initialising the queue for 10 elements\n",
    "Q = Queue(10)\n",
    "\n",
    "# enqueue and dequeue operaions\n",
    "Q.enqueue(5)\n",
    "Q.enqueue(3)\n",
    "Q.dequeue()\n",
    "Q.enqueue(2)\n",
    "Q.enqueue(8)\n",
    "Q.dequeue()\n",
    "Q.dequeue()\n",
    "Q.enqueue(9)\n",
    "Q.enqueue(1)\n",
    "Q.dequeue()\n",
    "Q.enqueue(7)\n",
    "Q.enqueue(6)\n",
    "Q.dequeue()\n",
    "Q.dequeue()\n",
    "Q.enqueue(4)\n",
    "Q.dequeue()\n",
    "Q.dequeue()\n",
    "\n",
    "# size and peek operations\n",
    "print(\"\\nNumber of elements remaining in the queue: \", Q.size())\n",
    "print(\"The element in the queue is: \", Q.peek())\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Q3."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Data Structure Question Related to Stacks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- A total of 50 enqueue operations are carried out on an empty queue (Q).\n",
    "- 15 dequeue operations were carried out, 5 of which raised errors (15 - 5 = 10).\n",
    "- 15 top operations were carried out. Top operations do not change the state and size of the stack and can be ignored."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- The order of operations does not matter, only the amount of successful enqueue()s and dequeue()s\n",
    "- 50 successful enqueues\n",
    "- 10 successful dequeues\n",
    "\n",
    "#### Current size of the queue (Q)\n",
    "- (50 - 10 = 40)\n",
    "- The current size of the stack is <b>40</b>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Things to Consider:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Speed:\n",
    "We will now test the running time as the input size grows, and compare running-time vs time complexity by plotting the following:\n",
    "- myLinkedList's add_first() method \n",
    "- Stack ADT's push() method\n",
    "- Queue ADT's enqueue() method"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# The test input we will be using for comparing running-time vs time complexity\n",
    "testInput = [20,220,420,620,820]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Testing LinkedList's add_first method for running-time and time complexity\n",
    "\n",
    "testLinkedList = myLinkedList()\n",
    "\n",
    "linkedTime = []\n",
    "linkedInput = []\n",
    "\n",
    "# Running 100 times and getting an average time\n",
    "for y in (testInput):\n",
    "    Timer = (timeit.timeit(f\"testLinkedList.add_first({y})\", \"from __main__ import testLinkedList,y\", number=100))/100\n",
    "    linkedTime.append(Timer)\n",
    "    linkedInput.append(y)\n",
    "    \n",
    "\n",
    "plt.xlabel('Linked List Input') \n",
    "plt.ylabel('Execution time in secs')\n",
    "plt.margins(0,15)\n",
    "plt.plot(linkedInput, linkedTime, label = \"Add First Method\")\n",
    "\n",
    "plt.grid()\n",
    "plt.legend(prop={\"size\":12})\n",
    "plt.savefig(\"LinkedListTimeComplexity\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Result:\n",
    "- After running myLinkedList's add_first() method, we can see that the time complexity of running our test input was O(1), as expected."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Testing Stack ADT's push() method for running-time and time complexity\n",
    "\n",
    "testStack = Stack()\n",
    "\n",
    "stackTime = []\n",
    "stackInput = []\n",
    "\n",
    "# Running 100 times and getting an average time\n",
    "for y in (testInput):\n",
    "    Timer = (timeit.timeit(f\"testStack.push({y})\", \"from __main__ import testStack,y\", number=100))/100\n",
    "    stackTime.append(Timer)\n",
    "    stackInput.append(y)\n",
    "    \n",
    "\n",
    "plt.xlabel('Stack Input') \n",
    "plt.ylabel('Execution time in secs')\n",
    "plt.margins(0,15)\n",
    "plt.plot(stackInput, stackTime, label = \"Push Method\")\n",
    "\n",
    "plt.grid()\n",
    "plt.legend(prop={\"size\":12})\n",
    "plt.savefig(\"StackTimeComplexity\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Result:\n",
    "- After running Stack ADT's push() method, we can see that it has a time complexity of O(1) as expected"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Testing Queue ADT's enqueue() method for running-time and time complexity\n",
    "\n",
    "testQueue = Queue(600)\n",
    "\n",
    "queueTime = []\n",
    "queueInput = []\n",
    "\n",
    "# Running 100 times and getting an average time\n",
    "for y in (testInput):\n",
    "    Timer = (timeit.timeit(f\"testQueue.enqueue({y})\", \"from __main__ import testQueue,y\", number=100))/100\n",
    "    queueTime.append(Timer)\n",
    "    queueInput.append(y)\n",
    "    \n",
    "\n",
    "plt.xlabel('Queue Input') \n",
    "plt.ylabel('Execution time in secs')\n",
    "plt.margins(0,15)\n",
    "plt.plot(queueInput, queueTime, label = \"Enqueue Method\")\n",
    "\n",
    "plt.grid()\n",
    "plt.legend(prop={\"size\":12})\n",
    "plt.savefig(\"QueueTimeComplexity\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Result:\n",
    "- By running the enqueue() method and plotting it on a graph, we can see that the graph displays O(1) time complexity as expected."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Efficiency:\n",
    "\n",
    "For Queue's ADT class, it is a requirement to specify the size of the list as you initialise the queue, this ensures optimum efficiency. The user must know the size of the queue list prior to initalisation.\n",
    "\n",
    "There is sufficient test coverage done throughout notebook. The The linked list class, Stack ADT class and Queue ADT class have all been thoroughly tested with large quantities (18+ digits) to ensure it has the right dependencies and the capabilities to handle large volumes of data. The classes should be able to handle any edge cases with ease. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Clarity & Correctness:\n",
    "\n",
    "- Naming conventions for variables, methods and classes were picked to ensure maximum readibility and clarity for the user.\n",
    "- This ensures the code is easy to read, understand and modify.\n",
    "- Comments have been inserted judiously throughout the notebook.\n",
    "- There are no instances of hardcoding within the code and have ensured it is scalable as demonstrated when testing for running-time and time complexity."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Maintainability:\n",
    "- As stated, comments have been placed judiciously throughout the code to ensure maximum clarity.\n",
    "- Please see <b>unit tests</b> below to test key functionality.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Unit Tests:\n",
    "9 Unit tests were carried out on:\n",
    "- myLinkedList() - (size, search_item, list_traversal)\n",
    "- Stack() - (isEmpty, peek)\n",
    "- Queue() - (isEmpty, peek, isFull, size)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test Input we will be using for our unit tests\n",
    "testInput2 = [150, 300, 450]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TestMyLinkedList(unittest.TestCase):\n",
    "    def test_size(self):\n",
    "        newLinkedList = myLinkedList()\n",
    "        self.assertEqual(newLinkedList.size(), 0)\n",
    "        \n",
    "    def test_searchItem(self):\n",
    "        newLinkedList2 = myLinkedList()\n",
    "        newLinkedList2.add_first(10)\n",
    "        self.assertTrue(newLinkedList2.search_item(10))\n",
    "        \n",
    "    def test_ListTraversal(self):\n",
    "        newLinkedList3 = myLinkedList()\n",
    "        newLinkedList3.add_first(5)\n",
    "        newLinkedList3.add_first(6)\n",
    "        newLinkedList3.add_first(7)\n",
    "        self.assertNotEqual(newLinkedList3.list_traversal(),8)\n",
    "        \n",
    "unittest.main(argv=[\"\"],verbosity=2, exit=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TestStack(unittest.TestCase):\n",
    "    def test_isEmpty(self):\n",
    "        stackADT = Stack()\n",
    "        self.assertTrue(stackADT.isEmpty)\n",
    "        \n",
    "    def test_peek(self):\n",
    "        stackADT2 = Stack()\n",
    "        for y in (testInput2):\n",
    "            stackADT2.push(y)\n",
    "            self.assertEqual(stackADT2.peek(), y)\n",
    "\n",
    "unittest.main(argv=[\"\"],verbosity=2, exit=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "class TestQueue(unittest.TestCase):\n",
    "    def test_isEmpty(self):\n",
    "        newQueue = Queue(5)\n",
    "        self.assertTrue(newQueue.isEmpty)\n",
    "        \n",
    "    def test_peek(self):\n",
    "        newQueue1 = Queue(5)\n",
    "        newQueue1.enqueue(2)\n",
    "        self.assertEqual(newQueue1.peek(),2)\n",
    "        \n",
    "    def test_isFull(self):\n",
    "        newQueue2 = Queue(1)\n",
    "        newQueue2.enqueue(10)\n",
    "        self.assertTrue(newQueue2.isFull())\n",
    "        \n",
    "    def test_size(self):\n",
    "        newQueue3 = Queue(5)\n",
    "        newQueue3.enqueue(10)\n",
    "        newQueue3.enqueue(12)\n",
    "        newQueue3.enqueue(14)\n",
    "        self.assertEqual(newQueue3.size(),3)\n",
    "    \n",
    "unittest.main(argv=[\"\"],verbosity=2, exit=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Conclusion: \n",
    "To conclude, we have implemented the myLinkedList() class, it's key operations and demonstrated some examples of these operations in use. We then defined Stack ADT and Queue ADT, giving their key/support operations as well as associated real world data examples.\n",
    "We then implemented the Stack() class, it's key operations and demonstrated examples of these operations in use. We then answered a data structures programming quesion in realtion to Stack ADT.\n",
    "In the last section, we implemented the Queue() class and it's key operations. We demonstrated examples of these operations in use and answered a data structures programming quesion in realtion to Queue ADT.\n",
    "\n",
    "After implementing both the Stack() and Queue() classes, the difference we can see between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.\n",
    "\n",
    "We demonstrated the <b>Speed</b> of the classes by testing running time as the input size grows, and compare running-time vs time complexity and plotting it on a graph for each of the classes. As stated, in each of the graphs, the time complexity of O(1) can be seen, as expected. We then discussed the <b>Efficiency</b>, <b>Clarity</b> and <b>Correctness</b> of the notebook. To illustrate the <b>Maintainability</b>, we implemented 9 unit tests which all run successfully."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}