''' 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._tree=BPTreeLeaf([],None, capacity)
		self._capacity=capacity

	def insert(self, key):
		''' insert key into our subtree '''
		pass

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

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

	def stats(self):
		''' return a tuple consisting of (height, number of nodes, number of leaves, number of keys) in the tree '''

		''' you may want to create separate height, numNodes, numLeaves, numKeys methods and 
			collect their information to return stats, for example, 
			
			return (self.height(), self.numNodes(), self.numLeaves(), self.numKeys())

			this way, all partners can work on a separate problem. We won't mark efficiency of this
			just that the code is simple, clear, obvious and works.
		'''
		pass

class BPTreeNode(object):
	def __init__(self, keys, pointers, capacity):
		''' New BPTreeNode with keys=[key0,key1,..., keyK], pointers=[pointer0, pointer1,...,keyK+1] '''

		self._keys=keys # in sorted order
		self._pointers=pointers # one more than the number of keys
		self._capacity=capacity

	def keys(self):
		''' Return a list of all keys in the linked list of leaves
		which are greater than or equal to the least key in this subtree. 
		In other words, starting at the least key in this subtree, 
		ending at the end of the linked list. '''

		pass

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

		# figure out which pointer we should follow, and then follow it
		# that is find index such that
		# self._keys[index-1]<=key<self._keys[index]
		# and then follow self._pointers[index]
		# NOTE: Check this with some examples to make sure this is the right thing!

		pass

	def insert_here(self, position, key, pointer):
		''' insert key, at 'position' and pointer at 'position+1'
		return (None, None) if there is nothing to promote
		return (pkey, ppointer) if self splits, 
		(pkey, ppointer) this is the promoted key, and, 
		a pointer to the newly created BPTreeNode '''

		self._keys.insert(position, key)
		self._pointers.insert(position+1, pointer)

		# if we are over capacity, we need to split. 

		# 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.

	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]

		# ask that subtree to insert the key

		# if the subtree promoted (pkey, ppointer) we have to insert_here
		pass

class BPTreeLeaf(object):
	def __init__(self, keys, next_leaf, capacity):
		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!

		pass

	def find(self, key):
		''' return whether key is in this leaf '''

		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 
		(pkey, ppointer) this is the promoted key, and, 
		a pointer to the newly created BPTreeLeaf '''

		# figure out where this new key goes

		# if the key is already there, do nothing

		# insert the key in the appropriate position in self._keys

		# 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.

		pass