# splay ought to not be called on a placeholder node, 
# lest it become root
from ..OrderedBinarySearchTree import *
from ..Entry import *
class SplayTree(OrderedBinarySearchTree):
  def __init__(self, key_transform = lambda x: x, comparator = comp):
    # BinarySearchTree.__init__(self, key_transform, comparator)
    OrderedBinarySearchTree.__init__(self, key_transform, comparator)
  @staticmethod
  def construct(entries):
    tree = SplayTree()
    for entry in entries:
      key, value = entry
      tree.insert(key, value)
    return tree
  # return whether we have a non-placeholder node to splay
  def _oughtToSplay(self, action_node):
    return not (action_node.isExternal() and action_node == self.getRoot())
  # candidates include current node and ancestors; 
  #   we are interested in the closest such node
  # if there is no non-placeholder node among these candidates, 
  #   return None
  def _getNodeToSplayGivenActionNode(self, action_node):
    return self._getNodeToSplayGivenActionNodeHelper(action_node)
  def _getNodeToSplayGivenActionNodeHelper(self, node):
    if not node.isExternal():
      return node
    else:
      if node == self.getRoot():
        return None
      else:
        return self._getNodeToSplayGivenActionNodeHelper(node.getParent())
  def _splayGivenActionNode(self, node):
    if self._oughtToSplay(node) == True:
      node_to_splay = self._getNodeToSplayGivenActionNode(node)
      self._splay(node_to_splay)
  def _splay(self, x):
    # if is left child of a left child, or right child of a right child
    # if is left child of a right child, or right child of a left child
    # if does not have a grandparent
    # print "splaying"
    parent = x.getParent()
    if parent == None:
      return
    grandparent = parent.getParent()
    if grandparent == None:
      self._zig(x)
    elif (x.isLeftChild() and parent.isLeftChild()) \
      or (x.isRightChild() and parent.isRightChild()):
      self._zig_zig(x)
    elif (x.isLeftChild() and parent.isRightChild()) \
      or (x.isRightChild() and parent.isLeftChild()):
      self._zig_zag(x)
    self._splay(x)
  def _zig_zig(self, x):
    # print "zig-zig"
    # x, y, z
    # replace z by x
    # make x have y as a child
    # make y have z as a child
    y = x.getParent()
    z = y.getParent()
    z_parent = z.getParent()
    z_has_parent = z.hasParent()
    if x.isLeftChild() == True:
      # print "left, left"
      # left, left
      t1 = x.getLeftChild()
      t2 = x.getRightChild()
      t3 = y.getRightChild()
      t4 = z.getRightChild()
      self._upperSituate(x, z)
      self._lowerSituate(t1, x)
      self._lowerSituate(t2, y)
      self._lowerSituate(t3, z)
      self._lowerSituate(t4, z)
      x.setLeftChild(t1)
      x.setRightChild(y)
      x.setParent(z_parent)
      y.setLeftChild(t2)
      y.setRightChild(z)
      y.setParent(x)
      z.setLeftChild(t3)
      z.setRightChild(t4)
      z.setParent(y)
    else:
      # print "right, right"
      # right, right
      t1 = z.getLeftChild()
      t2 = y.getLeftChild()
      t3 = x.getLeftChild()
      t4 = x.getRightChild()
      self._upperSituate(x, z)
      self._lowerSituate(t1, z)
      self._lowerSituate(t2, z)
      self._lowerSituate(t3, y)
      self._lowerSituate(t4, x)
      z.setLeftChild(t1)
      z.setRightChild(t2)
      z.setParent(y)
      y.setLeftChild(z)
      y.setRightChild(t3)
      y.setParent(x)
      x.setLeftChild(y)
      x.setRightChild(t4)
      x.setParent(z_parent)
  def _zig_zag(self, x):
    # print "zig-zag"
    # x, y, z
    # replace z by x
    # make x have y and z as children
    y = x.getParent()
    z = y.getParent()
    z_parent = z.getParent()
    z_has_parent = z.hasParent()
    if x.isRightChild() == True:
      # left, right
      t1 = y.getLeftChild()
      t2 = x.getLeftChild()
      t3 = x.getRightChild()
      t4 = z.getRightChild()
      self._upperSituate(x, z)
      self._lowerSituate(t1, y)
      self._lowerSituate(t2, y)
      self._lowerSituate(t3, z)
      self._lowerSituate(t4, z)
      y.setLeftChild(t1)
      y.setRightChild(t2)
      y.setParent(x)
      x.setLeftChild(y)
      x.setRightChild(z)
      x.setParent(z_parent)
      z.setLeftChild(t3)
      z.setRightChild(t4)
      z.setParent(x)
    else:
      # right, left
      t1 = z.getLeftChild()
      t2 = x.getLeftChild()
      t3 = x.getRightChild()
      t4 = y.getRightChild()
      self._upperSituate(x, z)
      self._lowerSituate(t1, z)
      self._lowerSituate(t2, z)
      self._lowerSituate(t3, y)
      self._lowerSituate(t4, y)
      z.setLeftChild(t1)
      z.setRightChild(t2)
      z.setParent(x)
      x.setLeftChild(z)
      x.setRightChild(y)
      x.setParent(z_parent)
      y.setLeftChild(t3)
      y.setRightChild(t4)
      y.setParent(x)
  # x might be an external node
  def _zig(self, x):
    # print "zig"
    # print x.getElement().toString()
    # x, y, w
    # make x have y and w as children
    y = x.getParent()
    w1 = x.getLeftChild()
    w2 = x.getRightChild()
    y_parent = y.getParent()
    y_has_parent = y.hasParent()
    # print x.getElement().toString()
    if x.isLeftChild() == True:
      # print "left"
      # left
      t3 = x.getRightChild()
      t4 = y.getRightChild()
      self._upperSituate(x, y)
      self._lowerSituate(t3, y)
      self._lowerSituate(t4, y)
      x.setLeftChild(w1)
      x.setRightChild(y)
      x.setParent(y_parent)
      y.setLeftChild(t3)
      y.setRightChild(t4)
      y.setParent(x)
    else:
      # print "right"
      # right
      t1 = y.getLeftChild()
      t2 = x.getLeftChild()
      self._upperSituate(x, y)
      self._lowerSituate(t1, y)
      self._lowerSituate(t2, y)
      y.setLeftChild(t1)
      y.setRightChild(t2)
      y.setParent(x)
      # print y.getElement().getKey()
      x.setLeftChild(y)
      x.setRightChild(w2)
      x.setParent(y_parent)
      # print x.getLeftChild() == x
      # print x.getLeftChild().getElement().getKey()
      # print self.getRoot().getElement().getKey()
  # return an (entry, node) pair
  def _findWithSplay(self, key, bst_find):
    """
    entry = bst_find(key)
    # perform splaying on lowest accessed node
    target_node = self.action_node
    self._splay(target_node)
    """
    result = bst_find(key)
    # perform splaying on lowest accessed node
    target_node = self.action_node
    self._splayGivenActionNode(target_node)
    return result
  # return an (entry, node) pair
  def find(self, key):
    # bst_find = lambda x: BinarySearchTree.find(self, x)
    bst_find = lambda x: BinarySearchTree.find(self, x)
    return self._findWithSplay(key, bst_find)
    """
    tree_search = BinarySearchTree._treeSearch
    return (self._findWithSplay(key, tree_search))[0]
    return self._findWithSplay(key)
    """
  # return an (entry, node) pair
  def _insertWithSplay(self, key, value, bst_insert):
    result = bst_insert(key, value)
    # perform splaying on lowest accessed node
    target_node = self.action_node
    # self._splay(target_node)
    self._splayGivenActionNode(target_node)
    return result
  # return an (entry, node) pair
  def insert(self, untransformed_key, value):
    # bst_insert = lambda key, value: BinarySearchTree.insert(self, key, value)
    bst_insert = lambda key, value: OrderedBinarySearchTree.insert(self, key, value)
    return self._insertWithSplay(untransformed_key, value, bst_insert)
  """
  def insertWithUntransformedKey(self, key, value):
    bst_insert = lambda x: BinarySearchTree.insertWithUntransformedKey(self, x)
    return self._insertWithSplay(key, value, bst_insert)
  """
  # return an (entry, node) pair
  def _removeWithSplay(self, entry, bst_remove):
    """
    bst_remove(entry)
    # perform splaying on lowest accessed node
    target_node = self.action_node
    self._splay(target_node)
    """
    result = bst_remove(entry)
    # perform splaying on lowest accessed node
    target_node = self.action_node
    self._splayGivenActionNode(target_node)
    return result
  # remove an entry with matching (transformed) key
  # note: entry provided should involve untransformed key
  # return an (entry, node) pair
  def remove(self, entry):
    # bst_remove = lambda x: BinarySearchTree.remove(self, x)
    # bst_remove = lambda entry: BinarySearchTree.remove(self, entry)
    bst_remove = lambda entry: OrderedBinarySearchTree.remove(self, entry)
    return self._removeWithSplay(entry, bst_remove)
    """
    tree_search = BinarySearchTree._treeSearch
    return (self._removeWithSplay(entry, tree_search))[0]
    """
  """
  def remove(self, entry_with_transformed_key):
    # bst_remove = lambda x: BinarySearchTree.remove(self, x)
    bst_remove = lambda entry: BinarySearchTree.remove(self, entry)
    return self._removeWithSplay(entry_with_transformed_key, bst_remove)
    # tree_search = BinarySearchTree._treeSearch
    # return (self._removeWithSplay(entry_with_untransformed_key, tree_search))[0]
  """
  """
  # remove an entry with matching untransformed key
  # return an (entry, node) pair
  def removeWithUntransformedKey(self, entry_with_untransformed_key):
    transform = self.getKeyTransform()
    key = entry_with_untransformed_key.getKey()
    value = entry_with_untransformed_key.getValue()
    # key, value = entry_with_untransformed_key
    transformed_key = transform(key)
    # arbitrarily create an entry object
    # entry_with_transformed_key = transformed_key, value
    entry_with_transformed_key = LocationAwareEntry(transformed_key, value)
    return self.remove(entry_with_transformed_key)
  """
  """
    # bst_remove = lambda x: BinarySearchTree.removeWithUntransformedKey(self, x)
    # return self._removeWithSplay(entry_with_untransformed_key, bst_remove)
  """
  """
    # tree_search = BinarySearchTree._treeSearchWithoutTransformedKey
    # return (self._removeWithSplay(entry_with_untransformed_key, tree_search))[0]
  """
  """
  def _treeSearchWithBalancingWithSplay(self, key, node, tree_search):
    result_node = tree_search(key, node)
    self.action_node = result_node
    # perform splaying on lowest accessed node
    target_node = self.action_node
    self._splayGivenActionNode(target_node)
    return result_node
  # this method is to be considered protected, not private
  def _treeSearchWithBalancing(self, key, node):
    tree_search = lambda x, y: self._treeSearch(self, x, y)
    return self._treeSearchWithBalancingWithSplay(key, node, tree_search)
  """
  """
  def _treeSearchWithBalancingWithUntransformedKey(self, key, node):
    tree_search = lambda x, y: self._treeSearchWithUntransformedKey(self, x, y)
    return self._treeSearchWithBalancingWithSplay(key, node, tree_search)
  """
"""
t2 = SplayTree.construct([(17, 1), (28, 1), (29, 1), (32, 1), (44, 1), (54, 1), (65, 1), (76, 1), (78, 1), (80, 1), (82, 1), (88, 1), (97, 1), (17, 1)])
t2.remove(LocationAwareEntry(32, 1))
print t2.toString()
print t2.toInorderList()
t2.remove(LocationAwareEntry(65, 1))
print t2.toInorderList()
"""
"""
t4 = SplayTree.construct([(17, 1), (28, 1), (29, 1)])
print t4.toInorderList()
print t4.toString()
t4.remove(LocationAwareEntry(28, 1))
t4.remove(LocationAwareEntry(17, 1))
# t4.remove(LocationAwareEntry(32, 1))
print t4.toInorderList()
print t4.toString()
"""

# splay ought to not be called on a placeholder node, 
# lest it become root
from ..OrderedBinarySearchTree import *
from ..Entry import *
class SplayTree(OrderedBinarySearchTree):
  def __init__(self, key_transform = lambda x: x, comparator = comp):
    # BinarySearchTree.__init__(self, key_transform, comparator)
    OrderedBinarySearchTree.__init__(self, key_transform, comparator)
  @staticmethod
  def construct(entries):
    tree = SplayTree()
    for entry in entries:
      key, value = entry
      tree.insert(key, value)
    return tree
  # return whether we have a non-placeholder node to splay
  def _oughtToSplay(self, action_node):
    return not (action_node.isExternal() and action_node == self.getRoot())
  # candidates include current node and ancestors; 
  #   we are interested in the closest such node
  # if there is no non-placeholder node among these candidates, 
  #   return None
  def _getNodeToSplayGivenActionNode(self, action_node):
    return self._getNodeToSplayGivenActionNodeHelper(action_node)
  def _getNodeToSplayGivenActionNodeHelper(self, node):
    if not node.isExternal():
      return node
    else:
      if node == self.getRoot():
        return None
      else:
        return self._getNodeToSplayGivenActionNodeHelper(node.getParent())
  def _splayGivenActionNode(self, node):
    if self._oughtToSplay(node) == True:
      node_to_splay = self._getNodeToSplayGivenActionNode(node)
      self._splay(node_to_splay)
  def _splay(self, x):
    # if is left child of a left child, or right child of a right child
    # if is left child of a right child, or right child of a left child
    # if does not have a grandparent
    # print "splaying"
    parent = x.getParent()
    if parent == None:
      return
    grandparent = parent.getParent()
    if grandparent == None:
      self._zig(x)
    elif (x.isLeftChild() and parent.isLeftChild()) \
      or (x.isRightChild() and parent.isRightChild()):
      self._zig_zig(x)
    elif (x.isLeftChild() and parent.isRightChild()) \
      or (x.isRightChild() and parent.isLeftChild()):
      self._zig_zag(x)
    self._splay(x)
  def _zig_zig(self, x):
    # print "zig-zig"
    # x, y, z
    # replace z by x
    # make x have y as a child
    # make y have z as a child
    y = x.getParent()
    z = y.getParent()
    z_parent = z.getParent()
    z_has_parent = z.hasParent()
    if x.isLeftChild() == True:
      # print "left, left"
      # left, left
      t1 = x.getLeftChild()
      t2 = x.getRightChild()
      t3 = y.getRightChild()
      t4 = z.getRightChild()
      self._upperSituate(x, z)
      self._lowerSituate(t1, x)
      self._lowerSituate(t2, y)
      self._lowerSituate(t3, z)
      self._lowerSituate(t4, z)
      x.setLeftChild(t1)
      x.setRightChild(y)
      x.setParent(z_parent)
      y.setLeftChild(t2)
      y.setRightChild(z)
      y.setParent(x)
      z.setLeftChild(t3)
      z.setRightChild(t4)
      z.setParent(y)
    else:
      # print "right, right"
      # right, right
      t1 = z.getLeftChild()
      t2 = y.getLeftChild()
      t3 = x.getLeftChild()
      t4 = x.getRightChild()
      self._upperSituate(x, z)
      self._lowerSituate(t1, z)
      self._lowerSituate(t2, z)
      self._lowerSituate(t3, y)
      self._lowerSituate(t4, x)
      z.setLeftChild(t1)
      z.setRightChild(t2)
      z.setParent(y)
      y.setLeftChild(z)
      y.setRightChild(t3)
      y.setParent(x)
      x.setLeftChild(y)
      x.setRightChild(t4)
      x.setParent(z_parent)
  def _zig_zag(self, x):
    # print "zig-zag"
    # x, y, z
    # replace z by x
    # make x have y and z as children
    y = x.getParent()
    z = y.getParent()
    z_parent = z.getParent()
    z_has_parent = z.hasParent()
    if x.isRightChild() == True:
      # left, right
      t1 = y.getLeftChild()
      t2 = x.getLeftChild()
      t3 = x.getRightChild()
      t4 = z.getRightChild()
      self._upperSituate(x, z)
      self._lowerSituate(t1, y)
      self._lowerSituate(t2, y)
      self._lowerSituate(t3, z)
      self._lowerSituate(t4, z)
      y.setLeftChild(t1)
      y.setRightChild(t2)
      y.setParent(x)
      x.setLeftChild(y)
      x.setRightChild(z)
      x.setParent(z_parent)
      z.setLeftChild(t3)
      z.setRightChild(t4)
      z.setParent(x)
    else:
      # right, left
      t1 = z.getLeftChild()
      t2 = x.getLeftChild()
      t3 = x.getRightChild()
      t4 = y.getRightChild()
      self._upperSituate(x, z)
      self._lowerSituate(t1, z)
      self._lowerSituate(t2, z)
      self._lowerSituate(t3, y)
      self._lowerSituate(t4, y)
      z.setLeftChild(t1)
      z.setRightChild(t2)
      z.setParent(x)
      x.setLeftChild(z)
      x.setRightChild(y)
      x.setParent(z_parent)
      y.setLeftChild(t3)
      y.setRightChild(t4)
      y.setParent(x)
  # x might be an external node
  def _zig(self, x):
    # print "zig"
    # print x.getElement().toString()
    # x, y, w
    # make x have y and w as children
    y = x.getParent()
    w1 = x.getLeftChild()
    w2 = x.getRightChild()
    y_parent = y.getParent()
    y_has_parent = y.hasParent()
    # print x.getElement().toString()
    if x.isLeftChild() == True:
      # print "left"
      # left
      t3 = x.getRightChild()
      t4 = y.getRightChild()
      self._upperSituate(x, y)
      self._lowerSituate(t3, y)
      self._lowerSituate(t4, y)
      x.setLeftChild(w1)
      x.setRightChild(y)
      x.setParent(y_parent)
      y.setLeftChild(t3)
      y.setRightChild(t4)
      y.setParent(x)
    else:
      # print "right"
      # right
      t1 = y.getLeftChild()
      t2 = x.getLeftChild()
      self._upperSituate(x, y)
      self._lowerSituate(t1, y)
      self._lowerSituate(t2, y)
      y.setLeftChild(t1)
      y.setRightChild(t2)
      y.setParent(x)
      # print y.getElement().getKey()
      x.setLeftChild(y)
      x.setRightChild(w2)
      x.setParent(y_parent)
      # print x.getLeftChild() == x
      # print x.getLeftChild().getElement().getKey()
      # print self.getRoot().getElement().getKey()
  # return an (entry, node) pair
  def _findWithSplay(self, key, bst_find):
    """
    entry = bst_find(key)
    # perform splaying on lowest accessed node
    target_node = self.action_node
    self._splay(target_node)
    """
    result = bst_find(key)
    # perform splaying on lowest accessed node
    target_node = self.action_node
    self._splayGivenActionNode(target_node)
    return result
  # return an (entry, node) pair
  def find(self, key):
    # bst_find = lambda x: BinarySearchTree.find(self, x)
    bst_find = lambda x: BinarySearchTree.find(self, x)
    return self._findWithSplay(key, bst_find)
    """
    tree_search = BinarySearchTree._treeSearch
    return (self._findWithSplay(key, tree_search))[0]
    return self._findWithSplay(key)
    """
  # return an (entry, node) pair
  def _insertWithSplay(self, key, value, bst_insert):
    result = bst_insert(key, value)
    # perform splaying on lowest accessed node
    target_node = self.action_node
    # self._splay(target_node)
    self._splayGivenActionNode(target_node)
    return result
  # return an (entry, node) pair
  def insert(self, untransformed_key, value):
    # bst_insert = lambda key, value: BinarySearchTree.insert(self, key, value)
    bst_insert = lambda key, value: OrderedBinarySearchTree.insert(self, key, value)
    return self._insertWithSplay(untransformed_key, value, bst_insert)
  """
  def insertWithUntransformedKey(self, key, value):
    bst_insert = lambda x: BinarySearchTree.insertWithUntransformedKey(self, x)
    return self._insertWithSplay(key, value, bst_insert)
  """
  # return an (entry, node) pair
  def _removeWithSplay(self, entry, bst_remove):
    """
    bst_remove(entry)
    # perform splaying on lowest accessed node
    target_node = self.action_node
    self._splay(target_node)
    """
    result = bst_remove(entry)
    # perform splaying on lowest accessed node
    target_node = self.action_node
    self._splayGivenActionNode(target_node)
    return result
  # remove an entry with matching (transformed) key
  # note: entry provided should involve untransformed key
  # return an (entry, node) pair
  def remove(self, entry):
    # bst_remove = lambda x: BinarySearchTree.remove(self, x)
    # bst_remove = lambda entry: BinarySearchTree.remove(self, entry)
    bst_remove = lambda entry: OrderedBinarySearchTree.remove(self, entry)
    return self._removeWithSplay(entry, bst_remove)
    """
    tree_search = BinarySearchTree._treeSearch
    return (self._removeWithSplay(entry, tree_search))[0]
    """
  """
  def remove(self, entry_with_transformed_key):
    # bst_remove = lambda x: BinarySearchTree.remove(self, x)
    bst_remove = lambda entry: BinarySearchTree.remove(self, entry)
    return self._removeWithSplay(entry_with_transformed_key, bst_remove)
    # tree_search = BinarySearchTree._treeSearch
    # return (self._removeWithSplay(entry_with_untransformed_key, tree_search))[0]
  """
  """
  # remove an entry with matching untransformed key
  # return an (entry, node) pair
  def removeWithUntransformedKey(self, entry_with_untransformed_key):
    transform = self.getKeyTransform()
    key = entry_with_untransformed_key.getKey()
    value = entry_with_untransformed_key.getValue()
    # key, value = entry_with_untransformed_key
    transformed_key = transform(key)
    # arbitrarily create an entry object
    # entry_with_transformed_key = transformed_key, value
    entry_with_transformed_key = LocationAwareEntry(transformed_key, value)
    return self.remove(entry_with_transformed_key)
  """
  """
    # bst_remove = lambda x: BinarySearchTree.removeWithUntransformedKey(self, x)
    # return self._removeWithSplay(entry_with_untransformed_key, bst_remove)
  """
  """
    # tree_search = BinarySearchTree._treeSearchWithoutTransformedKey
    # return (self._removeWithSplay(entry_with_untransformed_key, tree_search))[0]
  """
  """
  def _treeSearchWithBalancingWithSplay(self, key, node, tree_search):
    result_node = tree_search(key, node)
    self.action_node = result_node
    # perform splaying on lowest accessed node
    target_node = self.action_node
    self._splayGivenActionNode(target_node)
    return result_node
  # this method is to be considered protected, not private
  def _treeSearchWithBalancing(self, key, node):
    tree_search = lambda x, y: self._treeSearch(self, x, y)
    return self._treeSearchWithBalancingWithSplay(key, node, tree_search)
  """
  """
  def _treeSearchWithBalancingWithUntransformedKey(self, key, node):
    tree_search = lambda x, y: self._treeSearchWithUntransformedKey(self, x, y)
    return self._treeSearchWithBalancingWithSplay(key, node, tree_search)
  """
"""
t2 = SplayTree.construct([(17, 1), (28, 1), (29, 1), (32, 1), (44, 1), (54, 1), (65, 1), (76, 1), (78, 1), (80, 1), (82, 1), (88, 1), (97, 1), (17, 1)])
t2.remove(LocationAwareEntry(32, 1))
print t2.toString()
print t2.toInorderList()
t2.remove(LocationAwareEntry(65, 1))
print t2.toInorderList()
"""
"""
t4 = SplayTree.construct([(17, 1), (28, 1), (29, 1)])
print t4.toInorderList()
print t4.toString()
t4.remove(LocationAwareEntry(28, 1))
t4.remove(LocationAwareEntry(17, 1))
# t4.remove(LocationAwareEntry(32, 1))
print t4.toInorderList()
print t4.toString()
"""

# splay ought to not be called on a placeholder node, # lest it become root # BinarySearchTree.__init__(self, key_transform, comparator) # return whether we have a non-placeholder node to splay # candidates include current node and ancestors; #   we are interested in the closest such node # if there is no non-placeholder node among these candidates, #   return None # if is left child of a left child, or right child of a right child # if is left child of a right child, or right child of a left child # if does not have a grandparent # print "splaying" # print "zig-zig" # x, y, z # replace z by x # make x have y as a child # make y have z as a child # print "left, left" # left, left # print "right, right" # right, right # print "zig-zag" # x, y, z # replace z by x # make x have y and z as children # left, right # right, left # x might be an external node # print "zig" # print x.getElement().toString() # x, y, w # make x have y and w as children # print x.getElement().toString() # print "left" # left # print "right" # right # print y.getElement().getKey() # print x.getLeftChild() == x # print x.getLeftChild().getElement().getKey() # print self.getRoot().getElement().getKey() # return an (entry, node) pair entry = bst_find(key)
     # perform splaying on lowest accessed node
     target_node = self.action_node
     self._splay(target_node) # perform splaying on lowest accessed node # return an (entry, node) pair # bst_find = lambda x: BinarySearchTree.find(self, x) tree_search = BinarySearchTree._treeSearch
     return (self._findWithSplay(key, tree_search))[0]
     return self._findWithSplay(key) # return an (entry, node) pair # perform splaying on lowest accessed node # self._splay(target_node) # return an (entry, node) pair # bst_insert = lambda key, value: BinarySearchTree.insert(self, key, value) def insertWithUntransformedKey(self, key, value):
     bst_insert = lambda x: BinarySearchTree.insertWithUntransformedKey(self, x)
     return self._insertWithSplay(key, value, bst_insert) # return an (entry, node) pair bst_remove(entry)
     # perform splaying on lowest accessed node
     target_node = self.action_node
     self._splay(target_node) # perform splaying on lowest accessed node # remove an entry with matching (transformed) key # note: entry provided should involve untransformed key # return an (entry, node) pair # bst_remove = lambda x: BinarySearchTree.remove(self, x) # bst_remove = lambda entry: BinarySearchTree.remove(self, entry) tree_search = BinarySearchTree._treeSearch
     return (self._removeWithSplay(entry, tree_search))[0] def remove(self, entry_with_transformed_key):
     # bst_remove = lambda x: BinarySearchTree.remove(self, x)
     bst_remove = lambda entry: BinarySearchTree.remove(self, entry)
     return self._removeWithSplay(entry_with_transformed_key, bst_remove)
     # tree_search = BinarySearchTree._treeSearch
     # return (self._removeWithSplay(entry_with_untransformed_key, tree_search))[0] # remove an entry with matching untransformed key
   # return an (entry, node) pair
   def removeWithUntransformedKey(self, entry_with_untransformed_key):
     transform = self.getKeyTransform()
     key = entry_with_untransformed_key.getKey()
     value = entry_with_untransformed_key.getValue()
     # key, value = entry_with_untransformed_key
     transformed_key = transform(key)
     # arbitrarily create an entry object
     # entry_with_transformed_key = transformed_key, value
     entry_with_transformed_key = LocationAwareEntry(transformed_key, value)
     return self.remove(entry_with_transformed_key) # bst_remove = lambda x: BinarySearchTree.removeWithUntransformedKey(self, x)
     # return self._removeWithSplay(entry_with_untransformed_key, bst_remove) # tree_search = BinarySearchTree._treeSearchWithoutTransformedKey
     # return (self._removeWithSplay(entry_with_untransformed_key, tree_search))[0] def _treeSearchWithBalancingWithSplay(self, key, node, tree_search):
     result_node = tree_search(key, node)
     self.action_node = result_node
     # perform splaying on lowest accessed node
     target_node = self.action_node
     self._splayGivenActionNode(target_node)
     return result_node
   # this method is to be considered protected, not private
   def _treeSearchWithBalancing(self, key, node):
     tree_search = lambda x, y: self._treeSearch(self, x, y)
     return self._treeSearchWithBalancingWithSplay(key, node, tree_search) def _treeSearchWithBalancingWithUntransformedKey(self, key, node):
     tree_search = lambda x, y: self._treeSearchWithUntransformedKey(self, x, y)
     return self._treeSearchWithBalancingWithSplay(key, node, tree_search) t2 = SplayTree.construct([(17, 1), (28, 1), (29, 1), (32, 1), (44, 1), (54, 1), (65, 1), (76, 1), (78, 1), (80, 1), (82, 1), (88, 1), (97, 1), (17, 1)])
 t2.remove(LocationAwareEntry(32, 1))
 print t2.toString()
 print t2.toInorderList()
 t2.remove(LocationAwareEntry(65, 1))
 print t2.toInorderList() t4 = SplayTree.construct([(17, 1), (28, 1), (29, 1)])
 print t4.toInorderList()
 print t4.toString()
 t4.remove(LocationAwareEntry(28, 1))
 t4.remove(LocationAwareEntry(17, 1))
 # t4.remove(LocationAwareEntry(32, 1))
 print t4.toInorderList()
 print t4.toString()