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


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

cout << "---Creating " << inode->name << "---" << endl;
  strncpy(root->keys[0], inode->name, B_MAX_NAME_LENGTH);
  // insert pointer to data page to the right of the data
  root->childHead[1] = (void *)inode;
  root->childTail[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 (bnode == NULL || inode == NULL) return false;

  /*
   * Find the leaf node the inode goes into
   */
  assert(bnode->used);
 
  while (bnode != NULL && !bnode->leafNode) {
    if (strcmp(inode->name, bnode->keys[0] < 0))
      bnode = (bNode *)bnode->childHead[0];
    else
      if (strcmp(inode->name, bnode->keys[bnode->used-1]) >= 0)
        bnode = (bNode *)bnode->childHead[bnode->used];
      else {
        for (unsigned int i = 1; i < bnode->used; i++) {
          if (strcmp(inode->name, bnode->keys[i]) < 0) {
            bnode = (bNode *)bnode->childHead[i];
            break;
          } // if
        } // for i
      } // else
  } // while

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

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

    if (curSlot == 0) {

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

  } else {
    /*
     * Add node to leaf page. Scan through to find where it goes.
     */

    if (strcmp(inode->name, ((ubixfsInode *)bnode->childHead[curSlot])->name) < 0)
    {
      inode->next = (ubixfsInode *)bnode->childHead[curSlot];
      inode->prev = inode->next->prev;
      inode->next->prev = inode;
      if (inode->prev != NULL) inode->prev->next = inode;
      bnode->childHead[curSlot] = (void *)inode;
    } else 
      if (strcmp(inode->name, ((ubixfsInode *)bnode->childTail[curSlot])->name) > 0) {
        inode->prev = (ubixfsInode *)bnode->childTail[curSlot];
        inode->next = inode->prev->next;
        inode->prev->next = inode;
        if (inode->next != NULL) inode->next->prev = inode;
        bnode->childTail[curSlot] = inode;
      } else {
        ubixfsInode * tmpInode = (ubixfsInode *)bnode->childHead[curSlot];
        for (unsigned int i = 1; i < bnode->childCount[curSlot]; i++) {
// cout << "strcmp(" << inode->name << ", " << tmpInode->name << ") == " << 
// strcmp(inode->name, tmpInode->name) << endl;
          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

  if (++bnode->childCount[curSlot] == B_MAX_CHILD_COUNT) {
    cout << "slot[" << curSlot << "] is full" << endl;
    cout << "slot[" << curSlot+1 << "]->childCount is: " << bnode->childCount[curSlot+1] << endl; 
cout << "---- before split ----" << endl;
    Info();
    if (curSlot != bnode->used) {
      int shift = bnode->used - curSlot +1;
cout << "shift: " << shift << endl;
      memmove(&bnode->childHead[curSlot+1],
              &bnode->childHead[curSlot],
              sizeof(bnode->childHead[0]) * shift);
      memmove(&bnode->childTail[curSlot+1],
              &bnode->childTail[curSlot],
              sizeof(bnode->childTail[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->childHead[curSlot+1] = bnode->childHead[curSlot];
      bnode->childTail[curSlot+1] = bnode->childTail[curSlot];
      bnode->childCount[curSlot+1] = bnode->childCount[curSlot];
      bnode->present[curSlot+1] = bnode->present[curSlot];
    } // else

    ubixfsInode * tmpInode = (ubixfsInode *)bnode->childHead[curSlot];
    assert(tmpInode);
    for (unsigned int i = 0; i < (B_MAX_CHILD_COUNT+1) >> 1; i++) {
      tmpInode = tmpInode->next;
    } // for i

    strncpy(bnode->keys[curSlot], tmpInode->name, B_MAX_NAME_LENGTH);
    bnode->childHead[curSlot+1] = (void *)tmpInode;
    bnode->childTail[curSlot] = (void *)tmpInode->prev;
    bnode->childCount[curSlot] = (B_MAX_CHILD_COUNT+1) >> 1;
    bnode->childCount[curSlot+1] -= bnode->childCount[curSlot];
    bnode->present[curSlot] = true;
    ++bnode->used;
cout << "--- After split ---" << endl;
Info();
  } // if leaf is full

  return true;
} // bTree::Insert

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

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

  unsigned int splitLoc = (B_MAX_KEYS+1) >> 1;
  unsigned int shift = B_MAX_KEYS - splitLoc;

  newNode->used = (B_MAX_KEYS+1) >> 1;
  newNode->parent = oldNode->parent;
  newNode->leafNode = oldNode->leafNode;

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

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

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

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

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

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

  memset(&oldNode->childTail[splitLoc], 0, sizeof(newNode->childTail[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 (oldNode == root) {
    // allocate a new root node
    root = allocEmptyNode();
    oldNode->parent = root;
    newNode->parent = root;
    strncpy(root->keys[0], newNode->keys[0], B_MAX_NAME_LENGTH);
    root->childHead[0] = oldNode;
    root->childTail[0] = root->childTail[1] = NULL;
    root->childHead[1] = newNode;
    root->used = 1;
    root->leafNode = false;
    root->present[0] = root->present[1] = true;
    root->childCount[0] = oldNode->used;
    root->childCount[1] = newNode->used;
  } else {
    if (++oldNode->parent->used == B_MAX_KEYS) splitNode(oldNode->parent);
  } // esle
  return;
} // bTree::splitNode

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;
 
  return newNode;
} // bTree::allocEmptyNode

void
bTree::Info(void) {
  ubixfsInode * inode = NULL;
  if (root == NULL) return;
  cout << "root->used: " << root->used << endl;
  for (unsigned int i = 0; i <= root->used; i++) {
    inode = (ubixfsInode *)root->childHead[i];
cout << "root->childCount[i]: " << root->childCount[i] << endl;
    for (unsigned int j = 0; j < root->childCount[i]; j++) {
      assert(inode);
      cout << "[" << i << "].[" << j << "]->" << inode->name << endl;
      inode = inode->next;
    } // for j
  } // 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) {
  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) return NULL;
 
  if (bnode->used == 0) return NULL;
  if (bnode->leafNode) 
    if (bnode->childHead[0] != NULL) 
      return inodeSearch((ubixfsInode *)bnode->childHead[0], key);
    else
      return inodeSearch((ubixfsInode *)bnode->childHead[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->childHead[0], key);

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

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

  return NULL;
} // bTree::treeSearch

ubixfsInode *
bTree::GetFirstNode(void) {
  bNode * tmpNode = root;
  if (tmpNode == NULL) return NULL;
 
  if (root->leafNode) {
    if (root->used == 0) return NULL;
    if (root->used == 1 && root->childHead[0] == NULL) 
      return (ubixfsInode *) root->childHead[1];
    else
      return (ubixfsInode *) root->childHead[0];
  }  // if
  while (!tmpNode->leafNode) tmpNode = (bNode *)tmpNode->childHead[0];
  return (ubixfsInode *)tmpNode->childHead[0];
} // bTree::GetFirstNode

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