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

в 12:39, , рубрики: Delphi, Алгоритмы, украшательства, метки:

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

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

Допустим у вас есть список элементов, отображаемый в TListView, вы пробуете его отсортировать и получаете вот такой результат.

image

Не красиво, почему это второй элемент с именем «101» находится не на своем месте? Ведь это число, а стало быть место ему как минимум после элемента с именем «2». Да и «New Folder (101)» явно должна быть после «New Folder (2)». Ведь в проводнике все выглядит нормально.

image

Попробуем разобраться в причинах такого поведения и реализовать алгоритм более правильной, с точки зрения человека, сортировки.

Для начала давайте разберемся в причинах неверной сортировки.
По умолчанию в 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;

Смотрим результат работы данного алгоритма.

image

Собственно что и ожидалось.
Очередная «украшалка» готова :)

Можно конечно сказать что это велосипед и нужно использовать StrCmpLogicalW:
msdn.microsoft.com/en-us/library/windows/desktop/bb759947

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

image

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

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

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

Автор: Rouse

Источник

Поделиться

* - обязательные к заполнению поля