[GiNaC-list] hash tables and sets

[Chris Dams]

Dear Marko,

On Mon, 18 Sep 2006, Marko Riedel wrote:

> 1. What C++ type is best suited to representing sets?

There is a class set defined in the standard library. I would go for that
unless there is a good reason you cannot use it. You should use
 
> 2. Is there a hash function implemented for GiNaC expressions?

Yes there is. Call the method

unsigned ex::gethash()

to obtain the hash value. You should use std::set<ex, ex_is_less>.

> 3. Can GiNaC expressions be put into some kind of canonical form?

They are automatically put into some kind of canonical form. Of course one
cannot guarantee that equal expressions will end up with the same 
canonical form, as "being equal" is generally not a decidable property.

> 4. (Requirement.) The hash function should be such that e.g.
> 
>    a + b + c * (d + e)
> 
> and
> 
>    b + (e + d) * c + a
> 
> hash to the same value.

Both multiplications and additions are put in a canonical order, so these
two expressions will actually be turning themselves into identical
expressions.  The terms/factors will be sorted according to their hash
values. This also implies that these two expressions will have the same
hashvalue automatically.

Good luck!
Chris