2007/12/3, Voroztsov Artem <artem.voroztsov / gmail.com>:
>
> Yes
> 1) my version does not support argument
> 2) self-included array kills it
>
> But both can be solved in non-quadratic time.
> We can get rid of the second difference in O(L log L).
>
> I posted fixed version which works correct with Ryan's sample
>
> > - Charlie
> >
> >

I tried to add missed functionality:


  class Array
    def flatten2(level = nil)
      return flatten3(level) if level
      res = []
      x = self.dup
      met = {}
      while !x.empty?
        a = x.pop
        if a.is_a?(Array)
          raise "tried to flatten recursive array" if met[a.object_id]
          met[a.object_id] = 1
          a.each{|i| x << i}
        else
          res << a
        end
      end
      res.reverse
    end

    def flatten3(level)
      res = []
      x = [[self.dup, level+1]]
      met = {}
      while !x.empty?
        a,level = x.pop
        if a.is_a?(Array) && level > 0
          raise "tried to flatten recursive array" if met[a.object_id]
          met[a.object_id] = 1
          a.each{|i| x << [i,level-1]}
        else
          res << a
        end
      end
      res.reverse
    end
  end

  a = [:a, [:b, [:c], :d], :e]
  puts a.flatten2.inspect
  a = [:a, [:b, [:c], :d], :e, [[[[10]]]], [1,[2,[3,4]]], [5, 6], [[[7],8],9]]
  7.times {|i| puts a.flatten2(i).inspect}

  a << a
  puts a.flatten2.inspect

####

The posted test outputs:
      user     system      total        real
original flatten 20.515000   0.000000  20.515000 ( 20.531000)
self-made flatten  0.110000   0.000000   0.110000 (  0.110000)
true
      user     system      total        real
original flatten 20.265000   0.000000  20.265000 ( 20.328000)
self-made flatten  0.141000   0.000000   0.141000 (  0.141000)
true

So we these features give us 2-times growth in time (from  0.078 to 0.14)

Of cause, it needs more testing.

PS:
In the first implementation i use "met[a]" instead of
"met[a.object_id]" (it was not good idea) and got one more problem:

ftalen2.rb:10:in `hash': stack level too deep (SystemStackError)
	from ftalen2.rb:10:in `[]'
	from ftalen2.rb:10:in `flatten2'
	from ftalen2.rb:48

That is recursive array can't be used as key in Hash:  Array#hash get
"stack level too deep". I guess it is known issue. But exception
message should be more clear: "recursive array can't be used as key".

And in fact this problem can be solved too in no more than log(N) time factor,
I mean Array#== and Array#hash can work for recursive arrays.