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
It's not a gadget but something related to them yes its Podcasting!!. Podcasting is real fun, so what excatly is this podcasting? . hmmm..... I guess most of you have already been using RSS feeds (adding them to firefox livefeed toolbar) :-? , podcasting is akin to RSS syndication, actually normal RSS feeds get you only the text content from where ever you have subscribed the feed, now just imagine a feed which will play audio when ever you select it, rather than reading the feed you are now listening to the feed, sounds great!! right? this is excatly what is podcasting. In a little geeky terms podcasting is similar to tunnelling (protocol tunnelling) where you add (embedd) 'protocol2' in the carrier 'protocol1' as a payload, so the multimedia content is being added as the payload in RSS (Really simple syndication protocol) 2.0 protocol for syndicating audio content from the publisher.
So lets come to the bottomline "how can I get podcasting work".
1. Get a podcatcher I use 
