// 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 = (bNode *)malloc(sizeof(bNode));
  if (root == NULL) return;
  memset(root, 0, sizeof(bNode));
  root->magic1 = B_NODE_MAGIC_1;
  root->magic2 = B_NODE_MAGIC_2;
  root->used = 1;
  root->parent = NULL;
  root->leafNode = 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->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

  /*
   *
   */

  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
    } // 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;
      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);
      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

#if 0
  if (strcmp(inode->name, bnode->key[0]) < 0) {
    if (bnode->leafNode) {
      
    }   
  } else {
    if (strcmp(inode->name, bnode->key[bnode->used]) >= 0) {
    } else {
    }
  } // else
  if (bnode->leafNode) {
    if 
    for (unsigned int i = 0; i 
  } else {

  } // else

  /*
   * first search to see if the key we're looking for already exists
   * This may not be necessary, since if you've already allocated an
   * i-node you might have looked first. But, we'll leave it in as a sanity
   * check
   */

  assert(bnode->used);
restart:
  for (unsigned int i = 0; i <= tmpNode->used; i++) {
    if (i == tmpNode->used) goto skipCheck;
cout << "checking " << inode->name << " against " << tmpNode->keys[i];
    result = strcmp(inode->name, tmpNode->keys[i]);
cout << "   result: " << result << endl;
    if (result < 0) {
      // our key is less than this key. Walk left
skipCheck:
      // if we're in leaf nodes, just add it to the data page in the right
      // place
      if (tmpNode->leafNode) {
        ubixfsInode * tmpInode = (ubixfsInode *)tmpNode->childHead[i];

        // is this the first node in this data page?
        if (tmpInode == NULL) {
          if (i > 0)
            inode->prev = (ubixfsInode *)tmpNode->childTail[i-1];
           else 
            inode->prev = NULL;

          if (i < B_MAX_KEYS) 
            inode->next = (ubixfsInode *)tmpNode->childHead[i+1];
          else
            inode->next = NULL;
          tmpNode->childHead[i] = tmpNode->childTail[i] = inode;
          if (i != 0) ++tmpNode->used;
        } else {

cout << "CC[" << i << "]: " << tmpNode->childCount[i] << endl;
          for (unsigned int j = 0; j <= tmpNode->childCount[i]; j++) {
            if (j == tmpNode->childCount[i]) {
              assert(tmpInode);
              assert(inode);
              inode->prev = tmpInode;
              inode->next = tmpInode->next;
              tmpInode->next = inode;
           //   if (inode->next != NULL) inode->next->prev = inode;
              tmpNode->childTail[i] = inode;
              break;
            } // if 
assert(inode);
assert(tmpInode);
cout << inode->name << endl;
cout << tmpInode->name << endl;
            if (strcmp(inode->name, tmpInode->name) < 0) {
              inode->next = tmpInode;
              inode->prev = tmpInode->prev;
              tmpInode->prev = inode;
              if (j == 0) tmpNode->childHead[i] = inode;
              break;
            } // if
cout << "here2" << endl;
            tmpInode = tmpInode->next;
cout << "here3" << endl;
          } // for j
       
        } // else
assert(inode);
        if (inode->prev != NULL) inode->prev->next = inode;
        if (inode->next != NULL) inode->next->prev = inode;

        if (++tmpNode->childCount[i] == B_MAX_CHILD_COUNT) {
          ubixfsInode * tmpInode = (ubixfsInode *)tmpNode->childHead[i];
          assert(tmpInode);

          for (int k = 0; k < ((B_MAX_CHILD_COUNT+1) >> 1); k++) {
            tmpInode = (ubixfsInode *)tmpInode->next;
          } // for k

cout << "page is full. splitting. using: " << tmpInode->name << endl;
          if (tmpNode->childHead[0] == NULL) {
Print();
cout << "rotating left" << endl;
cout << "replacing " << tmpNode->keys[0] << " with " << tmpInode->name << endl;
            memset(tmpNode->keys[0], 0, B_MAX_NAME_LENGTH);
            strncpy(tmpNode->keys[0], tmpInode->name, B_MAX_NAME_LENGTH);
            tmpNode->childHead[0] = tmpNode->childHead[1];
            tmpNode->childTail[0] = (void *)tmpInode->prev;
            tmpNode->childHead[1] = (void *)tmpInode;
cout << "CC[0]: " << (int)tmpNode->childCount[0] << endl;
cout << "CC[1]: " << (int)tmpNode->childCount[1] << endl;
            tmpNode->childCount[0] = (B_MAX_CHILD_COUNT+1) >> 1;
            tmpNode->childCount[1] -= tmpNode->childCount[i];
            tmpNode->present[0] = true;
cout << "CC[0]: " << (int)tmpNode->childCount[0] << endl;
cout << "CC[1]: " << (int)tmpNode->childCount[1] << endl;
Print();
            return true;
          } 

          if (i != tmpNode->used) {
            // if we're the last node, don't move things over
            // shift denotes how many items to move over
            int shift = tmpNode->used - i;
cout << "shift: " << shift << endl;
            memmove(&tmpNode->childHead[i+1],
                    &tmpNode->childHead[i],
                    sizeof(tmpNode->childHead[0]) * shift);
            memmove(&tmpNode->childTail[i+1],
                    &tmpNode->childTail[i],
                    sizeof(tmpNode->childTail[0]) * shift);
            memmove(&tmpNode->present[i+1],
                    &tmpNode->present[i],
                    sizeof(tmpNode->present[0]) * shift);
            memmove(&tmpNode->childCount[i+1],
                    &tmpNode->childCount[i],
                    sizeof(tmpNode->childCount[0]) * shift);

            memmove(&tmpNode->keys[i+1],
                    &tmpNode->keys[i],
                    sizeof(tmpNode->keys[0]) * shift);
            memset(tmpNode->keys[i], 0, B_MAX_NAME_LENGTH);
          } else {
            tmpNode->childHead[i+1] = tmpNode->childHead[i];
            tmpNode->childTail[i+1] = tmpNode->childTail[i];
            tmpNode->childCount[i+1] = tmpNode->childCount[i];
            tmpNode->present[i+1] = tmpNode->present[i];
          }

          strncpy(tmpNode->keys[i], tmpInode->name, B_MAX_NAME_LENGTH);
          tmpNode->childHead[i+1] = (void *)tmpInode;
          tmpNode->childTail[i] = (void *)tmpInode->prev;
          tmpNode->childCount[i] = (B_MAX_CHILD_COUNT+1) >> 1;
          tmpNode->childCount[i+1] -= tmpNode->childCount[i];
          tmpNode->present[i] = true;
          ++tmpNode->used;
          
        } // if

        return true;

      } else {
        tmpNode = (bNode *)tmpNode->childHead[i];
        goto restart;
      } // else !leafNode
    } // if result < 0
  } // for i
#endif
  return true;
} // bTree::Insert

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];
    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;
#if 0
restart:
  for (unsigned int i = 0; i <= bnode->used; i++) {
    // if we're at the end of the list, follow the last link and continue
    if (i == bnode->used) {
      if (bnode->leafNode) {
         inode = (ubixfsInode *)bnode->childHead[i];
         goto inodeSearch;
      } else {
        bnode = (bNode *)bnode->childHead[i];
      }
      goto restart;
    } // if

    result = strcmp(key, bnode->keys[i]);

    if (result < 0) {
      // what we're looking for is somewhere down the left branch
      // if we're in leaf nodes we need to scan through the inode list
      if (bnode->leafNode) {
        inode = (ubixfsInode *)bnode->childHead[i];
inodeSearch:
        while (inode != NULL) {
          result = strcmp(inode->name, key);
          if (result == 0) return inode;
          if (result > 0) return NULL;
          inode = inode->next;
        } // while
        return NULL;
      } else {
        // since we aren't in leaf nodes yet, travel left
        bnode = (bNode *)bnode->childHead[i];
        goto restart;
      } // else  
    } // if result < 0
  } // for

  return NULL;
#endif
} // 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