circular_bst.c

This is a binary search tree with void* pointer in data segment in order you to search store and del

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


unsigned int size = 0;
short int found = 0;
short int del = 0;

Node_dt *CreateNew_dt(int id,int m){
	root = malloc(sizeof(Node_dt));
	root->id = id;
	root->rc = NULL;
	root->lc = NULL;
	root->p = NULL;
	root->DocL = (struct Node_sl*)CreateNew();
	printf("create root with id %d\n",id);
	size = 1;
	maxf = m;
	return root;
}

int Insert_dt(int id){
	/*if((2 >> maxf) > size) return -1;*/
	if(size < 1) {
	  CreateNew_dt(id,maxf);printf("Creating List from schratch\n");
	  return 1;
	}
	Node_dt *min = findMin_dt(root);
	Node_dt* targ = Find_dt(id);
	Node_dt* nextNode = NULL;
	if(targ->id == id)
		return -1;
	Node_dt* new = malloc(sizeof(Node_dt));
	if(targ->id > id)
		targ->lc = new;
	else
		targ->rc = new;
	new->id = id;
	new->p = targ;
	new->lc = NULL;
	new->rc = NULL;
	new ->DocL = (struct Node_sl*)CreateNew();
	size++;
/* Deal with files */
	findNextInorder_dt(root,&nextNode, id);
	found = 0;
	if(!nextNode ){
	  nextNode = findMin_dt(root);
	  Node_sl *file = nextNode->DocL;
	  while(file->next){
			file = file->next;
			if(file->id <= id && file->id > nextNode->id) {/*BAD SLOWWW*/
				Insert_sl(file->id,file->type,new->DocL);
				Delete_sl(file->id,nextNode->DocL);
			}
			
		}
	}
	else if( new->id < min->id ){
	  printf("MANIPULATE STRANGE FILE %d with next %d\n",new->id, nextNode->id);
	  Node_sl *file = nextNode->DocL;
	  while(file->next){
			file = file->next;
			if(file->id <= new->id  || file->id > nextNode->id) {/*BAD SLOWWW*/
			printf("File %d moved from %d to %d\n",file->id,nextNode->id,new->id);
				Insert_sl(file->id,file->type,new->DocL);
				Delete_sl(file->id,nextNode->DocL);
			}
			
		}
	}
	else{
	  printf("MANIPULATING NORMAL FILE %d with next %d\n",new->id, nextNode->id);
	  Node_sl *file = nextNode->DocL;
	  while(file->next){
			  file = file->next;
			  if(file->id <= id) {/*BAD SLOWWW*/
				  Insert_sl(file->id,file->type,new->DocL);
				  Delete_sl(file->id,nextNode->DocL);
			  }
			  
		  }
	}
/*Done with files*/
	return 1;
}


Node_dt* Find_dt(int id){
	Node_dt* tmp = root;
	while(tmp) {
		if(id > tmp->id) {
			if(tmp->rc == NULL){
				
				return tmp;	
			}
				tmp = tmp->rc;
 			continue;
		}
		else if(id < tmp->id) {
			if(tmp->lc == NULL){
				
				return tmp;
			}
				tmp = tmp->lc;
			continue;
		}
		else if(id == tmp->id){
			return tmp;
		}
	}
	return NULL;
}
int Delete_dtfinal(int id) {
      Node_dt *nextNode =NULL;
      Node_dt* tmp = Find_dt(id);
      findNextInorder_dt(root,&nextNode, id);
      found = 0;
      if(!nextNode)
	 nextNode = findMin_dt(root);
      Node_sl *file = tmp->DocL;
	  while(file->next){
	      file = file->next;
	      Insert_sl(file->id,file->type,nextNode->DocL);
	      Delete_sl(file->id,tmp->DocL);
	  }
	 Delete_dt(id);
}
int Delete_dt(int id){
	Node_dt* tmp = Find_dt(id);
	Node_dt *par = NULL,  *child = NULL, *successor = NULL; //Parent to child pointer, parent
	  Node_dt *nextNode = NULL;
	  if(size == 0) return -1;
	  else if(tmp->id != id) return -1; // found?
	  (par) = tmp->p;
		if(!tmp->lc && !tmp->rc){
		  if(par){
		    if(tmp->id < par->id){
			  par->lc = NULL;
		    }
		    else 
			  par->rc = NULL;
		    }
		    else
		      root = NULL;
		  }
		else if(!tmp->rc)  {
		  child = tmp->lc;
		  if(par){
		   if(tmp->id < par->id)
			par->lc = child;
		    else 
			par->rc = child;
		   }
		   else{
		    root = child;
		   }
		  child->p = par;
		 }
	
		else if(!tmp->lc){
		  child = tmp->rc;
		  if(par){
		   if(tmp->id < par->id)
			par->lc = child;
		    else 
			par->rc = child;
		   }
		   else{
		    root = child;
		   }
		  child->p = par;
		  }
		else {
			successor = findMin_dt(tmp->rc);
 			if(!successor)
 				return -1;
			int succId = successor->id;
			Node_sl *Docl = successor->DocL;
			Delete_dt(successor->id);
			tmp->id = succId;
			tmp->DocL = Docl;
			return 1;
		}
	size--;
	free(tmp);
	return 1;
}

Node_dt* findMin_dt(Node_dt* node){
	Node_dt* tmp = node;
	while(tmp->lc) tmp=tmp->lc;
	return tmp;
}
void _print(Node_dt* node){
  if(node){
	if(node->lc) _print(node->lc);
	printf("Nodeid %d\n",node->id);
	print_sl(node->DocL);
	printf("\n");
	if(node->rc) _print(node->rc);
  }
}

void findNextInorder_dt(Node_dt* node,Node_dt** ret, int id){
	if(node->lc && !found) findNextInorder_dt(node->lc,ret ,id);
	if(node->id > id && !found) {
		*ret = node;
		found = 1;
		return ;
	}
	if(node->rc && !found) findNextInorder_dt(node->rc,ret,id);
	return;
}

void print_dt(void) {
	printf("TOTAL SIZE %d\n",size);
	_print(root);
}

Node_sl* Find_File(int id) {
  Node_dt* tmp = Find_dt(id);
  if(tmp->id >= id){
    return Find_sl(id,tmp->DocL);
    }
  else{
    Node_dt* insNode=NULL;
    findNextInorder_dt(root,&insNode, tmp->id);
    found =0;
    if(insNode)
      return Find_sl(id,insNode->DocL);
    else
      return Find_sl(id,findMin_dt(root)->DocL);
   }
   return 1;
}

int Insert_File(int id, int type){
  Node_dt* tmp = Find_dt(id);
  if(tmp->id >= id){
    Insert_sl(id,type,tmp->DocL);
    }
  else{
    Node_dt* insNode=NULL;
    findNextInorder_dt(root,&insNode, tmp->id);
    found =0;
    if(insNode){
      Insert_sl(id,type,insNode->DocL);
    }
    else{

      Insert_sl(id,type,findMin_dt(root)->DocL);
    }
   }
   return 1;
}

int Delete_File(int id){
  Node_dt* tmp = Find_dt(id);
  if(tmp->id >= id){
    Delete_sl(id, tmp->DocL);
   }
  else{
    Node_dt* delNode=NULL;
    findNextInorder_dt(root,&delNode, tmp->id);
    found =0;
    if(delNode){
      Delete_sl(id, delNode->DocL);
    }
    else{
      Delete_sl(id, findMin_dt(root)->DocL);
    }
   }
   return 1;
}