!=========================================================================
! Copyright (C) VMware, Inc. 1986-2011.  All Rights Reserved.
!
! $Id: btreereadstr.gs,v 1.9 2008-01-09 22:50:08 stever Exp $
!
! Superclass Hierarchy:
!   BtreeReadStream, Stream, Object.
!
! class created in idxclasses.topaz
!=========================================================================

removeallmethods BtreeReadStream
removeallclassmethods BtreeReadStream

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

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

txt := (GsDocText new) details:
'BtreeReadStream supports the composition of query results by providing access
 to a B-tree structure.

 A BtreeReadStream can read all the entries of the B-tree one at a time.  Supply
 the root node when you create the stream, and send the ''next'' message to
 read the first node.  Send the ''next'' message repeatedly to iterate over
 the B-tree''s contents, and send the ''atEnd'' message to check if there are
 any more nodes.'.
doc documentClassWith: txt.

txt := (GsDocText new) details:
'The leaf node that is the last entry in the B-tree.'.
doc documentInstVar: #endNode with: txt.

txt := (GsDocText new) details:
'The index of the leaf node that is the last entry in the B-tree.'.
doc documentInstVar: #endIndex with: txt.

txt := (GsDocText new) details:
'An Array of B-tree node / offset pairs.  The successive elements of the
 Array indicate the path through the B-tree to the current entry.'.
doc documentInstVar: #currentStack with: txt.

self description: doc.
%

category: 'Instance Creation'
classmethod: BtreeReadStream
on: aBtreeNode

"Create a stream that can access the entire contents of the B-tree whose
 root node is aBtreeNode."

| arr1 arr2 newStream |
arr1 := Array new.
arr2 := Array new.

aBtreeNode _putFirstIndexOfFirstChildInto: arr1.
aBtreeNode _putLastIndexOfLastChildInto: arr2.

newStream := self new.
newStream endIndex: (arr2 at: 1).
newStream endNode: (arr2 at: 2).
newStream currentStack: arr1.

^ newStream
%

! ------------------- Instance methods for BtreeReadStream
category: 'Testing'
method: BtreeReadStream
_btreeAtEnd

""

^ (currentStack at: 1) == 0
%

category: 'Accessing'
method: BtreeReadStream
_btreeNext

"Returns the next value on a stream of B-tree values.  Updates the current
 stack for a subsequent 'next'."

| val leaf index lastValIndex |
" get the index into the leaf node and see if it has reached the end "
index := currentStack at: 1.
index == 0
    ifTrue: [ ^ self _errorEndOfStream ].

" get the leaf and the value within the leaf "
leaf := currentStack at: 2.
val := leaf _basicAt: index.

" if this is the end of the stream, sets the top index to zero and returns "
( leaf == endNode _and: [ endIndex == index ] )
    ifTrue: [
        currentStack at: 1 put: 0.
        ^ val
    ].

" see if index refers to last entry in this leaf "
lastValIndex := leaf _lastKeyIndex - 1.
index > lastValIndex
    ifTrue: [ self _error: #rtErrInvalidBtreeReadStream ].

index == lastValIndex
    ifTrue: [
        " must look down the stack for the next leaf node "
        self _nextLeaf
    ]
    ifFalse: [ currentStack at: 1 put: (index + leaf entrySize) ].

^ val
%

category: 'Error Handling'
method: BtreeReadStream
_errorEndOfStream

"Raises an error due to an attempt to read beyond the end of the stream."

^ self _error: #rtErrBtreeReadStreamEndOfStream .
%

category: 'Private'
method: BtreeReadStream
_peekKey

"Returns the key of the current entry in the stream."

| i |
i := currentStack at: 1.
i == 0
    ifTrue: [ ^ self _errorEndOfStream ].
^ (currentStack at: 2) _basicAt: i + 1
%

category: 'Private'
method: BtreeReadStream
_peekValue

"Returns the value of the current entry in the stream."

| i |
i := currentStack at: 1.
i == 0
    ifTrue: [ ^ self _errorEndOfStream ].
^ (currentStack at: 2) _basicAt: i
%

category: 'Testing'
method: BtreeReadStream
atEnd

"Returns true if the receiver is positioned at the end of the stream, and
 false otherwise."

^ (currentStack at: 1) == 0
%

category: 'Accessing'
method: BtreeReadStream
currentStack

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

^currentStack
%

category: 'Updating'
method: BtreeReadStream
currentStack: newValue

"Modifies the value of the instance variable 'currentStack'."

currentStack := newValue
%

category: 'Accessing'
method: BtreeReadStream
endIndex

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

^endIndex
%

category: 'Updating'
method: BtreeReadStream
endIndex: newValue

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

endIndex := newValue
%

category: 'Accessing'
method: BtreeReadStream
endNode

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

^endNode
%

category: 'Updating'
method: BtreeReadStream
endNode: newValue

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

endNode := newValue
%

category: 'Accessing'
method: BtreeReadStream
next

"Returns the next value on a stream of B-tree values.  Update the current
 stack for a subsequent 'next'."

self _btreeAtEnd
    ifTrue: [ ^ self _errorEndOfStream ].

^ self _btreeNext
%

category: 'Adding'
method: BtreeReadStream
nextPut: anObject

"Disallowed.  You cannot write to a BtreeReadStream."

self shouldNotImplement: #nextPut:
%

category: 'Query Support'
method: BtreeReadStream
_hasSameEndAs: otherStream

"Returns true if the receiver has the same end index and end node as the
 otherStream."

^ endIndex == otherStream endIndex _and: [
   endNode == otherStream endNode ]
%

category: 'Query Support'
method: BtreeReadStream
_positionToEnd

"Sets the current stack to the end index and end node.  This
 has the effect of advancing the stream to the last object."

currentStack at: 1 put: endIndex.
currentStack at: 2 put: endNode
%

category: 'Query Support'
method: BtreeReadStream
_valuesAddInto: collection

"Adds each entry value into the given NSC."

| querySpec |
querySpec := BtreeQuerySpec new.
^self _valuesAddInto: collection spec: querySpec
%

category: 'Accessing'
method: BtreeReadStream
_nextLeaf

"Looks down the stack for the next leaf node and makes it the current node."

| nodeIndex notPositioned currentNode currentIndex nextIndex node |

nodeIndex := 4.
notPositioned := true.
[ notPositioned ] whileTrue: [
    currentIndex := currentStack at: nodeIndex - 1.
    nil == (currentNode := currentStack at: nodeIndex)
        ifTrue: [ self _error: #rtErrInvalidBtreeReadStream ].


    " if the current index is the last in the node "
    currentIndex == (currentNode _lastKeyIndex - 1)
        ifTrue: [ " must look down the stack another level "
            nodeIndex == currentStack size
                ifTrue: [ ^ self _errorEndOfStream ].
            nodeIndex := nodeIndex + 2
        ]
        ifFalse: [ " current node has a next entry "
            nextIndex := currentIndex + currentNode entrySize.
            " put the next entry (index and node) on the stack "
            currentStack at: nodeIndex - 1 put: nextIndex.
            nil == (node := currentNode _basicAt: nextIndex)
                ifTrue: [ self _error: #rtErrInvalidBtreeReadStream ].
            currentStack at: nodeIndex - 2 put: node.

            " put the first child on any remaining levels in the stack "
            nodeIndex - 3 downTo: 3 by: 2 do: [ :i |
                currentStack at: i put: 1.
                currentStack at: i -1 put: ((currentStack at: i + 1) _basicAt: 1)
            ].
            currentStack at: 1 put: 1.
            notPositioned := false
        ]
]
%

category: 'Query Support'
method: BtreeReadStream
_valuesAddInto: collection identicalTo: aKey

"For each entry whose key is identical to the given key, add the value into
 the given collection."

| querySpec |
querySpec := BtreeComparisonQuerySpec key: aKey selector: #==.
^self _valuesAddInto: collection spec: querySpec
%

category: 'Query Support'
method: BtreeReadStream
_valuesAddInto: collection notEqualTo: aKey

"For each entry whose key is not identical to the given key, add the value
 into the given collection."

| querySpec |
querySpec := BtreeComparisonQuerySpec key: aKey selector: #~=.
^self _valuesAddInto: collection spec: querySpec
%

category: 'Query Support'
method: BtreeReadStream
_valuesAddInto: collection notIdenticalTo: aKey

"For each entry whose key is not identical to the given key, add the value
 into the given collection."

| querySpec |
querySpec := BtreeComparisonQuerySpec key: aKey selector: #~~.
^self _valuesAddInto: collection spec: querySpec
%

category: 'Query Support'
method: BtreeReadStream
_valuesAddInto: collection comparing: aSelector key: aKey

"Adds each entry value into the given NSC."

| querySpec |
querySpec := BtreeComparisonQuerySpec key: aKey selector: aSelector.
^self _valuesAddInto: collection spec: querySpec
%

category: 'Query Support'
method: BtreeReadStream
_valuesAddInto: collection comparing: aSelector1 key: aKey1 and: aSelector2 key: aKey2

"Adds each entry value into the given NSC."

| querySpec |
querySpec := BtreeRangeComparisonQuerySpec key: aKey1 selector: aSelector1 and: aKey2 selector: aSelector2.
^self _valuesAddInto: collection spec: querySpec
%

category: 'Query Support'
method: BtreeReadStream
_valuesAddInto: collection spec: querySpec

"Adds each entry value into the given NSC."

| leaf index eSize |

" get the index into the leaf node and see if it has reached the end "
index := currentStack at: 1.
index == 0
    ifTrue: [ ^ self ].

leaf := currentStack at: 2.
eSize := endNode entrySize.
" while current node is not the end node "
[ endNode ~~ leaf ] whileTrue: [
    " put the values for the current node in the set "
    querySpec addValuesFrom: leaf
                     start: index
                     end: leaf numElements * eSize  
                     into: collection.
    " look down the stack for the next leaf node "
    self _nextLeaf.

    leaf := currentStack at: 2.
    index := 1
].

" put values of end node in the NSC "
querySpec addValuesFrom: leaf
                 start: index
                 end: endIndex 
                 into: collection.
%

! Deleted:  _obj: anObject isIdenticalTo: anotherObject

category: 'Accessing'
method: BtreeReadStream
size

"Returns the number of elements contained in the receiver (that is, how many
successful 'next' operations can be performed)."

| array |
self atEnd ifTrue: [ 
  ^ 0 
  ].
array := #[ 0, false ].
(currentStack at: currentStack size)
  _totalElementsIn: currentStack
  endNode: endNode
  endIndex: endIndex
  into: array.
^ array at: 1
%
