[ruby-talk:11436] Re: Array bugs?

> From: ts [mailto:[e-mail]]
> >>>>> "M" == Mathieu Bouchard <[e-mail]> writes:
> 
> 
> M> def f(x); [x,x]; end
> M> def g(x); f f f f f f f f x; end
> M> (g g g 1) == (g g g 1) #=> true
> 
>  Try this
> 
>    def f(x); [x,x]; end
>    def g(x); f f f f f f f f x; end
>    p (g g g 1)
> 

Object (in)equality is an extremely subtle issue (un-decidable
for any half way expressive semantics, never mind thread safety,
persistence etc. ) and Ruby's untyped functions don't make 
things easier - on the other hand Matju's example is perfectly
legitimate (non abusive) and any Array (in)equality algorithm 
should be able to handle it (very few objects are created.)

I came up with following simple minded band-aid do handle
Array (in)equality (I don't even want think about Hashes 
right now ). 

Unfortunately this requires some minor changes to the language  
itself - i.e. consider this as a RCR request (this is a
request for a general direction - I am not hung up on 
names and I won't hold my breath that something like this
will be excepted;-) 

Christoph.

Ps. The example will probably flake out on windows (not on 
mine so) ...

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

$ ruby -w Untangle.rb
Untangle.rb:22: warning: push (...) interpreted as method call
Untangle.rb:25: warning: include? (...) interpreted as method call
Untangle.rb:51: warning: untangled_equal? (...) interpreted as method call
Untangle.rb:60: warning: untangled_equal? (...) interpreted as method call
Untangle.rb:68: warning: p (...) interpreted as method call
Untangle.rb:69: warning: p (...) interpreted as method call
Untangle.rb:82: warning: p (...) interpreted as method call
Untangle.rb:110: warning: untangled_equal? (...) interpreted as method call
Untangle.rb:59: warning: discarding old ==
true
false
[3]
[1, 2, 3, [...], [...]]
[1, 2, [...], [1, 2, 3, [...], [...]]]
true
true
false

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


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

class IdBag
##########################
# probably this class should also
# help im mangeging exceptions  
# and bag individual id's to aid 
# un_tangled flatten!, hashing etc. 
##########################
def initialize
	@bag = []
end

def  include_pair a, b
	@bag.push  (a+ b << Fixnum::Maxlog)
end	
def included_pair? a,b
	@bag.include?  (a+ b << Fixnum::Maxlog)
end	

private
##########################
# Since there is no Limits ...
# change this depending on 
# your maschine 
##########################
class Fixnum
Maxlog =  32  
end	                    
end                        


##########################
class Array
def  untangled_equal?  (other,id_bag)
	# sanety checks
	return false unless other.kind_of? Array
	return false unless length == other.length
	
	# bag the current id's and check 
	# if id's match
	id_bag.include_pair  id,  other.id 
	return true if  id == other.id
	
	each_index do |i|
		next if id_bag.included_pair? \
			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


##########################
# Examples 
##########################
p ([1,3,3,[3,4],"a"] == [1,3,3,[3,4],"a"]) 
p ([1,3,3,[3,4],"a"] == [1,3,3,[3,4],"b"])

##########################
a =[1,2,3]; a << a; b =[1,2]; b << b;  a  << a; b << a; 
p a - b; p a; p b

##########################
def f(x); [x,x]; end
def g(x); f f f f f f f f x; end
def h(x); g g g g g g g g x; end
def i(x);  h h h h h h h h x; end
def j(x); i i i i  i i i   x;end

p (j(1) == j(1))



##########################
# Integrate your own class in 
# untangle_equal? scheme ...
##########################

class UnOrderedPair
def untangled_equal?(other,id_bag) 
	return false  unless other.kind_of?  UnOrderedPair
	return true if id == other.id
     	
	#  different bag startegy  ...
	id_bag.include_pair  id,  other.id
	id_bag.include_pair  other.id, id
	#  ..... 
	
	return true if  id == other.id
	return true if \
	( @l.untangled_equal?(other.l, id_bag) ) && \
	( @r.untangled_equal?(other.r, id_bag) )
	return  true if \
	( @l.untangled_equal?(other.r, id_bag) ) && \
	( @r.untangled_equal?(other.l, id_bag) )
	return false
end
 
def  == (other)
 	untangled_equal? (other, IdBag.new )
end

def initialize(ll,rr)
	@l = ll; @r = rr
end	
protected 
attr_reader    :l, :r
end


##########################
# Examples 
##########################
l = [3,2,3]; r=[3,2]

pl = UnOrderedPair.new l,r
pr = UnOrderedPair.new r,l

l << pl; r << pr
p pl == pr

##########################
pl = UnOrderedPair.new l,r
pr = UnOrderedPair.new r,r

l << pl; r << pr
p pl == pr