Использование Objective-C, есть ли способ конвертировать дерево в Fast Enumeration?

Question

Если есть дерево, которое имеет rootNode, и оно указывает налево и вправо для своих дочерних узлов (двоичное дерево), есть ли способ преобразовать его в Fast Enumeration, как в Objective-C 2.0? Таким образом, мы можем сделать

for (id node in [tree allNodes]) { 
    // do something 
} 

предпочтительно, без построения O (N) объекта для размера памяти, используя объект коллекции, такие как NSMutableArray, NSSet или NSDictionary.

Порядок не имеет значения, но он может быть выполнен как заказ глубины.

Answer 1

При реализации быстрого перечисления вам не нужно возвращать сразу все элементы. Конечно, все, что вы получаете, если вы возвращаете их по одному, - это быстрый синтаксис перечисления, без значительной выгоды от производительности.

Вы можете вернуть один элемент каждый раз, когда вызывается countByEnumeratingWithState:objects:count, или вы можете вернуть все элементы или даже только N элементов.

Например, скажем, у вас огромное дерево. Вы можете использовать стек буфера передается вам, и его длина:

NSUInteger numItemsToReturn = MIN(100, lengthOfStackBuffer); 

Затем вы могли продолжить обходе дерева до numItemsToReturn или пока вы достигли конца своего дерева.

Внутренняя инфраструктура будет продолжать звонить countByEnumeratingWithState:objects:count, пока не «увидит» правильное количество элементов.

Обратите внимание, что если вы только возвращаете часть данных, вам необходимо будет хранить информацию в state, чтобы вы знали, где можно возобновить работу в следующий раз. Вот что такое extra.

EDIT

Видел ваш комментарий на исходное сообщение ... Если вы хотите поддержать быстрый-перечисление, то это довольно легко, как уже упоминалось выше.

Однако, если вы просто хотите пройти дерево, чтобы сделать что-то, вы можете рассмотреть API перечисления. Например:

-(void)enumerateWithOptions:(MyTreeEnumerationOptions)options 
       usingBlock:^(id object, unsigned int level, BOOL isLeaf, BOOL *stop)block { 
    // In here, you can use the options to determine if you are doing 
    // pre/post depth first search, breadth-first, reverse, even concurrent. 
    // You also provide an easy way to communicate to the caller not only the 
    // object at this node, but the tree-depth of this node, whether it is a 
    // leaf, and anything else you want to communicate. 
} 

Пользователи могли бы назвать:

[tree enumerateWithOptions:PreOrderDepthFirst 
       usingBlock:^(id object, unsigned int level, BOOL isLeaf, BOOL *stop) { 
    // Execute whatever code you want with this object... 
    // Set *stop = YES to abort the enumeration. 
}]; 

Answer 2

Как Джоди и waldrumpus говорят, вы должны соответствовать NSFastEnumeration. Это позволит вам написать:

for (id node in tree) { 
    // do something 
} 

В дополнении к этому, есть такой, как вы говорите, несколько способов перечислить т.е. траверса вашего дерево: Глубина первой (предзаказ, Симметричный, postorder) или ширину первым приходит на ум , Вы можете подклассифицировать свое дерево и предложить различные реализации метода делегирования countByEnumeratingWithState:objects:count как подходящие или (лучше) иметь typedef и свойство, описывающее, как дерево должно пройти, и обратиться к этому в методе делегата.

Answer 3

Если вы хотите пересечь дерево несколькими способами (pre-, in-, post-order), вы также можете подумать о создании собственных подклассов NSEnumerator вместо того, чтобы соответствовать только NSFastEnumeration.

Итак, создайте подклассы NSPreorderEnumerator, NSInorderEnumerator и NSPostOrderEnumerator, которые знают, как перемещаться по дереву.

Затем ваши объекты дерева отвечают на -preorderEnumerator, -inorderEnumerator, -postorderEnumerator, возвращая новый счетчик, созданный для вашего дерева.

Вы можете сделать

for(id node in [tree preorderEnumerator]) { 
    // do stuff 
} 

for(id node in [tree postorderEnumerator]) { 
    // do stuff 
} 

NSArray делает что-то подобное с -reverseObjectEnumerator, что позволяет вам петлю в обратном направлении.