Застосовуємо дженерики в RAD Studio Delphi. Створюємо бібліотеку сортування списків однотипних об'єктів

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

Мета завдання

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

  • оперувати з об'єктами списку;
  • застосовувати різні правила порівняння об'єктів;
  • застосовувати різні алгоритми сортування об'єктів.
На виході повинна вийти бібліотека класів, яка дозволяє:

  • прикладного розробнику сортувати будь 100 об'єктів будь-яким з 100 методів сортування;
  • допрацьовувати і підтримувати нові алгоритми або нові типи об'єктів протягом одного дня силами одного фахівця.

При створенні необхідно врахувати, що рішення повинно відповідати наступній моделі:

  • Кількість алгоритмів сортування — 100;
  • Типи об'єктів доступних для сортування — 100;
  • Кількість розробників, що одночасно працюють з бібліотекою, для створення типів об'єктів і алгоритмів сортування — 100.
  • Час розробки всіх алгоритмів сортування і типів об'єктів — 2 дні.

Приступаємо

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

Порівняння об'єктів
Щоб зрозуміти, який елемент набору даних більше іншого, для базових типів необхідно застосовувати оператор порівняння. А як бути з об'єктами? Базовий модуль System.Узагальнення.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

Дякую за увагу!
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.