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

! class created in idxclasses.topaz

removeallmethods BtreeBasicLeafNode
removeallclassmethods BtreeBasicLeafNode

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

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

txt := (GsDocText new) details:
'A BtreeBasicLeafNode represents an exterior node of a B-tree for which a binary
 search can be done for a key.' .
doc documentClassWith: txt.

self description: doc.
%

category: 'Searching'
method: BtreeBasicLeafNode
_binarySearchCoveringKey: aKey totalOrder: aBoolean 

"Returns the index for the first entry in which aKey is found utilizing a
 binary search.  This is the first entry whose key >= aKey."

<primitive: 114>
self _primitiveFailed: #_binarySearchCoveringKey:totalOrder: .
self _uncontinuableError
%

category: 'Searching'
method: BtreeBasicLeafNode
_binarySearchCoveringKey: aKey value: aValue 

"Returns the index for the entry in which aKey/aValue would be inserted.  This
 is the first entry which has its key >= aKey.  If multiple entries have the
 same key (key = aKey), then aValue is used (since entries with duplicate keys 
 are inserted by the value's OOP ordering).  If the receiver is empty, returns 
 1.  Uses a binary search."

<primitive: 112>
self _primitiveFailed: #_binarySearchCoveringKey:value: .
self _uncontinuableError
%

category: 'Searching'
method: BtreeBasicLeafNode
_binarySearchForKey: aKey value: aValue 

"Returns the 'value' index whose key equality matches aKey.  If no match is
 found, returns zero.  Uses a binary search."

<primitive: 113>
self _primitiveFailed: #_binarySearchForKey:value: .
self _uncontinuableError
%

category: 'Constants'
method: BtreeBasicLeafNode
_encryptionSize

"Two slots are used for encryption."

^ 2
%

category: 'Updating'
method: BtreeBasicLeafNode
_insertEncryptionFor: aKey value: aValue startingAt: index

"Gets the encryption for the given value and places it in the receiver starting
 at the given index."

<primitive: 373>
self _primitiveFailed: #_insertEncryptionFor:value:startingAt: .
self _uncontinuableError
%

category: 'Constants'
method: BtreeBasicLeafNode
entrySize

"Returns the size of an entry (with 2 slots for encryption)."

^ 4
%

category: 'Constants'
classmethod: BtreeBasicLeafNode
entrySize

"Returns the size of an entry (with 2 slots for encryption)."

^ 4
%

category: 'Constants'
classmethod: BtreeBasicLeafNode
maxNumberOfElements

"Returns the number of entries that are allowed in a leaf node."

^ 500
%

category: 'Constants'
method: BtreeBasicLeafNode
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'."

^ 250
%

category: 'Constants'
method: BtreeBasicLeafNode
parentNodeClass

"Returns the class of node to be created as the parent when a split occurs."

^ BtreeBasicInteriorNode
%

category: 'Testing'
method: BtreeBasicLeafNode
_canCompare: aKey withClass: aClass

"Returns whether the receiver can make comparisons with the given key."

^ self _basicCanCompare: aKey withClass: aClass
%

category: 'Accessing'
method: BtreeBasicLeafNode
_lastIndex

"Returns the index of the last used slot in the node."

^ numElements * 4
%

category: 'Accessing'
method: BtreeBasicLeafNode
_lastKeyIndex

"Returns the index of the key of the last entry, or zero if the node is empty."

^ numElements == 0
    ifTrue: [ 0 ]
    ifFalse: [ numElements * 4 - 2 ]
%

category: 'Comparison Operators'
method: BtreeBasicLeafNode
_compareKey: aKey equalToEntryAt: index 

"Performs an equality comparison between aKey and the entry whose key is at the
 given index.  Use encryption to make the comparison faster."

<primitive: 160>
self _primitiveFailed: #_compareKey:equalToEntryAt: .
self _uncontinuableError
%

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

<primitive: 588>

^ super
    _traverseValues: aQuerySpec
    start: startIndex
    end: endIndex 
    previous: previousValue
    into: collection
%

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

<primitive: 555>

^super 
    _addValues: aQuerySpec
    start: startIndex
    end: endIndex 
    into: collection
%

category: 'Searching'
method: BtreeBasicLeafNode
_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 maxIndex querySpec class |
" find first entry that might contain the key"
index := self _findCoveringIndexForKey: aKey totalOrder: false.
index == 0 ifTrue: [ ^ false ].
maxIndex := self _lastIndex.
querySpec := BtreeComparisonQuerySpec key: aKey selector: #==.
class := aCollection class.
((class == Array) _or: [class == NscBuilder]) 
  ifTrue: [
    querySpec addValuesFrom: self
                     start: index
                     end: maxIndex 
                     into: aCollection.
  ]
  ifFalse: [
    | ar |
    ar := Array new.
    querySpec addValuesFrom: self
                     start: index
                     end: maxIndex 
                     into: ar.
    aCollection addAll: ar.
  ].
^self _compare: aComparison key: aKey equalToEntryAt: (maxIndex - 4 + 2) 
%
