LexoRank Python

lexoRank.py

import math


def _pad(s, n):
    p = _alphabet[0] * (n - len(s))
    return s + p


def _debase(s):
    val = 0
    for i, c in enumerate(reversed(s)):
        val += _alphabet.index(c) * (_n ** i)
    return val


def _enbase(val, length):
    res = ""
    while val or length > 0:
        res = _alphabet[val % _n] + res
        val //= _n
        length -= 1
    return res


def _average(s1, s2):
    n = max(len(s1), len(s2))
    v1, v2 = _debase(_pad(s1, n)), _debase(_pad(s2, n))
    v = (v1 + v2) // 2
    res = _enbase(v, n)
    return (res if v != v1 else res + _middle).rstrip("a")


class LexoList:

    def __init__(self):
        self.list = []

    def _used(self, pos):
        self.list.sort(key=lambda e: e.pos)
        if len(pos) >= _reindex_threshold:
            self._reindex()

    def _add(self, pos, val):
        elem = LexoElem(pos, val)
        self.list.append(elem)
        self._used(pos)
        return elem

    def _reindex(self):
        size = len(self.list) + 1  # +1 as "a" cannot be used
        length = math.ceil(math.log(size, _n))
        rate = (_n ** length) // size
        margin = (_n ** length - size * rate) // 2
        for i in range(len(self.list)):
            self.list[i].pos = _enbase(margin + rate * (i + 1), length)

    def _average_at(self, i):
        if not self.list:
            return _middle
        if i >= len(self.list):
            return _average(self.list[-1].pos, _alphabet[-1] * len(self.list[-1].pos))
        if i <= 0:
            return _average(_alphabet[0] * len(self.list[0].pos), self.list[0].pos)
        return _average(self.list[i - 1].pos, self.list[i].pos)

    def append(self, val):
        return self._add(self._average_at(len(self.list)), val)

    def insert(self, i, val):
        return self._add(self._average_at(i), val)

    def move(self, old, new):
        if old == new:
            return self.list[new]
        elem = self.list[old]
        elem.pos = self._average_at(new)
        self._used(elem.pos)
        return elem

    def __str__(self):
        m1 = math.ceil(math.log(len(self.list), 10))
        m2 = len(max(e.pos for e in self.list))
        return "\n".join(f"{i: ^{m1}} | {e.pos: <{m2}} -> {e.val}" for i, e in enumerate(self.list))


class LexoElem:

    def __init__(self, pos, val):
        self.pos = pos
        self.val = val


_alphabet = "abcdefghijklmnopqrstuvwxyz"
_n = len(_alphabet)
_middle = _average(_alphabet[0], _alphabet[-1])
_reindex_threshold = 50