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

#ifndef _BTREENODE_H_
#define _BTREENODE_H_

#include <iostream.h>

enum BTreeNodeType { BTInternal, BTLeaf };

template <class K, class D>
class BTreeNode {

public:

  /* 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.
   */
  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);
  ~BTreeNode();

  // Returns the type of the node, either BTInternal, BTLeaf.
  BTreeNodeType type(void);

  // Returns true if and only if the node is the root of a tree.
  int isRoot(void);

  // PRE: type() == BTLeaf, 0 <= idx < numKeys()
  // Returns the data associated with the key at index idx.
  D getData(int idx);

  // PRE: type() == BTInternal, 0 <= idx < (numKeys() + 1)
  // Returns child number idx from the node (numbered left to right).
  BTreeNode<K, D> *getChild(int 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.
  int numKeys(void);

  // Returns the maximum number of keys which can be stored at the
  // node.
  int maxNumKeys(void);

  // PRE: 0 <= i < numKeys()
  // Returns key number i from the node.
  K getKey(int i);

  // PRE: 0 <= i < numKeys()
  // Sets key number i to a new value.
  void setKey(int i, K new_val);

  // Returns true if the node is full, or false otherwise
  int isFull(void);

  // Returns true if the node is below its minimum allowed size, or
  // false otherwise.
  int isTooSmall(void);

  // Returns true if the node may have an element removed and still
  // remain above its minimum size, or false otherwise.
  int canRemoveKey(void);

  // PRE: type() == BTLeaf, !isFull()
  // Adds the data with the given key to the leaf.
  void addData(K key, D data);

  // 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.
  void addKey(K key, BTreeNode<K, D>* subtree);
  
  // 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.
  void split(int k, K& new_key, BTreeNode<K, D> *&new_node);

  // Returns the parent pointer of the node; may be NULL
  BTreeNode<K,D>* parent(void);

  // Returns the left sibling pointer of the node; may be NULL
  BTreeNode<K,D>* leftSibling(void);

  // Returns the right sibling pointer of the node; may be NULL
  BTreeNode<K,D>* rightSibling(void);

  // 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.
  void removeData(int idx, K& key, D& data);

  // 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.
  void removeKey(int idx, K& key, BTreeNode<K,D>*& subtree);

  // 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.
  void removeLeftmost(K& key, BTreeNode<K,D>*& old_left);

  // 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.
  void replaceLeftmost(BTreeNode<K,D>* new_left, BTreeNode<K,D>*& old_left);

  // PRE: rightSibling() != NULL; 
  //      numKeys() + rightSibling()->numKeys() <= maxNumKeys() [for leaf]
  //      numKeys() + rightSibling()->numKeys() + 1 <= maxNumKeys() [internal]
  // 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.
  void mergeWithRight(void);

  // 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.
  void detach(void);

  // 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.
  void print(ostream& os, int spc);

private:

  BTreeNodeType _type;
  BTreeNode<K, D> *_parent, *_rightSib, *_leftSib;
  int _maxNumKeys;
  int _numKeys;
  K *_key;
  union {
    BTreeNode<K, D> **_child;
    D *_data;
  };
};

#endif