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

Question

I have an object something like this...

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;

(There's much more but this is the fundamental idea)

This allows a simple parent/child relationship between objects, a hierarchy. One is the root, which contains a hierarchy of more.

All this is fine, except I also need to iterate a complete list of all these objects, regardless of hierarchy.

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

end;

Naturally, I could just create an object list and maintain both at the same time...

FAllObjects: TObjectList<TMyObject>;

However, this is redundant. Every instance of TMyObject would have to be added/deleted to each structure at the same time. I'd like to get rid of requiring one master list, and only use the hierarchy objects. But I don't know how I could iterate all the objects without following the recursive hierarchy. For example, something as simple as getting a total count of all these items.

How can I maintain such an object hierarchy (which I can iterate all items in one single loop) without having to maintain two separate redundant structures?

For example, the TTreeView.Items has the behavior I'd like. You can use Items.Count and Items[Index] to iterate all items, or you can recursively iterate the tree hierarchy.

Answer 1

In a standard TTreeView, the best way to iterate through all of its nodes in a "linear" fashion from top to bottom is to utilize the TTreeNode.GetNext() method in a while loop, eg:

var
  Node: TTreeNode;

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

In your custom node list, you can implement a similar iteration by implementing an Enumerator that can be used with a for..in loop, which was introduced in Delphi 2007. See Embarcadero's documentation for more details:

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

For example:

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;

Behind the scenes, the compiler will generate code similar to the following:

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;

If you are using Delphi 2006 or earlier, for..in is not available, so you will have to use the above while loop explicitly instead.