#!/usr/bin/env python3
"""
atds.py
Advanced Topics Data Structures (atds) is a collection of classes for use in
the Advanced Topics in Computer Science class at Polytechnic School.
@author Richard White
@version 2017-03-13
"""

import sys

class Stack():
    """
    Uses lists to implement a stack class.
    """
    def __init__(self):
        self.stack = []
    
    def push(self, item):
        self.stack.append(item)

    def pop(self):
        return self.stack.pop()

    def peek(self):
        return self.stack[-1]

    def size(self):
        return len(self.stack)

    def isEmpty(self):
        return len(self.stack) == 0

    def __repr__(self):
        result = "Stack["
        for i in range(len(self.stack)):
            if (i == 0): result = result + str(self.stack[i])
            else: result = result + "," + str(self.stack[i])
        result += "]"
        return result


class Queue:
    """The Queue Abstract Data Type
    * Instatiation creates empy queue, and returns that queue.
    * enqueue(item) adds a new item to rear of queue, returns nothing
    * dequeue() removes the front item from the queue, returns the item
    * is_empty() returns True if queue is empty.
    * size() returns the number of items in the queue
    Assume index 0 is the rear of the list.
    """

    def __init__(self):
        self.q = []

    def enqueue(self, item):
        self.q.insert(0, item)

    def dequeue(self):
        item = self.q.pop()
        return item

    def isEmpty(self):
        return len(self.q) == 0

    def size(self):
        return len(self.q)

    def __repr__(self):
        result = "Queue["
        for i in range(len(self.q)):
            if (i == 0): result = result + str(self.q[i])
            else: result = result + "," + str(self.q[i])
        result += "]"
        return result


class Deque():
    """This class implements a double-ended
    queue. Consider the left side of the list
    to be the "front."
    """

    def __init__(self):
        self.deq = []

    def addFront(self, value):
        self.deq.insert(0, value)

    def removeFront(self):
        return self.deq.pop(0)

    def addRear(self, value):
        self.deq.append(value)

    def removeRear(self):
        return self.deq.pop()

    def size(self):
        return len(self.deq)
    
    def isEmpty(self):
        return len(self.deq) == 0
    
    def __repr__(self):
        result = "Deque["
        for i in range(len(self.deq)):
            if i == 0: result += str(self.deq[i])
            else:
                result += "," + str(self.deq[i])
        result += "]"
        return result

class Node:
    """A Node object is used to create a linked list, and is 
    characterized by a value (data), and a pointer (next) that 
    may be set to point to the next Node object in the 
    linked list.
    """

    def __init__(self, data):
        """Creates a node with a given value, and a next pointer
        initialized to None.
        """
        self.data = data
        self.next = None

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def setNext(self, newNext):
        self.next = newNext
    
    def setData(self, newData):
        self.data = newData


class UnorderedList():
    """An Unordered List object refers to the first Node in a linked
    list, call the "head." If the list has not been created yet, the 
    value of head is None.
    """

    def __init__(self):
        self.head = None

    def isEmpty(self):
        return self.head == None

    def add(self, item):
        """creates a new Node and adds it to the list"""
        newNode = Node(item)
        newNode.setNext(self.head)  # newNode points to old head
        self.head = newNode

    def length(self):
        """Traverses through the list to identify the total number
        of nodes in the list. This traversal strategy is used by 
        a number of the methods in this class.
        """
        nodeCount = 0
        nextNode = self.head
        while nextNode != None:
            nodeCount += 1
            nextNode = nextNode.getNext()
        return nodeCount

    def search(self, item):
        """Returns True if the item exists in the list."""
        nextNode = self.head
        while nextNode != None:
            if nextNode.getData() == item:
                return True
            nextNode = nextNode.getNext()
        return False

    def __repr__(self):
        """Creates a representation of the list suitable for printing,
        debugging.
        """
        returnValue = "UnorderedList["
        nextNode = self.head
        while nextNode != None:
            returnValue += str(nextNode.getData()) + ","
            nextNode = nextNode.getNext()
        if returnValue[-1] == ",":
            returnValue = returnValue[:-1] # remove trailing comma
        returnValue = returnValue + "]"
        return returnValue
            
    def remove(self,item):
        """This tricky method uses a pair of variables to monitor
        the traversal so that we can remove the desired item from the
        list by taking the pointer from the previous Node and setting
        it to the item AFTER the one that we're removing.

        In this version of the UnorderedList, remove works on 
        multiple values.
        """
        previous = None
        current = self.head
        while current != None:
            if current.getData() == item:
                if previous == None:
                    self.head = current.getNext()
                else:
                    previous.setNext(current.getNext())
                current = current.getNext()
            else:
                previous = current
                current = current.getNext()

    ############ ADDITIONAL UnsortedList METHODS ################

    def append(self, item):
        """Adds an item to the end of the list."""
        previous = None
        current = self.head
        while current != None:
            previous = current
            current = current.getNext()
        if previous == None:  # if we're in empty list
            self.head = Node(item)
        else:
            previous.setNext(Node(item))

    def insert(self, item, index):
        """Inserts a new Node into the UnsortedList at the specified
        index, where 0 is the head of the list. Assumes that the 
        index exists in the list.
        """
        position = 0
        previous = None
        current = self.head
        while position < index:
            previous = current
            current = current.getNext()
            position += 1
        newNode = Node(item)
        newNode.setNext(current)
        if previous != None:
            previous.setNext(newNode)
        else:
            self.head = newNode

    def index(self, item):
        """Returns the index value (position) of the item in the
        list. First element is numbered 0, second element is 1, etc.
        Assumes that the item exists in the list.
        """
        position = 0
        current = self.head
        while current != None:
            if current.getData() == item:
                return position
            else:
                current = current.getNext()
                position += 1
        return position

    def pop(self, index=0):
        """Pops the given item from the list and returns it, using
        strategies developed in methods above. Assumes that the index
        exists in the list.
        If no index is specified, pop takes off the first element in
        the list, (the zeroth element), assuming that an element is there.
        """
        position = 0
        previous = None
        current = self.head
        while position < index:
            previous = current
            current = current.getNext()
            position += 1
        # We're at the correct position. Pop the item and reset pointers
        item = current.getData()
        if previous == None:        # We're at first position 
            self.head = current.getNext()
        else:                       # bypass the current Node
            previous.setNext(current.getNext())
        return item


class OrderedList:
    """An Ordered List object refers to the first Node in a linked
    list, call the "head." If the list has not been created yet, the 
    value of head is None.
    """

    def __init__(self):
        self.head = None

    def isEmpty(self):
        return self.head == None

    def add(self, item):
        """creates a new Node and adds it to the list
        in the correct location, which requires traversing the list
        """
        newNode = Node(item)
        previous = None
        current = self.head
        while current != None and item > current.getData():
            previous = current
            current = current.getNext()
        if self.head == None:
            self.head = newNode
        else:
            previous.setNext(newNode)
            newNode.setNext(current)


    def length(self):
        """Traverses through the list to identify the total number
        of nodes in the list. This traversal strategy is used by 
        a number of the methods in this class.
        """
        nodeCount = 0
        nextNode = self.head
        while nextNode != None:
            nodeCount += 1
            nextNode = nextNode.getNext()
        return nodeCount

    def search(self, item):
        """Returns True if the item exists in the list."""
        nextNode = self.head
        while nextNode != None:
            if nextNode.getData() == item:
                return True
            nextNode = nextNode.getNext()
        return False

    def __repr__(self):
        """Creates a representation of the list suitable for printing,
        debugging.
        """
        returnValue = "OrderedList["
        nextNode = self.head
        while nextNode != None:
            returnValue += str(nextNode.getData()) + ","
            nextNode = nextNode.getNext()
        if returnValue[-1] == ",":
            returnValue = returnValue[:-1] # remove trailing comma
        returnValue = returnValue + "]"
        return returnValue
            
    def remove(self,item):
        """This tricky method uses a pair of variables to monitor
        the traversal so that we can remove the desired item from the
        list by taking the pointer from the previous Node and setting
        it to the item AFTER the one that we're removing.

        In this version, the remove method works on 
        multiple values.
        """
        previous = None
        current = self.head
        while current != None:
            if current.getData() == item:
                if previous == None:
                    self.head = current.getNext()
                else:
                    previous.setNext(current.getNext())
                current = current.getNext()
            else:
                previous = current
                current = current.getNext()


class UnorderedListStack():
    """Implements a stack using our unordered
    list class.
    """
    def __init__(self):
        """Creates a Stack implemented using the
        UnorderedList class (part of this atds.py
        module).
        """
        self.uls = UnorderedList()

    def push(self, data):
        """Uses the UnorderedList add method to 
        push onto the stack.
        """
        self.uls.add(data)

    def pop(self):
        """Pops from the top of the stack only!
        """
        return self.uls.pop()

    def size(self):
        return self.uls.length()

    def isEmpty(self):
        return self.uls.isEmpty()

    def __repr__(self):
        return self.uls.__repr__()

class HashTable():
    """Describes a hash table that will track key-value
    pairs using a pair of parallel lists.
    """

    def __init__(self, m):
        """Creates a hash table of the size m
        """
        self.size = m                       # use a prime number!
        self.slots = [None] * self.size     # a list of None keys
        self.data = [None] * self.size      # a list of None values
    
    def put(self, key, value):
        """Places a key-value pair in the hash table, or replaces
        the current value if the key already exists in the table.
        """
        hashvalue = self.hashfunction(key, self.size)
        if self.slots[hashvalue] == None:
            self.slots[hashvalue] = key
            self.data[hashvalue] = value
        elif self.slots[hashvalue] == key:      # Check replacing value
            self.data[hashvalue] = value    
        else:           # We're occupied. Time to start linear probe!
            nextslot = (hashvalue + 1) % self.size      # get the nextslot based 
            while self.slots[nextslot] != None and \
                  self.slots[nextslot] != key:
                nextslot = (nextslot + 1) % self.size
            # We stopped. Are we replacing value or entering new value?
            if self.slots[nextslot] == key:
                self.data[nextslot] = value
            else:
                self.slots[nextslot] = key
                self.data[nextslot] = value
            
    def get(self, key):
        """Tries to find a key-value pair in the hash table, or returns
        None if no key is found.
        """
        hashvalue = self.hashfunction(key, self.size)
        if self.slots[hashvalue] == None:
            return None
        elif self.slots[hashvalue] == key:  
            return self.data[hashvalue]  
        else:           # We're occupied. Time to start linear probe!
            nextslot = (hashvalue + 1) % self.size      # get the nextslot based 
            while self.slots[nextslot] != None and \
                  self.slots[nextslot] != key:
                nextslot = (nextslot + 1) % self.size
            # We stopped. Are we replacing value or entering new value?
            if self.slots[nextslot] == key:
                return self.data[nextslot]
            else:
                return None

    def hashfunction(self, key, size):
        """Return the value of the hash function, based on the key
        and the size of the table.
        """
        return key % size
        
    def __repr__(self):
        return "Keys:   " + str(self.slots) + "\n" + "Values: " + str(self.data)

class Graph:
    def __init__(self):
        self.vertices = {}
        self.numVertices = 0
        
    def addVertex(self,key):
        self.numVertices = self.numVertices + 1
        newVertex = Vertex(key)
        self.vertices[key] = newVertex
        return newVertex
    
    def getVertex(self,n):
        if n in self.vertices:
            return self.vertices[n]
        else:
            return None

    def __contains__(self,n):
        return n in self.vertices
    
    def addEdge(self,f,t,cost=0):
            if f not in self.vertices:
                nv = self.addVertex(f)
            if t not in self.vertices:
                nv = self.addVertex(t)
            self.vertices[f].addNeighbor(self.vertices[t],cost)
    
    def getVertices(self):
        return list(self.vertices.keys())
        
    def __iter__(self):
        return iter(self.vertices.values())
                

class Vertex:
    def __init__(self,num):
        self.id = num
        self.connectedTo = {}
        self.color = 'white'
        self.dist = sys.maxsize
        self.pred = None
        self.disc = 0
        self.fin = 0

    # def __lt__(self,o):
    #     return self.id < o.id
    
    def addNeighbor(self,nbr,weight=0):
        self.connectedTo[nbr] = weight
        
    def setColor(self,color):
        self.color = color
        
    def setDistance(self,d):
        self.dist = d

    def setPred(self,p):
        self.pred = p

    def setDiscovery(self,dtime):
        self.disc = dtime
        
    def setFinish(self,ftime):
        self.fin = ftime
        
    def getFinish(self):
        return self.fin
        
    def getDiscovery(self):
        return self.disc
        
    def getPred(self):
        return self.pred
        
    def getDistance(self):
        return self.dist
        
    def getColor(self):
        return self.color
    
    def getConnections(self):
        return self.connectedTo.keys()
        
    def getWeight(self,nbr):
        return self.connectedTo[nbr]
                
    def __str__(self):
        return str(self.id) + ":color " + self.color + ":disc " + str(self.disc) + ":fin " + str(self.fin) + ":dist " + str(self.dist) + ":pred \n\t[" + str(self.pred)+ "]\n"
    
    def getId(self):
        return self.id