Duncan Rose wrote:
On Monday, July 18, 2005, at 08:13 pm, rpgoldman@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.