Google Polyline encoder & decoder

## gistfile1.py
'''Provides utility functions for encoding and decoding linestrings using the
Google encoded polyline algorithm.
'''

def encode_coords(coords):
    '''Encodes a polyline using Google's polyline algorithm

    See http://code.google.com/apis/maps/documentation/polylinealgorithm.html
    for more information.

    :param coords: Coordinates to transform (list of tuples in order: latitude,
    longitude).
    :type coords: list
    :returns: Google-encoded polyline string.
    :rtype: string
    '''

    result = []

    prev_lat = 0
    prev_lng = 0

    for x, y in coords:
        lat, lng = int(y * 1e5), int(x * 1e5)

        d_lat = _encode_value(lat - prev_lat)
        d_lng = _encode_value(lng - prev_lng)

        prev_lat, prev_lng = lat, lng

        result.append(d_lat)
        result.append(d_lng)

    return ''.join(c for r in result for c in r)

def _split_into_chunks(value):
    while value >= 32: #2^5, while there are at least 5 bits

        # first & with 2^5-1, zeros out all the bits other than the first five
        # then OR with 0x20 if another bit chunk follows
        yield (value & 31) | 0x20
        value >>= 5
    yield value

def _encode_value(value):
    # Step 2 & 4
    value = ~(value << 1) if value < 0 else (value << 1)

    # Step 5 - 8
    chunks = _split_into_chunks(value)

    # Step 9-10
    return (chr(chunk + 63) for chunk in chunks)

def decode(point_str):
    '''Decodes a polyline that has been encoded using Google's algorithm
    http://code.google.com/apis/maps/documentation/polylinealgorithm.html

    This is a generic method that returns a list of (latitude, longitude)
    tuples.

    :param point_str: Encoded polyline string.
    :type point_str: string
    :returns: List of 2-tuples where each tuple is (latitude, longitude)
    :rtype: list

    '''

    # sone coordinate offset is represented by 4 to 5 binary chunks
    coord_chunks = [[]]
    for char in point_str:

        # convert each character to decimal from ascii
        value = ord(char) - 63

        # values that have a chunk following have an extra 1 on the left
        split_after = not (value & 0x20)
        value &= 0x1F

        coord_chunks[-1].append(value)

        if split_after:
                coord_chunks.append([])

    del coord_chunks[-1]

    coords = []

    for coord_chunk in coord_chunks:
        coord = 0

        for i, chunk in enumerate(coord_chunk):
            coord |= chunk << (i * 5)

        #there is a 1 on the right if the coord is negative
        if coord & 0x1:
            coord = ~coord #invert
        coord >>= 1
        coord /= 100000.0

        coords.append(coord)

    # convert the 1 dimensional list to a 2 dimensional list and offsets to
    # actual values
    points = []
    prev_x = 0
    prev_y = 0
    for i in xrange(0, len(coords) - 1, 2):
        if coords[i] == 0 and coords[i + 1] == 0:
            continue

        prev_x += coords[i + 1]
        prev_y += coords[i]
        # a round to 6 digits ensures that the floats are the same as when
        # they were encoded
        points.append((round(prev_x, 6), round(prev_y, 6)))

    return points
	'''Provides utility functions for encoding and decoding linestrings using the
	Google encoded polyline algorithm.
	'''

	def encode_coords(coords):
	'''Encodes a polyline using Google's polyline algorithm

	See http://code.google.com/apis/maps/documentation/polylinealgorithm.html
	for more information.

	:param coords: Coordinates to transform (list of tuples in order: latitude,
	longitude).
	:type coords: list
	:returns: Google-encoded polyline string.
	:rtype: string
	'''

	result = []

	prev_lat = 0
	prev_lng = 0

	for x, y in coords:
	lat, lng = int(y * 1e5), int(x * 1e5)

	d_lat = _encode_value(lat - prev_lat)
	d_lng = _encode_value(lng - prev_lng)

	prev_lat, prev_lng = lat, lng

	result.append(d_lat)
	result.append(d_lng)

	return ''.join(c for r in result for c in r)

	def _split_into_chunks(value):
	while value >= 32: #2^5, while there are at least 5 bits

	# first & with 2^5-1, zeros out all the bits other than the first five
	# then OR with 0x20 if another bit chunk follows
	yield (value & 31) \| 0x20
	value >>= 5
	yield value

	def _encode_value(value):
	# Step 2 & 4
	value = ~(value << 1) if value < 0 else (value << 1)

	# Step 5 - 8
	chunks = _split_into_chunks(value)

	# Step 9-10
	return (chr(chunk + 63) for chunk in chunks)

	def decode(point_str):
	'''Decodes a polyline that has been encoded using Google's algorithm
	http://code.google.com/apis/maps/documentation/polylinealgorithm.html

	This is a generic method that returns a list of (latitude, longitude)
	tuples.

	:param point_str: Encoded polyline string.
	:type point_str: string
	:returns: List of 2-tuples where each tuple is (latitude, longitude)
	:rtype: list

	'''

	# sone coordinate offset is represented by 4 to 5 binary chunks
	coord_chunks = [[]]
	for char in point_str:

	# convert each character to decimal from ascii
	value = ord(char) - 63

	# values that have a chunk following have an extra 1 on the left
	split_after = not (value & 0x20)
	value &= 0x1F

	coord_chunks[-1].append(value)

	if split_after:
	coord_chunks.append([])

	del coord_chunks[-1]

	coords = []

	for coord_chunk in coord_chunks:
	coord = 0

	for i, chunk in enumerate(coord_chunk):
	coord \|= chunk << (i * 5)

	#there is a 1 on the right if the coord is negative
	if coord & 0x1:
	coord = ~coord #invert
	coord >>= 1
	coord /= 100000.0

	coords.append(coord)

	# convert the 1 dimensional list to a 2 dimensional list and offsets to
	# actual values
	points = []
	prev_x = 0
	prev_y = 0
	for i in xrange(0, len(coords) - 1, 2):
	if coords[i] == 0 and coords[i + 1] == 0:
	continue

	prev_x += coords[i + 1]
	prev_y += coords[i]
	# a round to 6 digits ensures that the floats are the same as when
	# they were encoded
	points.append((round(prev_x, 6), round(prev_y, 6)))

	return points