You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
899 lines
31 KiB
899 lines
31 KiB
#!/usr/bin/env python
|
|
# coding:utf-8
|
|
# Author: Mozman
|
|
# Purpose: abstract base class for all binary trees
|
|
# Created: 03.05.2010
|
|
# Copyright (c) 2010-2013 by Manfred Moitzi
|
|
# License: MIT License
|
|
from __future__ import absolute_import
|
|
import sys
|
|
from .treeslice import TreeSlice
|
|
from operator import attrgetter
|
|
from copy import deepcopy
|
|
from abc import abstractmethod, abstractproperty
|
|
|
|
PYPY = hasattr(sys, 'pypy_version_info')
|
|
|
|
|
|
class _ABCTree(object):
|
|
"""
|
|
Abstract-Base-Class for ABCTree and Cython trees.
|
|
|
|
The _ABCTree Class
|
|
==================
|
|
|
|
T has to implement following properties
|
|
---------------------------------------
|
|
|
|
count -- get node count
|
|
|
|
T has to implement following methods
|
|
------------------------------------
|
|
|
|
get_value(...)
|
|
get_value(key) -> returns value for key
|
|
|
|
insert(...)
|
|
insert(key, value) <==> T[key] = value, insert key into T
|
|
|
|
remove(...)
|
|
remove(key) <==> del T[key], remove key from T
|
|
|
|
clear(...)
|
|
T.clear() -> None. Remove all items from T.
|
|
|
|
iter_items(...)
|
|
iter_items(s, e, [reverse]) -> iterate over all items with keys in range s <= key < e, yielding (k, v) tuple
|
|
|
|
foreach(...)
|
|
foreach(f, [order]) -> visit all nodes of tree and call f(k, v) for each node
|
|
|
|
pop_item(...)
|
|
T.pop_item() -> (k, v), remove and return some (key, value)
|
|
|
|
min_item(...)
|
|
min_item() -> get smallest (key, value) pair of T
|
|
|
|
max_item(...)
|
|
max_item() -> get largest (key, value) pair of T
|
|
|
|
prev_item(...)
|
|
prev_item(key) -> get (k, v) pair, where k is predecessor to key
|
|
|
|
succ_item(...)
|
|
succ_item(key) -> get (k,v) pair as a 2-tuple, where k is successor to key
|
|
|
|
floor_item(...)
|
|
floor_item(key) -> get (k, v) pair, where k is the greatest key less than or equal to key
|
|
|
|
ceiling_item(...)
|
|
ceiling_item(key) -> get (k, v) pair, where k is the smallest key greater than or equal to key
|
|
|
|
Methods defined here
|
|
--------------------
|
|
|
|
* __contains__(k) -> True if T has a key k, else False, O(log(n))
|
|
* __delitem__(y) <==> del T[y], del T[s:e], O(log(n))
|
|
* __getitem__(y) <==> T[y], T[s:e], O(log(n))
|
|
* __iter__() <==> iter(T)
|
|
* __len__() <==> len(T), O(1)
|
|
* __max__() <==> max(T), get max item (k,v) of T, O(log(n))
|
|
* __min__() <==> min(T), get min item (k,v) of T, O(log(n))
|
|
* __and__(other) <==> T & other, intersection
|
|
* __or__(other) <==> T | other, union
|
|
* __sub__(other) <==> T - other, difference
|
|
* __xor__(other) <==> T ^ other, symmetric_difference
|
|
* __repr__() <==> repr(T)
|
|
* __setitem__(k, v) <==> T[k] = v, O(log(n))
|
|
* __copy__() -> shallow copy support, copy.copy(T)
|
|
* __deepcopy__() -> deep copy support, copy.deepcopy(T)
|
|
* clear() -> None, remove all items from T, , O(n)
|
|
* remove_items(keys) -> None, remove items by keys
|
|
* copy() -> a shallow copy of T, O(n*log(n))
|
|
* discard(k) -> None, remove k from T, if k is present, O(log(n))
|
|
* get(k[,d]) -> T[k] if k in T, else d, O(log(n))
|
|
* is_empty() -> True if len(T) == 0, O(1)
|
|
* keys([reverse]) -> generator for keys of T, O(n)
|
|
* values([reverse]) -> generator for values of T, O(n)
|
|
* pop(k[,d]) -> v, remove specified key and return the corresponding value, O(log(n))
|
|
* set_default(k[,d]) -> value, T.get(k, d), also set T[k]=d if k not in T, O(log(n))
|
|
* update(E) -> None. Update T from dict/iterable E, O(E*log(n))
|
|
|
|
slicing by keys
|
|
|
|
* key_slice(s, e[, reverse]) -> generator for keys of T for s <= key < e, O(n)
|
|
* value_slice(s, e[, reverse]) -> generator for values of T for s <= key < e, O(n)
|
|
* item_slice(s, e[, reverse]) -> generator for items of T for s <= key < e, O(n)
|
|
* T[s:e] -> TreeSlice object, with keys in range s <= key < e, O(n)
|
|
* del T[s:e] -> remove items by key slicing, for s <= key < e, O(n)
|
|
|
|
if 's' is None or T[:e] TreeSlice/iterator starts with value of min_key()
|
|
if 'e' is None or T[s:] TreeSlice/iterator ends with value of max_key()
|
|
T[:] is a TreeSlice which represents the whole tree.
|
|
|
|
TreeSlice is a tree wrapper with range check and contains no references
|
|
to objects, deleting objects in the associated tree also deletes the object
|
|
in the TreeSlice.
|
|
|
|
* TreeSlice[k] -> get value for key k, raises KeyError if k not exists in range s:e
|
|
* TreeSlice[s1:e1] -> TreeSlice object, with keys in range s1 <= key < e1
|
|
|
|
* new lower bound is max(s, s1)
|
|
* new upper bound is min(e, e1)
|
|
|
|
TreeSlice methods:
|
|
|
|
* items() -> generator for (k, v) items of T, O(n)
|
|
* keys() -> generator for keys of T, O(n)
|
|
* values() -> generator for values of T, O(n)
|
|
* __iter__ <==> keys()
|
|
* __repr__ <==> repr(T)
|
|
* __contains__(key)-> True if TreeSlice has a key k, else False, O(log(n))
|
|
|
|
prev/succ operations
|
|
|
|
* prev_key(key) -> k, get the predecessor of key, O(log(n))
|
|
* succ_key(key) -> k, get the successor of key, O(log(n))
|
|
* floor_key(key) -> k, get the greatest key less than or equal to key, O(log(n))
|
|
* ceiling_key(key) -> k, get the smallest key greater than or equal to key, O(log(n))
|
|
|
|
Heap methods
|
|
|
|
* max_key() -> get largest key of T, O(log(n))
|
|
* min_key() -> get smallest key of T, O(log(n))
|
|
* pop_min() -> (k, v), remove item with minimum key, O(log(n))
|
|
* pop_max() -> (k, v), remove item with maximum key, O(log(n))
|
|
* nlargest(i[,pop]) -> get list of i largest items (k, v), O(i*log(n))
|
|
* nsmallest(i[,pop]) -> get list of i smallest items (k, v), O(i*log(n))
|
|
|
|
Set methods (using frozenset)
|
|
|
|
* intersection(t1, t2, ...) -> Tree with keys *common* to all trees
|
|
* union(t1, t2, ...) -> Tree with keys from *either* trees
|
|
* difference(t1, t2, ...) -> Tree with keys in T but not any of t1, t2, ...
|
|
* symmetric_difference(t1) -> Tree with keys in either T and t1 but not both
|
|
* is_subset(S) -> True if every element in T is in S
|
|
* is_superset(S) -> True if every element in S is in T
|
|
* is_disjoint(S) -> True if T has a null intersection with S
|
|
|
|
Classmethods
|
|
|
|
* from_keys(S[,v]) -> New tree with keys from S and values equal to v.
|
|
|
|
"""
|
|
|
|
@abstractmethod
|
|
def insert(self, key, value):
|
|
pass
|
|
|
|
@abstractmethod
|
|
def remove(self, key):
|
|
pass
|
|
|
|
@abstractmethod
|
|
def get_value(self, key):
|
|
pass
|
|
|
|
@abstractmethod
|
|
def min_item(self):
|
|
pass
|
|
|
|
@abstractmethod
|
|
def max_item(self):
|
|
pass
|
|
|
|
@abstractmethod
|
|
def prev_item(self):
|
|
pass
|
|
|
|
@abstractmethod
|
|
def succ_item(self):
|
|
pass
|
|
|
|
@abstractmethod
|
|
def floor_item(self):
|
|
pass
|
|
|
|
@abstractmethod
|
|
def ceiling_item(self):
|
|
pass
|
|
|
|
@abstractmethod
|
|
def iter_items(self, start_key=None, end_key=None, reverse=False):
|
|
return []
|
|
|
|
@abstractmethod
|
|
def foreach(self, func, order=0):
|
|
pass
|
|
|
|
@property
|
|
def count(self):
|
|
return 0
|
|
|
|
def __repr__(self):
|
|
"""T.__repr__(...) <==> repr(x)"""
|
|
tpl = "%s({%s})" % (self.__class__.__name__, '%s')
|
|
return tpl % ", ".join(("%r: %r" % item for item in self.items()))
|
|
|
|
def copy(self):
|
|
"""T.copy() -> get a shallow copy of T."""
|
|
tree = self.__class__()
|
|
self.foreach(tree.insert, order=-1)
|
|
return tree
|
|
|
|
__copy__ = copy
|
|
|
|
def __deepcopy__(self, memo):
|
|
"""copy.deepcopy(T) -> get a deep copy of T."""
|
|
|
|
def _deepcopy(key, value):
|
|
value_copy = deepcopy(value, memo)
|
|
tree.insert(key, value_copy)
|
|
|
|
tree = type(self)()
|
|
memo[id(self)] = tree
|
|
self.foreach(_deepcopy, order=-1)
|
|
return tree
|
|
|
|
def __contains__(self, key):
|
|
"""k in T -> True if T has a key k, else False"""
|
|
try:
|
|
self.get_value(key)
|
|
return True
|
|
except KeyError:
|
|
return False
|
|
|
|
def __len__(self):
|
|
"""T.__len__() <==> len(x)"""
|
|
return self.count
|
|
|
|
def __min__(self):
|
|
"""T.__min__() <==> min(x)"""
|
|
return self.min_item()
|
|
|
|
def __max__(self):
|
|
"""T.__max__() <==> max(x)"""
|
|
return self.max_item()
|
|
|
|
def __and__(self, other):
|
|
"""T.__and__(other) <==> self & other"""
|
|
return self.intersection(other)
|
|
|
|
def __or__(self, other):
|
|
"""T.__or__(other) <==> self | other"""
|
|
return self.union(other)
|
|
|
|
def __sub__(self, other):
|
|
"""T.__sub__(other) <==> self - other"""
|
|
return self.difference(other)
|
|
|
|
def __xor__(self, other):
|
|
"""T.__xor__(other) <==> self ^ other"""
|
|
return self.symmetric_difference(other)
|
|
|
|
def discard(self, key):
|
|
"""T.discard(k) -> None, remove k from T, if k is present"""
|
|
try:
|
|
self.remove(key)
|
|
except KeyError:
|
|
pass
|
|
|
|
def is_empty(self):
|
|
"""T.is_empty() -> False if T contains any items else True"""
|
|
return self.count == 0
|
|
|
|
def keys(self, reverse=False):
|
|
"""T.keys([reverse]) -> an iterator over the keys of T, in ascending
|
|
order if reverse is True, iterate in descending order, reverse defaults
|
|
to False
|
|
"""
|
|
return (item[0] for item in self.iter_items(reverse=reverse))
|
|
|
|
__iter__ = keys
|
|
|
|
def __reversed__(self):
|
|
return self.keys(reverse=True)
|
|
|
|
def values(self, reverse=False):
|
|
"""T.values([reverse]) -> an iterator over the values of T, in ascending order
|
|
if reverse is True, iterate in descending order, reverse defaults to False
|
|
"""
|
|
return (item[1] for item in self.iter_items(reverse=reverse))
|
|
|
|
def items(self, reverse=False):
|
|
"""T.items([reverse]) -> an iterator over the (key, value) items of T,
|
|
in ascending order if reverse is True, iterate in descending order,
|
|
reverse defaults to False
|
|
"""
|
|
return self.iter_items(reverse=reverse)
|
|
|
|
def __getitem__(self, key):
|
|
"""T.__getitem__(y) <==> x[y]"""
|
|
if isinstance(key, slice):
|
|
return TreeSlice(self, key.start, key.stop)
|
|
else:
|
|
return self.get_value(key)
|
|
|
|
def __setitem__(self, key, value):
|
|
"""T.__setitem__(i, y) <==> x[i]=y"""
|
|
if isinstance(key, slice):
|
|
raise ValueError('setslice is not supported')
|
|
self.insert(key, value)
|
|
|
|
def __delitem__(self, key):
|
|
"""T.__delitem__(y) <==> del x[y]"""
|
|
if isinstance(key, slice):
|
|
self.remove_items(self.key_slice(key.start, key.stop))
|
|
else:
|
|
self.remove(key)
|
|
|
|
def remove_items(self, keys):
|
|
"""T.remove_items(keys) -> None, remove items by keys"""
|
|
# convert generator to a tuple, because the content of the
|
|
# tree will be modified!
|
|
for key in tuple(keys):
|
|
self.remove(key)
|
|
|
|
def key_slice(self, start_key, end_key, reverse=False):
|
|
"""T.key_slice(start_key, end_key) -> key iterator:
|
|
start_key <= key < end_key.
|
|
|
|
Yields keys in ascending order if reverse is False else in descending order.
|
|
"""
|
|
return (k for k, v in self.iter_items(start_key, end_key, reverse=reverse))
|
|
|
|
def value_slice(self, start_key, end_key, reverse=False):
|
|
"""T.value_slice(start_key, end_key) -> value iterator:
|
|
start_key <= key < end_key.
|
|
|
|
Yields values in ascending key order if reverse is False else in descending key order.
|
|
"""
|
|
return (v for k, v in self.iter_items(start_key, end_key, reverse=reverse))
|
|
|
|
def item_slice(self, start_key, end_key, reverse=False):
|
|
"""T.item_slice(start_key, end_key) -> item iterator:
|
|
start_key <= key < end_key.
|
|
|
|
Yields items in ascending key order if reverse is False else in descending key order.
|
|
"""
|
|
return self.iter_items(start_key, end_key, reverse)
|
|
|
|
def __getstate__(self):
|
|
return dict(self.items())
|
|
|
|
def __setstate__(self, state):
|
|
# note for myself: this is called like __init__, so don't use clear()
|
|
# to remove existing data!
|
|
self._root = None
|
|
self._count = 0
|
|
self.update(state)
|
|
|
|
def set_default(self, key, default=None):
|
|
"""T.set_default(k[,d]) -> T.get(k,d), also set T[k]=d if k not in T"""
|
|
try:
|
|
return self.get_value(key)
|
|
except KeyError:
|
|
self.insert(key, default)
|
|
return default
|
|
|
|
setdefault = set_default # for compatibility to dict()
|
|
|
|
def update(self, *args):
|
|
"""T.update(E) -> None. Update T from E : for (k, v) in E: T[k] = v"""
|
|
for items in args:
|
|
try:
|
|
generator = items.items()
|
|
except AttributeError:
|
|
generator = iter(items)
|
|
|
|
for key, value in generator:
|
|
self.insert(key, value)
|
|
|
|
@classmethod
|
|
def from_keys(cls, iterable, value=None):
|
|
"""T.from_keys(S[,v]) -> New tree with keys from S and values equal to v."""
|
|
tree = cls()
|
|
for key in iterable:
|
|
tree.insert(key, value)
|
|
return tree
|
|
|
|
fromkeys = from_keys # for compatibility to dict()
|
|
|
|
def get(self, key, default=None):
|
|
"""T.get(k[,d]) -> T[k] if k in T, else d. d defaults to None."""
|
|
try:
|
|
return self.get_value(key)
|
|
except KeyError:
|
|
return default
|
|
|
|
def pop(self, key, *args):
|
|
"""T.pop(k[,d]) -> v, remove specified key and return the corresponding value.
|
|
If key is not found, d is returned if given, otherwise KeyError is raised
|
|
"""
|
|
if len(args) > 1:
|
|
raise TypeError("pop expected at most 2 arguments, got %d" % (1 + len(args)))
|
|
try:
|
|
value = self.get_value(key)
|
|
self.remove(key)
|
|
return value
|
|
except KeyError:
|
|
if len(args) == 0:
|
|
raise
|
|
else:
|
|
return args[0]
|
|
|
|
def prev_key(self, key):
|
|
"""Get predecessor to key, raises KeyError if key is min key
|
|
or key does not exist.
|
|
"""
|
|
return self.prev_item(key)[0]
|
|
|
|
def succ_key(self, key):
|
|
"""Get successor to key, raises KeyError if key is max key
|
|
or key does not exist.
|
|
"""
|
|
return self.succ_item(key)[0]
|
|
|
|
def floor_key(self, key):
|
|
"""Get the greatest key less than or equal to the given key, raises
|
|
KeyError if there is no such key.
|
|
"""
|
|
return self.floor_item(key)[0]
|
|
|
|
def ceiling_key(self, key):
|
|
"""Get the smallest key greater than or equal to the given key, raises
|
|
KeyError if there is no such key.
|
|
"""
|
|
return self.ceiling_item(key)[0]
|
|
|
|
def pop_min(self):
|
|
"""T.pop_min() -> (k, v), remove item with minimum key, raise ValueError
|
|
if T is empty.
|
|
"""
|
|
item = self.min_item()
|
|
self.remove(item[0])
|
|
return item
|
|
|
|
def pop_max(self):
|
|
"""T.pop_max() -> (k, v), remove item with maximum key, raise ValueError
|
|
if T is empty.
|
|
"""
|
|
item = self.max_item()
|
|
self.remove(item[0])
|
|
return item
|
|
|
|
def min_key(self):
|
|
"""Get min key of tree, raises ValueError if tree is empty. """
|
|
return self.min_item()[0]
|
|
|
|
def max_key(self):
|
|
"""Get max key of tree, raises ValueError if tree is empty. """
|
|
return self.max_item()[0]
|
|
|
|
def nsmallest(self, n, pop=False):
|
|
"""T.nsmallest(n) -> get list of n smallest items (k, v).
|
|
If pop is True, remove items from T.
|
|
"""
|
|
if pop:
|
|
return [self.pop_min() for _ in range(min(len(self), n))]
|
|
else:
|
|
items = self.items()
|
|
return [next(items) for _ in range(min(len(self), n))]
|
|
|
|
def nlargest(self, n, pop=False):
|
|
"""T.nlargest(n) -> get list of n largest items (k, v).
|
|
If pop is True remove items from T.
|
|
"""
|
|
if pop:
|
|
return [self.pop_max() for _ in range(min(len(self), n))]
|
|
else:
|
|
items = self.items(reverse=True)
|
|
return [next(items) for _ in range(min(len(self), n))]
|
|
|
|
def intersection(self, *trees):
|
|
"""T.intersection(t1, t2, ...) -> Tree, with keys *common* to all trees
|
|
"""
|
|
thiskeys = frozenset(self.keys())
|
|
sets = _build_sets(trees)
|
|
rkeys = thiskeys.intersection(*sets)
|
|
return self.__class__(((key, self.get(key)) for key in rkeys))
|
|
|
|
def union(self, *trees):
|
|
"""T.union(t1, t2, ...) -> Tree with keys from *either* trees
|
|
"""
|
|
thiskeys = frozenset(self.keys())
|
|
rkeys = thiskeys.union(*_build_sets(trees))
|
|
all_trees = [self]
|
|
all_trees.extend(trees)
|
|
return self.__class__(((key, _multi_tree_get(all_trees, key)) for key in rkeys))
|
|
|
|
def difference(self, *trees):
|
|
"""T.difference(t1, t2, ...) -> Tree with keys in T but not any of t1,
|
|
t2, ...
|
|
"""
|
|
thiskeys = frozenset(self.keys())
|
|
rkeys = thiskeys.difference(*_build_sets(trees))
|
|
return self.__class__(((key, self.get(key)) for key in rkeys))
|
|
|
|
def symmetric_difference(self, tree):
|
|
"""T.symmetric_difference(t1) -> Tree with keys in either T and t1 but
|
|
not both
|
|
"""
|
|
thiskeys = frozenset(self.keys())
|
|
rkeys = thiskeys.symmetric_difference(frozenset(tree.keys()))
|
|
all_trees = [self, tree]
|
|
return self.__class__(((key, _multi_tree_get(all_trees, key)) for key in rkeys))
|
|
|
|
def is_subset(self, tree):
|
|
"""T.issubset(tree) -> True if every element in x is in tree """
|
|
thiskeys = frozenset(self.keys())
|
|
return thiskeys.issubset(frozenset(tree.keys()))
|
|
|
|
issubset = is_subset # for compatibility to set()
|
|
|
|
def is_superset(self, tree):
|
|
"""T.issubset(tree) -> True if every element in tree is in x """
|
|
thiskeys = frozenset(self.keys())
|
|
return thiskeys.issuperset(frozenset(tree.keys()))
|
|
|
|
issuperset = is_superset # for compatibility to set()
|
|
|
|
def is_disjoint(self, tree):
|
|
"""T.isdisjoint(S) -> True if x has a null intersection with tree """
|
|
thiskeys = frozenset(self.keys())
|
|
return thiskeys.isdisjoint(frozenset(tree.keys()))
|
|
|
|
isdisjoint = is_disjoint # for compatibility to set()
|
|
|
|
|
|
def _build_sets(trees):
|
|
return [frozenset(tree.keys()) for tree in trees]
|
|
|
|
|
|
def _multi_tree_get(trees, key):
|
|
for tree in trees:
|
|
try:
|
|
return tree[key]
|
|
except KeyError:
|
|
pass
|
|
raise KeyError(key)
|
|
|
|
|
|
class CPYTHON_ABCTree(_ABCTree):
|
|
""" Base class for the Python implementation of trees.
|
|
|
|
T has to implement following methods
|
|
------------------------------------
|
|
|
|
insert(...)
|
|
insert(key, value) <==> T[key] = value, insert key into T
|
|
|
|
remove(...)
|
|
remove(key) <==> del T[key], remove key from T
|
|
|
|
Properties defined here
|
|
--------------------
|
|
|
|
* count -> get item count of tree
|
|
|
|
Methods defined here
|
|
--------------------
|
|
* __init__() Tree initializer
|
|
* get_value(key) -> returns value for key
|
|
* clear() -> None. Remove all items from tree.
|
|
* iter_items(start_key, end_key, [reverse]) -> iterate over all items, yielding (k, v) tuple
|
|
* foreach(f, [order]) -> visit all nodes of tree and call f(k, v) for each node, O(n)
|
|
* pop_item() -> (k, v), remove and return some (key, value)
|
|
* min_item() -> get smallest (key, value) pair of T, O(log(n))
|
|
* max_item() -> get largest (key, value) pair of T, O(log(n))
|
|
* prev_item(key) -> get (k, v) pair, where k is predecessor to key, O(log(n))
|
|
* succ_item(key) -> get (k,v) pair as a 2-tuple, where k is successor to key, O(log(n))
|
|
* floor_item(key) -> get (k, v) pair, where k is the greatest key less than or equal to key, O(log(n))
|
|
* ceiling_item(key) -> get (k, v) pair, where k is the smallest key greater than or equal to key, O(log(n))
|
|
"""
|
|
|
|
def __init__(self, items=None):
|
|
"""T.__init__(...) initializes T; see T.__class__.__doc__ for signature"""
|
|
self._root = None
|
|
self._count = 0
|
|
if items is not None:
|
|
self.update(items)
|
|
|
|
def clear(self):
|
|
"""T.clear() -> None. Remove all items from T."""
|
|
|
|
def _clear(node):
|
|
if node is not None:
|
|
_clear(node.left)
|
|
_clear(node.right)
|
|
node.free()
|
|
|
|
_clear(self._root)
|
|
self._count = 0
|
|
self._root = None
|
|
|
|
@property
|
|
def count(self):
|
|
"""Get items count."""
|
|
return self._count
|
|
|
|
def get_value(self, key):
|
|
node = self._root
|
|
while node is not None:
|
|
if key == node.key:
|
|
return node.value
|
|
elif key < node.key:
|
|
node = node.left
|
|
else:
|
|
node = node.right
|
|
raise KeyError(str(key))
|
|
|
|
def pop_item(self):
|
|
"""T.pop_item() -> (k, v), remove and return some (key, value) pair as a
|
|
2-tuple; but raise KeyError if T is empty.
|
|
"""
|
|
if self.is_empty():
|
|
raise KeyError("pop_item(): tree is empty")
|
|
node = self._root
|
|
while True:
|
|
if node.left is not None:
|
|
node = node.left
|
|
elif node.right is not None:
|
|
node = node.right
|
|
else:
|
|
break
|
|
key = node.key
|
|
value = node.value
|
|
self.remove(key)
|
|
return key, value
|
|
|
|
popitem = pop_item # for compatibility to dict()
|
|
|
|
def foreach(self, func, order=0):
|
|
"""Visit all tree nodes and process key, value.
|
|
|
|
parm func: function(key, value)
|
|
param int order: inorder = 0, preorder = -1, postorder = +1
|
|
"""
|
|
if self.count == 0:
|
|
return
|
|
|
|
def _traverse(node):
|
|
if order == -1:
|
|
func(node.key, node.value)
|
|
if node.left is not None:
|
|
_traverse(node.left)
|
|
if order == 0:
|
|
func(node.key, node.value)
|
|
if node.right is not None:
|
|
_traverse(node.right)
|
|
if order == +1:
|
|
func(node.key, node.value)
|
|
|
|
_traverse(self._root)
|
|
|
|
def min_item(self):
|
|
"""Get item with min key of tree, raises ValueError if tree is empty."""
|
|
if self.is_empty():
|
|
raise ValueError("Tree is empty")
|
|
node = self._root
|
|
while node.left is not None:
|
|
node = node.left
|
|
return node.key, node.value
|
|
|
|
def max_item(self):
|
|
"""Get item with max key of tree, raises ValueError if tree is empty."""
|
|
if self.is_empty():
|
|
raise ValueError("Tree is empty")
|
|
node = self._root
|
|
while node.right is not None:
|
|
node = node.right
|
|
return node.key, node.value
|
|
|
|
def succ_item(self, key):
|
|
"""Get successor (k,v) pair of key, raises KeyError if key is max key
|
|
or key does not exist. optimized for pypy.
|
|
"""
|
|
# removed graingets version, because it was little slower on CPython and much slower on pypy
|
|
# this version runs about 4x faster with pypy than the Cython version
|
|
# Note: Code sharing of succ_item() and ceiling_item() is possible, but has always a speed penalty.
|
|
node = self._root
|
|
succ_node = None
|
|
while node is not None:
|
|
if key == node.key:
|
|
break
|
|
elif key < node.key:
|
|
if (succ_node is None) or (node.key < succ_node.key):
|
|
succ_node = node
|
|
node = node.left
|
|
else:
|
|
node = node.right
|
|
|
|
if node is None: # stay at dead end
|
|
raise KeyError(str(key))
|
|
# found node of key
|
|
if node.right is not None:
|
|
# find smallest node of right subtree
|
|
node = node.right
|
|
while node.left is not None:
|
|
node = node.left
|
|
if succ_node is None:
|
|
succ_node = node
|
|
elif node.key < succ_node.key:
|
|
succ_node = node
|
|
elif succ_node is None: # given key is biggest in tree
|
|
raise KeyError(str(key))
|
|
return succ_node.key, succ_node.value
|
|
|
|
def prev_item(self, key):
|
|
"""Get predecessor (k,v) pair of key, raises KeyError if key is min key
|
|
or key does not exist. optimized for pypy.
|
|
"""
|
|
# removed graingets version, because it was little slower on CPython and much slower on pypy
|
|
# this version runs about 4x faster with pypy than the Cython version
|
|
# Note: Code sharing of prev_item() and floor_item() is possible, but has always a speed penalty.
|
|
node = self._root
|
|
prev_node = None
|
|
|
|
while node is not None:
|
|
if key == node.key:
|
|
break
|
|
elif key < node.key:
|
|
node = node.left
|
|
else:
|
|
if (prev_node is None) or (node.key > prev_node.key):
|
|
prev_node = node
|
|
node = node.right
|
|
|
|
if node is None: # stay at dead end (None)
|
|
raise KeyError(str(key))
|
|
# found node of key
|
|
if node.left is not None:
|
|
# find biggest node of left subtree
|
|
node = node.left
|
|
while node.right is not None:
|
|
node = node.right
|
|
if prev_node is None:
|
|
prev_node = node
|
|
elif node.key > prev_node.key:
|
|
prev_node = node
|
|
elif prev_node is None: # given key is smallest in tree
|
|
raise KeyError(str(key))
|
|
return prev_node.key, prev_node.value
|
|
|
|
def floor_item(self, key):
|
|
"""Get the element (k,v) pair associated with the greatest key less
|
|
than or equal to the given key, raises KeyError if there is no such key.
|
|
"""
|
|
# Note: Code sharing of prev_item() and floor_item() is possible, but has always a speed penalty.
|
|
node = self._root
|
|
prev_node = None
|
|
while node is not None:
|
|
if key == node.key:
|
|
return node.key, node.value
|
|
elif key < node.key:
|
|
node = node.left
|
|
else:
|
|
if (prev_node is None) or (node.key > prev_node.key):
|
|
prev_node = node
|
|
node = node.right
|
|
# node must be None here
|
|
if prev_node:
|
|
return prev_node.key, prev_node.value
|
|
raise KeyError(str(key))
|
|
|
|
def ceiling_item(self, key):
|
|
"""Get the element (k,v) pair associated with the smallest key greater
|
|
than or equal to the given key, raises KeyError if there is no such key.
|
|
"""
|
|
# Note: Code sharing of succ_item() and ceiling_item() is possible, but has always a speed penalty.
|
|
node = self._root
|
|
succ_node = None
|
|
while node is not None:
|
|
if key == node.key:
|
|
return node.key, node.value
|
|
elif key > node.key:
|
|
node = node.right
|
|
else:
|
|
if (succ_node is None) or (node.key < succ_node.key):
|
|
succ_node = node
|
|
node = node.left
|
|
# node must be None here
|
|
if succ_node:
|
|
return succ_node.key, succ_node.value
|
|
raise KeyError(str(key))
|
|
|
|
def iter_items(self, start_key=None, end_key=None, reverse=False):
|
|
"""Iterates over the (key, value) items of the associated tree,
|
|
in ascending order if reverse is True, iterate in descending order,
|
|
reverse defaults to False"""
|
|
# optimized iterator (reduced method calls) - faster on CPython but slower on pypy
|
|
|
|
if self.is_empty():
|
|
return []
|
|
if reverse:
|
|
return self._iter_items_backward(start_key, end_key)
|
|
else:
|
|
return self._iter_items_forward(start_key, end_key)
|
|
|
|
def _iter_items_forward(self, start_key=None, end_key=None):
|
|
for item in self._iter_items(left=attrgetter("left"), right=attrgetter("right"),
|
|
start_key=start_key, end_key=end_key):
|
|
yield item
|
|
|
|
def _iter_items_backward(self, start_key=None, end_key=None):
|
|
for item in self._iter_items(left=attrgetter("right"), right=attrgetter("left"),
|
|
start_key=start_key, end_key=end_key):
|
|
yield item
|
|
|
|
def _iter_items(self, left=attrgetter("left"), right=attrgetter("right"), start_key=None, end_key=None):
|
|
node = self._root
|
|
stack = []
|
|
go_left = True
|
|
in_range = self._get_in_range_func(start_key, end_key)
|
|
|
|
while True:
|
|
if left(node) is not None and go_left:
|
|
stack.append(node)
|
|
node = left(node)
|
|
else:
|
|
if in_range(node.key):
|
|
yield node.key, node.value
|
|
if right(node) is not None:
|
|
node = right(node)
|
|
go_left = True
|
|
else:
|
|
if not len(stack):
|
|
return # all done
|
|
node = stack.pop()
|
|
go_left = False
|
|
|
|
def _get_in_range_func(self, start_key, end_key):
|
|
if start_key is None and end_key is None:
|
|
return lambda x: True
|
|
else:
|
|
if start_key is None:
|
|
start_key = self.min_key()
|
|
if end_key is None:
|
|
return lambda x: x >= start_key
|
|
else:
|
|
return lambda x: start_key <= x < end_key
|
|
|
|
|
|
class PYPY_ABCTree(CPYTHON_ABCTree):
|
|
def iter_items(self, start_key=None, end_key=None, reverse=False):
|
|
"""Iterates over the (key, value) items of the associated tree,
|
|
in ascending order if reverse is True, iterate in descending order,
|
|
reverse defaults to False"""
|
|
# optimized for pypy, but slower on CPython
|
|
if self.is_empty():
|
|
return
|
|
direction = 1 if reverse else 0
|
|
other = 1 - direction
|
|
go_down = True
|
|
stack = []
|
|
node = self._root
|
|
in_range = self._get_in_range_func(start_key, end_key)
|
|
|
|
while True:
|
|
if node[direction] is not None and go_down:
|
|
stack.append(node)
|
|
node = node[direction]
|
|
else:
|
|
if in_range(node.key):
|
|
yield node.key, node.value
|
|
if node[other] is not None:
|
|
node = node[other]
|
|
go_down = True
|
|
else:
|
|
if not len(stack):
|
|
return # all done
|
|
node = stack.pop()
|
|
go_down = False
|
|
|
|
|
|
if PYPY:
|
|
ABCTree = PYPY_ABCTree
|
|
else:
|
|
ABCTree = CPYTHON_ABCTree
|