Russian Qt Forum

file111
file21
file3-11
file3-2

file3-2
file3-11
file21
file111

/*
**
** 2008 September 5, author Sergeich ( 2sergeich [---at---]gmail[---dot---]com )
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************/

namespace japanese_sort 
{
	int compare( const QString& str1, const QString& str2 );
	bool less( const QString& str1, const QString& str2 );
};

/*!
	Сравнение двух строк методом "японской сортировки" (http://acm.timus.ru/problem.aspx?space=1&num=1546):
	Входящие в строку цифры сравниваются как числа, а не как строки. Например при сортировке с помощью обычного 
	сравнения строк получим последовательность:
	\code
		file111
		file21
		file3-11
		file3-2
	\endcode
	а при "японской":
	\code
		file3-2
		file3-11
		file21
		file111
	\endcode

	Если первая строка меньше второй возвращается -1, если больше возвращается 1, если строки равны - 0.
	Сравнение нечувствительно к регистру.
*/
inline int japanese_sort::compare( const QString& str1, const QString& str2 )
{	
	register const QChar* c1 = str1.constData();
	register const QChar* c2 = str2.constData();
	forever 
	{
		QChar cc1 = c1->toLower();
		QChar cc2 = c2->toLower();
		// Проверка конца строки
		if ( cc1.isNull() )
			if ( cc2.isNull() )
				return 0;
			else 
				return -1;
		else if( cc2.isNull() )
			return 1;

		// Сравнение чисел
		if ( cc1.isDigit() && cc2.isDigit() ) 
		{
			// Запоминаем начало чисел
			const QChar* beg1 = c1;
			const QChar* beg2 = c2;

			// Определяем длину чисел
			int n1 = 1;
			int n2 = 1;
			while( !(++c1)->isNull() && c1->isDigit() )
				++n1;
			while( !(++c2)->isNull() && c2->isDigit() )
				++n2;
			int n = qMax(n1, n2);

			// Устанавливаем значение цифр в ноль
			cc1 = '0';
			cc2 = '0';
			int d1 = n1 - n;
			int d2 = n2 - n;
			for (int i=0; i < n; i++ )
			{
				// Сравниваем цифры
				if ( i + d1 >= 0 )
					cc1 = *(beg1++);
				if ( i + d2 >= 0 )
					cc2 = *(beg2++);
				if (cc1 > cc2 )
					return 1;
				if (cc1 < cc2 )
					return -1;
			}
		}
		// Обычное сравнение
		else 
		{
			if (cc1 > cc2 )
				return 1;
			if (cc1 < cc2 )
				return -1;
			++c1;
			++c2;
		}
	} // forever
}

inline bool japanese_sort::less( const QString& str1, const QString& str2 )
{
	return compare(str1, str2) == -1;
}