Twisted Pair Development

The following code is my implementation of RLE in Python. I’ve included a method to modify values without having to decode the entire value.

Please note that this algorithm is inferior to the RLE with Positioning I posted about here.

'''
Created on 09/06/2011

@author: adam
'''

import itertools
import copy

# Code modified from
# http://www.builderau.com.au/program/python/soa/Run-length-encoding-in-Python/0,2000064084,339280649,00.htm
def encode( values ):
    return [ (len(list(group)), name) for name, group in itertools.groupby( values ) ]

def decode( rleValues ):
    return sum( [length * [item] for length, item in rleValues], [] )

def getValueAt( rleValues, index ):
    # iterate down the list until we
    # reach our requested length
    start = 0
    for group in rleValues:
        if \
            index >= start and \
            index < (start + group[ 0 ]):
            return group[ 1 ]
        start += group[ 0 ]

def setValueAt( rleValues, index, value ):
    start = 0
    groupIndex = 0
    for group in rleValues:
        if \
            index >= start and \
            index < (start + group[ 0 ]):
            break
        start += group[ 0 ]
        groupIndex += 1

    # to make this easier, lets expand the current group, previous, and next
    # we will modify the value, then run our encoder over it
    # get the groups from our encoded array
    startIndex = groupIndex - 1 if groupIndex > 0 else groupIndex
    endIndex = groupIndex + 1 if groupIndex < len(rleValues) else groupIndex

    # de-code the values from our subset
    values = sum( [length * [item] for length, item in rleValues[ startIndex : endIndex + 1]], [] )

    # determine our offset within the decoded values
    groupStart = start
    if startIndex < groupIndex:
        groupStart -= rleValues[ startIndex ][ 0 ]

    # write our new value into the appropriate location
    values[ index - groupStart ] = value

    # re-encode the groups
    encoded = encode( values )

    # re-insert the values back into the encoded list
    rleValues[ startIndex : endIndex + 1 ] = encoded

    return rleValues

This entry was posted on 2011/06/10 at 1:35 am and is filed under Development, How To, Programming with tags development, howto, python, voxel. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.