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

! class created in idxclasses.topaz

removeallmethods BtreeNode
removeallclassmethods BtreeNode

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


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

txt := (GsDocText new) details:
'BtreeNode is the most general class for representing an node within a B-tree.'.
doc documentClassWith: txt.

txt := (GsDocText new) details:
'A SmallInteger that gives the number of elements contained in the node.'.
doc documentInstVar: #numElements with: txt.

self description: doc.
%

! ------------------- Class methods for BtreeNode
category: 'Instance Creation'
classmethod: BtreeNode
new

"Returns a new initialized instance with the correct size."

^ (super new: self entrySize * self maxNumberOfElements) numElements: 0.
%

! ------------------- Instance methods for BtreeNode
category: 'Searching'
method: BtreeNode
_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."

| lowPt midPt highPt entrySize index entryGreaterThan |

entrySize := self entrySize.
lowPt := 1.
highPt := numElements.
entryGreaterThan := false.
[ lowPt <= highPt ] whileTrue: [
  midPt := (lowPt + highPt) quo: 2.
  index := midPt - 1 * entrySize + 2.
  entryGreaterThan := false.

  (self _compareKey: aKey lessThanEntryAt: index)
    ifTrue: [ 
      highPt := midPt - 1.
   ]
    ifFalse: [
      (self _compareKey: aKey greaterThanEntryAt: index)
        ifTrue: [ 
          lowPt := midPt + 1.
          entryGreaterThan := true. 
        ]
        ifFalse: [ highPt := midPt - 1 ]
    ]
].

entryGreaterThan
  ifTrue: [ ^ index + entrySize - 1 ].

^ index - 1
%

category: 'Searching'
method: BtreeNode
_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."

| lowPt midPt highPt entrySize index entryGreaterThan entryEqualTo |

entrySize := self entrySize.
lowPt := 1.
highPt := numElements.
entryGreaterThan := false.
[ lowPt <= highPt ] whileTrue: [
  entryGreaterThan := false.
  entryEqualTo := false.
  midPt := (lowPt + highPt) quo: 2.
  index := midPt - 1 * entrySize + 2.

  (self _compareKey: aKey value: aValue lessThanEntryAt: index)
    ifTrue: [ 
      highPt := midPt - 1. 
    ]
    ifFalse: [
      (self _compareKey: aKey value: aValue greaterThanEntryAt: index)
        ifTrue: [ 
          lowPt := midPt + 1.
          entryGreaterThan := true. 
        ]
        ifFalse: [ 
          (self _compareKey: aKey equalToEntryAt: index)
            ifTrue: [ 
              (self _compareValueOop: aValue lessThanOrEqualToEntryValueOopAt: index)
                ifTrue: [ highPt := midPt - 1 ]
                ifFalse: [ lowPt := midPt + 1 ].
              entryEqualTo := true.
            ]
            ifFalse: [ 
              lowPt := midPt + 1.
            ]
        ]
    ]
].

entryGreaterThan
  ifTrue: [ ^ index + entrySize - 1 ].

(entryEqualTo _and: [self _compareValueOop: aValue greaterThanEntryValueOopAt: index])
  ifTrue: [ ^ index + entrySize - 1 ].

^ index - 1
%

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

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

| lowPt midPt highPt entrySize index |

numElements == 0 ifTrue: [ ^ 0 ].

entrySize := self entrySize.
lowPt := 1.
highPt := numElements.
[ lowPt <= highPt ] whileTrue: [
  midPt := (lowPt + highPt) quo: 2.
  index := midPt - 1 * entrySize + 2.

  (self _compareKey: aKey value: aValue equalToEntryAt: index)
    ifTrue: [ ^ index - 1 ].

  (self _compareKey: aKey value: aValue lessThanOrEqualToEntryAt: index)
    ifTrue: [ highPt := midPt - 1 ]
    ifFalse: [ lowPt := midPt + 1 ]
].

^ 0
%

category: 'Comparison Operators'
method: BtreeNode
_compareKey: aKey greaterThanOrEqualToEntryAt: index
                                                                                                           
"Perform a >= comparison between aKey and the entry whose key is at the given
index.  The default implementation uses no encryption."
                                                                                                           
^ self _compare: BtreeComparisonForSort key: aKey greaterThanOrEqualToEntryAt: index
%

category: 'Comparison Operators'
method: BtreeNode
_compare: aComparison key: aKey greaterThanOrEqualToEntryAt: index
                                                                                                           
"Perform a >= comparison between aKey and the entry whose key is at the given
index.  The default implementation uses no encryption."

^ aComparison compareKey: aKey greaterThanOrEqualTo: (self _at: index)
%

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

"Performs a = comparison between aKey and the entry whose key is at the given
index.  The default implementation uses no encryption."

^ self _compare: BtreeComparisonForSort key: aKey equalToEntryAt: index
%

category: 'Comparison Operators'
method: BtreeNode
_compare: aComparison key: aKey equalToEntryAt: index 

"Performs a = comparison between aKey and the entry whose key is at the given
index.  The default implementation uses no encryption."

^ aComparison compareKey: aKey equalTo: (self _at: index)
%

category: 'Comparison Operators'
method: BtreeNode
_compareKey: aKey lessThanEntryAt: index

"Perform a < comparison between aKey and the entry whose key is at the given
index.  The default implementation uses no encryption."

^ self _compare: BtreeComparisonForSort key: aKey lessThanEntryAt: index
%

category: 'Comparison Operators'
method: BtreeNode
_compare: aComparison key: aKey lessThanEntryAt: index

"Perform a < comparison between aKey and the entry whose key is at the given
index.  The default implementation uses no encryption."

^ aComparison compareKey: aKey lessThan: (self _at: index)
%

category: 'Comparison Operators'
method: BtreeNode
_compareKey: aKey greaterThanEntryAt: index

"Perform a > comparison between aKey and the entry whose key is at the given
index.  The default implementation uses no encryption."

^ self _compare: BtreeComparisonForSort key: aKey greaterThanEntryAt: index
%

category: 'Comparison Operators'
method: BtreeNode
_compare: aComparison key: aKey greaterThanEntryAt: index

"Perform a > comparison between aKey and the entry whose key is at the given
index.  The default implementation uses no encryption."

^ aComparison compareKey: aKey greaterThan: (self _at: index)
%

category: 'Comparison Operators'
method: BtreeNode
_compareKey: aKey lessThanOrEqualToEntryAt: index

"Performs a <= comparison between aKey and the entry whose key is at the given
index.  The default implementation uses no encryption."

^ self _compare: BtreeComparisonForSort key: aKey lessThanOrEqualToEntryAt: index
%

category: 'Comparison Operators'
method: BtreeNode
_compare: aComparison key: aKey lessThanOrEqualToEntryAt: index
                                                                                                           
"Perform a <= comparison between aKey and the entry whose key is at the given
index.  The default implementation uses no encryption."

^ aComparison compareKey: aKey lessThanOrEqualTo: (self _at: index)
%

category: 'Comparison Operators'
method: BtreeNode
_compareLastKeyLessThanOrEqualToKey: aKey value: aValue

"Returns whether the receivers last key/value pair is greater than or equal to
the given key/value pair."

numElements == 0 ifTrue: [ ^ false ].

" return aKey <= last key "
^ self
_compareKey: aKey
value: aValue
lessThanOrEqualToEntryAt: self _lastKeyIndex
%

category: 'Updating'
method: BtreeNode
primitiveAt: anIndex put: aValue

"Stores the argument aValue in the indexed variable of the
 receiver indicated by anIndex.  The argument anIndex must not be
 larger than 1 + the size of the receiver, and must not be less than 1.

 Generates an error if anIndex is not a SmallInteger or is out of
 bounds, if the receiver is not indexable, or if the
 receiver is not of the right class to store the given value.

 The primitive is equivalent to GciStoreIdxOop or GciStoreByte,
 depending on implementation of the receiver."

<primitive: 268>

(anIndex _isInteger)
  ifFalse: [ ^ self _errorNonIntegerIndex: anIndex].
(self class isIndexable) "not an indexable object"
  ifFalse: [ ^ self _errorNotIndexable].
((anIndex < 1) | (anIndex > (self size + 1))) "out of bounds"
  ifTrue: [ ^ self _errorIndexOutOfRange: anIndex].
(self class isBytes)
ifTrue: [ ((aValue class ~~ SmallInteger) _or: [ (aValue < 0) | (aValue > 255) ])
    ifTrue: [^ aValue _error: #rtErrExpectedByteValue].
  ].

self _primitiveFailed: #at:put: .
self _uncontinuableError
%

category: 'Updating'
method: BtreeNode
_createSibling

"Creates a new sibling node and moves half of the receiver's entries into the
sibling.  Returns the new sibling."

| newSibling sz splitIndex halfNumElements |
newSibling := self class new.
newSibling assignToSegment: self segment.
sz := numElements * self entrySize.

" splitIndex is where to split the receiver "
halfNumElements := numElements quo: 2.
splitIndex := halfNumElements * self entrySize + 1.

" copy the last half of entries into the new sibling "
newSibling _insertAt:1 from: self fromStart: splitIndex fromEnd: sz
   numToMoveDown: 0 .

" nil out last half of receiver "
self _deleteNoShrinkFrom: splitIndex to: sz.

" update the element counts in the receiver and the sibling "
newSibling numElements: (numElements - halfNumElements).
numElements := halfNumElements.

^ newSibling
%

category: 'Constants'
method: BtreeNode
_encryptionSize

"There is no default encryption."

^ 0
%

category: 'Searching'
method: BtreeNode
_findCoveringIndexForKey: aKey totalOrder: bool1 

"Returns the index for the first entry in which aKey is found.  This is the
first entry whose key >= aKey.  If the receiver's last key is greater than
aKey, or if the receiver is empty, returns 0.  Uses a binary search."

| index |
numElements == 0 ifTrue: [ ^ 0 ].

" faster if check results of binary search
(self _compareKey: aKey lessThanOrEqualToEntryAt: self _lastKeyIndex)
ifFalse: [ ^ 0 ].
"

index := self _binarySearchCoveringKey: aKey totalOrder: bool1.
" check if not found "
^ index > self _lastKeyIndex
ifTrue: [ 0 ]
ifFalse: [ index ]
%

category: 'Updating'
method: BtreeNode
_insertKey: aKey value: aValue atIndex: insertionIndex

"Insert the key/value pair in the receiver.  The sender of this message must
verify that the entry will fit in the receiver and provide the insertion
index."

| endIndex entrySize |

" see if any existing entries have to be moved "
entrySize := self entrySize .
endIndex := (numElements * entrySize) .

"move entries down to make room for a new entry, or add room at the end"
self _insertAt: insertionIndex 
     from: nil "from abstract Array of nils"
     fromStart: 1 
     fromEnd: entrySize 
     numToMoveDown: (endIndex - insertionIndex + 1) .


" add the new entry "
self _at: insertionIndex put: aValue.
self _at: (insertionIndex + 1) put: aKey.

self _insertEncryptionFor: aKey value: aValue startingAt: (insertionIndex + 2).

numElements := numElements + 1
%

category: 'Accessing'
method: BtreeNode
_lastIndex

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

^ numElements * self entrySize
%

category: 'Accessing'
method: BtreeNode
_lastKeyIndex

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

^ numElements == 0
ifTrue: [ 0 ]
ifFalse: [ numElements - 1 * self entrySize + 2 ]
%

category: 'Constants'
method: BtreeNode
entrySize

"Returns the size of an entry with no encryption."

^ 2
%

category: 'Constants'
classmethod: BtreeNode
entrySize

"Returns the size of an entry with no encryption."

^ 2
%

category: 'Testing'
method: BtreeNode
isLeaf

"Returns whether the B-tree node is a leaf node.  The default return is false."

^ false
%

category: 'Testing'
method: BtreeNode
isBtreeNode

"Returns true: the receiver is a B-tree node."

^ true
%

category: 'Accessing'
method: BtreeNode
numElements

"Returns the value of the instance variable 'numElements'."

^ numElements
%

category: 'Updating'
method: BtreeNode
numElements: newValue

"Modify the value of the instance variable 'numElements'."

numElements := newValue
%

category: 'Updating'
method: BtreeNode
_incrementNumElements

"Increment the value of the instance variable 'numElements' by 1."

numElements := numElements + 1
%

category: 'Constants'
method: BtreeNode
parentNodeClass

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

^ BtreeInteriorNode
%

category: 'Printing'
method: BtreeNode
prettyPrint

""

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

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

"Returns whether the receiver can make comparisons with the given key.
Returns true since the comparison will actually be attempted."

^ true
%

category: 'Indexing Support'
method: BtreeNode
maxNumWhenMerging

"Returns the maximum number of entries to add when building interior nodes
during a merge sort on index creation."

" ^ (self mergeThreshold + self class maxNumberOfElements) // 2 "
^ self class maxNumberOfElements - 5
%

category: 'Testing'
method: BtreeNode
_basicCanCompare: aKey withClass: aClass

"Returns true if the receiver can make comparisons with the given key, and
false otherwise.  Used for basic nodes."

(aKey isKindOfClass: aClass)
ifTrue: [ ^ true ].

( (aKey isKindOf: Number) _and:
[ ( aClass inheritsFrom: Number) _or: [ aClass == Number ] ] )
ifTrue: [ ^ true ].

( (aKey isKindOf: CharacterCollection) _and:
[ ( aClass inheritsFrom: CharacterCollection) _or:
[ aClass == CharacterCollection ] ] )
ifTrue: [ ^ true ].

( (aKey isKindOf: AbstractCharacter) _and:
[ ( aClass inheritsFrom: AbstractCharacter) _or:
[ aClass == AbstractCharacter ] ] )
ifTrue: [ ^ true ].

^ false
%

category: 'Formatting'
method: BtreeNode
printOn: aStream

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

"Default printing for non-protected access."


aStream nextPutAll: self asString
%

! Deleted:   _obj: anObject isIdenticalTo: anotherObject


category: 'Constants'
classmethod: BtreeNode
maxNumberOfElements

"Returns the number of entries that are allowed in an interior node."

^ 1000
%

! deleted _canonicalizeSymbolAt: offset oldSymbol: oldSym newSymbol: newSym

category: 'Searching'
method: BtreeNode
_scanForAllValuesForKey: aKey into: aCollection

"Places all values associated with the given key into aCollection."

^ self _scanForAllValuesForKey: aKey into: aCollection using: BtreeComparisonForSort
%
category: 'Searching Support'
method: BtreeNode
_putFirstIndexOfFirstChildInto: anArray ifGreaterThanOrEqualTo: aKey

"Puts first entry that is greater than or equal to aKey into the Array."

^ self _putFirstIndexOfFirstChildInto: anArray ifGreaterThanOrEqualTo: aKey using: BtreeComparisonForCompare
%
category: 'Searching'
method: BtreeNode
_findFirstValueForKey: aKey

"Returns the first value associated with the given key."

^ self _findFirstValueForKey: aKey using: BtreeComparisonForCompare
%
category: 'Searching'
method: BtreeNode
_findCoveringIndexForKey: aKey totalOrder: bool1 

"Returns the index for the first entry in which aKey is found.  This is the
first entry whose key >= aKey.  If the receiver's last key is greater than
aKey, or if the receiver is empty, returns 0.  Uses a binary search."

| index |
numElements == 0 ifTrue: [ ^ 0 ].

index := self _binarySearchCoveringKey: aKey totalOrder: bool1.
" check if not found "
^ index > self _lastKeyIndex
ifTrue: [ 0 ]
ifFalse: [ index ]
%
category: 'Searching Support'
method: BtreeNode
_findAllValuesLessThanKey: aKey into: anArray

"Puts into anArray information about the location of the match.  Returns true
 if a value was found, false otherwise."

^ self _findAllValuesLessThanKey: aKey into: anArray using: BtreeComparisonForCompare
%
category: 'Searching Support'
method: BtreeNode
_findAllValuesLessThanKey: aKey andEquals: aBoolean into: anArray

"Puts into anArray information about the location of the match.  Returns true
 if a value was found, false otherwise."

^ self _findAllValuesLessThanKey: aKey andEquals: aBoolean into: anArray using: BtreeComparisonForCompare
%
category: 'Searching Support'
method: BtreeNode
_findAllValuesGreaterThanKey: aKey into: anArray

"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."

^ self _findAllValuesGreaterThanKey: aKey into: anArray using: BtreeComparisonForCompare
%
category: 'Searching'
method: BtreeNode
_findAllValuesForKey: aKey into: aCollection

"Finds all the values for the given key, placing them in the collection."

^ self _findAllValuesForKey: aKey into: aCollection using: BtreeComparisonForSort
%
category: 'Searching'
method: BtreeNode
_findAllValuesForIdenticalKey: aKey into: aCollection

"Finds all the values for the given identical key, placing them in the
 collection.  Return whether the last key was equal or not (so the caller
 knows it must check the next leaf node)."

^ self _findAllValuesForIdenticalKey: aKey into: aCollection using: BtreeComparisonForSort
%

category: 'Audit'
method: BtreeNode
auditNsc: nsc for: pathTerm offset: offset on: aString

"Verifies that the btree structure consistent relative to the 
 given pathTerm.  This method is currently unsupported, but 
 is provided for customer support." 

  | indicatesIndexOnNscElements count key value bag ivOffset keys counts |
indicatesIndexOnNscElements := pathTerm indicatesIndexOnNscElements.
count := 0.
bag := IdentityBag new.
keys := Array new.
counts := Array new.
self _leafKeysAndValuesDo:  [:k :v |
  count := count + 1.
  indicatesIndexOnNscElements
    ifTrue: [
      (v == k)
        ifFalse: [
          pathTerm auditInfo: #[ k, nil, nil ] on: aString.
          aString add: 'Btree [';
            add: self asOop asString;
            add: '] has entry for [';
            add: v asOop asString;
            add: '] of class ';
            add: v class asString;
            add: ' associated with incorrect key [';
            add: k asOop asString;
            add: '] should be ( ';
            add:  v asOop asString;
            add: ') ';
            add: Character lf.
        ].
    ]
    ifFalse: [
      ivOffset := (pathTerm _ivOffsetFor: v).
      ((v instVarAt: ivOffset) == k)
        ifFalse: [
          pathTerm auditInfo: #[ k, nil, nil ] on: aString.
          aString add: 'Btree [';
            add: self asOop asString;
            add: '] has entry for [';
            add: v asOop asString;
            add: '] of class ';
            add: v class asString;
            add: ' associated with incorrect key [';
            add: k asOop asString;
            add: '] should be ( ';
            add:  (v instVarAt: ivOffset) asOop asString;
            add: ') ';
            add: Character lf.
      ].
    ].
  (count > 1)
    ifTrue: [
      (value == v)
        ifFalse: [
          self _auditKey: key 
                value: value 
                bag: bag 
                nsc: nsc 
                for: pathTerm 
                offset: offset 
                on: aString.
        ].
      (BtreeComparisonForSort compareKey: key equalTo: k)
        ifTrue: [
          | i |
          i := keys indexOfIdentical: k.
          i == 0 
            ifTrue: [
              keys add: k.
              counts add: 1.
            ]
            ifFalse: [
              counts at: i put: (counts at: i) + 1.
            ].
        ]
        ifFalse: [
            1 to: keys size do: [:j |
              (DependencyList for: (keys at: j)) ~~ nil
                 ifTrue: [
                    pathTerm auditDepListForByteObject: (keys at: j)
                        occurrences: (counts at: j)
                        index: (pathTerm at: offset)
                        on: aString.
                 ].
             ].
          keys size: 0.
          counts size: 0.
          keys add: k.
          counts add: 1.
        ].
    
    ]
    ifFalse: [
          | i |
          i := keys indexOfIdentical: k.
          i == 0 
            ifTrue: [
              keys add: k.
              counts add: 1.
            ]
            ifFalse: [
              counts at: i put: (counts at: i) + 1.
            ].
    ].
  value := v.
  key := k.
  bag add: v.
].
self _auditKey: key 
       value: value 
       bag: bag 
       nsc: nsc 
       for: pathTerm 
       offset: offset 
       on: aString.
1 to: keys size do: [:j |
  (DependencyList for: (keys at: j)) ~~ nil
    ifTrue: [
      pathTerm auditDepListForByteObject: (keys at: j)
                    occurrences: (counts at: j)
                    index: (pathTerm at: offset)
                    on: aString.
     ].
].
^count
%

category: 'Audit'
method: BtreeNode
_auditKey: key value: value bag: bag nsc: nsc for: pathTerm offset: offset on: aString

"Private.  
 This method is currently unsupported, but is provided for customer support." 

  | num ar index o |
index := pathTerm at: offset.
(index indexDictionary ~~ nil)
  ifTrue: [
    ar := Array new.
    o := index lastPathComponentsDictionaryOffset max: 1.
    index _addAllFor: value
          into: ar
          offset: 0
          pathTerm: (index at: o).
    num := ar size.
  ]
  ifFalse: [
    num := nsc occurrencesOf: value.
  ].
(bag size == num)
  ifFalse: [
    pathTerm auditInfo: #[ key, nil, nil ] on: aString.
    aString add: 'Btree [';
            add: self asOop asString;
            add: '] has incorrect number of entries (';
            add: (bag size) asString;
            add: ') for [';
            add: value asOop asString;
            add: '] of class ';
            add: value class asString;
            add: ' (should be '; add: num asString; add: ')';
            add: Character lf
  ].
bag removeAll: bag.    
%
