Last active
August 3, 2022 09:48
-
-
Save gruvw/256ef27fbcbcd81fde175eff73c64434 to your computer and use it in GitHub Desktop.
LexoRank Python
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment