Сегодня будем создавать в RAD Studio Delphi библиотеку классов, реализующих сортировку списков однотипных объектов.

Цель задачи

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

• оперировать с объектами списка;
• применять различные правила сравнения объектов;
• применять различные алгоритмы сортировки объектов.

На выходе должна получиться библиотека классов, которая позволяет:

• прикладному разработчику сортировать любой из 100 объектов любым из 100 методов сортировки;
• дорабатывать и поддерживать новые алгоритмы или новые типы объектов в течении одного дня силами одного специалиста.

При создании необходимо учесть, что решение должно удовлетворять следующей модели:

• Количество алгоритмов сортировки — 100;
• Типы объектов доступных для сортировки — 100;
• Количество разработчиков, одновременно работающих с библиотекой, для создания типов объектов и алгоритмов сортировки — 100.
• Время разработки всех алгоритмов сортировки и типов объектов — 2 дня.

Приступаем

Сортировка по возрастанию — это перестановка элементов набора данных таким образом, чтобы в результате каждый последующий элемент набора был больше предыдущего. Сортировка по убыванию — то же самое, только обход результирующего набора данных нужно начинать с конца.

Сравнение объектов

Чтобы понять, какой элемент набора данных больше другого, для базовых типов необходимо применять оператор сравнения. А как быть с объектами? Базовый модуль System.Generics.Defaults включает в себя нужный нам интерфейс и реализацию класса

  IComparer<T> = interface
    function Compare(const Left, Right: T): Integer;
  end;

  TComparer<T> = class(TInterfacedObject, IComparer<T>)
  public
    class function Default: IComparer<T>;
    class function Construct(const Comparison: TComparison<T>): IComparer<T>;
    function Compare(const Left, Right: T): Integer; virtual; abstract;
  end;

В интерфейсе видим единственный метод Compare вида

TComparison<T> = reference to function(const Left, Right: T): Integer;

На входе два параметра типа объект, а на выходе целое число (0 — объекты равны, -1 — первый меньше второго, 1 — первый больше второго).

Для сравнения наших объектов будем использовать свои функции сравнения, которые описывают логику правил сравнения для каждого типа объектов. Заключим такие функции в отдельный класс TAllComparison. В нем и описываются все наши функции сравнения, они имеют тот же вид

  TComparison<T> = reference to function(const Left, Right: T): Integer;

А класс TComparer(T) как раз служит для сравнения двух объектов путем вызова метода Compare.
Можно использовать сравнение по умолчанию (Default), или создать свой метод сравнения Construct, чем мы и займемся.

Для удобства описание всех объектов будем хранить в отдельном модуле AllObjects. Здесь же будем хранить описание всех 100 созданных нами объектов.

Операции с объектами

Для осуществления операций с объектами списка в Delphi уже имеется нужный нам параметризированный класс, он же дженерик, с нужными нам методами

  TList<T> = class(TEnumerable<T>)

Вообще, универсальные параметризированные типы (дженерики) появились еще в Delphi 2009, но для нашего примера я использую RAD Studio Berlin 10.1 UPD1. Если у вас что-то не компилируется, нужно будет допилить пример для своей версии Delphi.

Пишем основной класс нашей библиотеки наследник TList(T)

// Основной класс для работы со списком однотипных объектов
type
  TAppliedObjectList<T> = class(TList<T>)
  private type
    TSorting<T> = reference to function(var Values: array of T;
      const Comparer: IComparer<T>; Index, Count: Integer): Integer;

  var
    FCS: TCriticalSection; // операции с переносом элементов списка делаем потоконезависимыми
    FComparer: IComparer<T>; // хранится выбранный метод сравнения объектов списка
    Target: Array of T; // временный массив элементов, который передается в метод сортировки
    // создан, потому что массив элементов в родительском классе <i>Private</i>

  public
    constructor Create; overload;
    constructor Create(const AComparer: IComparer<T>); overload;
    destructor Destroy; override;

    // здесь будем размещать дополнительные публичные методы для оперирования над объектами

    // универсальный метод сортировки с указанием нужного метода
    // возвращает количество перестановок, надеюсь, что их будет меньше <i>MaxInt</i>
    function SortBy<T>(const AProc: TSorting<T>): Integer; overload;
  end;

Основной метод нашей задачи SortBy, опишем его использование далее.

Сортировка объектов

Пишем класс TAllSort, который содержит описание всех 100 методов сортировки вида:

TSorting<T> = reference to function(var Values: array of T; const Comparer: IComparer<T>;
    Index, Count: Integer): Integer;

На входе метод получает массив данных из списка, метод сравнения объектов, начальную позицию для сортировки, количество элементов в наборе. На выходе получаем количество произведенных в наборе данных перестановок.

type
  // Методы сортировки должны быть вида TSorting<T>
  TSorting<T> = reference to function(var Values: array of T; const Comparer: IComparer<T>;
    Index, Count: Integer): Integer;

  // Основной класс, содержит все 100 методов сортировки
  TAllSort = class
  public
    // *** Сортировка пузырьковым методом
    class function BubbleSort<T>(var Values: array of T; const Comparer: IComparer<T>;
      Index, Count: Integer): Integer;

    // *** Быстрая сортировка
    class function QuickSort<T>(var Values: array of T; const Comparer: IComparer<T>;
      Index, Count: Integer): Integer;
  end;

Для удобства, все методы сортировки будем держать в отдельном модуле SortMethods.

Демонстрация

В качестве демонстрации решения представляю 2 механизма сортировки: «Быстрая» и «Пузырьком». Сортировать будем 2 типа объектов: список двумерных векторов (упорядоченные пары) типа Integer и список со строками.

Для начала отсортируем массив строк «пузырьками»:

procedure TfmMainTest.Button4Click(Sender: TObject);
var
  // объявляем переменную типа TAppliedObjectList<String>
  // указываем, что список будет хранить объекты типа строка
  MyClass: TAppliedObjectList<String>;
  i: Integer;
begin
  Memo1.Clear;
  try
    // создаем экземпляр нашего класса,
    // в качестве метода сравнения будем использовать стандартный сравниватель для строк
    // типа IComparer<T>
    MyClass := TAppliedObjectList<String>.Create(TComparer<String>.Default);

    try
      Memo1.Lines.Text := 'Мой друг художник и поэт в дождливый вечер на стекле'
        + sLineBreak + 'Мою любовь нарисовал, открыв мне чудо на земле.' +
        sLineBreak + 'Сидел я молча у окна и наслаждался тишиной' + sLineBreak +
        'Моя любовь с тех пор всегда была со мной.' + sLineBreak +
        'И время как вода текло и было мне всегда тепло,' + sLineBreak +
        'Когда в дождливый вечер я смотрел в оконное стекло.' + sLineBreak +
        'Но год за годом я встречал в глазах любви моей печаль,' + sLineBreak +
        'Дождливой скуки тусклый след и вот, любовь сменила цвет.' + sLineBreak
        + 'Моя любовь сменила цвет, угас чудесный яркий день' + sLineBreak +
        'Мою любовь ночная укрывает тень.' + sLineBreak +
        'Веселых красок болтовня, игра волшебного огня' + sLineBreak +
        'Моя любовь уже не радует меня.';

      // заполняем список строками из Memo
      for i := 0 to Memo1.Lines.Count - 1 do
      begin
        MyClass.Add(Memo1.Lines[i]);
      end;

      // вызываем метод сортировки "пузырьками"
      i := MyClass.SortBy<String>(TAllSort.BubbleSort<String>);

      // выводим количество перестановок
      Memo1.Lines.Add(sLineBreak + 'Turns: ' + i.ToString);

      // выводим полученный список
      Memo1.Lines.Add('Полученный список:');
      for i := 0 to MyClass.Count - 1 do
      begin
        Memo1.Lines.Add(MyClass.Items[i]);
      end;
    finally
      // не забываем удалить экземпляр, когда закончили с ним работать
      MyClass.Free;
    end;
  except
    on E: Exception do
      Memo1.Lines.Add(E.Message);
  end;
end;

Получили результат:



А теперь «быстро» отсортируем массив двумерных векторов:

procedure TfmMainTest.Button3Click(Sender: TObject);
var
  // объявляем переменную типа TAppliedObjectList<TVector2D>
  // указываем, что список будет хранить объекты типа TVector2D
  MyClass: TAppliedObjectList<TVector2D>;
  // вспомогательная переменная типа TVector2D
  v: TVector2D;
  i: Integer;
begin
  Memo1.Clear;
  try
    // создаем экземпляр нашего класса списка,
    // в качестве метода сравнения будем использовать
    // метод TAllComparison.Compare_TVector2D
    MyClass := TAppliedObjectList<TVector2D>.Create
      (TComparer<TVector2D>.Construct(TAllComparison.Compare_TVector2D));

    try
      // заполняем список объектами типа 2D вектор
      Memo1.Lines.Add('Исходный список:');
      v.Create(10, 21);
      MyClass.Add(v);
      Memo1.Lines.Add(v.ToString);

      v.Create(-10, 20);
      MyClass.Add(v);
      Memo1.Lines.Add(v.ToString);

      v.Create(-10, -2);
      MyClass.Add(v);
      Memo1.Lines.Add(v.ToString);

      v.Create(-1, 7);
      MyClass.Add(v);
      Memo1.Lines.Add(v.ToString);

      // вызываем метод "бычстрой" сортировки
      i := MyClass.SortBy<TVector2D>(TAllSort.QuickSort<TVector2D>);

      // выводим количество перестановок
      Memo1.Lines.Add(sLineBreak + 'Turns: ' + i.ToString);

      // выводим полученный список
      Memo1.Lines.Add('Полученный список:');
      for i := 0 to MyClass.Count - 1 do
      begin
        Memo1.Lines.Add(MyClass.Items[i].ToString);
      end;

    finally
      // не забываем удалить экземпляр, когда закончили с ним работать
      if Assigned(MyClass) then
        MyClass.Free;
    end;
  except
    on E: Exception do
      Memo1.Lines.Add(E.Message);
  end;
end;

Вот такой результат получился с векторами:

Исходные коды

» Пример исходных кодов Delphi для работы с классом TAppliedObjectList

Спасибо за внимание!