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

     2 # Released under the New BSD license.

     3 """

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

     5 without specific data storage methods.

     6 

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

     8 

     9 Author: Aryeh Leib Taurog.

    10 """

    11 class ListMixin(object):

    12     """

    13     A base class which provides complete list interface.

    14     Derived classes must call ListMixin's __init__() function

    15     and implement the following:

    16 

    17     function _get_single_external(self, i):

    18         Return single item with index i for general use.

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

    20 

    21     function _get_single_internal(self, i):

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

    23         Note that if _get_single_internal and _get_single_internal return

    24         different types of objects, _set_list must distinguish

    25         between the two and handle each appropriately.

    26 

    27     function _set_list(self, length, items):

    28         Recreate the entire object.

    29 

    30         NOTE: items may be a generator which calls _get_single_internal.

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

    32             temp = list(items)

    33         before clobbering the original storage.

    34 

    35     function _set_single(self, i, value):

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

    37         If left undefined, all mutations will result in rebuilding

    38         the object using _set_list.

    39 

    40     function __len__(self):

    41         Return the length

    42 

    43     int _minlength:

    44         The minimum legal length [Optional]

    45 

    46     int _maxlength:

    47         The maximum legal length [Optional]

    48 

    49     type or tuple _allowed:

    50         A type or tuple of allowed item types [Optional]

    51 

    52     class _IndexError:

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

    54     """

    55 

    56     _minlength = 0

    57     _maxlength = None

    58     _IndexError = IndexError

    59 

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

    61 

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

    63         if not hasattr(self, '_get_single_internal'):

    64             self._get_single_internal = self._get_single_external

    65 

    66         if not hasattr(self, '_set_single'):

    67             self._set_single = self._set_single_rebuild

    68             self._assign_extended_slice = self._assign_extended_slice_rebuild

    69 

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

    71 

    72     def __getitem__(self, index):

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

    74         if isinstance(index, slice):

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

    76         else:

    77             index = self._checkindex(index)

    78             return self._get_single_external(index)

    79 

    80     def __delitem__(self, index):

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

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

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

    84 

    85         # calculate new length and dimensions

    86         origLen     = len(self)

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

    88             index = self._checkindex(index)

    89             indexRange  = [index]

    90         else:

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

    92 

    93         newLen      = origLen - len(indexRange)

    94         newItems    = ( self._get_single_internal(i)

    95                         for i in xrange(origLen)

    96                         if i not in indexRange )

    97 

    98         self._rebuild(newLen, newItems)

    99 

   100     def __setitem__(self, index, val):

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

   102         if isinstance(index, slice):

   103             self._set_slice(index, val)

   104         else:

   105             index = self._checkindex(index)

   106             self._check_allowed((val,))

   107             self._set_single(index, val)

   108 

   109     def __iter__(self):

   110         "Iterate over the items in the list"

   111         for i in xrange(len(self)):

   112             yield self[i]

   113 

   114     ### Special methods for arithmetic operations ###

   115     def __add__(self, other):

   116         'add another list-like object'

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

   118 

   119     def __radd__(self, other):

   120         'add to another list-like object'

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

   122 

   123     def __iadd__(self, other):

   124         'add another list-like object to self'

   125         self.extend(list(other))

   126         return self

   127 

   128     def __mul__(self, n):

   129         'multiply'

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

   131 

   132     def __rmul__(self, n):

   133         'multiply'

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

   135 

   136     def __imul__(self, n):

   137         'multiply'

   138         if n <= 0:

   139             del self[:]

   140         else:

   141             cache = list(self)

   142             for i in range(n-1):

   143                 self.extend(cache)

   144         return self

   145 

   146     def __cmp__(self, other):

   147         'cmp'

   148         slen = len(self)

   149         for i in range(slen):

   150             try:

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

   152             except IndexError:

   153                 # must be other is shorter

   154                 return 1

   155             else:

   156                 # elements not equal

   157                 if c: return c

   158 

   159         return cmp(slen, len(other))

   160 

   161     ### Public list interface Methods ###

   162     ## Non-mutating ##

   163     def count(self, val):

   164         "Standard list count method"

   165         count = 0

   166         for i in self:

   167             if val == i: count += 1

   168         return count

   169 

   170     def index(self, val):

   171         "Standard list index method"

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

   173             if self[i] == val: return i

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

   175 

   176     ## Mutating ##

   177     def append(self, val):

   178         "Standard list append method"

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

   180 

   181     def extend(self, vals):

   182         "Standard list extend method"

   183         self[len(self):] = vals

   184 

   185     def insert(self, index, val):

   186         "Standard list insert method"

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

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

   189         self[index:index] = [val]

   190 

   191     def pop(self, index=-1):

   192         "Standard list pop method"

   193         result = self[index]

   194         del self[index]

   195         return result

   196 

   197     def remove(self, val):

   198         "Standard list remove method"

   199         del self[self.index(val)]

   200 

   201     def reverse(self):

   202         "Standard list reverse method"

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

   204 

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

   206         "Standard list sort method"

   207         if key:

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

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

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

   211         else:

   212             temp = list(self)

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

   214             self[:] = temp

   215 

   216     ### Private routines ###

   217     def _rebuild(self, newLen, newItems):

   218         if newLen < self._minlength:

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

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

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

   222 

   223         self._set_list(newLen, newItems)

   224 

   225     def _set_single_rebuild(self, index, value):

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

   227 

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

   229         length = len(self)

   230         if 0 <= index < length:

   231             return index

   232         if correct and -length <= index < 0:

   233             return index + length

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

   235 

   236     def _check_allowed(self, items):

   237         if hasattr(self, '_allowed'):

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

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

   240 

   241     def _set_slice(self, index, values):

   242         "Assign values to a slice of the object"

   243         try:

   244             iter(values)

   245         except TypeError:

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

   247 

   248         self._check_allowed(values)

   249 

   250         origLen     = len(self)

   251         valueList   = list(values)

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

   253 

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

   255         # step will never be None

   256         if index.step is None:

   257             self._assign_simple_slice(start, stop, valueList)

   258         else:

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

   260 

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

   262         'Assign an extended slice by rebuilding entire list'

   263         indexList   = range(start, stop, step)

   264         # extended slice, only allow assigning slice of same size

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

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

   267                              'to extended slice of size %d'

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

   269 

   270         # we're not changing the length of the sequence

   271         newLen  = len(self)

   272         newVals = dict(zip(indexList, valueList))

   273         def newItems():

   274             for i in xrange(newLen):

   275                 if i in newVals:

   276                     yield newVals[i]

   277                 else:

   278                     yield self._get_single_internal(i)

   279 

   280         self._rebuild(newLen, newItems())

   281 

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

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

   284         indexList   = range(start, stop, step)

   285         # extended slice, only allow assigning slice of same size

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

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

   288                              'to extended slice of size %d'

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

   290 

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

   292             self._set_single(i, val)

   293 

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

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

   296         origLen = len(self)

   297         stop = max(start, stop)

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

   299         def newItems():

   300             for i in xrange(origLen + 1):

   301                 if i == start:

   302                     for val in valueList:

   303                         yield val

   304 

   305                 if i < origLen:

   306                     if i < start or i >= stop:

   307                         yield self._get_single_internal(i)

   308 

   309         self._rebuild(newLen, newItems())