rlist.py (plain text)


"""The RList module contains the class implementing the mutable recursive list
(RList) data abstraction for CS61A at UC Berkeley.

RLists are mutable recursive lists (an alternative to lists), which implement
a common data structure found in most other programming languages.

One might notice that none of the doctests for the ADT actually "show" a RList.
This is because this ADT is meant to be treated as a black box: the tests do
not assume any specific implementation for RLists.
"""

# TODO: Should I add support for slicing?
# TODO: Should I add support for negative indexing?
# TODO: Have we already provided too much?

class RList:
    """A recursive list consisting of a first element and the rest.
    
    >>> s = RList(1, RList(2, RList(3)))
    >>> str(s)
    '<1, 2, 3>'
    >>> len(s)
    3
    >>> s[0]
    1
    >>> s[1]
    2
    >>> s[2]
    3
    >>> s[1] = 55
    >>> str(s)
    '<1, 55, 3>'
    >>> s == RList.populate(1, 55, 3)
    True
    >>> s is RList.populate(1, 55, 3)
    False
    >>> s != RList.populate(1, 55, 3)
    False
    >>> s != RList.populate(1, 5, 3)
    True
    >>> str(s + RList.populate(3, 2, 1))
    '<1, 55, 3, 3, 2, 1>'
    >>> str(s)
    '<1, 55, 3>'
    >>> repr(s)
    'RList(1, RList(55, RList(3)))'
    """

    class EmptyRList:
        """A special class for defining the "base case" of the data structure.
        This should NEVER be instantiated outside the class, instead use the
        RList empty method.
        """
        def __len__(self):
            return 0

        def __add__(self, other):
            if other is not RList.empty():
                return RList(other.first, self + other.rest)
            return RList.empty()

        def __eq__(self, other):
            return type(other) is type(self)

        def __ne__(self, other):
            return not (self == other)

        def __getitem__(self, k):
            raise IndexError("Index out of bounds: {0}".format(k))

        def __setitem__(self, k, new_val):
            raise IndexError("Index out of bounds: {0}".format(k))

        def __repr__(self):
            return "RList.empty()"

        def __str__(self):
            return "<>"

    # The one and ONLY instance of the EmptyRList class.
    the_empty_rlist = EmptyRList()

    @staticmethod
    def empty():
        """Returns the empty RList."""
        return RList.the_empty_rlist

    def __init__(self, first, rest=the_empty_rlist):
        self.first = first
        self.rest = rest

    @staticmethod
    def populate(*items):
        """Populates a new RList with the items provided."""
        if len(items) == 0:
            return RList.empty()
        return RList(items[0], RList.populate(*items[1:]))

    def __len__(self):
        """Returns the length of the current RList. The builtin
        function len(x) calls x.__len__().
        """
        return 1 + len(self.rest)

    def __add__(self, other):
        """Returns the RList containing the elements of self followed by the
        elements of other.  The operator x + y calls x.__add__(y).
        """
        return RList(self.first, self.rest + other)

    def __eq__(self, other):
        """Returns True if the two RLists contain equivalent sequences of
        equivalent items.  The operator x == y calls x.__eq__(y).
        """
        return type(self) is type(other) \
                and self.first == other.first \
                and self.rest == other.rest

    def __ne__(self, other):
        """Returns True if the two RLists do NOT contain equivalent sequences
        of equivalent items.  The operator x != y calls x.__eq__(y).
        """
        return not (self == other)

    def __getitem__(self, i):
        """Returns the element of the current RList at position i.
        The selection operator x[i] calls x.__getitem__(i).
        """
        if i == 0:
            return self.first
        return self.rest[i - 1]
        
    def __setitem__(self, i, new_val):
        """Updates the element of the current RList at position i.

        The update operator

            x[i] = new_val

        calls x.__setitem__(i, new_val)
        """
        if i == 0:
            self.first = new_val
        else:
            self.rest[i - 1] = new_val 

    def __repr__(self):
        """A printed representation of self that resembles a Python
        expression that reproduces the same list. The builtin function
        repr(x) calls x.__repr__(). The Python interpreter uses __repr__
        to print the values of non-null expressions it evaluates.
        """
        f = repr(self.first)
        if self.rest is RList.empty():
            return 'RList({0})'.format(f)
        else:
            return 'RList({0}, {1})'.format(f, repr(self.rest))

    def __str__(self):
        """Return a string representation for self.

        >>> str(RList.populate(1, 2, 3, 4, 5))
        '<1, 2, 3, 4, 5>'
        >>> str(RList.empty())
        '<>'
        >>> str(RList.populate(RList.populate(1, 2), 3))
        '<<1, 2>, 3>'
        >>> str(RList.populate([1, 2], 3))
        '<[1, 2], 3>'
        >>> str(RList.populate((1, 2), 3))
        '<(1, 2), 3>'
        """
        cur = self
        result = "<"
        while cur is not RList.empty():
            if type(cur.first) is RList or cur.first is RList.empty():
                result += str(cur.first)
            else:
                result += repr(cur.first)
            # Move forward and add comma if necessary
            cur = cur.rest
            if cur is not RList.empty():
                result += ", "
        return result + ">"