@@ -284,3 +284,219 @@ describe('Order', () => {
284284 }
285285 } ) ;
286286} ) ;
287+
288+ class StringPair {
289+ constructor (
290+ readonly s1 : string ,
291+ readonly s2 : string
292+ ) { }
293+ }
294+
295+ class StringPairGenerator {
296+ constructor ( private stringGenerator : StringGenerator ) { }
297+
298+ next ( ) : StringPair {
299+ const prefix = this . stringGenerator . next ( ) ;
300+ const s1 = prefix + this . stringGenerator . next ( ) ;
301+ const s2 = prefix + this . stringGenerator . next ( ) ;
302+ return new StringPair ( s1 , s2 ) ;
303+ }
304+ }
305+
306+ class StringGenerator {
307+ private static readonly DEFAULT_SURROGATE_PAIR_PROBABILITY = 0.33 ;
308+ private static readonly DEFAULT_MAX_LENGTH = 20 ;
309+
310+ private readonly rnd : Random ;
311+ private readonly surrogatePairProbability : number ;
312+ private readonly maxLength : number ;
313+
314+ constructor ( seed : number ) ;
315+ constructor ( rnd : Random , surrogatePairProbability : number , maxLength : number ) ;
316+ constructor (
317+ seedOrRnd : number | Random ,
318+ surrogatePairProbability ?: number ,
319+ maxLength ?: number
320+ ) {
321+ if ( typeof seedOrRnd === 'number' ) {
322+ this . rnd = new Random ( seedOrRnd ) ;
323+ this . surrogatePairProbability =
324+ StringGenerator . DEFAULT_SURROGATE_PAIR_PROBABILITY ;
325+ this . maxLength = StringGenerator . DEFAULT_MAX_LENGTH ;
326+ } else {
327+ this . rnd = seedOrRnd ;
328+ this . surrogatePairProbability = StringGenerator . validateProbability (
329+ surrogatePairProbability !
330+ ) ;
331+ this . maxLength = StringGenerator . validateLength ( maxLength ! ) ;
332+ }
333+ }
334+
335+ private static validateProbability ( probability : number ) : number {
336+ if ( ! Number . isFinite ( probability ) ) {
337+ throw new Error (
338+ `invalid surrogate pair probability: ${ probability }
339+ ) ;
340+ } else if ( probability < 0.0 ) {
341+ throw new Error (
342+ `invalid surrogate pair probability: ${ probability }
343+ ) ;
344+ } else if ( probability > 1.0 ) {
345+ throw new Error (
346+ `invalid surrogate pair probability: ${ probability }
347+ ) ;
348+ }
349+ return probability ;
350+ }
351+
352+ private static validateLength ( length : number ) : number {
353+ if ( length < 0 ) {
354+ throw new Error (
355+ `invalid maximum string length: ${ length }
356+ ) ;
357+ }
358+ return length ;
359+ }
360+
361+ next ( ) : string {
362+ const length = this . rnd . nextInt ( this . maxLength + 1 ) ;
363+ const sb = new StringBuilder ( ) ;
364+ while ( sb . length ( ) < length ) {
365+ const codePoint = this . nextCodePoint ( ) ;
366+ sb . appendCodePoint ( codePoint ) ;
367+ }
368+ return sb . toString ( ) ;
369+ }
370+
371+ private isNextSurrogatePair ( ) : boolean {
372+ return StringGenerator . nextBoolean ( this . rnd , this . surrogatePairProbability ) ;
373+ }
374+
375+ private static nextBoolean ( rnd : Random , probability : number ) : boolean {
376+ if ( probability === 0.0 ) {
377+ return false ;
378+ } else if ( probability === 1.0 ) {
379+ return true ;
380+ } else {
381+ return rnd . nextFloat ( ) < probability ;
382+ }
383+ }
384+
385+ private nextCodePoint ( ) : number {
386+ if ( this . isNextSurrogatePair ( ) ) {
387+ return this . nextSurrogateCodePoint ( ) ;
388+ } else {
389+ return this . nextNonSurrogateCodePoint ( ) ;
390+ }
391+ }
392+
393+ private nextSurrogateCodePoint ( ) : number {
394+ const highSurrogateMin = 0xd800 ;
395+ const highSurrogateMax = 0xdbff ;
396+ const lowSurrogateMin = 0xdc00 ;
397+ const lowSurrogateMax = 0xdfff ;
398+
399+ const highSurrogate = this . nextCodePointRange (
400+ highSurrogateMin ,
401+ highSurrogateMax
402+ ) ;
403+ const lowSurrogate = this . nextCodePointRange (
404+ lowSurrogateMin ,
405+ lowSurrogateMax
406+ ) ;
407+
408+ return ( highSurrogate - 0xd800 ) * 0x400 + ( lowSurrogate - 0xdc00 ) + 0x10000 ;
409+ }
410+
411+ private nextNonSurrogateCodePoint ( ) : number {
412+ let codePoint ;
413+ do {
414+ codePoint = this . nextCodePointRange ( 0 , 0xffff ) ; // BMP range
415+ } while ( codePoint >= 0xd800 && codePoint <= 0xdfff ) ; // Exclude surrogate range
416+
417+ return codePoint ;
418+ }
419+
420+ private nextCodePointRange ( min : number , max : number ) : number {
421+ const rangeSize = max - min + 1 ;
422+ const offset = this . rnd . nextInt ( rangeSize ) ;
423+ return min + offset ;
424+ }
425+ }
426+
427+ class Random {
428+ private seed : number ;
429+
430+ constructor ( seed : number ) {
431+ this . seed = seed ;
432+ }
433+
434+ nextInt ( max : number ) : number {
435+ this . seed = ( this . seed * 9301 + 49297 ) % 233280 ;
436+ const rnd = this . seed / 233280 ;
437+ return Math . floor ( rnd * max ) ;
438+ }
439+
440+ nextFloat ( ) : number {
441+ this . seed = ( this . seed * 9301 + 49297 ) % 233280 ;
442+ return this . seed / 233280 ;
443+ }
444+ }
445+
446+ class StringBuilder {
447+ private buffer : string [ ] = [ ] ;
448+
449+ append ( str : string ) : StringBuilder {
450+ this . buffer . push ( str ) ;
451+ return this ;
452+ }
453+
454+ appendCodePoint ( codePoint : number ) : StringBuilder {
455+ this . buffer . push ( String . fromCodePoint ( codePoint ) ) ;
456+ return this ;
457+ }
458+
459+ toString ( ) : string {
460+ return this . buffer . join ( '' ) ;
461+ }
462+
463+ length ( ) : number {
464+ return this . buffer . join ( '' ) . length ;
465+ }
466+ }
467+
468+ describe ( 'CompareUtf8Strings' , ( ) => {
469+ it ( 'compareUtf8Strings should return correct results' , ( ) => {
470+ const errors = [ ] ;
471+ const seed = Math . floor ( Math . random ( ) * Number . MAX_SAFE_INTEGER ) ;
472+ let passCount = 0 ;
473+ const stringGenerator = new StringGenerator ( new Random ( seed ) , 0.33 , 20 ) ;
474+ const stringPairGenerator = new StringPairGenerator ( stringGenerator ) ;
475+
476+ for ( let i = 0 ; i < 1000000 && errors . length < 10 ; i ++ ) {
477+ const { s1, s2} = stringPairGenerator . next ( ) ;
478+
479+ const actual = order . compareUtf8Strings ( s1 , s2 ) ;
480+ const expected = Buffer . from ( s1 , 'utf8' ) . compare ( Buffer . from ( s2 , 'utf8' ) ) ;
481+
482+ if ( actual === expected ) {
483+ passCount ++ ;
484+ } else {
485+ errors . push (
486+ `compareUtf8Strings(s1="${ s1 } ${ s2 } ${ actual } +
487+ `but expected ${ expected } ${ i } ${ s1 . length } ${ s2 . length }
488+ ) ;
489+ }
490+ }
491+
492+ if ( errors . length > 0 ) {
493+ console . error (
494+ `${ errors . length } ${ passCount } ${ seed }
495+ ) ;
496+ errors . forEach ( ( error , index ) =>
497+ console . error ( `errors[${ index } ${ error } )
498+ ) ;
499+ throw new Error ( 'Test failed' ) ;
500+ }
501+ } ) . timeout ( 20000 ) ;
502+ } ) ;
0 commit comments