collections addPrototype: #Dictionary derivedFrom: {Set. Mapping}.
"Dictionary uses two separate arrays to store its keys and values; it behaves
as a Set of key-value pairs (but doesn't store Associations as in Smalltalk)."
Dictionary addSlot: #values valued: (Array newSize: 10).
"Stores the associated values for the array's objects which are the keys.
The correspondence is per-index, and there can obviously be only one value
per key."

d@(Dictionary traits) copy
[| newD |
  newD: resend.
  newD values: d values copy.
  newD
].

d@(Dictionary traits) newSize: n
[| newD |
  newD: resend.
  newD values: (d values newSizeOf: newD contents).
  newD
].

collections addSlot: #IdentityDictionary valued: Dictionary copy.
"IdentityDictionary is an alternate prototype Dictionary using ==-based
comparison and hashing."
IdentityDictionary hashBlock: [| :obj | obj identityHash].
IdentityDictionary equalsBlock: [| :a :b | a == b].

d@(Dictionary traits) acceptsKey: _@Nil
[False].

d@(Dictionary traits) = e@(Dictionary traits)
[
  d == e or:
    [d size = e size and:
      [d keysAndValuesDo:
	[| :key :value |
	   ((e at: key ifAbsent: [^ False]) = value) ifFalse: [^ False]].
       True]]
].

d@(Dictionary traits) includes: obj
"Returns whether the object is equal to some keyed value."
[
  (d detect: [| :each | d equalsBlock applyWith: obj with: each]) isNotNil
].

d@(Dictionary traits) includesIdentity: obj
"Returns whether the object is identical to some keyed value."
[
  (d detect: [| :each | obj == each]) isNotNil
].

d@(Dictionary traits) includesKey: key
[
  d at: key ifAbsent: [^ False].
  True
].

d@(Dictionary traits) occurrencesOf: obj
"The number of indexed values equal to obj."
[| count |
  count: 0.
  d do: [| :each | (d equalsBlock applyWith: obj with: each)
    ifTrue: [count: count + 1]].
  count
].

d@(Dictionary traits) atNewIndex: index put: assoc
[
  d contents at: index put: assoc key.
  d values at: index put: assoc value.
  d tally: d tally + 1.
  d fullCheck.
  d
].

d@(Dictionary traits) add: assoc
[| index element |
  index: (d scanFor: assoc key).
  (element: (d contents at: index))
    ifNil: [d atNewIndex: index put: assoc]
    ifNotNil: [d values at: index put: assoc value].
  assoc
].

d@(Dictionary traits) addAll: map@(Mapping traits)
"Adds all of the key-value pairs to the Dictionary. Notice that this works
for any Mapping, but that other collections will not do."
[
  d == map ifFalse:
    [map keysAndValuesDo: [| :key :value | d at: key put: value]].
  map
].

d@(Dictionary traits) declare: key from: e@(Dictionary traits)
"Add key to d, unless the key already exists. Remove key from e
and move its association to d."
[
  (d includesKey: key) ifTrue: [^ d].
  (e includesKey: key)
    ifTrue: [d add: (e associationAt: key).
        e removeKey: key]
    ifFalse: [d add: key -> Nil]
  d
].

d@(Dictionary traits) associationAt: key ifAbsent: block
[| index |
  index: (d scanFor: key).
  (d contents at: index)
    ifNil: [block do]
    ifNotNil: [(d contents at: index) -> (d values at: index)]
].

d@(Dictionary traits) associationAt: key
[
  d associationAt: key ifAbsent: [key keyNotFoundOn: d]
].

d@(Dictionary traits) at: key ifAbsent: block
[| index |
  index: (d scanFor: key).
  index ifNil: [^ block do].
  (d contents at: index)
    ifNil: [block do]
    ifNotNil: [d values at: index]
].

d@(Dictionary traits) at: key put: obj
[| index |
  index: (d scanFor: key).
  (d contents at: index) ifNil:
    [d contents at: index put: key.
     d tally: d tally + 1].
  d values at: index put: obj.
  d fullCheck.
  obj
].

d@(Dictionary traits) keyAtValue: obj ifAbsent: block
[
  d keysAndValuesDo: [| :key :value |
      (d equalsBlock applyWith: obj with: value) ifTrue: [^ key]].
  block do
].

d@(Dictionary traits) keyAtIdentityValue: obj ifAbsent: block
[
  d values doWithIndex: [| :each :index | each == obj
    ifTrue: [^ (d contents at: index)]].
  block do
].

d@(Dictionary traits) keyAtIdentityValue: obj
[
  d keyAtIdentityValue: obj ifAbsent: [obj elementNotFoundOn: d]
].

d@(Dictionary traits) keySet
[| keySet |
  keySet: (Set newSizeOf: d).
  d keysDo: [| :key | keySet add: key].
  keySet
].

d@(Dictionary traits) valueSet
[| out |
  out: (Set newSizeOf: d).
  d valuesDo: [| :value | out add: value].
  out
].

d@(Dictionary traits) keysAndValuesDo: block
[
  d isEmpty ifTrue: [^ d].
  d contents doWithIndex:
    [| :each :index | each ifNotNil:
      [block applyWith: each with: (d values at: index)]]
].

d@(Dictionary traits) keysDo: block
[
  d isEmpty ifTrue: [^ d].
  d contents doWithIndex:
    [| :each :index | each ifNotNil: [block applyWith: each]]
].

d@(Dictionary traits) valuesDo: block
[
  d isEmpty ifTrue: [^ d].
  d contents doWithIndex:
    [| :each :index | each ifNotNil: [block applyWith: (d values at: index)]]
].

d@(Dictionary traits) keysAndValuesRemove: block
"Removes key-value pairs that satisfy the two-argument block."
[| removals |
  removals: ExtensibleArray newEmpty.
  d keysAndValuesDo: [| :key :value | (block applyWith: key with: value)
      ifTrue: [removals add: key]].
  removals do: [| :each | d removeKey: each].
  d
].

d@(Dictionary traits) removeKey: key ifAbsent: block
[| index value |
  index: (d scanFor: key).
  index ifNil: [^ block do].
  d contents at: index put: Nil.
  d values at: index put: Nil.
  d tally: d tally - 1.
  d fixCollisionsFrom: index.
  value
].

d@(Dictionary traits) removeKey: key
[
  d removeKey: key ifAbsent: [key keyNotFoundOn: d]
].

d@(Dictionary traits) remove: key
[
  d removeKey: key
].

d@(Dictionary traits) remove: key ifAbsent: block
[
  d removeKey: key ifAbsent: block
].

d@(Dictionary traits) associationsDo: block
[
  d isEmpty ifTrue: [^ d].
  d contents doWithIndex:
    [| :each :index | each ifNotNil:
      [block applyWith: each -> (d values at: index)]]
].

d@(Dictionary traits) do: block
"Equivalent to valuesDo:."
[d valuesDo: block].

d@(Dictionary traits) select: block
"Filter the dictionary by values satisfying a block."
[| newCol |
  newCol: d newEmpty.
  d keysAndValuesDo:
    [| :key :value | (block applyWith: (values at: index))
	      ifTrue: [newCol noCheckAt: key put: value]].
  newCol
].

d@(Dictionary traits) collect: block
"Generate a new collection based on applying the block to each value."
[| result |
  result: ExtensibleArray newEmpty.
  d do: [| :each | result add: (block applyWith: each)].
  result
].

d@(Dictionary traits) swap: index1 with: index2
[
  d contents swap: index1 with: index2.
  d values swap: index1 with: index2.
  d
].

d@(Dictionary traits) noCheckAt: key put: value
[| index |
  index: (d scanFor: key).
  d contents at: index put: key.
  d values at: index put: value.
  d tally: d tally + 1.
  d
].

d@(Dictionary traits) noCheckAdd: assoc
[
  d noCheckAt: assoc key put: assoc value
].

d@(Dictionary traits) grow
[| tempDict |
  tempDict: (d newSize: d contents size + d growSize).
  d keysAndValuesDo: [| :key :value | tempDict noCheckAt: key put: value].
  d contents: tempDict contents.
  d values: tempDict values.
  d
].

d@(Dictionary traits) rehash
[| tempDict |
  tempDict: d newSameSize.
  d keysAndValuesDo: [| :key :value | tempDict noCheckAt: key put: value].
  d contents: tempDict contents.
  d values: tempDict values.
  d
].

d@(Dictionary traits) scanFor: obj
"Scans the key array for the first empty slot or an element matching the
object. Returns the index at which the object is used as a key, or Nil if
it's not found and the Dictionary is full."
[| key start end block |
  end: d contents size.
  start: ((d hashBlock applyWith: obj) \\ end) + 1.
  block: [| :index |
      ((key: (d contents at: index)) isNil or:
          [d equalsBlock applyWith: obj with: key])
        ifTrue: [^ index]].
  start below: end do: block.
  0 below: start do: block.
  Nil
].