Project

General

Profile

Actions

Task #1318

closed

NameTree enumeration

Added by Junxiao Shi about 10 years ago. Updated about 10 years ago.

Status:
Closed
Priority:
Normal
Assignee:
Category:
Tables
Target version:
Start date:
Due date:
% Done:

100%

Estimated time:
9.00 h

Description

Implement the new API for NameTree enumeration functions.

API

namespace name_tree {
/// determines whether to visit an entry
typedef function<bool(const Entry&)> EntrySelector;
/// a functor that accepts any entry
class AnyEntry : public EntrySelector;
/// determines whether to an entry and/or its descendants
/// \return .first indicates whether to visit entry, .second indicates whether to visit its descendants
typedef function<std::pair<bool,bool>(const Entry&)> EntrySubtreeSelector;
/// a functor that accepts any entry and its descendants
class AnyEntrySubtree : public EntrySubtreeSelector;
} // namespace name_tree

partial class NameTree
{
  /// ForwardIterator; *it is name_tree::Entry& type
  typedef ... const_iterator;
  /// full enumerate
  const_iterator fullEnumerate(const EntrySelector& selector = AnyEntry()) const;
  /// partial enumerate; an entry is included if accepted by selector, and none of its ancestors is rejected by subTreeSelector
  const_iterator partialEnumerate(const Name& name, const EntrySubtreeSelector& selector = AnyEntrySubtree()) const;
  /// enumerate along name and name's ancestors
  const_iterator findAllMatches(const Name& name, const EntrySelector& selector = AnyEntry()) const;
  /// begin iterator (full enumerate)
  const_iterator begin() const;
  /// end iterator
  const_iterator end() const;
};

Notes:

  • The snippet assumes using STL iterators. It's equally fine to use Boost.Range.
  • The snippet assumes all three operations use the same type of iterator. It's equally fine to have different types.
    If different iterator types are used, fullEnumerate partialEnumerate findAllMatches should return std::pair<const_iterator, const_iterator>, and begin end are unnecessary.
  • It's unacceptable to create a new container and copy results into it.

Examples

Give a NameTree containing these entries:

  • /
  • /A
  • /A/B
  • /A/B/C
  • /A/D
  • /E
  • /F

.fullEnumerate(f) ~ .end(), where f accepts A,C,E,F only:

visits A,C,E,F in any order.

.partialEnumerate(/A, f) ~ .end(), where f accepts root,B,C,D entries and root,A,F subtrees only:

visits B,D in any order.

If an entry is rejected, its children can still be visited (eg. A is rejected, but B can be visited).

If a subtree is rejected, its children are skipped, but the root entry of subtree can be visited (eg. B is rejected, so C is skipped, but B is visited).

.findAllMatches(/A/B/C/D, f) ~ .end(), where f accepts root,B,C,F only:

visits root,B,C in any order.

.begin() ~ .end():

equivalent to .fullEnumerate(AnyEntry()); visits root,A,B,C,D,E,F in any order.


Related issues 3 (0 open3 closed)

Blocks NFD - Task #1315: FIB enumerationClosedTian Song

Actions
Blocks NFD - Task #1234: Runtime strategy changeClosedJunxiao Shi03/12/2014

Actions
Blocks NFD - Task #1341: FIB: implicitly delete FIB entryClosedJunxiao Shi

Actions
Actions #1

Updated by Haowei Yuan about 10 years ago

  • Status changed from New to In Progress

For full enumeration,.begin() ~ .end(), shall we also provide the capability of performing full enumeration on FIB, PIT, or Measurement, with entry selector as an input argument?

Actions #2

Updated by Junxiao Shi about 10 years ago

  • Description updated (diff)
Actions #3

Updated by Haowei Yuan about 10 years ago

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?

Actions #4

Updated by Junxiao Shi about 10 years ago

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.

Actions #5

Updated by Haowei Yuan about 10 years ago

  • % Done changed from 0 to 30
Actions #6

Updated by Haowei Yuan about 10 years ago

  • 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?

Actions #7

Updated by Haowei Yuan about 10 years ago

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

Actions #8

Updated by Junxiao Shi about 10 years ago

  • Description updated (diff)
Actions #9

Updated by Alex Afanasyev about 10 years ago

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.

Actions #10

Updated by Junxiao Shi about 10 years ago

  • Description updated (diff)

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

Actions #11

Updated by Haowei Yuan about 10 years ago

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.

Actions #12

Updated by Junxiao Shi about 10 years ago

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.

Actions #13

Updated by Haowei Yuan about 10 years ago

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

Actions #14

Updated by Junxiao Shi about 10 years ago

  • Description updated (diff)

Haowei Yuan wrote:

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

See Task Description, look for "EntrySubtreeSelector".

Actions #15

Updated by Junxiao Shi about 10 years ago

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

Actions #16

Updated by Haowei Yuan about 10 years ago

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

Actions #17

Updated by Haowei Yuan about 10 years ago

  • % Done changed from 30 to 60

fullEnumeration(), begin(), and end() functions have been submitted to gerrit, please review.

Actions #18

Updated by Haowei Yuan about 10 years ago

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)..

Actions #19

Updated by Junxiao Shi about 10 years ago

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.

Actions #20

Updated by Haowei Yuan about 10 years ago

  • % Done changed from 60 to 70

Update: .partialEnumerate() is done. I am working on the unit test code now.

  • I will use the example in the description and a few corner cases to test the code. If you have interesting testing examples, please let me know.
Actions #21

Updated by Haowei Yuan about 10 years ago

  • Status changed from In Progress to Code review
  • % Done changed from 70 to 100
Actions #22

Updated by Junxiao Shi about 10 years ago

  • Status changed from Code review to Closed
Actions

Also available in: Atom PDF