Print all paths to leafs of a tree-like list array and concatenate corresponding values in the path with special conditions

Question

I have an array consisting of keys and values where keys are a tree like numbered list. This is the input array:

inputArr =  [
             ["1", "p"], 
             ["1.1", "q"], 
             ["1.2", "a"], 
             ["1.2", "b"], 
             ["1.2", "c"], 
             ["1.2.1", "d"], 
             ["1.2.2", "4"], 
             ["1.2.2.1", "5"], 
             ["1.3", "6"], 
             ["1.4x", "7"], 
             ["2", "8"], 
             ["2.1", "9"], 
             ["2.2", "10"], 
             ["2.2.1x", "11"],
             ["2.2.2", "12"],
             ["3", "13"], 
             ["4", "14"]
            ];

Expected output:

outputArr = [
             ["1.1", "p,q"], 
             ["1.2.1", "p,a,b,c,d"], 
             ["1.2.2.1", "p,a,b,c,4,5"], 
             ["1.3", "p,6"], 
             ["1.4x", "7"], // not "p,7", because key has a tailing 'x' 
             ["2.1", "8,9"], 
             ["2.2.1x", "11"], //not "8,10,11", because key has a tailing 'x'
             ["2.2.2", "8,10,12"],
             ["3", "13"], 
             ["4", "14"]
            ];

---

Let me explain the first output: ["1.1", "p,q"] :

It is the first leaf. It's path is: "1"->"1.1". The values in the path are: "p" , "q".

---

Let me explain the second output: ["1.2.1", "p,a,b,c,d"] :

It is the second leaf. Here, I have treated duplicate keys as extension of one.["1.2", "a"],["1.2", "b"],["1.2", "c"] means ["1.2", "abc"] .

So, the path of the second leaf is : "1"->("1.2" + "1.2" + "1.2")->"1.2.1".

---

Let me explain the fifth output:["1.4x", "7"] :

Please note: it is not "p,7". Since the key has a tailing 'x', this leaf should not take 'p' in the output.

Same logic is applicable for seventh output.

---

What I have done so far:

Here is my attempts to this issue so far.

This is a piece of code I am using right now:

//////////////////////////////////////

function getTreeBranch(arr, c, p) {

    var outputArr = [],
    s = [],
    curr,
    next;

    for (var i = 0; i < arr.length - 1; i++) {
        curr = arr[i];
        next = arr[i + 1];
        currLevel = curr[c].split(".").length
        nextLevel = next[c].split(".").length

            if (currLevel == 1) {
                s = []
                s.push(curr[p]);
                if (currLevel == nextLevel)
                    outputArr.push([curr[c], s.join(',')]);
            } else if (currLevel < nextLevel) {
                s.push(curr[p]);
            } else if (currLevel == nextLevel) {
                s.push(curr[p]);
                outputArr.push([curr[c], s.join(',')]);
                s.pop();
            } else if (currLevel > nextLevel) {
                outputArr.push([curr[c], s.join(',') + ',' +curr[p]]);
                for (j = 0; j < (currLevel - nextLevel); j++) {
                    s.pop()
                }
            }
    }

    var lastItem = arr[arr.length - 1];
    if ((lastItem[c].length) == 1) {
        s = []
    }
    s.push(lastItem[p]);
    outputArr.push([lastItem[c], s.join(',')]);

    return outputArr

}

But this function can't handle duplicate keys and tailing 'x's.

---

Can you suggest any correction or update, any alternative piece of code, any algorithm or hint about the problem? Any help will be much appreciated.

Answer 1

Filter the leaves by checking that there are no other entries which have them as the parent, making a special case for the entries with an 'x'.

Then, assuming the inputArr is in the correct order, find all parents and include them (again, with a special case where there is the 'x').

const inputArr = [["1","p"],["1.1","q"],["1.2","a"],["1.2","b"],["1.2","c"],["1.2.1","d"],["1.2.2","4"],["1.2.2.1","5"],["1.3","6"],["1.4x", "7"],["1.4x", "s"],["1.4x", "g"],["2","8"],["2.1","9"],["2.2","10"],["2.2.1x","11"],["2.2.2","12"],["3","13"],["4","14"]]

const outputArr = [...new Set(inputArr.map(([k])=>k))]
  .map(k=>[k,inputArr.filter(([i])=>i===k).map(([k,v])=>v)]).filter(([a])=>
    a.endsWith('x') || !inputArr.some(([b])=>b!==a && b.startsWith(a)
)).map((([a,b])=>[a,(a.endsWith('x')?b:
  inputArr.filter(([c])=>a.startsWith(c)).map(([c,d])=>d)).join(',')
]))

console.log(outputArr)

Answer 2

Here is the general process for reducing your sections:

1. You will need to first filter the sections by keeping ones that:
   • end with an "x" or
   • begins with another section
2. Now you can map the filtered section to a key-value pair
   • Key:
     • Replace any trailing "x" for a key
   • Value:
     • If the reference ID ends with an "x", use the value for that section
     • Else, filter sections by their ID that precede the reference ID
     • Join the values by a comma

Full example

const inputArr = [
  ["1", "p"], ["1.1", "q"], ["1.2", "a"], ["1.2", "b"], ["1.2", "c"], ["1.2.1", "d"],
  ["1.2.2", "4"], ["1.2.2.1", "5"], ["1.3", "6"], ["1.4x", "7"], ["2", "8"],
  ["2.1", "9"], ["2.2", "10"], ["2.2.1x", "11"], ["2.2.2", "12"], ["3", "13"],
  ["4", "14"]
];

const rollupSections = (sections, specialSuffix = '', stripSuffix = false) =>
  sections
    .filter(([id]) =>
      id.endsWith(specialSuffix) ||
      !sections.some(([subId]) => subId !== id && subId.startsWith(id)))
    .map((([id, value]) => [
      // Key
      specialSuffix && stripSuffix
       ? id.replace(new RegExp(`${specialSuffix}$`), '')
       : id,
      // Value
      id.endsWith(specialSuffix)
        ? [value].join(',')
        : sections
          .filter(([subId]) => id.startsWith(subId))
          .map(([, subValue]) => subValue)
          .join(',')
    ]));

const outputArr = rollupSections(inputArr, 'x', true);

outputArr.forEach(pair => console.log(JSON.stringify(pair)));

.as-console-wrapper { top: 0; max-height: 100% !important; }

Here is a functional example that shows how the output of one function can be used as the input of another.

const inputArr = [
  ["1", "p"], ["1.1", "q"], ["1.2", "a"], ["1.2", "b"], ["1.2", "c"], ["1.2.1", "d"],
  ["1.2.2", "4"], ["1.2.2.1", "5"], ["1.3", "6"], ["1.4x", "7"], ["2", "8"],
  ["2.1", "9"], ["2.2", "10"], ["2.2.1x", "11"], ["2.2.2", "12"], ["3", "13"],
  ["4", "14"]
];

const endsWithSpecialSuffix = ([id], specialSuffix) =>
  id.endsWith(specialSuffix);

const isChildOf = (id, parentId) => id.startsWith(parentId);

const hasParentSection = ([id], sections) =>
  sections.some(([subId]) => subId !== id && isChildOf(subId, id));

const isChildSection = (section, sections, specialSuffix) =>
  endsWithSpecialSuffix(section, specialSuffix) ||
  !hasParentSection(section, sections)

const childSections = (sections, specialSuffix) =>
  sections.filter((section) => isChildSection(section, sections, specialSuffix));

const formatKey = ([id], specialSuffix, stripSuffix) =>
  specialSuffix && stripSuffix
     ? id.replace(new RegExp(`${specialSuffix}$`), '')
     : id;

const hasSuffix = (id, specialSuffix) => id.endsWith(specialSuffix);

const formatSubValues = (id, sections) =>
  sections
    .filter(([subId]) => id.startsWith(subId))
    .map(([, subValue]) => subValue)
    .join(',');

const formatValue = ([id, value], sections, specialSuffix) =>
  hasSuffix(id, specialSuffix)
    ? [value].join(',')
    : formatSubValues(id, sections)

const rollupSections = (sections, specialSuffix = '', stripSuffix = false) =>
  childSections(sections, specialSuffix).map(((section) => [
    formatKey(section, specialSuffix, stripSuffix),
    formatValue(section, sections, specialSuffix)
  ]))

const outputArr = rollupSections(inputArr, 'x', true);

outputArr.forEach(pair => console.log(JSON.stringify(pair)));

.as-console-wrapper { top: 0; max-height: 100% !important; }

Answer 3

Prevent values with 'x'` as suffix of being splitted.

const
    getPathes = ({ value = [], sub }) => sub
        ? Object
            .entries(sub)
            .flatMap(([k, v]) => getPathes(v).map(([p, s]) => [
                k + (p && '.') + p, 
                [...value, ...s]
            ]))
        : [['', value]],
    input = [["1", "p"], ["1.1", "q"], ["1.2", "a"], ["1.2", "b"], ["1.2", "c"], ["1.2.1", "d"], ["1.2.2", "4"], ["1.2.2.1", "5"], ["1.3", "6"], ["1.4x", "7"], ["2", "8"], ["2.1", "9"], ["2.2", "10"], ["2.2.1x", "11"], ["2.2.2", "12"], ["3", "13"], ["4", "14"]],
    tree = input.reduce((t, [path, value]) => {
        const
            keys = path.endsWith('x')
                ? [path]
                : path.split('.'),
            target = keys.reduce((o, k) => (o.sub ??= {})[k] ??= {}, t);
        (target.value ??= []).push(value);
        return t;
    }, {}),
    result = getPathes(tree);

result.forEach(([k, v]) => console.log(k, ...v));
console.log(tree);

.as-console-wrapper { max-height: 100% !important; top: 0; }