// This may look like C code, but it is really -*- C++ -*-

#ifndef _BTREE_H_
#define _BTREE_H_

#include "BTreeNode.h"

template <class K, class D>
class BTree {

public:

  /* PRE: m >= 3. */
  /* Creates a new B-Tree, given the parameter m (as in the textbook). */
  BTree(int m);
  ~BTree();

  // PRE: key is not in the tree.
  // Inserts a (key, data) pair into the tree. 
  void insert(K key, D data);

  // Attempts to find the data associated with the given key.  If the key
  // is found, the data is placed into the second parameter and true is
  // returned.  Otherwise, if the key is not found, false is returned.
  int find(K key, D& data);

  // PRE: key is in the tree.
  // Removes the key and its associated data from the tree.
  void remove(K key);

  // Given an ostream (such as cout), print a text representation of the
  // tree.  The nodes are printed from right to left, so turning the 
  // output clockwise by 90 degrees should produce an accurate view
  // of the tree.
  void print(ostream& os);

private:

  // The number of spaces to indent each unit of depth in the tree.
  static const int _SPC_PER_DEPTH = 10;

  const int _m;			// The M constant for the tree.
  BTreeNode<K,D>* _root;	// The tree's root


  // Recursively prints the given (sub)tree, keeping track of the depth
  // in order to indent properly.
  void _print(ostream& os, BTreeNode<K,D>* root, int depth);

  /*
   * NOTE: I found the following private "helper" functions useful for
   * writing the methods above, but you are not required to implement them.
   *
   */

  // Given the root of a B-tree, this function returns the leaf
  // which contains the given key, or would contain it if it were
  // in the tree.
  // BTreeNode<K,D> *_findNodeForKey(BTreeNode<K,D>* root, K key);

  // Deallocates the memory held by the given subtree.
  // void _destroyTree(BTreeNode<K,D>* root);

  // Attempts to insert the key and data at the given leaf.  If the
  // leaf is full, then the function tries to give one of its elements
  // to a sibling.  If it can't, then the leaf is split and the new
  // subtree is inserted into the leaf's parent if it has one, or a
  // new root is created if not.
  // void _insertAtLeaf(BTreeNode<K,D>* leaf, K key, D data);

  // This function attempts to insert a new subtree with a given key
  // into an internal node.  As with the leaf case above, if the node
  // is full then it attempts to donate an element to a sibling, and 
  // if it fails then the node gets split.  The resulting new node is
  // inserted into the node's parent if it exists, or a new node
  // is created if not.
  // void _insertAtInternal(BTreeNode<K,D>* node, K key, BTreeNode<K,D> *subtree);

  // This function attempts to remove the key at the given leaf.  If the
  // resulting node is too small, it tries to borrow some data from a sibling.
  // if it cannot, then the node is merged with a sibling and a key deleted
  // from a parent.  If the parent is the root and its last key is deleted,
  // then the root is deleted and replaced with the merged node.
  // void _removeAtLeaf(BTreeNode<K,D>* leaf, K key);

  // This function tries to fix an internal node which has grown too
  // small.  It tries to borrow a key from a sibling.  if it cannot
  // and it is not the root, then the node is merged with a sibling
  // and a key is deleted from the parent.  If the node is the root
  // and its last key is deleted, then it is deleted and the root
  // replaced with the remaining child.
  // void _fixInternal(BTreeNode<K,D>* node);
};

#endif