Implementing python slice notation

Question

I'm trying to reimplement python slice notation in another language (php) and looking for a snippet (in any language or pseudocode) that would mimic the python logic. That is, given a list and a triple (start, stop, step) or a part thereof, determine correct values or defaults for all parameters and return a slice as a new list.

I tried looking into the source. That code is far beyond my c skills, but I can't help but agree with the comment saying:

/* this is harder to get right than you might think */

Also, if something like this is already done, pointers will be greatly appreciated.

This is my test bench (make sure your code passes before posting):

#place your code below
code = """
def mySlice(L, start=None, stop=None, step=None):
or 
<?php function mySlice($L, $start=NULL, $stop=NULL, $step=NULL) ...
or 
function mySlice(L, start, stop, step) ...
"""

import itertools

L = [0,1,2,3,4,5,6,7,8,9]

if code.strip().startswith('<?php'):
     mode = 'php'

if code.strip().startswith('def'):
     mode = 'python'

if code.strip().startswith('function'):
     mode = 'js'

if mode == 'php':
    var, none = '$L', 'NULL'
    print code, '\n'
    print '$L=array(%s);' % ','.join(str(x) for x in L)
    print "function _c($s,$a,$e){if($a!==$e)echo $s,' should be [',implode(',',$e),'] got [',implode(',',$a),']',PHP_EOL;}"

if mode == 'python':
    var, none = 'L', 'None'
    print code, '\n'
    print 'L=%r' % L
    print "def _c(s,a,e):\n\tif a!=e:\n\t\tprint s,'should be',e,'got',a"

if mode == 'js':
    var, none = 'L', 'undefined'
    print code, '\n'
    print 'L=%r' % L
    print "function _c(s,a,e){if(a.join()!==e.join())console.log(s+' should be ['+e.join()+'] got ['+a.join()+']');}"


print

n = len(L) + 3
start = range(-n, n) + [None, 100, -100]
stop  = range(-n, n) + [None, 100, -100]
step  = range(-n, n) + [100, -100]

for q in itertools.product(start, stop, step): 

    if not q[2]: q = q[:-1]

    actual = 'mySlice(%s,%s)' % (var, ','.join(none if x is None else str(x) for x in q))
    slice_ = 'L[%s]' % ':'.join('' if x is None else str(x) for x in q)
    expect = eval(slice_)

    if mode == 'php':
        expect = 'array(%s)' % ','.join(str(x) for x in expect)
        print "_c(%r,%s,%s);" % (slice_, actual, expect)

    if mode == 'python':
        print "_c(%r,%s,%s);" % (slice_, actual, expect)

    if mode == 'js':
        print "_c(%r,%s,%s);" % (slice_, actual, expect)

how to use it:

save into a file (test.py)
place your python, php or javascript code between """s
run python test.py | python or python test.py | php or python test.py | node

ecatmur · Accepted Answer · 2012-08-31 13:23:32Z

18

+200

Here's a straight port of the C code:

def adjust_endpoint(length, endpoint, step):
     if endpoint < 0:
         endpoint += length
         if endpoint < 0:
             endpoint = -1 if step < 0 else 0
     elif endpoint >= length:
         endpoint = length - 1 if step < 0 else length
     return endpoint

def adjust_slice(length, start, stop, step):
     if step is None:
         step = 1
     elif step == 0:
         raise ValueError("step cannot be 0")

     if start is None:
         start = length - 1 if step < 0 else 0
     else:
         start = adjust_endpoint(length, start, step)

     if stop is None:
         stop = -1 if step < 0 else length
     else:
         stop = adjust_endpoint(length, stop, step)

     return start, stop, step

def slice_indices(length, start, stop, step):
     start, stop, step = adjust_slice(length, start, stop, step)
     i = start
     while (i > stop) if step < 0 else (i < stop):
         yield i
         i += step

def mySlice(L, start=None, stop=None, step=None):
     return [L[i] for i in slice_indices(len(L), start, stop, step)]

answered Aug 31, 2012 at 13:23

ecatmur

158k28 gold badges311 silver badges387 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Claudiu Over a year ago

+1: when in doubt, just do a straightforward port of the code that is known to work

georg Over a year ago

It was a tough choice, since other answers are equally good, but your code is cleaner and you were the first -- so it's yours. Many thanks!

ecatmur Over a year ago

@saul.shanabrook sure: hg.python.org/cpython/file/3d4d52e47431/Objects/… (it's linked in the question as well).

inspectorG4dget · Accepted Answer · 2012-08-31 03:37:40Z

2

This is what I came up with (python)

def mySlice(L, start=None, stop=None, step=None):
    answer = []
    if not start:
        start = 0
    if start < 0:
        start += len(L)

    if not stop:
        stop = len(L)
    if stop < 0:
        stop += len(L)

    if not step:
        step = 1

    if stop == start or (stop<=start and step>0) or (stop>=start and step<0):
        return []

    i = start
    while i != stop:
        try:
            answer.append(L[i])
            i += step
        except:
            break
    return answer

Seems to work - let me know what you think

Hope it helps

edited Aug 31, 2012 at 3:37

answered Aug 29, 2012 at 8:46

inspectorG4dget

115k30 gold badges159 silver badges253 bronze badges

7 Comments

georg Over a year ago

Thanks, but this doesn't seem to handle negative values correctly.

verdesmarald Over a year ago

What's up with the weird modulo stuff? Slice doesn't work like that. Also slice is a poor choice of function name since it shadows a builtin.

inspectorG4dget Over a year ago

@veredesmarald: I checked the math on the modulo. It works as expected. Perhaps the C implementation differs from mine, but that doesn't make mine invalid (m I wrong?). Good point on the bad name - updated

Pierre GM Over a year ago

Things will break for step<0. Eg, the if (stop <= start): return [] will not allow you to have a slice like slice(10:1:-1), which is valid.

inspectorG4dget Over a year ago

@PierreGM: UPdated to handle negative step

|

westin · Accepted Answer · 2012-09-03 13:17:41Z

This is a solution I came up with in C# .NET, maybe not the prettiest, but it works.

private object[] Slice(object[] list, int start = 0, int stop = 0, int step = 0)
{
    List<object> result = new List<object>();

    if (step == 0) step = 1;
    if (start < 0)
    {
        for (int i = list.Length + start; i < list.Length - (list.Length + start); i++)
        {
            result.Add(list[i]);
        }
    }
    if (start >= 0 && stop == 0) stop = list.Length - (start >= 0 ? start : 0);
    else if (start >= 0 && stop < 0) stop = list.Length + stop;

    int loopStart = (start < 0 ? 0 : start);
    int loopEnd = (start > 0 ? start + stop : stop);

    if (step > 0)
    {
        for (int i = loopStart; i < loopEnd; i += step)
            result.Add(list[i]);
    }
    else if (step < 0)
    {
        for (int i = loopEnd - 1; i >= loopStart; i += step)
            result.Add(list[i]);
    }

    return result.ToArray();
}

Ja͢ck · Accepted Answer · 2012-09-05 07:53:36Z

I've written a PHP port based on the C code, optimized for step sizes -1 and 1:

function get_indices($length, $step, &$start, &$end, &$size)
{
        if (is_null($start)) {
                $start = $step < 0 ? $length - 1 : 0;
        } else {
                if ($start < 0) {
                        $start += $length;
                        if ($start < 0) {
                                $start = $step < 0 ? -1 : 0;
                        }
                } elseif ($start >= $length) {
                        $start = $step < 0 ? $length - 1 : $length;
                }
        }

        if (is_null($end)) {
                $end = $step < 0 ? -1 : $length;
        } else {
                if ($end < 0) {
                        $end += $length;
                        if ($end < 0) {
                                $end = $step < 0 ? - 1 : 0;
                        }
                } elseif ($end >= $length) {
                        $end = $step < 0 ? $length - 1 : $length;
                }
        }

        if (($step < 0 && $end >= $start) || ($step > 0 && $start >= $end)) {
                $size = 0;
        } elseif ($step < 0) {
                $size = ($end - $start + 1) / $step + 1;
        } else {
                $size = ($end - $start - 1) / $step + 1;
        }
}

function mySlice($L, $start = NULL, $end = NULL, $step = 1)
{
        if (!$step) {
                return false; // could throw exception too
        }
        $length = count($L);
        get_indices($length, $step, $start, $end, $size);

        // optimize default step
        if ($step == 1) {
                // apply native array_slice()
                return array_slice($L, $start, $size);
        } elseif ($step == -1) {
                // negative step needs an array reversal first
                // with range translation
                return array_slice(array_reverse($L), $length - $start - 1, $size);
        } else {
                // standard fallback
                $r = array();
                for ($i = $start; $step < 0 ? $i > $end : $i < $end; $i += $step) {
                        $r[] = $L[$i];
                }
                return $r;
        }
}

Very good idea to use array_slice, since most calls to mySlice will use step == 1.

mcrumley · Accepted Answer · 2012-09-06 20:19:12Z

1

This is based on @ecatmur's Python code ported again to PHP.

<?php
function adjust_endpoint($length, $endpoint, $step) {
    if ($endpoint < 0) {
        $endpoint += $length;
        if ($endpoint < 0) {
            $endpoint = $step < 0 ? -1 : 0;
        }
    }
    elseif ($endpoint >= $length) {
        $endpoint = $step < 0 ? $length - 1 : $length;
    }
    return $endpoint;
}

function mySlice($L, $start = null, $stop = null, $step = null) {
    $sliced = array();
    $length = count($L);

    // adjust_slice()
    if ($step === null) {
        $step = 1;
    }
    elseif ($step == 0) {
        throw new Exception('step cannot be 0');
    }

    if ($start === null) {
        $start = $step < 0 ? $length - 1 : 0;
    }
    else {
        $start = adjust_endpoint($length, $start, $step);
    }

    if ($stop === null) {
        $stop = $step < 0 ? -1 : $length;
    }
    else {
        $stop = adjust_endpoint($length, $stop, $step);
    }

    // slice_indices()
    $i = $start;
    $result = array();
    while ($step < 0 ? ($i > $stop) : ($i < $stop)) {
        $sliced []= $L[$i];
        $i += $step;
    }
    return $sliced;
}

answered Sep 6, 2012 at 20:19

mcrumley

5,7103 gold badges28 silver badges33 bronze badges

1 Comment

georg Over a year ago

Thanks! This appears to work well, but for the php version array_slice optimization (see @Jack's post) is indispensable.

Marcus · Accepted Answer · 2012-09-06 07:20:23Z

I can't say there's no bug in the codes, but it had past your test program :)

def mySlice(L, start=None, stop=None, step=None):
    ret = []
    le = len(L)
    if step is None: step = 1

    if step > 0: #this situation might be easier
        if start is None: 
            start = 0
        else:
            if start < 0: start += le
            if start < 0: start = 0
            if start > le: start = le

        if stop is None: 
            stop = le
        else:
            if stop < 0: stop += le
            if stop < 0: stop = 0
            if stop > le: stop = le
    else:
        if start is None:
            start = le-1
        else:
            if start < 0: start += le
            if start < 0: start = -1
            if start >= le: start = le-1

        if stop is None: 
            stop = -1 #stop is not 0 because we need L[0]
        else:
            if stop < 0: stop += le
            if stop < 0: stop = -1
            if stop >= le: stop = le

    #(stop-start)*step>0 to make sure 2 things: 
    #1: step != 0
    #2: iteration will end
    while start != stop and (stop-start)*step > 0 and start >=0 and start < le:
        ret.append( L[start] )
        start += step

    return ret

Collectives™ on Stack Overflow

Implementing python slice notation

6 Answers 6

3 Comments

7 Comments

Comments

1 Comment

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

3 Comments

7 Comments

Comments

1 Comment

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related