from copy import copy from collections import MutableSequence class LinkedList(MutableSequence): """Linked list class""" def __init__(self: 'LinkedList', item: object=None, rest: 'LinkedList'=None) -> None: """Create a new LinkedList. item - The first element of the linked list, Not present if self will be the empty linked list. rest - The linked list that contains the elements after item. Not present if self will be the empty linked list.""" self.empty = (item is None) and (rest is None) if not self.empty: self.item = item if rest is None: self.rest = LinkedList() else: self.rest = rest def prepend(self: 'LinkedList', item: object) -> None: """Add new item to front of self""" self.item, self.rest, self.empty = item, copy(self), False def __repr__(self: 'LinkedList') -> str: """Return str representation of LinkedList self""" if self.empty: return 'LinkedList()' else: return 'LinkedList({}, {})'.format( repr(self.item), repr(self.rest)) def decapitate(self: 'LinkedList') -> None: """Delete item from LinkedList self.""" if self.empty: raise Exception("Can't decapitate empty list!") elif not self.rest.empty: self.item, self.rest = self.rest.item, self.rest.rest else: self.empty = True del(self.item) del(self.rest) def __contains__(self: 'LinkedList', value: object) -> bool: """Return whether self LinkedList contains value""" return (not self.empty and (self.item == value or value in self.rest)) def __getitem__(self: 'LinkedList', ind: int) -> object: """Return the item at position ind. Raise exception if ind is out-of-range""" if self.empty or ind < 0: raise IndexError elif ind > 0: return self.rest.__getitem__(ind - 1) else: return self.item def __setitem__(self: 'LinkedList', ind: int, val: object) -> None: """Replace element at position ind by val. Raise exception if ind is out-of-range. """ if self.empty or ind < 0: raise IndexError elif ind > 0: self.rest.__setitem__(ind - 1, val) else: self.item = val def __len__(self: 'LinkedList') -> int: """Return length of this LinkedList""" return 0 if self.empty else 1 + self.rest.__len__() def insert(self: 'LinkedList', ind: int, val: object) -> None: """Insert val at position ind, shifting the current occupant and all subsequent indices up by 1. Raise an exception if ind is out-of-range. """ if ind < 0 or (ind > 0 and self.empty): raise IndexError elif ind > 0: self.rest.insert(ind - 1, val) else: self.prepend(val) def __delitem__(self: 'LinkedList', ind: int) -> None: """Remove item at position ind, shifting every item after that down by 1. Raise an exception if ind is out-of-range. """ if ind < 0 or self.empty: raise IndexError elif ind > 0: self.rest.__delitem__(ind - 1) else: self.decapitate() def __eq__(self: 'LinkedList', other: 'LinkedList') -> bool: """Return whether self is equivalent to other. Equivalence means that the items are equivalent and the rests are equivalent. >>> lnk = LinkedList(5) >>> lnk.prepend(7) >>> lnk2 = LinkedList() >>> lnk2.prepend(5) >>> lnk2.prepend(7) >>> lnk.__eq__(lnk2) True """ return (isinstance(other, LinkedList) and ((self.empty and other.empty) or ((not self.empty) and (not other.empty) and self.item == other.item and self.rest == other.rest))) def copy_ll(self: 'LinkedList') -> 'LinkedList': """Return a copy of LinkedList self >>> lnk = LinkedList(5) >>> lnk.prepend(7) >>> lnk2 = lnk.copy_ll() >>> lnk is lnk2 False >>> lnk == lnk2 True >>> lnk.prepend(11) >>> lnk == lnk2 False """ if self.empty: return LinkedList() else: lnk = self.rest.copy_ll() # it's crazy that... lnk.prepend(self.item) # ... this takes three steps, return lnk # ... without importing chaining tools def filter_ll(self: 'LinkedList', t: 'boolean single-argument function') -> 'LinkedList': """Return LinkedList of elements of self that pass t(item), in the same order they appear in self. >>> lnk = LinkedList(5) >>> lnk.prepend(4) >>> lnk.prepend(7) >>> def f(n): return n % 2 == 0 >>> lnk2 = lnk.filter_ll(f) >>> lnk2 == LinkedList(4) True """ if self.empty: return LinkedList() else: lnk = self.rest.filter_ll(t) if t(self.item): lnk.prepend(self.item) return lnk class Queue: """A collection of items stored in 'first-in, first-out' (FIFO) order. Items can have any type. Supports standard operations: enqueue, dequeue, front, is_empty. """ def __init__(self: 'Queue') -> None: """ Initialize this queue. >>> q = Queue() >>> isinstance(q, Queue) True """ self._items = LinkedList() self._back, self._front = self._items, self._items def enqueue(self: 'Queue', item: object) -> None: """ Add item to the back of this queue. item - object to put in queue >>> q = Queue() >>> q.enqueue(5) >>> q.enqueue(6) >>> q.dequeue() 5 """ self._back.prepend(item) self._back = self._back.rest def dequeue(self: 'Queue') -> object: """ Remove and return the front item in this queue, provided self is non-empty. >>> q = Queue() >>> q.enqueue(5) >>> q.enqueue(6) >>> q.dequeue() 5 """ item = self._front.item self._front.decapitate() if self._front.empty: # back and front should coincide self._back = self._front return item def front(self: 'Queue') -> object: """ Return the front item in this queue without removing it. >>> q = Queue() >>> q.enqueue(5) >>> q.enqueue(6) >>> q.front() 5 >>> q.dequeue() 5 """ return self._front.item def is_empty(self: 'Queue'): """ Return True iff this queue is empty. >>> Queue().is_empty() True """ return self._front.empty if __name__ == '__main__': import doctest doctest.testmod()