Когда проект практически завершен и вся бизнес логика находится в тестировании иногда возникает желание дополнить его «рюшечками и фишечками» и прочими «украшательствами», ну например перерисовать пару иконок на более красивые, или сделать выделение элементов через градиент с альфаканалом.
Вариантов таких спонтанных хотелок (особенно при наличии времени) много и все из серии украшательств, не несущих по сути никакой смысловой нагрузки — но вот хочется и все :)
В данной мини-статье я рассмотрю одну из таких «хотелок».
Допустим у вас есть список элементов, отображаемый в TListView, вы пробуете его отсортировать и получаете вот такой результат.
Не красиво, почему это второй элемент с именем «101» находится не на своем месте? Ведь это число, а стало быть место ему как минимум после элемента с именем «2». Да и «New Folder (101)» явно должна быть после «New Folder (2)». Ведь в проводнике все выглядит нормально.
Попробуем разобраться в причинах такого поведения и реализовать алгоритм более правильной, с точки зрения человека, сортировки.
Для начала давайте разберемся в причинах неверной сортировки.
По умолчанию в TListView для сравнения строк используется функция lstrcmp, которая сравнивает строки посимвольно.
К примеру если взять две строки «1» и «2», то первая строка должна располагаться над второй, т.к. символ единицы идет перед двойкой. Однако если вместо первой строки взять «101», функция lstrcmp так-же скажет что данная строка должна идти первой, ибо в этом случае она принимает решение по результату сравнения самого первого символа обеих строк, не учитывая тот факт что обе строки являются строковым представлением чисел.
Немножко усложним, возьмем строки «1a2» и «1a101» на которых lstrcmp опять выдаст неверный результат, сказав что вторая строка должна идти первой. Это решение она принимает на основе результата сравнения третьего символа обеих строк, не смотря на то что в данном случае они так-же являются строковыми представлениями чисел.
С причинами разобрались, теперь думаем решение.
Раз lstrcmp ошибается на сравнении, интерпретируя части чисел в виде символов, нужно реализовать аналогичный ей алгоритм сравнения, в котором числа будут сравниваться именно как числа, а не как символы.
Алгоритмически это сделать достаточно просто.
Возьмем опять-же «1a2» и «1a101». Разобьем их на отдельные составляющие, где символы будут отделены от чисел. Если представить первую строку в виде «1 + a + 2», а вторую в виде «1 + a + 101» то получится что нам нужно выполнить всего три сравнения.
1. Число с числом
2. Символ с символом
3. Опять число с числом
Итог такого сравнения будет верный и покажет что вторая строка действительно должна идти второй, а не первой, как нам об этом сообщала lstrcmp.
Теперь продумаем ТЗ к реализации данного алгоритма.
Очевидно что:
1. Если одна из строк, переданная для сравнения пустая — она должна идти выше первой.
2. Если обе строки пустые — они идентичны.
3. Регистр строк при сравнении не учитывается.
4. Для анализа строк используем курсор содержащий адрес текущего анализируемого символа каждой строки.
5. Если курсор одной из строк содержит число, а курсор другой строки содержит символ — первая строка выше второй.
6. Если курсоры строк указывают на символ — сравнение происходит по аналогу lstrcmp
7. Если курсоры строк указывают на число — извлекаем оба числа и сравниваем их между собой.
7.1 Если оба числа равны нулю (к примеру «00» и «0000») то вверх помещается число с меньшим количеством нулей.
8. Если в процессе анализа курсор любой из строк обнаружил терминирующий ноль — эта строка идет выше.
8.1 Если в этот-же момент курсор второй строки тоже находится на терминирующем нуле — строки идентичны.
Для реализации алгоритма, данного ТЗ более чем достаточно.
Собственно реализуем:
//
// CompareStringOrdinal сравнивает две строки по аналогу проводника, т.е.
// "Новая папка (3)" < "Новая папка (103)"
//
// Возвращает следующие значения
// -1 - первая строка меньше второй
// 0 - строки эквивалентны
// 1 - первая строка больше второй
// =============================================================================
function CompareStringOrdinal(const S1, S2: string): Integer;
// Функция CharInSet появилась начиная с Delphi 2009,
// для более старых версий реализуем ее аналог
function CharInSet(AChar: Char; ASet: TSysCharSet): Boolean;
begin
Result := AChar in ASet;
end;
var
S1IsInt, S2IsInt: Boolean;
S1Cursor, S2Cursor: PChar;
S1Int, S2Int, Counter, S1IntCount, S2IntCount: Integer;
SingleByte: Byte;
begin
// Проверка на пустые строки
if S1 = '' then
if S2 = '' then
begin
Result := 0;
Exit;
end
else
begin
Result := -1;
Exit;
end;
if S2 = '' then
begin
Result := 1;
Exit;
end;
S1Cursor := @AnsiLowerCase(S1)[1];
S2Cursor := @AnsiLowerCase(S2)[1];
while True do
begin
// проверка на конец первой строки
if S1Cursor^ = #0 then
if S2Cursor^ = #0 then
begin
Result := 0;
Exit;
end
else
begin
Result := -1;
Exit;
end;
// проверка на конец второй строки
if S2Cursor^ = #0 then
begin
Result := 1;
Exit;
end;
// проверка на начало числа в обоих строках
S1IsInt := CharInSet(S1Cursor^, ['0'..'9']);
S2IsInt := CharInSet(S2Cursor^, ['0'..'9']);
if S1IsInt and not S2IsInt then
begin
Result := -1;
Exit;
end;
if not S1IsInt and S2IsInt then
begin
Result := 1;
Exit;
end;
// посимвольное сравнение
if not (S1IsInt and S2IsInt) then
begin
if S1Cursor^ = S2Cursor^ then
begin
Inc(S1Cursor);
Inc(S2Cursor);
Continue;
end;
if S1Cursor^ < S2Cursor^ then
begin
Result := -1;
Exit;
end
else
begin
Result := 1;
Exit;
end;
end;
// вытаскиваем числа из обоих строк и сравниваем
S1Int := 0;
Counter := 1;
S1IntCount := 0;
repeat
Inc(S1IntCount);
SingleByte := Byte(S1Cursor^) - Byte('0');
S1Int := S1Int * Counter + SingleByte;
Inc(S1Cursor);
Counter := 10;
until not CharInSet(S1Cursor^, ['0'..'9']);
S2Int := 0;
Counter := 1;
S2IntCount := 0;
repeat
SingleByte := Byte(S2Cursor^) - Byte('0');
Inc(S2IntCount);
S2Int := S2Int * Counter + SingleByte;
Inc(S2Cursor);
Counter := 10;
until not CharInSet(S2Cursor^, ['0'..'9']);
if S1Int = S2Int then
begin
if S1Int = 0 then
begin
if S1IntCount < S2IntCount then
begin
Result := -1;
Exit;
end;
if S1IntCount > S2IntCount then
begin
Result := 1;
Exit;
end;
end;
Continue;
end;
if S1Int < S2Int then
begin
Result := -1;
Exit;
end
else
begin
Result := 1;
Exit;
end;
end;
end;
Смотрим результат работы данного алгоритма.
Собственно что и ожидалось.
Очередная «украшалка» готова :)
Можно конечно сказать что это велосипед и нужно использовать StrCmpLogicalW:
msdn.microsoft.com/en-us/library/windows/desktop/bb759947
Чтож, попробуйте — третья кнопка отвечает за такую сортировку.
Обратите внимание на первые пять элементов списка после сортировки.
Хоть они и похожи на то, что отобразит проводник, но не совсем верны. Ну не должен элемент с именем «0» располагаться под элементом «00» и прочими :)
Исходный код демо-примера можно забрать по данной ссылке.
© Александр (Rouse_) Багель
Июнь, 2013
Автор: Rouse
