List Shifting

ID:195068
 
Jun 14 2007, 10:36 am (Edited on Jun 14 2007, 10:43 am)
 
//Title: List Shifting
//Credit to: Foomer
//Contributed by: Foomer

// List shifting causes the entire list to shift so that the item
// specified in the argument becomes the first item in the list,
// while the order of the list remains the same. Example:

// Original: A, B, C, D, E, F, G, H, I

// ListShift(list, list.Find("E"))

// List Now: E, F, G, H, I, A, B, C, D

// This could be used if you want to work your way through a list
// of objects one at a time, but you always have to find out what
// the current 'next' object in the list is, including checking
// to see if the current object is the last object in the list.

proc/listshift(list/L, pos)
    if(!L) return
    if(pos == 1)
        return L // nothing to shift
    if(pos < 0 || pos > L.len)
        CRASH("Invalid position: [pos] of [L.len]")
    for(var/i=1, i<pos, i++)
        var/x = L[1]
        L -= L[1]
        L += x
    return L


// Sample Implementation:

var/list/testlist = list("A","B","C","D","E","F","G","H","I",)
mob/verb/TestListShift(position as num)
    world << "Test list shifted by [position]:"
    var/list/L = listshift(testlist, position)
    for(var/i in L)
        world << i

// Feel free to contribute a better version if you feel inclined to make one.
Aug 1 2007, 3:05 am
I generally like to use built-in procedures because they tend to go faster.
proc/listshift(var/list/L, var/pos)
    if(!L) return
    if(pos == 1) return L
    if(pos < 0)
        world.log << "listshift: pos less than L.len, adding L.len"
        pos += L.len
    else if(pos > L.len)
        world.log << "listshift: pos greater than L.len, subtracting L.len"
        pos -= L.len
    var/list/temp = L.Copy(pos, L.len+1)
    L.Cut(pos, L.len+1)
    L.Insert(1, temp)
    return L


I've enabled negative and greater-than-L.len positions for relative value. -1 will be the end, -2 will be second to last, etc...
Jun 17 2008, 2:28 pm
The main problem I have with both methods of this shown thus far is that they also modify the original list (in addition to returning the modified list). In other words, if you examine testlist after calling TestListShift(), you'll notice that it has been shifted.

My other issue is that I personally prefer to leave error-checking to the user, out of the implementation. Good documentation mentioning what valid inputs are should suffice in this case. For example, consider what yours essentially does in this case:
proc/ShiftSome(list/L, shiftCt=1)
    if(L && L.len)
        for(var/i in 1 to 10)
            L = listshift(L, 2)
            src << "First element: [L[1]]"


Given all of your error-checking, it essentially expands to this:
proc/ShiftSome(list/L, shiftCt=1)
    if(L && L.len)
        for(var/i in 1 to 10)
            if(!L) L = null
            if(2 == 1) L = L
            if(2 < 0 || 2 > L.len) CRASH()
            // ...

You'll notice that all 4 of those conditions will be redundantly checked for the 10 iterations of its calling, even though the second argument being passed (2) is constant
and qualifies, and the list is checked prior to the loop for validity so that it can be used in the output statement.

Here's how I would remake the proc, personally:
//Title: List Shifting (rev.)
//Credit to: Kuraudo
//Contributed by: Kuraudo
//Based from: List Shifting by Foomer


/*
Format:
    listshift(list, position)

Args:
    list: The list to shift
    position: The position to shift to the beginning.
    
Returns:
    A copy of list with the [position]th element as the first
    element, and wrapped to the end of the list.
*/

proc/listshift(list/L, pos)
    return L.Copy(pos) + L.Copy(1,pos)


///*
//Testing Code/Sample Implementation:

var/list/testlist = list("A","B","C","D","E","F","G","H","I",)
client/verb/TestListShift(position as num)
    if(position > 0 && position <= testlist.len)
        src << "Test list shifted to [position]\th element:"
        var/list/L = listshift(testlist, position)
        for(var/i in L)
            src << i
    else
        src << "[position] is out of bounds. Range: 1-[testlist.len]"


//*/
Jul 16 2008, 6:40 am
In response to Kuraudo
Kuraudo wrote:
proc/listshift(list/L, pos)
    return L.Copy(pos) + L.Copy(1,pos)


When I compare this to my own 'listshift' proc, I feel ashamed. How come I didn't think of this? Brilliant, thank you! :-)