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?

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`? — T.J. Crowder, Feb 06 '13 at 07:58
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. — elclanrs, Feb 06 '13 at 08:00
So why not `one.foo.two`? Are you supposed to scan the whole list to see if there's another `foo`? — Ja͢ck, Feb 06 '13 at 08:01
because `foo` is a key of `one`. I determine this because `foo` is not repeated. Only keys that are repeated enclose other keys. — elclanrs, Feb 06 '13 at 08:02
Perhaps you could share the background ... how did you get this data in the first place? — Ja͢ck, Feb 06 '13 at 08:03
@Jack: This is related [this other question from yesterday](http://stackoverflow.com/questions/14701879/negative-lookahead-regex). It's for a basic templating system. This keys are extracted from some text where I need to determine the start and end points to replace with the property that matches in an object literal. — elclanrs, Feb 06 '13 at 08:06
It was getting too complicated with regex so I decided to take a different approach. It seems doable but like I said I'm stuck... — elclanrs, Feb 06 '13 at 08:07
You are correct to avoid the regex, if your data is in an array. — Ray Toal, Feb 06 '13 at 08:18
I see, I've also answered that question :) my current answer should fit the bill, but let me see if there's something more optimal, now knowing where it came from :) — Ja͢ck, Feb 06 '13 at 08:26
I was just posting a graphic for more clarification. Yeah lol I tried with regex implementing the solution from yesterday but it got way too complicated... — elclanrs, Feb 06 '13 at 08:34
@elclanrs: The stack parser would be much easier if we knew which of the elements were an open/close pair. Can't you make the array include that information? — Bergi, Feb 06 '13 at 08:34
@Bergi, the start and end elements are those that are duplicated, a template could look like this http://pastebin.com/jwhgbMUL. I'm already assuming there are no duplicate keys since this is for a very simple system. — elclanrs, Feb 06 '13 at 08:39
@elclanrs: Yes, I remember the syntax from your previous question. What I meant is that the parser would be easier to write if you included the `@`-sign in the array to indicate "opening tags" so you don't need to search for those duplicates. — Bergi, Feb 06 '13 at 08:44
Oh, I see what you mean, I'll try that. Jack's solution does the work for now. Been struggling to parse this thing but things start to become more clear now. — elclanrs, Feb 06 '13 at 08:48

score 2 · Accepted Answer · answered Feb 06 '13 at 08:24

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

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. — elclanrs, Feb 06 '13 at 08:36

Ray Toal · Answer 2 · 2013-02-06T08:14:57.280

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.

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... — elclanrs, Feb 06 '13 at 08:19
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! — Ray Toal, Feb 06 '13 at 08:27

score 1 · Answer 3 · answered Feb 06 '13 at 10:39

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

Array recursion start end points

3 Answers3