// From the software distribution accompanying the textbook
// "A Practical Introduction to Data Structures and Algorithm Analysis,
// Third Edition" by Clifford A. Shaffer, Prentice Hall, 2007.
// Source code Copyright (C) 2006 by Clifford A. Shaffer.

// This is an outline for a B+ tree implementation. Primarily,
// this code tests the syntax for the outline. It is not a working,
// concrete implementation.

#include <iostream>
using namespace std;

#include "book.h"

// Include comparator functions
#include "compare.h"

#define MAXREC 10
#define THRESHOLD 6

#include "BPnode.ht"

bool BPNode::isLeaf() const {}

bool BPNode::isFull() const {}

// For simplicity, we will assume that the key is of type int
template <class Elem, class getKey>
class BPTree {
private:
  BPNode* root;
  int reccount;
  bool findhelp(BPNode* root, const int& K, Elem*& e) const;
  bool inserthelp(BPNode* root, Elem* e, int& retval, void*& retptr);
  bool removehelp(BPNode* root, const int& K, Elem*& e);
public:
  BPTree() { root = NULL; reccount = 0; }
  ~BPTree() {};
  bool insert(Elem* e) { // Insert node with value val
    int retval;               // Smallest value in newly created node
    void* retptr = NULL; // Newly created node
    bool inssucc = inserthelp(root, e, retval, retptr);
    if (retptr != NULL) {      // Root overflowed: make new root
      BPNode* temp = new BPNode;
      temp->recs[0].pkey = root->recs[0].pkey;
      temp->recs[0].ptr = root;
      temp->recs[1].pkey = retval;
      temp->recs[1].ptr = retptr;
      root = temp;
    }
    if (inssucc) reccount++;
    return inssucc;
  }
  bool remove(const int& K, Elem*& e) {
    e = NULL;
    removehelp(root, K, e);
    return e != NULL;
  }
  bool find(const int& K, Elem*& e) const
    { return findhelp(root, K, e); }
};


int binaryle(PAIR* array, int numrec, int K) {}

// Find the record with a given key value
template <class Elem, class getKey>
bool BPTree<Elem, getKey>::
findhelp(BPNode* root, const int& K, Elem*& e) const {
  // function binaryle(A, n, K) performs a binary search,
  //   returning the index for the greatest value less than
  //   or equal to K in array A of length n.
  int currec = binaryle(root->recs, root->numrec, K);
  if (root->isLeaf())
    if (root->recs[currec].pkey == K) {
      e = (Elem*) root->recs[currec].ptr;
      return true;
    }
    else return false;
  else
    return findhelp((BPNode*)root->recs[currec].ptr, K, e);
}


void putinarray(PAIR* array, int currec, int retval, void* retptr) {}

void* splitnode(BPNode* root, int currect, int& myretv, void*& myretp) {}

// B+-tree pseudocode: insert
// binaryle(A, n, K) returns the greatest value less
//   than or equal to K in array A of length n.
// putinarray(A, pos, k, p) places in array A at
//   position pos the key/pointer pair k and p.
// splitnode(rt, pos, k, p) places in node rt at
//   position pos the key/pointer pair k/p.  In the process,
//   the node is split into two, each taking half of the
//   records, and the new node is returned.
template <class Elem, class getKey>
bool BPTree<Elem, getKey>::
inserthelp(BPNode* root, Elem* e,
           int& retval, void*& retptr) {
  int myretv;  // Least key in new node if current is split
  void* myretp = NULL; // Pointer to new node on split
  int K = getKey::key(e);

  int currec = binaryle(root->recs, root->numrec, K);
  if (root->isLeaf()) { // Leaf node: set insert values
    myretv = K;
    myretp = e;
  }
  else { // internal node
    inserthelp((BPNode*)root->recs[currec].ptr, e,
               myretv, myretp);
    if (myretp == NULL) return true; // Child did not split,
  }                     // no need to insert to current node

  // Do insert to the current node.  Split if necessary
  if (root->isLeaf() && (root->recs[currec].pkey == myretv))
    return false; // Duplicate
  if (!root->isFull())
    putinarray(root->recs, currec, myretv, myretp);
  else {
    retptr = splitnode(root, currec, myretv,myretp);
    retval = ((BPNode*)retptr)->recs[0].pkey;
  }
  return true;
}

void removerec(BPNode* root, int numrec, int currec) {}

void merge_nodes(BPNode* root, BPNode* right) {}

void shuffle_nodes(BPNode* root, BPNode* right) {}

// removehelp returns true if a child has been removed.
//   If so, adjustment to the current node is required.
// binaryle(A, n, K) returns the greatest value less than
//   or equal to K in array A of length n.
// removerec(A, n, c) removes record at position c from
//   array A with n records.
// merge_nodes(N1, N2) merges together the record arrays of
//   BPNodes N1 and N2.
// shuffle_nodes(N1, N2) copies execess records from BPNode
//   N2 to BPNode N1, so that both have equal # of records. 
template <class Elem, class getKey>
bool BPTree<Elem, getKey>::
removehelp(BPNode* root, const int& K, Elem*& retval) {
  int currec;

  currec = binaryle(root->recs, root->numrec, K);
  if (root->isLeaf())
    if (K != root->recs[currec].pkey)
      return false;
    else retval = (Elem*)root->recs[currec].ptr;
  else                        // Delete from child
    if (!removehelp((BPNode*) root->recs[currec].ptr,
                          K, retval))
       return false;          // Child did not collapse
  // Now, remove record at position currec
  removerec(root, root->numrec, currec);
  if (root->numrec > THRESHOLD) return false;
  else                        // Underflow
    if (root->lftptr == NULL) // No left neighbor
      if (root->numrec+root->rghtptr->numrec <= MAXREC) {
        merge_nodes(root, root->rghtptr);
        return true;
      }
      else {                  // Key value has changed
        shuffle_nodes(root, root->rghtptr);
        retval = (Elem*)root->rghtptr->recs[0].ptr;
        return false;
      }
    else if(root->numrec+root->lftptr->numrec <= MAXREC) {
      merge_nodes(root->lftptr, root);
      return true;
    }
    else {
      shuffle_nodes(root, root->lftptr);
      retval = (Elem*)root->recs[0].ptr;
      return false;
    }
}

int main()
{
  BPTree<Int, getIntsKey> tree;

  Int* it;
  tree.find(5, it);
  tree.insert(new Int(5));
  tree.remove(5, it);
  return 0;
}