Split a recursive nested array in two

Question

I have an array like this:
["this", "is", ["a", ["nested", "array", "I"], "want", "to"], "split"]

And I would like a function to obtain two arrays like that:
["this", "is", ["a", ["nested", "ar"]]] [[["ray", "I"], "want", "to"], "split"]

Optimally, I would like the parameters to this function to be the initial array, the targeted string and an offset. So here, it would have been recurSplit(foo, foo[2][1][1], 2)
But I am open to any other solutions.

I made this working solution, but I am not satisfied as my hasCut variable needs to be outside the function. I'd like to know if I am on the left (or right) side of the target inside the function.

let hasCut = false
function recurSplit(element, target, offset) {
    let left, right
    if (typeof element == 'string') {
        if (element == target) {
            left = element.slice(0, offset)
            right = element.slice(offset)
            hasCut = true
        } else {
            left = hasCut ? false : element
            right = hasCut ? element : false
        }
    } else {
        left = []
        right = []
        for (const child of element) {
            const res = recurSplit(child, target, offset)
            if (res[0])
                left.push(res[0])
            if (res[1])
                right.push(res[1])
        }
    }
    return [left, right]
}

• Yes, I could make another function that checks it recursively, but that'd be hell of useless processing.
• Yes, I could make this function anonymous and encapsulate it inside another one, but that's very JS specific.

Isn't there any nicer ways ?
Thank you !

Answer 1

In this code, h is a 'holder' for the value v. This allows the value v to be altered at deeper levels of recursion, such that the alteration is visible at shallower levels of recursion. This value v indicates whether we should include items in the output or not.

As soon as the matching string is found, the value of v is flipped (achieved by h.v^=1). This allows us to start including items and then flip over to no longer including any more items, and vice versa.

The function f recursively visits all elements of all arrays, and uses flatMap to accept or reject elements returned by the mapping function depending on whether an empty or non-empty array is returned.

We call f twice, once to get everything prior to the split, and again to get everything after the split.

let foo = ["this","is",[],["a",["deep",[]],["nested","array","I",[]],"want",[],"to"],"split"]

function f(x,m,p,h={v:0}) {
  return (x===m) ? [x.substring(...(h.v^=1)?[0,p]:[p])] : Array.isArray(x) ?
    [x.flatMap(i=>f(i,m,p,h))].filter(i=>!h.v||i.length) : (h.v?[]:[x])
}

function recurSplit(...g) { return [f(...g), f(...g,{v:1})].flat() }

let [x,y] = recurSplit(foo, foo[3][2][1], 2);

[foo,x,y].forEach(i=>console.log(JSON.stringify(i)))

Answer 2

Instead of passing the inner element directly you can pass an array of indexes pointing to the element and then recurse over this array, slicing from the inside out and returning a tuple which is spread into each level on the way out. The snippet destructures the passed path array ([i, ...path]) and then checks if there are any remaining indexes in the trailing ...rest array. If there are recurse otherwise split the word and return the parts as a tuple.

const input = ["this", "is", ["a", ["nested", "array", "I"], "want", "to"], "split"]

function recursiveSplit(array, [i, ...path], offset) {
  const [left, right] = path.length
    ? recursiveSplit(array[i], path, offset)
    : [array[i].slice(0, offset), array[i].slice(offset)];

  return [
    [...array.slice(0, i), left],
    [right, ...array.slice(i + 1)],
  ];
}

const [head, tail] = recursiveSplit(input, [2, 1, 1], 2);

console.log('head: ', JSON.stringify(head));
console.log('tail: ', JSON.stringify(tail));

If you need to pass the target as a string you can pass the hasCut up from the bottom of the recursion, if hasCut is true break the loop and start back up, otherwise return the intact element and keep searching.

const input = ["this", "is", ["a", ['deep'], ["nested", "array", "I"], "want", "to"], "split"];

function recursiveSplit(array, target, offset) {
  let left, right, index, hasCut = false;

  for (const [i, element] of array.entries()) {
    index = i;

    if (element === target) {
      left = element.slice(0, offset);
      right = element.slice(offset);
      hasCut = true;
      break;
    }

    if (Array.isArray(element)) {
      ({ hasCut, left, right } = recursiveSplit(element, target, offset));
      if (hasCut) break;
    }
  }

  return {
    hasCut,
    left: hasCut ? [...array.slice(0, index), left] : array,
    right: hasCut ? [right, ...array.slice(index + 1)] : undefined
  }
}

const { left, right } = recursiveSplit(input, 'array', 2);

console.log('left: ', JSON.stringify(left));
console.log('right: ', JSON.stringify(right));

Or using the fairly common pattern of passing a context or state argument down as mentioned by @TrevorDixon in the comments

const input = ["this", "is", ["a", ["deep", []], ["nested", "array", "I"], "want", "to"], "split"];

function recursiveSplit(array, target, offset, status = { cut: false }) {
  let left, right, index;

  for (const [i, element] of array.entries()) {
    index = i;

    if (element === target) {
      left = element.slice(0, offset);
      right = element.slice(offset);
      status.cut = true;
      break;
    }

    if (Array.isArray(element)) {
      [left, right] = recursiveSplit(element, target, offset, status);
      if (status.cut) break;
    }
  }

  return status.cut
    ? [[...array.slice(0, index), left], [right, ...array.slice(index + 1)]]
    : [array];
}

const [left, right] = recursiveSplit(input, 'array', 2);

console.log('left: ', JSON.stringify(left));
console.log('right: ', JSON.stringify(right));

Answer 3

Oh, fun problem, here is a version that can handle multiple occurrences of the given string.

It pushes each element into a new array until a split occurs and that array is added to the final result and replaced by a new array. That way, you don't need to keep track if a split already occurred.

const nested = ["this", ["endstart"], [], ["is"], "endstart", ["a", ["nested", "endstart", "endstart", "I"], "want", "to"], "split"]

function splitAtWord([el, ...rest], word, splitAt, result = [], current = []){
  if (!el) {
    return [...result, current] // push current to result
  }
  if (Array.isArray(el)) {
    const splits = splitAtWord(el, word, splitAt).map((e, i) => i === 0 ? [...current, e] : [e])
    current = splits.pop() // keep working with end of nested array
    result.push(...splits) // done with all others (if any after pop)
    return splitAtWord(rest, word, splitAt, result, current)
  }
  if (el !== word) {
    return splitAtWord(rest, word, splitAt, result, [...current, el]) // just copy to current
  }
  const left = word.substring(0, splitAt)
  const right = word.substring(splitAt)
  return splitAtWord(rest, word, splitAt, [...result, [...current, left]], [right]) // finish left side, keep working with right
}

console.log(JSON.stringify(splitAtWord(nested, 'endstart', 3)))

But if you know the specific index you want to split at, it is much easier to use that:

let foo = ["this", "is", ["a", ["nested", "array", "I"], "want", "to"], "split"]

function splitAtIndex(arr, [ix, ...ixs], wordIx){
  const el = arr[ix];
  const [l,r] = Array.isArray(el) ?
    splitAtIndex(el, ixs, wordIx) : 
    [el.substring(0, wordIx), el.substring(wordIx)]
  return [[...arr.slice(0, ix), l], [r, ...arr.slice(ix+1)]]
}

console.log(JSON.stringify(splitAtIndex(foo, [2,1,1],2)))