Map nested array values to Map with functionality to set Map values by array index which will be reflected in nested array by reference

Question

Given the requirement to create a nested array or arbitrary depth, where the basic data structure is

[0, [1, [2, [3 /* , [N, [N+1, [..]]] */]]]]

or

["a", ["b", ["c", ["d" /* , [N, [N+1, [..]]] */]]]]

where arr is an Array instance and and map an Map instance the requirement is to map each depth is mapped to a Map object, where

map.get(2) // 2

or

map.get(2) // "c"

gets the value set at the nested array at index N where N are the linear indexes of the nested array.

In additions, the requirement is to have the ability to execute

m.set(2, "x")

which will result in

["a", ["b", ["x", ["d" /* , [N, [N+1, [..]]] */]]]]

Have been able to create the nested array data structure using Array.prototype.map() and two additional Array.

Am probably missing a simply adjustment which can be made to achieve the expected functionality. The current code only performs the m.get(<index>) procedure.

const treeMap = (tree, props = (!Array.isArray(tree) && typeof tree === "string" 
      ? tree.split` ` 
      : tree), res = [], t = [], m = new Map) => props.map((prop, index) => 
      !res.length // first iteration
      ? res.push(prop, t) && m.set(index, prop) // push first value
      : index < props.length-1 // check index
        ? t.push(prop, t = []) && m.set(index, prop) // `.push()` to `t`, re-declare `t` as `[]`
        : t.push(prop) && m.set(index, t[0])) // `.push()` last value `prop` to `t`
    && [res, m] // return `res`


let [arr, map] = treeMap("a b c");

console.log(arr, map);

console.log(map.get(2));

// console.log(treeMap([...Array(3).keys()]));
// [0, [1, [2, [3]]]]

After only two attempts decided to ask for a solution here, instead of simply solving the inquiry for self first. In general, test code several if not hundreds or thousands of times over, before asking a question.

How to achieve the above described requirement?

`.set` is meant to, essentially, set a property of the current map instance. Calling `.set` on a Map should only set the property of that Map, and shouldn't (and can't) mutate an external object, at least in sane code, unless you overwrite `Map.prototype.set`, which is *really weird*. Is the `map` variable *required* to be an actual `Map`, or can you return an object which *simulates* a `Map` while achieving the other requirements? — CertainPerformance, Feb 17 '19 at 01:03
@CertainPerformance A simulation of a `Map` is not restricted. Would initially probably avoid using a `Proxy` to limit the amount of objects needed to achieve the requirement, though using a `Proxy` is not explicitly restricted in the question. The main requirement is being able to set the _nth_ nested array index in linear order by considering the nested array data structure as only a an array of linear indexes `0`-`n` — guest271314, Feb 17 '19 at 01:06
@CertainPerformance The code was originally composed to achieve the requirement for a Code Review question [Execute promise tree in order of declaration](https://codereview.stackexchange.com/questions/211018/execute-promise-tree-in-order-of-declaration) that was eventually posted at SO [Call an array of promises in parallel, but resolve them in order without waiting for other promises to resolve](https://stackoverflow.com/questions/54620494/) with some modifications. Decided to extend the functionality in order to avoid having to traverse a nested data structure to get, set values. — guest271314, Feb 17 '19 at 01:08

CertainPerformance · Answer 1 · 2019-02-17T01:35:10.477

I'd construct a Map internal to the treeMap function, call it mapOfArrs, which maps each index to its associated nested array. For example, with an input of a b c:

mapOfArrs.get(0) // -> ['a', ['b', ['c']]]
mapOfArrs.get(1) // -> ['b', ['c']]
mapOfArrs.get(2) // -> ['c']

Then, you can return a psuedo-Map object which, when called with get(prop), accesses mapOfArrs.get(prop)[0] to get the associated nested value, while set(prop) retrieves the nested array with mapOfArrs.get(prop) and assigns the new value to its 0th index, mapOfArrs.get(prop)[0] = newVal;.

Due to the internal Map, accessing / modifying any of the nested values will have O(1) complexity:

const treeMap = (tree) => {
  const [initialItem, ...restItems] = Array.isArray(tree)
    ? tree
    : tree.split(' ');
  const root = [initialItem];
  const mapOfArrs = new Map()
    .set(0, root);
  // Construct the nested structure, putting the newly created arrays in mapOfArrs too:
  restItems.reduce((a, item, i) => {
      const newArr = [item];
      a.push(newArr);
      // we sliced off the first item for the initial value, so have to increment i by 1:
      mapOfArrs.set(i + 1, newArr);
      return newArr;
    }, root);
  
  const psuedoMap = {
    get(prop) {
      return mapOfArrs.get(prop)[0];
    },
    set(prop, newVal) {
      mapOfArrs.get(prop)[0] = newVal;
      return this;
    }
  };
  return [root, psuedoMap];
};

let [arr, map] = treeMap("a b c");

console.log(arr);
console.log(map.get(0), map.get(1), map.get(2));
map.set(2, "x")
   .set(0, 'zzz');
console.log(arr);
console.log(map.get(0), map.get(1), map.get(2));

(Map.prototype.set does not have side effects, so the external call of, for example, map.set(2, "x") has to go through a custom function, rather than through Map.prototype.set, for the associated array to be mutated as well)

Map nested array values to Map with functionality to set Map values by array index which will be reflected in nested array by reference

1 Answers1