#include <stdio.h>
#include <stdlib.h>

#define ANZ_NEXT 2

struct node
{
	unsigned char key;	// key is 0 for router
	struct node * next [ANZ_NEXT];
};

void ausgeben (struct node * root)
{
	
}

/**Adds a router node at where without any
 * further checking if valid. To change it
 * to a non-router, set the key.*/
void add (struct node ** where)
{
	int i;
	
	*where = (struct node *) malloc (sizeof (struct node));
	for (i=0; i<ANZ_NEXT; i++)
	{
		(*where)->next[i] = NULL;
	}
}

int boolean (int wert)
{
	if (wert == 0) return 0;
	return 1;
}	

/**Inserts a node with key in the
 * radix trie root*/
void insert (struct node ** root, unsigned char key, int depth)
{
	struct node * alt;
	if (*root == NULL)
	{
		printf ("Füge ein: %d, %d\n", *root, key);
		add (root);
		(*root)->key=key;
	} else if ((*root)->key == 0)	// routerknoten
	{
		printf ("routerknoten: %d, key: %d, depth: %d, l/r: %d\n"
			, *root, key, depth, boolean(key & depth));
		insert (&((*root)->next [boolean(key&depth)]), key, depth>>1);
	} else {	// datenknoten
		printf ("datenknoten: %d, key: %d, depth: %d, l/r: %d\n"
			, *root, key, depth, boolean(key & depth));
		if (depth == 0) return;	// kann nicht mehr in die Tiefe
		alt = *root;	// alten root merken
		add (root);
		(*root)->next[boolean(alt->key&depth)] = alt; // alten root umhängen
		insert (&((*root)->next[boolean(key&depth)]),key, depth>>1);
	}
}

/**Sucht nach einen Knoten in dem Radix Trie.*/
int suche (struct node * root, unsigned char key, int depth)
{
	if (root == NULL)
	{
		printf ("Nicht gefunden\n");
		return -1;
	} else if (root->key == 0) // roterknoten verfolgen
	{
		printf ("Verfolge suche: %d, key: %d, l/r: %d\n",
			root, key, boolean (key&depth));
		return suche (root->next [boolean (key&depth)], key, depth >> 1);
	} else if (root->key == key) {	// datenknoten gefunden
		printf ("Gefunden(key: %d)!\n", key);
		return key;
	} else {
		printf ("Nicht vorhanden\n");
		return -1;
	}
}

/**Entfernt einen Knoten aus dem Radix Trie.
 * Achtung, dieser muss tatsächlich vorkommen,
 * am besten davor suchen, ob er vorhanden ist.*/
int entferne (struct node ** root, unsigned char key, int depth)
{
	struct node * temp;
	if (*root == NULL) {
		printf ("Datensatz nicht im Radix Trie\n");
	} else if ((*root)->key == 0)
	{
		//zuerst zu den richtigen Datensatz absteigen
		printf ("Search: %d, key: %d\n",
			*root, key);
		entferne (&((*root)->next[boolean (key&depth)]),key, depth >> 1);
		//lösche redudante Routerknoten
		if ((*root)->next [0] == NULL && (*root)->next[1]->key!=0)
		{
			temp = (*root)->next[1];
			printf ("Kill (data right): %d\n", *root);
			free (*root);
			*root = temp;
		} else if ((*root)->next [1] == NULL && (*root)->next[0]->key!=0)
		{
			temp = (*root)->next[0];
			printf ("Kill (data left): %d\n", *root);
			free (*root);
			*root = temp;
		}
	} else { // Datensatz
		if ((*root)->key == key) {	// genauen Datensatz gefunden
			printf ("Destroy: %d, key: %d\n", *root, key);
			free (*root);
			*root = NULL;
		} else { 
			printf ("Datensatz nicht im Radix Trie\n");
		}
	}
}

int main()
{
	int s = 16;	// binary start value
	struct node * root = NULL;
	insert (&root, 5, s);
	insert (&root, 9, s);
	insert (&root, 14, s);
	insert (&root, 21, s);
	suche (root, 21, s);

	insert (&root, 22, s);
	suche (root, 21, s);

	entferne (&root, 22, s);
	suche (root, 21, s);
	return 0;
}