bool is_leaf;

int *key, size;

Node **ptr;

friend class BPTree;

Node();

Node *root;

void insertInternal(int, Node *, Node *);

void removeInternal(int, Node *, Node *);

Node *findParent(Node *, Node *);

public:

BPTree();

void search(int);

void insert(int);

void remove(int);

void display(Node *);

Node *getRoot();

if(root == NULL) {

root = new Node;

root->key[0] = x;

root->is_leaf = true;

root->size = 1;

return;

}

Node *cursor = root;

Node *parent;

// make cursor to the leaf within the range

while(!cursor->is_leaf) {

parent = cursor;

for(int i = 0; i < cursor->size; i++) {

if(x < cursor->key[i]) {

cursor = cursor->ptr[i];

break;

}

if(i == cursor->size - 1) {

cursor = cursor->ptr[i + 1];

}

}

}

// if it is addable, then add it

if(cursor->size < MAX) {

int i = 0;

while(x > cursor->key[i] && i < cursor->size)

i++;

for(int j = cursor->size; j > i; j--) {

cursor->key[j] = cursor->key[j - 1];

}

cursor->key[i] = x;

cursor->size++;

cursor->ptr[cursor->size] = cursor->ptr[cursor->size - 1];

cursor->ptr[cursor->size - 1] = NULL;

}

else {

Node *newLeaf = new Node;

int virtualNode[MAX + 1];// plus one

for(int i = 0; i < MAX; i++) {

virtualNode[i] = cursor->key[i];

}

int i = 0, j;

while(x > virtualNode[i] && i < MAX) i++;

for(int j = MAX + 1; j > i; j--) {

virtualNode[j] = virtualNode[j - 1];

}

virtualNode[i] = x;

newLeaf->is_leaf = 1;

cursor->size = (MAX + 1) / 2;

newLeaf->size = MAX + 1 - (MAX + 1) / 2;

// adjust the next node as leaf as a new node adds

cursor->ptr[cursor->size] = newLeaf;

newLeaf->ptr[newLeaf->size] = cursor->ptr[MAX];

cursor->ptr[MAX] = NULL;

for(i = 0; i < cursor->size; i++) {

cursor->key[i] = virtualNode[i];

}

for(i = 0, j = cursor->size; i < newLeaf->size; i++, j++) {

newLeaf->key[i] = virtualNode[j];

}

if(cursor == root) {

Node *newRoot = new Node;

newRoot->key[0] = newLeaf->key[0];

newRoot->ptr[0] = cursor;

newRoot->ptr[1] = newLeaf;

newRoot->is_leaf = 0;

newRoot->size = 1;

root = newRoot;

}

else {

insertInternal(newLeaf->key[0], parent, newLeaf);

}

}

if(cursor->size < MAX) {

int i = 0;

while(x > cursor->key[i] && i < cursor->size) i++;

for(int j = cursor->size; j > i; j--) {

cursor->key[j] = cursor->key[j - 1];

}

}

bool IS_LEAF;

int *key, size;

Node **ptr;

friend class BPTree;

public:

Node();

Node *root;

void insertInternal(int, Node *, Node *);

void removeInternal(int, Node *, Node *);

Node *findParent(Node *, Node *);

public:

BPTree();

void search(int);

void insert(int);

void remove(int);

void display(Node *);

Node *getRoot();

if (root == NULL) {

root = new Node;

root->key[0] = x;

root->IS_LEAF = true;

root->size = 1;

} else {

Node *cursor = root;

Node *parent;

while (cursor->IS_LEAF == false) {

parent = cursor;

for (int i = 0; i < cursor->size; i++) {

if (x < cursor->key[i]) {

cursor = cursor->ptr[i];

break;

}

if (i == cursor->size - 1) {

cursor = cursor->ptr[i + 1];

break;

}

}

}

if (cursor->size < MAX) {

int i = 0;

while (x > cursor->key[i] && i < cursor->size) i++;

for (int j = cursor->size; j > i; j--) {

cursor->key[j] = cursor->key[j - 1];

}

cursor->key[i] = x;

cursor->size++;

cursor->ptr[cursor->size] = cursor->ptr[cursor->size - 1];

cursor->ptr[cursor->size - 1] = NULL;

} else {

Node *newLeaf = new Node;

int virtualNode[MAX + 1];

for (int i = 0; i < MAX; i++) {

virtualNode[i] = cursor->key[i];

}

int i = 0, j;

while (x > virtualNode[i] && i < MAX) i++;

for (int j = MAX + 1; j > i; j--) {

virtualNode[j] = virtualNode[j - 1];

}

virtualNode[i] = x;

newLeaf->IS_LEAF = true;

cursor->size = (MAX + 1) / 2;

newLeaf->size = MAX + 1 - (MAX + 1) / 2;

cursor->ptr[cursor->size] = newLeaf;

newLeaf->ptr[newLeaf->size] = cursor->ptr[MAX];

cursor->ptr[MAX] = NULL;

for (i = 0; i < cursor->size; i++) {

cursor->key[i] = virtualNode[i];

}

for (i = 0, j = cursor->size; i < newLeaf->size; i++, j++) {

newLeaf->key[i] = virtualNode[j];

}

if (cursor == root) {

Node *newRoot = new Node;

newRoot->key[0] = newLeaf->key[0];

newRoot->ptr[0] = cursor;

newRoot->ptr[1] = newLeaf;

newRoot->IS_LEAF = false;

newRoot->size = 1;

root = newRoot;

} else {

insertInternal(newLeaf->key[0], parent, newLeaf);

}

}

}

if (cursor->size < MAX) {

int i = 0;

while (x > cursor->key[i] && i < cursor->size) i++;

for (int j = cursor->size; j > i; j--) {

cursor->key[j] = cursor->key[j - 1];

}

for (int j = cursor->size + 1; j > i + 1; j--) {

cursor->ptr[j] = cursor->ptr[j - 1];

}

cursor->key[i] = x;

cursor->size++;

cursor->ptr[i + 1] = child;

} else {

Node *newInternal = new Node;

int virtualKey[MAX + 1];

Node *virtualPtr[MAX + 2];

for (int i = 0; i < MAX; i++) {

virtualKey[i] = cursor->key[i];

}

for (int i = 0; i < MAX + 1; i++) {

virtualPtr[i] = cursor->ptr[i];

}

int i = 0, j;

while (x > virtualKey[i] && i < MAX) i++;

for (int j = MAX + 1; j > i; j--) {

virtualKey[j] = virtualKey[j - 1];

}

virtualKey[i] = x;

for (int j = MAX + 2; j > i + 1; j--) {

virtualPtr[j] = virtualPtr[j - 1];

}

virtualPtr[i + 1] = child;

newInternal->IS_LEAF = false;

cursor->size = (MAX + 1) / 2;

newInternal->size = MAX - (MAX + 1) / 2;

for (i = 0, j = cursor->size + 1; i < newInternal->size; i++, j++) {

newInternal->key[i] = virtualKey[j];

}

for (i = 0, j = cursor->size + 1; i < newInternal->size + 1; i++, j++) {

newInternal->ptr[i] = virtualPtr[j];

}

if (cursor == root) {

Node *newRoot = new Node;

newRoot->key[0] = cursor->key[cursor->size];

newRoot->ptr[0] = cursor;

newRoot->ptr[1] = newInternal;

newRoot->IS_LEAF = false;

newRoot->size = 1;

root = newRoot;

} else {

insertInternal(cursor->key[cursor->size], findParent(root, cursor),

newInternal);

}

}

if (root == NULL) {

cout << "Tree empty\n";

} else {

Node *cursor = root;

Node *parent;

int leftSibling, rightSibling;

while (cursor->IS_LEAF == false) {

for (int i = 0; i < cursor->size; i++) {

parent = cursor;

leftSibling = i - 1;

rightSibling = i + 1;

if (x < cursor->key[i]) {

cursor = cursor->ptr[i];

break;

}

if (i == cursor->size - 1) {

leftSibling = i;

rightSibling = i + 2;

cursor = cursor->ptr[i + 1];

break;

}

}

}

bool found = false;

int pos;

for (pos = 0; pos < cursor->size; pos++) {

if (cursor->key[pos] == x) {

found = true;

break;

}

}

if (!found) {

cout << "Not found\n";

return;

}

for (int i = pos; i < cursor->size; i++) {

cursor->key[i] = cursor->key[i + 1];

}

cursor->size--;

if (cursor == root) {

for (int i = 0; i < MAX + 1; i++) {

cursor->ptr[i] = NULL;

}

if (cursor->size == 0) {

cout << "Tree died\n";

delete[] cursor->key;

delete[] cursor->ptr;

delete cursor;

root = NULL;

}

return;

}

cursor->ptr[cursor->size] = cursor->ptr[cursor->size + 1];

cursor->ptr[cursor->size + 1] = NULL;

if (cursor->size >= (MAX + 1) / 2) {

return;

}

if (leftSibling >= 0) {

Node *leftNode = parent->ptr[leftSibling];

// sibling is full enough

if (leftNode->size >= (MAX + 1) / 2 + 1) {

for (int i = cursor->size; i > 0; i--) {

cursor->key[i] = cursor->key[i - 1];

}

cursor->size++;

cursor->ptr[cursor->size] = cursor->ptr[cursor->size - 1];

cursor->ptr[cursor->size - 1] = NULL;

cursor->key[0] = leftNode->key[leftNode->size - 1];

leftNode->size--;

leftNode->ptr[leftNode->size] = cursor;

leftNode->ptr[leftNode->size + 1] = NULL;

parent->key[leftSibling] = cursor->key[0];

return;

}

}

if (rightSibling <= parent->size) {

Node *rightNode = parent->ptr[rightSibling];

//right sibling is full enough

if (rightNode->size >= (MAX + 1) / 2 + 1) {

cursor->size++;

cursor->ptr[cursor->size] = cursor->ptr[cursor->size - 1];

cursor->ptr[cursor->size - 1] = NULL;

cursor->key[cursor->size - 1] = rightNode->key[0];

rightNode->size--;

rightNode->ptr[rightNode->size] = rightNode->ptr[rightNode->size + 1];

rightNode->ptr[rightNode->size + 1] = NULL;

for (int i = 0; i < rightNode->size; i++) {

rightNode->key[i] = rightNode->key[i + 1];

}

parent->key[rightSibling - 1] = rightNode->key[0];

return;

}

}

// two consequence

if (leftSibling >= 0) {

Node *leftNode = parent->ptr[leftSibling];

for (int i = leftNode->size, j = 0; j < cursor->size; i++, j++) {

leftNode->key[i] = cursor->key[j];

}

leftNode->ptr[leftNode->size] = NULL;

leftNode->size += cursor->size;

leftNode->ptr[leftNode->size] = cursor->ptr[cursor->size];

removeInternal(parent->key[leftSibling], parent, cursor);

delete[] cursor->key;

delete[] cursor->ptr;

delete cursor;

} else if (rightSibling <= parent->size) {

Node *rightNode = parent->ptr[rightSibling];

for (int i = cursor->size, j = 0; j < rightNode->size; i++, j++) {

cursor->key[i] = rightNode->key[j];

}

cursor->ptr[cursor->size] = NULL;

cursor->size += rightNode->size;

cursor->ptr[cursor->size] = rightNode->ptr[rightNode->size];

cout << "Merging two leaf nodes\n";

removeInternal(parent->key[rightSibling - 1], parent, rightNode);

delete[] rightNode->key;

delete[] rightNode->ptr;

delete rightNode;

}

}

if (cursor == root) {

if (cursor->size == 1) {

if (cursor->ptr[1] == child) {

delete[] child->key;

delete[] child->ptr;

delete child;

root = cursor->ptr[0];

delete[] cursor->key;

delete[] cursor->ptr;

delete cursor;

cout << "Changed root node\n";

return;

} else if (cursor->ptr[0] == child) {

delete[] child->key;

delete[] child->ptr;

delete child;

root = cursor->ptr[1];

delete[] cursor->key;

delete[] cursor->ptr;

delete cursor;

cout << "Changed root node\n";

return;

}

}

}

int pos;

for (pos = 0; pos < cursor->size; pos++) {

if (cursor->key[pos] == x) {

break;

}

}

for (int i = pos; i < cursor->size; i++) {

cursor->key[i] = cursor->key[i + 1];

}

for (pos = 0; pos < cursor->size + 1; pos++) {

if (cursor->ptr[pos] == child) {

break;

}

}

for (int i = pos; i < cursor->size + 1; i++) {

cursor->ptr[i] = cursor->ptr[i + 1];

}

cursor->size--;

if (cursor->size >= (MAX + 1) / 2 - 1) {

return;

}

if (cursor == root) return;

Node *parent = findParent(root, cursor);

int leftSibling, rightSibling;

for (pos = 0; pos < parent->size + 1; pos++) {

if (parent->ptr[pos] == cursor) {

leftSibling = pos - 1;

rightSibling = pos + 1;

break;

}

}

if (leftSibling >= 0) {

Node *leftNode = parent->ptr[leftSibling];

if (leftNode->size >= (MAX + 1) / 2) {

for (int i = cursor->size; i > 0; i--) {

cursor->key[i] = cursor->key[i - 1];

}

cursor->key[0] = parent->key[leftSibling];

parent->key[leftSibling] = leftNode->key[leftNode->size - 1];

for (int i = cursor->size + 1; i > 0; i--) {

cursor->ptr[i] = cursor->ptr[i - 1];

}

cursor->ptr[0] = leftNode->ptr[leftNode->size];

cursor->size++;

leftNode->size--;

return;

}

}

if (rightSibling <= parent->size) {

Node *rightNode = parent->ptr[rightSibling];

if (rightNode->size >= (MAX + 1) / 2) {

cursor->key[cursor->size] = parent->key[pos];

parent->key[pos] = rightNode->key[0];

for (int i = 0; i < rightNode->size - 1; i++) {

rightNode->key[i] = rightNode->key[i + 1];

}

cursor->ptr[cursor->size + 1] = rightNode->ptr[0];

for (int i = 0; i < rightNode->size; ++i) {

rightNode->ptr[i] = rightNode->ptr[i + 1];

}

cursor->size++;

rightNode->size--;

return;

}

}

if (leftSibling >= 0) {

Node *leftNode = parent->ptr[leftSibling];

leftNode->key[leftNode->size] = parent->key[leftSibling];

for (int i = leftNode->size + 1, j = 0; j < cursor->size; j++) {

leftNode->key[i] = cursor->key[j];

}

for (int i = leftNode->size + 1, j = 0; j < cursor->size + 1; j++) {

leftNode->ptr[i] = cursor->ptr[j];

cursor->ptr[j] = NULL;

}

leftNode->size += cursor->size + 1;

cursor->size = 0;

removeInternal(parent->key[leftSibling], parent, cursor);

} else if (rightSibling <= parent->size) {

Node *rightNode = parent->ptr[rightSibling];

cursor->key[cursor->size] = parent->key[rightSibling - 1];

for (int i = cursor->size + 1, j = 0; j < rightNode->size; j++) {

cursor->key[i] = rightNode->key[j];

}

for (int i = cursor->size + 1, j = 0; j < rightNode->size + 1; j++) {

cursor->ptr[i] = rightNode->ptr[j];

rightNode->ptr[j] = NULL;

}

cursor->size += rightNode->size + 1;

rightNode->size = 0;

removeInternal(parent->key[rightSibling - 1], parent, rightNode);

}

if (cursor != NULL) {

for (int i = 0; i < cursor->size; i++) {

cout << cursor->key[i] << " ";

}

cout << "\n";

if (cursor->IS_LEAF != true) {

for (int i = 0; i < cursor->size + 1; i++) {

display(cursor->ptr[i]);

}

}

}

BPTree node;

node.insert(5);

node.insert(15);

node.insert(25);

node.insert(35);

node.insert(45);

node.display(node.getRoot());

node.remove(15);

node.display(node.getRoot());