HTTree - Hacked Ternary Tree Implementation

////////////////////////////////////////////////////////////////////////////////
// The Hack Ternary Tree - HTTree
// Copyright (c) 2006 Gabriel Wernersbach Farinas
// Permission to use, copy, modify, distribute and sell this software for any 
//     purpose is hereby granted without fee, provided that the above copyright 
//     notice appear in all copies and that both that copyright notice and this 
//     permission notice appear in supporting documentation.
// The author makes no representations about the 
//     suitability of this software for any purpose. It is provided "as is" 
//     without express or implied warranty.
////////////////////////////////////////////////////////////////////////////////


#include "stdafx.h"
#include <iostream>

using namespace std;

template<typename DataType>
struct HTTNODE{
public:
    unsigned int C;/*MNRL*/
/*   M ine  
     N ext (if mine is equal)  
     R ight  
     L eft  */ 
    HTTNODE *LL,*LE,*LR;
    HTTNODE *EL,*EE,*ER;
    HTTNODE *RL,*RE,*RR;

    DataType *value,*rvalue,*lvalue,*nvalue;
};

template< typename DataType>
class HTTree
{
private:
	//root node
	 HTTNODE<DataType> * root;

	 //number of key/data stored 
	 unsigned int bttsize;
public:
	//Constructor - initializes the root node and size
	HTTree():root(NULL),bttsize(0){
		//create the root node and set it to empty
		root = new HTTNODE<DataType>;
		memset(root,0,sizeof(HTTNODE<DataType>));
	};
	//Destructor - clear the tree if it had nodes
	~HTTree(){
		//if there is something
		if(bttsize)
			//clear the tree
			HTTree::bttclear(root);
		else
			//just clear the root node
			delete root;
	}
	//Clear the branch starting by r
	void bttclear(HTTNODE<DataType>* r){
		//clear the branch
		bttdelete(r);
		//set the node to NULL - avoiding further usage
		r=NULL;
	}
	//Clear all the tree
	void bttclear(){
		bttdelete(root);
		//re-create the root node in case we use it again
		root = new HTTNODE<DataType>;
		memset(root,0,sizeof(HTTNODE<DataType>));
	}
	//Insert using key/data values
	HTTNODE<DataType>* bttinsert(const char *key,DataType *data){
		return bttinsert(root,key,data);
	}
	//Insert key/data in a recursive way using the node r as a starting point
	HTTNODE<DataType>* bttinsert(HTTNODE<DataType>* r,const char *key,DataType *data)
	{
		//LRNM DCBA
		unsigned int s=*((unsigned int*)key);
		//[A == 0]
			//S return error!
		if((s & 0x000000FF) == 0x00000000){
			return NULL;
		}
		if(!r){
			cout << "R is null!" << endl;
			return NULL;
		}
		//[NM == 00]
		if((r->C& 0x000FFFF) == 0x00000000){
			//S [B == 0]
			if((s & 0x0000FF00) == 0x00000000){
				//S M = A
				r->C |= s &0x000000FF; //insert M
				//insert value 
				if(!r->value){
					//S insert value
					r->value = data;++bttsize;
					return r;
				}else{
					//N collision!
					//cout<< "collision value" << endl;
					return NULL;
				}
			}else{
				//N NM = BA
				r->C |= s &0x0000FFFF; //insert NM
				//[C == 0]
				if((s & 0x00FF0000) == 0x00000000)
				{
					//S inset nvalue 
					if(!r->nvalue){
						//S insert value
						r->nvalue = data;++bttsize;
						return r;
					}else{
						//N collision!
						//cout<< "collision nvalue" << endl;
						return NULL;
					}
				}else{
					//N insert EE +2
					if(!r->EE){
						r->EE = new HTTNODE<DataType>;
						memset(r->EE,0,sizeof(HTTNODE<DataType>));
					}
					return bttinsert(r->EE,key+2,data);
				}
			}
		}else{
			//N [B == 0]
			if((s & 0x0000FF00) == 0x00000000){
				//S [M == 0]
				if((r->C& 0x00000FF) == 0x00000000){
					//S   M = A
					r->C |= s &0x000000FF; //insert M
					//insert value
					if(!r->value){
						//S insert value
						r->value = data;++bttsize;
						return r;
					}else{
						//N collision!
						//cout<< "collision value" << endl;
						return NULL;
					}
				}else{
					//N   [M == A ]
					if((r->C& 0x000000FF) == (s & 0x000000FF)){
						//S return collision!
						//cout<< "collision value" << endl;
						return NULL;
					}else{
							//N [ M > A]
						if((r->C& 0x000000FF) > (s & 0x000000FF)){
								//S [L == 0]
								if((r->C& 0xFF000000) == 0x00000000){
									//S L = A
									r->C |= ((s &0x000000FF) << 24); //insert L
									//insert lvalue
									if(!r->lvalue){
										r->lvalue = data;++bttsize;
										return r;
									}else{
										//cout<< "collision lvalue" << endl;
										return NULL;
									}
								}else{
									//N [L == A]
									if((r->C& 0xFF000000) == ((s & 0x000000FF)<<24)){
										//S return collision
										//cout<< "collision lvalue" << endl;
										return NULL;
									}else{
										//N [L > A]
										if((r->C& 0xFF000000) > ((s & 0x000000FF)<<24)){
											//S insert LL +0
											if(!r->LL){
												r->LL = new HTTNODE<DataType>;
												memset(r->LL,0,sizeof(HTTNODE<DataType>));
											}
											return bttinsert(r->LL,key,data);
										}else{
											//N insert LR +0
											if(!r->LR){
												r->LR = new HTTNODE<DataType>;
												memset(r->LR,0,sizeof(HTTNODE<DataType>));
											}
											return bttinsert(r->LR,key,data);
										}
									}
								}
						}else{
							//N [R == 0]
							if((r->C& 0x00FF0000) == 0x00000000){
								//S R = A
								r->C |= ((s &0x000000FF) << 16); //insert R
								//insert rvalue
								if(!r->rvalue){
									r->rvalue = data;++bttsize;
									return r;
								}else{
									//cout<< "collision rvalue " << endl;
									return NULL;
								}
							}else{
								//N [R == A]
								if((r->C& 0x00FF0000) == ((s&0x000000FF)<<16)){
									//cout<< "collision rvalue " << endl;
									return NULL;
								}else{
									//N [R > A]
									if((r->C& 0x00FF0000) > ((s&0x000000FF)<<16)){
										//S insert RL +0
										if(!r->RL){
											r->RL = new HTTNODE<DataType>;
											memset(r->RL,0,sizeof(HTTNODE<DataType>));
										}
										return bttinsert(r->RL,key,data);
									}else{
										//N insert RR +0
										if(!r->RR){
											r->RR = new HTTNODE<DataType>;
											memset(r->RR,0,sizeof(HTTNODE<DataType>));
										}
										return bttinsert(r->RR,key,data);
									}
								}
							}
						}
					}
				}
			}else{
				//N [NM == BA]
				if((r->C& 0x0000FFFF) == (s & 0x0000FFFF)){
					//S [C == 0]
					if((s & 0x00FF0000)==0x00000000){
						//S insert nvalue
						if(!r->nvalue){
							r->nvalue = data;++bttsize;
							return r;
						}else{
							//cout<< "collision nvalue " << endl;
							return NULL;
						}
					}else{
						//N insert EE +2
						if(!r->EE){
							r->EE = new HTTNODE<DataType>;
							memset(r->EE,0,sizeof(HTTNODE<DataType>));
						}
						return bttinsert(r->EE,key+2,data);
					}
				}else{
					//N   [M == 0]
					if((r->C& 0x000000FF) == 0x00000000){
						//S   M = A
						r->C |= s &0x000000FF; //insert M
						//insert value
						if(!r->value){
							r->value = data;++bttsize;
							return r;
						}else{
							//cout<< "collision value " << endl;
							return NULL;
						}
					}else{
							//N   [M == A ]
						if((r->C& 0x000000FF) == (s&0x000000FF)){
									//S [N == 0]
									if((r->C& 0x0000FF00) == (0x00000000)){
										//S [C == 0]
										if((s& 0x00FF0000) == (0x00000000)){
											//S insert nvalue return r;
											if(!r->nvalue){
												r->nvalue = data;++bttsize;
												return r;
											}else{
												//cout<< "collision nvalue " << endl;
												return NULL;
											}
										}
									}else{
										//N [ N == B]
										if((r->C& 0x0000FF00) == (s&0x0000FF00)){
											//S [C == 0]
											if((s& 0x00FF0000) == (0x00000000)){
												//cout<< "collision nvalue " << endl;
												return NULL;
											}else{
												//N insert EE + 2
												if(!r->EE){
													r->EE = new HTTNODE<DataType>;
													memset(r->EE,0,sizeof(HTTNODE<DataType>));
												}
												return bttinsert(r->EE,key+2,data);
											}
										}else{
											//N [N > B]
											if((r->C& 0x0000FF00) > (s&0x0000FF00)){
												//S insert EL +1
												if(!r->EL){
													r->EL = new HTTNODE<DataType>;
													memset(r->EL,0,sizeof(HTTNODE<DataType>));
												}
												return bttinsert(r->EL,key+1,data);
											}else{
												//N insert ER +1
												if(!r->ER){
													r->ER = new HTTNODE<DataType>;
													memset(r->ER,0,sizeof(HTTNODE<DataType>));
												}
												return bttinsert(r->ER,key+1,data);
											}
										}
									}
								}else{
								//N [ M > A]
								if((r->C& 0x000000FF) == (s&0x000000FF)){
									//S [L == 0]
									if((r->C& 0xFF000000) == 0x00000000){
										//S L = A
										r->C |= ((s &0x000000FF) << 24); //insert L
										//insert lvalue
										if(!r->lvalue){
											r->lvalue = data;++bttsize;
											return r;
										}else{
											//cout<< "collision lvalue" << endl;
											return NULL;
										}
									}else{
										//N [L == A]
										if((r->C& 0xFF000000) == ((s & 0x000000FF)<<24)){
											if(!r->LE){
												r->LE = new HTTNODE<DataType>;
												memset(r->LE,0,sizeof(HTTNODE<DataType>));
											}
											return bttinsert(r->LE,key+1,data);
										}else{
											//N [L > A]
											if((r->C& 0xFF000000) > ((s & 0x000000FF)<<24)){
												//S insert LL +0
												if(!r->LL){
													r->LL = new HTTNODE<DataType>;
													memset(r->LL,0,sizeof(HTTNODE<DataType>));
												}
												return bttinsert(r->LL,key,data);
											}else{
												//N insert LR +0
												if(!r->LR){
													r->LR = new HTTNODE<DataType>;
													memset(r->LR,0,sizeof(HTTNODE<DataType>));
												}
												return bttinsert(r->LR,key,data);
											}
										}
									}
								}else{
									//N [R == 0]
									if((r->C& 0x00FF0000) == 0x00000000){
										//S R = A
										r->C |= ((s &0x000000FF) << 16); //insert R
										//insert rvalue
										if(!r->rvalue){
											r->rvalue = data;++bttsize;
											return r;
										}else{
											//cout<< "collision rvalue " << endl;
											return NULL;
										}
									}else{
									//N [R == A]
									if((r->C& 0x00FF0000) == ((s&0x000000FF)<<16)){
										if(!r->RE){
											r->RE = new HTTNODE<DataType>;
											memset(r->RE,0,sizeof(HTTNODE<DataType>));
										}
										return bttinsert(r->RE,key+1,data);
									}else{
										//N [R > A]
										if((r->C& 0x00FF0000) > ((s&0x000000FF)<<16)){
											//S insert RL +0
											if(!r->RL){
												r->RL = new HTTNODE<DataType>;
												memset(r->RL,0,sizeof(HTTNODE<DataType>));
											}
											return bttinsert(r->RL,key,data);
										}else{
											//N insert RR +0
											if(!r->RR){
												r->RR = new HTTNODE<DataType>;
												memset(r->RR,0,sizeof(HTTNODE<DataType>));
											}
											return bttinsert(r->RR,key,data);
										}
									}
								}
							}
						}
					}
				}
			}
		}
	}
	//Search for a given key
	int bttsearch(const char *key){
		return bttsearch(root,key);
	}
	//Search for a given key starting at node r
	int bttsearch(HTTNODE<DataType>* r,const char *key)
	{
		//LRNM DCBA
		unsigned int s=*((unsigned int*)key);
		//[A == 0]
			//S return error!
		if((s & 0x000000FF) == 0x00000000){
			return 0;
		}
		//[NM == 00]
		if((r->C& 0x000FFFF) == 0x00000000){
			//S [B == 0]
			if((s & 0x0000FF00) == 0x00000000){
				if(!r->value){
					return 0;
				}else{

					return 1;
				}
			}else{
				//[C == 0]
				if((s & 0x00FF0000) == 0x00000000)
				{
					//S inset nvalue 
					if(!r->nvalue){
						return 0;
					}else{
						return 1;
					}
				}else{
					//N insert EE +2
					if(!r->EE){
						return 0;
					}
					return bttsearch(r->EE,key+2);
				}
			}
		}else{
			//N [B == 0]
			if((s & 0x0000FF00) == 0x00000000){
				//S [M == 0]
				if((r->C& 0x00000FF) == 0x00000000){
					if(!r->value){
						return 0;
					}else{
						return 1;
					}
				}else{
					//N   [M == A ]
					if((r->C& 0x000000FF) == (s & 0x000000FF)){
						return 1;
					}else{
						//N [ M > A]
						if((r->C& 0x000000FF) > (s & 0x000000FF)){
								//S [L == 0]
								if((r->C& 0xFF000000) == 0x00000000){
									if(!r->lvalue){
										return 0;
									}else{

										return 1;
									}
								}else{
									//N [L == A]
									if((r->C& 0xFF000000) == ((s & 0x000000FF)<<24)){

										return 1;
									}else{
										//N [L > A]
										if((r->C& 0xFF000000) > ((s & 0x000000FF)<<24)){
											//S insert LL +0
											if(!r->LL){
												return 0;
											}
											return bttsearch(r->LL,key);
										}else{
											//N insert LR +0
											if(!r->LR){
												return 0;
											}
											return bttsearch(r->LR,key);
										}
									}
								}
						}else{
							//N [R == 0]
							if((r->C& 0x00FF0000) == 0x00000000){
								if(!r->rvalue){
									return 0;
								}else{
									return 1;
								}
							}else{
								//N [R == A]
								if((r->C& 0x00FF0000) == ((s&0x000000FF)<<16)){
									//cout<< "collision rvalue " << endl;
									return 1;
								}else{
									//N [R > A]
									if((r->C& 0x00FF0000) > ((s&0x000000FF)<<16)){
										if(!r->RL){
											return 0;
										}
										return bttsearch(r->RL,key);
									}else{
										if(!r->RR){
											return 0;
										}
										return bttsearch(r->RR,key);
									}
								}
							}
						}
					}
				}
			}else{
				//N [NM == BA]
				if((r->C& 0x0000FFFF) == (s & 0x0000FFFF)){
					//S [C == 0]
					if((s & 0x00FF0000)==0x00000000){
						//S insert nvalue
						if(!r->nvalue){
							return 0;
						}else{
							//cout<< "collision nvalue " << endl;
							return 1;
						}
					}else{
						//N insert EE +2
						if(!r->EE){
							return 0;
						}
						return bttsearch(r->EE,key+2);
					}
				}else{
					//N   [M == 0]
					if((r->C& 0x000000FF) == 0x00000000){
						if(!r->value){
							return 0;
						}else{
							//cout<< "collision value " << endl;
							return 1;
						}
					}else{
						//N   [M == A ]
						if((r->C& 0x000000FF) == (s&0x000000FF)){
									//S [N == 0]
									if((r->C& 0x0000FF00) == (0x00000000)){
										//S [C == 0]
										if((s& 0x00FF0000) == (0x00000000)){
											if(!r->nvalue){
												return 0;
											}else{
												//cout<< "collision nvalue " << endl;
												return 1;
											}
										}
									}else{
										//N [ N == B]
										if((r->C& 0x0000FF00) == (s&0x0000FF00)){
											//S [C == 0]
											if((s& 0x00FF0000) == (0x00000000)){
												//cout<< "collision nvalue " << endl;
												return 1;
											}else{
												//N insert EE + 2
												if(!r->EE){
													return 0;
												}
												return bttsearch(r->EE,key+2);
											}
										}else{
											//N [N > B]
											if((r->C& 0x0000FF00) > (s&0x0000FF00)){
												//S insert EL b+1
												if(!r->EL){
													return 0;
												}
												return bttsearch(r->EL,key+1);
											}else{
												//N insert ER b+1
												if(!r->ER){
													return 0;
												}
												return bttsearch(r->ER,key+1);
											}
										}
									}
								}else{
								//N [ M > A]
								if((r->C& 0x000000FF) == (s&0x000000FF)){
									//S [L == 0]
									if((r->C& 0xFF000000) == 0x00000000){
										if(!r->lvalue){
											return 0;
										}else{
											//cout<< "collision lvalue" << endl;
											return 1;
										}
									}else{
										//N [L == A]
										if((r->C& 0xFF000000) == ((s & 0x000000FF)<<24)){
											//S return collision
											//cout<< "collision lvalue" << endl;
											return 1;
										}else{
											//N [L > A]
											if((r->C& 0xFF000000) > ((s & 0x000000FF)<<24)){
												//S insert LL b
												if(!r->LL){
													return 0;
												}
												return bttsearch(r->LL,key);
											}else{
												//N insert LR b
												if(!r->LR){
													return 0;
												}
												return bttsearch(r->LR,key);
											}
										}
									}
								}else{
									//N [R == 0]
									if((r->C& 0x00FF0000) == 0x00000000){
										if(!r->rvalue){
											return 0;
										}else{
											//cout<< "collision rvalue " << endl;
											return 1;
										}
									}else{
									//N [R == A]
									if((r->C& 0x00FF0000) == ((s&0x000000FF)<<16)){
										//cout<< "collision rvalue " << endl;
										return 1;
									}else{
										//N [R > A]
										if((r->C& 0x00FF0000) > ((s&0x000000FF)<<16)){
											//S insert RL b
											if(!r->RL){
												return 0;
											}
											return bttsearch(r->RL,key);
										}else{
											//N insert RR b
											if(!r->RR){
												return 0;
											}
											return bttsearch(r->RR,key);
										}
									}
								}
							}
						}
					}
				}
			}
		}
	}
	//Get the size of the tree (number of key/data pairs)
	unsigned int size(){return bttsize;}
private:
	//Delete everything under node p (including it)
	void bttdelete(HTTNODE<DataType>* p)
	{   if (!p) return;
		bttdelete(p->LL);
		bttdelete(p->LE);
		bttdelete(p->LR);

		bttdelete(p->EL);
		bttdelete(p->EE);
		bttdelete(p->ER);

		if(p->lvalue){
			--bttsize;
			delete p->lvalue;
		}
		if(p->value){
			--bttsize;
			delete p->value;
		}
		if(p->nvalue){
			--bttsize;
			delete p->nvalue;
		}
		if(p->rvalue){
			--bttsize;
			delete p->rvalue;
		}
	    
		bttdelete(p->RL);
		bttdelete(p->RE);
		bttdelete(p->RR);
		
		delete p;
	}
};

//simple data struct to use as Data
struct string_data{
	char data[50];
};
//This function test the normal behavior of the tree:
//insert values on the tree - but not in a straight foward way...
void testBTT(int max){
	string_data *str;
    char key[sizeof(int)*50];
	HTTree<string_data > HTTree;
    int i;

	//clear the key memory
    memset(&key,0,sizeof(int)*50);

    //insert the first half of the keys 
	for(i=max - (max/2);i>=1 ;i--){
        sprintf((char*)&key,"%.8d",i); // create the string for the key
		str=new string_data; // create the new data
		strcpy((char*)&str->data,(char*)&key);//copy the key also in data (just for testing)
        HTTree.bttinsert((char*)&key,str);//insert the pair
    }
	//insert the second half
	for(i=max - (max/2);i<= max ;i++){
        sprintf((char*)&key,"%.8d",i);
		str=new string_data;
		strcpy((char*)&str->data,(char*)&key);
        HTTree.bttinsert((char*)&key,str);
    }

	//search all the key space to see if something get wrong
    for(i=1;i<=max ;i++){
        sprintf((char*)&key,"%.8d",i);//create the key string
        if(!HTTree.bttsearch((char*)&key)){ //search
            printf("key not found %d\n",i);
            break;
        }
    }
	//clear the tree
	HTTree.bttclear();

}
///////////////////////////////////////////////////////////////////
//simplistic ternary tree
//this tree I create for testing the "integrity" of my HTTree
//sorry but I'll not explain the ternary tree algorithm...
//////////////////////////////////////////////////////////////////
#define BUFFER_SIZE 50
typedef struct tnode *Tptr;
typedef struct tnode {
    char splitchar;
    char* value;
    Tptr lokid, eqkid, hikid;
} Tnode;

char* insertstr;
Tptr insert(Tptr r,char * b)
{   

    char*s = b;
    Tptr p = r,base;
    if(r==NULL){
        p = (Tptr)malloc(sizeof(Tnode));
        memset(p,0,sizeof(Tnode));
        p->splitchar = *s;
        p->lokid = p->eqkid = p->hikid = NULL;
        base=p;
    }else
        base=r;
begin:
    if (p == NULL) {
        p = (Tptr)malloc(sizeof(Tnode));
        memset(p,0,sizeof(Tnode));
        p->splitchar = *s;
        p->lokid = p->eqkid = p->hikid = NULL;
        
    }
    if (*s < p->splitchar){
        if(!p->lokid){
            p->lokid = (Tptr)malloc(sizeof(Tnode));
            memset(p->lokid,0,sizeof(Tnode));
            p = p->lokid;p->splitchar = *s;
            p->lokid = p->eqkid = p->hikid = NULL;
        }else
            p = p->lokid;
        goto begin;
    }else 
        if (*s == p->splitchar) {
            if (*s == '\0'){
                if(p->value){
/*                    //printf("collision of values\n");  */
                    return NULL;
                }
                //p->value = strdup(insertstr);
                p->value = (char*)malloc(strlen(insertstr)+1);
                memset(p->value,0,strlen(insertstr)+1);
                strcpy(p->value,insertstr);
            }else{
                ++s;
                if(!p->eqkid){
                    p->eqkid = (Tptr)malloc(sizeof(Tnode));
                    memset(p->eqkid,0,sizeof(Tnode));
                    p = p->eqkid;p->splitchar = *s;
                    p->lokid = p->eqkid = p->hikid = NULL;
                }else
                    p = p->eqkid;
                goto begin;
            }
        } else{
            if(!p->hikid){
                p->hikid = (Tptr)malloc(sizeof(Tnode));
                memset(p->hikid,0,sizeof(Tnode));
                p = p->hikid;p->splitchar = *s;
                p->lokid = p->eqkid = p->hikid = NULL;
            }else
                p = p->hikid;
            goto begin;
        }
    return base;
}
int search(Tptr root,char *b)
{   Tptr p;
    char*s=b;
    p = root;
    while (p) {
        if (*s < p->splitchar)
            p = p->lokid;
        else if (*s == p->splitchar)  {
            if (*s == 0){
/*              //printf("found %s\n",p->value);  */
                return 1;
            }
            p = p->eqkid;
            ++s;
        } else
            p = p->hikid;
    }
    return 0;
}
int ttsize=0;
void traverse(Tptr p)
{   if (!p) return;
    traverse(p->lokid);
    if (p->splitchar)
        traverse(p->eqkid);
    else{
        //printf("%s\n",p->value);
		++ttsize;
    }
    traverse(p->hikid);
}
void ttdelete(Tptr p)
{   if (!p) return;
    ttdelete(p->lokid);
    if (p->splitchar)
        ttdelete(p->eqkid);
    else{
        free(p->value);
    }
    ttdelete(p->hikid);
	free(p);
}
///////////////////////////////////////////////////////////////////////////////////
//Now the tree integrity will be tested! If there is something different in the
//two trees, then a error message should be fired and the program ends!
//but everything is working fine... ;-)

//this global HTTree is for easy access by the traverseForTesting function
HTTree<string_data > HTTree_integrity;

//This function search all values in the simpler ternary tree and check if it exists in the HTTree also
void traverseForTesting(Tptr p)
{   if (!p) return;
    traverseForTesting(p->lokid);
    if (p->splitchar)
        traverseForTesting(p->eqkid);
    else{
        //printf("%s\n",p->value);
		if(!HTTree_integrity.bttsearch(p->value)){
			//if there is a key in one and not in the other
			printf("################# not found [%s] !!!!!!!!!!!\n",p->value);
			//end execution
			exit(1);
        }
		//this else is for debugging - and see the values inside
		//else
			//printf("found [%s]",p->value);
    }
    traverseForTesting(p->hikid);	
}

#include <time.h>
//This function build the environment for the integrity test:
//it insert random keys and values in both trees and check if
//both are the same!
void TestIntegrity(unsigned int max)
{
	char buffer[sizeof(int)*50];
	unsigned int i;
    Tptr   rootTT = NULL;//ternary tree root node
	string_data *str;
    
	srand( (unsigned)time( NULL ) );//initialize the random

    memset(&buffer,0,sizeof(int)*50);//clear the buffer
    insertstr = (char*)&buffer; //pointer to insert value - simpler ternary tree

    sprintf((char*)&buffer,"%.8d",rand());//first key
    rootTT = insert(rootTT,(char*)&buffer);//insert on the simpler ternary tree

	str=new string_data;//new data struct
	strcpy((char*)&str->data,(char*)&buffer);//copy the key into the data struct
    HTTree_integrity.bttinsert((char*)&buffer,str);//insert on the HTTree

	//repeat the insertion until max is reached
    for(i=1;i<=max ;i++){
        sprintf((char*)&buffer,"%.8d%.8d",i,rand());
        insert(rootTT,(char*)&buffer);

		str=new string_data;
		strcpy((char*)&str->data,(char*)&buffer);
        HTTree_integrity.bttinsert((char*)&buffer,str);
    }
    ttsize=0;//set the ternary tree size as zero
    traverseForTesting(rootTT);//check the integrity
	traverse(rootTT);//count the key/data pairs in the simpler ternary tree
	//show the sizes
    cout << "sizes[" << HTTree_integrity.size() << "==" << ttsize << "]" << endl;
	//clear the root - this is to show that the tree can be re-used
	HTTree_integrity.bttclear();
	//clear the simpler ternary tree
	ttdelete(rootTT);
}

//WARNING this program uses lots of memory in the test. If you have less than 1 gigabyte of
//ram, set the max parameters to a lower value!!!
int _tmain(int argc, _TCHAR* argv[])
{
	int i=0;
	//simple test using the HTTree 
	testBTT (1000000);

	//Do the integrity test 10 times
	while(i++<=10)
		 TestIntegrity(500000);

	cout << "everything is fine!!" << endl;
	return 0;
}