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

! IdentityCollisionBucket created in bom.c

! remove existing behavior from IdentityCollisionBucket
removeallmethods IdentityCollisionBucket
removeallclassmethods IdentityCollisionBucket

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

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

txt := (GsDocText new) details:
'An IdentityCollisionBucket is a CollisionBucket that is used in an
 IdentityKeyValueDictionary to store a collection of key/value pairs for which
 the keys hash to the same value.  It provides support for the identity
 comparisons required by IdentityKeyValueDictionaries.  The bucket is
 sorted by the identity of the keys. ' .
doc documentClassWith: txt.

self description: doc.
%

! ------------------- Class methods for IdentityCollisionBucket

category: 'Instance Creation'
classmethod: IdentityCollisionBucket
new

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

^ self new: 0
%

! ------------------- Instance methods for IdentityCollisionBucket

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

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

^ key1 == key2
%

category: 'Searching'
method: IdentityCollisionBucket
searchForKey: aKey

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

"Does a binary search."

<primitive: 391>
aKey == nil ifTrue:[ ^ self _error: #rtErrNilKey ] .
self _primitiveFailed: #searchForKey:
%

category: 'Searching'
method: IdentityCollisionBucket
binarySearchForInsertKey: aKey

"Returns the negated index of aKey if found, or the offset at which to
 insert aKey."

"Does a binary search."

<primitive: 448>
aKey == nil ifTrue:[ ^ self _error: #rtErrNilKey ] .
self _primitiveFailed: #binarySearchForInsertKey:
%

category: 'Private'
method: IdentityCollisionBucket
_validateSortedKeys

"Private."

| prevOop thisOop |
prevOop := 0 .
1 to: numElements * 2 by: 2 do:[:j |
   thisOop := (self basicAt: j) asOop .
   thisOop <= prevOop 
      ifTrue:[ self _halt:'IdentityCollisionBucket not sorted' ].
   prevOop := thisOop 
   ].
%

category: 'Private'
method: IdentityCollisionBucket
at: aKey put: aValue keyValDict: aKeyValDict

"Private.  Adds the key-value pair (aKey, aValue) to the collision bucket.
 Returns aValue ."

| marker |

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

marker := self binarySearchForInsertKey: aKey.
marker < 0 ifTrue:[ "replace existing key" 
  self at: marker negated putValue: aValue.
  ^ aValue
  ].
(numElements >= 974) ifTrue:[
  aKeyValDict _rebuild.
  aKeyValDict at: aKey put: aValue .
  ^ aValue
  ].
self insertAt: marker key: aKey value: aValue. 
^ aValue
%

category: 'Private'
method: IdentityCollisionBucket
at: aKey put: aValue keyValDict_coll: aKeyValDict

"Private.  Adds the key-value pair (aKey, aValue) to the collision bucket.
 Returns 1 if this at:put: added a new key, 0 if this at:put:
 replaced the value for an existing  key .  "

| marker |

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

marker := self binarySearchForInsertKey: aKey.
marker < 0 ifTrue:[ "replace existing key" 
  self at: marker negated putValue: aValue.
  aKeyValDict _markDirty .
  ^ 0
  ].
(numElements >= 974) ifTrue:[
  aKeyValDict _rebuild.
  aKeyValDict at: aKey put: aValue .
  ^ 0
  ].
self insertAt: marker key: aKey value: aValue. 
^ 1
%

category: 'Private'
method: IdentityCollisionBucket
insertAt: marker key: aKey value: aValue

"Private.  Inserts the given key-value pair (aKey, aValue) at the
 position marker."

  self insertAll: #[ aKey, aValue ] at: (marker * 2 - 1).
  numElements := numElements + 1.
  ^ self.
%

category: 'Removing'
method: IdentityCollisionBucket
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 valueOffset aValue |
  keyIndex := self searchForKey: aKey.
  keyIndex == nil
    ifFalse: [
      numElements := numElements - 1.
      aValue := self valueAt: keyIndex.
      valueOffset := keyIndex * 2 .
      self removeFrom: valueOffset - 1 to: valueOffset .
      ^aValue 
      ]
    ifTrue: [ ^ self _reportKeyNotFound: aKey with: aBlock ]
%

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

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

  | keyIndex valueOffset aValue |
  keyIndex := self searchForKey: aKey.
  keyIndex == nil
    ifFalse: [
      numElements := numElements - 1.
      aValue := self valueAt: keyIndex.
      valueOffset := keyIndex * 2 .
      self removeFrom: valueOffset - 1 to: valueOffset .
      ^aValue
      ]
    ifTrue: [ ^ notFoundValue ].
%


