"""
file: 		myList.py
language: 	python3
author: 	paw@cs.rit.edu	Phil White
description: 	linked list implementation from class notes
"""
######################################################################
# Class definitions
######################################################################

class LinkedList():
    __slots__ = ("head","size")

class Node():
    __slots__ = ("data", "next")

######################################################################
# Class builders
######################################################################

def mkLinkedList():
    """Builder: mkList: () -> LinkedList"""
    lst = LinkedList()
    lst.head = None
    lst.size = 0
    return lst

def mkNode( data, nextNode ):
    """Builder: Node -> Node"""
    node = Node()
    node.data = data
    node.next = nextNode
    return node

######################################################################
# Function definitions
######################################################################

def toString( lst ):
    res="["
    curr=lst.head
    while curr != None:
        res=res + str(curr.data)
        if curr.next!=None:
            res=res+", "
        curr = curr.next
    return res + "]"

def size( lst ):
    return lst.size
"""
def size( lst ):
    return sizeR(lst.head)

def sizeR(curr):
    if curr == None:
        return 0
    else:
        return 1 + sizeR(curr.next)
"""

def get( lst, pos ):
    if pos >= lst.size or pos < 0:
        raise IndexError("*** pos=",pos," invalid since size=", \
                         lst.size," ***")
    curr = lst.head
    for i in range(pos):
        curr = curr.next
    return curr.data

def index( lst, ele ):
    ind = 0
    curr=lst.head
    while curr != None and curr.data != ele:
        ind += 1
        curr = curr.next
    if curr == None:
        return -1
    else:
        return ind

def append( lst, ele ):
    if lst.size == 0:
        lst.head = mkNode(ele,None)
        lst.size +=1
    else:
        lst.size +=1
        curr=lst.head
        while curr.next != None:
            curr = curr.next
        curr.next = mkNode(ele,None)
            
def insert( lst, ele, pos ):
    if pos > lst.size or pos < 0:
        raise IndexError("*** pos=",pos," invalid since size=", \
                         lst.size," ***")
    else:
        nod = mkNode(ele,None)
        lst.size += 1
        if pos == 0:
            nod.next = lst.head
            lst.head = nod
        else:
            curr = lst.head
            for i in range(pos-1):
                curr = curr.next
            nod.next = curr.next
            curr.next = nod

def pop( lst, pos ):
    if pos >= lst.size or pos < 0:
        raise IndexError("*** pos=",pos," invalid since size=", \
                         lst.size," ***")
    elif pos == 0:
        res = lst.head.data
        lst.head = lst.head.next
        lst.size -= 1
    else:
        curr = lst.head
        for i in range(pos-1):
            curr = curr.next
        res = curr.next.data
        curr.next = curr.next.next
        lst.size -= 1
    return res

######################################################################
# Iterator like Function definitions
######################################################################

def getItr( lst ):
    """
    returns a reference to the first node in the list.
    NOTE: if the lst contains no nodes, this returns a reference to None
    """
    return lst.head

def nxt( itr ):
    return itr.next

def hasNxt( itr ):
    return itr.next != None

def isEnd( itr ):
    return itr == None

def getData( itr ):
    return itr.data

def addAfter( itr, lst, ele ):
    """
    adds a new node whose data is 'ele' after the iterator node.
    NOTE: this function can not be used to insert at the front of the list
        (which is equivalent to inserting into an empty list),
        you will need to use 'insert(lst,ele,0)' to do that.
    NOTE 2: the list has to be passed in, since we need to increase
        the size value
    """
    if itr == None:
        raise IndexError("*** invalid iterator loc (itr = None),"\
                         "so can't addAfter ***")
    else:
        nod = mkNode(ele,None)
        lst.size += 1
        nod.next = itr.next
        itr.next = nod

######################################################################
# test function definitions
######################################################################

def initTestLists():
    l1 = mkLinkedList()

    l2 = mkLinkedList()
    append(l2,"p")

    l3 = mkLinkedList()
    append(l3,'a')
    append(l3,'b')
    append(l3,'c')

    return l1,l2,l3

def printTest(l1,l2,l3):
    print("list1: ", toString( l1 ) )
    print("list2: ", toString( l2 ) )
    print("list3: ", toString( l3 ) )
    print("=========================")

def test():
    l1,l2,l3 = initTestLists()
    print("size l1=",size(l1))
    print("size l2=",size(l2))
    print("size l3=",size(l3))
    printTest(l1,l2,l3)
    
    l1,l2,l3 = initTestLists()
    print("get l2 #0",get(l2,0))
    print("get l3 #0",get(l3,0))
    print("get l3 #1",get(l3,1))
    print("get l3 #2",get(l3,2))
    printTest(l1,l2,l3)

    l1,l2,l3 = initTestLists()
    print("index l1 'b'",index(l2,"b"))
    print("index l2 'p'",index(l2,"p"))
    print("index l2 'a'",index(l2,"a"))
    print("index l3 'a'",index(l3,"a"))
    print("index l3 'b'",index(l3,"b"))
    print("index l3 'c'",index(l3,"c"))
    print("index l3 'p'",index(l3,"p"))
    printTest(l1,l2,l3)
    
    l1,l2,l3 = initTestLists()
    append(l1,"Z")
    append(l2,"Z")
    append(l3,"Z")
    printTest(l1,l2,l3)
    
    l1,l2,l3 = initTestLists()
    insert(l1,"Z",0)
    print('insert(l1,"Z",0): l1=',toString(l1))
    insert(l1,"Y",0)
    print('insert(l1,"Y",0): l1=',toString(l1))
    insert(l2,"Z",1)
    print('insert(l2,"Z",1): l1=',toString(l2))
    insert(l3,"P",1)
    print('insert(l3,"Z",1): l1=',toString(l3))
    insert(l3,"Z",4)
    print('insert(l3,"Z",4): l1=',toString(l3))
    printTest(l1,l2,l3)

    l1,l2,l3 = initTestLists()
    print("pop l2 #0",pop(l2,0))
    print("pop l3 #0",pop(l3,0))
    print("pop l3 #0",pop(l3,0))
    print("pop l3 #0",pop(l3,0))
    printTest(l1,l2,l3)

    l1,l2,l3 = initTestLists()
    print("pop l3 #1",pop(l3,1))
    print("pop l3 #1",pop(l3,1))
    print("pop l3 #0",pop(l3,0))
    printTest(l1,l2,l3)

def testExcept():
    l1,l2,l3 = initTestLists()
    try:
        r=get(l3,-1)
        print("get failed bad index -1, returned <",r,">")
    except IndexError:
        print("'get' passed bad -1 index test")
    try:
        r=get(l3,6)
        print("get failed bad index 6, returned <",r,">")
    except IndexError:
        print("'get' passed bad >size index test")
    try:
        insert(l1,"Bad",-1)
        print("insert failed bad index -1, list=",toString(l1))
    except IndexError:
        print("'insert' passed bad -1 index test")
    try:
        insert(l2,"Bad",6)
        print("insert failed bad index 6, list=",toString(l2))
    except IndexError:
        print("'insert' passed bad >size index test")
    try:
        r=pop(l2,-1)
        print("get failed bad index -1, returned <",r,">")
    except IndexError:
        print("'pop' passed bad -1 index test")
    try:
        r=pop(l3,6)
        print("get failed bad index 6, returned <",r,">")
    except IndexError:
        print("'pop' passed bad >size index test")
    printTest(l1,l2,l3)

def testIter(lst):
    it = getItr(lst)
    if isEnd(it):
        insert(lst,"WAS EMPTY",0)
        it = getItr(lst)    #list changed with insert, so get new iter
    else:
        addAfter(it,lst, "WAS NON-EMPTY")
    addAfter(it,lst,"CC")       # note: iter doesn't move with this
    addAfter(it,lst,"BB")
    addAfter(it,lst,"AA")
    
    it = getItr(lst)
    while not hasNxt(it):
        nxt(it)
    addAfter(it,lst,"ZZ")
    
    it = getItr(lst)
    print("<",end="")
    while not isEnd(it):
        print(str(getData(it)),end="")
        if hasNxt(it):
            print(", ",end="")
        it = nxt(it)
    print(">")
    
def testIterAll():
    l1,l2,l3 = initTestLists()
    testIter(l1)
    testIter(l2)
    testIter(l3)
    printTest(l1,l2,l3)
    

"""
n2=mkNode(42,None)
n1=mkNode(0,n2)
n0=mkNode(25,n1)

head=mkNode(25,mkNode(0,mkNode(42,None)))
lst1=mkLinkedList()
lst1.head=head
lst1.size=3
print(toString(lst1))
print(size(lst1))
print(get(lst1,2))
print(get(lst1,1))
print(get(lst1,0))
print(index(lst1,42))
print(index(lst1,444))
append(lst1,99)
print(toString(lst1))
test()

"""
if __name__ == "__main__":
    test()
    testExcept()
    testIterAll()