HASH_TABLE with tuple keys of type TUPLE[STRING, STRING]

Hi NG,

I'm doing my first steps in Eiffel, and I've got a question.

I was trying to use a HASH_TABLE like this:

table: HASH_TABLE[INTEGER, TUPLE[STRING, STRING]]

This doesn't work with neither the Gobo kernel library nor the ISE one,
as both use is_equal() for the key comparison in the lookup routine.

Is this a bug or a feature? :-)

Greetings,

Holger

Holger Kiskowski wrote:
> Hi NG,
>
> I'm doing my first steps in Eiffel, and I've got a question.
>
> I was trying to use a HASH_TABLE like this:
>
> table: HASH_TABLE[INTEGER, TUPLE[STRING, STRING]]
>
> This doesn't work with neither the Gobo kernel library nor the ISE one,
> as both use is_equal() for the key comparison in the lookup routine.
>
> Is this a bug or a feature? :-)

I think that if you want to use tuples as keys you should
call `compare_objects' on them just after creating them.

--
Eric Bezault
mailto:ericb@gobosoft.com
http://www.gobosoft.com

Eric Bezault wrote:
> Holger Kiskowski wrote:

>> table: HASH_TABLE[INTEGER, TUPLE[STRING, STRING]]
>>
>> This doesn't work with neither the Gobo kernel library nor the ISE one,
>> as both use is_equal() for the key comparison in the lookup routine.
>> Is this a bug or a feature? :-)
>
> I think that if you want to use tuples as keys you should
> call `compare_objects' on them just after creating them.

Another option might be to use proper abstraction.

Define a class that
(b) has exactly the equality test that you want because you
wrote it.
(a) as an additional benefit, informs about what you want to
do with a pair of strings. (The class has a name and
its feature set contract.)

(TUPLE is really a low level thing.)


-- Georg

Thanks alot for both your responses.

Georg Bauhaus <rm.tsoh.plus-bug.bauhaus@maps.futureapps.de> wrote:
>> I think that if you want to use tuples as keys you should
>> call `compare_objects' on them just after creating them.

> Another option might be to use proper abstraction.
>
> Define a class that
> (b) has exactly the equality test that you want because you
> wrote it.

Yes, but in this case I would have to supply my own hash_code feature in
order to be HASHABLE, right?

> (a) as an additional benefit, informs about what you want to do with a
> pair of strings. (The class has a name and its feature set contract.)

Okay, this is what I'm after exactly:

I want to implement a simple Moore FSM. states and events shall be
represented as strings. Actions will be implemented as agents.

The problem space endities which came to my mind at first glance are:
STATE, TRANSITION, EVENT, FSM.

I wanted to implement the transition function as a table lookup with
keys {state,event}. Same for the state -> action mapping (with keys
{state}).

The Eiffel statements for building the table are supposed to be
generated by a script which gets the STT as input. Something like:

stt.extend("state2", ["state1", "event1"])
action_table.extend(action, "stateN")
(As Eric pointed out, in case of using strings as keys the TUPLE objects
would have to be attached to a temporary prior use, as they have to be
configured with compare_objects)

Would you, now knowing more details, suggest to rather abstract the
transitions as objects with the responsibility to e.g. know their target
states?

Holger

Holger Kiskowski wrote:

>> Define a class that
>> (b) has exactly the equality test that you want because you
>> wrote it.
>
> Yes, but in this case I would have to supply my own hash_code feature in
> order to be HASHABLE, right?

Yes, very likely. As a hash table is an easy but not the fastest
thing to use for a state machine, but as you indend to use then,
I guess you could even afford to delegate hashing to one of
the strings.

> The problem space endities which came to my mind at first glance are:
> STATE, TRANSITION, EVENT, FSM.

So it seems to be an idea to define the classes and relations
you have named.

This is more work than to just use strings for implementing
objects, but types should, for example, help identifying objects
when something goes wrong. A state string and an event string
are both strings and not easily distinguished. On the other hand,
STATE objects will not conform to EVENT objects, and vice versa.
Types allow a somewhat more flexible program, too; you can
define a feature in your classes that will report inner workings
of the state machine. They could be called automatically
when some tracing switch is on, can be redefined to report
elsewhere, etc.

Holger Kiskowski <holger.ki@freenet.de> writes:

> Hi NG,
>
> I'm doing my first steps in Eiffel, and I've got a question.
>
> I was trying to use a HASH_TABLE like this:
>
> table: HASH_TABLE[INTEGER, TUPLE[STRING, STRING]]
>
> This doesn't work with neither the Gobo kernel library nor the ISE one,
> as both use is_equal() for the key comparison in the lookup routine.
>
> Is this a bug or a feature? :-)

Hi!

Most likely the HASH_TABLE uses both, the hash code and is_equal. If the
default (inherited definitions) of both functions aren't OK, you'll have to
redefine them.

Are you saying that is_equal produces the wrong result for
TUPLE[STRING, STRING]?

Regards,
Ulrich

Ulrich Windl <Ulrich.Windl@RZ.Uni-Regensburg.DE> wrote:
>> table: HASH_TABLE[INTEGER, TUPLE[STRING, STRING]]
>>
>> This doesn't work with neither the Gobo kernel library nor the ISE one,
>> as both use is_equal() for the key comparison in the lookup routine.
[...]
> Are you saying that is_equal produces the wrong result for
> TUPLE[STRING, STRING]?

As I'm still very new to Eiffel, I wouldn't dare to judge right or wrong
here. :-)

But let's put it this way: It surprised me, that is_deep_equal() is not
the default in the key lookup routine.

I especially expected the following to be true, but it isn't:

equal(TUPLE["a"], TUPLE["a"])

On the other hand, this yields true:

equal(TUPLE[1], TUPLE[1])

So defaulting to comparison of object references smells a bit like
premature optimisation to me. :-)

Do you know what was the actual design reason for using is_equal()
instead of is_deep_equal()?

Anyway, as I learnt in this thread, there are tree ways out of it:

1. Change the default of TUPLE with compare_objects
2. Use proper abstraction
3. Redefine the features with the offending behaviour.

Thanks very much,

Holger

> Do you know what was the actual design reason for using is_equal()
> instead of is_deep_equal()?

You are confusing things here. The default comparison is using `=', i.e.
for references: comparison of the references, and for expanded:
comparison of their content using `is_equal'.

Regards,
Manu

Emmanuel Stapf [ES] <manus_no_spam@eiffel.nospam.com> wrote:
>> Do you know what was the actual design reason for using is_equal()
>> instead of is_deep_equal()?

> You are confusing things here. The default comparison is using `=', i.e.
> for references: comparison of the references, and for expanded:
> comparison of their content using `is_equal'.

Ah, I see now! Thanks for the clarification.

Holger