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

Is there a way to set a personalized callback function when closing a modal with MicroModal?

Unable to transfer an object into a component due to a subscribe restriction

Can you explain the distinction between using this.function and making a function call in React?

PHP object representing a datetime in JSON format

What is the best way to distinguish if users are accessing my Facebook app through an iframe or by directly entering the

Highlighting table column when input is selected

AngularJS: Importing a parent directive within a child directive

Using CKEditor in an AngularJS web application: Tips and tricks

Raspberry Pi 4: My LED is only blinking 8 times instead of the expected 16 times

Utilize or Bring in an external JavaScript file within Ionic 2

What is the best way to refresh or render a list in a React application?

Discovering nested routes in Ember.js through search functionality

Converting HTML content into a single string simplifies data manipulation and extraction

audio enhancement in a web-based game

ng grid shift select issue mistakenly selects extra rows

Having issues transferring the variable from JavaScript to PHP?

gulp-webpack is unable to locate node packages

Please provide the text input for the specified version numbers (1.1, 1.2, 3.0, etc.)

Incoming information obtained via Websocket

A ServiceWorker used a promise in FetchEvent.respondWith() that resulted in a non-Response value of 'undefined'. This caused an issue in browser-sync