!=========================================================================
! Copyright (C) VMware, Inc. 1986-2011.  All Rights Reserved.
!
! $Id: abstractcollbkt.gs,v 1.11 2008-01-09 22:50:07 stever Exp $
!
! Superclass Hierarchy:
!   AbstractCollisionBucket, Array, SequenceableCollection, Collection, Object.
!
!=========================================================================

removeallmethods AbstractCollisionBucket
removeallclassmethods AbstractCollisionBucket

category: 'For Documentation Installation only'
classmethod: AbstractCollisionBucket
installDocumentation

| doc txt |
doc := GsClassDocumentation newForClass: self.

txt := (GsDocText new) details:
'An AbstractCollisionBucket is an Array that is used in a KeyValueDictionary to
 store a collection of key/value pairs for which the keys hash to the same
 value.' .
doc documentClassWith: txt.

txt := (GsDocText new) details:
'A SmallInteger that gives the number of key/value pairs in the bucket.' .
doc documentInstVar: #numElements with: txt.

txt := (GsDocText new) details:
'Methods in this category are obsolete and are provided only for compatibility
 with earlier releases of GemStone.  They will be removed in a future release.'.
doc documentCategory: #'Backward Compatibility' with: txt.

self description: doc.
%

category 'Accessing'
method: AbstractCollisionBucket
keyValueDictionary

"Returns nil.  Only IdentityCollisionBuckets have the keyValueDictionary
 instance variable."

^nil
%

category 'Updating'
method: AbstractCollisionBucket
keyValueDictionary: aDict

"No-op for AbstractCollisionBuckets.  Used only for IdentityCollisionBuckets."
%

category: 'Instance Creation'
classmethod: AbstractCollisionBucket
new: aSize

"Returns an AbstractCollisionBucket with the specified size."

|result|
result := super new: (aSize * 2).
result initialize.
^result
%

category: 'Instance Creation'
classmethod: AbstractCollisionBucket
new

"Returns an AbstractCollisionBucket with a default capacity of four key/value
 pairs."

^ self new: 4
%

category: 'Error Handling'
method: AbstractCollisionBucket
_errorKeyNotFound: aKey

"No key/value pair with given key, 'aKey', was found."

^ self _error: #rtErrKeyNotFound args: #[aKey].
%

category: 'Backward Compatibility'
method: AbstractCollisionBucket
doKeys: aBlock

"Obsolete in GemStone 5.0.  Use the keysDo: method instead."

^ self keysDo: aBlock.
%

category: 'Enumerating'
method: AbstractCollisionBucket
keysDo: aBlock

"For each key/value pair in the receiver, evaluates the one-argument block
 aBlock with the key as the argument.  Returns the receiver."

| aKey |
1 to: self tableSize do: [ :index |
  (aKey := self keyAt: index) ~~ nil ifTrue: [ aBlock value: aKey ]
  ].
%

category: 'Enumerating'
method: AbstractCollisionBucket
valuesDo: aBlock

"For each key/value pair in the receiver, evaluates the one-argument block
 aBlock with the value as the argument.  Returns the receiver."

1 to: self tableSize do: [ :index |
  (self keyAt: index) == nil ifFalse: [ aBlock value: (self valueAt: index) ]
  ].
%

category: 'Enumerating'
method: AbstractCollisionBucket
keysAndValuesDo: aBlock

"For each key/value pair in the receiver, evaluates the two-argument block
 aBlock with the key and value as the arguments.  Returns the receiver."

| aKey |
1 to: self tableSize do: [ :index |
  (aKey := self keyAt: index) ~~ nil 
    ifTrue: [ 
      aBlock value: aKey value: (self valueAt: index)
      ]
  ].
%

category: 'Backward Compatibility'
method: AbstractCollisionBucket
doValues: aBlock

"Obsolete in GemStone 5.0.  Use the valuesDo: method instead."

^ self valuesDo: aBlock.
%

category: 'Removing'
method: AbstractCollisionBucket
removeKey: aKey ifAbsent: aBlock

"Removes the key/value pair having the key aKey.  If aKey is not found,
 returns the result of evaluating the zero-argument block aBlock."

  | keyIndex aValue |

  keyIndex := self searchForKey: aKey.
  keyIndex == nil
    ifFalse: [
      numElements := numElements - 1.
      aValue := self valueAt: keyIndex.
      self at: keyIndex putKey: nil.
      self at: keyIndex putValue: nil.
      ^aValue ]
    ifTrue: [ ^ self _reportKeyNotFound: aKey with: aBlock ]
%

! added for 36675
category: 'Removing'
method: AbstractCollisionBucket
removeKey: aKey otherwise: notFoundValue

"Removes the key/value pair having the key aKey.  If aKey is not found,
 returns the notFoundValue. "

  | keyIndex aValue |

  keyIndex := self searchForKey: aKey.
  keyIndex == nil
    ifFalse: [
      numElements := numElements - 1.
      aValue := self valueAt: keyIndex.
      self at: keyIndex putKey: nil.
      self at: keyIndex putValue: nil.
      ^aValue ]
    ifTrue: [ ^ notFoundValue ]
%


category: 'Removing'
method: AbstractCollisionBucket
_removeKey: aKey 

"Removes the key/value pair having the key aKey.  If aKey is not found,
 generates an error."

  | keyIndex |

  keyIndex := self searchForKey: aKey.
  keyIndex == nil
    ifFalse: [
      numElements := numElements - 1.
      self at: keyIndex putKey: nil.
      self at: keyIndex putValue: nil.
    ]
    ifTrue: [ self _errorKeyNotFound: aKey ]
%

category: 'Accessing'
method: AbstractCollisionBucket
_reportKeyNotFound: aKey with: aBlock

"Private."

aBlock == nil ifTrue:[^ self _errorKeyNotFound: aKey ] .
^aBlock value
%

category: 'Accessing'
method: AbstractCollisionBucket
at: aKey

"Returns the value that corresponds to aKey."

^self at: aKey
    ifAbsent: nil "optimization, errors reported via _reportKeyNotFound"
%

category: 'Accessing'
method: AbstractCollisionBucket
keyAt: index

"Returns the key at the specified index."

^super at: (2 * index - 1)
%

category: 'Accessing'
method: AbstractCollisionBucket
valueAt: index

"Returns the value at the specified index."

^super at: (2 * index)
%

category: 'Accessing'
method: AbstractCollisionBucket
at: aKey ifAbsent: aBlock

"Returns the value that corresponds aKey.  If no such key/value pair exists,
 returns the result of evaluating the zero-argument block aBlock."

  | index |
  index := self searchForKey: aKey.
  index ~~ nil
    ifTrue: [
      ^self valueAt: index ]
    ifFalse: [ ^ self _reportKeyNotFound: aKey with: aBlock ] .
%

category: 'Accessing'
method: AbstractCollisionBucket
tableSize

"Returns the number of key/value pairs in the capacity of the receiver."

^self _basicSize // 2
%

category: 'Accessing'
method: AbstractCollisionBucket
numElements

"Returns value of the numElements instance variable.  (The name numElements
 is provided for compatibility with earlier releases.  The instance method
 size is preferred for new code.)"

^numElements
%

category: 'Accessing'
method: AbstractCollisionBucket
size

"Returns value of the numElements instance variable."

^numElements
%

category: 'Accessing'
method: AbstractCollisionBucket
at: aKey otherwise: aValue

"Returns the value that corresponds to aKey by searching the elements in the
 bucket.  If no such key/value pair exists, returns the given alternate value."

  | index |
  index := self searchForKey: aKey.
  index ~~ nil ifTrue:
    [ ^self valueAt: index ]
  ifFalse:
    [ ^aValue ].
%

category: 'Accessing'
method: AbstractCollisionBucket
keyAt: aKey otherwise: aValue

"Returns the key that corresponds to aKey by searching the elements in the
 bucket.  If no such key/value pair exists, returns the given alternate value."

  | index |
  index := self searchForKey: aKey.
  index ~~ nil ifTrue:
    [ ^self keyAt: index ]
  ifFalse:
    [ ^aValue ].
%

category: 'Updating'
method: AbstractCollisionBucket
at: anIndex putKey: aKey

"Stores the key aKey into the key part of the key/value pair referenced by
 anIndex.  Note that this method overwrites the key value at the given index
 and destroys the ordering of the keys in the receiver.  Returns aKey."

super at: (anIndex * 2) - 1 put: aKey
%

category: 'Updating'
method: AbstractCollisionBucket
at: anIndex putValue: aValue

"Stores the value aValue into the value part of the key/value pair referenced
 by atIndex.  Returns aValue."

super at: (anIndex * 2) put: aValue
%

category: 'Updating'
method: AbstractCollisionBucket
at: aKey put: aValue 

"Stores the aKey/aValue pair in the receiver.   Returns aValue."

^ self at: aKey put: aValue keyValDict: nil.
%

category: 'Updating'
method: AbstractCollisionBucket
at: aKey put: aValue keyValDict: aKeyValDict

"Stores the aKey/aValue pair in the receiver.  Returns aValue."

  | emptySlotIndex startTableSize thisKey |

  "emptySlotIndex initialized to nil by method invocation"
  startTableSize := self tableSize .

  aKey == nil ifTrue:[ ^ self _error: #rtErrNilKey ] .

  "search for aKey, or for the first empty slot "
  1 to: startTableSize do:[:index |
    thisKey := self keyAt: index.
    (self compareKey: aKey with: thisKey) ifTrue:[
      "Key found.  Store given value"
      ^ self at: index putValue: aValue .
      ] .
    emptySlotIndex == nil ifTrue:[
      thisKey == nil ifTrue:[ emptySlotIndex := index ].
      ].
    ] .
  "Key not found so add key and value"
  emptySlotIndex == nil ifTrue:[
    " bucket is full so grow it "
    self size: (self _basicSize + 8 ) .  "accommodate 4 more key,value pairs"
    emptySlotIndex := startTableSize + 1 .
    ] .
  numElements := numElements + 1.
  self at: emptySlotIndex putKey: aKey.
  ^ self at: emptySlotIndex putValue: aValue .
%

category: 'Updating'
method: AbstractCollisionBucket
at: aKey put: aValue keyValDict_coll: aKeyValDict

"Stores the aKey/aValue pair in the receiver.  
 Returns 1 if this at:put: added a new key, 0 if this at:put: 
 replaced the value of an existing key."

  | emptySlotIndex startTableSize thisKey |

  "emptySlotIndex initialized to nil by method invocation"
  startTableSize := self tableSize .

  aKey == nil ifTrue:[ ^ self _error: #rtErrNilKey ] .

  "search for aKey, or for the first empty slot "
  1 to: startTableSize do:[:index |
    thisKey := self keyAt: index.
    (self compareKey: aKey with: thisKey) ifTrue:[
      "Key found.  Store given value"
      self at: index putValue: aValue .
      aKeyValDict _markDirty .
      ^ 0
      ] .
    emptySlotIndex == nil ifTrue:[
      thisKey == nil ifTrue:[ emptySlotIndex := index ].
      ].
    ] .
  "Key not found so add key and value"
  emptySlotIndex == nil ifTrue:[
    " bucket is full so grow it "
    self size: (self _basicSize + 8 ) .  "accommodate 4 more key,value pairs"
    emptySlotIndex := startTableSize + 1 .
    ] .
  numElements := numElements + 1.
  self at: emptySlotIndex putKey: aKey.
  self at: emptySlotIndex putValue: aValue .
  ^ 1
%

category: 'Searching'
method: AbstractCollisionBucket
includesKey: aKey

"Returns true if the receiver contains a key that is equal to 'aKey'.
 Otherwise, returns false."

^(self searchForKey: aKey) ~~ nil
%

category: 'Searching'
method: AbstractCollisionBucket
searchForKey: aKey

"Returns the index of aKey, or if not found, nil."

   aKey == nil ifTrue:[ ^ self _error: #rtErrNilKey ] .
   1 to: self tableSize do: [ :index |
      (self compareKey: aKey with: (self keyAt: index))
         ifTrue: [ ^index ]
      ].
   "Key not found"
   ^nil
%

category: 'Searching'
method: AbstractCollisionBucket
firstPair

"Returns an Association containing the receiver's first key/value pair.
 If the receiver is empty, returns an Association containing nils."

   | aKey |
   numElements == 0 ifFalse: [
      "Search for the first non-nil index"
      1 to: self tableSize do: [ :i |
         (aKey := self keyAt: i) == nil ifFalse: [
            ^Association new key: aKey value: (self valueAt: i) ]]].
   "No first pair was found"
   ^Association newWithKey: nil value: nil
%

category: 'Adding'
method: AbstractCollisionBucket
add: anAssociation

"Adds the key/value pair found in anAssociation to the
 AbstractCollisionBucket."

anAssociation _validateClass: Association.
self at: anAssociation key put: anAssociation value
%

category: 'Initializing'
method: AbstractCollisionBucket
initialize

"Initializes the instance variable of the receiver to be an empty
 CollisionBucket."

numElements := 0.
%

category: 'Private'
method: AbstractCollisionBucket
compareKey: key1 with: key2

"Returns true if key1 is equivalent to key2, and false otherwise."

^ key1 = key2
%

category: 'Formatting'
method: AbstractCollisionBucket
printOn: aStream

"Puts a displayable representation of the receiver on the given stream."

"Copy the implementation from Object so we don't inherit it from Collection."

aStream nextPutAll: self asString
%

category: 'Private'
method: AbstractCollisionBucket
_removeAll

"Dereferences the receiver from its parent and shrinks the receiver.
 Used while rebuilding a KeyValueDictionary."

numElements := 0.
self size: 0 
%

! deleted _canonicalizeSymbolAt: offset oldSymbol: oldSym newSymbol: newSym

