#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdint.h>
#include <limits.h>
#include <string.h>
#include "btree.h"
//#define uint_fast16_t uint16_t
#define KEYLEN_MAX 200
static int prntcmp=0;
const unsigned char* utf8decode(const unsigned char *utf8, unsigned short *ucs);
/*FIXME: I don't work, try to make a comp that gets the length and compares with that (no prob's with 0 chars)*/
const char utf8strcnmp(const unsigned char *s1, const unsigned char *s2,unsigned short n1,unsigned short n2){
     unsigned short i;
     unsigned short c1,c2;
     unsigned short ls1p,l;
     const unsigned char *s1p,*s2p;
     s1p=s1;
     s2p=s2;
     for(;;){
     	if(s1p-s1==n1){
     		if(n1==n2&&n2==s2p-s2) return 0;
     		else return -1;
     	}
     	if(s2p-s2==n2){
     		if(n1==n2&&n1==s1p-s1) return 0;
     		else return 1;
     	}
     	s1p=utf8decode(s1p,&c1);
	s2p=utf8decode(s2p,&c2);
	if(c1==' ')c1='_';
	if(c2==' ')c2='_';
	if(c1<128&&c2<128){
	        //printf("TLC\n);
		c1=tolower(c1);
		c2=tolower(c2);
	}
/*	if((n!=USHRT_MAX)&&((s1p-s1)>=n||(s2p-s2)>=n))
     		return 0;*/
     	if(c1<c2) return -1;
     	else if (c1>c2) return 1;
     	/*else continue*/
     }
     printf("CMPEND\n");
     return 0;/*won't happen*/
}
/* Decode 1 UTF-8 char and return a pointer to the next char. */
const unsigned char* utf8decode(const unsigned char *utf8, unsigned short *ucs)
{
    unsigned char c = *utf8++;
    unsigned long code;
    int tail = 0;

    if ((c <= 0x7f) || (c >= 0xc2)) {
        /* Start of new character. */
        if (c < 0x80) {        /* U-00000000 - U-0000007F, 1 byte */
            code = c;
        } else if (c < 0xe0) { /* U-00000080 - U-000007FF, 2 bytes */
            tail = 1;
            code = c & 0x1f;
        } else if (c < 0xf0) { /* U-00000800 - U-0000FFFF, 3 bytes */
            tail = 2;
            code = c & 0x0f;
        } else if (c < 0xf5) { /* U-00010000 - U-001FFFFF, 4 bytes */
            tail = 3;
            code = c & 0x07;
        } else {
            /* Invalid size. */
            code = 0xfffd;
        }

        while (tail-- && ((c = *utf8++) != 0)) {
            if ((c & 0xc0) == 0x80) {
                /* Valid continuation character. */
                code = (code << 6) | (c & 0x3f);

            } else {
                /* Invalid continuation char */
                code = 0xfffd;
                utf8--;
                break;
            }
        }
    } else {
        /* Invalid UTF-8 char */
        code = 0xfffd;
    }
    /* currently we don't support chars above U-FFFF */
    *ucs = (code < 0x10000) ? code : 0xfffd;
    return utf8;
}
/**A key is a int_fast_16_t that holds the size in char's of the rest of the key, and then the rest of the key*/
unsigned char *getkey(void* key){
	return (unsigned char *)(key+sizeof(uint_fast16_t));
}

const char compare(void *key1,void *key2){
	if(prntcmp)
		printf ("CMP:%s,%s:%d:%d,%d\n",getkey(key1), getkey(key2),utf8strcnmp(getkey(key1), getkey(key2),*(uint_fast16_t*)key1,*(uint_fast16_t*)key2),*(uint_fast16_t*)key1,*(uint_fast16_t*)key2);
	return utf8strcnmp(getkey(key1), getkey(key2),*(uint_fast16_t*)key1,*(uint_fast16_t*)key2);
}
void int16le(uint16_t val, unsigned char* addr)
{
    addr[0] = val & 0xFF;
    addr[1] = (val >> 8) & 0xff;
}

void int32le(uint32_t val, unsigned char* addr)
{
    addr[0] = val & 0xFF;
    addr[1] = (val >> 8) & 0xff;
    addr[2] = (val >> 16) & 0xff;
    addr[3] = (val >> 24) & 0xff;
}
void int64le(uint64_t val, unsigned char* addr)
{
    addr[0] = val & 0xFF;
    addr[1] = (val >> 8) & 0xff;
    addr[2] = (val >> 16) & 0xff;
    addr[3] = (val >> 24) & 0xff;
    addr[4] = (val >> 32) & 0xff;
    addr[5] = (val >> 40) & 0xff;
    addr[6] = (val >> 48) & 0xff;
    addr[7] = (val >> 56) & 0xff;
}

unsigned short bnode_write_len(void *tree,bt_node *node){//depends on key/data structure
	/*Static node length:
	1:uint8_t (flags:leaf)
	2:uint16_t (nr_active)
	3*/
	unsigned int i;
	uint16_t bnodelen=3;
	for(i=0;i < node->nr_active;i++){
		/*Static key length:
		8:uint64_t (datapointer)
		4:uint32_t (childpointer)
		2:uint16_t (keylength)
		14
		*/
		bnodelen+=(*(uint_fast16_t*)node->key_vals[i]->key);
		bnodelen+=14;
	}
	if(!node->leaf)bnodelen+=4;
	return bnodelen;
}
void bnode_write(FILE *file,void *tree,bt_node *node,uint32_t *chldptrs){//depends on key/data structure
	unsigned char bnode_write_buffer[((btree*)tree)->node_write_len(tree,node)];
	memset(bnode_write_buffer,111,((btree*)tree)->node_write_len(tree,node));
	unsigned short bfcntr=0,i=0;
	bnode_write_buffer[bfcntr]=node->leaf;
	bfcntr++;
	int16le(node->nr_active,&bnode_write_buffer[bfcntr]);
	bfcntr+=2;
	for(i=0;i < node->nr_active;i++){
		/*Why do I have to write these (dataptrs) inverse of how they were readed?*/
		//printf("UN:%d\n",((uint32_t)(*((uint32_t*)(node->key_vals[i]->val+sizeof(uint32_t))))));
		int32le(((uint32_t)(*((uint32_t*)node->key_vals[i]->val))),&bnode_write_buffer[bfcntr]);
		bfcntr+=4;
		int32le(((uint32_t)(*((uint32_t*)(node->key_vals[i]->val+sizeof(uint32_t))))),&bnode_write_buffer[bfcntr]);
		bfcntr+=4;
		int32le(chldptrs[i],&bnode_write_buffer[bfcntr]);
		bfcntr+=4;
		int16le((*(uint_fast16_t*)node->key_vals[i]->key),&bnode_write_buffer[bfcntr]);
		bfcntr+=2;
		memcpy(&bnode_write_buffer[bfcntr],(node->key_vals[i]->key+sizeof(uint_fast16_t)),(*(uint_fast16_t*)node->key_vals[i]->key));
		bfcntr+=(*(uint_fast16_t*)node->key_vals[i]->key);
	}
 	if(!node->leaf){		
		int32le(chldptrs[node->nr_active],&bnode_write_buffer[bfcntr]);
		bfcntr+=4;
	}

	fwrite(bnode_write_buffer,sizeof(char),bfcntr,file);//is it correct with sizeof
}


unsigned int keysize(void * key) {
        return sizeof(uint_fast16_t)+(sizeof(char)*(*(uint_fast16_t*)key));
}

unsigned int datasize(void * data) {
        return sizeof(uint32_t)*2;
}

void *mallockey(unsigned char* str,uint_fast16_t length){
	void *ret = malloc(sizeof(uint_fast16_t)+(sizeof(unsigned char)*length));
	void *rtm=(ret+sizeof(uint_fast16_t));
	memcpy(rtm,str,length);
	//printf("SS:%s,%s,%s,%s:\n",rtm,getkey(ret),ret+sizeof(uint_fast16_t),(unsigned char *)((void*)(ret+sizeof(uint_fast16_t)));
	*((uint_fast16_t*)ret)=length;
	return ret;
}

bt_key_val* makekv(char* key,uint_fast16_t keylen,uint32_t data1,uint32_t data2){
	bt_key_val * kv;
	kv = (bt_key_val*)malloc(sizeof(bt_key_val));
	kv->key = mallockey((unsigned char*)key,keylen);
	kv->val = malloc(sizeof(uint32_t)*2);
	*(uint32_t *)kv->val = data1;
	*(uint32_t *)(kv->val+sizeof(uint32_t)) = data2;
	return kv;
}
// void addkey(btree *tree,char* key,uint32_t data1,uint32_t data2){
// 	btree_insert_key(tree,makekv(key,data1,data2));
// }
//remove the first of the upper node and readd, or better, check why in the algoritm...
int main(int argc,char * argv[])
{
	if(argc<4){
		printf("Usage: <in-list> <redirect-list> <out-tree>\n");
		return 0;
	}
	btree * tree;
	bt_key_val * kv;
	void *key;
	bt_key_val * kvr;
	tree = btree_create(30);	
	tree->key_size = keysize;
	tree->data_size = datasize;
	tree->compare = compare;
	tree->node_write_len=bnode_write_len;
	tree->node_write=bnode_write;
	char finlne[KEYLEN_MAX+1],tinlne[KEYLEN_MAX+1];
	char elmhdr[12];
	uint_fast16_t fkeylen=0,tkeylen=0;
	FILE *fd=fopen(argv[1],"r");
	while(fread(elmhdr,sizeof(uint8_t),12,fd)==12){
		if(*((uint32_t*)&elmhdr[8])==0){
	        	printf("Skipping empty\n");
	        	continue;
		}
		fkeylen=*((uint32_t*)&elmhdr[8])<KEYLEN_MAX?*((uint32_t*)&elmhdr[8]):KEYLEN_MAX;
		fread(finlne,sizeof(char),fkeylen,fd);
		if((*(uint32_t*)&elmhdr[8])-fkeylen>0)
			fseek(fd,(*((uint32_t*)&elmhdr[8]))-fkeylen,SEEK_CUR);
		finlne[fkeylen]=0;
 		if(strlen(finlne)!=(fkeylen)){
			printf("Bad keylen: %s\n",finlne);
			continue;
		}
		kv=makekv(finlne,fkeylen,*((uint32_t*)&elmhdr),*((uint32_t*)&elmhdr[4]));
		btree_insert_key(tree,kv);
		kv=0;
	}
	printf("SCRLD\n");
// 	prntcmp=1;
	fclose(fd);	
	fd=NULL;
	if(strlen(argv[2])!=0){
		FILE *rfd=fopen(argv[2],"rb");
		while(fread(elmhdr,sizeof(uint8_t),8,rfd)==8){
			if(*((uint32_t*)&elmhdr[0])==0||*((uint32_t*)&elmhdr[4])==0){
				printf("Skipping empty\n");
				continue;
			}
			fkeylen=*((uint32_t*)&elmhdr[0])<KEYLEN_MAX?*((uint32_t*)&elmhdr[0]):KEYLEN_MAX;
			tkeylen=*((uint32_t*)&elmhdr[4])<KEYLEN_MAX?*((uint32_t*)&elmhdr[4]):KEYLEN_MAX;
			fread(finlne,sizeof(char),fkeylen,rfd);
			if((*(uint32_t*)&elmhdr[0])-fkeylen>0){
				printf("MXLADJf %s,%d,skip %d\n",finlne,*(uint32_t*)&elmhdr[0],(*((uint32_t*)&elmhdr[0]))-fkeylen);
				fseek(rfd,(*((uint32_t*)&elmhdr[0]))-fkeylen,SEEK_CUR);
			}
			fread(tinlne,sizeof(char),tkeylen,rfd);
			if((*(uint32_t*)&elmhdr[4])-tkeylen>0){
				printf("MXLADJt %s,%d,skip %d\n",tinlne,*(uint32_t*)&elmhdr[4],(*((uint32_t*)&elmhdr[4]))-tkeylen);
				fseek(rfd,(*((uint32_t*)&elmhdr[4]))-tkeylen,SEEK_CUR);
			}
			finlne[fkeylen]=0;
			tinlne[tkeylen]=0;
			if(strlen(finlne)!=(fkeylen)||strlen(tinlne)!=(tkeylen)){
				printf("Bad keylen: %s,%s,%d=%d,%d=%d\n",finlne,tinlne,strlen(finlne),(fkeylen),strlen(tinlne),(tkeylen));
				continue;
			}
			//printf("Lookup:%s,%d\n",tinlne,tkeylen);
			key=mallockey((unsigned char*) tinlne,tkeylen);
			if((kvr=btree_search(tree,key))!=NULL){
				kv=makekv(finlne,fkeylen,(*((uint32_t*)kvr->val)),(*((uint32_t*)(kvr->val+sizeof(uint32_t)))));
				btree_insert_key(tree,kv);
			}else{
				//printf("Not found:%s,%d\n",tinlne,tkeylen);
			}
			free(key);
		}
		fclose(rfd);
		rfd=NULL;
	}
	FILE *ofd=fopen(argv[3],"w");
	btree_write(ofd,tree,tree->root);
	fclose(ofd);
	ofd=NULL;
#if 0
	int i = 0;
	btree * tree;
	bt_key_val * kv;
	int item = 0x43;
	int count;
	int order;
        int * values;
	
	srandom(time(NULL));
	
	for(order=2;order<60;order++) {
	    count = random()%512;		
            values = (int *)malloc(count*sizeof(int));

            for(i = 0;i<count;i++) {
                values[i] = random()%1024;
            }
            
	    tree = btree_create(order);	
            tree->value = value;
            tree->key_size = keysize;
            tree->data_size = datasize;
	    
	    for (i=0;i<count;i++) {	
		    kv = (bt_key_val*)malloc(sizeof(*kv));
		    kv->key = malloc(sizeof(int));		
		    *(int *)kv->key = values[i];
		    kv->val = malloc(sizeof(int));
		    *(int *)kv->val = values[i];
		    btree_insert_key(tree,kv);
	    }		
    	    print_subtree(tree,tree->root);
	    
	    for (i= count - 1; i > -1; i-= (random()%5)) {	
		    item = values[i];
		    btree_delete_key(tree,tree->root,&item);
	    }
	    free(values);
            btree_destroy(tree);
	}
	return 0;
#endif
}