Iterating over nested lists with a Next() function, without a generator.

Question

Whilst I'd love to solve this problem in python, I'm stuck in Delphi for this one. I have nested lists (actually objects with nested lists as properties, but nevermind), and I want to iterate over them in a generator fashion. That is, I want to write a Next function, which gives me the next item from the leaves of the tree described by the nested lists.

For example, lets say I have

 [[1,2,3],[4,5],[],[6],[7,8]]

I want 8 consecutive calls to Next() to return 1..8.

How can I do this in a language without yield and generators?

Note that the depth of the nesting is fixed (2 in this example, 4 in real life), but answers which solve the more general case where depth is variable are welcome.

EDIT: Sorry, I should have mentioned, this is Delphi 2007.

Answer 1

If you're using any Delphi list that has a built-in enumerator, it can be done easily enough with a bit of recursion. Your base list is a list of numbers, like a TList<integer>. Then you have nested lists implemented as TList<TList<integer>>. (I'm assuming you have Delphi 2009 or 2010. If not, it gets a bit trickier.)

What you need is to make your own specialized list class descended from TList<T> and add a virtual Next() function to it, and a field for an enumerator for your list. The compiler uses enumerators internally when you set up a for..in loop, but you can run them manually. The Next() function creates the enumerator if it's not already assigned and puts it in the field, then calls MoveNext() on it. If this succeeds, call GetCurrent and get your number. Otherwise, you're done. FreeAndNil the enumerator, and signal to the calling function that you've got nothing to return. Probably the simplest way to do this is to put a var boolean parameter in Next() that returns the result of its call to MoveNext, and have the calling function check its value.

For the higher lists, it's a little more complicated, but not much. Descend from the generic class you just set up, and override Next(). This one will get an enumerator that enumerates over the lists that it holds, and return the value of FEnumerator.GetCurrent.Next() until that sub-list is exhausted, then call MoveNext on its enumerator.

This should work for any depth of nested lists. Just don't try to make a list that contains both numbers and lists.

Answer 2

Method 1 : a "layered list" is a tree, use (or write) a tree/treenode class, and do a simple depth-first search of its values.

Method 2 : explicitly write the depth-first search for your layered list type :

TEnumerator = RECORD
  private
    FStack : Stack of TNestedList;  //a stack, holding which level of the tree you are exploring
    FIndexStack : Stack of Integer; //a twin stack, holding the index of the child you are exploring at each layer

  public
    Init( AList : TNestedList );
    Next( var AVal : Integer ) : boolean;
end;


procedure TEnumerator.Init( AList );
begin
  SetLength(FStack, 1);
  FStack[0] := AList;
  SetLength( FIndexStack, 1 );
  FIndexStack[0] := 0;

  _GoToNextValue();
end;

procedure TEnumerator._GoToNextValue();
begin
  while FStack.notEmpty()
    and FIndexStack.last > FStack.last.length do
     begin
     //we have finished exploring FStack.last, we need to explore its next sibling :
     //pop FStack.last :
       FIndexStack.pop;
       FStack.pop;
     //go to next sibling :
       FIndexStack.last := FIndexStack.last + 1;
     end;

  //nothing left to explore :
  if FStack.empty then Exit;

  //else :
  //  dig through the layers of list until you reach a value
  while FStack.last.isAList() do
  begin
    FStack.push( FStack.last[ FIndexStack.last ] );
    FIndexStack.push( 0 );    
  end;
end;

function Next( var AVal : Integer ) : boolean;
begin
  _GoToNextValue();

  Result := FStack.notEmpty();

  if Result then
  begin
    AVal := FStack.last[ FIndexStack.last ];
    FIndexSatck.last := FIndexSatck.last + 1;
  end;
end;

You basically do explicitly what a "yield" would do (ie : save a "freeze copy" of the call stack, return the current value)

Usage :

LEnum : TEnumerator;

LEnum.Init( myList );
while LEnum.Next( LVal ) do
begin
  <do something>
end;

Answer 3

To solve this problem, I ended up making a flat list of indexes and remembering my position in that: (in pythonesque, because its shorter)

class Nested:
    nestedList = [[1,2,3],[4,5],[],[6],[7,8]]
    positions = []
    curr = 0

    def Setup:
        for a in nestedList:
            for b in a:
               positions.add((a,b))

    def Next:
        p = positions[curr]
        curr += 1
        return nestedList[p[0]][p[1]]

Obviously my list doesn't change during iteration or this probably wouldn't work...