// http://www.cs.msstate.edu/~cs2314/global/BTreeAnimation/algorithm.html
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <iostream>
#include "btree.h"
#include "inode.h"
#include "assert.h"

using namespace std;
#define VERIFY(x, y, z, n) if ((x) != (y)) { cout << "verify " << z << " failed" << endl; PrintWholeTree(); }

bTree::bTree(ubixfsInode * inode) : root(NULL) {
  treeDepth = 1;
  treeWidth = 0;
  treeLeafCount = 0;
  if (inode == NULL) return;
  root = allocEmptyNode();
  if (root == NULL) return;
  root->used = 1;
  root->parent = NULL;
  root->leaf = true;
  root->childCount[1] = 1;

// cout << "---Creating " << inode->name << "@" << inode << endl;
  strncpy(root->keys[0], inode->name, B_MAX_NAME_LENGTH);
  // insert pointer to data page to the right of the data
  root->head[1] = (void *)inode;
  root->tail[1] = (void *)inode;

  root->present[1] = true;
  if (inode != NULL) {
    inode->next = inode->prev = NULL;
  } // if
  return;
} // bTree:bTree

bool
bTree::Insert(ubixfsInode * inode) {
  bNode * bnode = root;
  ubixfsInode * tmpInode = NULL;
  unsigned int curSlot = 0;

  if (inode == NULL) return false;
 
  // note: this code is right out of the constructor
  if (root == NULL) {
    treeDepth = 1;
    treeWidth = 0;
    treeLeafCount = 0;
    root = allocEmptyNode();
    assert(root);
    if (root == NULL) return false;
    
    root->used = 1;
    root->parent = NULL;
    root->leaf = true;
    root->childCount[1] = 1;

    strncpy(root->keys[0], inode->name, B_MAX_NAME_LENGTH);
    // insert pointer to data page to the right of the data
    root->head[1] = (void *)inode;
    root->tail[1] = (void *)inode;

    root->present[1] = true;
    inode->next = inode->prev = NULL;
    return true;
  } // if
    
  tmpInode = Find(inode->name);
  if (tmpInode != NULL) return false;
//  PrintWholeTree();
// cout << "Insert(" << inode->name << ")" << endl;
//Info(bnode);
  ++treeLeafCount;
  /*
   * Find the leaf node the inode goes into
   */
  assert(bnode->used);
// cout << "---Inserting " << inode->name << "@" << inode << endl; 
  while (bnode != NULL && !bnode->leaf) {
    if (strcmp(inode->name, bnode->keys[0]) < 0) {
      bnode = (bNode *)bnode->head[0];
    } else {
      if (strcmp(inode->name, bnode->keys[bnode->used-1]) >= 0) {
        bnode = (bNode *)bnode->head[bnode->used];
      } else {
        for (unsigned int i = 1; i < bnode->used; i++) {
          if (strcmp(inode->name, bnode->keys[i]) < 0) {
            bnode = (bNode *)bnode->head[i];
            break;
          } // if
        } // for i
      } // else
    }
  } // while

  /*
   *
   */

assert(bnode);
if (bnode->leaf != true) cout << "leafnode!=true" << endl;
assert(inode);

  if (strcmp(inode->name, bnode->keys[curSlot = 0]) < 0)
    tmpInode = (ubixfsInode *)bnode->head[curSlot];
  else
    if (strcmp(inode->name, bnode->keys[(curSlot = bnode->used)-1]) >= 0)
      tmpInode = (ubixfsInode *)bnode->head[bnode->used];
    else {
      for (curSlot = 1; curSlot < bnode->used; curSlot++) {
        if (strcmp(inode->name, bnode->keys[curSlot]) < 0) {
          tmpInode = (ubixfsInode *)bnode->head[curSlot];
          break;
        } // if
      } // for curSlot
      tmpInode = (ubixfsInode *)bnode->head[curSlot];
    } // else


  if (tmpInode == NULL) {
    /*
     * This is the first node in this leaf
     */
    bnode->head[curSlot] = bnode->tail[curSlot] = inode;
    bnode->present[curSlot] = true;

    if (curSlot == 0) {

      if (bnode->head[1] != NULL)  {
        ubixfsInode * iptr = (ubixfsInode *)bnode->head[1];
        inode->prev = iptr->prev;
        inode->next = iptr;
        iptr->prev = inode;
        if (inode->prev != NULL) inode->prev->next = (ubixfsInode *)inode;
      } else {
        inode->next = inode->prev = NULL;
      } // else

    } else {
      ++bnode->used; 
    } // else

  } else {
    /*
     * Add node to leaf page. Scan through to find where it goes.
     */
    if (strcmp(inode->name, ((ubixfsInode *)bnode->head[curSlot])->name) < 0)
    {

      inode->next = (ubixfsInode *)bnode->head[curSlot];
      inode->prev = inode->next->prev;
      inode->next->prev = inode;
      if (inode->prev != NULL) inode->prev->next = inode;
      bnode->head[curSlot] = (void *)inode;

    } else {

      if (strcmp(inode->name, ((ubixfsInode *)bnode->tail[curSlot])->name) > 0) {

        inode->prev = (ubixfsInode *)bnode->tail[curSlot];
        inode->next = inode->prev->next;
        inode->prev->next = inode;

        if (inode->next != NULL) inode->next->prev = inode;
        bnode->tail[curSlot] = inode;

      } else {


        ubixfsInode * tmpInode = (ubixfsInode *)bnode->head[curSlot];
        for (unsigned int i = 0; i < bnode->childCount[curSlot]; i++) {
          if (strcmp(inode->name, tmpInode->name) < 0) {
            inode->next = tmpInode;
            inode->prev = tmpInode->prev;
            inode->next->prev = inode;
            inode->prev->next = inode;
            break;
          } // if
          tmpInode = tmpInode->next; 
        } // for i

      } // else

    } // else

  } // else



  if (++bnode->childCount[curSlot] == B_MAX_CHILD_COUNT) {

// cout << "---- before split ----" << endl;
// Info(bnode);

    if (curSlot != bnode->used) {
      int shift = bnode->used - curSlot +1;

      memmove(&bnode->head[curSlot+1],
              &bnode->head[curSlot],
              sizeof(bnode->head[0]) * shift);
      memmove(&bnode->tail[curSlot+1],
              &bnode->tail[curSlot],
              sizeof(bnode->tail[0]) * shift);
      memmove(&bnode->present[curSlot+1],
              &bnode->present[curSlot],
              sizeof(bnode->present[0]) * shift);
      memmove(&bnode->childCount[curSlot+1],
              &bnode->childCount[curSlot],
              sizeof(bnode->childCount[0]) * shift);

      memmove(&bnode->keys[curSlot+1],
              &bnode->keys[curSlot],
              sizeof(bnode->keys[0]) * (shift-1));
      memset(bnode->keys[curSlot], 0, B_MAX_NAME_LENGTH);
    } else {
      bnode->head[curSlot+1] = bnode->head[curSlot];
      bnode->tail[curSlot+1] = bnode->tail[curSlot];
      bnode->childCount[curSlot+1] = bnode->childCount[curSlot];
      bnode->present[curSlot+1] = bnode->present[curSlot];
    } // else

    ubixfsInode * tmpInode = (ubixfsInode *)bnode->head[curSlot];

    for (unsigned int i = 0; i < (B_MAX_CHILD_COUNT+1) >> 1; i++) {
      assert(tmpInode);
      tmpInode = tmpInode->next;
    } // for i

    strncpy(bnode->keys[curSlot], tmpInode->name, B_MAX_NAME_LENGTH);
    bnode->head[curSlot+1] = (void *)tmpInode;
    bnode->tail[curSlot] = (void *)tmpInode->prev;
    bnode->childCount[curSlot] = (B_MAX_CHILD_COUNT+1) >> 1;
    bnode->childCount[curSlot+1] -= bnode->childCount[curSlot];
    bnode->present[curSlot] = true;
    ++treeWidth;
    if (++bnode->used == B_MAX_KEYS) splitNode(bnode);

  } // if leaf is full
// Info(bnode);
  return true;
} // bTree::Insert

void 
bTree::splitNode(bNode * oldNode) {
  ubixfsInode * tmpInode = NULL;
  assert(oldNode);
  if (oldNode == NULL) return;
  if (oldNode->used != B_MAX_KEYS) return;

  bNode * newNode = allocEmptyNode();
  if (newNode == NULL) return;

  unsigned int shift = B_MAX_KEYS >> 1;
  unsigned int splitLoc = B_MAX_KEYS - shift;
  ++ shift;
// cout << "oldNode before split: " << endl;
// Info(oldNode);
// cout << "splitLoc: " << splitLoc << endl;
// cout << "shift: " << shift << endl;

  newNode->used = oldNode->used = B_MAX_KEYS >> 1;
  newNode->parent = oldNode->parent;
  assert(newNode->parent != oldNode);
  assert(oldNode->parent != newNode);
  newNode->leaf = oldNode->leaf;

// cout << "newNode->used: " << newNode->used << endl;
// cout << "oldNode->used: " << oldNode->used << endl;

  memcpy(&newNode->keys[0],
         &oldNode->keys[splitLoc],
         sizeof(newNode->keys[0]) * (shift-1));
  
  memset(&oldNode->keys[splitLoc], 0, sizeof(newNode->keys[0]) * (shift-1));

  memcpy(&newNode->present[0],
         &oldNode->present[splitLoc],
         sizeof(newNode->present[0]) * shift);

  memset(&oldNode->present[splitLoc], 0, sizeof(newNode->present[0]) * shift);

  memcpy(&newNode->head[0],
         &oldNode->head[splitLoc],
         sizeof(newNode->head[0]) * shift);

  memset(&oldNode->head[splitLoc], 0, 
         sizeof(newNode->head[0]) * shift);

  memcpy(&newNode->tail[0],
         &oldNode->tail[splitLoc],
         sizeof(newNode->tail[0]) * shift);

  memset(&oldNode->tail[splitLoc], 0, 
         sizeof(newNode->tail[0]) * shift);

  memcpy(&newNode->childCount[0],
         &oldNode->childCount[splitLoc],
         sizeof(newNode->childCount[0]) * shift);

  memset(&oldNode->childCount[splitLoc], 0, 
         sizeof(newNode->childCount[0]) * shift);

  if (!newNode->leaf) {
    for (unsigned int i = 0; i <= newNode->used; i++) {
      ((bNode *)newNode->head[i])->parent = newNode;
    } // for i
  } // if newNode isn't a leaf

  tmpInode = GetFirstNode(newNode);
  assert(tmpInode);

  if (oldNode == root) {
    // allocate a new root node
    ++treeDepth;
    root = allocEmptyNode();
    oldNode->parent = root;
    newNode->parent = root;
 //   strncpy(root->keys[0], newNode->keys[0], B_MAX_NAME_LENGTH);
    strncpy(root->keys[0], tmpInode->name, B_MAX_NAME_LENGTH);
    root->head[0] = oldNode;
    root->tail[0] = root->tail[1] = NULL;
    root->head[1] = newNode;
    root->used = 1;
    root->leaf = false;
    root->present[0] = root->present[1] = true;
    root->childCount[0] = root->childCount[1] = 0;
//    root->childCount[0] = oldNode->used;
//    root->childCount[1] = newNode->used;

// cout << "parent" << endl;
// Info(newNode->parent);
// cout << "oldNode" << endl;
// Info(oldNode);
// cout << "-----" << endl;
// cout << "newNode" << endl;
// Info(newNode);
// cout << "-----" << endl;

  } else {
    assert(newNode->parent != oldNode);
    assert(oldNode->parent != newNode);
    insertNode(newNode->parent, tmpInode->name, newNode, NULL);
    assert(newNode->parent != oldNode);
    assert(oldNode->parent != newNode);
   // if (oldNode->parent->used == B_MAX_KEYS) splitNode(oldNode->parent);
  } // else
  assert(newNode->parent != oldNode);
  assert(oldNode->parent != newNode);
  return;
} // bTree::splitNode

void
bTree::insertNode(bNode * node, const char * key, 
                  void * headPtr, void * tailPtr) {
  unsigned int curSlot = 0;
  if (node == NULL || key == NULL) return;

  if (strcmp(key, node->keys[node->used-1]) >= 0){
    curSlot = node->used;
    memset(node->keys[curSlot], 0, B_MAX_NAME_LENGTH);
    strncpy(node->keys[curSlot], key, B_MAX_NAME_LENGTH);
    node->head[curSlot+1] = headPtr;
    node->tail[curSlot+1] = tailPtr;
    node->present[curSlot+1] = true;
    node->childCount[node->used] = 0; // maybe?

  } else {

    for (curSlot = 0; curSlot < node->used; curSlot++) {
      if (strcmp(key, node->keys[curSlot]) < 0) break;
    } // for 

    /*
     * note that there is one more item for everything but keys
     * So, make the shift count +1 and just subtract it from the key shift
     * later
     */
    int shift = node->used - curSlot +1;

    memmove(&node->head[curSlot+1],
            &node->head[curSlot],
            sizeof(node->head[0]) * shift);
    memmove(&node->tail[curSlot+1],
            &node->tail[curSlot],
            sizeof(node->tail[0]) * shift);
    memmove(&node->present[curSlot+1],
            &node->present[curSlot],
            sizeof(node->present[0]) * shift);
    memmove(&node->childCount[curSlot+1],
            &node->childCount[curSlot],
            sizeof(node->childCount[0]) * shift);

    memmove(&node->keys[curSlot+1],
            &node->keys[curSlot],
            sizeof(node->keys[0]) * (shift-1));
    
    memset(node->keys[curSlot], 0, B_MAX_NAME_LENGTH);
    strncpy(node->keys[curSlot], key, B_MAX_NAME_LENGTH);
    node->head[curSlot+1] = headPtr;
    node->tail[curSlot+1] = tailPtr;
    node->present[curSlot+1] = true;
//    node->childCount[node->used] = ?;
  } // else 
  if (++node->used == B_MAX_KEYS) splitNode(node); 
  return;
} // bTree::insertNode

bNode *
bTree::allocEmptyNode(void) {
  bNode * newNode = (bNode *)malloc(sizeof(bNode));

  memset(newNode, 0, sizeof(bNode));
  newNode->magic1 = B_NODE_MAGIC_1;
  newNode->magic2 = B_NODE_MAGIC_2;
  newNode->parent = NULL;
 
  return newNode;
} // bTree::allocEmptyNode

void
bTree::Info(const bNode * node) {
  ubixfsInode * inode = NULL;
  if (node == NULL) return;
  cout <<  node << " | " << node->parent << endl;
  for (unsigned int i = 0; i <= node->used; i++) {
    inode = (ubixfsInode *)node->head[i];
//    cout << "(" << node->childCount[i] << ")";
    for (unsigned int k = 0; k < node->childCount[i]; k++) {
      cout << "[" << inode->name << "]";
      inode = inode->next;
    } // for k
    if (i != node->used) cout << " {" << node->keys[i] << "} ";
  } // for i
  cout << endl;
  return;
#if 0
  for (unsigned int i = 0; i < node->used; i++) {
    cout << "keys[" << i << "]: " << node->keys[i] << "  ";
  } // for i
  cout << endl;
  cout << "node->used: " << node->used << endl;
  cout << "leaf: " << node->leaf << endl;
  for (unsigned int i = 0; i <= node->used; i++) {
    inode = (ubixfsInode *)node->head[i];
cout << "node->childCount["<<i<<"]: " << node->childCount[i] << endl;
    for (unsigned int j = 0; j < node->childCount[i]; j++) {
      assert(inode);
      cout << "[" << i << "].[" << j << "]->" << inode->name << endl;
      inode = inode->next;
    } // for j
  } // for i
#endif
} // bTree::Info

void
bTree::Info(void) {
  ubixfsInode * inode = NULL;
  if (root == NULL) return;
  for (unsigned int i = 0; i <= root->used; i++) {
    cout << "CC[" << i << "]: " << root->childCount[i] << "  ";
  } // for i

  cout << endl;
  for (unsigned int i = 0; i <= root->used; i++) {
    cout << "CH[" << i << "]: " << root->head[i] << "  ";
  } // for i

  cout << endl;
  for (unsigned int i = 0; i <=root->used; i++) {
    cout << "CT[" << i << "]: " << root->tail[i] << "  ";
  } // for i
  cout << endl;
  for (unsigned int i = 0; i < root->used; i++) {
    cout << "keys[" << i << "]: " << root->keys[i] << "  ";
  } // for i
  cout << endl;

cout << "root->used: " << root->used << endl;
    for (unsigned int i = 0; i <= root->used; i++) {
      inode = (ubixfsInode *)root->head[i];
cout << "root->childCount["<<i<<"]: " << root->childCount[i] << endl;
    if (root->leaf) {
cout << "root contains leaf node" << endl;
      for (unsigned int j = 0; j < root->childCount[i]; j++) {
        assert(inode);
        cout << "[" << i << "].[" << j << "]->" << inode->name << endl;
        inode = inode->next;
      } // for j
    } // if root->leaf
  } // for i
} // bTree::Info

void
bTree::Print(void) {
  ubixfsInode * node = GetFirstNode();
  while (node != NULL) {
    cout << node->name << endl;
    node = node->next;
  }
} // bTree::Print

ubixfsInode *
bTree::Find(const char * key) {
  ubixfsInode * tmp = GetFirstNode();
  while (tmp!=NULL) {
    if (strcmp(tmp->name, key) == 0) return tmp;
    tmp = tmp->next;
  }
  return NULL;
//  return treeSearch(root, key);
} // bTree::Find

ubixfsInode *
bTree::inodeSearch(ubixfsInode * inode, const char * key) {
  if (inode == NULL || key == NULL) return NULL;
  int result = strcmp(inode->name, key);
  if (result == 0) return inode;

  if (result < 0) {
    inode = inode->next;
    while (inode != NULL && ((result = strcmp(inode->name, key)) < 0)) {
      inode = inode->next;
    } // while
  } else {
    inode = inode->prev;
    while (inode != NULL && ((result = strcmp(inode->name, key)) > 0)) {
      inode = inode->prev;
    } // while
  } // else
  return (result == 0 ? inode : NULL);
} // bTree::inodeSearch

ubixfsInode *
bTree::treeSearch(bNode * bnode, const char * key) {

  if (bnode == NULL || key == NULL || bnode->used == 0) return NULL;
 
  if (bnode->leaf) 
    return inodeSearch(GetFirstNode(bnode), key);
/*
 *   if (bnode->head[0] != NULL) 
 *     return inodeSearch((ubixfsInode *)bnode->head[0], key);
 *   else
 *     return inodeSearch((ubixfsInode *)bnode->head[1], key);
 */
// cout << "key: " << key << "  keys[0]: " << bnode->keys[0] << "  result: " << strcmp(key, bnode->keys[0]) << endl;

  if (strcmp(key, bnode->keys[0]) < 0) 
    return treeSearch((bNode *)bnode->head[0], key);

  if (strcmp(key, bnode->keys[bnode->used-1]) >= 0)
    return treeSearch((bNode *)bnode->head[bnode->used], key);

  for (unsigned int i = 1; i < bnode->used; i++) {
    if (strcmp(key, bnode->keys[i]) < 0) 
      return treeSearch((bNode *)bnode->head[i], key);
  } // for i

  return NULL;
} // bTree::treeSearch

ubixfsInode * 
bTree::GetFirstNode(void) {
  return GetFirstNode(root);
} // bTree::GetFirstNode

ubixfsInode *
bTree::GetFirstNode(bNode * node) {
  bNode * tmpNode = node;

  if (tmpNode == NULL) return NULL;

  while (!tmpNode->leaf) {
    for (unsigned int i = 0; i < tmpNode->used; i++) {
      if (tmpNode->head[i] != NULL) {
        tmpNode = (bNode *)tmpNode->head[i];
        break;
      }  // if
    } // for i
  } // while

  for (unsigned int i = 0; i < tmpNode->used; i++) {
    if (tmpNode->head[i] != NULL) return (ubixfsInode * )tmpNode->head[i];
  } // for i
  return NULL;
} // bTree::GetFirstNode

bNode *
bTree::findLeafNode(bNode * node, const char * key) {
  assert(node);
  assert(key);
  if (node == NULL || key == NULL) return NULL;
  assert(node->used);
  if (node->leaf) return node;

  if (strcmp(key, node->keys[0]) < 0) 
    return findLeafNode((bNode *)node->head[0], key);

  if (strcmp(key, node->keys[node->used-1]) >= 0) 
    return findLeafNode((bNode *)node->head[node->used], key);
  
  for (unsigned int i = 1; i < node->used; i++) {
    if (strcmp(key, node->keys[i]) < 0) 
      return findLeafNode((bNode *)node->head[i], key);
  } // for i
  
  return NULL;
} // bTree::findLeafNode

bool 
bTree::Save(const char * filename) {
  if (filename == NULL) return false;
  
  return true;
} // bTree::Save

bool
bTree::Load(const char * filename) {
  if (filename == NULL) return false;
  return true;
} // bTree::Load

bool
bTree::Delete(const char * key) {

  if (key == NULL) return false;
  return true;
} // bTree::Delete

bool
bTree::Verify(void) {
  ubixfsInode * node = GetFirstNode();
  if (node == NULL) return true;
 
  while (node != NULL) {
    ubixfsInode * next = node->next;
    if (next != NULL) {
  //  cout << node->name << "::" << node->next->name << ":::" << strcmp(node->name, node->next->name) << endl;
      if (strcmp(node->name, next->name) > 0) return false;
    }
    node = next;
  } // while
  return true;
} // bTree::Verify

void 
bTree::Print(bNode * node) {
  if (node == NULL) return;
  Info(node);
  if (!node->leaf)
    for (unsigned int i = 0; i <= node->used; i++) {
      Print((bNode *)node->head[i]);
    } // for i
} // bTree::Print

void
bTree::PrintWholeTree(void) {
  Print(root);
} // bTree::PrintWholeTree;

bTree::~bTree(void) {
  cout << "tree depth: " << treeDepth << endl;
  cout << "tree width: " << treeWidth << endl;
  cout << "tree leaf count: " << treeLeafCount << endl;
} // bTree::~bTree