Some FSet collections rely on a comparison function to order their elements. In mathematical terms,
this function must compute a
strict weak
ordering. FSet’s provided methods on compare satisfy this requirement, and the methods
added by define-equality-slots do so also, so as long as you confine yourself to those, as I
expect most users will, you don’t need to understand this section. But if you want to write a
completely custom comparison function for use with the WB collections, you should make sure it has
the following properties:
For our purposes, this just means that the function returns :equal (not :less or
:greater) on equal arguments.
If the function returns :less on the pair 〈A, B〉, then it returns :greater on 〈B, A〉,
and conversely.
If the function returns :less on 〈A, B〉, and :less on 〈B, C〉, then it also returns
:less on 〈A, C〉; and similarly for :greater.
If the function returns :equal on 〈A, B〉, then it also returns :equal on 〈B, A〉.
If the function returns :equal on 〈A, B〉, and :equal on 〈B, C〉, then it also
returns :equal on 〈A, C〉.
If the function returns :unequal on 〈A, B〉, then it also returns :unequal on 〈B, A〉.
If the function returns :unequal on 〈A, B〉, and either :equal or :unequal on
〈B, C〉, then it returns :unequal on 〈A, C〉.
Satisfying these requirements is fairly straightforward if you follow this plan. Assuming that the
values you’re comparing are represented by objects of the same class, you compare their slot values
in some order you choose. For each comparison, if the result is :less or :greater,
return that; if it’s :equal or :unequal, proceed to the next slot if there is one.
Once you’ve compared all the slots, if any slot value comparison returned :unequal, return
:unequal; otherwise, return :equal.
In many cases you will be able to know that no individual slot value comparison can return
:unequal — for example, if you’re comparing integers or strings — so you won’t need to
handle that case.
FSet exports a macro, compare-slots, that will do the above comparison for you in the case
where there’s a fixed list of slots to compare. If that’s not the case — for example, if you’ve
got a non-FSet collection class that you would like to nest inside FSet collections — you’ll have
to code the comparison yourself; see the next section.
A handy macro for writing the bodies of compare methods and comparison functions for user
classes. Returns the result of comparing the two objects by comparing the results of calling each
of accessors, in order, on the objects. Despite the name, an accessor can actually be any
function on the class in question; it can also be a symbol, which will be used to access the slot
via slot-value. For example, if class frob has accessor frob-color and slot
id:
(defmethod compare ((f1 frob) (f2 frob)) (compare-slots f1 f2 #'frob-color 'id))
At least on SBCL, it will be fastest to use slot names (e.g. 'id) on standard classes, but
accessor functions (e.g. #'frob-color) on structure classes. If you’re writing a function
instead of a method, declaring the type of the parameters can also help.
By default, the values of a given accessor on the two objects will be compared with compare.
To override this, you have two choices depending on whether the function you want to call obeys the
FSet comparison protocol (returning :equal, :less, :greater, or
:unequal) or is just a boolean predicate \(like cl:<\). In the first case, supply the
accessor as a list (:compare-fn acc compare-fn) where acc is the accessor
and compare-fn is the name of the function to use; in the second case, use
:less-fn instead of :compare-fn. For example:
(defmethod compare ((f1 frob) (f2 frob))
(compare-slots f1 f2 (:compare-fn #'frob-color #'compare-colors)
(:less-fn 'id #'<)))
If the symbol :eql is supplied as the last accessor, then if the comparisons
by the other supplied accessors all return :equal but obj1 and obj2 are
not eql, this returns :unequal.