upsetjs import type { ISet , ISetCombination , ISetCombinations , ISets , SetCombinationType } from '../model' ; import { postprocessCombinations , SortCombinationOrder , SortCombinationOrders } from './asCombinations' ; import type { SortSetOrder } from './asSets' ; import { SET_JOINERS } from './constants' ; import extractSets from './extractSets' ; import generateCombinations from './generateCombinations' ; export interface ExtractCombinationsOptions < T > { type ? : SetCombinationType ; setOrder ? : SortSetOrder ; setLimit ? : number ; combinationOrder ? : SortCombinationOrder | SortCombinationOrders ; combinationLimit ? : number ; sets ? : ISets < T > ; joiner ? : string ; } type IWriteAbleSetCombination < T > = ISetCombination < T > & { readonly elems : T [ ] ; cardinality : number ; } ; function createTree < T > ( byDegree , getOrCreateCombination ) { const children = new Map < IWriteAbleSetCombination < T > , IWriteAbleSetCombination < T > [ ] > ( ) ; byDegree . slice ( ) . reverse ( ) . forEach ( ( csOfDegree ) => { if ( csOfDegree . length === 0 || csOfDegree [ 0 ] . degree === 1 ) { return ; } csOfDegree . forEach ( ( c ) => { const sets = Array . from ( c . sets ) . map ( ( d ) => d . name ) ; for ( let i = 0 ; i < sets . length ; i ++ ) { const subSet = sets . slice ( ) ; subSet . splice ( i , 1 ) ; const parent = getOrCreateCombination ( subSet ) ; if ( children . has ( parent ) ) { children . get ( parent ) ! . push ( c ) ; } else { children . set ( parent , [ c ] ) ; } } } ) ; } ) ; return children ; } param elements param acc param options export default function extractCombinations < T > ( elements , acc , options ? ) ; param elements param options export default function extractCombinations < T extends { sets : string [ ] ; } > ( elements , options ? ) ; export default function extractCombinations < T > ( elements , accOrOptions ? , o = { } ) { const acc = typeof accOrOptions === 'function' ? accOrOptions : ( e ) => ( e as unknown as { sets : string [ ] ; } ) . sets ; const options = ( typeof accOrOptions !== 'function' ? accOrOptions : o ) ?? { } ; const type = options . type ?? 'intersection' ; const sets = options . sets ?? extractSets ( elements , acc , { limit : options . setLimit , order : options . setOrder , } ) ; if ( type === 'union' ) { return { sets , combinations : generateCombinations ( sets , { type : 'union' , limit : options . combinationLimit , order : options . combinationOrder , } ) , } ; } const setLookup = Object . create ( null ) ; sets . forEach ( ( set , i ) => { setLookup [ set . name ] = [ set , i ] ; } ) ; const isSortedAlphabetically = sets . map ( ( d ) => d . name ) . sort ( ) . every ( ( d , i ) => sets [ i ] . name === d ) ; const bySet = isSortedAlphabetically ? undefined : ( a , b ) => { const ai = setLookup [ a ] ?. [ 1 ] ?? - 1 ; const bi = setLookup [ b ] ?. [ 1 ] ?? - 1 ; return ai - bi ; } ; const validSet = options . sets == null && options . setLimit == null ? null : new Set ( sets . map ( ( d ) => d . name ) ) ; const joiner = options . joiner ?? SET_JOINERS [ type ] ; const cs = [ ] ; const csLookup = Object . create ( null ) ; const byDegree = Array ( sets . length + 1 ) . fill ( 0 ) . map ( ( _ ) => [ ] ) ; function genName ( setsOfElem ) { switch ( setsOfElem . length ) { case 0 : return '()' ; case 1 : return setsOfElem [ 0 ] ; default : const sorted = setsOfElem . slice ( ) . sort ( bySet ) ; const joined = sorted . join ( joiner ) ; return '(' + joined + ')' ; } } function genKey ( setsOfElem ) { switch ( setsOfElem . length ) { case 0 : return '' ; case 1 : return setsOfElem [ 0 ] ; case 2 : { if ( ( bySet != null && bySet ( setsOfElem [ 0 ] , setsOfElem [ 1 ] ) > 0 ) || ( bySet == null && setsOfElem [ 1 ] > setsOfElem [ 0 ] ) ) { return setsOfElem [ 1 ] + '&' + setsOfElem [ 0 ] ; } return setsOfElem [ 0 ] + '&' + setsOfElem [ 1 ] ; } default : const sorted = setsOfElem . slice ( ) . sort ( bySet ) ; return sorted . join ( '&' ) ; } } function getOrCreateCombination ( setsOfElem ) { const key = genKey ( setsOfElem ) ; const entry = csLookup [ key ] ; if ( entry ) { return entry ; } const newEntry = { type , name : genName ( setsOfElem ) , degree : setsOfElem . length , sets : new Set ( setsOfElem . map ( ( s ) => setLookup [ s ] ! [ 0 ] ) ) , cardinality : 0 , elems : [ ] , } ; csLookup [ key ] = newEntry ; cs . push ( newEntry ) ; byDegree [ newEntry . degree ] ! . push ( newEntry ) ; return newEntry ; } elements . forEach ( ( elem ) => { let setsOfElem = acc ( elem ) ; if ( validSet ) { setsOfElem = setsOfElem . filter ( ( d ) => validSet . has ( d ) ) ; } const c = getOrCreateCombination ( setsOfElem ) ; c . elems . push ( elem ) ; ( c as { cardinality : number ; } ) . cardinality ++ ; } ) ; const finalize = ( ) => { return { sets , combinations : postprocessCombinations ( sets , cs , { order : options . combinationOrder , limit : options . combinationLimit , } ) , } ; } ; if ( type === 'distinctIntersection' ) { return finalize ( ) ; } const children = createTree ( byDegree , getOrCreateCombination ) ; function visit ( node , visited , agg ) { if ( visited . has ( node ) ) { return ; } visited . add ( node ) ; if ( node . elems . length < 1000 ) { agg [ 0 ] . push ( ... node . elems ) ; } else { agg . push ( node . elems ) ; } ( children . get ( node ) ?? [ ] ) . forEach ( ( child ) => visit ( child , visited , agg ) ) ; } byDegree . slice ( 1 ) . forEach ( ( level ) => { level . forEach ( ( node ) => { const visited = new Set < IWriteAbleSetCombination < T > > ( ) ; const agg = [ node . elems ] ; ( children . get ( node ) ?? [ ] ) . forEach ( ( child ) => { visit ( child , visited , agg ) ; } ) ; const elems = agg . length === 1 ? agg [ 0 ] : agg . flat ( ) ; Object . assign ( node , { elems , cardinality : elems . length } ) ; } ) ; } ) ; return finalize ( ) ; }