Сортировка списка по аналогу "Проводника Windows"

Когда проект практически завершен и вся бизнес логика находится в тестировании иногда возникает желание дополнить его "рюшечками и фишечками" и прочими "украшательствами", ну например перерисовать пару иконок на более красивые, или сделать выделение элементов через градиент с альфаканалом.
Вариантов таких спонтанных хотелок (особенно при наличии времени) много и все из серии украшательств, не несущих по сути никакой смысловой нагрузки - но вот хочется и все :)

В данной мини-статье я рассмотрю одну из таких "хотелок".

Допустим у вас есть список элементов, отображаемый в 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:
http://msdn.microsoft.com/en-us/library/windows/desktop/bb759947

Чтож, попробуйте - третья кнопка отвечает за такую сортировку.
Обратите внимание на первые пять элементов списка после сортировки.

Хоть они и похожи на то, что отобразит проводник, но не совсем верны. Ну не должен элемент с именем "0" располагаться под элементом "00" и прочими :)

Исходный код демо-примера можно забрать по данной ссылке.

---

© Александр (Rouse_) Багель

Июнь, 2013