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.

Answer 2

I would solve this in a functional way without any need to modify (*) the structure/classes you want to traverse.

What you need is the root items and a function to get an items childs.

(*) Regarding your TMyObject class it would need to expose the Childs somehow (I would do that by putting a property Childs: TEnumerable<TMyObject> in order to make them read only.

Here is how you can pre-order traverse basically any non-polymorph hierarchy:

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.

Using would look like this:

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