main.cpp

目前最快速的字符串排序算法

/* Copyright 2007 Stefan Webb

This file is part of Burstsort.

Burstsort is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

Burstsort is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with Burstsort; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA */

#include "main.h"

unsigned int nextline(wchar_t*, unsigned int);
unsigned int whatnewline(wchar_t*, int);

int _tmain(int argc, _TCHAR* argv[])
{
	// Open our test file to be sorted
	// may need to change the path of the file
	Textfile test(L"dictwords.txt");
	wchar_t* text = test.gettext();
	// Count how many lines in the file
	unsigned int linecount = 0;
	for (unsigned int i = 0;;) {
		linecount++;
		if (!text[i = nextline(text, i)]) break;
	}
	// Convert the text file into strings and insert into the bursttrie
	Burstsort bs;
	//wchar_t** strings = (wchar_t**) malloc (sizeof(wchar_t*) * linecount);
	int beforenextline = 0, linelen = 0;
	for (unsigned int i = 0, j = 0; j < linecount; j++) {
		beforenextline = i;
		i = nextline(text, i);
		linelen = i - beforenextline - whatnewline(text, i);
		wchar_t* string = (wchar_t*) malloc((linelen + 1) * sizeof(wchar_t));
		wcsncpy(string, &text[beforenextline], linelen);
		string[linelen] = 0;
		bs.insert(string);
		free(string);
	}
	// Print the bursttrie
	bs.sort();
	bs.print();



	//Burstsort bs;
	//bs.debug();
	//bs.print();
	return 0;
}

unsigned int nextline(wchar_t* text, unsigned int i) {
	while(text[i]!=0x0d && text[i]!=0x0a && text[i]!=0)
		i++;
	if ((text[i]==0x0d && text[i+1]==0x0a) || (text[i+1]==0x0d && text[i]==0x0a))
		i++;
	if (text[i])
		i++;
	return i;
}

unsigned int whatnewline(wchar_t* f, int i) {
	if (i > 1) {
		if (((f[i-1] == 0x0d) && (f[i-2] == 0x0a)) || ((f[i-2] == 0x0d) && (f[i-1] == 0x0a)))
			return 2;
	}
	if (i > 0) {
		if (f[i-1] == 0x0d || f[i-1] == 0x0a)
			return 1;
	}
	return 0;
}