#include <assert.h>
#include "BTree.h"

#ifndef TRUE
#define TRUE 1
#endif

#ifndef FALSE
#define FALSE 0
#endif

/* Creates a new B-Tree, given the parameter m (as in the textbook). */
template<class K, class D>
BTree<K,D>::BTree(int m) : _m(m)
{
}


template<class K, class D>
BTree<K,D>::~BTree()
{
}


// PRE: key is not in the tree.
// Inserts a (key, data) pair into the tree. 
template<class K, class D>
void 
BTree<K,D>::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.
template<class K, class D>
int 
BTree<K,D>::find(K key, D& data)
{
}
  

// PRE: key is in the tree.
// Removes the key and its associated data from the tree.
template<class K, class D>
void 
BTree<K,D>::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.
template<class K, class D>
void 
BTree<K,D>::print(ostream& os)
{
  _print(os, _root, 0);
}


// Recursively prints the given (sub)tree, keeping track of the depth
// in order to indent properly.

template<class K, class D>
void
BTree<K,D>::_print(ostream& os, BTreeNode<K,D>* root, int depth)
{
  int i;

  if (root == NULL) {
    for (i = 0; i < depth * _SPC_PER_DEPTH; i++) os << ' ';
    os << "Empty.\n";
  }
  else if (root->type() == BTInternal) {
    for (i = root->numKeys(); i >= ((root->numKeys() + 1) / 2); i--)
      _print(os, root->getChild(i), depth + 1);
    root->print(os, depth * _SPC_PER_DEPTH);
    while (i >= 0) {
      _print(os, root->getChild(i), depth + 1);
      i--;
    }
  }
  else
    root->print(os, depth * _SPC_PER_DEPTH);
}