"""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 + ">"