extra/assocs/extras/extras.factor

   1 ! Copyright (C) 2012 John Benediktsson, Doug Coleman
   2 ! See https://factorcode.org/license.txt for BSD license
   3 USING: arrays assocs assocs.private kernel math math.statistics
   4 sequences sequences.extras sets ;
   5 IN: assocs.extras
   6
   7 : of* ( assoc key -- value/f ? ) swap at* ; inline
   8
   9 : of+ ( assoc key n -- assoc ) '[ 0 or _ + ] change-of ; inline
  10
  11 : of+* ( assoc key n -- assoc old new ) '[ [ 0 or _ + ] keep swap dup ] change-of ; inline
  12
  13 : delete-of ( assoc key -- assoc ) over delete-at ; inline
  14
  15 : delete-of* ( assoc key -- assoc value/f ? )
  16     [ of* ] [ delete-of -rot ] 2bi ;
  17
  18 : ?delete-of ( assoc key -- assoc value/key ? )
  19     [ ?of ] [ delete-of -rot ] 2bi ;
  20
  21 : rename-of ( assoc key newkey -- assoc )
  22     [ delete-of* ] dip swap [ set-of ] [ 2drop ] if ;
  23
  24 : inc-of ( assoc key -- assoc ) 1 of+ ; inline
  25
  26 : inc-of* ( assoc key -- assoc old new ) 1 of+* ; inline
  27
  28 : push-at-each ( value keys assoc -- )
  29     '[ _ push-at ] with each ; inline
  30
  31 : deep-of ( assoc seq -- value/f )
  32     [ of ] each ; inline
  33
  34 : deep-of-but-last ( assoc seq -- obj key )
  35     unclip-last [ [ of ] each ] dip ; inline
  36
  37 : deep-change-of ( assoc seq quot -- )
  38     [ deep-of-but-last swap ] dip change-at ; inline
  39
  40 : deep-set-of ( assoc seq elt -- )
  41     [ deep-of-but-last ] dip spin set-at ; inline
  42
  43 : zip-longest-with ( seq1 seq2 fill -- assoc )
  44     pad-longest zip ;
  45
  46 : zip-longest ( seq1 seq2 -- assoc )
  47     f zip-longest-with ;
  48
  49 : substitute! ( seq assoc -- seq )
  50     substituter map! ;
  51
  52 : assoc-reduce ( ... assoc identity quot: ( ... prev key value -- next ) -- ... result )
  53     [ >alist ] 2dip [ first2 ] prepose reduce ; inline
  54
  55 : reduce-keys ( ... assoc identity quot: ( ... prev elt -- ... next ) -- ... result )
  56     [ drop ] prepose assoc-reduce ; inline
  57
  58 : reduce-values ( ... assoc identity quot: ( ... prev elt -- ... next ) -- ... result )
  59     [ nip ] prepose assoc-reduce ; inline
  60
  61 : sum-keys ( assoc -- n ) 0 [ + ] reduce-keys ; inline
  62
  63 : sum-values ( assoc -- n ) 0 [ + ] reduce-values ; inline
  64
  65 : map-keys ( assoc quot: ( key -- key' ) -- assoc )
  66     '[ _ dip ] assoc-map ; inline
  67
  68 : map-values ( assoc quot: ( value -- value' ) -- assoc )
  69     '[ swap _ dip swap ] assoc-map ; inline
  70
  71 : filter-keys ( assoc quot: ( key -- key' ) -- assoc' )
  72     '[ drop @ ] assoc-filter ; inline
  73
  74 : filter-values ( assoc quot: ( value -- value' ) -- assoc' )
  75     '[ nip @ ] assoc-filter ; inline
  76
  77 : reject-keys ( assoc quot: ( key -- key' ) -- assoc' )
  78     '[ drop @ ] assoc-reject ; inline
  79
  80 : reject-values ( assoc quot: ( value -- value' ) -- assoc' )
  81     '[ nip @ ] assoc-reject ; inline
  82
  83 : rekey-new-assoc ( assoc keys -- newassoc )
  84     [ tuck of ] with H{ } map>assoc ; inline
  85
  86 : rekey-assoc ( assoc keys -- assoc )
  87     [ dup keys ] dip diff over [ delete-at ] curry each ; inline
  88
  89 : if-assoc-empty ( ..a assoc quot1: ( ..a -- ..b ) quot2: ( ..a assoc -- ..b ) -- ..b )
  90     [ dup assoc-empty? ] [ [ drop ] prepose ] [ ] tri* if ; inline
  91
  92 : assoc-invert-as ( assoc exemplar -- newassoc )
  93     [ swap ] swap assoc-map-as ;
  94
  95 : assoc-invert ( assoc -- newassoc )
  96     dup assoc-invert-as ;
  97
  98 : assoc-collect! ( assoc1 assoc2 -- assoc1 )
  99     over [ push-at ] with-assoc assoc-each ;
 100
 101 : assoc-collect ( assoc1 assoc2 -- newassoc )
 102     [ [ [ assoc-size ] bi@ + ] [ drop ] 2bi new-assoc ] 2keep
 103     [ assoc-collect! ] bi@ ;
 104
 105 ! iterate over assoc2, replace conflicting values
 106 ! Modifies assoc1
 107 : assoc-merge! ( assoc1 assoc2 quot: ( value1 value2 -- new-value ) -- assoc1' )
 108     [| key2 val2 quot | val2 key2 pick
 109     at* [ swap quot call ] [ drop ] if
 110     key2 pick set-at ] curry assoc-each ; inline
 111
 112 ! Same as above, non-destructive
 113 : assoc-merge ( assoc1 assoc2 quot: ( value1 value2 -- new-value ) -- new-assoc )
 114     pick [ [ clone ] 2dip assoc-merge! ]
 115     [ drop nip ] if
 116     ; inline
 117
 118 ! Successively apply assoc-merge operation
 119 : assoc-collapse ( seq quot: ( value1 value2 -- new-value ) -- assoc )
 120     over empty?
 121     [ 2drop f ]
 122     [ [ unclip-slice H{ } or clone ] [ [ assoc-merge! ] curry ] bi* reduce ] if ; inline
 123
 124 : assoc-collapse! ( assoc seq quot: ( value1 value2 -- new-value ) -- assoc )
 125     [ assoc-merge! ] curry each ; inline
 126
 127 : assoc-collapse-as ( seq quot: ( value1 value2 -- new-value ) exemplar -- assoc )
 128     pick first assoc-size swap new-assoc
 129     -rot assoc-collapse! ; inline
 130
 131 GENERIC: delete-value-at ( value assoc -- )
 132
 133 M: assoc delete-value-at
 134     [ value-at* ] keep swap [ delete-at ] [ 2drop ] if ;
 135
 136 ERROR: key-exists value key assoc ;
 137 : set-once-at ( value key assoc -- )
 138     2dup ?at [
 139         key-exists
 140     ] [
 141         drop set-at
 142     ] if ;
 143
 144 : kv-with ( obj assoc quot -- assoc curried )
 145     swapd [ -rotd call ] 2curry ; inline
 146
 147 <PRIVATE
 148
 149 : (sequence>assoc) ( seq map-quot insert-quot assoc -- assoc )
 150     [ swap curry compose each ] keep ; inline
 151
 152 : (sequence-index>assoc) ( seq map-quot insert-quot assoc -- assoc )
 153     [ swap curry compose each-index ] keep ; inline
 154
 155 PRIVATE>
 156
 157 : sequence>assoc! ( assoc seq map-quot: ( x -- ..y ) insert-quot: ( ..y assoc -- ) -- assoc )
 158     roll (sequence>assoc) ; inline
 159
 160 : assoc>object ( assoc map-quot insert-quot exemplar -- object )
 161     clone [ swap curry compose assoc-each ] keep ; inline
 162
 163 : assoc>object! ( assoc seq map-quot: ( x -- ..y ) insert-quot: ( ..y assoc -- ) -- object )
 164     roll assoc>object ; inline
 165
 166 : sequence>assoc ( seq map-quot insert-quot exemplar -- assoc )
 167     clone (sequence>assoc) ; inline
 168
 169 : sequence-index>assoc ( seq map-quot insert-quot exemplar -- assoc )
 170     clone (sequence-index>assoc) ; inline
 171
 172 : sequence-index>hashtable ( seq map-quot insert-quot -- hashtable )
 173     H{ } sequence-index>assoc ; inline
 174
 175 : sequence>hashtable ( seq map-quot insert-quot -- hashtable )
 176     H{ } sequence>assoc ; inline
 177
 178 : ?1array ( obj -- seq ) dup sequence? [ 1array ] unless ; inline
 179
 180 : expand-keys-set-at-as ( assoc exemplar -- hashtable' )
 181     [
 182         [ swap ?1array ]
 183         [ '[ _ set-at ] with each ]
 184     ] dip assoc>object ;
 185
 186 : expand-keys-set-at ( assoc -- hashtable' )
 187     H{ } expand-keys-set-at-as ;
 188
 189 : expand-keys-push-at-as ( assoc exemplar -- hashtable' )
 190     [
 191         [ swap ?1array ]
 192         [ push-at-each ]
 193     ] dip assoc>object ;
 194
 195 : expand-keys-push-at ( assoc -- hashtable' )
 196     H{ } expand-keys-push-at-as ; inline
 197
 198 : expand-keys-push-as ( assoc exemplar -- hashtable' )
 199     [
 200         [ [ ?1array ] dip ]
 201         [ '[ _ 2array _ push ] each ]
 202     ] dip assoc>object ;
 203
 204 : expand-keys-push ( assoc -- hashtable' )
 205     V{ } expand-keys-push-as ; inline
 206
 207 : expand-values-set-at-as ( assoc exemplar -- hashtable' )
 208     [
 209         [ ?1array swap ]
 210         [ '[ _ _ set-at ] each ]
 211     ] dip assoc>object ;
 212
 213 : expand-values-set-at ( assoc -- hashtable' )
 214     H{ } expand-values-set-at-as ; inline
 215
 216 : expand-values-push-at-as ( assoc exemplar -- hashtable' )
 217     [
 218         [ ?1array swap ]
 219         [ '[ _ _ push-at ] each ]
 220     ] dip assoc>object ;
 221
 222 : expand-values-push-at ( assoc -- assoc )
 223     H{ } expand-values-push-at-as ; inline
 224
 225 : expand-values-push-as ( assoc exemplar -- assoc )
 226     [
 227         [ ?1array ]
 228         [ '[ 2array _ push ] with each ]
 229     ] dip assoc>object ;
 230
 231 : expand-values-push ( assoc -- sequence )
 232     V{ } expand-values-push-as ; inline
 233
 234 : assoc-any-key? ( ... assoc quot: ( ... key -- ... ? ) -- ... ? )
 235     [ drop ] prepose assoc-find 2nip ; inline
 236
 237 : assoc-any-value? ( ... assoc quot: ( ... value -- ... ? ) -- ... ? )
 238     [ nip ] prepose assoc-find 2nip ; inline
 239
 240 : assoc-all-key? ( ... assoc quot: ( ... key -- ... ? ) -- ... ? )
 241     [ not ] compose assoc-any-key? not ; inline
 242
 243 : assoc-all-value? ( ... assoc quot: ( ... value -- ... ? ) -- ... ? )
 244     [ not ] compose assoc-any-value? not ; inline
 245
 246 : any-multi-key? ( assoc -- ? )
 247     [ sequence? ] assoc-any-key? ;
 248
 249 : any-multi-value? ( assoc -- ? )
 250     [ sequence? ] assoc-any-value? ;
 251
 252 : flatten-keys ( assoc -- assoc' )
 253     dup any-multi-key? [ expand-keys-set-at flatten-keys ] when ;
 254
 255 : flatten-values ( assoc -- assoc' )
 256     dup any-multi-value? [ expand-values-set-at flatten-values ] when ;
 257
 258 : intersect-keys-as ( assoc seq exemplar -- elts )
 259   [ [ of ] with ] dip zip-with-as sift-values ; inline
 260
 261 : intersect-keys ( assoc seq -- elts )
 262     over intersect-keys-as ; inline
 263
 264 : values-of ( assoc seq -- seq' )
 265     [ of ] with map ; inline
 266
 267 : counts ( seq elts -- counts )
 268     [ histogram ] dip intersect-keys ;
 269
 270 : histogram-diff ( hashtable1 hashtable2 -- hashtable3 )
 271     [ neg swap pick at+ ] assoc-each
 272     [ 0 > ] filter-values ;
 273
 274 : collect-by-multi! ( ... assoc seq quot: ( ... obj -- ... new-keys ) -- ... assoc )
 275     [ keep swap ] curry rot [
 276         [ push-at-each ] curry compose each
 277     ] keep ; inline
 278
 279 : collect-by-multi ( ... seq quot: ( ... obj -- ... new-keys ) -- ... assoc )
 280     [ H{ } clone ] 2dip collect-by-multi! ; inline
 281
 282
 283 : collect-assoc-by! ( ... assoc input-assoc quot: ( ... key value -- ... key' value' ) -- ... assoc )
 284     rot [ '[ @ swap _ push-at ] assoc-each ] keep ; inline
 285
 286 : collect-assoc-by ( ... input-assoc quot: ( ... key value -- ... key value ) -- ... assoc )
 287     [ H{ } clone ] 2dip collect-assoc-by! ; inline
 288
 289 : collect-key-by! ( ... assoc input-assoc quot: ( ... key value -- ... new-key ) -- ... assoc )
 290     '[ _ keepd ] collect-assoc-by! ; inline
 291
 292 : collect-key-by ( ... input-assoc quot: ( ... key value -- ... new-key ) -- ... assoc )
 293     [ H{ } clone ] 2dip collect-key-by! ; inline
 294
 295 : collect-value-by! ( ... assoc input-assoc quot: ( ... key value -- ... new-key ) -- ... assoc )
 296     '[ _ keep ] collect-assoc-by! ; inline
 297
 298 : collect-value-by ( ... input-assoc quot: ( ... key value -- ... new-key ) -- ... assoc )
 299     [ H{ } clone ] 2dip collect-value-by! ; inline
 300
 301
 302 : collect-assoc-by-multi! ( ... assoc input-assoc quot: ( ... key value -- ... new-keys value' ) -- ... assoc )
 303     rot [ '[ @ swap _ push-at-each ] assoc-each ] keep ; inline
 304
 305 : collect-assoc-by-multi ( ... assoc quot: ( ... key value -- ... new-keys value' ) -- ... assoc )
 306     [ H{ } clone ] 2dip collect-assoc-by-multi! ; inline
 307
 308
 309 : collect-key-by-multi! ( ... assoc input-assoc quot: ( ... key value -- ... new-keys ) -- ... assoc )
 310     '[ _ keepd ] collect-assoc-by-multi! ; inline
 311
 312 : collect-key-by-multi ( ... assoc quot: ( ... key -- ... new-keys ) -- ... assoc )
 313     [ H{ } clone ] 2dip collect-key-by-multi! ; inline
 314
 315
 316 : collect-value-by-multi! ( ... assoc input-assoc quot: ( ... key value -- ... new-keys ) -- ... assoc )
 317     '[ _ keep ] collect-assoc-by-multi! ; inline
 318
 319 : collect-value-by-multi ( ... assoc quot: ( ... value -- ... new-keys ) -- ... assoc )
 320     [ H{ } clone ] 2dip collect-value-by-multi! ; inline
 321
 322 : assoc-operator* ( assoc quot -- alist quot' )
 323     [ >alist ] dip [ first2 swap ] prepose ; inline
 324
 325 : assoc-each* ( ... assoc quot: ( ... value key -- ... ) -- ... )
 326     assoc-operator* each ; inline