shorturl.py

# coding=utf-8
from math import log2, ceil


# valid chars for a url path component: a-z A-Z 0-9 .-_~!$&'()*+,;=:@
# for the default set here (base 72) we have excluded $'();:@
radix_alphabet = sorted(
    "0123456789"
    "abcdefghijklmnopqrstuvwxyz"
    "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    ".-_~!&*+,="
)
radix = len(radix_alphabet)
reverse_radix = {ch: i for i, ch in enumerate(radix_alphabet)}
length_limit = ceil(128 / log2(radix))  # don't decode numbers much over 128 bits


def int_to_url(i):
    """Accepts an int and returns a url-compatible string representing it"""
    # map from signed int to positive int
    i *= 2
    if i < 0:
        i = -i - 1

    url = ""
    while i:
        i, digit = divmod(i, radix)
        url += radix_alphabet[digit]

    return url or radix_alphabet[0]


def url_to_int(url):
    """Accepts a string and extracts the int it represents in this radix encoding"""
    if not url or len(url) > length_limit:
        return None

    i = 0
    try:
        for ch in reversed(url):
            i = i * radix + reverse_radix[ch]
    except KeyError:
        return None

    # map from positive int to signed int
    sign = i & 1
    i >>= 1
    return -i - 1 if sign else i