Mercurial > kallithea
view rhodecode/lib/oset.py @ 1585:56276c716599 beta
Remove dead code
author | Nicolas VINOT <aeris@imirhil.fr> |
---|---|
date | Sat, 01 Oct 2011 16:38:51 +0200 |
parents | 37625d304a16 |
children |
line wrap: on
line source
KEY, PREV, NEXT = range(3) import collections class OrderedSet(collections.MutableSet): def __init__(self, iterable=None): self.end = end = [] end += [None, end, end] # sentinel node for doubly linked list self.map = {} # key --> [key, prev, next] if iterable is not None: self |= iterable def __len__(self): return len(self.map) def __contains__(self, key): return key in self.map def add(self, key): if key not in self.map: end = self.end curr = end[PREV] curr[NEXT] = end[PREV] = self.map[key] = [key, curr, end] def discard(self, key): if key in self.map: key, prev, next = self.map.pop(key) prev[NEXT] = next next[PREV] = prev def __iter__(self): end = self.end curr = end[NEXT] while curr is not end: yield curr[KEY] curr = curr[NEXT] def __reversed__(self): end = self.end curr = end[PREV] while curr is not end: yield curr[KEY] curr = curr[PREV] def pop(self, last=True): if not self: raise KeyError('set is empty') key = next(reversed(self)) if last else next(iter(self)) self.discard(key) return key def __repr__(self): if not self: return '%s()' % (self.__class__.__name__,) return '%s(%r)' % (self.__class__.__name__, list(self)) def __eq__(self, other): if isinstance(other, OrderedSet): return len(self) == len(other) and list(self) == list(other) return set(self) == set(other) def __del__(self): self.clear() # remove circular references