From: Joel VanderWerf <vjoel@...>
Date: 2002-06-07T05:09:03+09:00
Subject: Re: Unflatten

Shashank Date wrote:

> I am trying to convert  a flat list (array) of  tokens  into a nested list
> (hence the name UNflatten) using a simple rule:
> Every token which looks like  '(' begins a nested list and the corresponding
> ')' token ends it ... in a recursive fashion.
> e.g:
> ["a", "(","b", ")"]                 ==> ["a",[ "b" ]]
> [ "(", "a", "(","b", ")", ")"]    ==> [["a",["b"]]]
> 
> Of course, I also want a function (reflatten) which traverses the nested
> list to generate the original back.

Coincidentally, I wrote an inverse for flatten yesterday. (Well,
actually only a right inverse since flatten is not injective.) What you
are doing isn't precisely an inverse of Array#flatten, though, which I
guess is why you have reflatten. So this may not be useful to you.

Anyway, it's called Enumerable#nest. You give it a proc that calculates
the depth of each item, and it returns a nesting of arrays in which each
item has the desired depth. I'm using it to parse strings with
Python-like indentation syntax, but it isn't limited to strings. It's
probably not going to help you because, in your case, you can't
calculate the depth from each object by itself--you have to know the
paren count.

Any suggestions appreciated...

--------------------------
module Enumerable
  def nest(&compare)
    ary = to_a
    i = 0
    # wrap into Array::Iterator?
    items_left  = proc { i < ary.size }
    get_cur     = proc { ary[i] }
    go_next     = proc { i += 1 }
    Enumerable.nest items_left, get_cur, go_next, compare
  end

  def Enumerable.nest items_left, get_cur, go_next, compare
    # should handle compare.arity == 2 like a <=> proc
    result = []; item = depth = nil
    while items_left[]
      item = get_cur[]
      depth = compare[item]
      base_depth ||= depth
        
      if depth < base_depth
        break
      elsif depth > base_depth
        result << nest(items_left, get_cur, go_next, compare)
      else
        result << item; go_next[]
      end
    end
    return result
  end
end

str = <<END
a
 aa
 ab
  aba
  abb
   abba
    abbaa
   abbb
 ac
 ad
  ada
   adaa
  adb
b
 ba
 bb
c
 ca
END

lines = str.split "\n"
nested = lines.nest { |line| line.scan(/^\s*/)[0].length }
p nested
flat = nested.flatten
p flat
p flat == lines