Incorrect lexical ordering

[ataggart]

Per RFC 4122, section 3, "Rules for Lexical Equivalence":

Consider each field of the UUID to be an unsigned integer as shown
in the table in section Section 4.1.2.

IIUC, the following should be the correct ordering (0x7d < 0xb6):

1. 7d7d081d-7440-441d-9828-26e57c614219
2. b6be8d3b-7bad-4499-8a33-50634dc9e3a9

And yet:

user=> (def x #uuid "7d7d081d-7440-441d-9828-26e57c614219")
#'user/x
user=> (def y #uuid "b6be8d3b-7bad-4499-8a33-50634dc9e3a9")
#'user/y
user=> (sort (comparator uuid<) [x y])
(#uuid "b6be8d3b-7bad-4499-8a33-50634dc9e3a9" #uuid "7d7d081d-7440-441d-9828-26e57c614219")

This is a consequence of using signed comparison:

user=> (.getMostSignificantBits x)
9042392549427266589
user=> (.getMostSignificantBits y)
-5278626426614102887
user=> (Long/compare (.getMostSignificantBits x) (.getMostSignificantBits y))
1
user=> (Long/compareUnsigned (.getMostSignificantBits x) (.getMostSignificantBits y))
-1

This is also an issue with the implementation of java.util.UUID/compareTo:

user=> (sort [x y])
(#uuid "b6be8d3b-7bad-4499-8a33-50634dc9e3a9" #uuid "7d7d081d-7440-441d-9828-26e57c614219")

Given the ubiquity of the problem, I suspect providing new, compliant lexical functions would be better than changing the existing behaviour.

[danlentz]

For lexical ordering, see #53