Skip to content

Update traversal to allow post-order traversal #301

Open
@grapoza

Description

@grapoza

Currently only pre-order traversal is supported by the depthFirstSearch and breadthFirstSearch methods. Traversal should be updated to allow both pre and post order callbacks. Here's a proof-of-concept that got worked out during the initial filtering work. It would need to be updated to include filtering, which would be trivial.

  // TODO incorporate this into regular traversal method
  function depthFirstTraverseWithPostorder(nodeActionPreorderCallback, nodeActionPostorderCallback) {

    if (treeModel.value.length === 0) {
      return;
    }

    let nodeQueue = treeModel.value.slice();
    let visited = [];  // OPTIMIZATION - Don't track this if no postorder callback is given (and also don't push current after preorder processing)

    while (nodeQueue.length > 0) {
      let current = nodeQueue.shift();

      if (!visited.includes(current)) {
        nodeActionPreorderCallback(current);
        visited.push(current);

        let childrenPropName = current.treeNodeSpec.childrenProperty;
        nodeQueue = [...current[childrenPropName], current].concat(nodeQueue);
      }
      else {
        // this is either a leaf or a parent whose children have all been processed
        nodeActionPostorderCallback(current);
      }
    }
  }

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions