Motto

В тихом саду здравомыслия
Пусть на вас постоянно падают
кокосовые орехи пробужденности.
Чогьям Трунгпа РИНПОЧЕ


Версия для мобильного


среда, 22 июля 2009 г.

Часть 3. Generics в Delphi 2009 для Win32. Создание обобщённого класса.

В пособии также рассматриваются анонимные методы и процедурные ссылки.


Словарь терминов
  • 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 – создание экземпляра объекта;

III. Создание обобщённого класса

Теперь, когда мы знаем, как использовать обобщённые классы, пришло время рассмотреть их внутреннее устройство.
Мы разработаем класс TTreeNode<T>, который станет обобщённой реализацией дерева. На этот раз, это будет не просто обучение. Мы создадим реальный класс, который Вы сможете использовать в своих реальных проектах.
III-A. Декларация класса
Давайте же начнем с самого начала: с объявления класса. Как Вы, наверное, помните из объявления TList<T>, обобщённый параметр (традиционно называемый Т, когда нет более точного названия) добавляется между угловыми скобками. Вот так:
unit Generics.Trees;
type
  TTreeNode<T> = class(TObject)
  end;
Узел дерева будет помечен значением типа T, и сможет иметь 0 и более детей. При уничтожении узла, он будет освобождать всех своих детей.
Что за значение типа T? Это также просто, как и «FValue: T;», также как и для любого другого нормального типа. Для хранения списка детей, мы будем использовать TObjectList<U>, объявленный в Generics.Collections. Я использовал здесь U, чтобы не запутаться. На деле, U будет заменено на TTreeNode<T>! Кстати да, разрешается использовать обобщённый класс, как фактический обобщённый параметр.
image Мы не будем реализовывать поиск по дереву. Следовательно, нам не нужно делать компаратор, как мы делали с TList<T>.
Наш класс будет иметь следующие поля:
type
  TTreeNode<T> = class(TObject)
  private
    FParent: TTreeNode<T>;
    FChildren: TObjectList<TTreeNode<T>>;
    FValue: T;
  end;
        
Странно? Если вдуматься, то не очень. Мы уже говорили ранее, что обобщённый тип, может быть заменён любым другим типом. Так почему бы не использовать класс обобщённого типа?
image Хочу обратить Ваше внимание на тот факт, что в имени TTreeNode<T>, T не является фактическим обобщённым параметром (если хотите, формальным параметр). Но внутри класса, он становится фактическим типом! Оно ведёт себя точно также как и параметры процедуры. При объявлении (примечание переводчика: в оригинале было «In the signature»), у Вас есть формальные параметры, но в теле процедуры, с ними работают, как и с любыми другими локальными переменными. Вот почему, Вы можете использовать T как тип для FValue, или даже как актуальный параметр для параметризации TTreeNode<T>, при объявлении FChildren.
image Когда я сказал, что мы можем использовать в качестве фактического параметра любой тип, я был не до конца честен. Это не всегда так. Например, в TObjectList<T>, T всегда должно быть классовым типом. Это объясняется тем, что TObjectList<T> имеет ограничение на свой параметризуемый тип. Позже мы рассмотрим его более подробно, но я хочу указать на него уже сейчас, поскольку именно сейчас мы используем TObjectList<T>. А используем мы именно его для того, чтобы извлечь пользу от автоматического освобождения объектов хранящихся в TObjectList<T>, чего не умеет делать TList<T>.
Помимо конструктора и деструктора, мы предоставим методы для обхода в глубину (префиксного и постфиксного (примечание переводчика: в оригинале было pre-order и post-order)), а также методы для добавления/перемещения и удаления дочерних узлов. Собственно, добавление будет запрашивать ребёнок, когда ему будет назначен его родитель.
Для обхода, нам понадобится call-back тип. Угадайте какой? Процедурные ссылки. Мы реализуем два способа (примечание переводчика: в оригинале, использовался термин “overload” - перегрузка. Но мне это режет слух, поэтому я использовал слово «способ», однако в скобках оставил упоминания об оригинальном термине) обхода: обход по узлам, и обход по значению узлов. Второй способ (overload), вероятно, будет использоваться чаще при использовании класса TTreeNode<T>. Первый же предусмотрен для полноты и является более общим. Он будет использоваться всего в нескольких методах TTreeNode<T> (например, во второй перегрузке (overload)).
Наконец, доступ к свойствам Parent, Children и Value. Всё это реализуется в коде, приведённом ниже. Как Вы можете заметить, там нет ничего нового, кроме упоминания 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), мы всегда будем использовать её при работе с обобщёнными типами.
image Концепцию тяжёлых и лёгких типов я придумал сам. Она неофициальна, поэтому никаких цитат и ссылок. Под тяжёлым типом я подразумеваю, тип, чьи параметры (во время исполнения) лучше передавать как const всегда, когда это только возможно. По большому счёту, это типы, которые занимают больше чем 4 байта (не считая float и Int64), а также типы, которые требуют инициализации. Такие как строки, записи, массивы, интерфейсы (не классы) и Variants.
Однако, если параметр имеет тип TTreeNode<T>, мы не будем ставить Const. Действительно, независимо от того, чем является Т, TTreeNode <T> остаётся классовым типом, который является «лёгким».
III-B. Реализация метода
Чтобы проиллюстрировать особенности реализации обобщённого метода, давайте рассмотрим простой метод GetRootNode. Он написан следующим образом:
{*
  Корневой узел дерева
  @возвращает Корневой узел дерева
*}
function TTreeNode<T>.GetRootNode: TTreeNode<T>;
begin
  if IsRoot then
    Result := Self
  else
    Result := Parent.RootNode;
end;
        
Единственное на что здесь стоит обратить внимание, состоит в том, что каждый раз, когда Вы пишете реализацию обобщённого метода, необходимо добавлять <T> к имени класса. Это обязательное требование, потому что TTreeNode (без <T>), по сути является другим типом, который кстати может быть объявлен в том же модуле (юните).
III-C. Псевдо-процедура Default
Чтобы реализовать два конструктора, не имеющие параметра 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;
        
image В случае инициализации объектного поля, это, строго говоря, не является необходимым, посколько при создании экземпляра объекта, все его поля уже оказываются проинициализированными значениями по умолчанию. Но я не мог найти лучшее место для того, чтобы познакомить Вас с этой псевдо-процедурой.
III-D. Процедурные ссылки и обход дерева
Чтобы взглянуть на процедурные ссылки с другой стороны, давайте посмотрим реализацию обхода дерева.
Оба способа (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;
        
Разве не чудесный кусок кода у нас получился?
image Вы можете сказать, что я непоследователен в том, что говорю о const параметрах, так как параметр Node в анонимной процедуре объявлен как const, хотя это явно классовый тип. Причина в том, что необходимо обеспечить совместимость с сигнатурой типа TValueCallBack<TTreeNode<T>>, которая требует именно const параметр ;-).
III-D-1. А анонимные процедуры используются в других методах?
Да, ещё в двух. 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;
        
III-E. И остальное
В остальном… Это классический пример ;-) Ничего нового. Я не буду распространяться на этот счет, но и полный источник доступен для скачивания, так как все другие, в конце учебника.
III-F. Как использовать TTreeNode<T> ?
Это, безусловно, приятно написать класс обобщённого дерева, но как его использовать?
После того как мы рассмотрели в деталях использование обобщённых классов на примере класса 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 комментария:

  1. Спасибо за продолжение полезного дела. Нормальное письмо пока времени нет написать.

    Продолжим терминологические вопросы.
    Дети это все потомки узла или нет? У Вас сначала вроде это не так, а потом (при обходе) именно так.

    Стандартная терминология.
    Пусть дерево изображено стандартно - корень сверху.
    Тогда неформально:
    Предок (ancestor) - любой узел выше по ветви.
    Потомок (descendant) - любой узел ниже по ветви.
    Родительский узел (parent) - узел на предыдущем уровне в ветви.
    Дочерний узел (child) - любой узел на следующем уровне ветви.

    ОтветитьУдалить
  2. За этот комментарий особенное спасибо. Когда переводил не задумывался о том, что дети и потомки могут быть разными понятиями. =)
    В оригинале везде использовалось Child.

    ОтветитьУдалить
  3. по хорошему, более притянутого за уши механизма еще не было. Даже короткого взгляда внутрь Generics.Defaults хватает, чтобы понять, насколько это криво реализовано.

    ОтветитьУдалить

Постоянные читатели