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

! class created in idxclasses.topaz

removeallmethods SortNode
removeallclassmethods SortNode

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

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

txt := (GsDocText new) details:
'A SortNode is a BtreeBasicLeafNode that can sort node entries by index path.' .
doc documentClassWith: txt.

txt := (GsDocText new) details: ''.
doc documentInstVar: #pathSorter with: txt.

txt := (GsDocText new) details: ''.
doc documentInstVar: #sortLevel with: txt.

txt := (GsDocText new) details: ''.
doc documentInstVar: #totalElements with: txt.

self description: doc.
%

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

"Returns a new initialized instance with the correct size."
| newOne |
newOne := self basicNew: (self entrySize * self initialNumberOfElements).
newOne numElements: 0.
newOne totalElements: 0.
^ newOne

%

category: 'Instance Creation'
classmethod: SortNode
new: size

"Returns a new initialized instance with the correct size."
| newOne |
newOne := self basicNew: self entrySize * (size min: self maxNumberOfElements).
newOne numElements: 0.
newOne totalElements: 0.
^ newOne
%

category: 'Indexing Support'
classmethod: SortNode
recalculateSelectionTree: sortNodeArray for: node offsets: offsets

"Recalculate the selection tree based on a change of the minimum entry
 in the given node."

| parent lChild rChild offset1 offset2 newOffset i j currNode |
currNode := node.

[ true ] whileTrue: [
    " get the parent of the node that has changed "
    parent := currNode at: 2.

    lChild := parent at: 3.
    rChild := parent at: 4.
    " get the offset in the receiver of the corresponding run "
    offset1 := lChild at: 1.
    offset2 := rChild at: 1.

    " check if either of the runs are now empty "
    i := offsets at: offset1.
    j := offsets at: offset2.
    i == nil
        ifTrue: [ newOffset := offset2 ]
        ifFalse: [
             j == nil
                 ifTrue: [ newOffset := offset1 ]
                 ifFalse: [
                     ( (sortNodeArray at: offset1)
                         _compareEntryAt: i
                         lessThanNode: (sortNodeArray at: offset2)
                         entryAt: j
                         useValue: true)
                         ifTrue: [ newOffset := offset1 ]
                         ifFalse: [ newOffset := offset2 ]
                 ]
        ].
    parent at: 1 put: newOffset.

    " if no parent, then this is the root "
    (parent at: 2) == nil
        ifTrue: [ ^ self ].

    currNode := parent
]
%

! ------------------- Instance methods for SortNode
category: 'Comparison Operators'
method: SortNode
_compareEntryAt: index1
lessThanNode: aNode
entryAt: index2
useValue: aBoolean

"Perform a < comparison between the entries at the given indexes.
 The default implementation uses no encryption."

| o1 o2 |
" first compare the keys "
( (o1 := self _at: index1) _idxForSortLessThan: (o2 := aNode _at: index2) )
    ifTrue: [ ^ true ]
    ifFalse: [
        " if using the values and keys are equal, use the OOP of the value "
        ( aBoolean _and: [ o1 _idxForSortEqualTo: o2 ] )
            ifTrue: [
                ^ (self _at: index1 - 1) asOop < (aNode _at: index2 - 1) asOop
            ]
            ifFalse: [ ^ false ]
    ]
%

category: 'Updating'
method: SortNode
_insertDuplicateKey: aKey value: aValue atIndex: insertionIndex

"The given key is already present in the receiver, so insert the entry
 in a secondary sort node (creating it if necessary)."

| val newNode sortArray hasSecondarySort |

" get the existing value "
val := self _at: insertionIndex.
" see if the value is already sort nodes on the secondary sort path "
val _class == SortNodeArray
  ifTrue: [
    pathSorter _addObject: aValue
      inNodes: val
      hasSecondarySort: (pathSorter size > val last sortLevel)
      incompletes: nil
      incomplete: #_incompletePathTraversal
  ]
  ifFalse: [
    " create sort node for the secondary sort path and put it in a sort Array "
    newNode := (pathSorter sortNodeClassForSortLevel: sortLevel + 1)
      new: self sizeForSecondarySorts.
    newNode pathSorter: pathSorter.
    newNode sortLevel: sortLevel + 1.
    sortArray := SortNodeArray with: newNode.
    self _basicAt: insertionIndex put: sortArray.
    hasSecondarySort := pathSorter size > newNode sortLevel.

    pathSorter _addObject: aValue
      inNodes: sortArray
      hasSecondarySort: hasSecondarySort
      incompletes: nil
      incomplete: #_incompletePathTraversal.

    pathSorter _addObject: val
      inNodes: sortArray
      hasSecondarySort: hasSecondarySort
      incompletes: nil
      incomplete: #_incompletePathTraversal.
  ].
%

category: 'Updating'
method: SortNode
_insertKey: aKey
value: aValue
atIndex: insertionIndex
hasSecondarySort: hasSecondarySort

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

| lastIndex eSize |
lastIndex := self _lastIndex.
" see if there is more than one sort path remaining and if the given key
is already present in the receiver."
( insertionIndex < lastIndex _and: [ hasSecondarySort _and:
[ self _compareKey: aKey equalToEntryAt: insertionIndex + 1 ] ] )
    ifTrue: [ " duplicate keys "
        ^ self _insertDuplicateKey: aKey value: aValue atIndex: insertionIndex
    ].

eSize := self entrySize .

"move entries down to make room for a new entry, or add room at the end"
self _insertAt: insertionIndex 
     from: nil "insert nils" fromStart: 1 fromEnd: eSize
     numToMoveDown: (numElements * eSize) - insertionIndex + 1 .
            
" add the new entry "
super _basicAt: insertionIndex put: aValue.
super _basicAt: (insertionIndex + 1) put: aKey.

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

numElements := numElements + 1
%

category: 'Updating'
method: SortNode
_at: aKey put: aValue forBtree: aBool hasSecondarySort: hasSecondarySort

"Adds the key/value pair to the node.  Sender must verify that the node is not
 full.  Used as optimized method by PathSorter (optimized when receiver is
 a BasicSortNode).  aBool should always be false."

^ self at: aKey put: aValue hasSecondarySort: hasSecondarySort
%

category: 'Updating'
method: SortNode
at: aKey put: aValue hasSecondarySort: hasSecondarySort

"Adds the key/value pair to the node.  Sender must verify that the node is not
 full."

| index |
numElements == 0
  ifTrue: [ index := 1 ]
  ifFalse: [ index := self _binarySearchCoveringKey: aKey totalOrder: false ].

self _insertKey: aKey
  value: aValue
  atIndex: index
  hasSecondarySort: hasSecondarySort.

totalElements := totalElements + 1
%

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

"Adds the key/value pair to the node.  Sender must verify that the node is not
 full."

| index |
numElements == 0
  ifTrue: [ index := 1 ]
  ifFalse: [ index := self _binarySearchCoveringKey: aKey value: aValue ].
self _btreeInsertKey: aKey value: aValue atIndex: index.
totalElements := totalElements + 1
%

category: 'Constants'
method: SortNode
sizeForSecondarySorts

"Returns the number of entries to allocate when creating a sort node to
 hold secondary sorts."

^ 10
%

category: 'Constants'
classmethod: SortNode
initialNumberOfElements

"Returns the number of entries that are allocated when a node is created."

^ 100
%

category: 'Accessing'
method: SortNode
pathSorter

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

^pathSorter
%

category: 'Updating'
method: SortNode
pathSorter: newValue

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

pathSorter := newValue
%

category: 'Sorting'
method: SortNode
sortInto: anArray startingAt: index

"Insert the values of the receiver into the given Array starting at the
 given index in sorted order.  Returns the number inserted. "

| j k obj snarray start |
snarray := SortNodeArray.
(pathSorter directions at: sortLevel)
    ifTrue: [ " sort is ascending "
        j := index.
        " for each value in the receiver ... "
        1 to: (numElements * self entrySize) by: self entrySize do: [ :i |
            " if it is an Array of nodes, then a merge sort is needed "
            (obj := self _at: i) _class == snarray
                ifTrue: [
                    obj sortInto: anArray startingAt: j.
                    j := j + obj totalElements
                ]
                ifFalse: [
                    anArray at: j put: obj.
                    j := j + 1
                ].
        ].
        ^ j - index
    ]
    ifFalse: [ " sort is descending "
        start := index + totalElements - 1.
        j := start.
        " for each value in the receiver ... "
        1 to: (numElements * self entrySize) by: self entrySize do: [ :i |
            " if it is an Array of nodes, then a merge sort is needed "
            (obj := self _at: i) _class == snarray
                ifTrue: [
                    k := j - obj totalElements + 1.
                    obj sortInto: anArray startingAt: k.
                    j := k - 1
                ]
                ifFalse: [
                    anArray at: j put: obj.
                    j := j - 1
                ].
        ].
        ^ start - j
    ]
%

category: 'Accessing'
method: SortNode
sortLevel

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

^sortLevel
%

category: 'Updating'
method: SortNode
sortLevel: newValue

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

sortLevel := newValue
%

category: 'Accessing'
method: SortNode
totalElements

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

^totalElements
%

category: 'Updating'
method: SortNode
totalElements: newValue

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

totalElements := newValue
%

category: 'Indexing Support'
method: SortNode
sortIntoBtreeNodes: anArray

"Put all of the receiver's entries in the B-tree leaf nodes contained
 in anArray.  If there are not enough B-tree leaf nodes, create more."

| leafNode num secondLeaf half |
totalElements == 0
    ifTrue: [ ^ self ].

leafNode := anArray at: 1.

num := leafNode maxNumWhenMerging.
totalElements < num
    ifTrue: [
        "All of the receiver's entries will fit in the single B-tree leaf node"
        self
            copyFrom: 1
            to: totalElements * self entrySize
            into: leafNode
            startingAt: 1.
        leafNode numElements: self totalElements.
    ]
    ifFalse: [
        "Create another B-tree leaf node and put half of the receiver's entries in each"
        secondLeaf := leafNode class new.
        secondLeaf assignToSegment: leafNode segment.
        half := totalElements // 2.
        num := half * self entrySize.
        self
            copyFrom: 1
            to: num
            into: leafNode
            startingAt: 1.
        leafNode numElements: half.

        self
            copyFrom: num + 1
            to: totalElements * self entrySize
            into: secondLeaf
            startingAt: 1.
        secondLeaf numElements: totalElements - half.

        anArray add: secondLeaf
    ].
%

category: 'Updating'
method: SortNode
_btreeInsertKey: 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 must provide the insertion
 index."

| lastIndex eSize |
lastIndex := self _lastIndex.
eSize := self entrySize .

"move entries down to make room for a new entry, or add room at the end"
self _insertAt: insertionIndex 
     from: nil fromStart: 1 fromEnd: eSize
     numToMoveDown: lastIndex - insertionIndex + 1 .

" add the new entry "
super _basicAt: insertionIndex put: aValue.
super _basicAt: (insertionIndex + 1) put: aKey.

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

numElements := numElements + 1
%

category: 'Testing'
method: SortNode
isFull

"Returns if the node is full."

^ numElements == self class maxNumberOfElements
%
