src/core/dictionary.slate

   1 collections define: #Dictionary &parents: {Set. Mapping} &slots: {#values -> (Array newSize: 10)}.
   2
   3 Set identityHash.
   4 Mapping identityHash.
   5 Dictionary identityHash.
   6
   7 "Dictionary uses two separate arrays to store its keys and values; it behaves
   8 as a Set of key-value pairs (but doesn't store Associations as in Smalltalk)."
   9 "Stores the associated values for the array's objects which are the keys.
  10 The correspondence is per-index, and there can obviously be only one value
  11 per key."
  12
  13 d@(Dictionary traits) copy
  14 [resend `>> [values := d values copy. ]].
  15
  16 d@(Dictionary traits) new &capacity: n
  17 [
  18   resend `>>
  19     [| :newD |
  20      values := d values new &capacity: ((n ifNil: [0]) max: newD contents size). ]
  21 ].
  22
  23 d@(Dictionary traits) newFrom: keys@(Sequence traits) to: values@(Sequence traits)
  24 [
  25   result ::= d new &capacity: (keys size min: values size).
  26   keys with: values do: #(result at: _ put: _) `er.
  27   result
  28 ].
  29
  30 collections IdentityDictionary ::= Dictionary copy `>>
  31   [hashBlock := #identityHash`er.
  32    equalsBlock := #==`er. ].
  33 "IdentityDictionary is an alternate prototype Dictionary using ==-based
  34 comparison and hashing."
  35
  36 d@(Dictionary traits) acceptsKey: _@Nil
  37 [False].
  38
  39 d@(Dictionary traits) = e@(Dictionary traits)
  40 [
  41   d == e
  42    \/ [d size = e size
  43          /\ [d keysAndValuesDo:
  44                [| :key :value |
  45                 (e at: key ifAbsent: [^ False]) = value ifFalse: [^ False]].
  46              True]]
  47 ].
  48
  49 d@(Dictionary traits) clear
  50 [
  51   resend.
  52   d values clear.
  53   d
  54 ].
  55
  56 d@(Dictionary traits) includes: obj
  57 "Returns whether the Dictionary includes the object as a value."
  58 [
  59   (d detect: [| :each | d equalsBlock apply*, obj, each]) isNotNil
  60 ].
  61
  62 d@(Dictionary traits) includesIdentity: obj
  63 "Returns whether the object is identical to some keyed value."
  64 [
  65   (d detect: [| :each | obj == each]) isNotNil
  66 ].
  67
  68 d@(Dictionary traits) occurrencesOf: obj
  69 "The number of indexed values equal to obj."
  70 [| count |
  71   count := 0.
  72   d do: [| :each | (d equalsBlock apply*, obj, each)
  73     ifTrue: [count += 1]].
  74   count
  75 ].
  76
  77 d@(Dictionary traits) addAll: map@(Mapping traits)
  78 "Adds all of the key-value pairs to the Dictionary. Notice that this works
  79 for any Mapping, but that other collections will not do."
  80 [
  81   d == map ifFalse:
  82     [map keysAndValuesDo: #(d at: _ put: _) `er].
  83   map
  84 ].
  85
  86 d@(Dictionary traits) addAll: seq@(Sequence traits)
  87 [
  88   seq doWithIndex: [| :assoc :index |
  89     (assoc isSameAs: Association)
  90       ifTrue: [d add: assoc]
  91       ifFalse: [d at: index put: assoc]].
  92   seq
  93 ].
  94
  95 d@(Dictionary traits) declare: key from: e@(Dictionary traits)
  96 "Add key to d, unless the key already exists. Remove key from e
  97 and move its association to d."
  98 [
  99   (d includesKey: key) ifFalse:
 100     [(e includesKey: key)
 101        ifTrue: [d add: (e associationAt: key).
 102                 e removeKey: key]
 103        ifFalse: [d add: key -> Nil]].
 104   d
 105 ].
 106
 107 d@(Dictionary traits) associationAt: key ifAbsent: block
 108 [
 109   (d contents at: (index ::= d scanFor: key))
 110     ifNil: [block do]
 111     ifNotNil: [(d contents at: index) -> (d values at: index)]
 112 ].
 113
 114 d@(Dictionary traits) associationAt: key
 115 [
 116   d associationAt: key ifAbsent: [key keyNotFoundOn: d]
 117 ].
 118
 119 d@(Dictionary traits) at: key ifAbsent: block
 120 [
 121   (d contents at: (index ::= d scanFor: key))
 122     ifNil: [block do]
 123     ifNotNil: [d values at: index]
 124 ].
 125
 126 d@(Dictionary traits) add: assoc@(Association traits)
 127 "Adds a new key value pair to the Dictionary from an assocation.
 128 For example: Dictionary new `>> [ add: 'first' -> 'Joe Henry'. ]."
 129 [
 130   d at: assoc key put: assoc value.
 131   assoc
 132 ].
 133
 134 d@(Dictionary traits) at: key put: obj
 135 [
 136   (d contents at: (index ::= d scanFor: key)) ifNil:
 137     [d contents at: index put: key.
 138      d tally += 1].
 139   d values at: index put: obj.
 140   d fullCheck.
 141   obj
 142 ].
 143
 144 d@(Dictionary traits) acceptsKey: _@Nil [False].
 145 d@(Dictionary traits) at: _@Nil put: obj
 146 [error: 'Dictionary cannot accept Nil keys.'].
 147 "TODO: extend Dictionary to handle Nil keys."
 148
 149 d@(Dictionary traits) keyAtValue: obj ifAbsent: block
 150 [
 151   d keysAndValuesDo: [| :key :value |
 152       (d equalsBlock apply*, obj, value) ifTrue: [^ key]].
 153   block do
 154 ].
 155
 156 d@(Dictionary traits) keyAtIdentityValue: obj ifAbsent: block
 157 [
 158   d values doWithIndex: [| :each :index | each == obj
 159     ifTrue: [^ (d contents at: index)]].
 160   block do
 161 ].
 162
 163 d@(Dictionary traits) keyAtIdentityValue: obj
 164 [
 165   d keyAtIdentityValue: obj ifAbsent: [obj elementNotFoundOn: d]
 166 ].
 167
 168 d@(Dictionary traits) keySet
 169 [
 170   result ::= Set newSizeOf: d.
 171   result equalsBlock := d equalsBlock.
 172   d keysDo: #(result add: _) `er.
 173   result
 174 ].
 175
 176 d@(Dictionary traits) keys [d keySet].
 177
 178 d@(Dictionary traits) valueSet
 179 [
 180   result ::= Set newSizeOf: d.
 181   result equalsBlock := d equalsBlock.
 182   d valuesDo: #(result add: _) `er.
 183   result
 184 ].
 185
 186 d@(Dictionary traits) values [d valueSet].
 187
 188 d@(Dictionary traits) keysAndValuesDo: block
 189 [
 190   d isEmpty ifFalse:
 191     [d contents doWithIndex:
 192        [| :each :index |
 193         each ifNotNil: [block apply*, each, (d values at: index)]]]
 194 ].
 195
 196 d@(Dictionary traits) keysDo: block
 197 [
 198   d isEmpty ifFalse:
 199     [d contents doWithIndex:
 200        [| :each :index | each ifNotNil: [block apply*, each]]]
 201 ].
 202
 203 d@(Dictionary traits) valuesDo: block
 204 [
 205   d isEmpty ifFalse:
 206     [d contents doWithIndex:
 207        [| :each :index | each ifNotNil: [block apply*, (d values at: index)]]]
 208 ].
 209
 210 d@(Dictionary traits) keysAndValuesRemove: block
 211 "Removes key-value pairs that satisfy the two-argument block."
 212 [
 213   removals ::= ExtensibleArray new.
 214   d keysAndValuesDo: [| :key :value | (block apply*, key, value)
 215       ifTrue: [removals add: key]].
 216   removals do: #(d removeKey: _) `er.
 217   d
 218 ].
 219
 220 d@(Dictionary traits) removeKey: key ifAbsent: block
 221 [
 222   (index ::= d scanFor: key)
 223     ifNil: [^ block do].
 224   value ::= d contents at: index.
 225   d contents at: index put: Nil.
 226   d values at: index put: Nil.
 227   d tally -= 1.
 228   d fixCollisionsFrom: index.
 229   value
 230 ].
 231
 232 d@(Dictionary traits) removeKey: key
 233 [
 234   d removeKey: key ifAbsent: [key keyNotFoundOn: d]
 235 ].
 236
 237 d@(Dictionary traits) remove: key
 238 [
 239   d removeKey: key
 240 ].
 241
 242 d@(Dictionary traits) remove: key ifAbsent: block
 243 [
 244   d removeKey: key ifAbsent: block
 245 ].
 246
 247 d@(Dictionary traits) associationsDo: block
 248 [
 249   d isEmpty ifFalse:
 250     [d contents doWithIndex:
 251        [| :each :index | each ifNotNil:
 252           [block apply*, (each -> (d values at: index))]]]
 253 ].
 254
 255 d@(Dictionary traits) do: block
 256 "Applies a single-argument block to each keyed value in the Dictionary.
 257 Equivalent to valuesDo:."
 258 [d valuesDo: block].
 259
 260 d mapSelect: block into: result@(Dictionary traits)
 261 "Filter the dictionary by values satisfying a block."
 262 [d keysAndValuesDo:
 263   [| :key :value | (block apply*, key, value)
 264       ifTrue: [result noCheckAt: key put: value]].
 265   result
 266 ].
 267
 268 d select: block into: result@(Dictionary traits)
 269 [d mapSelect: [| :_ :value | block apply*, each] into: result].
 270
 271 d@(Dictionary traits) collect: block
 272 "Generate a new collection based on applying the block to each value."
 273 [
 274   result ::= ExtensibleArray new.
 275   d do: [| :each | result add: (block apply*, each)].
 276   result
 277 ].
 278
 279 d@(Dictionary traits) swap: index1 with: index2
 280 [
 281   d contents swap: index1 with: index2.
 282   d values swap: index1 with: index2.
 283   d
 284 ].
 285
 286 d@(Dictionary traits) noCheckAt: key put: value
 287 [
 288   index ::= d scanFor: key.
 289   d contents at: index put: key.
 290   d values at: index put: value.
 291   d tally += 1.
 292 ].
 293
 294 d@(Dictionary traits) noCheckAdd: assoc
 295 [
 296   d noCheckAt: assoc key put: assoc value
 297 ].
 298
 299 d@(Dictionary traits) growBy: growthAmount
 300 [
 301   tempDict ::= d new &capacity: d contents size + growthAmount.
 302   d keysAndValuesDo: #(tempDict noCheckAt: _ put: _) `er.
 303   d contents := tempDict contents.
 304   d values := tempDict values.
 305   d
 306 ].
 307
 308 d@(Dictionary traits) rehash
 309 [
 310   tempDict ::= d newSameSize.
 311   d keysAndValuesDo: #(tempDict noCheckAt: _ put: _) `er.
 312   d contents := tempDict contents.
 313   d values := tempDict values.
 314   d
 315 ].
 316
 317 d@(Dictionary traits) scanFor: obj
 318 "Scans the key array for the first empty slot or an element matching the
 319 object. Returns the index at which the object is used as a key, or Nil if
 320 it's not found and the Dictionary is full."
 321 [| key |
 322   end ::= d contents size.
 323   start ::= ((d hashBlock apply*, obj) \\ end) + 1.
 324   block ::=
 325     [| :index |
 326      (key := d contents at: index) isNil \/
 327        [d equalsBlock apply*, obj, key]
 328        ifTrue: [^ index]].
 329   start below: end do: block.
 330   0 below: start do: block.
 331   Nil
 332 ].
 333
 334 x@(Root traits) slotNamesAndValues
 335 "Answers a Dictionary of the slot names and values from the argument."
 336 [
 337   result ::= Dictionary new.
 338   x slotNamesAndValuesDo: #(result at: _ put: _) `er.
 339   result
 340 ].