# Path: cache-simulator/cache_model_evaluation/bintrees/abctree.py
# PYPY = hasattr(sys, 'pypy_version_info')
# class _ABCTree(object):
# class CPYTHON_ABCTree(_ABCTree):
# class PYPY_ABCTree(CPYTHON_ABCTree):
#     def __repr__(self):
#     def copy(self):
#     def __contains__(self, key):
#     def __len__(self):
#     def __min__(self):
#     def __max__(self):
#     def __and__(self, other):
#     def __or__(self, other):
#     def __sub__(self, other):
#     def __xor__(self, other):
#     def discard(self, key):
#     def is_empty(self):
#     def keys(self, reverse=False):
#     def __reversed__(self):
#     def values(self, reverse=False):
#     def items(self, reverse=False):
#     def __getitem__(self, key):
#     def __setitem__(self, key, value):
#     def __delitem__(self, key):
#     def remove_items(self, keys):
#     def key_slice(self, start_key, end_key, reverse=False):
#     def value_slice(self, start_key, end_key, reverse=False):
#     def item_slice(self, start_key, end_key, reverse=False):
#     def __getstate__(self):
#     def __setstate__(self, state):
#     def set_default(self, key, default=None):
#     def update(self, *args):
#     def from_keys(cls, iterable, value=None):
#     def get(self, key, default=None):
#     def pop(self, key, *args):
#     def prev_key(self, key):
#     def succ_key(self, key):
#     def floor_key(self, key):
#     def ceiling_key(self, key):
#     def pop_min(self):
#     def pop_max(self):
#     def min_key(self):
#     def max_key(self):
#     def nsmallest(self, n, pop=False):
#     def nlargest(self, n, pop=False):
#     def intersection(self, *trees):
#     def union(self, *trees):
#     def difference(self, *trees):
#     def symmetric_difference(self, tree):
#     def is_subset(self, tree):
#     def is_superset(self, tree):
#     def is_disjoint(self, tree):
# def _build_sets(trees):
# def _multi_tree_get(trees, key):
#     def __init__(self, items=None):
#     def clear(self):
#         def _clear(node):
#     def count(self):
#     def get_value(self, key):
#     def pop_item(self):
#     def foreach(self, func, order=0):
#         def _traverse(node):
#     def min_item(self):
#     def max_item(self):
#     def succ_item(self, key):
#     def prev_item(self, key):
#     def floor_item(self, key):
#     def ceiling_item(self, key):
#     def iter_items(self,  start_key=None, end_key=None, reverse=False):
#     def _iter_items_forward(self, start_key=None, end_key=None):
#     def _iter_items_backward(self, start_key=None, end_key=None):
#     def _iter_items(self, left=attrgetter("left"), right=attrgetter("right"), start_key=None, end_key=None):
#     def _get_in_range_func(self, start_key, end_key):
#     def iter_items(self, start_key=None, end_key=None, reverse=False):


from .abctree import ABCTree
from array import array
        """Remove all references."""
        self.left = None
        self.right = None
        self.key = None
        self.value = None


def height(node):
    return node.balance if node is not None else -1


def jsw_single(root, direction):
    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):
    other_side = 1 - direction
    root[other_side] = jsw_single(root[other_side], other_side)
    return jsw_single(root, direction)



# Path: cache-simulator/cache_model_evaluation/bintrees/abctree.py
# PYPY = hasattr(sys, 'pypy_version_info')
# class _ABCTree(object):
# class CPYTHON_ABCTree(_ABCTree):
# class PYPY_ABCTree(CPYTHON_ABCTree):
#     def __repr__(self):
#     def copy(self):
#     def __contains__(self, key):
#     def __len__(self):
#     def __min__(self):
#     def __max__(self):
#     def __and__(self, other):
#     def __or__(self, other):
#     def __sub__(self, other):
#     def __xor__(self, other):
#     def discard(self, key):
#     def is_empty(self):
#     def keys(self, reverse=False):
#     def __reversed__(self):
#     def values(self, reverse=False):
#     def items(self, reverse=False):
#     def __getitem__(self, key):
#     def __setitem__(self, key, value):
#     def __delitem__(self, key):
#     def remove_items(self, keys):
#     def key_slice(self, start_key, end_key, reverse=False):
#     def value_slice(self, start_key, end_key, reverse=False):
#     def item_slice(self, start_key, end_key, reverse=False):
#     def __getstate__(self):
#     def __setstate__(self, state):
#     def set_default(self, key, default=None):
#     def update(self, *args):
#     def from_keys(cls, iterable, value=None):
#     def get(self, key, default=None):
#     def pop(self, key, *args):
#     def prev_key(self, key):
#     def succ_key(self, key):
#     def floor_key(self, key):
#     def ceiling_key(self, key):
#     def pop_min(self):
#     def pop_max(self):
#     def min_key(self):
#     def max_key(self):
#     def nsmallest(self, n, pop=False):
#     def nlargest(self, n, pop=False):
#     def intersection(self, *trees):
#     def union(self, *trees):
#     def difference(self, *trees):
#     def symmetric_difference(self, tree):
#     def is_subset(self, tree):
#     def is_superset(self, tree):
#     def is_disjoint(self, tree):
# def _build_sets(trees):
# def _multi_tree_get(trees, key):
#     def __init__(self, items=None):
#     def clear(self):
#         def _clear(node):
#     def count(self):
#     def get_value(self, key):
#     def pop_item(self):
#     def foreach(self, func, order=0):
#         def _traverse(node):
#     def min_item(self):
#     def max_item(self):
#     def succ_item(self, key):
#     def prev_item(self, key):
#     def floor_item(self, key):
#     def ceiling_item(self, key):
#     def iter_items(self,  start_key=None, end_key=None, reverse=False):
#     def _iter_items_forward(self, start_key=None, end_key=None):
#     def _iter_items_backward(self, start_key=None, end_key=None):
#     def _iter_items(self, left=attrgetter("left"), right=attrgetter("right"), start_key=None, end_key=None):
#     def _get_in_range_func(self, start_key, end_key):
#     def iter_items(self, start_key=None, end_key=None, reverse=False):


# Path: cache-simulator/cache_model_evaluation/bintrees/avltree.py
from .abctree import ABCTree
from array import array

        """Remove all references."""
        self.left = None
        self.right = None
        self.key = None
        self.value = None


def height(node):
    return node.balance if node is not None else -1


def jsw_single(root, direction):
    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):
    other_side = 1 - direction
    root[other_side] = jsw_single(root[other_side], other_side)
    return jsw_single(root, direction)



class AVLTree(ABCTree):