"""This module defines the LinkedList class, which is a (limited)
implementation of the List ADT using a linked list data structure."""

from node import Node

class LinkedList(object):

    """Implementation of the List ADT using a linked list."""
    
    def __init__(self):
        """Create an empty linked list."""
        self._head = None
        self._size = 0
        
    def search(self, target):
        """Search the list to see if it contains a node with data value of
        target.  Return True if found, False if not."""
        current = self._head
        while current is not None:
            if current.data == target:
                return True
            else:
                current = current.next
        return False
        
    def insert(self, i, value):
        """Insert value into the list so that it appears in position i.  Raise
        an IndexError exception if i is not a valid position to insert at."""
        if i > self._size or i < 0:
            raise IndexError("Cannot insert into position " + str(i))
        if i == 0:
            # Insert into the beginning of the list.
            new_node = Node(value)
            new_node.next = self._head
            self._head = new_node
            self._size = self._size + 1
        else:
            # Find node i-1
            index = 0
            current = self._head
            while index < i - 1:
                current = current.next
                index = index + 1
            # Insert after node i-1
            new_node = Node(value)
            new_node.next = current.next
            current.next = new_node
            self._size = self._size + 1
            
    def remove(self, i):
        """Remove node at position i.  Raise an IndexError exception if there
        is no node at position i."""
        if i >= self._size or i < 0:
            raise IndexError("There is no node at position " + str(i))
        if i == 0:
            # Remove the node at the start of the list.
            self._head = self._head.next
            self._size = self._size - 1
        else:
            # Find node i-1
            index = 0
            current = self._head
            while index < i - 1:
                current = current.next
                index = index + 1
            # Remove node after i-1
            current.next = current.next.next
            self._size = self._size - 1
            
    def __str__(self):
        """Return a string representation of the list."""
        contents = []
        current = self._head
        while current is not None:
            contents.append(current.data)
            current = current.next
        return str(contents)
        
if __name__ == "__main__":
    llist = LinkedList()
    for i in range(5):
        llist.insert(i, 3*i)
    print llist
    llist.remove(3)
    print llist
    llist.insert(0, 45)
    print llist
    llist.insert(5,100)
    print llist
    llist.remove(5)
    print llist
    print llist.search(5)
    print llist.search(45)
    print llist.search(3)