如何在没有冗余列表的情况下迭代 parent/child 层次结构中的对象？

Question

我有一个类似这样的对象...

type
  TMyObject = class(TObject)
  private
    FParent: TMyObject;
    FChildren: TObjectList<TMyObject>;
    function GetChildren(const Index: Integer): TMyObject;
  public
    constructor Create(AParent: TMyObject);
    destructor Destroy; override;
    function AddChild: TMyObject;
    procedure DeleteChild(const Index: Integer);
    function ChildCount: Integer;
    property Children[const Index: Integer]: TMyObject read GetChildren; default;
  end;

（还有很多，但这是基本思想）

这允许对象之间存在简单的 parent/child 关系，即层次结构。一个是根，包含了一层层级的more。

这一切都很好，除了我还需要迭代所有这些对象的完整列表，而不考虑层次结构。

var
  Node: TMyObject;
for X := 0 to AllNodes.Count-1 do begin
  Node := AllNodes[X];
  //Do something with `Node`... 

end;

当然，我可以只创建一个对象列表并同时维护它们...

FAllObjects: TObjectList<TMyObject>;

然而，这是多余的。 TMyObject 的每个实例都必须同时对每个结构 added/deleted。我想摆脱对一个主列表的要求，而只使用层次结构对象。但我不知道如何在不遵循递归层次结构的情况下迭代所有对象。例如，像获取所有这些项目的总数这样简单的事情。

如何维护这样的对象层次结构（我可以在一个循环中迭代所有项目）而不必维护两个单独的冗余结构？

例如，TTreeView.Items 具有我想要的行为。您可以使用 Items.Count 和 Items[Index] 来迭代所有项，或者您可以递归地迭代树层次结构。

Answer 1

在标准 TTreeView 中，以 "linear" 方式从上到下遍历其所有节点的最佳方法是在 while循环，例如：

var
  Node: TTreeNode;

Node := TreeView.GetFirstNode;
while Node <> nil do
begin
  //Do something with Node... 
  Node := Node.GetNext;
end;

在您的自定义节点列表中，您可以通过实现一个可与 for..in 循环一起使用的枚举器来实现类似的迭代，该循环是在 Delphi 2007 年引入的。有关更多信息，请参阅 Embarcadero 的文档详情：

Declarations and Statements (Delphi): Iteration Over Containers Using For statements

例如：

type
  TMyObject = class(TObject)
  private
    FParent: TMyObject;
    FChildren: TObjectList<TMyObject>;
  public
    constructor Create(AParent: TMyObject);
    destructor Destroy; override;
    function PreviousSibling: TMyObject;
    function NextSibling: TMyObject;
    function FirstChild: TMyObject;
    property Parent: TMyObject read FParent;
  end;

function TMyObject.PreviousSibling: TMyObject;
var
  Index: Integer;
begin
  Result := nil;
  if FParent <> nil then
  begin
    Index := FParent.FChildren.IndexOf(Self);
    if Index > 0 then
      Result := FParent.FChildren[Index-1];
  end;
end;

function TMyObject.NextSibling: TMyObject;
var
  Index: Integer;
begin
  Result := nil;
  if FParent <> nil then
  begin
    Index := FParent.FChildren.IndexOf(Self);
    if (Index >= 0) and (Index < (FParent.FChildren.Count-1)) then
      Result := FParent.FChildren[Index+1];
  end;
end;

function TMyObject.FirstChild: TMyObject;
begin
  if FChildren.Count > 0 then
    Result := FChildren.First
  else
    Result := nil;
end;

type
  TMyListEnumerator = class
  private
    FList: TMyList;
    FCurrent: TMyObject;
  public
    constructor Create(AList : TMyList);
    function MoveNext: Boolean;
    property Current: TMyObject read FCurrent;
  end;

  TMyList = class
  private
    FRoot: TMyObject;
  public
    function GetEnumerator: TMyListEnumerator;
  end; 

constructor TMyListEnumerator.Create(AList: TMyList);
begin
  inherited Create;
  FList := AList;
  FCurrent := nil;
end;

function TMyListEnumerator.MoveNext: Boolean;
var
  LObject, LParent: TMyObject;
begin
  if FCurrent = nil then begin
    FCurrent := FList.FRoot;
  end else
  begin
    LObject := FCurrent.FirstChild;
    if LObject = nil then
      LObject := FCurrent.NextSibling;
    LParent := FCurrent;
    while (LObject = nil) and (LParent <> nil) do
    begin
      LParent := LParent.Parent;
      LObject := LParent.NextSibling;
    end;
    FCurrent := LObject;
  end;
  Result := FCurrent <> nil;
end;

function TMyList.GetEnumerator: TMyListEnumerator;
begin
  Result := TMyListEnumerator.Create(Self);
end;

var
  MyList: TMyList;
  Node: TMyObject;

// populate MyList as needed...

for Node in MyList do
begin
  //Do something with Node... 
end;

在后台，编译器会生成类似下面的代码：

var
  MyList: TMyList;
  Node: TMyObject;
  Enum: TMyListEnumerator;

// populate MyList as needed...

Enum := MyList.GetEnumerator;
try
  while Enum.MoveNext do
  begin
    Node := Enum.Current;
    //Do something with Node... 
  end;
finally
  Enum.Free;
end;

如果您使用的是 Delphi 2006 或更早版本，for..in 不可用，因此您必须明确地使用上述 while 循环。

Answer 2

我会以实用的方式解决这个问题，无需修改 (*) 您要遍历的 structure/classes。

您需要的是根项和获取子项的函数。

(*) 关于您的 TMyObject class 它需要以某种方式公开 Childs（我会通过放置 property Childs: TEnumerable<TMyObject> 来使它们只读。

这里是你可以预先排序遍历基本上任何非多态层次结构的方法：

unit HierarchyEnumerator;

interface

uses
  Generics.Collections,
  SysUtils;

type
  THierarchyEnumerable<T> = record
  private
    fItems: TEnumerable<T>;
    fChildSelector: TFunc<T, TEnumerable<T>>;

    type
      TEnumerator = class
      private
        fStack: TStack<TEnumerator<T>>;
        fChildSelector: TFunc<T, TEnumerable<T>>;
        fCurrent: T;
      public
        constructor Create(const items: TEnumerable<T>; const childSelector: TFunc<T, TEnumerable<T>>);
        destructor Destroy; override;
        function MoveNext: Boolean;
        property Current: T read fCurrent;
      end;
  public
    constructor Create(const items: TEnumerable<T>; const childSelector: TFunc<T, TEnumerable<T>>);
    function GetEnumerator: TEnumerator;
  end;

implementation

{ THierarchyEnumerable<T> }

constructor THierarchyEnumerable<T>.Create(const items: TEnumerable<T>;
  const childSelector: TFunc<T, TEnumerable<T>>);
begin
  fItems := items;
  fChildSelector := childSelector;
end;

function THierarchyEnumerable<T>.GetEnumerator: TEnumerator;
begin
  Result := TEnumerator.Create(fitems, fChildSelector);
end;

{ THierarchyEnumerable<T>.TEnumerator }

constructor THierarchyEnumerable<T>.TEnumerator.Create(const items: TEnumerable<T>;
  const childSelector: TFunc<T, TEnumerable<T>>);
var
  item: T;
begin
  inherited Create;
  fStack := TStack<TEnumerator<T>>.Create;
  fStack.Push(items.GetEnumerator);
  fChildSelector := childSelector;
end;

destructor THierarchyEnumerable<T>.TEnumerator.Destroy;
begin
  fStack.Free;
  inherited;
end;

function THierarchyEnumerable<T>.TEnumerator.MoveNext: Boolean;
var
  e: TEnumerator<T>;
begin
  while fStack.Count > 0 do
  begin
    e := fStack.Pop;
    if e.MoveNext then
    begin
      fStack.Push(e);
      fCurrent := e.Current;
      fStack.Push(fChildSelector(fCurrent).GetEnumerator);
      Exit(True);
    end
    else
      e.Free;
  end;

  Result := False;
end;

end.

使用看起来像这样：

for o in THierarchyEnumerable<TMyObject>.Create(list,
  function(item: TMyObject): TEnumerable<TMyObject>
  begin
    Result := item.Children;
  end) do
  ...

如何在没有冗余列表的情况下迭代 parent/child 层次结构中的对象？

How to iterate objects in parent/child hierarchy without redundant lists?

delphi

hierarchy

tobjectlist