```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.

```