class BPTreeLeafInitException(Exception):
	pass

''' It turns out that the right convention can greatly simplify your code.
One convention that makes life simpler here is to make sure that when we split,
the new bucket is the larger 1/2. This means that our parent already has a pointer
to the smaller 1/2 of the spit bucket. With this convention, we are always
promoting (pkey, ppointer) where ppointer is a pointer to the subtree with pkey<=keys. 
Draw a picture after a few inserts to understand this. '''

class BPTree(object):
	def __init__(self, capacity):
		''' create an empty BPTree where 
		each node has capacity keys and capacity+1 pointers
		each leaf has capacity keys '''

		self._capacity=capacity 
		self._tree=BPTreeLeaf([],None, self._capacity)

	def insert(self, key):
		''' insert key into our subtree '''
		(pkey,ppointer)=self._tree.insert(key)
		if (pkey, ppointer)!=(None,None):
			self._tree=BPTreeNode([pkey], [self._tree, ppointer], self._capacity)

	def keys(self):
		''' return a list of all keys in self '''
		return self._tree.keys()

	def find(self, key):
		''' return whether key is in this BPTree '''
		return self._tree.find(key)

	def stats():
		pass

	def search(self, keyword):
		''' return a list of all document numbers associated with keyword '''
		return self._tree.search(keyword)

class BPTreeNode(object):
	def __init__(self, keys, pointers, capacity):
		''' New BPTreeNode with keys=[key], pointers=[least, pointer] '''

		self._keys=keys # in sorted order
		self._pointers=pointers
		self._capacity=capacity

	def keys(self):
		return self._pointers[0].keys()

	def find(self, key):
		''' return whether key is in this tree (at the appropriate leaf) '''

		# figure out which pointer we should follow, that is, follow
		# self._pointers[index] where
		# self._keys[index-1]<=key<self._keys[index]

		index=0
		while index<len(self._keys) and key>=self._keys[index]:
			index=index+1

		return self._pointers[index].find(key)
		
	def search(self, keyword):
		''' return a list of all document numbers associated with keyword '''
		pass

	def insert_here(self, position, key, pointer):
		''' insert key, pointer in this node at the specified position
		return (None, None) if there is nothing to promote
		return (pkey, ppointer) if self splits '''
		self._keys.insert(position, key)
		self._pointers.insert(position+1, pointer)

		# if we are over capacity, we need to split. 
		if len(self._keys)>self._capacity:

			# Find the middle key in self, this will be promoted and deleted from this level.
			# the middle key as well as the pointer to the greater bucket will be returned.
			m=len(self._keys)//2
			lower_keys=self._keys[:m]
			lower_pointers=self._pointers[:m+1]

			pkey=self._keys[m]

			upper_keys=self._keys[m+1:]
			upper_pointers=self._pointers[m+1:]

			ppointer=BPTreeNode(upper_keys, upper_pointers, self._capacity)
			self._keys=lower_keys
			self._pointers=lower_pointers

			return(pkey, ppointer)
		else:
			return (None, None)

	def insert(self, key):
		''' insert key into this subtree
		return (None, None) if there is nothing to promote
		return (pkey, ppointer) if self splits '''

		# figure out which pointer we should follow, that is, follow
		# self._pointers[index] where
		# self._keys[index-1]<=key<self._keys[index]

		index=0
		while index<len(self._keys) and key>=self._keys[index]:
			index=index+1
		
		# ask that subtree to insert the key
		(pkey,ppointer)=self._pointers[index].insert(key)

		# if the subtree promoted (pkey, ppointer) we have to insert_here
		if (pkey, ppointer)!=(None, None):
			return self.insert_here(index, pkey, ppointer)
		else:
			return (None, None)

class BPTreeLeaf(object):
	def __init__(self, keys, next_leaf, capacity):

		if len(keys)>capacity:
			raise BPTreeLeafInitException()

		self._keys=keys # in sorted order
		self._next=next_leaf # next BPTreeLeaf
		self._capacity=capacity

	def keys(self):
		''' return a list of all keys from here to the end of the linked list of BPTreeLeaf '''
		# this probably should be done non-recursively, since the linked list could be long!

		all_keys=[]
		bucket=self
		while bucket is not None:
			all_keys.extend(bucket._keys)
			bucket=bucket._next
		return all_keys

	def find(self, key):
		''' return whether key is in this tree (at the appropriate leaf) '''

		# figure out which pointer we should follow, that is, follow
		# self._pointers[index] where
		# self._keys[index-1]<=key<self._keys[index]

		index=0
		while index<len(self._keys) and key>self._keys[index]:
			index=index+1
		if index<len(self._keys) and self._keys[index]==key:
			return True
		else:
			return False

	def search(self, keyword):
		''' return a list of all document numbers associated with keyword '''
		pass

	def insert(self, key):
		''' insert key into self. A key should not appear twice in the BPTreeLeaf level
		return (None, None) if there is nothing to promote
		return (pkey, ppointer) if self splits '''

		# figure out where this new key goes
		index=0
		while index<len(self._keys) and key>self._keys[index]:
			index=index+1

		# if the key is already there, do nothing
		if index<len(self._keys) and self._keys[index]==key:
			return (None, None)

		# insert the key in the appropriate position in self._keys
		self._keys.insert(index,key)

		# if we are over capacity, we need to split, maintaining
		# the linked list of buckets. All keys stay at this level and 
		# we promote a copy of the first key in the greater
		# bucket.

		if len(self._keys)>self._capacity:
			m=len(self._keys)//2
			lower_keys=self._keys[:m]
			upper_keys=self._keys[m:]

			self._keys=lower_keys
			self._next=BPTreeLeaf(upper_keys, self._next, self._capacity)

			return (self._next._keys[0], self._next)
		else:
			return (None, None)