Dynamic Trees with Revert

#!/usr/bin/python

class Node:
  def __init__(self, left = None, right = None, parent = None):
    self.left   = left
    self.right  = right
    self.parent = parent
    self.link   = None
    self.rev    = False
    self.size   = 1

def size(v):
  return 0 if v == None else v.size

def recomp(v):
  v.size = 1 + size(v.left) + size(v.right)

def set_parent(child, parent):
  if child != None:
    child.parent = parent

def reverse(v):
  if v != None:
    v.rev ^= True

def push(v):
  if v != None and v.rev:
    v.left, v.right = v.right, v.left
    v.rev = False
    reverse(v.left)
    reverse(v.right)


def keep_parent(v):
  set_parent(v.left, v)
  set_parent(v.right, v)
  recomp(v)

def rotate(parent, child):
  """Rotates the parent-child nodes and keeps consistency of the tree"""
  gparent = parent.parent
  if gparent != None:
    if gparent.left == parent:
      gparent.left = child
    else:
      gparent.right = child

  if parent.left == child:
    parent.left, child.right = child.right, parent
  else:
    parent.right, child.left = child.left, parent

  keep_parent(parent)
  keep_parent(child)
  child.parent = gparent

def splay(v):
  if v.parent == None:
    return v
  parent = v.parent
  gparent = parent.parent
  if gparent == None:
    rotate(parent, v)
    return v
  else:
    zigzig = (gparent.left == parent) == (parent.left == v)
    if zigzig:
      rotate(gparent, parent)
      rotate(parent, v)
    else:
      rotate(parent, v)
      rotate(gparent, v)
    return splay(v)

def find(v, lhs):
  if v == None:
    return None
  push(v)
  threshold = size(v.left)
  if lhs == threshold:
    return splay(v)
  if lhs < threshold and v.left != None:
    return find(v.left, lhs)
  if lhs > threshold and v.right != None:
    return find(v.right, lhs - threshold - 1)
  return splay(v)

def split(root, lhs):
  if root == None:
    return None, None
  root = find(root, lhs)
  if root.size <= lhs:
    return root, None
  set_parent(root.left, None)
  root.left = None
  recomp(root)
  return root.left, root


def merge(left, right):
  if right == None:
    return left
  if left == None:
    return right
  right = find(right, 0)
  right.left = left
  keep_parent(right)
  return right

def cleanup(v):
  if v == None:
    return
  cleanup(v.parent)
  push(v)

def supportRoot(v):
  cleanup(v)
  return splay(v)

def cutout(v):
  supportRoot(v)
  left, right = split(v, size(v.left) + 1)
  if right != None:
    find(right, 0).link = v
  return v

def expose(v):
  v = find(cutout(v), 0)
  while v.link != None:
    nxt = cutout(v.link)
    v.link = None
    v = find(merge(nxt, v), 0)
  return v

def depth(v):
  expose(v)
  return supportRoot(v).size - 1

def link(child, parent):
  child.link = parent
  return expose(child)

def cut(child, parent):
  expose(parent)
  child.link = None

def find_root(v):
  return expose(v)

def revert(v):
  root = expose(v)
  reverse(supportRoot(root))

def dist(u, v):
  revert(u)
  w = expose(v)
  if w != u:
    return -1
  return depth(v)

def add(u, v):
  revert(u)
  link(u, v)

def rem(u, v):
  revert(v)
  cut(u, v)

def main():
  v = [Node() for i in range(10)]
  link(v[1], v[0])
  link(v[2], v[1])
  link(v[3], v[2])
  link(v[4], v[2])
  revert(v[1])
  print [depth(v[i]) for i in range(5)]

if __name__ == "__main__":
  main()