Array recursion start end points

Question

I have an array like this:

["one", "foo", "two", "baz", "two", "one", "three", "lulz", "wtf", "three"]
 1 2 2 1 3 3

Each string is a key to access an object literal. What I want to do is prepend the full path to children keys delimited by main keys in this case one, two, and three. This is the expected result:

[
 'one', 'one.foo', 'one.two', 'one.two.baz', 'one.two', 'one',
 'three', 'three.lulz', 'three.wtf', 'three'
]

I've been trying for past few hours with loops and extracting the duplicated items first and then trying to slice the array by a given start and end points. Then I tried with regex, just to see if it was possible but JS doesn't handle recursion in regular expressions, and it got very complicated and probably unnecesary. I'm at that point where I got frustrated and nothing is working. I've no clue where to go now. I'm stuck.

Edit: I've been trying the above for a while because it seemed simpler but ideally all I want to extract is the chain of keys without the closing "tags".

[
 'one', 'one.foo', 'one.two', 'one.two.baz',
 'three', 'three.lulz', 'three.wtf'
]

Can somebody enlighten me here?

• T.J. Crowder: How do you know when to start again? E.g., what's special about the second 'two' that you go from one.two.baz to one.two?
• elclanrs: The keys are unique, the second two closes the first one so two is at level one` thus one.two for both opening and closing tags. But ideally I don't need the duplicated one, I'll edit my answer.
• Ja͢ck: So why not one.foo.two? Are you supposed to scan the whole list to see if there's another foo?
• Ovilia: I didn't get it... What defines the main keys?
• elclanrs: because foo is a key of one. I determine this because foo is not repeated. Only keys that are repeated enclose other keys.

Answer 1

Without recursion you can solve it like this; it keeps a common prefix and at every iteration it scans both left and right to find an identical item.

If there's an identical item to the left, reduce the prefix (before emit); if there's an item to the right, increase the prefix (after emit).

var a = ["one", "foo", "two", "baz", "two", "one", "three", "lulz", "wtf", "three"];
var prefix = '',
 keys = [];
for (var i = 0, len = a.length; i < len; ++i) {
 var left = a.indexOf(a[i]),
 right = a.indexOf(a[i], i + 1);
 if (left >= 0 && left < i) {
 prefix = prefix.substr(0, prefix.lastIndexOf(a[i]));
 }
 keys.push(prefix + a[i]);
 if (right !== -1) {
 prefix = prefix + a[i] + '.';
 }
}
console.log(keys);

Demo

• elclanrs: Oh man this is perfect. Thank again. This actually looks pretty similar to what I was trying to implement, with start end points first extracting the duplicates. But I fogot about lastIndexOf genius! That was driving crazy cuz I was reversing the array to find the end point from the other side.

Answer 2

You can avoid recursion here. Just walk the array. Compare the current array element to the string you are accumulating. When you see a new "main" element for the first time, append it to the string you are building. When you see a closing instance of a main element that matches the suffix of the string you have so far, pop it. Build up the resulting array as you walk.

For example, given

["one", "foo", "two", "baz", "two", "one", "three", "lulz", "wtf", "three"]

You first see "one" so emit that

result = ["one"]
working = "one"

Then you see "foo" so emit, but keep only "one" as the string to compare against.

result = ["one", "one.foo"]
working = "one"

Next you have "two" so emit and keep "one.two".

result = ["one", "one.foo", "one.two"]
working = "one.two"

Next is "baz" emit but do not keep.

result = ["one", "one.foo", "one.two", "one.two.baz"]
working = "one.two"

Next is a "two" so you can pop!

result = ["one", "one.foo", "one.two", "one.two.baz"]
working = "one"

Next, a "one" so pop again!

result = ["one", "one.foo", "one.two", "one.two.baz"]
working = ""

Now a three, which is a main tag, so emit and keep:

result = ["one", "one.foo", "one.two", "one.two.baz", "three"]
working = "three"

Straightforward! I think you can take it from here. No fancy recursion is needed. Of course you may have to check for errors in nesting and balancing.

• elclanrs: I see the idea here but how do you determine "Next you have "two" so emit and keep "one.two" if I don't know that "foo" is not a main key yet? Maybe I'm just too tired...
• Ray Toal: Oh! You are saying that you don't know which keys are main keys UNTIL you see a duplicate! I misunderstood. I thought the main keys were known up front. No wonder it seemed to easy. You can always backtrack and pop from the result array as you go.... Probably quadratic in the worst case, though!

Answer 3

Here is a recursive solution. The function takes the current prefix and the array it is working with. It returns an empty array of keys if the array is empty, otherwise it builds keys with the current prefix by shifting items off the front of the array. If during that process it reaches the end of the array, or an element which occurs later in the array, it stops building new keys and recurses.

The recursion works by splitting the array on the next occurrence of the element found to repeat. The current key is used as a prefix along with the left sub array for one call, and a blank prefix is used with the right sub array for the other. The function returns the keys it found plus the keys found by the two recursive calls.

Not the most efficient solution, the iterative one is better on that front, but I figured I'd post the recursive solution for anyone interested.

function foldKeys(prefix, arr) {
 var keys = [],
 key,
 i;
 if (arr.length == 0) {
 return keys;
 }
 do {
 next = arr.shift();
 key = prefix + (prefix == '' ? next : ('.' + next));
 keys.push(key);
 } while (arr.length && (i = arr.indexOf(next)) === -1);
 return keys
 .concat(foldKeys(key, arr.slice(0, i)))
 .concat(foldKeys('', arr.slice(i + 1)));
}
var arr = ["one", "foo", "two", "baz", "two", "one", "three", "lulz", "wtf", "three"];
var keys = foldKeys('', arr);
console.log(keys.toString());