Применяем дженерики в RAD Studio Delphi. Создаем библиотеку сортировки списков однотипных объектов

    Сегодня будем создавать в 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

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

    Comments 4

      +1
      Стоит добавить, что дженерики это независимая от классов и объектов вещь, например, итератор на типах Record, в Lazarus последние два сообщения в треде:
      http://delphikingdom.ru/asp/answer.asp?IDAnswer=83335
        0
        Спасибо, это важно
        0
        Простите, но не совсем понятна цель, и выхлоп, получившийся в конце статьи.
        Количество алгоритмов сортировки — 100;
        Эм… огласите весь список пожалуйста. Я столько разных алгоритмов то и не слышал. Может штук 15 наскребу, от силы. Очень интересно посмотреть хотя бы на список.
        прикладному разработчику сортировать любой из 100 объектов любым из 100 методов сортировки;
        Зачем программисту таааак много методов сортировки? Я не понимаю, объясните.

        Ну и выхлоп в конце статьи ооочень скудный. Это 2 метода сортировки. Один из них — QuickSort, скопированный из TArray.QuickSort, а второй — сортировка пузырьком, которая даже хуже, чем классическая реализация. Ведь у вас:
          for i := 0 to N - 1 do
            for j := 1 to N - 1 do
        

        А в классической реализации обычно:
          for i := 0 to N - 1 do
            for j := 1 to N - i - 1 do
        

        Нет бы реализовать полезный алгоритм, типа HeapSort. Заодно можно было бы сделать контейнер «бинарная куча», но реализован только пузырек, который даже хуже чем пузырек…

        Мое мнение — вам надо либо цель менять на: «Обучится пользоваться дженериками на примерах», либо результат. Но я не представляю как реализовать 100 различных алгоритмов сортировки.
          0
          Эм… огласите весь список пожалуйста. Я столько разных алгоритмов то и не слышал. Может штук 15 наскребу, от силы. Очень интересно посмотреть хотя бы на список.

          Когда человечество придумает 100 методов сортировки, у нас уже будет готовый класс для работы с ними =)

          Нет бы реализовать полезный алгоритм, типа HeapSort.

          Готово.
          В исходниках лежит приложение, которое умеет сортировать пирамидально.


          Only users with full accounts can post comments. Log in, please.