Friday, November 13, 2009

Rectangle intersection problem with tree datastructure

The problem here is to write a program that will find all the rectangles that intersects with a given rectangle once the left bottom and top right of the rectangles are given.

#include < stdio.h>
#include < stdlib.h>
#include < sys/stat.h>


struct rect {
int x,y;
struct rect *left,*right,*rtpoint;
};

int xmin,ymin,xmax,ymax;

typedef struct rect rec;
rec *root=NULL,*newptr=NULL;

void find(int x1,int cnd) {
rec *parent=NULL,*tptr=NULL;
rec *ptr=root;
while(ptr!=NULL) {
parent=ptr;
if(cnd==0) {
//if( ((ptr->x > x1) && (ptr->rtpoint)->x < x1) || ((ptr->x < x1) && ((ptr->rtpoint)->x>x1) ) )
if(ptr->rtpoint!=NULL) {
if(check(ptr)) {
printf("\nIntersects (%d,%d) - (%d, %d)\n",ptr->x,ptr->y,(ptr->rtpoint)->x,(ptr->rtpoint)->y);
(ptr->rtpoint)->rtpoint=NULL;
ptr->rtpoint=NULL;
}
}
}
if(ptr->x > x1)
ptr=ptr->left;
else
ptr=ptr->right;
}
if(cnd==1) {
if(parent->x > x1 )
parent->left=newptr;
else
parent->right=newptr;
}
}

int check(rec *temp) {
rec *temp2=temp->rtpoint;
int ys=temp->y,xs=temp->x;
int yr=temp2->y,xr=temp2->x,t;
if(ys>yr) {
t=ys;
ys=yr;
yr=t;
}
if(xs>xr) {
t=xs;
xs=xr;
xr=t;
}
return !( (yr <= ymin) || (ys >= ymax) || (xr <= xmin) || (xs >= xmax) );
}

void preorder(rec *ptr) {
if(ptr!=NULL) {
preorder(ptr->left);
printf("x=%d y=%d\n",ptr->x,ptr->y);
preorder(ptr->right);
}
}
void bt_free() {
if(root==NULL)
return;
bt_free(root->left);
bt_free(root->right);
free(root);
}

int main() {

FILE * fp;
int temp;
rec *temp_ptr=NULL;
struct stat stFileInfo;
char filename[50];
do {
printf ("Enter the filename to get data : ");
gets(filename);
temp=stat(filename,&stFileInfo);
if(temp!=0) {
printf("File doesnt exist!!! \n");
}
}while(temp != 0);
fp = fopen(filename,"r");
while(fscanf(fp,"%d %d %d %d",&xmin,&ymin,&xmax,&ymax) > 0) {
if(root==NULL) {
root=(rec *)malloc(sizeof(rec));
root->x=xmin;
root->y=ymin;
root->left=NULL;
root->right=NULL;
temp_ptr=root;
newptr=(rec *)malloc(sizeof(rec));
newptr->left=NULL;
newptr->right=NULL;
newptr->rtpoint=temp_ptr;
newptr->x=xmax;
newptr->y=ymax;
find(xmax,1);
temp_ptr->rtpoint=newptr;
}
else {
newptr=(rec *)malloc(sizeof(rec));
newptr->left=NULL;
newptr->right=NULL;
newptr->x=xmin;
newptr->y=ymin;
temp_ptr=newptr;
find(xmin,1);
newptr=(rec *)malloc(sizeof(rec));
newptr->left=NULL;
newptr->right=NULL;
newptr->rtpoint=temp_ptr;
newptr->x=xmax;
newptr->y=ymax;
find(xmax,1);
temp_ptr->rtpoint=newptr;
}
}
fclose(fp);
printf("Tree created successfully\nPreorder traversal follows\n");
preorder(root);
printf("\nEnter the test rectangle co-ordinates seperated by comas\n");
scanf("%d,%d,%d,%d",&xmin,&ymin,&xmax,&ymax);
if(xmin>xmax) {
temp=xmin;
xmin=xmax;
xmax=temp;
temp=ymin;
ymin=ymax;
ymax=temp;
}
find(xmin,0);
find(xmax,0);
bt_free();
return 0;
}


Sample input file
6 6 11 11
0 0 2 2
9 9 12 12
60 0 70 100
7 2 8 12

COM/Serial communication in C

This program will help you to understand how to do serial communication in C.
The C program will illustrate the basics of serial communication.


/////////////////////////////////////////////////
// Serial port interface program //
/////////////////////////////////////////////////

#include < stdio.h > // standard input / output functions
#include < string.h > // string function definitions
#include < unistd.h > // UNIX standard function definitions
#include < fcntl.h > // File control definitions
#include < errno.h > // Error number definitions
#include < termios.h > // POSIX terminal control definitionss
#include < time.h > // time calls
#include < stdlib.h >
#include < sys/types.h >
#include < netinet/in.h >
int fd;
int open_port(void)
{
int fd; // file description for the serial port

fd = open("COM2", O_RDWR);

if(fd == -1) // if open is unsucessful
{
perror("open_port: Unable to open /dev/ttyS0 - ");
}
else
{
printf("Opened %d\n",fd);
}

return(fd);
}

int configure_port(int fd) // configure the port
{
struct termios oldtio,port_settings; // structure to store the port settings in
tcgetattr(fd,&oldtio);
//cfsetispeed(&port_settings, B115200); // set baud rates
//cfsetospeed(&port_settings, B115200);

bzero (&port_settings, sizeof (port_settings));
port_settings.c_cflag = B115200 | CLOCAL | CREAD;
port_settings.c_cflag &= ~PARENB; // set no parity, stop bits, data bits 8N1
port_settings.c_cflag &= ~CSTOPB;
port_settings.c_cflag &= ~CSIZE;
port_settings.c_cflag |= CS8;
port_settings.c_iflag = IGNPAR | ICRNL;
port_settings.c_oflag = 0;
port_settings.c_lflag &= ~ICANON;
tcflush(fd, TCIFLUSH);
tcsetattr(fd,TCSANOW,&port_settings);
return(fd);
}

int query_modem(int fd) // query modem with an AT command
{

int k=0;
char str[5];
str[0]=2;
str[1]=str[2]='f';
str[3]=str[4]=3;
k=write(fd,str,strlen(str)); // send an AT command followed by a CR
printf("command %d\n",k);

}
int dsadas()
{
printf("In fm");
int bytesRead;
char *str;
char *buff;
//str=(char *)malloc(100*sizeof(char));
//buff=(char *)malloc(1024*sizeof(char));
while(1)
{

//printf("In while");
if(read(fd,str,10)>0)
{
printf("in if");
buff="";
printf("yesyeysyes %s\n",str);
//strcpy(buff,str);
do
{
//sleep(100);
//append
printf("Buffer = %s",buff);
strcat(buff,str);
bytesRead=read(fd,str,10);
}while(bytesRead>0);
//send bytes to ip
printf("Buffer = %s",buff);
}
}
}

int main(void)
{
pthread_t thread1,thread2;
fd = open_port();
configure_port(fd);
query_modem(fd);
int iret1, iret2;
//iret1 = pthread_create( &thread1, NULL, dsadas);
//pthread_join(thread1, NULL);
return(0);
}

Create tree from preorder traversal

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

int current=0;

struct bstree {
int val;
struct bstree *left,*right;
};

typedef struct bstree node;

node* tree_build(int* inarr,int* prearr,int left,int right);
void sort(int inarray[], int begin, int end);
void swap(int *a,int *b);
void inorder_traverse(node *ptr);
void bt_free(node *ptr);

main() {
int i;
int prearr[]={10,4,3,2,5,6,11,13,12};
int inarr[10];
for(i=0;i<9;i++)
inarr[i]=prearr[i];
sort(inarr,0,9);
node* root = tree_build(inarr,prearr,0,9);
printf("\n\nTREE CREATED. NOW DOING AN INORDER TRAVERSAL ON THE TREE...\n\n");
inorder_traverse(root);
printf("\n\n");
bt_free(root);
}

void bt_free(node *ptr) {
if(ptr==NULL)
return;
bt_free(ptr->left);
bt_free(ptr->right);
free(ptr);
}

void swap(int *a,int *b) {
int temp=*a;
*a=*b;
*b=temp;
}

void sort(int inarray[],int begin,int end) {
if (end > begin + 1) {
int pivot=inarray[begin],l=begin+1,r=end;
while(l if (inarray[l] <= pivot)
l++;
else
swap(&inarray[l],&inarray[--r]);
}
swap(&inarray[--l],&inarray[begin]);
sort(inarray,begin,l);
sort(inarray,r,end);
}
}

node* tree_build(int inarr[],int prearr[],int left,int right) {
int i,position;
if(left==right)
return NULL;
node *temp=(node *)malloc(sizeof(node));
temp->val=prearr[current];
if(left+1==right)
return temp;
i=left;
while(i if(inarr[i]==prearr[current])
break;
i++;
}
for(position=0;inarr[position]!=inarr[i];position++);
if(position>left) {
current++;
temp->left=tree_build(inarr,prearr,left,position);
}
if(position+1 current++;
temp->right=tree_build(inarr,prearr,position+1,right);
}
return temp;
}

void inorder_traverse(node *ptr) {
if(ptr==NULL)
return;
inorder_traverse(ptr->left);
printf(" %d - ",ptr->val);
inorder_traverse(ptr->right);
}