Перебор вложенных списков с помощью функции Next () без генератора

Question

Хотя я бы хотел решить эту проблему в python, я застрял в Delphi на этот раз. У меня есть вложенные списки (на самом деле объекты с вложенными списками в качестве свойств, но не имеют значения), и я хочу перебирать их в генераторе. То есть я хочу написать функцию Next, которая дает мне следующий элемент из листьев дерева, описанных вложенными списками.

Например, допустим, у меня есть

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

Я хочу, чтобы 8 последовательных вызовов Next () вернули 1..8.

Как я могу сделать это на языке без выхода и генераторов?

Обратите внимание, что глубина вложения фиксирована (2 в этом примере, 4 в реальной жизни), но приветствуются ответы, которые решают более общий случай, когда глубина является переменной.

РЕДАКТИРОВАТЬ: Извините, я должен был упомянуть, это Delphi 2007.

Answer 1

Если вы используете какой-либо список Delphi со встроенным перечислителем, это можно сделать достаточно легко с небольшим количеством рекурсии. Ваш базовый список представляет собой список чисел, например TList<integer>. Затем у вас есть вложенные списки, реализованные как TList<TList<integer>>. (Я предполагаю, что у вас Delphi 2009 или 2010. Если нет, то он становится немного хитрее.)

Вам нужно сделать свой собственный специализированный класс списков спущенным с TList<T> и добавить к нему виртуальную функцию Next () и поле для перечислителя для вашего списка. При настройке цикла for..in компилятор использует внутренние счетчики, но вы можете запустить их вручную. Функция Next () создает перечислитель, если он еще не назначен, и помещает его в поле, а затем вызывает MoveNext () для него. Если это удастся, позвоните в GetCurrent и получите свой номер. В противном случае, вы сделали. Освободите перечислитель и сообщите вызывающей функции, что вам нечего возвращать. Вероятно, самый простой способ сделать это - поместить логический параметр var в Next (), который возвращает результат своего вызова MoveNext, и вызывающая функция проверяет его значение.

Для более высоких списков это немного сложнее, но не намного. Отойдите от общего класса, который вы только что установили, и переопределите Next (). Он получит перечислитель, который перечисляет списки, которые он содержит, и вернет значение FEnumerator.GetCurrent.Next() до тех пор, пока этот подсписок не будет исчерпан, а затем вызовет MoveNext для своего перечислителя.

Это должно работать для любой глубины вложенных списков. Только не пытайтесь составить список, содержащий как цифры, так и списки.

Answer 2

Чтобы решить эту проблему, я сделал полный список индексов и запомнил свою позицию в этом: (по-Питонски, потому что он короче)

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]]

Очевидно, что мой список не меняется во время итерации, или это, вероятно, не сработает ...

Answer 3

Метод 1: «многоуровневый список» - это дерево, используйте (или напишите) класс дерева / триода и выполните простой поиск его значений в глубину.

Метод 2: явно напишите поиск в глубину для типа многоуровневого списка:

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;

В основном вы явно делаете то, что будет делать «yield» (то есть: сохраните «стоп-копию» стека вызовов, верните текущее значение)

Использование:

LEnum : TEnumerator;

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