Virtual Slicing

[Bryan Olson]

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 += 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)
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()

 

[Sybren Stuvel]

Bryan Olson enlightened us with:

I recently wrote a module supporting value-shared slicing.

Maybe I'm dumb, but could you explain this concept? Why would someone
whant this?

Sybren

 

[Oren Tirosh]

I recently wrote a module supporting value-shared slicing. I
don't know if this functionality already existed somewhere,

In the Numarray module slices are a view into the underlying array
rather than a copy.

http://www.stsci.edu/resources/software_hardware/numarray

 

[Bryan Olson]

> Bryan Olson enlightened us with:
>
>
> Maybe I'm dumb, but could you explain this concept? Why would someone
> whant this?

My original motivation was reduce the amount of copying in some
tools that parse nested structures. All I really needed at the
time was a reference to a string, and the start and stop values.
Once I adopted Python's sequence interface, I thought I might as
well implement it consistently, generally, and completely.

So the first reason someone might want this is for efficiency,
in space and/or time.

The second reason is more abstract. Python's slice assignment is
a useful feature, but the slice selection must appear on the
right-hand-side of assignment. VSlice lets one instantiate the
updatable slice as an object, and pass it around.

I looked into supporting slice assignment between slices of
different sizes when possible, but the various options I came up
with all sucked.