Сегодня будем создавать в RAD Studio Delphi библиотеку классов, реализующих сортировку списков однотипных объектов.
Цель задачи
Прикладной разработчик должен получить инструмент для создания дочерних классов, в которых можно:
- оперировать с объектами списка;
- применять различные правила сравнения объектов;
- применять различные алгоритмы сортировки объектов.
На выходе должна получиться библиотека классов, которая позволяет:
- прикладному разработчику сортировать любой из 4000 объектов любым из 100 методов сортировки;
- дорабатывать и поддерживать новые алгоритмы или новые типы объектов в течении одного дня силами одного специалиста.
При создании необходимо учесть, что решение должно удовлетворять следующей модели:
- Количество алгоритмов сортировки — 100;
- Типы объектов доступных для сортировки — 10;
- Количество разработчиков, одновременно работающих с библиотекой, для создания типов объектов и алгоритмов сортировки — 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
Спасибо за внимание!
ссылка на оригинал статьи https://habrahabr.ru/post/314780/
Добавить комментарий