Improve sorting / comparison code so it uses Unicode code point order

[dlongley]

See comments here: w3c/rdf-canon#17 (comment)

[dlongley]

This may be of some use:

/* chosen char examples from:
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort
*/

// expected unicode code point order
const expected = ['a', '\uFF3A', '\uD855\uDE51'];
console.log('expected', expected);

// use native code to sort by code point
const codePoint = ['\uFF3A', 'a', '\uD855\uDE51'];
const collator = new Intl.Collator();
codePoint.sort(collator.compare);
console.log('codePoint', codePoint);

// default native sort is by utf-16 code units
const utf16 = ['\uFF3A', 'a', '\uD855\uDE51'];
utf16.sort();
console.log('utf16', utf16);

// use 'en' locale to sort
const en = ['\uFF3A', 'a', '\uD855\uDE51'];
const enCollator = new Intl.Collator('en');
en.sort(enCollator.compare);
console.log('en', en);

Output from node 16:

expected [ 'a', 'Ｚ', '𥙑' ]
codePoint [ 'a', 'Ｚ', '𥙑' ]
utf16 [ 'a', '𥙑', 'Ｚ' ]
en [ 'a', 'Ｚ', '𥙑' ]

It could be that my default locale, which is en might be what is used if I don't specify one in the Collator constructor.

More test values should be added and specs checked to make sure that using new Intl.Collator().compare as the comparator function (which appears to be well supported) will sort by Unicode code point (using the natural order / element table order).

[dlongley]

Yes, it is the case that not passing any options to Intl.Collator() results in using the system defaults:

> c = new Intl.Collator()
Collator [Intl.Collator] {}
> c.resolvedOptions()
{
  locale: 'en-US',
  usage: 'sort',
  sensitivity: 'variant',
  ignorePunctuation: false,
  collation: 'default',
  numeric: false,
  caseFirst: 'false'
}

[dlongley]

Other comparator functions to consider: https://stackoverflow.com/a/70137366/399274

function compareCodePoints(s1, s2) {
    const len = Math.min(s1.length, s2.length);
    let i = 0;
    // note: `c1` unused; iteration is constructed this
    // way to ensure proper character enumeration
    for (const c1 of s1) {
        if (i >= len) {
            break;
        }
        const cp1 = s1.codePointAt(i);
        const cp2 = s2.codePointAt(i);
        const order = cp1 - cp2;
        if (order !== 0) {
            return order;
        }
        i++;
        if (cp1 > 0xFFFF) {
            i++;
        }
    }
    return s1.length - s2.length;
}

Other algorithms to consider here: https://icu-project.org/docs/papers/utf16_code_point_order.html