import { extendArray , fastParseInt10 , sgndiff } from "./utils" ; const string_type = typeof "" ; export type SortingVector = ( number | string ) [ ] ; type BucketRange = { lower_index_incl : number ; upper_index_excl : number ; } ; type CompareEquals < T > = ( a : T , b : T ) => number ; type GetVector < T > = ( t : T ) => SortingVector ; export function bucketSort < T > ( array , getVector ? , compareEquals ? ) { getVector = getVector || function ( d ) { return d ; } as any ; var current_sorted_array = array ; var current_bucket_ranges = [ { lower_index_incl : 0 , upper_index_excl : array . length } ] ; var new_sorted_array , new_bucket_ranges , bucket_range , sorted_result ; var max_length_vector = [ ] ; var proposed_vector ; for ( var i = 0 ; i < array . length ; i ++ ) { proposed_vector = getVector ( array [ i ] ) ; if ( proposed_vector . length > max_length_vector . length ) { max_length_vector = proposed_vector ; } } var vector_length = max_length_vector . length ; for ( var vector_index = 0 ; vector_index < vector_length ; vector_index ++ ) { new_sorted_array = [ ] ; new_bucket_ranges = [ ] ; for ( var j = 0 ; j < current_bucket_ranges . length ; j ++ ) { bucket_range = current_bucket_ranges [ j ] ; sorted_result = bucketSortHelper ( current_sorted_array , getVector , bucket_range . lower_index_incl , bucket_range . upper_index_excl , vector_index , ( typeof max_length_vector [ vector_index ] === string_type ) ) ; extendArray ( new_sorted_array , sorted_result . sorted_array ) ; extendArray ( new_bucket_ranges , sorted_result . bucket_ranges ) ; } current_sorted_array = new_sorted_array ; current_bucket_ranges = new_bucket_ranges ; } if ( compareEquals ) { new_sorted_array = [ ] ; var bucket_elts ; for ( var j = 0 ; j < current_bucket_ranges . length ; j ++ ) { bucket_range = current_bucket_ranges [ j ] ; bucket_elts = current_sorted_array . slice ( bucket_range . lower_index_incl , bucket_range . upper_index_excl ) ; bucket_elts . sort ( compareEquals ) ; extendArray ( new_sorted_array , bucket_elts ) ; } current_sorted_array = new_sorted_array ; } return current_sorted_array ; } export function stringSort < T > ( array , getString ? ) { getString = getString || function ( d ) { return d ; } as any ; var data = array . map ( function ( d ) { return { d : d , vector : stringToVector ( getString ( d ) ) } ; } ) ; var sorted = bucketSort ( data , function ( d ) { return d . vector ; } ) ; return sorted . map ( function ( datum ) { return datum . d ; } ) ; } export function stringToVector ( string ) { var vector = [ ] ; var len = string . length ; var numberStartIncl = - 1 ; var charCode ; for ( var i = 0 ; i < len ; i ++ ) { charCode = string . charCodeAt ( i ) ; if ( charCode >= 48 && charCode <= 57 ) { if ( numberStartIncl === - 1 ) { numberStartIncl = i ; } } else { if ( numberStartIncl > - 1 ) { vector . push ( fastParseInt10 ( string , numberStartIncl , i ) ) ; numberStartIncl = - 1 ; } vector . push ( charCode ) ; } } if ( numberStartIncl > - 1 ) { vector . push ( fastParseInt10 ( string , numberStartIncl ) ) ; } return vector ; } export function compareFull < T > ( d1 , d2 , getVector , compareEquals ? ) { var ret = compare ( getVector ( d1 ) , getVector ( d2 ) ) ; if ( ret === 0 && compareEquals ) { ret = compareEquals ( d1 , d2 ) ; } return ret ; } function compareVectorElements ( elt1 , elt2 ) { if ( typeof elt1 === string_type ) { return compare ( stringToVector ( elt1 as string ) , stringToVector ( elt2 as string ) ) ; } else { return sgndiff ( elt1 as number , elt2 as number ) ; } } export function compare ( vector1 , vector2 ) { var ret = 0 ; var cmp ; for ( var i = 0 ; i < vector1 . length ; i ++ ) { if ( i >= vector2 . length ) { ret = 1 ; break ; } cmp = compareVectorElements ( vector1 [ i ] , vector2 [ i ] ) ; if ( cmp !== 0 ) { ret = cmp ; break ; } } if ( ret === 0 ) { if ( vector1 . length < vector2 . length ) { ret = - 1 ; } } return ret ; } export function bucketSortHelper < T > ( array , getVector , sort_range_lower_index_incl , sort_range_upper_index_excl , vector_index , isStringElt ) { if ( ! array . length || sort_range_lower_index_incl >= sort_range_upper_index_excl ) { return { sorted_array : [ ] , bucket_ranges : [ ] } ; } var buckets = { } ; var keys = [ ] ; var vector , key ; var sortFirst = [ ] ; for ( var i = sort_range_lower_index_incl ; i < sort_range_upper_index_excl ; i ++ ) { vector = getVector ( array [ i ] ) ; if ( vector . length > vector_index ) { key = vector [ vector_index ] ; if ( ! ( key in buckets ) ) { keys . push ( key ) ; buckets [ key ] = [ ] ; } buckets [ key ] . push ( array [ i ] ) ; } else { sortFirst . push ( array [ i ] ) ; } } if ( ! isStringElt ) { keys . sort ( sgndiff ) ; } else { keys = stringSort ( keys ) ; } var sorted_array = [ ] ; var bucket_ranges = [ ] ; var lower_index_incl , upper_index_excl ; if ( sortFirst . length ) { lower_index_incl = sort_range_lower_index_incl + sorted_array . length ; bucket_ranges . push ( { lower_index_incl : lower_index_incl , upper_index_excl : lower_index_incl + sortFirst . length } ) ; extendArray ( sorted_array , sortFirst ) ; } for ( var i = 0 ; i < keys . length ; i ++ ) { var bucket = buckets [ keys [ i ] ] ; lower_index_incl = sort_range_lower_index_incl + sorted_array . length ; upper_index_excl = lower_index_incl + bucket . length ; bucket_ranges . push ( { lower_index_incl : lower_index_incl , upper_index_excl : upper_index_excl } ) ; extendArray ( sorted_array , bucket ) ; } return { sorted_array : sorted_array , bucket_ranges : bucket_ranges } ; }