[mcclim-devel] question about CLIM spec [format-graph-from-roots]

[Robert P. Goldman]

Duncan Rose wrote:

> 
> On Monday, July 18, 2005, at 08:13  pm, rpgoldman at real-time.com wrote:
> 
>>
>> AFAICT, the CLIM spec doesn't say anything about what are the
>> acceptable values for the DUPLICATE-TEST argument to
>> FORMAT-GRAPH-FROM-ROOTS (although it does specify that the default
>> value is EQL).  This seems very unfortunate.  If we were to be limited
> 
> 
> It says that it is a '...function of two arguments that is used to 
> compare two objects...'
> I think any function of two arguments that can be used to compare two 
> objects should be ok.
> 
>> to the conventional equality test values, then we would be able to use
>> a hash-table to store the graph nodes.  However, if the spec permits
>> arbitrary functions of two arguments, that seems to make use of
>> hash-tables impossible.  Am I overlooking something?  Is this a
>> deficiency in the spec?
> 
> 
> I don't understand what the benefit of using hashtables to store the 
> nodes is. That said, it seems to me that whilst the spec permits 
> arbitrary functions of two arguments, any specific node type will need a 
> particular DUPLICATE-TEST function... or am I missing the point of the 
> question totally?

Given the fact that there might be a very large number of nodes, and 
that we have to check for duplicates, a hash-table providing constant 
time lookup seems pretty desirable, so one could do

(make-hash-table :test duplicate-test)
(gethash (funcall duplicate-key node) hash-table)

to find duplicates.

Perhaps /I'm/ missing the point --- do you have a different vision of 
how the duplicate detection could be performed?

I haven't thought long and hard about it, but in the worst case, given 
an arbitrary duplicate-test function, isn't it the case that we can't do 
better than linear search to check for duplicates?  I.e., we have no 
idea how to thin the field of possible match candidates, so we can't do 
better than check EVERY existing graph node to see if a newly-added one 
matches.  That seems unacceptable.  Or am I overlooking somethign?

Note also that since you have the freedom to define the DUPLICATE-KEY 
funciton yourself, restricting the DUPLICATE-TEST values to one of the 
hash-table-acceptable alternatives doesn't seem like a profound sacrifice.

Can anyone think of a case where it would be a substantial sacrifice?

Best,

Robert


P.S.  This discussion has reminded me to add an annotation to the CLIM 
spec to this effect.