Personalized path-finding tree iterator

Question

Personalized path-finding tree iterator

I am trying to implement a custom iterator in JavaScript that can traverse a DOM tree based on specific criteria provided by a callback function. The goal is to return an array of the nodes that match the criteria as the generator iterates through the tree structure.

  root
  / \
P1   P2
 |   |
T1   T2

The idea is to use iter.next(isP) or iter.next(isText) to update the matcher and move to the next matching node in the tree.

type Matcher = (node: INode) => boolean
export function* nextNode(node: INode, matcher: Matcher = () => true, store: []): Generator<INode, any, Matcher> {
  let reset: Matcher = matcher
  store = store.concat(node)
  if (reset(node)) {
    reset = yield store
    store = []
  }
  if (node.children) {
    for (let childNode of node.children) {
      yield *nextNode(childNode, matcher, store)
    }
  }
  return
}

One issue I have encountered is that the reset variable gets lost as the function call stack is popped. This causes problems when trying to switch the matcher in the middle of traversal, such as going from one text node to another. How can this be addressed?

const iter = nextNode(root, isT)
iter.next() <-- currently at T1
iter.next(isP) <-- expected to go to T2 instead of P2

javascript typescript iterator generator

Answer 1

Answer №1

Utilize the return value of the generator to carry forward the traversal state. Once yield* returns from the first child of the root, it will provide you with the store and matcher that were made available in the subsequent next call after yielding root and p1.

…
if (node.children) {
  for (let childNode of node.children) {
    [reset, store] = yield* nextNode(childNode, reset, store)
//  ^^^^^^^^^^^^^^^^^                           ^^^^^
  }
}
return [reset, store]
//     ^^^^^^^^^^^^^^

An illustration:

function* nextNode(node, matcher = () => true, store = []) {
  store.push(node.name)
  if (matcher(node)) {
    matcher = yield store
    store = []
  }
  if (node.children) {
    for (let childNode of node.children) {
      [matcher, store] = yield* nextNode(childNode, matcher, store)
    }
  }
  return [matcher, store]
}

const node = (name, children) => ({name, children})
const is = c => n => n.name[0] == c

const iter = nextNode(node("root", [
  node("p1", [node("t1")]),
  node("p2", [node("t2")])
]), is("t"))
console.log("until next t:", iter.next())
console.log("until next p:", iter.next(is("p")))
console.log("until next p:", iter.next(is("p")))

Answer 2

Utilize the return value of the generator to carry forward the traversal state. Once yield* returns from the first child of the root, it will provide you with the store and matcher that were made available in the subsequent next call after yielding root and p1.

…
if (node.children) {
  for (let childNode of node.children) {
    [reset, store] = yield* nextNode(childNode, reset, store)
//  ^^^^^^^^^^^^^^^^^                           ^^^^^
  }
}
return [reset, store]
//     ^^^^^^^^^^^^^^

An illustration:

function* nextNode(node, matcher = () => true, store = []) {
  store.push(node.name)
  if (matcher(node)) {
    matcher = yield store
    store = []
  }
  if (node.children) {
    for (let childNode of node.children) {
      [matcher, store] = yield* nextNode(childNode, matcher, store)
    }
  }
  return [matcher, store]
}

const node = (name, children) => ({name, children})
const is = c => n => n.name[0] == c

const iter = nextNode(node("root", [
  node("p1", [node("t1")]),
  node("p2", [node("t2")])
]), is("t"))
console.log("until next t:", iter.next())
console.log("until next p:", iter.next(is("p")))
console.log("until next p:", iter.next(is("p")))

Answer 3

Answer №2

It appears that implementing a global matcher could be a straightforward solution.

type Matcher = (node: INode) => boolean
type TYield = INode[]
function* traverseNodes(
  node: INode,
  matcher: Matcher = () => true,
): Generator<TYield, TYield, Matcher> {
  let store: INode[] = []
  let reset = matcher
  function* _traverseNodes(node: INode): Generator<TYield, any, Matcher> {
    store.push(node)
    if (reset(node)) {
      reset = yield store
      if (!reset) reset = matcher
      store = []
    }
    if (node.children) {
      for (const childNode of node.children) {
        yield* _traverseNodes(childNode)
      }
    }
    return
  }
  yield* _traverseNodes(node)
  return store
}

Answer 4

It appears that implementing a global matcher could be a straightforward solution.

type Matcher = (node: INode) => boolean
type TYield = INode[]
function* traverseNodes(
  node: INode,
  matcher: Matcher = () => true,
): Generator<TYield, TYield, Matcher> {
  let store: INode[] = []
  let reset = matcher
  function* _traverseNodes(node: INode): Generator<TYield, any, Matcher> {
    store.push(node)
    if (reset(node)) {
      reset = yield store
      if (!reset) reset = matcher
      store = []
    }
    if (node.children) {
      for (const childNode of node.children) {
        yield* _traverseNodes(childNode)
      }
    }
    return
  }
  yield* _traverseNodes(node)
  return store
}

Personalized path-finding tree iterator

Answer №1

Answer №2

Similar questions

What is the best way to run a function within an if statement without duplicating code if the condition is false?

Is there a way to efficiently import only a specific data array into a NextJs page without importing the entire component dynamically?

Creating a menu header similar to Gmail's design is a great way to

The implementation of useState is not functioning properly when used within a parent useState function

Attempting to nest an AJAX request within the success callback of another AJAX request

Ensuring session data is updated when saving a mongoose model

Encountering issues with React Apollo hooks after integrating React Native into the monorepo system

How can I set an object as a variable in JavaScript (specifically React) based on two different conditions?

The Intersection Observer fails to function properly with images

The process of incorporating user properties into the output of a Service Bus topic from a Javascript Azure Function

Is it feasible to bring in a Typescript file into an active ts-node REPL session?

Leverage the power of Angular's $http module in conjunction with Django's urlpatterns to fetch

Is there a way to substitute the HOC with a single call and solely modify the prop?

Efficient method for managing complex JSON object updates using setState in React

Using typescript, we can pass a generic class as a parameter to a function

Problems that seem to loop endlessly

The next-auth/discord callbacks do not make any changes to the data

The combination of Object.keys() and the find function

Vue element fails to appear on the screen

"Using axios and async/await in VUE.JS to perform multiple asynchronous GET