Если есть дерево, которое имеет rootNode и указывает налево и направо для своих дочерних узлов (бинарное дерево), есть ли способ преобразовать его в быстрое перечисление, как в Objective-C 2.0? Так что мы можем сделать
for (id node in [tree allNodes]) {
// do something
}
предпочтительно без создания объекта O(n) для размера памяти, используя объект коллекции, такой как NSMutableArray, NSSet или NSDictionary.
Порядок не важен, но он может оказаться порядком в глубину.
Когда вы реализуете быстрое перечисление, вам не нужно возвращать все элементы сразу. Конечно, все, что вы получаете, возвращая их по одному, — это быстрый синтаксис перечисления без особого выигрыша в производительности.
Вы можете возвращать один элемент каждый раз, когда вызывается countByEnumeratingWithState:objects:count, или вы можете возвращать все элементы или даже только N элементов.
Например, допустим, у вас есть огромное дерево. Вы можете использовать переданный вам буфер стека и его длину:
NSUInteger numItemsToReturn = MIN(100, lengthOfStackBuffer);
Затем вы можете продолжить обход дерева до numItemsToReturn или пока не дойдете до конца вашего дерева.
Внутренняя инфраструктура будет продолжать вызывать countByEnumeratingWithState:objects:count до тех пор, пока не "увидит" нужное количество элементов.
Однако обратите внимание, что если вы вернете только часть данных, вам придется сохранить информацию в state, чтобы вы знали, где возобновить работу в следующий раз. Вот для чего нужен extra.
ИЗМЕНИТЬ
Видел ваш комментарий к исходному сообщению... Если вы хотите поддерживать быстрое перечисление, то это довольно просто, как упоминалось выше.
Однако, если вы просто хотите пройтись по дереву, чтобы что-то сделать, вы можете рассмотреть 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.
}];
Как говорят Джоди и Вальдрампус, вы должны соответствовать NSFastEnumeration. Это позволит вам написать:
for (id node in tree) {
// do something
}
В дополнение к этому, как вы говорите, существует несколько способов перечисления, т.е. обхода вашего дерева: сначала приходит на ум глубина (предварительный порядок, порядок, постпорядок) или ширина. Вы можете подклассифицировать свое дерево и предложить различные реализации метода делегата countByEnumeratingWithState:objects:count по мере необходимости или (лучше) иметь typedef и свойство, описывающие, как дерево должно быть пройдено, и обращаться к этому в методе делегата.
Если вы хотите пройти по дереву несколькими способами (до, в порядке, после заказа), вы также можете рассмотреть возможность создания собственной 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, что позволяет вам зацикливаться в обратном порядке.
