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 !

Add an optional context or state parameter with default value {hasCut: false} and pass it with the recursive calls, and change that object's value instead of the variable outside the function. — Trevor Dixon
– Trevor Dixon, Commented Feb 12, 2023 at 1:45
Oh, good idea to use an object instead of a boolean as parameter ! — Florent Descroix
– Florent Descroix, Commented Feb 12, 2023 at 9:18

pilchard · Accepted Answer · 2023-02-12 12:13:20Z

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));

Moritz Ringler · Accepted Answer · 2023-02-12 10:48:36Z

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)))

Andrew Parks · Accepted Answer · 2023-02-12 15:24:53Z

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)))

edited Feb 12, 2023 at 15:24

answered Feb 12, 2023 at 1:49

Andrew Parks

8,1672 gold badges21 silver badges35 bronze badges

3 Comments

pilchard Over a year ago

seems to break if there are any complete array elements before the array containing the target. ie on the sample array ["this", "is", ["a", ['deep'], ["nested", "array", "I"], "want", "to"], "split"] the result is ["this","is",["a",["deep"],["nested","ar"]]] and [[[],["ray","I"],"want","to"],"split"] with an empty array introduced at the start of the right split.

Florent Descroix Over a year ago

Thankfully this is not too much JS specific ah ah ! Thank anyway for this crazy four lines solution... I'd need some hour to understand it though ^^

Andrew Parks Over a year ago

I've fixed the issue with empty arrays, I think

Collectives™ on Stack Overflow

Split a recursive nested array in two

3 Answers 3

Comments

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related