NFD

I plan to use the same type of iterator. For the NameTree iterator class, is there any preference on whether it should be a nested class within Name Tree or it should simply be a friend class of the name tree class?

Nested iterator class or iterator class made as a friend are both acceptable. If separate iterator class is used, it shall be declared inside nfd::name_tree namespace, and typedef'ed as NameTree::const_iterator.

• I am working on const_iterator now, do we also need a regular iterator class?

• Inside the (const) iterator class, shall we keep a name_tree::entry* or a shared_ptr as the private member? Any preference?

I have a question about the partialEnumerate() description in the task description.

.partialEnumerate(/A, f1, f2) ~ .end(), where f1 accepts root,B,C,D only, and f2 accepts root,A,F only:
visits root,B,D in any order.
If an entry is rejected by f1, its children can still be visited (eg. A is rejected by f1, but B can be visited).
If an entry is rejected by f2, its children are skipped, but the entry itself can be visited (eg. B is rejected by f2, so C is skipped, but B is visited).

It seems to me that since /A is given, the partialEnumerate function should start with /A, rather than start with Root(/). As a result, even Root can be accepted by f1, it still should not be visited by this iterator.

In addition, what's the use cases of this partialEnumeration() function? I thought generally the entrySelector would just check if this entry contains a FIB entry or not..

I'm also have a question about partialEnumeration. What is the intended use case for it?

Also, there is a performance problem---each entry is required to be checked twice (= name will be compared twice). More efficient (but less straightforward) is to use different predicate f, that returns not just true/false, but enum value: Reject, RejectNodeAcceptChildren, AcceptNodeRejectChildren. In this case, optimization is possible inside the predicate.

Junxiao Shi wrote:

partialEnumerate is used by StrategyChoice::changeStrategy to clear incompatible StrategyInfo attached under a namespace whosee effective Strategy is being changes. If a subtree has another StrategyChoice entry, its effective Strategy is unchanged and would be skipped.

I am working on the iterator for the partial enumeration. As we will need to follow children pointers in each Name Tree entry, the behavior of this iterator is the same as an iterator for a tree (with multiple children for each node). The current algorithm works as follows:

1. To start, find the left-most child (A) (this child node has no children, or it cannot be accepted by f2), this is our current *this.
2. Check to see if this child has a sibling or not via: visiting its parent node, go through parent node's children list, and see if this child is in the end.
3. If this child is in the end of the list, then there is nothing left in this subtree, and we need to check its parent.
   • 3-1. If the parent node is accepted by f1, then parent becomes the current *this.
   • 3-2. If the parent node is not accepted by f1, then goto 2 and check parent's sibling.
4. If the left-most child (A) has a sibling (S)
   • 4-1. If S is not accepted by f2, then go to 2 to see if S has a sibling or not.
   • 4-2. If S is accepted by f2, then find the left-most child (say B) in that subtree.
     • 4-2-1. If B is accepted by f1, then B becomes the *this.
     • 4-2-2. If B is not accepted by f1, then go to 1 check B's siblings.

Essentially, this is similar to post-order traversal, as we won't process the parent node until all of the children are processed. In terms of efficiency, the post-order traversal requires walking down the tree and then walking up, which takes more time comparing to the current breadth-first search method, but doesn't require additional memory space.

Please let me know if you see a more efficient way of implementing the iterator for partialEnumerate.

NameTree is free to iterate in any order.

Please note that there is only one selector now, which determines ( whether to visit node, whether to visit children ) together.
The reason for this change is in note-9.

Pre-order tree traversal shall be more efficient after this API change, because the EntrySubtreeSelector only needs to be invoked once.

What's the return value of this single selector? Are they Reject, RejectNodeAcceptChildren, AcceptNodeRejectChildren?

If partialEnumerate needs longer time, please prioritize fullEnumerate and check in this one first, so that #1315 can start.

OK, I will work on fullEnumerate() function first.

Junxiao Shi wrote:

NameTree is free to iterate in any order.

Please note that there is only one selector now, which determines ( whether to visit node, whether to visit children ) together.
The reason for this change is in note-9.

Pre-order tree traversal shall be more efficient after this API change, because the EntrySubtreeSelector only needs to be invoked once.

It seems to me that pre-order traversal also requires invoking this selector twice. The first time is when a node satisfies the requirement and returned back; the second time is when the ++ operator is applied to this node, then the first thing to do is check if has any children and if this subtree is acceptable (which requires invoking the selector). So it seems pre-order and post-order traversal have similar complexity.

.partialEnumerate() will be added tomorrow (Thursday)..

A boolean field in iterator can remember selector's decision. operator++ uses this field to decide whether to visit children, or move to sibling/patent.