Re: Equivalent keys/elements in Ada.Containers Maps and Sets

["Matthew Heaney" <mheaney@on2.com>]

Niklas Holsti wrote:
>
> -- First problem: "equivalence" in Ordered Maps and Sets
>
> However, one can easily make
> an example of a strict ordering "<" in which the "incomparable" relation
> is not transitive; say we have three values X, Y, Z where the only
> relation is X < Z; thus X and Y are incomparable and Y and Z are
> incomparable, but X and Z are not incomparable.

I don't see this.  Please provide an example.


> For example, by A.18.7(22/2) the function Equivalent_Sets reports two
> sets S1 and S2 as equivalent if they have the same number of elements
> and if for every element E1 of S1 there is an element E2 of S2 such that
> E1 and E2 are "equivalent". (Note the asymmetry of this definition: it
> "traverses" S1 and "searches" for equivalent elements in S2.)

The search only applies to the hashed set.  (A search is necessary
because hashed containers can have different capacities.)  For the
ordered set, you only need to traverse both sets simultaneously; there
is no search.


> Now, if "equivalence" of elements is not transitive, we can have two
> sets S1 and S2 such that Equivalent_Sets (S1, S2) is True even if S2
> contains an element that is not "equivalent" to any element in S1.

I still don't know what you mean by equivalence not being transitive.
Please provide an example.


> -- Second problem: "=" for Element_Type in Sets
>
> For Sets, however, I find it puzzling that no relationship is required
> or expected between this "=" and the other formal functions
> Equivalent_Elements, Hash and "<".

Equality implies equivalence, so there is no puzzle.  (But note that
equivalence does not imply equality -- hence two separate generic
formal functions.)


> For example, in the case of two
> elements E1 and E2 in an Ordered_Set it would be very natural to require
> that if E1 "=" E2 then we cannot also have E1 "<" E2 or E2 "<" E1, in
> other words we should have E1 "equivalent" to E2.

Yes, that is indeed implied.

  E1 = E2 => Is_Equivalent (E1, E2)


> One point where this may be significant is the definition of the "="
> operator on Sets in A.18.7(20/2). The definition requires each element
> of the Left set to be compared for "=" with the elements of the Right
> set. If the actual "=" function is unrelated to the Hash function or to
> the "<" operator for elements, I don't see how the "=" operator on Sets
> can be implemented in less than O(N**2) complexity.

No, your premise is false.

  E1 = E2 => Hash (E1) = Hash (E2)

Equality is always O(1).  There are no operations that are O(N**2).


> I think the definition of "=" for Sets expects the implementation to
> compare only "equivalent" elements of the Left and Right Sets. If
> "equivalence" is transitive this means that each element of Left can be
> compared with "=" to exactly one element of Right (or, for Hashed_Sets,
> to the elements in one bucket, if the implementation prefers to use "="
> directly and not first check Equivalent_Elements).

The implementation of "=" for hashed sets does not use
Equivalent_Elements to test the elemenets in the bucket -- it uses
element "=" (since element "=" implies that Is_Equivalent is also
true).


> I know that there are no RM requirements or advice on the complexity of
> the "=" operator for Sets, but under the current rules I think that the
> natural, fast implementation that only compares the equivalent elements
> is wrong.

The "=" operator for sets is O(n).


> To solve this problem I think that A.18.6(3/2) should be extended to
> also require or expect that two "=" elements are "equivalent".

That's already implied.


> For Hashed_Sets this means that if E1 "=" E2 then
> Equivalent_Elements(E1,E2) must be True. A consequence is that Hash(E1)
> = Hash(E2).

Yes, of course.


> For Ordered_Sets this means that if E1 "=" E2 then both E1 "<" E2 and
> E2 "<" E1 must be False.

Yes, of course.


> -- Last words
>
> Should I submit these comments to ada-comment@ada-auth.org? Or were the
> issues already considered in the design of Ada.Containers? I would be
> grateful for your advice.

Yes, they were indeed considered, and are already implied by the RM.

-Matt