00001
00009 #include <stdio.h>
00010 #include <string.h>
00011 #include <stdlib.h>
00012 #include <time.h>
00013 #include "util.h"
00014
00019 #define BUFSIZE 32
00020
00024 long seed=0;
00025
00026 int rgets(char** str)
00027 {
00028 char* str1,* str2;
00029 char tmp;
00030 int length,count;
00031
00032 if(!str) return -2;
00033 else
00034 {
00035 length=BUFSIZE;
00036 str1=(char*)malloc((length+1)*sizeof(char));
00037
00038 if(!str)
00039 {
00040 *str=NULL;
00041 return -1;
00042 }
00043
00044 for(count=0;(tmp=getchar())!='\n';count++)
00045 {
00046 if(count>=length)
00047 {
00048 length*=2;
00049 str2=(char*)realloc(str1,length+1);
00050 if(!str2)
00051 {
00052 free(str1);
00053 *str=NULL;
00054 return -1;
00055 }
00056 else str1=str2;
00057 }
00058
00059 str1[count]=tmp;
00060 }
00061
00062 str1[count]='\0';
00063 *str=str1;
00064 return count;
00065 }
00066 }
00067
00068
00069
00070 int rgetsEOF(char** str)
00071 {
00072 char* str1,* str2;
00073 char tmp;
00074 int length,count;
00075
00076 if(!str) return -2;
00077 else
00078 {
00079 length=BUFSIZE;
00080 str1=(char*)malloc((length+1)*sizeof(char));
00081
00082 if(!str1)
00083 {
00084 *str=NULL;
00085 return -1;
00086 }
00087
00088 for(count=0;(tmp=getchar())!=EOF;count++)
00089 {
00090 if(count>=length)
00091 {
00092 length*=2;
00093 str2=(char*)realloc(str1,length+1);
00094 if(!str2)
00095 {
00096 free(str1);
00097 *str=NULL;
00098 return -1;
00099 }
00100 else str1=str2;
00101 }
00102
00103 str1[count]=tmp;
00104 }
00105
00106 str1[count]='\0';
00107 *str=str1;
00108 return count;
00109 }
00110 }
00111
00112
00113
00114 int rngets(char *str,int dim)
00115 {
00116 int length;
00117
00118 str[dim-1]=str[dim-2]=1;
00119 fgets(str,dim,stdin);
00120
00121 if(str[dim-1]=='\0'&&str[dim-2]!='\n')
00122 {
00123 while(getchar()!='\n');
00124 return -1;
00125 }
00126 else
00127 {
00128 length=strlen(str)-1;
00129 str[length]='\0';
00130 return length;
00131 }
00132 }
00133
00134
00135
00136 int getRandom(int min,int max)
00137 {
00138 int r;
00139
00140 if(!seed)
00141 {
00142 time(&seed);
00143 srand((unsigned)seed);
00144 }
00145
00146 r=min+rand()%(max-min+1);
00147
00148 return r;
00149 }
00150
00151
00152
00165 static int merge(void* vals[],int begin,int midle,int end,
00166 int(*comp)(void*,void*))
00167 {
00168 int i,j,k;
00169 int sizeLeft=midle-begin;
00170 int sizeRight=end-midle+1;
00171
00172 void** left=calloc(sizeLeft,sizeof(void*));
00173 void** right=calloc(sizeRight,sizeof(void*));
00174
00175 if(!left||!right) return 1;
00176 else
00177 {
00178 for(i=0;i<sizeLeft;i++) left[i]=vals[begin+i];
00179 for(i=0;i<sizeRight;i++) right[i]=vals[midle+i];
00180
00181 for(i=0,j=0,k=begin;k<=end;k++)
00182 {
00183 if(j>=sizeRight||(i<sizeLeft&&((*comp)(left[i],right[j])<0)))
00184 {
00185 vals[k]=left[i];
00186 i++;
00187 }
00188 else
00189 {
00190 vals[k]=right[j];
00191 j++;
00192 }
00193 }
00194
00195 return 0;
00196 }
00197 }
00198
00199
00200
00201 int mergeSort(void* vals[],int begin,int end,int(*comp)(void*,void*))
00202 {
00203 int m,res;
00204
00205 if(begin<end)
00206 {
00207 m=(begin+end)/2;
00208 res+=mergeSort(vals,begin,m,*comp);
00209 res+=mergeSort(vals,m+1,end,*comp);
00210 res+=merge(vals,begin,m+1,end,*comp);
00211 }
00212
00213 return res;
00214 }