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
 *deal with address's.
 *
 *
 *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.