Float comparisons

[cmlsharp]

cmpfn.{c,h} define comparison functions for many types, including floats and doubles. It defines them like so:

int doubleCmpFn(const void *p1, const void *p2) {
   double v1, v2;
   v1 = *((double *) p1);
   v2 = *((double *) p2);
   if (v1 == v2) return 0;
   return (v1 < v2) ? -1 : +1;
}

IEEE floating point numbers should not be compared for equality. (Source). As it currently stands, structures that uses a CompareFn (BST and HashMap for example) are inherently implementation defined. This does not seem suitable for a library with "portable" in its name.

A simple fix would be to change v1==v2 to something like abs(v1 - v2) < DBL_EPSILON, however, this creates a scenario in which one double is, conceptually, both equal to and less/greater than another -- in other words, a partial ordering.

The description and implementation of these functions imply that a CompareFn will produce a total ordering; this is fundamentally incompatible with IEEE floating point numbers, as they are only partially orderable. Consequently, any structures which assume a total ordering (e.g. BST) could still exhibit strange behavior with the epsilon solution.

I would propose two ways of dealing with this. One would be to remove doubleCmpFn and floatCmpFn, and have types that use CompareFns throw an error if they are given floating point numbers. The other would be somewhat more complicated as it would involve creating an additional PartialCompareFn interface and implementing it for types which are partially orderable (a superset of types that are totally orderable). Incidentally this is how ordering is done in the Rust standard library, which exports two traits (somewhat analogous to Java interfaces): Ord and PartialOrd.

[cmlsharp]

Comparing float/doubles gets even more complicated when NAN and INF come into the picture since NAN compared with anything is always false, meaning there isn't even a strict equivalence relation for floats since NAN != NAN. Adding NAN to a BST would have very unintuitive results since as the above function is implemented, it would appear to be greater than any other number.

[dmalan]

Are these actually used anywhere in the library itself?

[cmlsharp]

Yes, doubleCmpFn is a possible return value of getCompareFnForType which is used in the construction of both set and bst which themselves are the underlying data structure for graph and map respectively.

[dmalan]

Know why those are using floats?

[cmlsharp]

Ah I think I misunderstood your original questions. The library itself never creates a "bst of doubles" internally or something similar (unless the user chooses to create a data structure that relies on it i.e. a map involving doubles) but it does export the fairly broken functionality to the user.