52 CStreamPos(
long int inContent):mContent(inContent){
59 operator long int()
const{
64 mContent=mContent+
static_cast<T
>(1);
69 mContent=mContent+
static_cast<T
>(1);
74 return mContent % inMod;
77 return mContent / inMod;
79 bool operator< (CStreamPos<T>& inThan)
const{
80 return this->mContent < inThan.mContent;
82 bool operator! ()
const{
83 return !(this->mContent);
91 #define STREAMPOS_T long long int
93 #define STREAMPOS_T CStreamPos<fstream::pos_type>
108 void merge_streams(istream& in1,
const STREAMPOS_T inCount1,
109 istream& in2,
const STREAMPOS_T inCount2,
111 int inNumberOfPageElements=1){
119 const STREAMPOS_T lPageSize(
sizeof(T)*inNumberOfPageElements);
132 out.write((
char*)&l2,
146 out.write((
char*)&l1,
170 out.write((
char*)&l1,
183 out.write((
char*)&l2,
196 out.write((
char*)&l1,
208 out.write((
char*)&l2,
222 void first_level_quicksort(
int inNumberOfPageElements,
223 const char* inFileToBeSortedName,
224 const char* inTemporaryName){
226 cout <<
"Starting quicksort: "
227 << inNumberOfPageElements
228 <<
" elements per page." << endl
229 <<
"Sorting files " << inFileToBeSortedName << endl
230 <<
"to " << inTemporaryName << endl;
231 cout <<
"NOW ALLOCATING A PAGE" << inNumberOfPageElements << endl;
232 auto_ptr<T> lPage(
new T[inNumberOfPageElements]);
234 cout <<
"H" << flush;
236 const STREAMPOS_T lPageSize(
sizeof(T)*inNumberOfPageElements);
238 cout <<
"I" << flush;
240 STREAMPOS_T lFileSize(0);
241 ifstream lToBeSorted1(inFileToBeSortedName);
242 assert(lToBeSorted1);
243 lToBeSorted1.seekg(0,
245 lFileSize=lToBeSorted1.tellg();
246 lToBeSorted1.clear();
247 lToBeSorted1.seekg(0,
249 cout <<
"E" << flush;
251 ofstream lTemporary(inTemporaryName);
253 cout <<
"R" << flush;
257 T* lBegin(lPage.get());
258 T* lEnd(lPage.get());
260 cout <<
"FIRSTLEVELQUICK" << lFileSize <<
";" << lSum<< endl;
261 while((lSum<lFileSize)
264 cout <<
"." << flush;
267 if(lSum+lPageSize < lFileSize){
268 lToBeSorted1.read((
char*)lPage.get(),
272 lToBeSorted1.read((
char*)lPage.get(),
274 lRead=lFileSize-lSum;
277 lEnd=lBegin+(lRead)/
sizeof(T);
279 lTemporary.write((
char*)lPage.get(),lRead);
298 char* merge_sort_streams(
const char* inFileToBeSortedName,
299 const char* inTemporaryName,
300 int inNumberOfPageElements=(1 << 20)
303 const char* lFileToBeSortedName(inFileToBeSortedName);
304 const char* lTemporaryName(inTemporaryName);
306 STREAMPOS_T lFileSize(0);
307 ifstream lToBeSorted1(inFileToBeSortedName);
308 lToBeSorted1.seekg(0,
310 lFileSize=lToBeSorted1.tellg();
311 lToBeSorted1.close();
314 ifstream lToBeSorted2;
316 #ifdef first_level_quick
317 first_level_quicksort<T>(inNumberOfPageElements,
318 inFileToBeSortedName,
320 swap(lFileToBeSortedName,
323 cout <<
"STARTING mit MERGESIZE1" << endl;
324 inNumberOfPageElements=1;
326 STREAMPOS_T lCount(0);
327 for(STREAMPOS_T iMergeSize(
sizeof(T)*inNumberOfPageElements);
328 (iMergeSize < lFileSize)
335 (iMergeSize = iMergeSize << 1),
336 (lCount=lCount+static_cast<STREAMPOS_T>(1))){
338 cout <<
"MERGESORT MergeSize "
342 lToBeSorted1.open(lFileToBeSortedName);
343 lToBeSorted1.clear();
345 lToBeSorted2.open(lFileToBeSortedName);
346 lToBeSorted2.clear();
348 lTemporary.open(lTemporaryName);
352 for(STREAMPOS_T i(0);
354 i = i + iMergeSize*2){
355 lToBeSorted1.seekg(i);
358 cerr << __FILE__ <<
":" << __LINE__ <<
" lToBeSorted false, after seekg("
359 <<
static_cast<long int>(i)
364 assert(lToBeSorted1);
366 if(i+iMergeSize<lFileSize){
367 lToBeSorted2.seekg(i+iMergeSize);
368 assert(lToBeSorted2);
371 STREAMPOS_T lMergeSize1=lFileSize-i;
375 STREAMPOS_T lMergeSize2=lFileSize-i-iMergeSize;
376 if(lFileSize < i + iMergeSize){
383 if(lMergeSize1>iMergeSize){
384 lMergeSize1=iMergeSize;
386 if(lMergeSize2>iMergeSize){
387 lMergeSize2=iMergeSize;
391 merge_streams<T>(lToBeSorted1,
392 lMergeSize1/
sizeof(T),
394 lMergeSize2/
sizeof(T),
396 inNumberOfPageElements
399 merge_streams<T>(lToBeSorted1,
400 lMergeSize1.operator/(
sizeof(T)),
402 lMergeSize2.operator/(
sizeof(T)),
404 inNumberOfPageElements
410 lToBeSorted1.close();
411 lToBeSorted2.close();
412 swap(lFileToBeSortedName,
414 cout <<
"endmerge" << endl;
416 return strdup(lFileToBeSortedName);