## Thursday, September 20, 2007

### [TECH] Generic Randomized Quicksort algorithm.

Adding to my own collection of generic data structures, today I added a generic Randomized Quicksort algorithm, I need a good sorting routine in the SAPE algorithm for sorting distances. I want to makesure that it can sort any kind array (array of char's,int's,float's,double's and also structures).


/*A generic Randomized Quicksort:
*The key idea of being generic comes
*from the fact that you take a memory
*block and size of each element and
*sort this memory chunk, so we always
*
*
*Sep 20,2007 vamsik@engr.uconn.edu
**/
#include
#include
#include
#include
#include
#include "RandQsort.h"

/*INPUT: swap_routine,compare_routine
* swap_routine: The algorithm gives the
* (void *)'s swap_routine of two things
* which need to be swapped.
*
* compare_routine: The algorithm gives the
* (void *)'s to the compare_routine its
*/
static char QSORT_RAND_SEED=0;
static void (*swap_routine)(void *,void *) = NULL;
static unsigned char (*compare_routine_l)(void *,void *) = NULL;
static unsigned char (*compare_routine_g)(void *,void *) = NULL;
static time_t t_rqsort;
unsigned int GetPivot(void){
if(!QSORT_RAND_SEED){
assert(((time_t)-1)!=time(&t_rqsort));
srand(t_rqsort);
fprintf(stdout,"Setting RAND_SEED to %d \n",t_rqsort);
QSORT_RAND_SEED=1;
}
return ((unsigned int)rand());
}
/*Avoid loosing the pivot during swaps*/
void UpdatePivot(void **pivot,void **i,void **j){
if(*i==*pivot){
*pivot = *j;
}else if(*j == *pivot){
*pivot = *i;
}
}
/*Take a memory address location and size
of the data items[Inplace partition]*/
static void PartitionWithPivot(void* start,void* end,
unsigned int dsize){
void *pivot=NULL;
void* i=start;
void* j=end;
unsigned int p_index = GetPivot();
if(start==end){
return;
}
p_index %= (((unsigned int)(end-start))/dsize);
pivot=(void *)((unsigned long)start+
(unsigned long)((p_index)*dsize));
while(i=start)){
j-=dsize;
}
/*Swap i,j*/
if(istart){
swap_routine(pivot,(void *)(i-dsize));
PartitionWithPivot(start,(void *)(i-(2*dsize)),
dsize);
}
if((i+dsize)<=end){
PartitionWithPivot(i,end,dsize);
}
}
/*Call PartitionWithPivot recursively*/
void RandQsort(void *start,void *end,unsigned int dsize,
void_void_fptr sroutine,bool_void_fptr croutine_l){
swap_routine = sroutine;
compare_routine_l = croutine_l;
assert(swap_routine && compare_routine_l);
PartitionWithPivot(start,end,dsize);
}
#ifdef UNIT_TEST_RQSORT
/*TEST1:Testing for chars*/
unsigned char CharCompare_L(void *a,void *b){
return ((*((char *)a))<=(*((char *)b)))?1:0;
}
unsigned char CharCompare_G(void *a,void *b){
return ((*((char *)a))>=(*((char *)b)))?1:0;
}
void CharSwap(void *a,void *b){
char temp=*((char *)a);
*((char *)a) = *((char *)b);
*((char *)b) = temp;
}
void TestCharSort(){
char *data = malloc(sizeof(char)*10);
char test_buffer[64];
unsigned int i,j,k;
time_t test_time;
for(i=0;i<10;i++){
data[9-i] = '0'+i;
}
/*Randomize the input data*/
time(&test_time);
srand(test_time);
for(i=0;i<100;i++){
j=(rand())%10;
k=(rand())%10;
test_buffer[63]=data[j];
data[j]=data[k];
data[k]=test_buffer[63];
}
/*Print the buffer*/
if(strncpy(test_buffer,data,10)!=test_buffer){
fprintf(stderr,"SYSTEM_ISSUE:Copy into buffer failed\n");
}else{
test_buffer[10]='\0';
fprintf(stdout,"%s\n",test_buffer);
}
RandQsort((void *)data,(void *)(data+9),1,
CharSwap,CharCompare_L);
for(i=0;i<10;i++){
if(data[i]-('0'+i)){
printf("Test Failed for Chars\n");
printf("Expecting %d but found %d\n",i,
((unsigned int)data[i]-'0'));
exit(1);
}
}
test_buffer[0]='\0';
if(strncpy(test_buffer,data,10)!=test_buffer){
fprintf(stderr,"FAILED_TEST: UNABLE TO COPY BUFFER\n");
fprintf(stderr,"MAY_BE_SOME_MEMORY_CORRUPTION_DURING_SORT\n");
exit(1);
}else{
fprintf(stdout,"%s\n",data);
}
printf("Test Passed For Chars....\n");
}

unsigned char FloatCompare(void *a,void *b){
int a_int = (int)((*(float *)a)*10000);
int b_int = (int)((*(float *)b)*10000);
return (a_int<=b_int)?1:0;
}
void FloatSwap(void *a,void *b){
float temp;
temp = *((float *)a);
*((float *)a) = *((float *)b);
*((float *)b) = temp;
}

#include
void TestFloatSort(){
float *data = malloc(sizeof(float)*10);
float temp;
unsigned int i,j,k;
time_t test_time;
for(i=0;i<10;i++){
data[9-i] = (float)sin(i);
}
/*Randomize the input data*/
time(&test_time);
srand(test_time);
for(i=0;i<100;i++){
j=(rand())%10;
k=(rand())%10;
temp=data[j];
data[j]=data[k];
data[k]=temp;
}
/*Print the buffer*/
for(i=0;i<10;i++){
printf("%f ",data[i]);
}
printf("\n");
printf("The # of elements %d\n",(&data[9]-&data[0])/4);
RandQsort((void *)&data[0],(void *)&(data[9]),4,
FloatSwap,FloatCompare);
for(i=1;i<10;i++){
if(!FloatCompare((void *)&data[i-1],(void *)&data[i])){
printf("Test FAILED comparing %f , %f\n",
data[i-1],data[i]);
exit(1);
}
}
for(i=0;i<10;i++){
printf("%f ",data[i]);
}
printf("\n");
printf("Test Passed For Floats....\n");
}

/*Test for floats*/
int main(){
TestCharSort();
TestFloatSort();
exit(0);
}
#endif




## Saturday, September 08, 2007

### [TECH] Perl template toolkit and Bugzilla

I have now done with the customization of Bugzilla for our internal needs, to keep track of things. The core of the idea of templates was simple

• Seperate the presentation from the code
The good thing about using Perl + TTK is that the split (presentation code and actual code) is very wide compared to any other framework which I'm aware at least from my past experience. I have used the following frameworks previously. Its a very useful add on as a skill learn more about http://www.template-toolkit.org

Have few things to fix today, Add code to SAPE_1 with the new Center of Gravity algorithm.

Cheers!
Vamsi

## Monday, September 03, 2007

### [TECH] Bugzilla Internals

Got back to work today !

Was looking at the Bugzilla's perl code to extend it for some of my internal work, I found that it was a expert level perl code (Object oriented) they are using several things which I never used, It was a good learning experience.

I want extract few concepts from this code

• How do all these websystem's avoid hard coding of HTML inside the code which generate's HTML dynamically (I know its kind of servlet and JSP/ASP situation), I found that these guys have some mechanism based on templates which avoids hard coding of the HTML inside the dynamic HTML generation code

I guess this is the key idea/concept behind all the code which generates HTML dynamically.

I was reading Sriram's "Advanced Perl Programming" I think its a great book the way he build's up the concepts, I was really impressed by a quote by him in the book
"It is indicative of inflexible procedural design if you find yourself using conditional statements to distinguish between object types"

I want to go out to get some lunch today :)
Cheers!
Vamsi

## Sunday, September 02, 2007

### [NON-TECH] The old and cold feeling comes back........

I visited India from Aug10-Aug30 all those 20 days were great most of the time I was in Hyderabad, life was great in India except that there was a lot of pollution especially in Hyderabad and also overcrowded places especially because of the booming IT industry.

Some of the things I noticed have changed in India from the time I left

• The money spending power of people have increased a lot, I heard that the average salary for a undergrad is now around 5.0 lack/annum ($12.5k ), this was a huge increase compared to average of 2.4 lack/annum ($6k) which is more than double.
• The cost of living has gone up from the last year, I remember that I used to eat in a hotel called Kakatiya in Ameerpet a full meal for Rs 26.00/- the same costs Rs 32.00/- now. A bottle of mineral water went up to 13.00/- from 10.00/-
• There have been a lot of malls/multiplexes mushrooming every where in Hyderabad. I saw several existing houses being demolished and new multiplexes and malls are taking their place.
• Looks to me that almost every thing is available in India now. I was shocked to see PSP in Music World, I guess people are now getting into games market and if its true India will be a great market for selling computer games.
• In India cell phone has become a revolution I find that almost every one in the country has a mobile phone, thanks to Reliance which had a vision of making cell phones affordable to every one.

All these things are fine but my old feeling comes back again, I remember all those dilemma which I was having when I just landed in U.S went to riverside and came to UCONN, all those feeling are fresh in my mind. Well that COLD FEELING of missing India comes back again I don't know why but its back.....I feel sorry for myself I don't know what I'm up to in my life.....But I'm transforming my self to be better than what I used to be, and I believe that what ever is happening is just transformation for something better........as usual Connecticut is very lonely very quiet place, I used to go for jogging in India every day around 7-8 a.m in the morning.....

Well its life and lets face it without fear!
Cheer! Vamsi.