Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version
Go to top

HTTree - Hacked Ternary Tree Implementation

, 6 Jun 2006
This is a new type of tree based on the ternary tree algorithm
httree_demo.zip
HTTree
bin
HTTree.exe
HTTree
HTTree.suo
////////////////////////////////////////////////////////////////////////////////
// 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;
}


By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

GabrielWF
Software Developer (Senior)
Brazil Brazil
I did extremly different works: services to control harware, internet banking sites, Operational System migration (from Digital to Aix , from HpUX to Linux and from tru64 4.0 to 5.1b), Grafical user interfaces for lots of programs and different OS's...
I also know and had use Delphi, c, c++, java, python, assembly and perl.

| Advertise | Privacy | Mobile
Web01 | 2.8.140916.1 | Last Updated 6 Jun 2006
Article Copyright 2006 by GabrielWF
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid