// 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"

using namespace std;

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 << "@" << inode << 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;
  tmpInode = Find(inode->name);
  if (tmpInode != NULL) cout << tmpInode->name << " " << inode->name << endl;
  /*
   * Find the leaf node the inode goes into
   */
  assert(bnode->used);
//  cout << "---Inserting " << inode->name << "@" << inode << endl; 
  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

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

  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 {
      for (curSlot = 1; curSlot < bnode->used; curSlot++) {
        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 << "---- before split ----" << endl;
// cout << "slot[" << curSlot << "] is full" << endl;
// cout << "slot[" << curSlot+1 << "]->childCount is: " << bnode->childCount[curSlot+1] << 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];
// cout << "childCount[" << curSlot << "] : " << bnode->childCount[curSlot] << endl;
// cout << "childCount[" << curSlot+1 << "] : " << bnode->childCount[curSlot+1] << endl;
    bnode->present[curSlot] = true;
    if (++bnode->used == B_MAX_KEYS) splitNode(bnode);
// cout << "--- After split ---" << endl;
// Info();
  } // if leaf is full

  return true;
} // bTree::Insert

void 
bTree::splitNode(bNode * oldNode) {
// cout << "---in splitNode()---" << endl;
  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;

// cout << "splitLoc: " << splitLoc << "   shift: " << shift << endl;
  newNode->used = shift;
  newNode->parent = oldNode->parent;
  newNode->leafNode = oldNode->leafNode;
  oldNode->used -= newNode->used+1;

  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+1));

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

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

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

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

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

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

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

  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;
//cout << "---root node begin---" << endl;
//    Info();
//cout << "---root node end---" << endl;
  } else {
    insertNode(oldNode->parent, newNode->keys[0], newNode, NULL);
    if (oldNode->parent->used == B_MAX_KEYS) splitNode(oldNode->parent);
  } // else
// cout << "---oldNode begin---" << endl;
//   Info(oldNode);
// cout << "---oldNode end---" << endl;
// cout << "---newNode---" << endl;
//  Info(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->childHead[curSlot+1] = headPtr;
    node->childTail[curSlot+1] = tailPtr;
    node->present[curSlot+1] = true;
//    node->childCount[node->used] = ?;

  } 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->childHead[curSlot+1],
            &node->childHead[curSlot],
            sizeof(node->childHead[0]) * shift);
    memmove(&node->childTail[curSlot+1],
            &node->childTail[curSlot],
            sizeof(node->childTail[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->childHead[curSlot+1] = headPtr;
    node->childTail[curSlot+1] = tailPtr;
    node->present[curSlot+1] = true;
//    node->childCount[node->used] = ?;
  } // else 
  ++node->used; 
  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;
 
  return newNode;
} // bTree::allocEmptyNode

void
bTree::Info(const bNode * node) {
  ubixfsInode * inode = NULL;
  if (node == NULL) return;

  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;
  for (unsigned int i = 0; i <= node->used; i++) {
    inode = (ubixfsInode *)node->childHead[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
} // 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->childHead[i] << "  ";
  } // for i

  cout << endl;
  for (unsigned int i = 0; i <=root->used; i++) {
    cout << "CT[" << i << "]: " << root->childTail[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->childHead[i];
cout << "root->childCount["<<i<<"]: " << root->childCount[i] << endl;
    if (root->leafNode) {
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->leafNode
  } // 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;
  while (!tmpNode->leafNode) {
    for (unsigned int i = 0; i < tmpNode->used; i++) {
      if (tmpNode->childHead[i] != NULL) {
        tmpNode = (bNode *)tmpNode->childHead[i];
        break;
      }  // if
    } // for i
  } // while

  for (unsigned int i = 0; i < tmpNode->used; i++) {
    if (tmpNode->childHead[i] != NULL) return (ubixfsInode * )tmpNode->childHead[i];
  }
  return NULL;
} // 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