!=========================================================================
! Copyright (C) VMware, Inc. 1986-2011.  All Rights Reserved.
!
! $Id: btreeleaf.gs,v 1.18 2008-01-09 22:50:08 stever Exp $
!
! Superclass Hierarchy:
!   BtreeLeafNode, BtreeNode, Array, SequenceableCollection, Collection,
!   Object.
!
!=========================================================================

! class created in idxclasses.topaz

removeallmethods BtreeLeafNode
removeallclassmethods BtreeLeafNode

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


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

txt := (GsDocText new) details:
'A BtreeLeafNode represents an exterior node of a B-tree.' .
doc documentClassWith: txt.

self description: doc.
%

category: 'Comparison Operators'
method: BtreeLeafNode
_compareValueOop: aValue greaterThanEntryValueOopAt: index 

""

^ aValue asOop > (super at: (index - 1)) asOop
%

category: 'Comparison Operators'
method: BtreeLeafNode
_compareValueOop: aValue lessThanOrEqualToEntryValueOopAt: index 

""

^ aValue asOop <= (super at: (index - 1)) asOop
%

category: 'Comparison Operators'
method: BtreeLeafNode
_compareKey: aKey value: aValue equalToEntryAt: index 

"Performs a = comparison between aKey and the entry whose key is at the given
 index.  If the keys are equal, use the OOP of the value as the next basis for
 comparison.  The default implementation uses no encryption."

^ (aKey _idxForSortEqualTo: (super at: index)) _and:
   [ aValue asOop == (super at: (index - 1)) asOop ]
%

category: 'Comparison Operators'
method: BtreeLeafNode
_compareKey: aKey value: aValue lessThanOrEqualToEntryAt: index

"Performs a <= comparison between aKey and the entry whose key is at the given
 index.  If the keys are equal, then use the OOP of the value for the
 comparison.  The default implementation uses no encryption."

" first compare the keys "
( aKey _idxForSortLessThan: (super at: index) )
    ifTrue: [ ^ true ].

" if the keys are equal, use the OOP of the value "
(aKey _idxForSortEqualTo: (super at: index))
    ifTrue: [ ^ aValue asOop <= (super at: (index - 1)) asOop ].

^ false
%

category: 'Comparison Operators'
method: BtreeLeafNode
_compareKey: aKey value: aValue lessThanEntryAt: index

"Performs a < comparison between aKey and the entry whose key is at the given
 index.  If the keys are equal, then use the OOP of the value for the
 comparison.  The default implementation uses no encryption."

" first compare the keys "
( aKey _idxForSortLessThan: (super at: index) )
    ifTrue: [ ^ true ].

^ false
%

category: 'Comparison Operators'
method: BtreeLeafNode
_compareKey: aKey value: aValue greaterThanEntryAt: index

"Performs a > comparison between aKey and the entry whose key is at the given
 index.  If the keys are equal, then use the OOP of the value for the
 comparison.  The default implementation uses no encryption."

" first compare the keys "
( aKey _idxForSortGreaterThan: (super at: index) )
    ifTrue: [ ^ true ].

^ false
%

category: 'Searching'
method: BtreeLeafNode
_findAllValuesForKey: aKey into: aCollection using: aComparison

"Finds all the values for the given key, placing them in the collection.  For
 leaf nodes, must first find the appropriate entry, then iterate through
 successive entries until we reach the end or a key does not match."

| index eSize maxIndex |
" find first entry that might contain the key "
index := self _findCoveringIndexForKey: aKey totalOrder: false.
index == 0 ifTrue: [ ^ self ].

eSize := self entrySize.
maxIndex := self _lastIndex.

" now scan entries until reach the end or no match using sort ="
[ (index < maxIndex) _and:
[ self _compare: aComparison key: aKey equalToEntryAt: (index + 1) ] ] whileTrue: [
    aCollection add: (super at: index).
    index := index + eSize
]
%

category: 'Searching'
method: BtreeLeafNode
_findAllValuesForIdenticalKey: aKey into: aCollection using: aComparison

"Finds all the values for the given identical key, placing them in the
 collection.  For leaf nodes, must first find the appropriate entry, then
 iterate through successive entries until we reach the end or a key does
 not match.  Return whether the last key was equal or not (so the caller
 knows it must check the next leaf node)."

| index eSize maxIndex |
" find first entry that might contain the key "
index := self _findCoveringIndexForKey: aKey totalOrder: false.
index == 0 ifTrue: [ ^ false ].

eSize := self entrySize.
maxIndex := self _lastIndex.

" now scan entries until reach the end or no match using sort ="
[ (index < maxIndex) _and:
[ self _compare: aComparison key: aKey equalToEntryAt: index + 1 ] ] whileTrue: [
  (aKey == (super at: index + 1))
    ifTrue: [ aCollection add: (super at: index) ].
  index := index + eSize
].
^ index >= maxIndex
%

category: 'Searching Support'
method: BtreeLeafNode
_findAllValuesGreaterThanKey: aKey into: anArray using: aComparison

"Puts into anArray the index and the leaf node of the entry that is greater
 than the given key.  Returns true if a value was found, false otherwise."

| index eSize lastIndex |
numElements == 0
    ifTrue: [ ^ false ].
lastIndex := self _lastKeyIndex.

" find index where the key would be inserted "
index := self _findCoveringIndexForKey: aKey totalOrder: false.
index == 0
    ifTrue: [ ^false ].

"skip keys that sort ="
eSize := self entrySize.
[ self _compare: BtreeComparisonForSort key: aKey equalToEntryAt: index + 1 ] whileTrue: [
    index := index + eSize.
    index > lastIndex ifTrue: [ ^ false ]
].

aKey ~~ nil
  ifTrue: [
    "bugfix 33805 - verify that aKey < index entry"
    (self _compare: BtreeComparisonForSort key: aKey lessThanEntryAt: index + 1)
      ifFalse: [ ^false ].
  ].

anArray addLast: index.
anArray addLast: self.

^ true
%

category: 'Searching Support'
method: BtreeLeafNode
_findAllValuesLessThanKey: aKey into: anArray using: aComparison

"Puts into anArray the index and the leaf node of the entry that is less than
 the given key.  Returns true if a value was found, false otherwise."

| index eSize lastIndex |
numElements == 0
  ifTrue: [ ^ false ].

lastIndex := self _lastIndex.

" first see if all entries are > aKey "
(self _compare: BtreeComparisonForSort key: aKey lessThanOrEqualToEntryAt: self _lastKeyIndex)
  ifFalse: [ 
    "bugfix 33805 - verify that aKey is > index entry"
    ((aKey == nil) _or: [self _compare: aComparison key: aKey greaterThanEntryAt: self _lastKeyIndex])
      ifTrue: [
        " if so, put the rightmost leaf entry in the Array "
        self _putLastIndexOfLastChildInto: anArray.
        ^ true
    ].
  ].
" find index where the key would be inserted "
index := self _findCoveringIndexForKey: aKey totalOrder: false.

" if index == 0, found no entryes"
index == 0 ifTrue: [^ false ].

" if index == 1, check if any are < aKey "
index == 1
  ifTrue: [
    " if the first entry is greater than or equal to aKey, none satisfy "
    ( (self _compare: BtreeComparisonForSort key: aKey lessThanEntryAt: 2) _or:
       [self _compare: BtreeComparisonForSort key: aKey equalToEntryAt: 2])
      ifTrue: [ ^ false ]
  ].

eSize := self entrySize.

" subtract an entry to point to a valid 'less than' entry "
index > 1 ifTrue: [ index := index - eSize ].

aKey ~~ nil 
  ifTrue: [
    "bugfix 33805 - verify that index aKey is > entry"
    (self _compare: BtreeComparisonForSort key: aKey greaterThanEntryAt: index + 1)
      ifFalse: [ 
            (self _compare: aComparison key: aKey equalToEntryAt: index + 1)
              ifTrue: [ ^false].
            (self _compare: aComparison key: aKey lessThanEntryAt: index + 1)
              ifFalse: [ ^false ].
      ].
   ].

anArray addLast: index.
anArray addLast: self.

^ true
%

category: 'Searching Support'
method: BtreeLeafNode
_findAllValuesLessThanKey: aKey andEquals: aBoolean into: anArray using: aComparison

"Puts into anArray the index and the leaf node of the entry that is less than
 (or less than and equal to if aBoolean is true) the given key.  Returns true
 if a value was found, false otherwise."

numElements == 0
    ifTrue: [ ^ false ].

aBoolean 
  ifFalse: [ ^self  _findAllValuesLessThanKey: aKey into: anArray using: aComparison].

(self _findAllValuesGreaterThanKey: aKey into: anArray using: aComparison)
  ifTrue: [
    | eSize index |
    eSize := self entrySize.
    index := anArray at: 1.
    index > eSize
      ifTrue: [ 
        "move index pointer for first greater than entry to first less than or equal to entry"
        index := index - eSize.
        anArray at: 1 put: index.
      ]
      ifFalse: [ 
         "first entry is greater than, so no entries are less than or equal"
         anArray size: 0.
        ^false 
      ].
    ^true
  ].
  ((aKey == nil) 
    _or: [ self _compare: aComparison key: aKey greaterThanOrEqualToEntryAt: self _lastKeyIndex ])
    ifTrue: [
      " if so, put the rightmost leaf entry in the Array "
      self _putLastIndexOfLastChildInto: anArray.
      ^ true
    ].
^false
%

category: 'Searching'
method: BtreeLeafNode
_findFirstValueForKey: aKey using: aComparison

"Returns the first value associated with the given key.  For leaf nodes, finds
 the appropriate entry and makes the comparison.  If one is not found,
 returns the incomplete path traversal object."

| index eSize maxIndex |

index := self _findCoveringIndexForKey: aKey totalOrder: false.
index == 0 ifTrue: [ ^ #_incompletePathTraversal ].

eSize := self entrySize.
maxIndex := self _lastIndex.

" now scan entries until reach the end or no match "
[ (index < maxIndex) _and:
[ self _compare: BtreeComparisonForSort key: aKey lessThanOrEqualToEntryAt: (index + 1) ] ] whileTrue: [
  (self _compare: aComparison key: aKey equalToEntryAt: (index + 1))
    ifTrue: [ ^ super at: index ].
  index := index + eSize
].
^ #_incompletePathTraversal
%

category: 'Updating'
method: BtreeLeafNode
_insertEncryptionFor: aKey value: aValue startingAt: insertionIndex

"Gets the encryption for the given key and place it in the receiver starting at
 the given index.  Subclasses may provide their own encryption; there is no
 default encryption."

%

category: 'Searching Support'
method: BtreeLeafNode
_putFirstIndexOfFirstChildInto: anArray

"Puts the receiver and the first index of the receiver into the Array."

numElements == 0
    ifTrue: [ anArray addLast: 0]
    ifFalse: [ anArray addLast: 1 ].
anArray addLast: self
%

category: 'Searching Support'
method: BtreeLeafNode
_putFirstIndexOfFirstChildInto: anArray ifGreaterThanOrEqualTo: aKey using: aComparison

"If first entry is greater than or equal to aKey, Puts the receiver 
 and the first index of the receiver into the Array.

 Because of NANs we need to validate the assumption of the caller 
 (i.e., that all entries are greater than aKey). See bug33805."

"make sure that key is less than or equal to first entry"
(aKey == nil 
   _or: [ self _compare: aComparison key: aKey lessThanOrEqualToEntryAt: 2 ])
  ifTrue: [
    numElements == 0
      ifTrue: [ anArray addLast: 0]
      ifFalse: [ anArray addLast: 1 ].
  ]
  ifFalse: [
    anArray addLast: 0.
  ].
  anArray addLast: self
%

category: 'Searching Support'
method: BtreeLeafNode
_putLastIndexOfLastChildInto: anArray

"Puts the receiver and the last index of the receiver into the Array."

anArray addLast: self _lastKeyIndex - 1.
anArray addLast: self
%

category: 'Searching'
method: BtreeLeafNode
_scanForAllValuesForKey: aKey into: aCollection using: aComparison

"Places all values associated with the given key into aCollection.  Start with
 the first entry, and iterate through consecutive entries until we reach the
 end or the key does not match."

| index eSize maxIndex |

numElements == 0 ifTrue: [ ^ self ].
index := 1.
eSize := self entrySize.
maxIndex := self _lastIndex.

" now scan entries until reach the end or no match using sort ="
[ (index < maxIndex) _and:
[ self _compare: aComparison key: aKey equalToEntryAt: (index + 1) ] ] whileTrue: [
    aCollection add: (super at: index).
    index := index + eSize
]
%

category: 'Updating'
method: BtreeLeafNode
_splitUsingKey: aKey value: aValue

"Creates a new sibling node, moving half of the receiver's entries into the
 sibling.  Then inserts a new entry with the given key/value into either the
 receiver or sibling.  Returns the new sibling."

| index newSibling lastKeyIndex lastKey |
newSibling := self _createSibling.

" get the last key in the receiver "
lastKeyIndex := self _lastKeyIndex.
lastKey := super at: lastKeyIndex.

" determine if new entry goes in the first half or second half "
(self _compareKey: aKey value: aValue lessThanOrEqualToEntryAt: lastKeyIndex)
  ifTrue: [  " adding to the first half "
    index := self _binarySearchCoveringKey: aKey value: aValue.
    self _insertKey: aKey value: aValue atIndex: index
  ]
  ifFalse: [ " adding to the second half "
    index := newSibling _binarySearchCoveringKey: aKey value: aValue.
    newSibling _insertKey: aKey value: aValue atIndex: index
  ].

^ newSibling
%

category: 'Updating'
method: BtreeLeafNode
_updateLastValue

"For leaf nodes, the last value is derived, so nothing is required."

%

category: 'Updating'
method: BtreeLeafNode
btreeAt: aKey put: aValue

""

^ self at: aKey put: aValue
%

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

"Adds the key/value pair to the node.  If the node is full, performs a 'split'
 on the parent.  Returns the new sibling if a split is performed, otherwise
 returns the receiver."

| index |
" determine if a split is needed "
numElements == self class maxNumberOfElements
  ifTrue: [ " performs the split and returns the new sibling "
    ^ self _splitUsingKey: aKey value: aValue
  ]
  ifFalse: [ " entry will fit in leaf node "
    numElements == 0
      ifTrue: [ index := 1 ]
      ifFalse: [
        index := self _binarySearchCoveringKey: aKey value: aValue.
      ].
    self _insertKey: aKey value: aValue atIndex: index
  ]
%

category: 'Testing'
method: BtreeLeafNode
isLeaf

"Returns whether the B-tree node is a leaf node."

^ true
%

category: 'Accessing'
method: BtreeLeafNode
lastValue

"Returns the value for the last entry in the receiver."

^ super at: (numElements - 1 * self entrySize + 1)
%

category: 'Constants'
method: BtreeLeafNode
mergeThreshold

"Returns the threshold such that if an entry has less than this number, it must
 have elements added from its sibling or be merged with its sibling.  This
 value is usually the same as the result of the message
 'self maxNumberOfElements quo: 2'."

^ 500
%

category: 'Printing'
method: BtreeLeafNode
printOn: aStream withIndentationLevel: anInteger

"Puts a displayable representation of the keys of the receiver on the given
 stream, indenting the given number of spaces."

anInteger timesRepeat: [ aStream nextPut: Character space ].

"aStream nextPutAll: '  { '; nextPutAll: self _alias asString; nextPutAll: ' } '."

2 to: (numElements * self entrySize) by: self entrySize do: [ :i |
    aStream nextPutAll: (super at: i) asString;
        nextPut: $(;
        nextPutAll: (super at: i - 1) asString;
        nextPutAll: ') '
].
aStream nextPut: Character lf
%

category: 'Printing'
method: BtreeLeafNode
printOn: aStream withIndentationLevel: anInteger includingValues: aBoolean

"Puts a displayable representation of the keys of the receiver on the given
 stream, indenting the given number of spaces."

anInteger timesRepeat: [ aStream nextPut: Character space ].

"aStream nextPutAll: '  { '; nextPutAll: self _alias asString; nextPutAll: ' } '."

2 to: (numElements * self entrySize) by: self entrySize do: [ :i |
    aStream nextPutAll: (super at: i) asString.

    "aStream nextPut: $(;
        nextPutAll: (super at: i - 1) _alias asString;
        nextPut: $).
    "
    aBoolean
        ifTrue: [
            aStream nextPut: $(;
                nextPutAll: (super at: i - 1) asString;
                nextPutAll: ') '
        ]
        ifFalse: [ aStream nextPutAll: ' ' ]
].
aStream nextPut: Character lf
%

category: 'Removing'
method: BtreeLeafNode
removeKey: aKey value: aValue

"Removes the key/value pair.  Finds the index for the given key and then shifts
 any following entries to the left."

| valueIndex eSize |
valueIndex := self _binarySearchForKey: aKey value: aValue.

valueIndex == 0 ifTrue: [ ^ false ].
eSize := self entrySize.

self _deleteNoShrinkFrom: valueIndex to: valueIndex + eSize - 1 .
numElements := numElements - 1.

^ true
%

category: 'Printing'
method: BtreeLeafNode
stringRep

""

| aStream |

aStream := PrintStream printingOn: String new.
self printOn: aStream withIndentationLevel: 0.
^ aStream contents
%

category: 'Enumerating'
method: BtreeLeafNode
_preOrderDo: aBlock

"Execute the one-argument block with the receiver."

aBlock value: self
%

category: 'Enumerating'
method: BtreeLeafNode
_leafKeysAndValuesDo: aBlock

"Execute the two-argument block with the key and value of each entry in the
 receiver."

1 to: (numElements * self entrySize) by: self entrySize do: [ :i |
    aBlock value: (self _at: i + 1) value: (self _at: i)
]
%

category: 'Aggregate Support'
method: BtreeLeafNode
_numNonNilElements

"Returns the number of non-nil elements."

| count |
count := 0.
" count from beginning the number of nils "
2 to: (numElements * self entrySize) by: self entrySize do: [ :i |
    nil == (self _at: i) ifTrue: [ count := count + 1]
].

^ numElements - count
%

category: 'Private'
method: BtreeLeafNode
numElementsInStack: array
level: level
endNode: endNode
endIndex: endIndex
into: result

"Put the count in the first slot in the argument array and returns whether we
 reached the end."

" if receiver is the beginning node "
self == (array at: level + 1)
    ifTrue: [
        " if receiver is also the ending node "
        self == endNode
            ifTrue: [ " all entries within this node "
                result at: 1 put: ( endIndex - (array at: level)) // self entrySize.
                ^ true
            ]
            ifFalse: [ " first elements are in this node "
                result at: 1 put: numElements - ((array at: level) // self entrySize).
                ^ false
            ]
    ]
    ifFalse: [ 
        " if receiver is the ending node "
        self == endNode
            ifTrue: [ " last elements are in this node "
                result at: 1 put: endIndex // self entrySize.
                ^ true
            ]
            ifFalse: [ " all elements are in this node "
                result at: 1 put: numElements.
                ^ false
            ]
    ]
%

category: 'Sorting Support'
method: BtreeLeafNode
_putAscendingValuesInto: array startingAt: offset

"Returns the number of elements."

| j |
j := offset.
1 to: (numElements * self entrySize) by: self entrySize do: [ :i |
  array at: j put: (self _at: i).
  j := j + 1
].
^ numElements
%

category: 'Sorting Support'
method: BtreeLeafNode
_putDescendingValuesInto: array startingAt: offset

"Returns the number of elements."

| j |
j := offset.
1 to: (numElements * self entrySize) by: self entrySize do: [ :i |
  array at: j put: (self _at: i).
  j := j - 1
].
^ numElements
%

category: 'Accessing'
method: BtreeLeafNode
_totalElementsIn: stack endNode: endNode endIndex: endIndex into: array

"Determine the total number of entries, checking the given stack and
 end node from a stream object.  The given Array contains the current
 sum of elements in the first slot, and the second slots indicates if
 the end was hit."

| i start end sum |
(i := stack indexOf: self) > 0
  ifTrue: [ start := stack at: i - 1 ]
  ifFalse: [ start := 1 ].

self == endNode
  ifTrue: [
    end := endIndex.
    array at: 2 put: true.
  ]
  ifFalse: [ end := self _lastIndex ].

sum := (array at: 1) + ((end - start) // self entrySize) + 1.
array at: 1 put: sum
%

category: 'Accessing'
method: BtreeLeafNode
totalElements

"Return the number of elements."

^ numElements
%

category: 'Private'
method: BtreeLeafNode
_insertEncodingForString: aString encoding: numToEncode startingAt: startIdx

<primitive: 538>
aString  _validateClass: String .
numToEncode _validateClass: SmallInteger .
startIdx _validateClass: SmallInteger .

^ self _primitiveFailed: #_insertEncodingForString:encoding:startingAt:
%

category: 'Query Support'
method: BtreeLeafNode
_traverseValues: aQuerySpec
start: startIndex
end: endIndex 
previous: previousValue
into: collection

^aQuerySpec 
    _traverseValuesFrom: self
    entrySize: self entrySize
    start: startIndex
    end: endIndex 
    previous: previousValue
    into: collection
%

category: 'Query Support'
method: BtreeLeafNode
_addValues: aQuerySpec
start: startIndex
end: endIndex 
into: collection

^aQuerySpec 
    _addValuesFrom: self
    entrySize: self entrySize
    start: startIndex
    end: endIndex 
    into: collection
%
