#!/usr/bin/env python

# pylint: disable=too-many-lines,superfluous-parens
# too-many-lines: We're a rather complex sort of tree; we need a lot of lines
# superfluous-parens: parens are nice for clarity and portability

#coding:utf-8

'''
Author:  mozman (python version)
Purpose: avl tree module (Julienne Walker's unbounded none recursive algorithm)
source: http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx
Created: 01.05.2010
Copyright (C) 2010, 2011 by Manfred Moitzi
License: LGPLv3

Conclusion of Julienne Walker

AVL trees are about as close to optimal as balanced binary search trees can
get without eating up resources. You can rest assured that the O(log N)
performance of binary search trees is guaranteed with AVL trees, but the extra
bookkeeping required to maintain an AVL tree can be prohibitive, especially
if deletions are common. Insertion into an AVL tree only requires one single
or double rotation, but deletion could perform up to O(log N) rotations, as
in the example of a worst case AVL (ie. Fibonacci) tree. However, those cases
are rare, and still very fast.

AVL trees are best used when degenerate sequences are common, and there is
little or no locality of reference in nodes. That basically means that
searches are fairly random. If degenerate sequences are not common, but still
possible, and searches are random then a less rigid balanced tree such as red
black trees or Andersson trees are a better solution. If there is a significant
amount of locality to searches, such as a small cluster of commonly searched
items, a splay tree is theoretically better than all of the balanced trees
because of its move-to-front design.
'''

from __future__ import absolute_import

__all__ = ['AVL_tree']

import array
import functools

def my_range(top):
    '''A range() with consistent semantics for CPython 2.x and 3.x'''
    number = 0
    while number < top:
        yield number
        number += 1

class TreeSlice(object):
    '''A slice type for our AVL tree'''
    __slots__ = ['_tree', '_start', '_stop']
    def __init__(self, tree, start, stop):
        self._tree = tree
        self._start = start
        self._stop = stop

    def __repr__(self):
        tpl = "%s({%s})" % (self._tree.__class__.__name__, '%s')
        return tpl % ", ".join(("%r: %r" % item for item in self.items()))

    def __contains__(self, key):
        if self._inrange(key):
            return key in  self._tree
        else:
            return False

    def _inrange(self, key):
        '''Is key between self._start and self._stop?'''
        if self._start is not None and key < self._start:
            return False
        if self._stop is not None and key >= self._stop:
            return False
        return True

    def __getitem__(self, key):
        if isinstance(key, slice):
            return self._subslice(key.start, key.stop)
        if self._inrange(key):
            return self._tree[key]
        else:
            raise KeyError(key)

    def _subslice(self, start, stop):
        '''Slice a slice'''
        def newstart():
            '''New left edge'''
            if start is None:
                return self._start
            elif self._start is None:
                return start
            else:
                return max(start, self._start)
        def newstop():
            '''New right edge'''
            if stop is None:
                return self._stop
            elif self._stop is None:
                return stop
            else:
                return min(stop, self._stop)

        return TreeSlice(self._tree, newstart(), newstop())

    def keys(self):
        '''Return the keys in a slice'''
        return self._tree.keyslice(self._start, self._stop)
    __iter__ = keys

    def values(self):
        '''Return the values in a slice'''
        return self._tree.valueslice(self._start, self._stop)

    def items(self):
        '''Return the keys and values (as tuples) in a slice'''
        return self._tree.itemslice(self._start, self._stop)

class Walker(object):
    '''Walk over the nodes in a tree, among other things'''
    __slots__ = ['_node', '_stack', '_tree']

    def __init__(self, tree):
        self._tree = tree
        self._node = tree.root
        self._stack = []

    def reset(self):
        '''Start again at the beginning'''
        self._stack = []
        self._node = self._tree.root

    @property
    def key(self):
        '''Return the current node's key'''
        return self._node.key

    @property
    def value(self):
        '''Return the current node's value'''
        return self._node.value

    @property
    def item(self):
        '''Return the current node's key, value pair'''
        return (self._node.key, self._node.value)

    @property
    def is_valid(self):
        '''Is this a valid (non-None) node?'''
        return self._node is not None

    def goto(self, key):
        '''Hop to a node'''
        self._node = self._tree.root
        while self._node is not None:
            if key == self._node.key:
                return True
            elif key < self._node.key:
                self.go_left()
            else:
                self.go_right()
        return False

    def push(self):
        '''add a node to a stack'''
        self._stack.append(self._node)

    def pop(self):
        '''pop a node from a stack'''
        self._node = self._stack.pop()

    def stack_is_empty(self):
        '''Is the stack empty?'''
        return len(self._stack) == 0

    def goto_leaf(self):
        '''get a leaf node'''
        while self._node is not None:
            if self.has_left():
                self.go_left()
            elif self.has_right():
                self.go_right()
            else:
                return

    def has_child(self, direction):
        '''Do we have a (relevant) child node?'''
        if direction == 0:
            return self._node.left is not None
        else:
            return self._node.right is not None

    def down(self, direction):
        '''Go down'''
        if direction == 0:
            self._node = self._node.left
        else:
            self._node = self._node.right

    def go_left(self):
        '''Go left'''
        self._node = self._node.left

    def go_right(self):
        '''Go right'''
        self._node = self._node.right

    def has_left(self):
        '''Do we have a left child?'''
        return self._node.left is not None

    def has_right(self):
        '''Do we have a right child?'''
        return self._node.right is not None

    def succ_item(self, key):
        """ Get successor (k,v) pair of key, raises KeyError if key is max key
        or key does not exist.
        """
        node = self._tree.root
        succ = None
        while node is not None:
            if key == node.key:
                break
            elif key < node.key:
                if (succ is None) or (node.key < succ[0]):
                    succ = (node.key, node.value)
                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 is None:
                succ = (node.key, node.value)
            elif node.key < succ[0]:
                succ = (node.key, node.value)
        elif succ is None: # given key is biggest in tree
            raise KeyError(str(key))
        return succ

    def prev_item(self, key):
        """ Get predecessor (k,v) pair of key, raises KeyError if key is min key
        or key does not exist.
        """
        node = self._tree.root
        prev = None
        while self._node is not None:
            if key == node.key:
                break
            elif key < node.key:
                node = node.left
            else:
                if (prev is None) or (node.key > prev[0]):
                    prev = (node.key, node.value)
                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 is None:
                prev = (node.key, node.value)
            elif node.key > prev[0]:
                prev = (node.key, node.value)
        elif prev is None: # given key is smallest in tree
            raise KeyError(str(key))
        return prev

    def iteritemsforward(self):
        """ optimized forward iterator (reduced method calls) """
        if self._tree.is_empty():
            return
        node = self._tree.root
        stack = self._stack
        go_left = True
        while True:
            if node.left is not None and go_left:
                stack.append(node)
                node = node.left
            else:
                yield (node.key, node.value)
                if node.right is not None:
                    node = node.right
                    go_left = True
                else:
                    if len(stack) == 0:
                        return # all done
                    node = stack.pop()
                    go_left = False

    def iteritemsbackward(self):
        """ optimized backward iterator (reduced method calls) """
        if self._tree.is_empty():
            return
        node = self._tree.root
        stack = self._stack
        go_right = True
        while True:
            if node.right is not None and go_right:
                stack.append(node)
                node = node.right
            else:
                yield (node.key, node.value)
                if node.left is not None:
                    node = node.left
                    go_right = True
                else:
                    if len(stack) == 0:
                        return # all done
                    node = stack.pop()
                    go_right = False

class TreeMixin(object):
    # pylint: disable=R0904
    # R0904: We need a bunch of public methods...
    '''
    Abstract-Base-Class for the pure Python Trees: BinaryTree, AVLTree and RBTree
    Mixin-Class for the Cython based Trees: FastBinaryTree, FastAVLTree, FastRBTree

    The TreeMixin Class
    ===================

    T has to implement following properties
    ---------------------------------------

    count -- get node count

    T has to implement following methods
    ------------------------------------

    get_walker(...)
        get a tree walker object, provides methods to traverse the tree see walker.py

    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.

    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))
    * clear() -> None, Remove all items from T, , O(n)
    * 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)
    * items([reverse]) -> generator for (k, v) items of T, O(n)
    * 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))
    * popitem() -> (k, v), remove and return some (key, value) pair as a 2-tuple, O(log(n))
    * setdefault(k[,d]) -> 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))
    * foreach(f, [order]) -> visit all nodes of tree and call f(k, v) for each node, O(n)

    slicing by keys

    * itemslice(s, e) -> generator for (k, v) items of T for s <= key < e, O(n)
    * keyslice(s, e) -> generator for keys of T for s <= key < e, O(n)
    * valueslice(s, e) -> generator for values 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_item(key) -> get (k, v) pair, where k is predecessor to key, O(log(n))
    * prev_key(key) -> k, get the predecessor of key, O(log(n))
    * succ_item(key) -> get (k,v) pair as a 2-tuple, where k is successor to key, O(log(n))
    * succ_key(key) -> k, get the successor of key, O(log(n))

    Heap methods

    * max_item() -> get largest (key, value) pair of T, O(log(n))
    * max_key() -> get largest key of T, O(log(n))
    * min_item() -> get smallest (key, value) pair 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
    * issubset(S) -> True if every element in T is in S
    * issuperset(S) -> True if every element in S is in T
    * isdisjoint(S) ->  True if T has a null intersection with S

    Classmethods

    * fromkeys(S[,v]) -> New tree with keys from S and values equal to v.
    '''

    def __init__(self):
        '''Otherwise pylint complains that we're setting these outside __init__'''
        self._root = None
        self._count = 0

    def get_walker(self):
        '''get a tree walker object, provides methods to traverse the tree'''
        return Walker(self)

    def __repr__(self):
        """ x.__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 __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):
        """ x.__len__() <==> len(x) """
        return self.count

    def __min__(self):
        """ x.__min__() <==> min(x) """
        return self.min_item()

    def __max__(self):
        """ x.__max__() <==> max(x) """
        return self.max_item()

    def __and__(self, other):
        """ x.__and__(other) <==> self & other """
        return self.intersection(other)

    def __or__(self, other):
        """ x.__or__(other) <==> self | other """
        return self.union(other)

    def __sub__(self, other):
        """ x.__sub__(other) <==> self - other """
        return self.difference(other)

    def __xor__(self, other):
        """ x.__xor__(other) <==> self ^ other """
        return self.symmetric_difference(other)

    def discard(self, key):
        """ x.discard(k) -> None, remove k from T, if k is present """
        try:
            self.remove(key)
        except KeyError:
            pass

    def __del__(self):
        self.clear()

    def is_empty(self):
        """ x.is_empty() -> False if T contains any items else True"""
        return self.count == 0

    def keys(self, reverse=False):
        """ T.iterkeys([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.items(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.items(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
        """
        if self.is_empty():
            return []

        def default_iterator(node):
            '''An iteritems'''
            direction = 1 if reverse else 0
            other = 1 - direction
            go_down = True
            while True:
                if node.has_child(direction) and go_down:
                    node.push()
                    node.down(direction)
                else:
                    yield node.item
                    if node.has_child(other):
                        node.down(other)
                        go_down = True
                    else:
                        if node.stack_is_empty():
                            return # all done
                        node.pop()
                        go_down = False

        treewalker = self.get_walker()
        try: # specialized iterators
            if reverse:
                return treewalker.iteritemsbackward()
            else:
                return treewalker.iteritemsforward()
        except AttributeError:
            return default_iterator(treewalker)

    def __getitem__(self, key):
        '''x.__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):
        '''x.__setitem__(i, y) <==> x[i]=y'''
        if isinstance(key, slice):
            raise ValueError('setslice is not supported')
        self.insert(key, value)

    def __delitem__(self, key):
        '''x.__delitem__(y) <==> del x[y]'''
        if isinstance(key, slice):
            self.delitems(self.keyslice(key.start, key.stop))
        else:
            self.remove(key)

    def delitems(self, keys):
        '''
        T.delitems(keys) -> remove all items by keys
        '''
        # convert generator to a set, because the content of the
        # tree will be modified!
        for key in frozenset(keys):
            self.remove(key)

    def keyslice(self, startkey, endkey):
        '''
        T.keyslice(startkey, endkey) -> key iterator:
        startkey <= key < endkey.
        '''
        return (item[0] for item in self.itemslice(startkey, endkey))

    def itemslice(self, startkey, endkey):
        # pylint: disable=R0912
        # R0912: We just need quite a few branches in this case
        '''
        T.itemslice(s, e) -> item iterator: s <= key < e.

        if s is None: start with min element -> T[:e]
        if e is None: end with max element -> T[s:]
        T[:] -> all items
        '''
        if self.is_empty():
            return

        if startkey is None:
            # no lower bound
            can_go_left = lambda: node.has_left() and visit_left
        else:
            # don't visit subtrees without keys in search range
            can_go_left = lambda: node.key > startkey and node.has_left() and visit_left

        if endkey is None:
            # no upper bound
            #can_go_right = lambda: node.has_right()
            can_go_right = functools.partial(node.has_right)
        else:
            # don't visit subtrees without keys in search range
            can_go_right = lambda: node.key < endkey and node.has_right()

        if (startkey, endkey) == (None, None):
            key_in_range = lambda: True
        elif startkey is None:
            key_in_range = lambda: node.key < endkey
        elif endkey is None:
            key_in_range = lambda: node.key >= startkey
        else:
            key_in_range = lambda: startkey <= node.key < endkey

        node = self.get_walker()
        visit_left = True
        while True:
            if can_go_left():
                node.push()
                node.go_left()
            else:
                if key_in_range():
                    yield node.item
                if can_go_right():
                    node.go_right()
                    visit_left = True
                else:
                    if node.stack_is_empty():
                        return
                    node.pop()
                    # left side is already done
                    visit_left = False

    def valueslice(self, startkey, endkey):
        '''
        T.valueslice(startkey, endkey) -> value iterator:
        startkey <= key < endkey.
        '''
        return (item[1] for item in self.itemslice(startkey, endkey))

    def get_value(self, key):
        '''Look up a value by its 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 __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 setdefault(self, key, default=None):
        '''T.setdefault(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

    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 fromkeys(cls, iterable, value=None):
        '''
        T.fromkeys(S[,v]) -> New tree with keys from S and values equal to v.

        v defaults to None.
        '''
        tree = cls()
        for key in iterable:
            tree.insert(key, value)
        return tree

    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 popitem(self):
        '''
        T.popitem() -> (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("popitem(): tree is empty")
        walker = self.get_walker()
        walker.goto_leaf()
        result = walker.item
        self.remove(walker.key)
        return result

    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
        '''
        def _traverse():
            '''Traverse the tree'''
            if order == -1:
                func(node.key, node.value)
            if node.has_left():
                node.push()
                node.go_left()
                _traverse()
                node.pop()
            if order == 0:
                func(node.key, node.value)
            if node.has_right():
                node.push()
                node.go_right()
                _traverse()
                node.pop()
            if order == +1:
                func(node.key, node.value)

        node = self.get_walker()
        _traverse()

    def min_item(self):
        '''
        Get item with min key of tree, raises ValueError if tree is empty.
        '''
        if self.count == 0:
            raise ValueError("Tree is empty")
        node = self._root
        while node.left is not None:
            node = node.left
        return (node.key, node.value)

    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 min_key(self):
        '''Get min key of tree, raises ValueError if tree is empty.'''
        key, value = self.min_item()
        dummy = value
        return key

    def prev_item(self, key):
        '''
        Get predecessor (k,v) pair of key, raises KeyError if key is min key
        or key does not exist.
        '''
        if self.count == 0:
            raise KeyError("Tree is empty")
        walker = self.get_walker()
        return walker.prev_item(key)

    def succ_item(self, key):
        '''
        Get successor (k,v) pair of key, raises KeyError if key is max key
        or key does not exist.
        '''
        if self.count == 0:
            raise KeyError("Tree is empty")
        walker = self.get_walker()
        return walker.succ_item(key)

    def prev_key(self, key):
        '''
        Get predecessor to key, raises KeyError if key is min key
        or key does not exist.
        '''
        key = self.prev_item(key)
        return key

    def succ_key(self, key):
        '''
        Get successor to key, raises KeyError if key is max key
        or key does not exist.
        '''
        key = self.succ_item(key)
        return key

    def max_item(self):
        '''Get item with max key of tree, raises ValueError if tree is empty.'''
        if self.count == 0:
            raise ValueError("Tree is empty")
        node = self._root
        while node.right is not None:
            node = node.right
        return (node.key, node.value)

    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 max_key(self):
        '''Get max key of tree, raises ValueError if tree is empty.'''
        key, value = self.max_item()
        dummy = value
        return key

    def nsmallest(self, num_smallest, pop=False):
        '''
        T.nsmallest(num_smallest) -> get list of num_smallest smallest items (k, v).
        If pop is True, remove items from T.
        '''
        if pop:
            #return [self.pop_min() for _ in range(min(len(self), num_smallest))]
            for dummy in range(min(len(self), num_smallest)):
                yield self.pop_min()
        else:
            items = list(self.items())
            #return  [ next(items) for _ in range(min(len(self), num_smallest)) ]
            for smallestno in my_range(num_smallest):
                yield items[smallestno]

    def nlargest(self, num_largest, pop=False):
        '''
        T.nlargest(num_largest) -> get list of num_largest largest items (k, v).
        If pop is True remove items from T.
        '''
        if pop:
            #return [self.pop_max() for _ in range(min(len(self), num_largest))]
            for dummy in range(min(len(self), num_largest)):
                yield self.pop_max()
        else:
            items = list(self.items(reverse=True))
            #return [ next(items) for _ in range(min(len(self), num_largest)) ]
            for largestno in my_range(num_largest):
                yield items[largestno]

    def intersection(self, *trees):
        # pylint: disable=too-many-function-args
        '''
        x.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):
        # pylint: disable=too-many-function-args
        '''
        x.union(t1, t2, ...) -> Tree with keys from *either* trees
        '''
        thiskeys = frozenset(self.keys())
        rkeys = thiskeys.union(*_build_sets(trees))
        return self.__class__(((key, self.get(key)) for key in rkeys))

    def difference(self, *trees):
        # pylint: disable=too-many-function-args
        '''
        x.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):
        # pylint: disable=too-many-function-args
        ''' x.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()))
        return self.__class__(((key, self.get(key)) for key in rkeys))

    def issubset(self, tree):
        ''' x.issubset(tree) -> True if every element in x is in tree '''
        thiskeys = frozenset(self.keys())
        return thiskeys.issubset(frozenset(tree.keys()))

    def issuperset(self, tree):
        ''' x.issubset(tree) -> True if every element in tree is in x '''
        thiskeys = frozenset(self.keys())
        return thiskeys.issuperset(frozenset(tree.keys()))

    def isdisjoint(self, tree):
        ''' x.isdisjoint(S) ->  True if x has a null intersection with tree '''
        thiskeys = frozenset(self.keys())
        treekeys = frozenset(tree.keys())
        if thiskeys & treekeys:
            return False
        else:
            return True
        #return thiskeys.isdisjoint(frozenset(tree.keys()))

def _build_sets(trees):
    '''Build a frozenset from our trees' keys'''
    return [frozenset(tree.keys()) for tree in trees]


MAXSTACK = 32

class Node(object):
    # pylint: disable=R0903
    # R0903: We don't need a lot of public methods
    '''Internal object, represents a treenode'''
    __slots__ = ['left', 'right', 'balance', 'key', 'value']
    def __init__(self, key=None, value=None):
        self.left = None
        self.right = None
        self.key = key
        self.value = value
        self.balance = 0

    def __getitem__(self, key):
        """ x.__getitem__(key) <==> x[key], where key is 0 (left) or 1 (right) """
        return self.left if key == 0 else self.right

    def __setitem__(self, key, value):
        """ x.__setitem__(key, value) <==> x[key]=value, where key is 0 (left) or 1 (right) """
        if key == 0:
            self.left = value
        else:
            self.right = value

    def free(self):
        """Remove all references."""
        self.left = None
        self.right = None
        self.key = None
        self.value = None

def height(node):
    '''Find the height of a node'''
    return node.balance if node is not None else -1

def jsw_single(root, direction):
    '''I'm afraid I have no idea what this is'''
    other_side = 1 - direction
    save = root[other_side]
    root[other_side] = save[direction]
    save[direction] = root
    rlh = height(root.left)
    rrh = height(root.right)
    slh = height(save[other_side])
    root.balance = max(rlh, rrh) + 1
    save.balance = max(slh, root.balance) + 1
    return save

def jsw_double(root, direction):
    '''I'm afraid I have no idea what this is'''
    other_side = 1 - direction
    root[other_side] = jsw_single(root[other_side], other_side)
    return jsw_single(root, direction)


class AVL_tree(TreeMixin):
    # pylint: disable=R0904
    # R0904: We need several public methods...
    '''
    AVLTree implements a balanced binary tree with a dict-like interface.

    see: http://en.wikipedia.org/wiki/AVL_tree

    In computer science, an AVL tree is a self-balancing binary search tree, and
    it is the first such data structure to be invented. In an AVL tree, the
    heights of the two child subtrees of any node differ by at most one;
    therefore, it is also said to be height-balanced. Lookup, insertion, and
    deletion all take O(log n) time in both the average and worst cases, where n
    is the number of nodes in the tree prior to the operation. Insertions and
    deletions may require the tree to be rebalanced by one or more tree rotations.

    The AVL tree is named after its two inventors, G.M. Adelson-Velskii and E.M.
    Landis, who published it in their 1962 paper "An algorithm for the
    organization of information."

    AVLTree() -> new empty tree.
    AVLTree(mapping) -> new tree initialized from a mapping
    AVLTree(seq) -> new tree initialized from seq [(k1, v1), (k2, v2), ... (kn, vn)]

    see also TreeMixin() class.
    '''
    def __init__(self, items=None):
        ''' x.__init__(...) initializes x; see x.__class__.__doc__ for signature '''
        TreeMixin.__init__(self)
        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):
            '''Recursively clear an AVL tree'''
            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):
        """ count of items """
        return self._count

    @property
    def root(self):
        """ root node of T """
        return self._root

    def _new_node(self, key, value):
        """ Create a new treenode """
        self._count += 1
        return Node(key, value)

    def insert(self, key, value):
        """ T.insert(key, value) <==> T[key] = value, insert key, value into Tree """
        if self._root is None:
            self._root = self._new_node(key, value)
        else:
            node_stack = [] # node stack
            dir_stack = array.array('I') # direction stack
            done = False
            top = 0
            node = self._root
            # search for an empty link, save path
            while True:
                if key == node.key: # update existing item
                    node.value = value
                    return
                direction = 1 if key > node.key else 0
                dir_stack.append(direction)
                node_stack.append(node)
                if node[direction] is None:
                    break
                node = node[direction]

            # Insert a new node at the bottom of the tree
            node[direction] = self._new_node(key, value)

            # Walk back up the search path
            top = len(node_stack) - 1
            while (top >= 0) and not done:
                direction = dir_stack[top]
                other_side = 1 - direction
                topnode = node_stack[top]
                left_height = height(topnode[direction])
                right_height = height(topnode[other_side])

                # Terminate or rebalance as necessary */
                if (left_height-right_height == 0):
                    done = True
                if (left_height-right_height >= 2):
                    branch_a = topnode[direction][direction]
                    branch_b = topnode[direction][other_side]

                    if height(branch_a) >= height(branch_b):
                        node_stack[top] = jsw_single(topnode, other_side)
                    else:
                        node_stack[top] = jsw_double(topnode, other_side)

                    # Fix parent
                    if top != 0:
                        node_stack[top-1][dir_stack[top-1]] = node_stack[top]
                    else:
                        self._root = node_stack[0]
                    done = True

                # Update balance factors
                topnode = node_stack[top]
                left_height = height(topnode[direction])
                right_height = height(topnode[other_side])

                topnode.balance = max(left_height, right_height) + 1
                top -= 1

    def remove(self, key):
        # pylint: disable=R0914,R0912,R0915
        # R0914: This is a complex operation, that needs some locals
        # R0912: We need several branches...
        # R0915: We need several statements...
        '''
        T.remove(key) <==> del T[key], remove item <key> from tree
        '''
        if self._root is None:
            raise KeyError(str(key))
        else:
            node_stack = [None] * MAXSTACK # node stack
            dir_stack = array.array('I', [0] * MAXSTACK) # direction stack
            top = 0
            node = self._root

            while True:
                # Terminate if not found
                if node is None:
                    raise KeyError(str(key))
                elif node.key == key:
                    break

                # Push direction and node onto stack
                direction = 1 if key > node.key else 0
                dir_stack[top] = direction

                node_stack[top] = node
                node = node[direction]
                top += 1

            # Remove the node
            if (node.left is None) or (node.right is None):
                # Which child is not null?
                direction = 1 if node.left is None else 0

                # Fix parent
                if top != 0:
                    node_stack[top-1][dir_stack[top-1]] = node[direction]
                else:
                    self._root = node[direction]
                node.free()
                self._count -= 1
            else:
                # Find the inorder successor
                heir = node.right

                # Save the path
                dir_stack[top] = 1
                node_stack[top] = node
                top += 1

                while (heir.left is not None):
                    dir_stack[top] = 0
                    node_stack[top] = heir
                    top += 1
                    heir = heir.left

                # Swap data
                node.key = heir.key
                node.value = heir.value

                # Unlink successor and fix parent
                xdir = 1 if node_stack[top-1].key == node.key else 0
                node_stack[top-1][xdir] = heir.right
                heir.free()
                self._count -= 1

            # Walk back up the search path
            top -= 1
            while top >= 0:
                direction = dir_stack[top]
                other_side = 1 - direction
                topnode = node_stack[top]
                left_height = height(topnode[direction])
                right_height = height(topnode[other_side])
                b_max = max(left_height, right_height)

                # Update balance factors
                topnode.balance = b_max + 1

                # Terminate or rebalance as necessary
                if (left_height - right_height) == -1:
                    break
                if (left_height - right_height) <= -2:
                    branch_a = topnode[other_side][direction]
                    branch_b = topnode[other_side][other_side]
                    if height(branch_a) <= height(branch_b):
                        node_stack[top] = jsw_single(topnode, direction)
                    else:
                        node_stack[top] = jsw_double(topnode, direction)
                    # Fix parent
                    if top != 0:
                        node_stack[top-1][dir_stack[top-1]] = node_stack[top]
                    else:
                        self._root = node_stack[0]
                top -= 1