Source code for tryalgo.skip_list

# -*- coding: utf-8 -*-
"""\
skip-list
louis abraham - 2017-2019

Inspired by https://kunigami.blog/2012/09/25/skip-lists-in-python/
count contains the gap between the positions
(https://www.cs.bgu.ac.il/~ds112/wiki.files/ds112_ps7.pdf)
"""
# pylint: disable=line-too-long, missing-docstring, redefined-outer-name
# pylint: disable=fixme, super-init-not-called, notimplemented-raised
# pylint: disable=raising-bad-type, no-member, line-too-long
# pylint: disable=self-cls-assignment, no-else-raise

from __future__ import print_function
from collections import namedtuple
from random import random


# TODO: add order_of_key

[docs]class AbstractSkipList(): def __init__(self): raise NotImplemented def __getattr__(self, k): return getattr(self.head, k) def __iter__(self): """Iterable in ascending order""" if not self.next: return self = self.next[0] while self is not None: yield self.key self = self.next[0] def __len__(self): return self._len def __bool__(self): return bool(len(self)) def __contains__(self, key): return self.find(key) is not None def _updateList(self, key): heigh = len(self.next) update = [None] * heigh count = [0] * heigh c = -1 x = self for i in reversed(range(heigh)): while x.next[i] is not None and x.next[i].key < key: c += x.count[i] x = x.next[i] update[i] = x count[i] = c return update, count
[docs] def getkth(self, k): "starts from 0" if k >= len(self): raise IndexError k += 1 # self has index -1 h = len(self.next) - 1 x = self while k: while x.next[h] is None or x.count[h] > k: h -= 1 k -= x.count[h] x = x.next[h] return x.key
[docs] def nextNode(self, key, update=None): if update is None: update = self._updateList(key)[0] if update: ans = update[0].next[0] if ans is not None: return ans return None
[docs] def nextKey(self, key): """nextKey(key) >= key""" ans = self.nextNode(key) return (ans.key if ans is not None else None)
[docs] def lastKey(self, key): """lastKey(key) < key""" update = self._updateList(key)[0] return (update[0].key if update else None)
[docs] def find(self, key, update=None): ans = self.nextNode(key, update) return (ans if ans is not None and ans.key == key else None)
[docs] def insert(self, node): # nup = len(self.next) while len(self.next) < len(node.next): self.next.append(None) self.count.append(self._len) update, index = self._updateList(node.key) # print(index) # for i in range(nup, len(self.count)): # self.count[i] += 1 nindex = index[0] + 1 if self.find(node.key, update) is None: self._len += 1 for i in range(len(node.next)): node.next[i] = update[i].next[i] update[i].next[i] = node node.count[i] = index[i] + update[i].count[i] + 1 - nindex update[i].count[i] = nindex - index[i] for i in range(len(node.next), len(update)): update[i].count[i] += 1
[docs] def remove(self, key): update = self._updateList(key)[0] node = self.find(key, update) if node is None: raise KeyError self._len -= 1 for i in range(len(node.next)): update[i].next[i] = node.next[i] update[i].count[i] += node.count[i] - 1 for i in range(len(node.next), len(update)): update[i].count[i] -= 1
[docs] @staticmethod def randomHeight(): p = 2 r = p * random() ans = 1 while r < 1: r = r * p ans += 1 return ans
[docs]class SortedSet(AbstractSkipList): Node = namedtuple('Node', 'key next count') def __init__(self, iterable=()): self.head = self.Node(None, [], []) self._len = 0 for i in iterable: self.add(i)
[docs] def pop(self): """Pops the first element""" try: x = next(iter(self)) self.remove(x) return x except StopIteration: raise KeyError('pop from an empty set')
# raise KeyError('pop from an empty set') from None
[docs] def add(self, key): height = self.randomHeight() self.insert(self.Node(key, [None] * height, [0] * height))
def __repr__(self): return '{%s}' % (', '.join(map(str, iter(self))))
[docs]class SortedDict(AbstractSkipList): Node = namedtuple('Node', 'key val next count') def __init__(self, iterable=()): self.head = self.Node(None, None, [], []) self._len = 0 if hasattr(iterable, 'keys') and hasattr(iterable, '__getitem__'): for i in iterable.keys(): self[i] = iterable[i] else: for i, j in iterable: self[i] = j
[docs] def keys(self): return list(self)
def __getitem__(self, key): x = self.find(key) if x is None: raise KeyError else: return x.val def __setitem__(self, key, value): try: self.remove(key) except KeyError: pass height = self.randomHeight() self.insert(self.Node(key, value, [None] * height, [0] * height)) def __delitem__(self, key): self.remove(key) def __repr__(self): return '{%s}' % (', '.join('%s: %s' % (k, self[k]) for k in self))
if __name__ == '__main__': from random import sample def display(a): while a is not None: # if sys.version_info.major < 3: # print (a.key if a.key is not None else 'N') + ' | ', # else: print(a.key if a.key is not None else 'N', end=' | ') print(*('(%s, %s)' % (i.key if i is not None else 'N', c) for i, c in zip(a.next, a.count))) a = a.next[0] n = SortedSet() for i in sample(range(5), 5): n.add(i) display(n) print(n.getkth(0)) print("----------") for i in sample(range(5), 0): n.remove(i) display(n) print("----------")