#!/usr/bin/python

## Editor width - you must be at least this tall to enjoy this ride #############################################################################################

# Appears to be an excellent reference on treaps in java:
# http://users.cis.fiu.edu/~weiss/dsaajava/Code/DataStructures
# However, I'm not certain the remove method is correct
#
# Another nice reference on treaps in java:
# https://blog.eldslott.org/2009/04/25/treap-implementation-in-java/
# It doesn't seem to mention removals, but it shows rotations nicely
#
# A pretty complete-looking java implementation of treaps:
# http://www.nada.kth.se/~snilsson/public/code/treap/source/Treap.java
# It has what looks like a nice remove.  However, I wound up using something based on Weiss's code with two additional if's instead.

dnl a couple of macros to allow us to insert literal backticks and apostrophes
define(`LQ',`changequote(<,>)`dnl'
changequote`'')
define(`RQ',`changequote(<,>)dnl`
'changequote`'')

import sys
import copy
import math
import time
import functools
try:
	import pyx_`'ifdef(`m4dup',dup)treap_node
	treap_node = pyx_`'ifdef(`m4dup',dup)treap_node
except:
	import py_`'ifdef(`m4dup',dup)treap_node
	treap_node = py_`'ifdef(`m4dup',dup)treap_node

# Each element is stored in a node in a tree, and each node contains an integer and two references, one to the left
# subtree and one to the right subtree.

# We need to increase the recurision limit to fend off the randomization trolls from causing an over-deep recursion
# In practice, this`'RQ()ll be very unlikely, extremely unlikely, unless the client of this package chooses a
# small priority_size and saves a large number of values
min_heap_size = 100000
if sys.getrecursionlimit() < min_heap_size:
	sys.setrecursionlimit(min_heap_size)

def pad_to(s, length):
	return s + `'RQ()_`'RQ() * (length - `len(s)' - 1) + `'RQ() `'RQ()

def center(s, field_use_width, field_avail_width):
	field_use = (s + `'RQ()_`'RQ()*(field_use_width-1))[:field_use_width-1]
	pad_width = (field_avail_width - `len(field_use))' / 2.0
	result = `'RQ() `'RQ() * int(pad_width) + field_use + `'RQ() `'RQ() * int(math.ceil(pad_width))
	return result

# this is the public portion
class ifdef(`m4dup',dup)treap:
	def __init__(self, inorder=True):
		self.root = None
		self.length = 0

	# __bool__ is the python 3 name of the special method, while __nonzero__ is the python 2 name
	def __bool__(self):
		if self.root is None:
			return False
		else:
			return True

	__nonzero__ = __bool__

	def __len__(self):
		return self.length

	def insert(self, key, value, priority = None):
		if self.root is None:
			self.root = treap_node._treap_node()
			self.root.key = key
			self.root.value = value
			if priority:
				self.root.priority = priority

			self.length = 1
		else:
			(length_delta, self.root) = self.root.insert(self.root, key, value, priority )
			assert length_delta in [ 0, 1 ]
			self.length += length_delta

	__setitem__ = insert

	def remove(self, x):
		if self.root != None:
			(found, self.root) = self.root.remove(self.root, x)
			if found:
				self.length -= 1
			else:
				raise KeyError
		else:
			raise KeyError

	__delitem__ = remove

	def remove_min(self):
		if self.root != None:
			(self.root, result) = self.root.remove_min(self.root)
			if not (result is None):
				self.length -= 1
			return result
		else:
			raise KeyError

	def remove_max(self):
		if self.root != None:
			(self.root, result) = self.root.remove_max(self.root)
			if not (result is None):
				self.length -= 1
			return result
		else:
			raise KeyError

	def find(self, x):
		current = self.root

		while True:
			if current is None:
				raise KeyError
			elif x < current.key:
				current = current.left
			elif x > current.key:
				current = current.right
			else:
				# equal
				return current.value

	__getitem__ = find

	def find_min(self):
		current = self.root

		if current is None:
			raise KeyError

		while current.left != None:
			current = current.left

		return current.key

	def find_max(self):
		current = self.root

		if current is None:
			raise KeyError

		while current.right != None:
			current = current.right

		return current.key

	def inorder_traversal(self, visit):
		if self.root != None:
			self.root.inorder_traversal(visit)

	def detailed_inorder_traversal(self, visit):
		if self.root != None:
			self.root.detailed_inorder_traversal(visit)

	def check_tree_invariant(self):
		if self.root is None:
			return True
		else:
			return self.root._check_tree_invariant()

	def check_heap_invariant(self):
		if self.root is None:
			return True
		else:
			return self.root._check_heap_invariant()

	def depth(self):
		class maxer:
			def __init__(self, foo=-1):
				self.max = foo

			def feed(self, node, key, value, depth, from_left):
				if depth > self.max:
					self.max = depth

			def result(self):
				return self.max+1

		max_obj = maxer()
		self.detailed_inorder_traversal(max_obj.feed)
		return max_obj.result()

	def _depth_and_field_width(self):
		class maxer:
			def __init__(self, foo=-1):
				self.depth_max = foo
				self.field_width_max = -1

			def feed(self, node, key, value, depth, from_left):
				if depth > self.depth_max:
					self.depth_max = depth
				str_node = str(node)
				len_key = `len(str_node)'
				if len_key > self.field_width_max:
					self.field_width_max = len_key

			def result(self):
				return (self.depth_max+1, self.field_width_max)

		max_obj = maxer()
		self.detailed_inorder_traversal(max_obj.feed)
		return max_obj.result()

	def __str__(self):
		class Desc:
			def __init__(self, pretree):
				self.tree = pretree

			def update(self, node, key, value, depth, from_left):
				self.tree[depth][from_left] = str(node)

		if self.root is None:
			# empty output for an empty tree
			return `'RQ()`'RQ()
		else:
			pretree = []
			depth, field_use_width = self._depth_and_field_width()
			field_use_width += 1
			for level in xrange(depth):
				s = `'RQ()_`'RQ() * (field_use_width - 1)
				pretree.append([ s ] * 2**level)
			desc = Desc(pretree)
			self.root.detailed_inorder_traversal(desc.update)
			result = []
			widest = 2**(depth - 1) * field_use_width
			for level in xrange(depth):
				two_level = 2**level
				field_avail_width = widest / 2**level
				s = `'RQ()`'RQ().join([ center(x, field_use_width, field_avail_width) for x in desc.tree[level] ])
				# this really isn`'RQ()t useful for more than dozen values or so, and that without priorities printed
				result.append((`'RQ()%2d `'RQ() % level) + s)
			return `'RQ()\n`'RQ().join(result)

	class state_class:
		def __init__(self, todo, node):
			self.todo = todo
			self.node = node

		def __repr__(self):
			return `'RQ()%s %s`'RQ() % (self.todo, self.node)

dnl Arguments:
dnl $1 is the name of the method
dnl $2 is what the yield, including the yield keyword
define(iterator_macro, 
	def $1(self):
		stack = [ self.state_class(`'RQ()L`'RQ(), self.root) ]

		while stack:
			state = stack.pop()
			if state.node != None:
				if state.todo == `'RQ()V`'RQ():
					dnl yield state.node.key
					$2
				else:
					if state.node.right != None:
						stack.append(self.state_class(`'RQ()R`'RQ(), state.node.right))
					stack.append(self.state_class(`'RQ()V`'RQ(), state.node))
					if state.node.left != None:
						stack.append(self.state_class(`'RQ()L`'RQ(), state.node.left))
)

	# These three things: keys, values, items; are a bit of a cheat.  In Python 2, they're really supposed to return lists, but we return iterators
	# like python 3.  A better implementation would check what version of python we're targetting, give this behavior for python 3, and coerce the
	# value returned to a list for python 2.
	iterator_macro(iterkeys,yield state.node.key)
	keys = iterator = __iter__ = iterkeys

	iterator_macro(itervalues,yield state.node.value)
	values = itervalues

	iterator_macro(iteritems,`yield state.node.key, state.node.value')
	items = iteritems

	def reverse_iterator(self):
		stack = [ self.state_class(`'RQ()L`'RQ(), self.root) ]

		while stack:
			state = stack.pop()
			if state.node != None:
				if state.todo == `'RQ()V`'RQ():
					yield state.node.key
				else:
					if state.node.left != None:
						stack.append(self.state_class(`'RQ()L`'RQ(), state.node.left))
					stack.append(self.state_class(`'RQ()V`'RQ(), state.node))
					if state.node.right != None:
						stack.append(self.state_class(`'RQ()R`'RQ(), state.node.right))