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

#ifndef TRUE
#define TRUE 1
#endif

#ifndef FALSE
#define FALSE 0
#endif

/* Revision history:

   1.2: Fixed bug in replaceLeftmost(); needed to update the parent
        and sibling pointers of the new leftmost node.  Fixed bug
        in split which caused the new rightmost node in the original
        node to have an invalid right child.

   1.1: Fixed minor destructor bug in which destructor did not 
        differentiate between internal and leaf nodes; this should
        not affect the operation of the program. 
*/

/* This function creates a new node.  The data it requires is as follows:
     type          = the type of node
     max_num_keys  = the max number of keys; the max number of children
                     for an internal node will be one greater.
     parent        = the parent of the tree; NULL for the root.
     right_sibling = the left sibling of the node; NULL for the root and
                     the rightmost child of a node
     left_sibling  = the left sibling of the node; NULL for the root and
                     the leftmost child of a node
     initial_child = the initial child of an internal node.  Should be
                     NULL if the node is a leaf.
   */
template<class K, class D>
BTreeNode<K,D>::BTreeNode(BTreeNodeType type, int max_num_keys, 
			  BTreeNode<K, D> *parent,
			  BTreeNode<K, D> *left_sib, 
			  BTreeNode<K, D> *right_sib, 
			  BTreeNode<K, D> *initial_child)
{
  _type = type;
  _numKeys = 0;
  _maxNumKeys = max_num_keys;
  _parent = parent;
  _leftSib = left_sib;
  _rightSib = right_sib;
  _key = new K[_maxNumKeys];
  if (_type == BTInternal) {
    _child = new BTreeNode<K,D> *[_maxNumKeys + 1];
    _child[0] = initial_child;
    if (initial_child) {
      initial_child->_parent = this;
      initial_child->_leftSib = NULL;
      initial_child->_rightSib = NULL;
    }
  } else 
    _data = new D[_maxNumKeys];
}  


template<class K, class D>
BTreeNode<K,D>::~BTreeNode()
{
  if (_type == BTInternal)
    delete [] _child;
  else
    delete [] _data;
  delete [] _key;
}


// Returns the type of the node, either BTInternal, BTLeaf.
template<class K, class D>
BTreeNodeType 
BTreeNode<K,D>::type(void)
{
  return _type;
}


// Returns true if and only if the node is the root of a tree.
template<class K, class D>
int 
BTreeNode<K,D>::isRoot(void)
{
  return (_parent == NULL);
}


// PRE: type() == BTLeaf, 0 <= idx < numKeys()
// Returns the data associated with the key at index idx.
template<class K, class D>
D 
BTreeNode<K,D>::getData(int idx)
{
  assert((type() == BTLeaf) && (0 <= idx) && (idx < numKeys()));

  return _data[idx];
}


// PRE: type() == BTInternal, 0 <= idx < (numKeys() + 1)
// Returns child number idx from the node (numbered left to right).
template<class K, class D>
BTreeNode<K, D> *
BTreeNode<K,D>::getChild(int idx)
{
  assert((type() == BTInternal) && (0 <= idx) && (idx < (numKeys() + 1)));

  return _child[idx];
}


// Returns the number of keys stored at the node.  Note that the number
// of children of an internal node is this number plus 1.
template<class K, class D>
int 
BTreeNode<K,D>::numKeys(void)
{
  return _numKeys;
}


// Returns the maximum number of keys which can be stored at the
// node.
template<class K, class D>
int 
BTreeNode<K,D>::maxNumKeys(void)
{
  return _maxNumKeys;
}


// PRE: 0 <= i < numKeys()
// Returns key number i from the node.
template<class K, class D>
K 
BTreeNode<K,D>::getKey(int i)
{
  assert((0 <= i) && (i < numKeys()));
  
  return _key[i];
}


// PRE: 0 <= i < numKeys()
// Sets key number i to a new value.
template<class K, class D>
void
BTreeNode<K,D>::setKey(int i, K new_val)
{
  assert((0 <= i) && (i < numKeys()));
  
  _key[i] = new_val;
}


// Returns true if the node is full, or false otherwise
template<class K, class D>
int 
BTreeNode<K,D>::isFull(void)
{
  return (_numKeys == _maxNumKeys);
}


// Returns true if the node is below its minimum allowed size, or
// false otherwise.
template<class K, class D>
int 
BTreeNode<K,D>::isTooSmall(void)
{
  if (isRoot()) 
    return (_numKeys < 1);
  else if (_type == BTInternal)
    return ((_numKeys + 1) < (int) ((float) (_maxNumKeys + 1) / 2.0 + 0.6));
  else 
    return (_numKeys < (int) ((float) _maxNumKeys / 2.0 + 0.6));
}


// Returns true if the node is below its minimum allowed size, or
// false otherwise.
template<class K, class D>
int 
BTreeNode<K,D>::canRemoveKey(void)
{
  if (isRoot()) 
    return ((_numKeys - 1) >= 1);
  else if (_type == BTInternal)
    return (_numKeys >= (int) ((float) (_maxNumKeys + 1) / 2.0 + 0.6));
  else 
    return ((_numKeys - 1) >= (int) ((float) _maxNumKeys / 2.0 + 0.6));
}


// PRE: type() == BTLeaf, !isFull()
// Adds the data with the given key to the leaf.
template<class K, class D>
void 
BTreeNode<K,D>::addData(K key, D data)
{
  int cur_key = _numKeys;

  assert((type() == BTLeaf) && !isFull());

  while ((cur_key > 0) && (_key[cur_key - 1] > key)) {
    _key[cur_key] = _key[cur_key - 1];
    _data[cur_key] = _data[cur_key - 1];
    cur_key--;
  }

  _key[cur_key] = key;
  _data[cur_key] = data;
  _numKeys++;
}


// PRE: type() == BTInternal, !isFull()
//      all keys in the associated tree must be >= the key and <=
//      the next greatest key at the node;
// Adds a key and an associated subtree.  Set's the subtree's parent
// and sibling pointers appropriately.
template<class K, class D>
void 
BTreeNode<K,D>::addKey(K key, BTreeNode<K, D>* subtree)
{
  int cur_key = _numKeys;

  assert((type() == BTInternal) && !isFull());

  while ((cur_key > 0) && (_key[cur_key - 1] > key)) {
    _key[cur_key] = _key[cur_key - 1];
    _child[cur_key + 1] = _child[cur_key];
    cur_key--;
  }

  _key[cur_key] = key;
  _child[cur_key + 1] = subtree;

  subtree->_parent = this;
  subtree->_leftSib = _child[cur_key];
  _child[cur_key]->_rightSib = subtree;
  if (cur_key < _numKeys) {
    subtree->_rightSib = _child[cur_key + 2];
    _child[cur_key + 2]->_leftSib = subtree;
  }
  else {
    subtree->_rightSib = NULL;
  }

  _numKeys++;
}
 

// PRE: numKeys() == maxNumKeys(), 0 <= k < numKeys
// This function splits a full node so that the k smallest keys remain
// in the current node and the remainder get placed in a new node.
// However, the new node is *not* added to the tree; the user should
// add it to the parent of the original node.  The two parameters are
// output parameters, giving a pointer to the new node and its
// associated key.
template<class K, class D>
void 
BTreeNode<K,D>::split(int k, K& new_key, BTreeNode<K, D> *&new_node)
{
  assert((numKeys() == maxNumKeys()) && (0 <= k) && (k < _numKeys));

  int cp;
  BTreeNode<K,D> *result;

  if (type() == BTInternal) {
    result = new BTreeNode<K,D>(BTInternal, _maxNumKeys, NULL, NULL, 
				NULL, NULL);
    new_key = _key[k];
    _child[k]->_rightSib = NULL;
    result->_child[0] = _child[k + 1];
    result->_child[0]->_leftSib = NULL;
    result->_child[0]->_parent = result;
    for (cp = k + 1; cp < _numKeys; cp++) {
      result->_key[result->_numKeys] = _key[cp];
      result->_numKeys++;
      result->_child[result->_numKeys] = _child[cp + 1];
      result->_child[result->_numKeys]->_parent = result;
      result->_child[result->_numKeys]->_leftSib = 
	result->_child[result->_numKeys - 1];
      result->_child[result->_numKeys - 1]->_rightSib = 
	result->_child[result->_numKeys];
    }
    result->_child[result->_numKeys]->_rightSib = NULL;
  }
  else {
    result = new BTreeNode<K,D>(BTLeaf, _maxNumKeys, NULL, NULL, 
				NULL, NULL);
    new_key = _key[k];
    for (cp = k; cp < _numKeys; cp++) {
      result->_key[result->_numKeys] = _key[cp];
      result->_data[result->_numKeys] = _data[cp];
      result->_numKeys++;
    }
  }

  _numKeys = k;
  new_node = result;
}


// Returns the parent pointer of the node; may be NULL
template<class K, class D>
BTreeNode<K, D>* 
BTreeNode<K,D>::parent(void)
{
  return _parent;
}


// Returns the left sibling pointer of the node; may be NULL
template<class K, class D>
BTreeNode<K, D>* 
BTreeNode<K,D>::leftSibling(void)
{
  return _leftSib;
}


// Returns the right sibling pointer of the node; may be NULL
template<class K, class D>
BTreeNode<K, D>* 
BTreeNode<K,D>::rightSibling(void)
{
  return _rightSib;
}


// PRE: type() == BTLeaf and 0 <= idx < numKeys()
// Removes the (key, data) pair with the given index from the leaf.
// The key and data removed are placed in the key and data output
// parameters.
template<class K, class D>
void 
BTreeNode<K,D>::removeData(int idx, K& key, D& data)
{
  assert((type() == BTLeaf) && (0 <= idx) && (idx < _numKeys));

  int i;

  key = _key[idx];
  data = _data[idx];
  for (i = idx; (i + 1) < _numKeys; i++) {
    _key[i] = _key[i + 1];
    _data[i] = _data[i + 1];
  }
  _numKeys--;
}


// PRE: type() == BTInternal and 0 <= idx < numKeys()
// Removes the (key, subtree) pair with the given index from the node.
// The key and subtree removed are placed in the key and data output
// parameters, and the sibling pointers of the remaining subtrees
// are updated.
template<class K, class D>
void 
BTreeNode<K,D>::removeKey(int idx, K& key, BTreeNode<K,D>*& subtree)
{
  assert((type() == BTInternal) && (0 <= idx) && (idx < _numKeys));

  int i;

  key = _key[idx];
  subtree = _child[idx + 1];
  if (subtree->_leftSib) 
    subtree->_leftSib->_rightSib = subtree->_rightSib;
  if (subtree->_rightSib)
    subtree->_rightSib->_leftSib = subtree->_leftSib;
  subtree->detach();

  for (i = idx; (i + 1) < _numKeys; i++) {
    _key[i] = _key[i + 1];
    _child[i + 1] = _child[i + 2];
  }

  _numKeys--;
}


// PRE: type() == BTInternal; numKeys() >= 1
// This function removes the leftmost subtree of a node; the next node's
// sibling pointer is updated.  The former first key in the node becomes
// the key for the whole node; this key is placed in the key parameter.
// The removed subtree is placed in the old_left parameter.
template<class K, class D>
void 
BTreeNode<K,D>::removeLeftmost(K& key, BTreeNode<K,D>*& old_left)
{
  K dummy;
  BTreeNode<K,D> *removed;

  assert((type() == BTInternal) && (numKeys() >= 1));

  key = _key[0];
  old_left = _child[0];
  removeKey(0, dummy, removed);
  _child[0] = removed;
  _child[0]->_parent = this;
  if (_numKeys >= 1) {
    _child[0]->_rightSib = _child[1];
    _child[1]->_leftSib = _child[0];
  }
}


// PRE: type() == BTInternal; the replacement subtree's keys must be
//      less than all keys in the node.
// This function replaces the leftmost child of a node with a new
// subtree, whose parent and sibling pointers are updated appropriately.
// The former leftmost child is detached and returned through the output 
// parameter.
template<class K, class D>
void 
BTreeNode<K,D>::replaceLeftmost(BTreeNode<K,D>* new_left, 
				BTreeNode<K,D>*& old_left)
{
  assert(type() == BTInternal);

  old_left = _child[0];
  _child[0] = new_left;
  new_left->_parent = this;
  new_left->_leftSib = NULL;
  new_left->_rightSib = old_left->_rightSib;
  if (old_left->_rightSib)
    old_left->_rightSib->_leftSib = new_left;
}


// PRE: rightSibling() != NULL; 
//      numKeys() + rightSibling()->numKeys() <= maxNumKeys()
// Merges the node with its right sibling, and updates the parent of the
// nodes.  However, it does not delete or alter the parent node if its
// number of children drops below the minimum.

template<class K, class D>
void 
BTreeNode<K,D>::mergeWithRight(void)
{
  K dummy_key;
  BTreeNode<K,D> *dummy_node;
  int total_added = 0;
  int idx;

  if (_type == BTLeaf) {
    assert((_rightSib != NULL) && 
	   (_numKeys + _rightSib->_numKeys <= _maxNumKeys));

    while (total_added < _rightSib->_numKeys) {
      _key[_numKeys] = _rightSib->_key[total_added];
      _data[_numKeys] = _rightSib->_data[total_added];
      _numKeys++;
      total_added++;
    }

    for (idx = 0; _parent->_child[idx + 1] != _rightSib; idx++)
      /* no-op */ ;

    _parent->removeKey(idx, dummy_key, dummy_node);
  }
  else {
    assert((_rightSib != NULL) && 
	   (_numKeys + _rightSib->_numKeys + 1 <= _maxNumKeys));

    for (idx = 0; _parent->_child[idx + 1] != _rightSib; idx++)
      /* no-op */ ;
    _key[_numKeys] = _parent->_key[idx];
    _child[_numKeys + 1] = _rightSib->_child[0];
    _child[_numKeys + 1]->_parent = this;
    _child[_numKeys + 1]->_leftSib = _child[_numKeys];
    _child[_numKeys]->_rightSib = _child[_numKeys + 1];
    _numKeys++;
    
    while (total_added < _rightSib->_numKeys) {
      _key[_numKeys] = _rightSib->_key[total_added];
      _child[_numKeys + 1] = _rightSib->_child[total_added + 1];
      _child[_numKeys + 1]->_parent = this;
      _child[_numKeys + 1]->_leftSib = _child[_numKeys];
      _child[_numKeys]->_rightSib = _child[_numKeys + 1];
      _numKeys++;
      total_added++;
    }
    _child[_numKeys]->_rightSib = NULL;

    _parent->removeKey(idx, dummy_key, dummy_node);
  }

  delete dummy_node;
} 


// Sets the parent and sibling fields to NULL, thus "detaching" the
// subtree rooted at the node from the rest of the tree.  Helpful
// for removing the old root if it shrinks down to only one child.
template<class K, class D>
void 
BTreeNode<K,D>::detach(void)
{
  _parent = _leftSib = _rightSib = NULL;
}


// This function prints a representation of the node to the given stream.
// The parameter spc gives the number of spaces to indent each line by.
template<class K, class D>
void 
BTreeNode<K,D>::print(ostream& os, int spc)
{
  int i, j;

  if (type() == BTLeaf) {
    for (j = _numKeys - 1; j >= 0; j--) {
      for (i = 0; i < spc; i++) os << ' ';
      os << "( " << _key[j] << " , " << _data[j] << " )\n";
    }
    os << endl;
  }
  else {
    for (j = _numKeys - 1; j >= 0; j--) {
      for (i = 0; i < spc; i++) os << ' ';
      os << _key[j] << endl;
    }
  }
}