遍历字符串中的数字

Question

我正在尝试考虑一个函数，该函数接受表示树中节点的字符串十进制整数的平面数组，每个句点表示该树中的层次结构。我正在尝试创建 prevNode 和 nextNode 函数。采用三个参数 ids, id, planeLock。如果节点没有 prev 或 next id 则返回 false。如果 planeLock 是 true 那么它不会转到树中的下一个节点（例如从 1 到 0.1）它将转到该平面中的下一个节点（例如. 从 1 到 0) 否则知道它是兄弟姐妹，而不是最深的兄弟姐妹 child.

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

prevNode(ids, '0') -> false // 没有上一个节点
prevNode(ids, '1', true) -> 0 // pass true 保持在同一平面上
prevNode(ids, '1') -> 0.1 // 树中的上一个节点
prevNode(ids, '2.0', true) -> false
prevNode(ids, '2.0') -> 2 // 上升一个节点

如何解析这些字符串以获得所需的结果？

Answer 1

var _ = require('lodash')

function compare (n1, n2) {
  var path1 = n1.split('.')
  var path2 = n2.split('.')
  var maxLen = Math.max(path1.length, path2.length)
  var i = 0
  while (i < maxLen) {
    if (!path1[i] || +path1[i] < +path2[i]) {
      return -1
    }
    if (!path2[i] || +path1[i] > +path2[i]) {
      return 1
    }
    i++
  }
  return 0
}

function subset (ids, id) {
  return _.filter(ids, function (_id) {
    var _idArr = _id.split('.')
    var idArr = id.split('.')
    var _idChop = _.take(_idArr, _idArr.length - 1).join('.')
    var idChop = _.take(idArr, idArr.length - 1).join('.')
    if (_idChop === idChop) return true
    return false
  })
}

function metaInfo (ids, id) {
  ids = ids.sort(compare)
  var idIndex = ids.indexOf(id)
  var meta = {}
  meta.prev = (ids[idIndex - 1]) ? ids[idIndex - 1] : false
  meta.next = (ids[idIndex + 1]) ? ids[idIndex + 1] : false
  var idsSubset = subset(ids, id)
  var idSubsetIndex = idsSubset.indexOf(id)
  meta.prevSibling = (idsSubset[idSubsetIndex - 1]) ? idsSubset[idSubsetIndex - 1] : false
  meta.nextSibling = (idsSubset[idSubsetIndex + 1]) ? idsSubset[idSubsetIndex + 1] : false
  return meta
}

var ids = [ '0', '1', '2', '3', '0.0.0', '0.0.1', '0.0', '1.0' ]

var val = metaInfo(ids, '1')
console.log(val)

Answer 2

一种可能的方法：

function getLevel(id) {
  return id.split('.').length;
}

function siblingNode(ids, id, planeLock, goesBack) {
  var index = ids.indexOf(id);
  var level = getLevel(id);

  while (goesBack ? --index >= 0 : ++index < ids.length) {
    var currEl = ids[index];
    var currLevel = getLevel(currEl);
    if (!planeLock || currLevel === level) {
      return currEl;
    }
    if (currLevel < level) {
       break;
    }
  }
  return false; 
}

function prevNode(ids, id, planeLock) {
  return siblingNode(ids, id, planeLock, true);
}

function nextNode(ids, id, planeLock) {
  return siblingNode(ids, id, planeLock, false);
}

Demo。显然，在记忆所有级别（快速但需要内存）和不记忆（反之亦然）之间存在权衡。如果源数组是动态的，并且您必须在插入新项目时寻找位置，我强烈建议使用记忆方法（因为您必须在每次插入时检查 level）。

Answer 3

对整个事情进行排序是一个好方法。但是如果你想用额外的功能来扩展它，最好将你的 id 列表转换成树。

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

这是一种可能性。 nextNode 的实现将遵循相同的方法并重用大部分函数，但改变迭代器的行为方式除外。

function prevNode(collection, item, planeLock) {
  var iterator = collection.indexOf(item) - 1

  if (planeLock) {    
    while(   ~iterator 
          && !( item.split('.').length === 1 && collection[iterator].split('.').length === 1) 
          && !( item.split('.').length === collection[iterator].split('.').length && item.split('.')[0] === collection[iterator].split('.')[0] ) )
      iterator--
    return ~iterator ? collection[iterator] : false
  } else return collection[iterator] || false
}

遍历字符串中的数字

Traverse digits in strings

javascript

arrays

sorting

traversal