"""Definition and implementation of SortedList, a class which uses a linked
list to maintain a sorted list of elements."""

from node import Node

class SortedList(object):
    
    """Implementation of a sorted list, internally using a linked list."""
    
    def __init__(self):
        """Create an empty linked list."""
        self._head = None
        
    def insert(self, value):
        """Insert value to the end of the list.  Modify this so value inserted
        into a position such that the list remains sorted."""
        if self._head is None:
            # Insert into the front of the list.
            self._head = Node(value)
        else:
            # Move to the last element.
            current = self._head
            while current.next is not None:
                current = current.next
            current.next = Node(value)
            
    def remove(self, value):
        """Remove the first occurence of value from the list.  Modify this so
        that it removes all occurrences of value."""
        if (self._head is not None) and (self._head.data == value):
            # Remove the first element.
            self._head = self._head.next
        else:
            # Find the first occurrance of value.
            current = self._head
            while (current is not None) and (current.next.data != value):
                current = current.next
            # If we did not hit the end of the list, remove current.next.
            if current is not None:
                current.next = current.next.next
    
    def __str__(self):
        """Return a string representation of the sorted list."""
        elements = []
        current = self._head
        while current is not None:
            elements.append(current.data)
            current = current.next
        return str(elements)