#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include "btree.h"
#include "btree_types.h"
#include "btree_consts.h"
#include "btree_standardVFS.h"

bool 
operator ==(uPtr u1, uPtr u2) {
  return (u1.offset == u2.offset);
} // overloaded operator ==

bTree::bTree(const char * filename, uInt32 nodeSize, treeTypes tt, bTreeVFS * virtualFS) {
  memoryTree = (filename != NULL && *filename != '\0');

  info = new bTreeInfo;
  assert(info);
  memset(info, 0, sizeof(struct bTreeInfo));
  
  vfs = virtualFS;

  info->magic  = B_NODE_TREEINFO;
  info->root.offset = 0;           // should be set with setNull() !!!
  info->firstDeleted.offset = 0;   // should be set with setNull() !!!
  info->nodes  = 0;
  info->height = 0;
  info->keys   = 0;
  info->bNodeSize = nodeSize;
  info->treeType = tt;

  if (!memoryTree) {

    if (vfs == NULL) vfs = new StandardVFS();

    if (vfs->fExist(filename)) {
      if (!vfs->fOpen(filename)) exit(42);
      if (!vfs->fRead(info, sizeof(bTreeInfo))) exit(42);
    } else {
      if (!vfs->fCreate(filename)) exit(42);
      if (!vfs->fWrite(info, sizeof(bTreeInfo))) exit(42);
    }

  } // if not memoryTree

  switch (info->treeType) {
    case BT_CUSTOM: 
      InstallUserFunctions(compareKeyNull,   copyKeyNull,   keySizeNull);
      break;
    case BT_PCHAR:
      InstallUserFunctions(compareKeyPChar,  copyKeyPChar,  keySizePChar);
      break;
    case BT_STRING:
      InstallUserFunctions(compareKeyString, copyKeyString, keySizeString);
      break;
    case BT_SINGLE:
      InstallUserFunctions(compareKeySingle, copyKeySingle, keySizeSingle);
      break;
    case BT_DOUBLE:
      InstallUserFunctions(compareKeyDouble, copyKeyDouble, keySizeDouble);
      break;
    case BT_INT32:
      InstallUserFunctions(compareKeyInt32,  copyKeyInt32,  keySizeInt32);
      break;
    case BT_INT64:
      InstallUserFunctions(compareKeyInt64,  copyKeyInt64,  keySizeInt64);
      break;
    default:
      InstallUserFunctions(compareKeyNull,   copyKeyNull,  keySizeNull);
      break;
  } // switch
 
  treeChanged = false;
  return;
} // bTree::bTree

bTree::bTree(const char * filename, bTreeVFS * virtualFS) {
  info = NULL;
  memoryTree = false;
  treeChanged = false;
  InstallUserFunctions(compareKeyNull, copyKeyNull, keySizeNull);
  
  vfs = virtualFS;
  
  if (vfs == NULL) vfs = new StandardVFS();
  if (!vfs->fExist(filename)) {
    assert(false);
    return;
  } // if filename doesn't exist

  info = new bTreeInfo;
  memset(info, 0, sizeof(bTreeInfo));
  if (!vfs->fOpen(filename)) exit(42);
  if (!vfs->fRead(info, sizeof(bTreeInfo))) exit(42);
  if (info->magic != B_NODE_TREEINFO) exit(42);
  
  switch (info->treeType) {
    case BT_CUSTOM: 
      InstallUserFunctions(compareKeyNull,   copyKeyNull,   keySizeNull);
      break;
    case BT_PCHAR:
      InstallUserFunctions(compareKeyPChar,  copyKeyPChar,  keySizePChar);
      break;
    case BT_STRING:
      InstallUserFunctions(compareKeyString, copyKeyString, keySizeString);
      break;
    case BT_SINGLE:
      InstallUserFunctions(compareKeySingle, copyKeySingle, keySizeSingle);
      break;
    case BT_DOUBLE:
      InstallUserFunctions(compareKeyDouble, copyKeyDouble, keySizeDouble);
      break;
    case BT_INT32:
      InstallUserFunctions(compareKeyInt32,  copyKeyInt32,  keySizeInt32);
      break;
    case BT_INT64:
      InstallUserFunctions(compareKeyInt64,  copyKeyInt64,  keySizeInt64);
      break;
    default:
      InstallUserFunctions(compareKeyNull,   copyKeyNull,  keySizeNull);
      break;
  } // switch
} // bTree::bTree

int
bTree::align(int keyLength) {
  return ((sizeof(uPtr) + keyLength + 7) >> 3) << 3;
} // bTree::align

uPtr
bTree::allocEmptyNode(void) {
  struct TbNode * newNode = NULL;
  uPtr result;

  saveSuperBlock();
  setNull(result);

  if (!isNull(getFirstDeleted())) {
    newNode = loadPage(getFirstDeleted());
    if (newNode == NULL) return result;
    setFirstDeleted(newNode->parent);
  } else {
    newNode = static_cast<TbNode *>(calloc(1, info->bNodeSize));
    setNodes(getNodes() + 1);
    newNode->tag = getNodes();
  } // else 

  newNode->magic           = B_NODE_LEAF;
  newNode->numKeys         = 1;
  newNode->size            = (int)&newNode->data - (int)newNode;

  // these should really be setNull() calls, but gcc doesn't support it.
  // GNU bastards. Die. Die. Die.

  newNode->left.offset     = 0;
  newNode->right.offset    = 0;
  newNode->parent.offset   = 0;
  newNode->reserved.offset = 0;

  result = getAddress(newNode);
  savePage(newNode);
  discardPage(newNode);

  return result;
} // bTree::allocEmptyNode

int
bTree::calcSize(TbNode * node) {
  int size;
  TbNodeData * dataNode;

  if (node == NULL) return 0;
  dataNode = &node->data;
  size = (int)dataNode - (int)node;
  
  for (unsigned int curNode = 1; curNode <= node->numKeys; curNode++) {
    size += align(keySize(&dataNode->key));

    uInt8 * tmpPtr = (uInt8 *)dataNode;
    tmpPtr += align(keySize(&dataNode->key));
    dataNode = (TbNodeData *)tmpPtr;

  } // for curNode 
  return size;
} // bTree::calcSize

void
bTree::deAllocNode(TbNode * node) {
  if (node == NULL) return;
 
  node->magic    = B_NODE_OPEN;

  // these should really be setNull() calls, but, as mentioned elsewhere
  // GNU is evil and likes to put kittens in blenders.

  node->left.offset     = 0;
  node->right.offset    = 0;
  node->reserved.offset = 0;
  if (!memoryTree) node->parent = getFirstDeleted();
  node->size = (int)&node->data - (int)node;
  memset(&node->data, 0, info->bNodeSize - node->size);

  if (!memoryTree) setFirstDeleted(getAddress(node));
  savePage(node);
  free(node);
} // bTree::deAllocNode

uPtr
bTree::deleteEntry(uPtr u, void * key, uPtr value) {
  TbNode * bnode;
  TbNode * tmpNode;
  TbNode * neighbor;
  TbNode * parent;

  TbNodeData * dataNode;
  TbNodeData * nextDataNode;
  TbNodeData * tmpDataNode;

  void * src;
  void * dst;

  uInt8 * convPtr = NULL;
  uPtr result, tmpLink;

  uInt32 nodeSize, tmpTag;
  unsigned int curNode;
  int res, size, neighborSize;

  bool found;

  setNull(result);

  if (isNull(u)) return result;
  
  bnode = loadPage(u);

  assert(bnode->numKeys != 0);  // this should never happen
  
  if (bnode->magic == B_NODE_LEAF) {
    dataNode = &bnode->data;
    curNode = 0;

    do {
      res = compareKeys(&dataNode->key, key);
      if (res >= 0) break;
      convPtr = (uInt8 *)dataNode;
      convPtr += align(keySize(&dataNode->key));
      dataNode = (TbNodeData *)convPtr;
      curNode++;
    } while (curNode != bnode->numKeys);

    if (res != 0) {
//      cerr << "Could not find in leaf node" << endl;
      discardPage(bnode);
      return result;
    } // if res != 0

    // Since we found the entry, we will have to save the superblock
    // at the end. Set treeChanged to true.
    treeChanged = true;
    result = dataNode->link;

    nodeSize = align(keySize(&dataNode->key));
  
    convPtr = (uInt8 *) dataNode;
    convPtr += nodeSize;
    nextDataNode = (TbNodeData *) dataNode;  

    memmove(dataNode, nextDataNode, bnode->size - ((int)nextDataNode - (int)bnode));
    bnode->numKeys--;
    bnode->size -= nodeSize;
    dataNode = (TbNodeData *)((int)bnode + bnode->size);
    memset(dataNode, 0, nodeSize);
    setKeys(getKeys() - 1);

    if (getAddress(bnode) == getRoot()) {
      if (bnode->numKeys == 0) {
        info->root.offset = 0;   // should be a setNull() call
        setRoot(info->root);
        setHeight(getHeight() - 1);
        deAllocNode(bnode);
        return result;
      }
    } else {  // not root
      if (bnode->size < (info->bNodeSize / 2)
    } // else not root
  } else {

  } // else bnode->magic != B_NODE_LEAF
  return result;
} // bTree::deleteEntry

void
bTree::discardPage(TbNode * node) {
  if (!memoryTree)
    if (node != NULL) free(node);
} // bTree::discardPage

bool
bTree::fetchFirstKey(uPtr u, bTreeSearch & search) {
  TbNode * node;
  TbNodeData * dataNode;
  bool result = false;
  
  if (isNull(u)) return false;
  node = loadPage(u);
  if (node == NULL) return false;
 
  dataNode = &node->data;

  if (node->magic == B_NODE_LEAF) {
    search.value = dataNode->link;
    search.keySize = keySize(&dataNode->key);
    search.key = calloc(1, align(search.keySize));
    if (search.key == NULL) return result;
    copyKey(&dataNode->key, search.key);
    result = true;
  } else {
    return fetchFirstKey(dataNode->link, search);
  } // else not B_NODE_LEAF
  discardPage(node);
  return result;
} // bTree::fetchFirstKey

bool
bTree::fetchLastKey(uPtr u, bTreeSearch & search) {
  TbNode * node;
  TbNodeData * dataNode;
  bool result = false;

  if (isNull(u)) return false;
  node = loadPage(u);
  if (node == NULL) return false;
  
  dataNode = &node->data;
 
  if (node->magic == B_NODE_LEAF) {
    for (unsigned int curNode = 1; curNode < node->numKeys; curNode++) {

      uInt8 * tmpPtr = (uInt8 *)dataNode;
      tmpPtr += align(keySize(&dataNode->key));
      dataNode = (TbNodeData *)tmpPtr;

    } // for curNode

   search.value = dataNode->link;
   search.keySize = keySize(&dataNode->key);
   search.key = calloc(1, align(search.keySize));
   copyKey(&dataNode->key, search.key);
   result = true;
  } else {
    for (unsigned int curNode = 1; curNode <= node->numKeys; curNode++) {

      uInt8 * tmpPtr = (uInt8 *)dataNode;
      tmpPtr += align(keySize(&dataNode->key));
      dataNode = (TbNodeData *)tmpPtr;

    } // for curNode
    result = fetchLastKey(dataNode->link, search);
  } // else not B_NODE_LEAF  
  discardPage(node);
  return result;
} // bTree::fetchLastKey

uPtr
bTree::findLeafNode(uPtr u, void * key) {
  TbNode * bnode;
  TbNodeData * dataNode;
  uPtr link;
  uPtr result;

  setNull(result);
  if (key == NULL) return result;
  if (isNull(u)) return result;

  bnode = loadPage(u);

  if (bnode->magic == B_NODE_LEAF) {
    discardPage(bnode);
    return u;
  } else {
    dataNode = &bnode->data;
    for (unsigned int curNode = 0; curNode < bnode->numKeys; curNode++) {
      if (compareKeys(key, &dataNode->key) <= 0) {
        link = dataNode->link;
        discardPage(bnode);
        return findLeafNode(link, key);
      } 
// This code:
//      dataNode += align(keySize(&dataNode->key));
// Becomes the following because I can't do manual byte adjusts:
      uInt8 * tmpPtr = (uInt8 *)dataNode;
      tmpPtr += align(keySize(&dataNode->key));
      dataNode = (TbNodeData *)tmpPtr;
    } // for curnode
    link = dataNode->link;
    discardPage(bnode);
    return findLeafNode(link, key);
  } // else not B_NODE_LEAF 
  return result;
} // bTree::findLeafNode

void 
bTree::freeAll(void) {
  if (!memoryTree) return;
  freePage(getRoot());
  // setNull(info->root);
  info->root.offset = 0;  // this really should be a setNull() call. Die GNU.
} // bTree::freeAll

void
bTree::freePage(uPtr u) {
  TbNode * node;
  TbNodeData * dataNode;

  if (isNull(u)) return;

  node = u.bPtr;
  if (node->magic = B_NODE_INDEX) {
    dataNode = &node->data;
    for (unsigned int curNode = 0; curNode < node->numKeys; curNode++) {
      freePage(dataNode->link);

      uInt8 * tmpPtr = (uInt8 *) dataNode;
      tmpPtr += align(keySize(&dataNode->key));
      dataNode = (TbNodeData *) tmpPtr;

    } // for curNode
    freePage(dataNode->link); 
  } // if index node
  free(node);
} // bTree::freePage

void
bTree::getNeighbor(TbNode * bnode, TbNode ** neighbor, int & neighborSize) {
  TbNode * l;
  TbNode * r;
  // a check to see if neighbor is null is probably not needed as
  // this function is only used by deleteEntry() and we pass variables in.
  *neighbor = NULL;
  neighborSize = 0;

  l = loadPage(bnode->left);
  r = loadPage(bnode->right);

  if (l == NULL) {
    // this next check may be unnecessary
    if (r->parent == bnode->parent) {
      *neighbor = r;
      neighborSize = r->size;
    } 
    return;
  } // if l == null

  if (r == NULL) {
    // this next check may be unnecessary
    if (l->parent == bnode->parent) {
      *neighbor = l;
      neighborSize = l->size;
    }  
    return;
  } // if r == null

  if (l->parent == r->parent) {  // both are children of the same parent

    if (l->size < r->size) {
      *neighbor = l;
      neighborSize = l->size;
      discardPage(r);
      return;
    } else {
      *neighbor = r;
      neighborSize = r->size;
      discardPage(l);
      return;
    } // else l->size >= r->size
    
  } else {                      // one of the neighbors has a different parent

    if (l->parent == bnode->parent) {
      *neighbor = l;
      neighborSize = l->size;
      discardPage(r);
      return;
    } else {
      *neighbor = r;
      neighborSize = r->size;
      discardPage(l);
      return;
    } // else l->parent != bnode->parent

  } // else

  discardPage(l); 
  discardPage(r);
} // bTree::getNeighbor

uPtr
bTree::getAddress(TbNode * node) {
  uPtr u;
  setNull(u);
  
  if (memoryTree) 
    u.bPtr = node;
  else
    u.offset = node->tag;

  return u;
} // bTree::getAddress

uPtr
bTree::getFirstDeleted(void) {

  if (!memoryTree) {
    if (!vfs->fSeek((int)&info->firstDeleted - (int)info)) exit(42);
    if (!vfs->fRead(&info->firstDeleted, sizeof(info->firstDeleted))) exit(42);
  } // if not memoryTree

  return info->firstDeleted;
} // bTree::getFirstDeleted

uInt32
bTree::getNodes(void) {

  if (!memoryTree) {
    if (!vfs->fSeek((int)&info->nodes - (int)info)) exit(42);
    if (!vfs->fRead(&info->nodes, sizeof(info->nodes))) exit(42);
  } // if not memoryTree

  return info->nodes;
} // bTree::getNodes

uInt32 
bTree::getHeight(void) {

  if (!memoryTree) {
    if (!vfs->fSeek((int)&info->height - (int)info)) exit(42);
    if (!vfs->fRead(&info->height, sizeof(info->height))) exit(42);
  } // if not memoryTree
 
  return info->height;
} // bTree::getHeight

uInt32
bTree::getKeys(void) {
  
  if (!memoryTree) {
    if (!vfs->fSeek((int)&info->keys - (int)info)) exit(42);
    if (!vfs->fRead(&info->keys, sizeof(info->keys))) exit(42);
  } // if not memoryTree

  return info->keys;
} // bTree::getKeys

uPtr
bTree::getRoot(void) {
  
  if (info == NULL) {
    uPtr result;
    setNull(result);
    return result;
  } // if info == NULL

  if (!memoryTree) {
    if (!vfs->fSeek((int)&info->root - (int)info)) exit(42);
    if (!vfs->fRead(&info->root, sizeof(info->root))) exit(42);
  } // if not memoryTree

  return info->root;
} // bTree::getRoot

bool
bTree::isNull(uPtr u) {
  return (u.offset == 0);
} // bTree::isNull

TbNode *
bTree::loadPage(uPtr u) {
  TbNode * node;

  if (isNull(u)) return NULL;

  if (memoryTree) 
    node = u.bPtr;
  else {
    if (!vfs->fSeek((int)u.offset * info->bNodeSize)) exit(42);
    node = (TbNode *)malloc(info->bNodeSize);
    if (node == NULL) return NULL;
    if (!vfs->fRead(node, info->bNodeSize)) exit(42);
  } // else

  return node;
} // bTree::loadPage

void
bTree::loadSuperBlock(void) {
  if (memoryTree) return;

  if (!vfs->fSeek(0)) exit(42);
  if (!vfs->fRead(info, sizeof(bTreeInfo))) exit(42);
} // bTree::loadSuperBlock

void
bTree::savePage(TbNode * node) {
  if (memoryTree) return;
  
  if (node == NULL) return;
  
  if (!vfs->fSeek((int)node->tag * info->bNodeSize)) exit(42);
  if (!vfs->fWrite(node, info->bNodeSize)) exit(42);
} // bTree::savePage

void 
bTree::saveSuperBlock(void) {
  if (memoryTree) return;

  if (!vfs->fSeek(0)) exit(42);
  if (!vfs->fWrite(info, sizeof(bTreeInfo))) exit(42);

} // bTree::saveSuperBlock

void
bTree::setFirstDeleted(uPtr value) {
  info->firstDeleted = value;

  if (memoryTree) return;

  if (!vfs->fSeek((int)&info->firstDeleted - (int)info)) exit(42);
  if (!vfs->fWrite(&info->firstDeleted, sizeof(info->firstDeleted))) exit(42);

} // bTree::setFirstDeleted

void
bTree::setNodes(uInt32 value) {
  info->nodes = value;

  if (memoryTree) return;

  if (!vfs->fSeek((int)&info->nodes - (int)info)) exit(42);
  if (!vfs->fWrite(&info->nodes, sizeof(info->nodes))) exit(42);

} // bTree::setNodes

void
bTree::setHeight(uInt32 value) {
  info->height = value;

  if (memoryTree) return;

  if (!vfs->fSeek((int)&info->height - (int)info)) exit(42);
  if (!vfs->fWrite(&info->height, sizeof(info->height))) exit(42);

} // bTree::setHeight

void
bTree::setKeys(uInt32 value) {
  info->keys = value;

  if (memoryTree) return;

  if (!vfs->fSeek((int)&info->keys - (int)info)) exit(42);
  if (!vfs->fWrite(&info->keys, sizeof(info->keys))) exit(42);

} // bTree::getKeys

void 
bTree::setLeft(uPtr u, uPtr newPtr) {
  TbNode * node = loadPage(u);
  if (node == NULL) return;

  node->left = newPtr;
  savePage(node);
  discardPage(node);
} // bTree::setLeft

void
bTree::setParent(uPtr u, uPtr newPtr) {
  TbNode * node = loadPage(u);
  if (node == NULL) return;

  node->parent = newPtr;
  savePage(node);
  discardPage(node);
} // bTree::setParent

void
bTree::setRight(uPtr u, uPtr newPtr) {
  TbNode * node = loadPage(u);
  if (node == NULL) return;

  node->right = newPtr;
  savePage(node);
  discardPage(node);
} // bTree::setRight

void
bTree::setRoot(uPtr value) {
  info->root = value;

  if (memoryTree) return;

  if (!vfs->fSeek((int)&info->root - (int)info)) exit(42);
  if (!vfs->fWrite(&info->root, sizeof(info->root))) exit(42);

} // bTree::setRoot

void
bTree::setNull(uPtr & u) {
  u.offset = 0;
} // bTree::setNull

/*************************************/
/*  Public Methods                   */
/*************************************/

uInt32
bTree::GetKeyCount(void) {
  if (info != NULL) 
    return getKeys();
  else
    return 0;
} // bTree::GetKeyCount

uInt32
bTree::GetTreeHeight(void) {
  return getHeight();
} // bTree::GetTreeHeight


void
bTree::InstallUserFunctions(compareKeyFunc cmpFunc, copyKeyProc copyProc, keySizeFunc ksFunc) {
  compareKeys = cmpFunc;
  copyKey = copyProc;
  keySize = ksFunc;
  return;
} // bTree::InstallUserFunctions

bTree::~bTree(void) {
  return;
} // bTree::~bTree