Yandex Maps Base64 encoding realization

# Copyright (C) 2010 Andrey Solomatin
#
# This program is free software; you can redistribute it and/or modify
# it under the terms of the GNU General Public License as published by
# the Free Software Foundation; either version 2 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License along
# with this program; if not, write to the Free Software Foundation, Inc.,
# 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

# -*- coding: UTF-8 -*-
from decimal import Decimal
import re

'http://api.yandex.ru/maps/jsapi/doc/dg/tasks/how-to-add-polyline.xml#encoding-polyline-points'

code_string = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_="

def to_bin(n):
    HexBin = {"0":"0000", "1":"0001", "2":"0010", "3":"0011", "4":"0100", "5":"0101", "6":"0110", "7":"0111", "8":"1000", "9":"1001", "A":"1010", "B":"1011", "C":"1100", "D":"1101", "E":"1110", "F":"1111"}
    res = "".join([HexBin[i] for i in '%X' % n]).lstrip('0')
    return res

# gets difference between coords
def _diff(coords, index):
    x1, y1 = coords[index + 1]
    x2, y2 = coords[index]
    return x1 - x2, y1 - y2

def _fromBit(line): # and revers
    eight = zip(*[iter(line)] * 8)[::-1]
    num = "".join(["".join(x) for x in eight])
    if num[0] == "0":
        res = int(num, 2)
    else:
        res = int(num, 2) - 4294967296
    return res

def _toBit(decim): # and revers
    """convert decimal to  bit   Fill it to 4 bytes (32 bits) and reverse bytes.
    Args:
    decim : Decimal number for convertation

    Return:
    String
    """
    n = int(decim)
    if n < 0:
        n += 4294967296
    n = to_bin(n)
    #HexBin ={"0":"0000", "1":"0001", "2":"0010", "3":"0011", "4":"0100", "5":"0101", "6":"0110", "7":"0111", "8":"1000", "9":"1001", "A":"1010", "B":"1011", "C":"1100", "D":"1101", "E":"1110", "F":"1111"}
    #n = "".join([HexBin[i] for i in '%X'%n]).lstrip('0')
    n = n.rjust(32, "0")
    n = re.findall("\d{8}", n)
    n.reverse()
    return str().join(n)

def encode_base64_yandex(tuple_of_coord_pairs):
    """Converts coordinates to string
    Keyword arguments:
    tuple_of_coord_pairs ((lat,lang),(lat,lang),...)
    Returns: string
    """

    coords = [(Decimal(str(x).strip()) * 10**6, Decimal(str(y).strip())*10 ** 6)for y, x in tuple_of_coord_pairs]
    if not coords: return ""
    new_coords = [coords[0]]
    if len(coords) is 1:
        line = str().join([_toBit(x) + _toBit(y) for x, y in new_coords])
    for index in range(len(coords) - 1):
        new_coords.append(_diff(coords, index))
        line = str().join([_toBit(x) + _toBit(y) for x, y in new_coords])
    ends = ""
    if len(line) % 6 == 2:
        ends = "=="
        line += "0000"
    elif len(line) % 6 == 4:
        ends = "="
        line += "00"
    return  str().join([code_string[int(x, 2)] for x in re.findall("\d{6}|\d{4}|\d{2}", line)]) + ends

def decode_base64_yandex(text):
    line = [to_bin(code_string.index(x)).rjust(6, "0") for x in text]
    line = "".join(line)
    line = zip(*[iter(line)] * 32)
    nums = [_fromBit("".join(x)) for x in line]
    if not nums:
        return []
    lats = nums[::2]
    longs = nums[1::2]
    last = [(lats[0], longs[0]), ]
    for ind in xrange(1, len(lats)):
        last.append((lats[ind] + last[ind - 1][0], longs[ind] + last[ind - 1][1]))
    last = [(Decimal(x[0]) / 10 ** 6, Decimal(x[1]) / 10 ** 6) for x in last]
    return [[str(y) for y in x[::-1]] for x in last]

if __name__ == "__main__":
    line = [
            ("37.593578", "55.735094"),
            ("37.592159", "55.732469"),
            ("37.589374","55.734162"),]


    a =  encode_base64_yandex(line)

    c = decode_base64_yandex(a)
    print c
    print line