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

! class created in idxclasses.topaz

removeallmethods BasicSortNode
removeallclassmethods BasicSortNode

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

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

txt := (GsDocText new) details:
'BasicSortNode is a class for leaf nodes that implements a binary insertion
 sort and utilizes an encryption for fast comparisons.'.
doc documentClassWith: txt.

self description: doc.
%

! ------------------- Class methods for BasicSortNode

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

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

<primitive: 211>
self _primitiveFailed: #recalculateSelectionTreeFor:offsets: .
self _uncontinuableError
%

! ------------------- Instance methods for BasicSortNode
category: 'Searching'
method: BasicSortNode
_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. Uses a binary 
 search."

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

category: 'Searching'
method: BasicSortNode
_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: 204>
self _primitiveFailed: #_binarySearchCoveringKey:value: .
self _uncontinuableError
%

category: 'Constants'
method: BasicSortNode
_encryptionSize

"Two slots are used for encryption."

^ 2
%

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

"Get the encryption for the given value and place it
 in the receiver starting at the given index."

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

category: 'Constants'
classmethod: BasicSortNode
entrySize

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

^ 4
%

category: 'Constants'
method: BasicSortNode
entrySize

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

^ 4
%

category: 'Constants'
classmethod: BasicSortNode
maxNumberOfElements

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

^ 500
%

category: 'Comparison Operators'
method: BasicSortNode
_compareEntryAt: index1
lessThanNode: aNode
entryAt: index2
useValue: aBoolean

"Perform a < comparison between the entries at the given indexes.
 Use encryption to optimize the comparison."

<primitive: 159>
self _primitiveFailed: #_compareEntryAt:lessThanNode:entryAt:useValue: .
self _uncontinuableError
%

category: 'Updating'
method: BasicSortNode
_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 |
lastIndex := numElements * 4.

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

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

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

numElements := numElements + 1
%

category: 'Updating'
method: BasicSortNode
_at: aKey put: aValue forBtree: aBoolean hasSecondarySort: hasSecondarySort

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

<primitive: 360>
self _primitiveFailed: #_at:put:forBtree:hasSecondarySort: .
self _uncontinuableError
%

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

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

^ self _at: aKey put: aValue forBtree: false hasSecondarySort: hasSecondarySort
%

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

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

^ self _at: aKey put: aValue forBtree: true hasSecondarySort: false
%

category: 'Comparison Operators'
method: BasicSortNode
_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."

"Boolean must be false; case-insensitive semantics not yet implemented."

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

category: 'Testing'
method: BasicSortNode
isFull

"Returns if the node is full."

^ numElements == 500
%

category: 'Accessing'
method: BasicSortNode
_lastIndex

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

^ numElements * 4
%


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

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

^ self _basicCanCompare: aKey withClass: aClass
%
