CS 345 Homework 8

# hw8 solution cs345 sp2017
import unittest


class EmptyQueue(Exception):
    """Custom Exception"""
    def __init__(self, value):
        self.value = value
    def __str__(self):
        return repr(self.value)
        
class CircularQueue:
    """Queue implementation using circularly linked list for storage."""

    #---------------------------------------------------------------------------
    # nested _Node class
    class _Node:
        """Lightweight, nonpublic class for storing a singly linked node."""
        __slots__ = '_element', '_next'         # streamline memory usage

        def __init__(self, element, next):
          self._element = element
          self._next = next

    # end of _Node class
    #--------------------------------------------------------------------------

    def __init__(self):
        """Create an empty queue."""
        self._tail = None                     # will represent tail of queue
        self._size = 0                        # number of queue elements

    def __len__(self):
        """Return the number of elements in the queue."""
        return self._size

    def is_empty(self):
        """Return True if the queue is empty."""
        return self._size == 0

    def first(self):
        """Return (but do not remove) the element at the front of the queue.

        Raise EmptyQueue exception if the queue is empty.
        """
        if self.is_empty():
          raise EmptyQueue('Queue is empty')
        head = self._tail._next
        return head._element

    def dequeue(self):
        """Remove and return the first element of the queue (i.e., FIFO).

        Raise EmptyQueue exception if the queue is empty.
        """
        if self.is_empty():
          raise EmptyQueue('Queue is empty')
        oldhead = self._tail._next
        if self._size == 1:                   # removing only element
          self._tail = None                   # queue becomes empty
        else:
          self._tail._next = oldhead._next    # bypass the old head
        self._size -= 1
        return oldhead._element

    def enqueue(self, e):
        """Add an element to the back of queue."""
        newest = self._Node(e, None)          # node will be new tail node
        if self.is_empty():
          newest._next = newest               # initialize circularly
        else:
          newest._next = self._tail._next     # new node points to head
          self._tail._next = newest           # old tail points to new node
        self._tail = newest                   # new node becomes the tail
        self._size += 1

    def rotate(self):
        """Rotate front element to the back of the queue."""
        if self._size > 0:
          self._tail = self._tail._next       # old head becomes new tail

    def find(self, query):
        """
        takes one argument, query. Method should return true if query exists in the queue and false otherwise. Method should return immediately if query is found. Queue should remain unmodified.
        """
        curr_node  = self._tail
        while curr_node:
            if query == curr_node._element:
                return True
            elif curr_node._next != self._tail:
                curr_node = curr_node._next
            else:
                curr_node = None
        return False

    def dequeue_end(self):
        """
        takes no arguments. Method should remove the tail node from the list while maintaining circularity. O(n)
        """
        if not self._tail:
            raise EmptyQueue('Queue is empty.')
        
        curr_node = self._tail
        while curr_node._next != self._tail:
            curr_node = curr_node._next
        
        val = self._tail._element      
        curr_node._next = self._tail._next
        self._tail = curr_node
        self._size -= 1
        return val

    def enqueue_cutter(self, e):
        """
        takes one argument, the element to enqueue at the front. Method should add new element to the front of the list while maintaining circularity.
        O(1)
        """
        newest = self._Node(e, None)
        if not self._tail:
            self._tail = newest
        else:       
            newest._next = self._tail._next
        
        self._tail._next = newest
        self._size += 1

    def extend_queue(self, queue):
        """
         takes one argument, queue. Note: queue should be an instance of CircularQueue. Method should concatenate queue to the linked list. This grows the queue by the size of queue. This method MUST be implemented with O(1) (constant time) efficiency.
        """
        curr_head = self._tail._next
        self._tail._next = queue._tail._next
        self._tail = queue._tail
        self._tail._next = curr_head
        self._size += queue._size

    def rotate_rev(self):
        """
        takes no arguments. The method should rotate the linked list in reverse (rotate right): tail becomes head. O(n)
        """
        if not self._tail:
            raise EmptyQueue('Queue is empty.')
        
        curr_node = self._tail
        while curr_node._next != self._tail:
            curr_node = curr_node._next        

        self._tail = curr_node

    def rotate_n(self, n):
        """ 
        takes one argument, n, a postive integer. The method should rotate the linked list left, n times.
        """
        for i in range(n):
            self.rotate()

    def as_string(self, node=None):  # Using optional parameters
        """
        takes one argument, node of type Node. Method should return a string containing the contents of the circular queue. The string should begin with the head and end with the tail. Each element must be printed with a space between. Must be implemented with recursion.
        """
        if not self._tail:
            raise EmptyQueue('Queue is empty.')

        if not node:  # initial call: initialize node to head.
            node = self._tail._next 

        if node == self._tail:  # base case: we're at the tail.
            return str(node._element)              
        
        # tail recursion: printing in order of recursive calls
        return str(node._element) + ' ' + self.as_string(node._next)


class TestCircularQueueMethods(unittest.TestCase):
    """define your unit tests here."""
    
    def test_find(self):
        cirque = CircularQueue()
        cirque.enqueue('red')
        cirque.enqueue('blue')
        cirque.enqueue('green')
        self.assertEqual(cirque.find('blue'), True)
        self.assertEqual(cirque.find('purple'), False)

    def test_dequeue_end(self):
        cirque = CircularQueue()

        # test empty list exception
        with self.assertRaises(EmptyQueue):
            cirque.dequeue_end()

        cirque.enqueue('red')
        cirque.enqueue('blue')
        cirque.enqueue('green')    

        self.assertEqual(cirque.dequeue_end(), 'green')
        self.assertEqual(cirque.dequeue_end(), 'blue')   

    def test_enqueue_cutter(self):
        cirque = CircularQueue()
        
        #  test cutter into empty queue
        cirque.enqueue_cutter('orange')

        #  test cutter after enqueue operations
        cirque.enqueue('red')
        cirque.enqueue('blue')
        cirque.enqueue('green')        
        cirque.enqueue_cutter('purple')
        self.assertEqual(cirque.first(), 'purple')
        self.assertEqual(cirque.as_string(), 'purple orange red blue green')

    def test_extend_queue(self):
        cirque = CircularQueue()
        cirque.enqueue('red')
        cirque.enqueue('blue')
        cirque.enqueue('green')

        cirque2 = CircularQueue()       
        cirque2.enqueue('purple')
        cirque2.enqueue('orange')
        cirque2.enqueue('yellow')

        cirque.extend_queue(cirque2)
        self.assertEqual(cirque.first(), 'red')
        self.assertEqual(cirque.dequeue_end(), 'yellow')
        self.assertEqual(cirque._size, 5)

    def test_rotate_rev(self):
        cirque = CircularQueue()

        # test empty list exception
        with self.assertRaises(EmptyQueue):
            cirque.as_string()

        cirque.enqueue('red')
        cirque.enqueue('blue')
        cirque.enqueue('green')
        cirque.rotate_rev()
        self.assertEqual(cirque.first(), 'green')
        self.assertEqual(cirque._tail._element, 'blue')

    def test_rotate_n(self):
        cirque = CircularQueue()   

        cirque.enqueue('red')
        cirque.enqueue('blue')
        cirque.enqueue('green')
        cirque.rotate_n(4)
        self.assertEqual(cirque.first(), 'blue')
        self.assertEqual(cirque._tail._element, 'red')

    def test_as_string(self):
        cirque = CircularQueue()

        # test empty list exception
        with self.assertRaises(EmptyQueue):
            cirque.as_string()

        # test correct print order
        cirque.enqueue('red')
        cirque.enqueue('blue')
        cirque.enqueue('green')
        self.assertEqual(cirque.as_string(), 'red blue green')


"""Run the unit tests on invocation of this file with python interpreter.

> python <name of this file>.py
"""
if __name__ == '__main__':
    unittest.main()