Exploring numerical characters within a sequence of characters

Question

Exploring numerical characters within a sequence of characters

I'm currently working on developing a function that can handle a flat array of string decimal integers representing nodes in a tree. Each period signifies hierarchy within the tree. The goal is to build functions called prevNode and nextNode, which will take three parameters: ids, id, planeLock. If a node does not have a previous or next id, the function will return false. When planeLock is set to true, the navigation will stay on the same level instead of moving to the child nodes (e.g., from 1 to 0.1). This is referred to as navigating within the same plane, i.e., sibling nodes rather than their deepest children.

var ids = [
  '0',
  '0.1',
  '1',
  '2',
  '2.0',
  '2.1',
]

prevNode(ids, '0') -> false // no previous node
prevNode(ids, '1', true) -> 0 // stays on the same plane with plane lock
prevNode(ids, '1') -> 0.1 // previous node in the tree
prevNode(ids, '2.0', true) -> false
prevNode(ids, '2.0') -> 2 // goes up one node

What would be the best approach to parse these strings for the intended outcomes?

javascript arrays sorting traversal

Answer 1

Answer №1

Here is a potential solution:

const determineDepth = (nodeID) => {
  return nodeID.split('.').length;
}

const findSiblingNode = (nodeIDs, targetID, lockLevel, goBackwards) => {
  let index = nodeIDs.indexOf(targetID);
  let level = determineDepth(targetID);

  while (goBackwards ? --index >= 0 : ++index < nodeIDs.length) {
    let currentElement = nodeIDs[index];
    let currentLevel = determineDepth(currentElement);
    if (!lockLevel || currentLevel === level) {
      return currentElement;
    }
    if (currentLevel < level) {
       break;
    }
  }
  return false; 
}

const findPreviousNode = (nodeIDs, targetID, lockLevel) => {
  return findSiblingNode(nodeIDs, targetID, lockLevel, true);
}

const findNextNode = (nodeIDs, targetID, lockLevel) => {
  return findSiblingNode(nodeIDs, targetID, lockLevel, false);
}

Check out the demo. It seems that there's a trade-off between caching all depths (quicker but uses memory) and not doing so (slower). If the array is dynamic and you often need to find insertion points, using memoization is recommended. This way, you won't have to recalculate levels repeatedly upon each insertion.

Answer 2

Here is a potential solution:

const determineDepth = (nodeID) => {
  return nodeID.split('.').length;
}

const findSiblingNode = (nodeIDs, targetID, lockLevel, goBackwards) => {
  let index = nodeIDs.indexOf(targetID);
  let level = determineDepth(targetID);

  while (goBackwards ? --index >= 0 : ++index < nodeIDs.length) {
    let currentElement = nodeIDs[index];
    let currentLevel = determineDepth(currentElement);
    if (!lockLevel || currentLevel === level) {
      return currentElement;
    }
    if (currentLevel < level) {
       break;
    }
  }
  return false; 
}

const findPreviousNode = (nodeIDs, targetID, lockLevel) => {
  return findSiblingNode(nodeIDs, targetID, lockLevel, true);
}

const findNextNode = (nodeIDs, targetID, lockLevel) => {
  return findSiblingNode(nodeIDs, targetID, lockLevel, false);
}

Check out the demo. It seems that there's a trade-off between caching all depths (quicker but uses memory) and not doing so (slower). If the array is dynamic and you often need to find insertion points, using memoization is recommended. This way, you won't have to recalculate levels repeatedly upon each insertion.

Answer 3

Answer №2

Implementing a sort algorithm is a solid strategy. However, for added functionality, consider transforming your list of IDs into a tree structure.

function createSortedTree(ids) {
  var tree = {name: "", id: "root", children: {}};
  function insert(tree, elem) {
    if(!tree.children[elem[0]]) {
      tree.children[elem[0]] = {
        id: elem[0],
        children: {},
        parent: tree,
        name: tree.id === "root" ? "" + elem[0] : tree.name + "." + elem[0]
      };
    }
    if(elem.length > 1) insert(tree.children[elem[0]], elem.slice(1));
  }
  for(i in ids) insert(tree, ids[i].split("."));

  function traverse(tree) {
    if(current) {
      current.next = tree;
      tree.prev = current;
    }
    current = tree;

    var children = Object.keys(tree.children)
                         .sort(function(a, b) {if(a < b) return -1; else if(a > b) return 1; else return 0;})
                         .map(function(key) {return tree.children[key]});
    for(i in children) {
      if(i > 0) children[i].prevPlane = children[i-1];
      if(i < children.length - 1) children[i].nextPlane = children[i+1];
      traverse(children[i]);
    }
  }
  var current = null;
  traverse(tree);

  return tree;
}

function getNode(tree, id) {
  if(typeof id === "string") id = id.split(".");
  if(id.length === 0) return tree;
  else return getNode(tree.children[id[0]], id.slice(1));
}

var tree = createSortedTree(["0", "0.1", "1", "2", "2.0", "2.1"])
var node = getNode(tree, "2.0");
console.log(node.prev.name);
console.log(node.next.name);

var node = getNode(tree, "1");
console.log(node.prev.name);
console.log(node.prevPlane.name);

http://jsfiddle.net/jxyqjq3c/

Answer 4

Implementing a sort algorithm is a solid strategy. However, for added functionality, consider transforming your list of IDs into a tree structure.

function createSortedTree(ids) {
  var tree = {name: "", id: "root", children: {}};
  function insert(tree, elem) {
    if(!tree.children[elem[0]]) {
      tree.children[elem[0]] = {
        id: elem[0],
        children: {},
        parent: tree,
        name: tree.id === "root" ? "" + elem[0] : tree.name + "." + elem[0]
      };
    }
    if(elem.length > 1) insert(tree.children[elem[0]], elem.slice(1));
  }
  for(i in ids) insert(tree, ids[i].split("."));

  function traverse(tree) {
    if(current) {
      current.next = tree;
      tree.prev = current;
    }
    current = tree;

    var children = Object.keys(tree.children)
                         .sort(function(a, b) {if(a < b) return -1; else if(a > b) return 1; else return 0;})
                         .map(function(key) {return tree.children[key]});
    for(i in children) {
      if(i > 0) children[i].prevPlane = children[i-1];
      if(i < children.length - 1) children[i].nextPlane = children[i+1];
      traverse(children[i]);
    }
  }
  var current = null;
  traverse(tree);

  return tree;
}

function getNode(tree, id) {
  if(typeof id === "string") id = id.split(".");
  if(id.length === 0) return tree;
  else return getNode(tree.children[id[0]], id.slice(1));
}

var tree = createSortedTree(["0", "0.1", "1", "2", "2.0", "2.1"])
var node = getNode(tree, "2.0");
console.log(node.prev.name);
console.log(node.next.name);

var node = getNode(tree, "1");
console.log(node.prev.name);
console.log(node.prevPlane.name);

http://jsfiddle.net/jxyqjq3c/

Answer 5

Answer №3

const _ = require('lodash')

function comparePaths (path1, path2) {
  const path1Arr = path1.split('.')
  const path2Arr = path2.split('.')
  const maxLength = Math.max(path1Arr.length, path2Arr.length)
  let index = 0
  while (index < maxLength) {
    if (!path1Arr[index] || +path1Arr[index] < +path2Arr[index]) {
      return -1
    }
    if (!path2Arr[index] || +path1Arr[index] > +path2Arr[index]) {
      return 1
    }
    index++
  }
  return 0
}

function getSubset (idsArray, idValue) {
  return _.filter(idsArray, function (_id) {
    const _idArr = _id.split('.')
    const idArr = idValue.split('.')
    const _choppedId = _.take(_idArr, _idArr.length - 1).join('.')
    const choppedId = _.take(idArr, idArr.length - 1).join('.')
    if (_choppedId === choppedId) return true
    return false
  })
}

function extractMetadata (idsList, targetId) {
  idsList = idsList.sort(comparePaths)
  const idx = idsList.indexOf(targetId)
  const metadata = {}
  metadata.prev = (idsList[idx - 1]) ? idsList[idx - 1] : false
  metadata.next = (idsList[idx + 1]) ? idsList[idx + 1] : false
  const subsetIds = getSubset(idsList, targetId)
  const subIndex = subsetIds.indexOf(targetId)
  metadata.prevSibling = (subsetIds[subIndex - 1]) ? subsetIds[subIndex - 1] : false
  metadata.nextSibling = (subsetIds[subIndex + 1]) ? subsetIds[subIndex + 1] : false
  return metadata
}

const identifiers = [ '0', '1', '2', '3', '0.0.0', '0.0.1', '0.0', '1.0' ]

const result = extractMetadata(identifiers, '1')
console.log(result)

Answer 6

const _ = require('lodash')

function comparePaths (path1, path2) {
  const path1Arr = path1.split('.')
  const path2Arr = path2.split('.')
  const maxLength = Math.max(path1Arr.length, path2Arr.length)
  let index = 0
  while (index < maxLength) {
    if (!path1Arr[index] || +path1Arr[index] < +path2Arr[index]) {
      return -1
    }
    if (!path2Arr[index] || +path1Arr[index] > +path2Arr[index]) {
      return 1
    }
    index++
  }
  return 0
}

function getSubset (idsArray, idValue) {
  return _.filter(idsArray, function (_id) {
    const _idArr = _id.split('.')
    const idArr = idValue.split('.')
    const _choppedId = _.take(_idArr, _idArr.length - 1).join('.')
    const choppedId = _.take(idArr, idArr.length - 1).join('.')
    if (_choppedId === choppedId) return true
    return false
  })
}

function extractMetadata (idsList, targetId) {
  idsList = idsList.sort(comparePaths)
  const idx = idsList.indexOf(targetId)
  const metadata = {}
  metadata.prev = (idsList[idx - 1]) ? idsList[idx - 1] : false
  metadata.next = (idsList[idx + 1]) ? idsList[idx + 1] : false
  const subsetIds = getSubset(idsList, targetId)
  const subIndex = subsetIds.indexOf(targetId)
  metadata.prevSibling = (subsetIds[subIndex - 1]) ? subsetIds[subIndex - 1] : false
  metadata.nextSibling = (subsetIds[subIndex + 1]) ? subsetIds[subIndex + 1] : false
  return metadata
}

const identifiers = [ '0', '1', '2', '3', '0.0.0', '0.0.1', '0.0', '1.0' ]

const result = extractMetadata(identifiers, '1')
console.log(result)

Answer 7

Answer №4

One potential solution is to adjust the implementation of nextNode in a similar manner, reusing most of the function but modifying how the iterator behaves.

function nextItem(list, element, axisLock) {
  var pointer = list.indexOf(element) + 1;

  if (axisLock) {    
    while(   ~pointer 
          && !( element.split('.').length === 1 && list[pointer].split('.').length === 1) 
          && !( element.split('.').length === list[pointer].split('.').length && element.split('.')[0] === list[pointer].split('.')[0] ) )
      pointer++;
    return ~pointer ? list[pointer] : false;
  } else return list[pointer] || false;
}

Answer 8

One potential solution is to adjust the implementation of nextNode in a similar manner, reusing most of the function but modifying how the iterator behaves.

function nextItem(list, element, axisLock) {
  var pointer = list.indexOf(element) + 1;

  if (axisLock) {    
    while(   ~pointer 
          && !( element.split('.').length === 1 && list[pointer].split('.').length === 1) 
          && !( element.split('.').length === list[pointer].split('.').length && element.split('.')[0] === list[pointer].split('.')[0] ) )
      pointer++;
    return ~pointer ? list[pointer] : false;
  } else return list[pointer] || false;
}

Exploring numerical characters within a sequence of characters

Answer №1

Answer №2

Answer №3

Answer №4

Similar questions

Is there a way to incorporate a JavaScript variable into an error message while maintaining a single font ID tag?

Vue Charts.js failing to render charts post data retrieval

Sorting a multidimensional array B in PHP based on the values order in a one-dimensional array A

Top method for adjusting a multi-dimensional array in PHP

Retrieving JSON data using Jquery (undefined)

What could be causing NPM to generate an HTTP Error 400 when trying to publish a package?

The YouTube-Search NPM module is producing unexpected outcomes

Switch the class between two elements using a link

Inheriting from the AudioWorkletProcessor class and incorporating a pre-existing audioNode within the class

Incorporate a "Back" button following the removal of the navigation bar in a Meteor-Ionic

Differences between the application/xml and text/xml MIME types

A guide to activating an input field based on the value of another input field in AngularJs

Creating a Nuxt3 sitemap for optimal website indexing

When converting to TypeScript, the error 'express.Router() is not defined' may

Access the contents of objects during the creation process

Learn how to dynamically clear and update source data in jQuery autocomplete for enhanced functionality

How to make a section header stay at the top of a wrapper container

Objects within the Prototype in Javascript

In either PHP or JavaScript regex, extract the initial letter and the rest of the string as individual values

Can you explain the slow parameter feature in Mocha?