From: Christoph Rippel <crippel@...>
Date: 2001-02-28T02:46:15+09:00
Subject: [ruby-talk:11704] Re: Array bugs?

> From: ts [mailto:decoux@moulon.inra.fr]
[...]
>  A little patch, I've forgotten to re-define Array#<=>

Before anything you probably should know (easy to
change of course) that my orginal "unsigned long long int" 
encoding scheme is flawed ...

---------------------
The orginal Array (normal Hashing is
virtually the same)

def  include_pair a,n
	@bag <<  (a+ (b << Fixnum::Maxlog)) 
end	


$ time ruby Untangle.rb
true
false
[3]
[1, 2, 3, [...], [...]]
[1, 2, [...], [1, 2, 3, [...], [...]]]
true
true
false

real    0m29.272s
user    0m24.755s
sys     0m0.500s


---------------------
Your version (note you have Thread
protection)  
$ time ruby b.rb
true
false
[3]
[1, 2, 3, [...], [...]]
[1, 2, [...], [1, 2, 3, [...], [...]]]
true
true
false

real    0m31.255s
user    0m30.934s
sys     0m0.090s


---------------------
New Id-Pair encoding scheme
$ time ruby UntangleNew.rb
true
false
[3]
[1, 2, 3, [...], [...]]
[1, 2, [...], [1, 2, 3, [...], [...]]]
true
true
false

real    0m2.033s
user    0m1.692s
sys     0m0.240s

---------------------

class Object 
##########################
# In general just ignore the bag
##########################
def  untangled_equal? (other, bag)
	  self == other
end

class IdBag
def initialize
	@bag = {}
end
def  sym_pair_include a, b
	@bag[SymIdPair.new a,b] =1
end	
def sym_pair_include? a,b
	@bag.key? (SymIdPair.new a,b)
end	

private 
class SymIdPair
def initialize l,r
	if l > r
		@l = l; @r = r
	else
		@l = r; @r = l
	end
#I believe that a scheme
# based on 
# if l > r
#	@l = l+ 11*r; @r = r
# else
#	@l = r+ 11*r; @r = l
# end
# in VALUE -i.e. 
# ``unsigned long int'' arithmetic
# is probably more robust in
# certain situations (not measurable
# slower in general)
end		
def hash;	@l end
def eql?(other)
	@r.eql?  (other.r)
end	
protected 
	attr_reader :r
end
end                        
end

##########################
class Array
def  untangled_equal?  (other,id_bag)
	return false unless other.kind_of? Array
	return false unless length == other.length
	id_bag.sym_pair_include  id,  other.id 
	return true if  id == other.id
	for i in 0...length do
		next if id_bag.sym_pair_include? self[i].id, other[i].id
		if self[i].untangled_equal? (other[i], id_bag) 
			next
		else
			return false
		end
	end	
	return true
end
def  == (other)
	untangled_equal? (other, IdBag.new )
end
end



Christoph