extra/assocs/extras/extras.factor

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