" Smalltalk/Set.st							-*- Smalltalk -*- "

Set : Collection ( tally array )

Set new: size
[
    self := self _clone.
    tally := 0.
    array := Array new: size.
]

Set size
[
    ^tally
]

Set add: newObject
[
    | index |
    newObject isNil ifTrue: [ self error: 'Sets cannot meaningfully contain nil as an element' ].
    index := self findElementOrNil: newObject.
    (array at: index) isNil ifTrue: [ self atNewIndex: index put: newObject ].
    ^newObject
]

Set findElementOrNil: anObject
[
    " Answer the index of a first slot containing either a nil
      (indicating an empty slot) or an element that matches the given
      object.  Answer the index of that slot or zero.  Fail if neither
      a match nor an empty slot is found. "
    | index |
    index := self scanFor: anObject.
    index < 0 ifTrue: [ self error: 'there is no free space in this set' ].
    ^index
]

Set scanFor: anObject
[
    " Scan the array for the first slot containing either a nil
      (indicating an empty slot) or an element that matches anObject.
      Answer the index of that slot or -1 if no slot is found.  This
      method will be overridden in various subclasses that have
      different interpretations for matching elements. "
    | finish start element |
    finish := array size.
    start := anObject hash \\ finish.
    " search from (hash mod size) to the end "
    start to: finish - 1 do:
      [ :index |
        element := array at: index.
        (element isNil or: [element = anObject]) ifTrue: [ ^index ] ].
    " search from start to (hash mod size) "
    0 to: start - 1 do:
      [ :index |
        element := array at: index.
        (element isNil or: [element = anObject]) ifTrue: [ ^index ] ].
    ^-1 " no match AND no empty slot "
]

Set atNewIndex: index put: anObject
[
    array at: index put: anObject.
    tally := tally + 1.
    self fullCheck
]

Set fullCheck
[
    " Keep array at least 1/4 free for decent hash behavior. "
    (array size - tally) < (1 max: (array size // 4)) ifTrue: [self grow]
]

Set growSize
[
    ^3 max: array size + 1
]

Set grow
[
    " Grow the elements array and reinsert the old elements. "
    | oldElements oldSize |
    oldElements := array.
    oldSize := array size.
    array := Array new: oldSize + self growSize.
    tally := 0.
    oldElements do: [:element | element isNil ifFalse: [self noCheckAdd: element]]
]

Set noCheckAdd: anObject
[
    array at: (self findElementOrNil: anObject) put: anObject.
    tally := tally + 1
]

Set do: unaryBlock
[
    tally = 0 ifFalse: [array do: [:element | element isNil ifFalse: [unaryBlock value: element]]]
]

Set like: anObject
[
    | index |
    index := self scanFor: anObject.
    ^index < 0 ifFalse: [array at: index]
]