[Gecode] Re: Problem with operator== for views, equality vs. aliasing.

[Christian Schulte]

Dear all,

I now have provided some working infrastructure for testing sharing and
equality.

A view x depends on a variable v, either if x is an identify view for v or x
is derived from a view v' which depends on v (this assumes the terminology
in the views paper).

Two views x and y (of not necessarily the same type) _share_ a variable v,
if both x and y depend on v. The views are also called shared. Written in
Gecode as x & y.

Two views x and y of the same type are _equal_, if they are identical. This
means that when becoming assigned they will have the same value. Written in
Gecode as x == y (also != is available).

Additionally, there is an ordering on views. The order is completely
arbitrary (implemented for example by location in memory) and is not stable
with respect to cloning. However, the following important invariant holds:
if x<y and x and y are shared, then for a view z that is not shared with x
or y: z < x or y < z but never x < z < y. For example, the implementation
achieves this by using lexicographic ordering where the variable component
of a derived view takes precedence.

This means that when sorting views of the same type wrt <, shared views are
next to each other.
 
ViewArrays now provide some functionality for sorting and finding shared or
equal views. For a ViewArray x:
	x.equal()	tests whether x has at least two equal views.
	x.shared()	tests whether x has at least two shared views.
	x.group_equal()	sorts the views in x and returns x.equal()
	x.group_shared()	sorts the views in x and returns x.shared()

All operations take n log n in average (based on quicksorting the views). If
the order of views in a ViewArray does not matter, the group_-variants are
more efficient (in-place sorting).

However, the original problem we wanted to tackle with all this, is still
unsolved: how to decide idempotence with shared views... See next Email.

Christian

--
Christian Schulte, http://www.imit.kth.se/~schulte/