В пособии также рассматриваются анонимные методы и процедурные ссылки.
- generics - дженерики, генерики, параметризованные классы, шаблоны, обобщения;
- generic class – обобщённый класс;
- generic parameter – обобщённый параметр;
- сast – приведение типа;
- anonymous routines - анонимные методы;
- routine references - процедурные ссылки;
- ordinal type – порядковый тип (данных);
- interface type – интерфейсный тип (данных);
- class type – классовый тип;
- comparer – компаратор;
- unit – модуль, юнит;
- Типы данных: string – строка, record – запись;
- Callback – обратный вызов, но я оставил его непереведённым;
- pre-order walk – префиксный обход (дерева);
- instanciate – создание экземпляра объекта;
Теперь, когда мы знаем, как использовать обобщённые классы, пришло время рассмотреть их внутреннее устройство.
Мы разработаем класс
TTreeNode<T>, который станет обобщённой реализацией
дерева. На этот раз, это будет не просто обучение. Мы создадим реальный класс, который Вы сможете использовать в своих реальных проектах.
Давайте же начнем с самого начала: с объявления класса. Как Вы, наверное, помните из объявления
TList<T>, обобщённый параметр (традиционно называемый
Т, когда нет более точного названия) добавляется между угловыми скобками. Вот так:
unit Generics.Trees;
type
TTreeNode<T> = class(TObject)
end;
|
Узел дерева будет помечен значением типа
T, и сможет иметь 0 и более детей. При уничтожении узла, он будет освобождать всех своих детей.
Что за значение типа
T? Это также просто, как и «
FValue: T;», также как и для любого другого нормального типа. Для хранения списка детей, мы будем использовать
TObjectList<U>, объявленный в
Generics.Collections. Я использовал здесь
U, чтобы не запутаться. На деле,
U будет заменено на
TTreeNode<T>! Кстати да, разрешается использовать обобщённый класс, как фактический обобщённый параметр.
 |
Мы не будем реализовывать поиск по дереву. Следовательно, нам не нужно делать компаратор, как мы делали с TList<T>. |
Наш класс будет иметь следующие поля:
type
TTreeNode<T> = class(TObject)
private
FParent: TTreeNode<T>;
FChildren: TObjectList<TTreeNode<T>>;
FValue: T;
end;
|
Странно? Если вдуматься, то не очень. Мы уже говорили ранее, что обобщённый тип, может быть заменён
любым другим типом. Так почему бы не использовать класс обобщённого типа?
 |
Хочу обратить Ваше внимание на тот факт, что в имени TTreeNode<T>, T не является фактическим обобщённым параметром (если хотите, формальным параметр). Но внутри класса, он становится фактическим типом! Оно ведёт себя точно также как и параметры процедуры. При объявлении (примечание переводчика: в оригинале было «In the signature»), у Вас есть формальные параметры, но в теле процедуры, с ними работают, как и с любыми другими локальными переменными. Вот почему, Вы можете использовать T как тип для FValue, или даже как актуальный параметр для параметризации TTreeNode<T>, при объявлении FChildren. |
|
Когда я сказал, чтобы мы можем использовать в качестве фактического параметра любой тип, я был не до конца честен. Это не всегда так. Например, в TObjectList<T>, T всегда должно быть классовым типом. Это объясняется тем, что TObjectList<T> имеет ограничение на свой параметризуемый тип. Позже мы рассматрим его более подробно, но я хочу указать на него уже сейчас, поскольку именно сейчас мы используем TObjectList<T>. А используем мы именно его для того, чтобы извлечь пользу от автоматического освобождения объектов хранящихся в TObjectList<T>, чего не умеет делать TList<T>. |
Помимо конструктора и деструктора, мы предоставим методы для
обхода в глубину (префискного и постфиксного (
примечание переводчика: в оригинале было pre-order и post-order)), а также методы для добавления/перемещения и удаления дочерних узлов. Собственно, добавление будет запрашивать ребёнок, когда ему будет назначен его родитель.
Для обхода, нам понадобится call-back тип. Угадайте какой? Процедурные ссылки. Мы реализуем два способа
(примечание переводчика: в оригинале, использовался термин “overload” - перегрузка. Но мне это режет слух, поэтому я использовал слово «способ», однако в скобках оставил упоминания об оригинальном термине) обхода: обход по узлам, и обход по значению узлов. Второй способ (
overload), вероятно, будет использоваться чаще при использовании класса
TTreeNode<T>. Первый же предусмотрен для полноты и является более общим. Он будет использоваться всего в нескольких методах
TTreeNode<T> (например, во второй
перегрузке (overload)).
Наконец, будет, конечно же, доступ к свойствам родителей, детей и значению. Всё это реализуется в коде, приведённом ниже. Как Вы можете заметить, там нет ничего нового, кроме упоминания
T,
где только можно.
Вот полное объявление класса (которое, можете быть уверены, я даю только после того как полностью реализовал класс^^).
type
/// Процедурная ссылка для Call-back с единственным параметром
TValueCallBack<T> = reference to procedure(const Value: T);
{*
Структура обобщённого дерева
*}
TTreeNode<T> = class(TObject)
private
FParent: TTreeNode<T>; /// Родительский узел. (nil для корневого узла)
FChildren: TObjectList<TTreeNode<T>>; /// Список детей
FValue: T; /// Значение
FDestroying: Boolean; /// Становится True во время уничтожения объекта
procedure DoAncestorChanged;
function GetRootNode: TTreeNode<T>;
function GetChildCount: Integer; inline;
function GetChildren(Index: Integer): TTreeNode<T>; inline;
function GetIndexAsChild: Integer; inline;
function GetIsRoot: Boolean; inline;
function GetIsLeaf: Boolean; inline;
function GetDepth: Integer;
protected
procedure AncestorChanged; virtual;
procedure Destroying; virtual;
procedure AddChild(Index: Integer; Child: TTreeNode<T>); virtual;
procedure RemoveChild(Child: TTreeNode<T>); virtual;
procedure SetValue(const AValue: T); virtual;
property IsDestroying: Boolean read FDestroying;
public
constructor Create(AParent: TTreeNode<T>; const AValue: T); overload;
constructor Create(AParent: TTreeNode<T>); overload;
constructor Create(const AValue: T); overload;
constructor Create; overload;
destructor Destroy; override;
procedure AfterConstruction; override;
procedure BeforeDestruction; override;
procedure MoveTo(NewParent: TTreeNode<T>; Index: Integer = -1); overload;
procedure MoveTo(Index: Integer); overload;
function IndexOf(Child: TTreeNode<T>): Integer; inline;
procedure PreOrderWalk(
const Action: TValueCallBack<TTreeNode<T>>); overload;
procedure PreOrderWalk(const Action: TValueCallBack<T>); overload;
procedure PostOrderWalk(
const Action: TValueCallBack<TTreeNode<T>>); overload;
procedure PostOrderWalk(const Action: TValueCallBack<T>); overload;
property Parent: TTreeNode<T> read FParent;
property RootNode: TTreeNode<T> read GetRootNode;
property ChildCount: Integer read GetChildCount;
property Children[Index: Integer]: TTreeNode<T> read GetChildren;
property IndexAsChild: Integer read GetIndexAsChild;
property IsRoot: Boolean read GetIsRoot;
property IsLeaf: Boolean read GetIsLeaf;
property Value: T read FValue write SetValue;
end;
|
Давайте обозначим, на что здесь стоит обратить внимание. Собственно, не на что, кроме того факта, что каждый параметр типа
T объявляется как
const. На момент написания, мы не знаем, чем станет
T. И соответственно, существует вероятность, что
T будет одним из «тяжёлых» типов (таким как строка или запись), для которых более эффективно использовать именно
const. А так как
const не имеет побочных эффектов (оно просто не даёт эффекта при использовании «лёгких» типов, таких как Integer), мы всегда будем использовать её при работе с обобщёнными типами.
|
Концепцию тяжёлых и лёгких типов я придумал сам. Она неофициальна, поэтому никаких цитат и ссылок. Под тяжёлым типом я подразумеваю, тип, чьи параметры (во время исполнения) лучше передавать как const всегда, когда это только возможно. По большому счёту, это типы, которые занимают больше чем 4 байта (не считая float и Int64), а также типы, которые требуют инициализации. Такие как строки, записи, массивы, интерфейсы (не классы) и Variants. |
Однако, если параметр имеет тип
TTreeNode<T>, мы не будем ставить
Const. Действительно, независимо от того, чем является
Т,
TTreeNode <T> остаётся классовым типом, который является «лёгким».
Чтобы проиллюстрировать особенности реализации обобщённого метода, давайте рассмотрим простой метод
GetRootNode. Он написан следующим образом:
{*
Корневой узел дерева
@возвращает Корневой узел дерева
*}
function TTreeNode<T>.GetRootNode: TTreeNode<T>;
begin
if IsRoot then
Result := Self
else
Result := Parent.RootNode;
end;
|
Единственное на что здесь стоит обратить внимание, состоит в том, что
каждый раз, когда Вы пишете реализацию обобщённого метода, необходимо добавлять
<T> к имени класса. Это обязательное требование, потому что
TTreeNode (без
<T>), по сути является другим типом, который кстати может быть объявлен в том же модуле (юните).
Чтобы реализовать два конструктора, не имеющие параметра
AValue, нам необходимо как-то инициализировать
FValue. Естественно, но ведь нам неизвестен фактический тип значения, как мы можем указать значение по умолчанию, которое подошло бы для любого возможного типа?
Выход в добавлении новой псевдо-процедуры
Default. Как и
TypeInfo, эта псевдо-процедура будет принимать в качестве параметра идентификатор типа. А название обобщенного класса, по сути, и является таким идентификатором.
Это псевдо-процедура будет возвращать значение по умолчанию для указанного типа. Поэтому можно будет писать так:
{*
Создаёт узел с родителем и без значения
@param AParent Parent
*}
constructor TTreeNode<T>.Create(AParent: TTreeNode<T>);
begin
Create(AParent, Default(T));
end;
{*
Создаёт новый узел без родителя и без значения
*}
constructor TTreeNode<T>.Create;
begin
Create(nil, Default(T));
end;
|
|
В случае инициализации объектного поля, это, строго говоря, не является необходимым, посколько при создании экземпляра объекта, все его поля уже оказываются проинициализированными значениями по умолчанию. Но я не мог найти лучшее место для того, чтобы познакомить Вас с этой псевдо-процедурой. |
Чтобы взглянуть на процедурные ссылки с другой стороны, давайте посмотрим реализацию обхода дерева.
Оба способа (overloads) обхода принимают в качестве параметра ссылку на процедуру. Обратите внимание, что и здесь мы использовали
const параметр. Внимательный читатель, наверняка помнит о том, что ссылки на процедуры, по сути, являются интерфейсами. А интерфейсы мы договорились считать «тяжёлым» типом. Поэтому лучше использовать
const, когда это возможно.
Кроме этого примера, о первом способе (там, где обход по узлам) сказать особо нечего:
{*
Префиксный обход (preorder walk) узлов дерева
@param Action Действие выполняемое для каждого узла
*}
procedure TTreeNode<T>.PreOrderWalk(const Action: TValueCallBack<TTreeNode<T>>);
var
Index: Integer;
begin
Action(Self);
for Index := 0 to ChildCount-1 do
Children[Index].PreOrderWalk(Action);
end;
|
Для вызова call-back, мы написали точно такой же код, что и для процедурных типов, т.е. в той же форме, что и вызов процедуры, но используя ссылку на процедуру вместо её имени.
При реализации второго способа (overload), мы воспользуемся первым способом, а в качестве
Action, будем передавать... анонимную процедуру!
{*
Префиксный обход (preorder walk) по значениям узлов дерева
@param Action Действие выполняемое для каждого значения узла
*}
procedure TTreeNode<T>.PreOrderWalk(const Action: TValueCallBack<T>);
begin
PreOrderWalk(
procedure(const Node: TTreeNode<T>)
begin
Action(Node.Value);
end);
end;
|
Разве не чудесный кусок кода у нас получился?
|
Вы можете сказать, что я непоследователен в том, что говорю о const параметрах, так как параметр Node в анонимной процедуре объявлен как const, хотя это явно классовый тип. Причина в том, что необходимо обеспечить совместимость с сигнатурой типа TValueCallBack<TTreeNode<T>>, которая требует именно const параметр ;-). |
Да, ещё в двух.
DoAncestorChanged, который должен сделать префиксный обход для метода
AncestorChanged. И
BeforeDestruction, который должен обойти всех (
do a preorder walk) детей вызвав метод
Destroying.
{*
Вызывает метод AncestorChanged для каждого потомка (префиксно)
*}
procedure TTreeNode<T>.DoAncestorChanged;
begin
PreOrderWalk(
procedure(const Node: TTreeNode<T>)
begin
Node.AncestorChanged;
end);
end;
{*
[@inheritDoc]
*}
procedure TTreeNode<T>.BeforeDestruction;
begin
inherited;
if not IsDestroying then
PreOrderWalk(procedure(const Node: TTreeNode<T>) begin Node.Destroying end);
if (Parent <> nil) and (not Parent.IsDestroying) then
Parent.RemoveChild(Self);
end;
|
В остальном… Это классический пример ;-) Ничего нового. Я не буду распространяться на этот счет, но и полный источник доступен для скачивания, так как все другие,
в конце учебника.
Это, безусловно, приятно написать класс обобщённого дерева, но как его использовать?
После того как мы рассмотрели в деталях использование обобщённых классов на примере класса
TList<T>, добавить в сущности нечего. Я только дам Вам код небольшой тестовой программки.
procedure TestGenericTree;
const
NodeCount = 20;
var
Tree, Node: TTreeNode<Integer>;
I, J, MaxDepth, Depth: Integer;
begin
Tree := TTreeNode<Integer>.Create(0);
try
// Строим дерево
MaxDepth := 0;
for I := 1 to NodeCount do
begin
Depth := Random(MaxDepth+1);
Node := Tree;
for J := 0 to Depth-1 do
begin
if Node.IsLeaf then
Break;
Node := Node.Children[Random(Node.ChildCount)];
end;
if TTreeNode<Integer>.Create(Node, I).Depth > MaxDepth then
Inc(MaxDepth);
end;
// Показать дерево с помощью префиксного обхода
Tree.PreOrderWalk(
procedure(const Node: TTreeNode<Integer>)
begin
Write(StringOfChar(' ', 2*Node.Depth));
Write('- ');
WriteLn(Node.Value);
end);
finally
Tree.Free;
end;
end;
|
Дата перевода: 22 июля 2009 года.
Версия для мобильного
3 человек заметили этот пост: