Select Git revision
showcase.c 10.42 KiB
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
// UTILS ----------------------------------------------------------
#define M 4
#include <stdlib.h>
typedef struct node {
struct node *childs[M + 1];
int data[M];
int count;
struct node *next;
} node;
typedef struct control {
int value;
node *lhs;
node *rhs;
} control;
const control CONST_CONTR = {.value = 0, .lhs = NULL, .rhs = NULL};
node *bp_create_node() {
node *nd = malloc(sizeof(node));
for (int i = 0; i < M + 1; i++)
nd->childs[i] = NULL;
for (int i = 0; i < M; i++)
nd->data[i] = 0;
nd->count = 0;
nd->next = NULL;
return nd;
}
control value_to_insert(int val) {
control c;
c.value = val;
c.lhs = c.rhs = NULL;
return c;
}
bool bp_is_leaf(node *nd) { return nd->childs[0] == NULL; }
void bp_node_shift(node *nd, int index) {
// as there is one more child than values, we must do one more iteration
// outside of the for
nd->childs[M] = nd->childs[M - 1];
for (int i = M - 1; i > index; i--) {
nd->data[i] = nd->data[i - 1];
nd->childs[i + 1] = nd->childs[i];
}
}
node *bp_split(node *nd) {
node *new = bp_create_node();
/*
this weird thing is for the for loop
up to how many loop do we want to do
we need it outside because if the order of the tree is odd, we must do
one more loop
*/
int upto = (int)floor(M / 2);
int index = upto;
// update the new counts
nd->count = (int)floor(nd->count / 2); new->count = upto;
// as explained, do shit if the order is odd
if (M % 2 == 1) {
upto++;
new->count++;
}
// no need in this situation to reassign child pointers as there is no
// childs for leaves
for (int i = 0; i < upto; i++) {
new->data[i] = nd->data[index + i];
nd->data[index + i] = 0;
}
return new;
}
node *bp_split_root(node *root) {
node *new = bp_create_node(); // will be the new root
node *rhs = bp_create_node(); // second child of the new root
int index = (int)floor(M / 2); // index to the pivot
int looper = index; /* How many runs of our for loops we'll need to do
(different to index in the case our tree order is even)*/
new->count = 1;
root->count = index;
rhs->count = index;
if (M % 2 == 0) {
looper--;
rhs->count--;
}
// first assing the child pointers
for (int i = 0; i <= looper; i++) {
rhs->childs[i] = root->childs[index + i + 1];
root->childs[index + i + 1] = NULL;
}
// then assing the datas
for (int i = 0; i < looper; i++) {
rhs->data[i] = root->data[index + i + 1];
root->data[index + i + 1] = 0;
}
new->childs[0] = root;
new->childs[1] = rhs;
new->data[0] = root->data[index];
root->data[index] = 0;
return new;
}
control bp_split_unleaf(node *nd) {
// This one is used to split a node that is neither a leaf or a root
// it works exactly like the split of a root except it doesn't return a node
// that becomes the new root
// it instead returns a control value to send to the parent
control new;
node *rhs = bp_create_node();
int index = (int)floor(M / 2);
int looper = index;
nd->count = index;
rhs->count = index;
if (M % 2 == 0) { looper--;
rhs->count--;
}
for (int i = 0; i <= looper; i++) {
rhs->childs[i] = nd->childs[index + i + 1];
nd->childs[index + i + 1] = NULL;
}
for (int i = 0; i < looper; i++) {
rhs->data[i] = nd->data[index + i + 1];
nd->data[index + i + 1] = 0;
}
new.lhs = nd;
new.rhs = rhs;
new.value = nd->data[index];
nd->data[index] = 0;
return new;
}
void bp_do_the_insert(node *nd, control val) {
// look for a 0 in the node (it is guarenteed to exist in this version of
// the algorithm)
for (int i = 0; i < M; i++) {
// if we plainly find a 0
if (nd->data[i] == 0) {
nd->data[i] = val.value;
nd->childs[i + 1] = val.rhs;
break;
}
// if we need to insert the value between two values, we need to
// shift everything greater than our value one case further
if (nd->data[i] > val.value) {
bp_node_shift(nd, i);
nd->data[i] = val.value;
nd->childs[i + 1] = val.rhs;
break;
}
}
nd->count++;
}
// INSERT ----------------------------------------------------------
control bp_insert_into(node *nd, control val) {
bp_do_the_insert(nd, val);
// if the node is now full, we split
if (nd->count == M) {
control v;
node *new = bp_split(nd);
v.lhs = nd;
v.rhs = new;
v.value = new->data[0];
// if the new node we created is a leaf, we must add it to the
// linked list
if (bp_is_leaf(new)) {
if (nd->next != NULL)
new->next = nd->next;
nd->next = new;
}
return v;
}
return CONST_CONTR;
}
control bp_insert(node *nd, control val, int depth) {
control c; // will help us to return the pivot, and the two pointers of the
// childs-to-be
// if we are in a leaf, we found where to insert the value, so let's do it
if (bp_is_leaf(nd))
c = bp_insert_into(nd, val);
else // otherwise let's keep looking
{
for (int i = 0; i < M; i++) {
if (nd->data[i] > val.value || nd->data[i] == 0) {
c = bp_insert(nd->childs[i], val, depth + 1);
break;
}
}
// treat the control return here
// if a split happened and we are not the root
if (c.value != 0 && depth != 0) {
bp_do_the_insert(nd, c);
// if after the child split, the node is full, split the node
if (nd->count == M)
return bp_split_unleaf(nd);
return CONST_CONTR;
}
}
// if a split happened
if (c.value != 0) {
return c;
}
return CONST_CONTR;
}
node *bp_insert_val(node *tree, int val) {
// Parse the val into a control struct then insert it in the tree
control test = bp_insert(tree, value_to_insert(val), 0);
/*
depending on the control item, we act differently
if the control has pointers to node, then we had a split in the direct
childs of the root. We must add the values upringed to the root
*/
if (test.rhs != NULL) {
// if the root isn't a leaf, first we add the value into the node
if (!bp_is_leaf(tree)) {
bp_do_the_insert(tree, test);
// If the root is full, we must split it
if (tree->count == M) {
return bp_split_root(tree);
}
// if not, we can simply return the root
return tree;
}
// if, after a split, the root was a leaf, we must create a new
// node which will contain the values from the control
tree = bp_create_node();
tree->childs[0] = test.lhs;
tree->childs[1] = test.rhs;
tree->data[0] = test.value;
tree->count = 1;
}
return tree;
}
// MEMORY ----------------------------------------------------------
void bp_destroy(node *root) {
if (root == NULL)
return;
// free the childs first
if (!bp_is_leaf(root)) {
for (int i = 0; i < M; i++) {
bp_destroy(root->childs[i]);
}
}
// then free the root
free(root);
}
// PRINTING ----------------------------------------------------------
void bp_print_as_ll(node *root) {
// if we reached the end of the list
if (root == NULL) {
printf("NULL\n");
return;
}
// search for the first leaf on the tree
if (!bp_is_leaf(root)) {
return bp_print_as_ll(root->childs[0]);
}
printf("|");
// print every values in the node until hitting 0, then we can get on the
// next node
for (int i = 0; i < M; i++) {
printf(" %d |", root->data[i]);
if (root->data[i + 1] == 0) {
printf(" -> ");
return bp_print_as_ll(root->next);
}
}
}
void bp_print(node *root, int depth) {
// if we are on a leaf, we can print the values directly next to each other
if (bp_is_leaf(root)) {
for (int i = 0; i < depth; i++)
printf(" ");
for (int i = 0; i < M; i++) {
printf(" %d |", root->data[i]);
// if we reach a 0, we have seen every values in the node
if (root->data[i + 1] == 0)
break;
}
return;
}
for (int i = 0; i < M; i++) {
bp_print(root->childs[i], depth + 1);
printf("\n");
for (int i = 0; i < depth; i++)
printf(" ");
printf(" %d |\n", root->data[i]);
if (root->data[i + 1] == 0)
return bp_print(root->childs[i + 1], depth + 1);
}
}
int main() { node *tree = bp_create_node();
tree = bp_insert_val(tree, 3);
bp_print(tree, 0);
printf("\n|||||||||\n");
tree = bp_insert_val(tree, 6);
bp_print(tree, 0);
printf("\n|||||||||\n");
tree = bp_insert_val(tree, 5);
bp_print(tree, 0);
printf("\n|||||||||\n");
tree = bp_insert_val(tree, 4);
bp_print(tree, 0);
printf("\n|||||||||\n");
tree = bp_insert_val(tree, 8);
bp_print(tree, 0);
printf("\n|||||||||\n");
tree = bp_insert_val(tree, 13);
bp_print(tree, 0);
printf("\n|||||||||\n");
tree = bp_insert_val(tree, 9);
bp_print(tree, 0);
printf("\n|||||||||\n");
tree = bp_insert_val(tree, 15);
bp_print(tree, 0);
printf("\n|||||||||\n");
tree = bp_insert_val(tree, 11);
bp_print(tree, 0);
printf("\n|||||||||\n");
tree = bp_insert_val(tree, 12);
bp_print(tree, 0);
printf("\n|||||||||\n");
tree = bp_insert_val(tree, 7);
bp_print(tree, 0);
printf("\n|||||||||\n");
tree = bp_insert_val(tree, 14);
bp_print(tree, 0);
printf("\n|||||||||\n");
tree = bp_insert_val(tree, 10);
bp_print(tree, 0);
printf("\n|||||||||\n");
tree = bp_insert_val(tree, 16);
bp_print(tree, 0);
printf("\n|||||||||\n");
tree = bp_insert_val(tree, 17);
bp_print(tree, 0);
printf("\n|||||||||\n");
tree = bp_insert_val(tree, 18);
bp_print(tree, 0);
printf("\n|||||||||\n");
bp_print_as_ll(tree);
bp_destroy(tree);
return 0;
}