# Copyright (c) 2008-2009 Aryeh Leib Taurog, all rights reserved.

# Released under the New BSD license.

"""

This module contains a base type which provides list-style mutations

without specific data storage methods.

See also http://www.aryehleib.com/MutableLists.html

Author: Aryeh Leib Taurog.

"""

class ListMixin(object):

    """

    A base class which provides complete list interface.

    Derived classes must call ListMixin's __init__() function

    and implement the following:

    function _get_single_external(self, i):

        Return single item with index i for general use.

        The index i will always satisfy 0 <= i < len(self).

    function _get_single_internal(self, i):

        Same as above, but for use within the class [Optional]

        Note that if _get_single_internal and _get_single_internal return

        different types of objects, _set_list must distinguish

        between the two and handle each appropriately.

    function _set_list(self, length, items):

        Recreate the entire object.

        NOTE: items may be a generator which calls _get_single_internal.

        Therefore, it is necessary to cache the values in a temporary:

            temp = list(items)

        before clobbering the original storage.

    function _set_single(self, i, value):

        Set the single item at index i to value [Optional]

        If left undefined, all mutations will result in rebuilding

        the object using _set_list.

    function __len__(self):

        Return the length

    int _minlength:

        The minimum legal length [Optional]

    int _maxlength:

        The maximum legal length [Optional]

    type or tuple _allowed:

        A type or tuple of allowed item types [Optional]

    class _IndexError:

        The type of exception to be raise on invalid index [Optional]

    """

    _minlength = 0

    _maxlength = None

    _IndexError = IndexError

    ### Python initialization and special list interface methods ###

    def __init__(self, *args, **kwargs):

        if not hasattr(self, '_get_single_internal'):

            self._get_single_internal = self._get_single_external

        if not hasattr(self, '_set_single'):

            self._set_single = self._set_single_rebuild

            self._assign_extended_slice = self._assign_extended_slice_rebuild

        super(ListMixin, self).__init__(*args, **kwargs)

    def __getitem__(self, index):

        "Get the item(s) at the specified index/slice."

        if isinstance(index, slice):

            return [self._get_single_external(i) for i in xrange(*index.indices(len(self)))]

        else:

            index = self._checkindex(index)

            return self._get_single_external(index)

    def __delitem__(self, index):

        "Delete the item(s) at the specified index/slice."

        if not isinstance(index, (int, long, slice)):

            raise TypeError("%s is not a legal index" % index)

        # calculate new length and dimensions

        origLen     = len(self)

        if isinstance(index, (int, long)):

            index = self._checkindex(index)

            indexRange  = [index]

        else:

            indexRange  = range(*index.indices(origLen))

        newLen      = origLen - len(indexRange)

        newItems    = ( self._get_single_internal(i)

                        for i in xrange(origLen)

                        if i not in indexRange )

        self._rebuild(newLen, newItems)

    def __setitem__(self, index, val):

        "Set the item(s) at the specified index/slice."

        if isinstance(index, slice):

            self._set_slice(index, val)

        else:

            index = self._checkindex(index)

            self._check_allowed((val,))

            self._set_single(index, val)

    def __iter__(self):

        "Iterate over the items in the list"

        for i in xrange(len(self)):

            yield self[i]

    ### Special methods for arithmetic operations ###

    def __add__(self, other):

        'add another list-like object'

        return self.__class__(list(self) + list(other))

    def __radd__(self, other):

        'add to another list-like object'

        return other.__class__(list(other) + list(self))

    def __iadd__(self, other):

        'add another list-like object to self'

        self.extend(list(other))

        return self

    def __mul__(self, n):

        'multiply'

        return self.__class__(list(self) * n)

    def __rmul__(self, n):

        'multiply'

        return self.__class__(list(self) * n)

    def __imul__(self, n):

        'multiply'

        if n <= 0:

            del self[:]

        else:

            cache = list(self)

            for i in range(n-1):

                self.extend(cache)

        return self

    def __cmp__(self, other):

        'cmp'

        slen = len(self)

        for i in range(slen):

            try:

                c = cmp(self[i], other[i])

            except IndexError:

                # must be other is shorter

                return 1

            else:

                # elements not equal

                if c: return c

        return cmp(slen, len(other))

    ### Public list interface Methods ###

    ## Non-mutating ##

    def count(self, val):

        "Standard list count method"

        count = 0

        for i in self:

            if val == i: count += 1

        return count

    def index(self, val):

        "Standard list index method"

        for i in xrange(0, len(self)):

            if self[i] == val: return i

        raise ValueError('%s not found in object' % str(val))

    ## Mutating ##

    def append(self, val):

        "Standard list append method"

        self[len(self):] = [val]

    def extend(self, vals):

        "Standard list extend method"

        self[len(self):] = vals

    def insert(self, index, val):

        "Standard list insert method"

        if not isinstance(index, (int, long)):

            raise TypeError("%s is not a legal index" % index)

        self[index:index] = [val]

    def pop(self, index=-1):

        "Standard list pop method"

        result = self[index]

        del self[index]

        return result

    def remove(self, val):

        "Standard list remove method"

        del self[self.index(val)]

    def reverse(self):

        "Standard list reverse method"

        self[:] = self[-1::-1]

    def sort(self, cmp=cmp, key=None, reverse=False):

        "Standard list sort method"

        if key:

            temp = [(key(v),v) for v in self]

            temp.sort(cmp=cmp, key=lambda x: x[0], reverse=reverse)

            self[:] = [v[1] for v in temp]

        else:

            temp = list(self)

            temp.sort(cmp=cmp, reverse=reverse)

            self[:] = temp

    ### Private routines ###

    def _rebuild(self, newLen, newItems):

        if newLen < self._minlength:

            raise ValueError('Must have at least %d items' % self._minlength)

        if self._maxlength is not None and newLen > self._maxlength:

            raise ValueError('Cannot have more than %d items' % self._maxlength)

        self._set_list(newLen, newItems)

    def _set_single_rebuild(self, index, value):

        self._set_slice(slice(index, index + 1, 1), [value])

    def _checkindex(self, index, correct=True):

        length = len(self)

        if 0 <= index < length:

            return index

        if correct and -length <= index < 0:

            return index + length

        raise self._IndexError('invalid index: %s' % str(index))

    def _check_allowed(self, items):

        if hasattr(self, '_allowed'):

            if False in [isinstance(val, self._allowed) for val in items]:

                raise TypeError('Invalid type encountered in the arguments.')

    def _set_slice(self, index, values):

        "Assign values to a slice of the object"

        try:

            iter(values)

        except TypeError:

            raise TypeError('can only assign an iterable to a slice')

        self._check_allowed(values)

        origLen     = len(self)

        valueList   = list(values)

        start, stop, step = index.indices(origLen)

        # CAREFUL: index.step and step are not the same!

        # step will never be None

        if index.step is None:

            self._assign_simple_slice(start, stop, valueList)

        else:

            self._assign_extended_slice(start, stop, step, valueList)

    def _assign_extended_slice_rebuild(self, start, stop, step, valueList):

        'Assign an extended slice by rebuilding entire list'

        indexList   = range(start, stop, step)

        # extended slice, only allow assigning slice of same size

        if len(valueList) != len(indexList):

            raise ValueError('attempt to assign sequence of size %d '

                             'to extended slice of size %d'

                             % (len(valueList), len(indexList)))

        # we're not changing the length of the sequence

        newLen  = len(self)

        newVals = dict(zip(indexList, valueList))

        def newItems():

            for i in xrange(newLen):

                if i in newVals:

                    yield newVals[i]

                else:

                    yield self._get_single_internal(i)

        self._rebuild(newLen, newItems())

    def _assign_extended_slice(self, start, stop, step, valueList):

        'Assign an extended slice by re-assigning individual items'

        indexList   = range(start, stop, step)

        # extended slice, only allow assigning slice of same size

        if len(valueList) != len(indexList):

            raise ValueError('attempt to assign sequence of size %d '

                             'to extended slice of size %d'

                             % (len(valueList), len(indexList)))

        for i, val in zip(indexList, valueList):

            self._set_single(i, val)

    def _assign_simple_slice(self, start, stop, valueList):

        'Assign a simple slice; Can assign slice of any length'

        origLen = len(self)

        stop = max(start, stop)

        newLen  = origLen - stop + start + len(valueList)

        def newItems():

            for i in xrange(origLen + 1):

                if i == start:

                    for val in valueList:

                        yield val

                if i < origLen:

                    if i < start or i >= stop:

                        yield self._get_single_internal(i)

        self._rebuild(newLen, newItems())