gistfile1.pytb

# linked_list.py
# A simple link-based list example
"""
linked_list - An link-based list implementation for Python.

Emulates an link-based list implementation via an internal collection of
linked-list nodes. Behaves like a normal Python list via operator overloading.
"""
import copy

####################### 
# Class representing links in the list

class Link:
    """A link which linked lists are made of.
    
    Usage:
    >>> from linked_list import Link
    >>> link1 = Link(1)
    >>> link1.data == 1
    True
    >>> link1.next is None
    True
    >>> link2 = Link(2, link1)
    >>> link2.data == 2
    True
    >>> link2.next.data == 1
    True
    >>> link2.next.next is None
    True
    """
    
    def __init__(self, data, next = None):
        """Create a new link. Initially not linked.
        
        Usage:
        >>> from linked_list import Link
        >>> link1 = Link(1)
        >>> link1.data == 1
        True
        >>> link1.next is None
        True
        >>> link2 = Link(2, link1)
        >>> link2.data == 2
        True
        >>> link2.next == link1
        True
        >>> link1.next is None
        True
        """
        # Data is a property. No need to wrap it as get/set safe
        self.data = data
        # Next we have to protect as update requires linking properly 
        self._next = next
    
    @property
    def next(self):
        """link.next -> Returns the next link.
        
        May be None if there is no following link.
        
        Usage
        >>> from linked_list import Link
        >>> link1 = Link(1)
        >>> link1.next is None
        True
        >>> link2 = Link(2, link1)
        >>> link2.next == link1
        True
        """
        return self._next    
        
    @next.setter
    def next(self, link):
        """link.next = link -> Update the link.
        
        Change where we point.
        
        Usage
        >>> from linked_list import Link
        >>> link1 = Link(1)
        >>> link2 = Link(2)
        >>> link2.next = link1
        >>> link2.next == link1
        True
        >>> link2.next = None
        >>> link2.next is None
        True
        """
        # Make sure we have the correct type (has a link or is None)
        if link is not None and not hasattr(link, "next"):
            raise TypeError("Invalid link.")
        self._next = link

####################### 
# Class representing the actual list

class LinkedList:
    """Emulates an linked-based list implementation via a collection of Link
    instances. Behaves like a normal Python list via operator 
    overloading.
    """

    def __init__(self, sequence = ()):
        """LinkedList([seq]) -> create an empty LinkedList
        
        The LinkedList is empty by default; if provided a sequence, it will
        copy the elements from the sequence.
        
        Usage:
        >>> from linked_list import LinkedList
        >>> a = LinkedList()
        >>> len(a) == 0
        True
        >>> a.head is None
        True
        >>> a.tail is None
        True
        >>> a = LinkedList([1,2,3])
        >>> len(a) == 3
        True
        >>> a.head.data == 1
        True
        >>> a[1] == 2
        True
        >>> a.tail.data == 3
        True
        """
        # We need a link to the head and tail, both initially None. The
        # size is also zero
        self._head = None
        self._tail = None
        self._size = 0
        
        # If we have any items, add them
        for item in sequence:
            self.append(item)

    @property
    def head(self):
        """linkedList.head -> The Link instance at the start of the list.
        
        Usage
        >>> from linked_list import LinkedList
        >>> a = LinkedList()
        >>> a.head is None
        True
        >>> a.append(1)
        >>> a.head.data == 1
        True
        """
        # We make a deep copy so our internal list can be modified.
        return self._head
        
    @property
    def tail(self):
        """linkedList.tail -> The Link instance at the end of the list.
        
        Usage
        >>> from linked_list import LinkedList
        >>> a = LinkedList()
        >>> a.tail is None
        True
        >>> a.append(1)
        >>> a.tail.data == 1
        True
        >>> a.append(2)
        >>> a.tail.data == 2
        True
        """
        return self._tail
        
    def __len__(self):
        """len(linkedList) -> length of the linked list.
        
        Returns the number of items in stored in the array.

        Usage
        >>> from linked_list import LinkedList
        >>> a = LinkedList()
        >>> len(a) == 0  # List initially empty
        True
        >>> a.append(1)
        >>> a.append(2)
        >>> a.append(3)
        >>> len(a) == 3
        True
        """
        return self._size
        
    def __str__(self):
        """str(linkedList) -> create a string representation of the list.

        Usage
        >>> from linked_list import LinkedList
        >>> a = LinkedList()
        >>> a.append(1)
        >>> a.append(2)
        >>> a.append(3)
        >>> str(a)
        '[1, 2, 3]'
        """
        # Create a list of strings from array
        strings = []
        for item in self:
            strings.append(str(item))
        return "[" + ", ".join(strings) + "]"
        
    def __getitem__(self, index):
        """linkedList[index] -> returns item stored at given index.
        
        Looks up in the iterates over the linked lest until the given index
        is found and returns the items. 
        
        Negative indices and slicing are not supported; an exception is thrown. 
        An exception is also thrown if the index is beyond the last link.
        
        Usage:
        >>> from linked_list import LinkedList
        >>> a = LinkedList()
        >>> a.append(1)
        >>> a.append(2)
        >>> a.append(3)
        >>> a[0] == 1
        True
        >>> a[2] == 3
        True
        """
        # Only positive indices supported
        if index < 0:
            raise IndexError("Negative indices not supported")
            
        if index >= len(self):
            raise IndexError("Index pass boundary")
        
        if index == 0:
            # Quick to get first
            return self.head.data
        elif index == len(self) - 1:
            # Quick to get last
            return self.tail.data
        else:
            # SLower to get rest; have to walk through
            # Enumerate implicitly uses __iter__
            for i, item in enumerate(self):
                if i == index:
                    return item
        
    def __setitem__(self, index, value):
        """linkedList[index] = value -> updates item stored at given index.
        
        Stores value in the list. If index is invalid, IndexError is raised.
        Negative indices are slices not supported (can implement for extra
        credit).
        
        Usage:
        >>> from linked_list import LinkedList
        >>> a = LinkedList()
        >>> a.append(1)
        >>> a[0] = 2
        >>> a[0] == 2
        True
        """
        # Only positive indices supported
        if index < 0:
            raise IndexError("Negative indices not supported")
            
        if index >= len(self):
            raise IndexError("Index pass boundary")
        
        if index == 0:
            # Quick to update first
            self.head.data = value
        elif index == len(self) - 1:
            # Quick to update last
            self.tail.data = value
        else:
            # Slow to update middle
            # We can't use __iter__, as that gives us the values, not the link.
            # So we walk manually via the iterlinks.
            for i, link in enumerate(self.iterlinks()):
                if i == index:
                    link.data = value
                    break
        
    def append(self, item):
        """linkedList.append(item) -> add item to end of the linked list.
        
        Adds a new item at the end. 
        
        Usage
        >>> from linked_list import LinkedList
        >>> a = LinkedList()
        >>> a.append(1)
        >>> a.append(2)
        >>> a.append(3)
        >>> a[0] == 1 and a[1] == 2 and a[2] == 3
        True
        >>> len(a) == 3
        True
        """
        # Just call insert
        self.insert(len(self), item)

    def __delitem__(self, index):
        """del linkedList[index] -> Removes value at index.
        
        Removes value in the array. If index is invalid, IndexError is raised.
        Negative indices are slices not supported (can implement for extra
        credit).
        
        Usage:
        >>> from linked_list import LinkedList
        >>> a = LinkedList()
        >>> a.append(1)
        >>> a.append(2)
        >>> a.append(3)
        >>> a.append(4)
        >>> len(a) == 4
        True
        >>> del a[1]  # Test deletion in middle
        >>> len(a) == 3
        True
        >>> a[1] == 3
        True
        >>> del a[2] # Test deletion at end
        >>> len(a) == 2
        True
        >>> a.tail == a.head.next
        True
        >>> newHead = a.head.next
        >>> del a[0] # Test deletion at front
        >>> len(a) == 1
        True
        >>> a.head == newHead
        True
        """
        # Only positive indices supported
        if index < 0:
            raise IndexError("Negative indices not supported")
            
        if index >= len(self):
            raise IndexError("Index pass boundary")
            
        if index == 0:
            # Quick to remove head
            # Make new head the node after the current head
            self._head = self._head.next
            
            # See if we are deleting at end
            if self._size == 1:
                self._tail = self._head
        else:
            # Slow to remove anywhere else
            # Walk the list to the position before the deletion then update:
            # - Node before deletion now points to one after
            for i, link in enumerate(self.iterlinks()):
                if i == index - 1:
                    link.next = link.next.next
                    
                    # See if we are deleting at the end
                    if index == self._size - 1:
                        self._tail = link
            
        # Reduce list length by one
        self._size -= 1

    def pop(self, index=-1):
        """linkedList.pop([index]) -> Removes and returns value at index.
        
        index is the last value by default.
        
        Usage:
        >>> from linked_list import LinkedList
        >>> a = LinkedList()
        >>> a.append(1)
        >>> a.append(2)
        >>> a.pop(0) == 1
        True
        >>> a.pop() == 2
        True
        """
        if index == -1:
            index = len(self) - 1
        # Only positive indices supported
        if index < 0:
            raise IndexError("Negative indices not supported")
            
        if index >= len(self):
            raise IndexError("Index pass boundary")

        value = self[index]
        del self[index]
        return value

    def __iter__(self):
        for link in self.iterlinks():
            yield link.data
            
    def iterlinks(self):
        current = self.head
        while current is not None:
            yield current
            current = current.next
        
    def insert(self, index, item):
        """linkedList.insert(index, item) -> add item internally.
        
        Adds a new item at index. An IndexException should be thrown in 
        an invalid index is passed.

        This implementation does not support negative indices or slices.
        
        Usage
        >>> from linked_list import LinkedList
        >>> a = LinkedList()
        >>> len(a) == 0
        True
        >>> a.head == a.tail and a.head is None
        True
        >>> a.insert(0, 1)
        >>> a[0] == 1
        True
        >>> a.head == a.tail and a.head is not None
        True
        >>> len(a) == 1
        True
        >>> a.insert(0, 2)
        >>> a.head != a.tail
        True
        >>> a[0] == 2 and a[1] == 1
        True
        >>> len(a) == 2
        True
        >>> a.insert(1, 3)
        >>> a[0] == 2 and a[1] == 3 and a[2] == 1
        True
        >>> len(a) == 3
        True
        >>> a.insert(3, 4)
        >>> a[0] == 2 and a[1] == 3 and a[2] == 1 and a[3] == 4
        True
        >>> len(a) == 4
        True
        """
        if index < 0 or index > self._size:
            raise IndexError("Error out of bounds: %s" % index)
        
        if index == 0:
            # Adding at beginning is fast
            #  - Create new link
            #  - Make new link point to previous head
            #  - Made head point to new link
            # TODO: Students implement this
            newLink = Link(item, self.head)
            self._head = newLink
            
            # Check to see if this is the first item
            if self._tail is None:
                self._tail = self._head
            
        elif index == self._size:
            # Adding at end is also fast
            # - Create new link
            # - Make tail point new new link
            # - Make new link the tail
            newLink = Link(item)
            self._tail.next = newLink
            self._tail = newLink
            
        else:
            # Adding elsewhere requires us to walk the list
            # - Walk list until we find the spot *before* the insertion
            # - Make the new link
            # - Make new link point to the spot at the insertion
            # - Make the previous point to the new item
            for i, link in enumerate(self.iterlinks()):
                if i == index - 1:
                    # TODO: Students implement this
                    newLink = Link(item, link.next)
                    link.next = newLink
                    break
        
        # Always increase size by 1
        self._size += 1
        

# Rig for doctest
if __name__ == "__main__":
    import doctest
    doctest.testmod()
    
def __reverse__(self):
    stack = []      
#while ( len(self): > 0):
    stack.append(self.item)
    i = i - 1
print(stack)