Virtual Slicing

Bryan Olson fakeaddress at nowhere.org
Sat Aug 27 10:00:45 CEST 2005



I recently wrote a module supporting value-shared slicing. I
don't know if this functionality already existed somewhere, but
I think it's useful enough that other Pythoners might want it,
so here it is.

Also, my recent notes on Python warts with respect to negative
indexes were based on problems I encoutered debugging this
module, so I'm posting it partially as a concrete example of
what I was talking about.

--
--Bryan

----------------------------------------------------------------

"""
     vslice.py by Bryan G. Olson, 2005
     This module is free software and may be modified and/or
     distributed under the same terms as Python itself.

     Virtual Slicing differs from normal Python slicing in that
     that the cells in the given sequence are not copied; they
     are shared between the underlying sequence and the VSlice.
     VSlices are themselves Python sequences. You can index
     VSlices, slice them, iterate over them, get their len(),
     test 'if val in', compare them, add them, and multiply them
     by integers.

     The 'vslice' function creates virtual slices of sequences:

         vslice(sequence, start, stop, step)

     returns an instance of VSlice that is much-the-same-as:

         sequence[start : stop : step]

     The default for start, stop and step is None, and passing
     None or omitting parameters works the same as in Python
     slicing.

     VSlices also have read-only properties 'sequence', 'start',
     'stop' and 'step', in case you need to access the underlying
     sequence directly. Like Python's 'slice' object, the stop
     value will be negative if and only if step is negative and
     the slice includes the zero index.

     A VSlice of a VSlice will use the same underlying sequence.
     It will translate the start-stop-step values upon
     construction, so later access will go through only one layer
     of VSlicing. The sequence, start, stop, and step properties
     of the VSlice-of-a-VSlice will generally not be same as the
     parameters passed to the vslice factory function; they
     relate to the underlying sequence.

         >>> a = range(100)
         >>> from vslice import vslice
         >>> vs1 = vslice(a, 10, None, 2)
         >>> vs2 = vslice(vs1, 2, -2, 3)
         >>>
         >>> print vs2 == a[10 : None : 2][2 : -2 : 3]
         True
         >>> print vs2.sequence == vs1
         False
         >>> print vs2.sequence == a
         True
         >>> print vs2.sequence is a
         True
         >>> print vs2.start, vs2.stop, vs2.step
         14 96 6
         >>> print vs2 == a[14 : 96 : 6]
         True


     If the underlying sequence is mutable, the VSlice is semi-
     mutable. You can assign to elements, but not insert nor
     delete elements; similarly, no append, push, pop and such.
     Slice assignments must have the same length slice on both
     sides.

     A slice of a VSlice is a regular Python slice; it is a copy
     made by slicing the underlying sequence with translated
     start-stop-step values. For sane sequence types, the slice
     of the VSlice will therefore have the same type as the
     underlying sequence.

     A VSlice's start-stop-step and len are set on construction.
     Adding or removing indices from the underlying sequence will
     not change them, and is usually a bad thing to do.

     VSlices support any positive or negative integer step value,
     but are most efficient in both time and space when the step
     value is one. Fortunately, the need for any other step value
     is rare. The vslice function will choose between two sub-
     classes of VSlice, depending on whether the step is one. The
     VxSlice can support any step size; the V1Slice is faster and
     smaller, but only supports a step of one. VxSlice instances
     store five slots; V1Slices, 3.

"""


def vslice(sequence, start=None, stop=None, step=None):
     """ Return a VSlice (virtual slice). See module's __doc__.
     """
     start, stop, step = slice(start, stop, step).indices(len(sequence))
     if isinstance(sequence, VSlice):
         start = sequence.start + start * sequence.step
         stop = sequence.start + stop * sequence.step
         step *= sequence.step
         sequence = sequence.sequence
     if step == 1:
         return V1Slice(sequence, start, stop)
     else:
         return VxSlice(sequence, start, stop, step)



from itertools import islice

_type_err_note = 'VSlice index must be integer or slice.'

_module_doc = __doc__

class VSlice (object):

     __doc__ = _module_doc

     def __init__(self, *args):
         if self.__class__ == VSlice:
             raise RuntimeError("Attempt to instantiate abstract base " +
             "class VSlice. To create a VSlice, call vslice.vslice().")

     def get_sequence(self):
         return self._seq
     sequence = property(get_sequence, None, None,
             'The underlying sequence, never itself a VSlice.')

     def get_start(self):
         return self._start
     start = property(get_start, None, None,
             'Inclusive bound in the underlying sequence.')

     def get_stop(self):
         return self._stop
     stop = property(get_stop, None, None,
             'Exclusive bound in the underlying sequence.')

     def get_step(self):
         return self._step
     step = property(lambda self: self.get_step(), None, None,
             'Size of steps relative to the underlying sequence.')

     def __getitem__(self, key):
         if isinstance(key, (int, long)):
             return self._seq[self._translate(key)]
         elif isinstance(key, slice):
             (start, stop, step) = self._translate_slice(key)
             return self._seq[start : stop : step]
         else:
             raise TypeError(_type_err_note)

     def __setitem__(self, key, value):
         if isinstance(key, (int, long)):
             self._seq[self._translate(key)] = value
         elif isinstance(key, slice):
             (start, stop, step) = self._translate_slice(key)
             self._seq[start : stop : step] = value
         else:
             raise TypeError(_type_err_note)

     def __cmp__(self, other):
         # Compare progressively larger chunks.
         start, stop = 0, 4
         while 1:
             me = self[start : stop]
             them = other[start : stop]
             if me != them:
                 return cmp(me, them)
             if len(me) < stop - start:
                 return 0
             start, stop = stop, stop + stop

     def __repr__(self):
         return 'vslice(%s)' % repr(self[:])

     def __add__(self, term):
         return self[:] + term

     def __mul__(self, term):
         return self[:] * term

     def __hash__(self):
         return hash(self[:])

     #   Various bad ideas for  def __getattr__(self, name):
     #       return getattr(self[:], name)
     #       return getattr(self[0:0], name)
     #       return getattr(self._seq, name)



class V1Slice (VSlice):

     'VSlice subclass for step == 1'

     __slots__ = '_seq', '_start', '_stop'

     def __init__(self, sequence, start, stop):
         self._seq, self._start, self._stop = sequence, start, stop

     def get_step(self):
         return 1

     def __len__(self):
         return self._stop - self._start

     def __iter__(self):
         return islice(self._seq, self._start, self._stop)

     def _translate(self, i):
         length = self._stop - self._start
         if not -length <= i < length:
             raise IndexError
         return slice(i, i + 1).indices(length)[0]

     def _translate_slice(self, key):
         start, stop, step = key.indices(len(self))
         stop = self._start + stop
         if stop < 0:
             stop = None
         return (self._start + start, stop, step)



class VxSlice(VSlice):

     'VSlice subclass for step of any integer'

     __slots__ = '_seq', '_start', '_stop', '_step', '_length'

     def __init__(self, sequence, start=None, stop=None, step=1):
         self._seq, self._start, self._stop, self._step = (
                     sequence, start, stop, step)
         self._length = max(0, (self._stop - self._start +
                 self._step - (self._step / abs(self._step))) // self._step)

     def __len__(self):
         return self._length

     def __iter__(self):
         if self._step >= 0:
             return islice(self._seq, self._start, self._stop, self._step)
         else:
             def gen():
                 seq, i, stop, step = (self._seq, self._start,
                         self._stop, self._step)
                 while i > stop:
                     yield seq[i]
                     i += step
             return gen()

     def _translate(self, index):
         if index < 0:
             index = self._length + index
         if index < 0 or index > self._length:
             raise IndexError('VxSlice index %d out of range' % index)
         return self._start + (index * self._step)

     def _translate_slice(self, key):
         start, stop, step = key.indices(self._length)
         start, stop, step = (
                 self._start + (start * self._step),
                 self._start + (stop * self._step),
                 step * self._step)
         if stop < 0:
             stop = None
         return (start, stop, step)



def test():
     print __doc__

     def assert_equal(vslice, target):
         assert len(vslice) == len(target)
         assert vslice == target
         assert vslice[:] == target
         assert vslice[: 7L] + vslice[7 :] == target
         assert vslice[::-1][::-1] == target
         assert [x for x in vslice] == [x for x in target]
         blist, clist, dlist = [], [], []
         for i in range(len(vslice)):
             blist.append(vslice[i])
             j = 0 - i - 1
             clist.append(vslice[j])
             dlist.append(vslice[long(i)])
         assert blist == [x for x in target]
         clist.reverse()
         assert clist == [x for x in target]
         assert dlist == [x for x in target]
         assert vslice[2 : -3] == target[2 : -3]
     base = [1 + 2 * n for n in range(100)]
     a = base[:]
     # Test various copies
     va = vslice(a)
     assert_equal(va, a)
     assert_equal(vslice(a, None, None, -1), a[:: -1])
     assert_equal(vslice(va, None, None, -3), a[:: -3])
     assert_equal(vslice(a, 4L, 67, 5), a[4: 67 : 5])
     assert_equal(vslice(va, -84, 67, 4), a[-84: 67 : 4])
     assert_equal(vslice(va, 22, -12, 8), a[22: -12 : 8])
     assert_equal(vslice(va, -91, -17, 7), a[-91: -17 : 7])
     assert_equal(vslice(a, -97, -10, -6), a[-97: -10 : -6])
     assert_equal(vslice(va, -83, -11, -3), a[-83: -11 : -3])
     # Test some updates
     va[6 : 82 : 7] = [6 + x * 17 for x in range(4, 80, 7)]
     assert_equal(va, a)
     a[22] = 9427
     assert_equal(va, a)
     b = base[:]
     vb = base[:]
     assert_equal(vb, b)
     b[37] = 61107
     assert tuple(b) != tuple(vb)
     vb[37] = 61107
     assert tuple(b) == tuple(vb)
     newjunk = [12 + x * 3 for x in range(4, 80, 7)]
     b[5 : 80 : 7] = newjunk
     assert tuple(b) != tuple(vb)
     vb[5 : 80 : 7] = newjunk
     assert tuple(b) == tuple(vb)
     print "Good."


if __name__ == '__main__':
     test()




More information about the Python-list mailing list