path: root/hw4/assignment_lists_sortingandsearching_f22.py

# -*- coding: utf-8 -*-
"""assignment-lists-sortingAndSearching_f22.ipynb

Automatically generated by Colaboratory.

Original file is located at
    https://colab.research.google.com/drive/1Ra4cQV_Fn1TwDr-EzF2VlzM3Pnk752PA
"""



"""### Doubly Linked List

We have previously developed a doubly linked list in an object oriented way. A proper implementation is found below, but feel free to use the code you wrote instead of mine.

The code needs to be extended to have Class functions that will search for values and also will sort the values.

## Constructing a Doubly Linked List

The **Node** and **Doubly Linked List** class implementations are given:
"""

class Node(object):
    """Doubly linked node which stores an object"""

    def __init__(self, element, next_node=None, previous_node=None):
        # The underscores are to prevent overwriting the variables if inherited and prevents access from outside of scope
        self.__element = element
        self.__next_node = next_node
        self.__previous_node = previous_node

    def get_element(self):
        """Returns the element stored in this node"""
        return self.__element

    def get_previous(self):
        """Returns the previous linked node"""
        return self.__previous_node

    def get_next(self):
        """Returns the next linked node"""
        return self.__next_node

    def set_element(self, element):
        """Sets the element stored in this node"""
        self.__element = element

    def set_previous(self, previous_node):
        """Sets the previous linked node"""
        self.__previous_node = previous_node

    def set_next(self, next_node):
        """Sets the next linked node"""
        self.__next_node = next_node

    def __gt__(self, node):
        if self.get_element() > node.get_element():
            return True
        return False

    def __ge__(self, node):
        if node.get_element() <= self.get_element():
            return True
        return False

    def __str__(self):
        return str(self.__element)

class DoublyLinkedList(object):
    """Doubly linked node data structure"""

    def __init__(self):
        self.__size = 0
        self.__header = Node('Header')
        self.__trailer = Node('Trailer')
        self.__header.set_next(self.__trailer)
        self.__trailer.set_previous(self.__header)
        self.__current = None

    def __repr__(self):
        if not self.is_empty():
            out = f'('
            for node in self:
                out += f"({node.get_element()}), "
            out = out[:-2]
            out += ')'
        else:
            out = 'Empty List'
        return out
    def __iter__(self):
        self.__current = None
        return self

    def __next__(self):
        """Standard python iterator method"""
        if self.is_empty() or self.__current == self.__trailer:
            raise StopIteration()
        elif self.__current is None:
            self.__current = self.__header
        self.__current = self.__current.get_next()
        if self.__current != self.__trailer:
            return self.__current
        else:
            raise StopIteration()

    def map(self, function):
        """Run function on every element in the list"""
        for node in self:
            if node != self.__trailer and node != self.__header:
                node.set_element(function(node.get_element()))

    def size(self):
        """Returns the number of elements in the list"""
        return self.__size

    def is_empty(self):
        """Returns the number of elements in the list"""
        return self.__size == 0

    def get_first(self):
        """Get the first element of the list"""
        if self.is_empty():
            raise Exception("List is empty")
        else:
            return self.__header.get_next()

    def get_last(self):
        """Get the last element of the list"""
        if self.is_empty():
            raise Exception("List is empty")
        else:
            return self.__trailer.get_previous()

    def get_previous(self, node):
        """Returns the node before the given node"""
        if node == self.__header:
            raise Exception("Cannot get the element before the header of this list")
        else:
            return node.get_previous()

    def get_next(self, node):
        """Returns the node after the given node"""
        if node == self.__trailer:
            raise Exception("Cannot get the element after the trailer of this list")
        else:
            return node.get_next()

    def add_before(self, new, existing):
        """Insert the new before existing"""
        previous_existing = self.get_previous(existing)
        new.set_previous(previous_existing)
        new.set_next(existing)
        existing.set_previous(new)
        previous_existing.set_next(new)
        self.__size += 1

    def add_after(self, new, existing):
        """Insert the new after existing"""
        next_existing = self.get_next(existing)
        new.set_previous(existing)
        new.set_next(next_existing)
        existing.set_next(new)
        next_existing.set_previous(new)
        self.__size += 1

    def add_first(self, new):
        """Insert the node at the head of the list"""
        self.add_after(new, self.__header)

    def add_last(self, new):
        """Insert the node at the tail of the list"""
        self.add_before(new, self.__trailer)

    def remove(self, node):
        """Removes the given node from the list"""
        before = self.get_previous(node)
        after = self.get_next(node)
        before.set_next(after)
        after.set_previous(before)
        node.set_next(None)
        node.set_previous(None)
        self.__size -= 1
        return node

    def __getitem__(self, index):
        """
        Move to a given index in the list
        I copied this over from the last assignment to make things easier
        """
        assert index < self.__size
        if index < (self.__size // 2):
            pos = self.get_next(self.__header)
            for _ in range(index):
                pos = self.get_next(pos)
        else:
            pos = self.__trailer
            for _ in range(self.__size - index):
                pos = self.get_previous(pos)

        return pos

    def swap(self, target, moving):
        """
        prev -> moving - > target

        >>> dll = DoublyLinkedList()
        >>> dll.add_last(Node('a'))
        >>> b = Node('b')
        >>> dll.add_last(b)
        >>> c = Node('c')
        >>> dll.add_last(c)
        >>> dll
        ((a), (b), (c))
        >>> dll.swap(b, c)
        >>> dll
        ((a), (c), (b))
        """
        if moving == self.__trailer or moving == self.__header:
            raise Exception("You cannot move the header or trailer")
        pm = moving.get_previous()
        am = moving.get_next()
        pm.set_next(am)
        am.set_previous(pm)
        prev = target.get_previous()
        prev.set_next(moving)
        moving.set_previous(prev)
        moving.set_next(target)
        target.set_previous(moving)


    def swap_forward(self, node):
        """
        before: prev -> node -> next
        after:  prev -> next -> node

        >>> dll = DoublyLinkedList()
        >>> dll.add_first(Node('a'))
        >>> dll.add_first(Node('b'))
        >>> c = Node('c')
        >>> dll.add_first(c)
        >>> dll.swap_forward(c)
        >>> dll
        ((b), (c), (a))
        """
        self.swap(node, node.get_next())

    def swap_backward(self, node):
        """
        before: prev -> node -> next
        after:  next -> prev -> next

        >>> dll = DoublyLinkedList()
        >>> dll.add_last(Node('a'))
        >>> dll.add_last(Node('b'))
        >>> c = Node('c')
        >>> dll.add_last(c)
        >>> dll.swap_backward(c)
        >>> dll
        ((a), (c), (b))
        """
        self.swap(node.get_previous(), node)

    def replace(self, new, existing):
        """
        before: prev -> existing -> next
        after: prev -> new -> next
        """
        self.add_before(new, existing)
        self.remove(existing)

    def sequential_search(self,value):
        """Finds the value in the list and returns the node"""
        for node in self:
            if node.get_element() == value:
                return node
        return None

    def binary_search(self,value):
        """Implementation of a binary search for a value,
            also returns the node"""
        #HINT: REQUIRES THE LIST TO BE SORTED!
        max = self.size()
        index = max // 2
        val = self[index]
        while val.get_element() != value:
            if index <= 0 or index >= self.size() - 1:
                return None
            elif val.get_element() > value:
                max = index
                index = index // 2
                val = self[index]
            else:
                index += (max - index) // 2
                val = self[index]
        return val

    def bubble_sort(self):
        """
        >>> dll = DoublyLinkedList()
        >>> [ dll.add_first(Node(i)) for i in range(20) ]
        >>> dll.bubble_sort()
        >>> dll
        """
        for i in range(self.size()):
            n = self.get_first()
            for j in range(self.size()-i):
                if n.get_next() != self.__trailer:
                    if n > n.get_next():
                        self.swap_forward(n)
                    else:
                        n = n.get_next()

    def selection_sort(self):
        """
        Sort a list using insertion sort
        >>> dll = DoublyLinkedList()
        >>> [ dll.add_first(Node(i)) for i in range(20) ]
        >>> dll.insertion_sort()
        >>> dll
        """
        # Start at the beginning and move through every element
        head = self.__header
        while head != self.get_last():
            min = head.get_next()
            cmp = min
            # Find the minimum value in the rest of the unsorted list
            while cmp != self.__trailer:
                if cmp <= min:
                    min = cmp
                cmp = cmp.get_next()
            # This prevents elements from linking to themselves
            if head.get_next() != min:
                self.swap(head.get_next(), min)
            head = min

    def insertion_sort(self):
        """
        Sort a list using insertion sort
        >>> dll = DoublyLinkedList()
        >>> [ dll.add_first(Node(i)) for i in range(20) ]
        >>> dll.insertion_sort()
        >>> dll
        """
        # Get the first element to compare to others
        cmphead = self.get_first()
        cmp = cmphead.get_next()
        # Move through all elements
        while cmp != self.__trailer:
            # Switch the cmphead if the compared node is bigger
            if cmphead < cmp:
                cmphead = cmp
                cmp = cmphead.get_next()
                continue
            # Move the cmp node to its right place
            prev = cmp.get_previous()
            while prev != self.__header:
                if prev > cmp:
                    prev = prev.get_previous()
                    self.swap_backward(cmp)
                else:
                    break
            cmp = cmphead.get_next()

    def shell_sort(self):
        gap = self.size() // 2 # This should give a good gap size
        while 1 < gap:
            j = 0
            while j - gap < 0: # This prevents running out of elements
                if self[j] > self[j+gap]:
                    k = self[j].get_element()
                    self[j].set_element(self[j+gap].get_element())
                    self[j+gap].set_element(k)
                j += 1
            gap -= 1

        # At this point with a gap size of 1 it is insertion sort
        self.insertion_sort()



    def merge_sort(self):
        """
        Sort a list using merge sort
        >>> dll = DoublyLinkedList()
        >>> [ dll.add_first(Node(i)) for i in range(20) ]
        >>> dll.merge_sort()
        >>> dll
        """
        if self.size() < 2:
            return
        left = DoublyLinkedList()
        right = DoublyLinkedList()
        m = self.size() // 2
        while self.size() > 0:
            if m > 0:
                left.add_last(self.remove(self.get_first()))
            else:
                right.add_last(self.remove(self.get_first()))
            m -= 1

        left.merge_sort()
        right.merge_sort()
        self.merge(left, right)

    def merge(self, left, right):
        while left.size() > 0 or right.size() > 0:
            # Dump the right list if left is empty
            if left.size() <= 0:
                while right.size() > 0:
                    self.add_last(right.remove(right.get_first()))
            # Dump the left list if right is empty
            elif right.size() <= 0:
                while left.size() > 0:
                    self.add_last(left.remove(left.get_first()))
            else:
                # Merge Nodes from each list depending on size
                if left.get_first() < right.get_first():
                    self.add_last(left.remove(left.get_first()))
                else:
                    self.add_last(right.remove(right.get_first()))

    def quick_sort(self, b=None, e=None):
        # I decided to do this one with indexing because it made it easier for
        # me to figure out the base case for the recursion.
        if b == None and e == None:
            b = 0
            e = self.size() - 1

        if e <= b:
            return

        pivot = self[e]
        i = b
        j = i - 1

        while i <= e:
            if self[i] < pivot:
                j += 1
                # This prevents swapping with itself
                if j != i:
                    self.swap(self[j], self[i])
            i += 1

        # Put the pivot in the right place
        j += 1
        if self[j] != pivot:
            # This prevents swapping with itself
            self.swap(self[j], pivot)

        self.quick_sort(b, j - 1)
        self.quick_sort(j + 1, e)


"""**Task 1 (25 points)**: Implement a sequential search and show the implementation works."""

from numpy import random

print("Testing Sequential Search")
dL = DoublyLinkedList()
for i in range(1,21,2):
    dL.add_first(Node(i))
print(dL)

#The code below is broken - make it work
node13 = dL.sequential_search(13)
print(node13)

# This is to show it works
print("One moment please")
import matplotlib.pyplot as plt
from time import time
min, max, offset = 0, 500, 20
times = []
dl = DoublyLinkedList()
[ dl.add_first(Node(i+offset)) for i in range(max) ]
for i in range(min + offset, max + offset):
    t0 = time()
    dl.sequential_search(i)
    times.append(time() - t0)
times.sort()
plt.plot(times)
print("As can be seen from the plot, the sequential search runs in linear time or O(n)")
plt.show()
print("Searching for value not in list")
print(dl.sequential_search(0))



"""**Task 2 (25 points)**: A Faster Search

A **binary search** should return the node which has a value faster than the above sequential search.

Implement a **binary search** and run it on the ***Doubly Linked List*** created.

"""

#Test your implementation here
#The code below is broken - make it work
print("Testing Binary Search")
dL.quick_sort()
node15 = dL.binary_search(15)
print(node15)

# this is to show it works
print("One moment please")
min, max, offset = 0, 500, 20
times = []
dl.quick_sort()
for i in range(min + offset, max + offset):
    t0 = time()
    dl.binary_search(i)
    times.append(time() - t0)
times.sort()
plt.yscale('log')
plt.plot(times)
print("As can be seen from the plot, the binary search runs in roughly logorithmic time or O(log n)")
plt.show()
print("Searching for value not in list")
print(dl.binary_search(0))

"""**Task 4 (50 points)**: Implement the two of the following sorting methods <br>
`Bubble Sort`, `The Selection Sort`, `The Insertion Sort`, `The Shell Sort`,<br>
`The Merge Sort`, or `The Quick Sort`

If you did not like your grade on the previous ** Doubly Linked List** assignment, <br>
I will neglect that grade and count this assignment twice if you successfully implement the `Merge Sort` or `Quick Sort` algorithm(s).
"""

#Test your implementation here
#do a sort here
from random import randint

max = 20
dl = DoublyLinkedList()
[ dl.add_first(Node(i)) for i in range(max)]
print(f"Before Quick Sort: {dl}")
dl.quick_sort()
print(f"After Quick Sort:  {dl}\n")

dl = DoublyLinkedList()
[ dl.add_first(Node(randint(0, max))) for i in range(max) ]
l = dl.size()
print(f"Before Quick Sort: {dl}")
dl.quick_sort()
print(f"After Quick Sort:  {dl}\n")

dl = DoublyLinkedList()
[ dl.add_last(Node(i)) for i in range(max)]
print(f"Before Quick Sort: {dl}")
dl.quick_sort()
print(f"After Quick Sort:  {dl}\n")


dl = DoublyLinkedList()
[ dl.add_first(Node(i)) for i in range(max)]
print(f"Before Merge Sort: {dl}")
dl.merge_sort()
print(f"After Merge Sort:  {dl}\n")

dl = DoublyLinkedList()
[ dl.add_first(Node(randint(0, max))) for i in range(max) ]
l = dl.size()
print(f"Before Merge Sort: {dl}")
dl.merge_sort()
print(f"After Merge Sort:  {dl}\n")

dl = DoublyLinkedList()
[ dl.add_last(Node(i)) for i in range(max)]
print(f"Before Merge Sort: {dl}")
dl.merge_sort()
print(f"After Merge Sort:  {dl}\n")