!=========================================================================
! Copyright (C) VMware, Inc. 1986-2011.  All Rights Reserved.
!
! $Id: equalityquery.gs,v 1.8 2008-01-09 22:50:10 stever Exp $
!
! Superclass Hierarchy:
!   EqualityIndexQueryEvaluator, IndexedQueryEvaluator, Object.
!
!=========================================================================

! class created in idxclasses.topaz

removeallmethods EqualityIndexQueryEvaluator
removeallclassmethods EqualityIndexQueryEvaluator

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

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

txt := (GsDocText new) details:
'EqualityIndexQueryEvaluator is a concrete class that implements the behavior used to 
 evaluate queries against UnordedCollections that have equality indexes. This class is
 used in the internal implementation of indexing and should not be modified.'.
doc documentClassWith: txt.

self description: doc.
%
! ------------------- Class methods for EqualityIndexQueryEvaluator
! ------------------- Instance methods for EqualityIndexQueryEvaluator
category: 'Accessing'
method: EqualityIndexQueryEvaluator
btreeRoot

  ^self index btreeRoot
%
category: 'Accessing'
method: EqualityIndexQueryEvaluator
comparisonForCompare

  ^ BtreeComparisonForCompare
%
category: 'Accessing'
method: EqualityIndexQueryEvaluator
comparisonForSort

  ^ BtreeComparisonForSort
%
category: 'Query Select'
method: EqualityIndexQueryEvaluator
findAllValuesEqualTo: aValue

"Returns a set of all values that satisfy the query."

^ (self 
    _findAllValuesGreaterThan: aValue 
    andEquals: true
    andLessThan: aValue
    andEquals: true
    using: self comparisonForCompare) makeNscComparing: #= key: aValue
%
category: 'Query Select'
method: EqualityIndexQueryEvaluator
findAllValuesGreaterThan: val1
andEquals: bool1
andLessThan: val2
andEquals: bool2

"Returns a set of all values that satisfy the query."

  | selector1 selector2 |
  selector1 := bool1
    ifTrue: [ #>= ]
    ifFalse: [ #> ].
  selector2 := bool2
    ifTrue: [ #<= ]
    ifFalse: [ #< ].
  ^ (self
          _findAllValuesGreaterThan: val1
          andEquals: bool1
          andLessThan: val2
          andEquals: bool2
          using: self comparisonForCompare)  makeNscComparing: selector1 
                                             key: val1
                                             and: selector2
                                             key: val2.
%
category: 'Query Select'
method: EqualityIndexQueryEvaluator
findAllValuesGreaterThanKey: aValue andEquals: aBoolean

"Returns a set of all values that satisfy the query."

  | selector |
  selector := aBoolean
    ifTrue:[ #>= ]
    ifFalse: [ #> ].
^ (self 
    _findAllValuesGreaterThanKey: aValue 
    andEquals: aBoolean
    using: self comparisonForCompare) makeNscComparing: selector key: aValue
%
category: 'Query Select'
method: EqualityIndexQueryEvaluator
findAllValuesIdenticalTo: aValue

"Returns a set of all values that satisfy the query.  Since this is an identity
 comparison on a range index (which supports equality comparison), this
 method creates a B-tree read stream for equal values, then iterates through the
 values making the identity comparison."

| tmpHolder stream |

" optimize query for objects in the NSC itself "
self index isIndexOnRootNsc
    ifTrue: [ ^ self _allIdenticalTo: aValue in: self nscRoot ].

stream := self _findAllValuesIdenticalTo: aValue.

stream == nil 
  ifTrue: [ ^ self nscRoot speciesForSelect new ].

tmpHolder := NscBuilder for: self nscRoot speciesForSelect new max: self sizeForNscBuilder.
self index size == 1
    ifTrue: [ stream _valuesAddInto: tmpHolder identicalTo: aValue ]
    ifFalse: [ stream _uniqueValuesAddInto: tmpHolder identicalTo: aValue ].
^ tmpHolder completeBag
%
category: 'Query Select'
method: EqualityIndexQueryEvaluator
findAllValuesLessThanKey: aValue andEquals: aBoolean

"Returns a set of all values that satisfy the query."

  | selector |
  selector := aBoolean
    ifTrue:[ #<= ]
    ifFalse: [ #< ].
  ^ (self
      _findAllValuesGreaterThan: nil
      andEquals: true
      andLessThan: aValue
      andEquals: aBoolean
      using: self comparisonForCompare) makeNscComparing: selector key: aValue
%
category: 'Query Select'
method: EqualityIndexQueryEvaluator
findAllValuesNotEqualTo: aValue 
 
"Returns a set of all values that satisfy the query." 
| preStream eqStream postStream tmpHolder | 
 
preStream := self _findAllValuesGreaterThan: nil andEquals: true
                       andLessThan: aValue andEquals: false using: self comparisonForSort.
eqStream := self _findAllValuesGreaterThan: aValue andEquals: true
                       andLessThan: aValue andEquals: true using: self comparisonForSort.
postStream := self _findAllValuesGreaterThanKey: aValue andEquals: false using: self comparisonForSort. 
 
tmpHolder := NscBuilder for: self nscRoot speciesForSelect new max: self sizeForNscBuilder. 
self index size == 1 
    ifTrue: [ 
        preStream _valuesAddInto: tmpHolder. 
        eqStream _valuesAddInto: tmpHolder notEqualTo: aValue. 
        postStream _valuesAddInto: tmpHolder. 
    ] 
    ifFalse: [ 
        preStream _uniqueValuesAddInto: tmpHolder. 
        eqStream _uniqueValuesAddInto: tmpHolder notEqualTo: aValue. 
        postStream _uniqueValuesAddInto: tmpHolder. 
    ]. 
^ tmpHolder completeBag 
%
category: 'Query Detect'
method: EqualityIndexQueryEvaluator
findFirstValueEqualTo: aValue

"Returns the first value that satisfies the query."

| val |
(index _canCompareWith: aValue)
    ifFalse: [ self _error: #assocErrBadComparison ].

val := self btreeRoot _findFirstValueForKey: aValue using: self comparisonForCompare.

(val == #_incompletePathTraversal)
    ifTrue: [ ^ #_incompletePathTraversal ].

^ self _findFirstValueForKey: val
%
category: 'Query Detect'
method: EqualityIndexQueryEvaluator
findFirstValueGreaterThan: val1
andEquals: bool1
andLessThan: val2
andEquals: bool2

"Returns the first value that satisfies the query."

| stream selector1 selector2 |
stream := self
    _findAllValuesGreaterThan: val1
    andEquals: bool1
    andLessThan: val2
    andEquals: bool2 
    using: self comparisonForCompare.

stream == nil 
  ifTrue: [ ^ #_incompletePathTraversal ].
selector1 := bool1
  ifTrue: [ #_idxForCompareGreaterThanOrEqualTo: ]
  ifFalse: [ #_idxForCompareGreaterThan: ].
selector2 := bool2
  ifTrue: [ #_idxForCompareLessThanOrEqualTo: ]
  ifFalse: [ #_idxForCompareLessThan: ].
^ stream getNextValueComparing: selector1 key: val1 and: selector2 key: val2
%
category: 'Query Detect'
method: EqualityIndexQueryEvaluator
findFirstValueGreaterThanKey: aValue
andEquals: aBoolean

"Returns the first value that satisfies the query."

| stream selector |
stream := self  _findAllValuesGreaterThanKey: aValue 
                    andEquals: aBoolean
                    using: self comparisonForCompare.
stream == nil 
  ifTrue: [ ^ #_incompletePathTraversal ].
selector := aBoolean
  ifTrue: [ #_idxForCompareGreaterThanOrEqualTo: ]
  ifFalse: [ #_idxForCompareGreaterThan: ].
^ stream getNextValueComparing: selector key: aValue
%
category: 'Query Detect'
method: EqualityIndexQueryEvaluator
findFirstValueIdenticalTo: aValue

"Returns the first value that satisfies the query.  Since this is an identity
 comparison on a range index (which supports equality comparison), create a
 BtreeReadStream for equal values, then iterate through the values making
 the identity comparison."

| stream |

stream := self _findAllValuesIdenticalTo: aValue.

(stream == nil)
  ifTrue: [ ^ #_incompletePathTraversal ].

" iterate through the stream, checking for an identical value "
[ stream atEnd not ] whileTrue: [
    (stream _peekKey == aValue)
        ifTrue: [ ^ self _findFirstValueForKey: stream _peekValue ].
    stream _btreeNext
].
^ #_incompletePathTraversal
%
category: 'Query Detect'
method: EqualityIndexQueryEvaluator
findFirstValueLessThanKey: aValue
andEquals: aBoolean

"Returns the first value that satisfies the query."

| stream selector |
stream := self 
      _findAllValuesGreaterThan: nil
      andEquals: true
      andLessThan: aValue
      andEquals: aBoolean
      using: self comparisonForCompare.
stream == nil 
  ifTrue: [ ^ #_incompletePathTraversal ].
selector := aBoolean
  ifTrue: [ #_idxForCompareLessThanOrEqualTo: ]
  ifFalse: [ #_idxForCompareLessThan: ].
^ stream getNextValueComparing: selector key: aValue
%
category: 'Query Detect'
method: EqualityIndexQueryEvaluator
findFirstValueNotEqualTo: aValue

"Returns the first value that satisfies the query."

| stream totalStream obj bag incomplete |
" find the ones that are equal "
stream := self
  _findAllValuesGreaterThan: aValue
  andEquals: true
  andLessThan: aValue
  andEquals: true
  using: self comparisonForCompare.

" if none are equal, pick the first one "
stream _atEnd
  ifTrue: [
    incomplete := #_incompletePathTraversal.
    bag := self nscRoot _asIdentityBag.
    1 to: bag size do: [ :i |
      obj := bag _at: i.
      ((self index traverseObject: obj) == incomplete)
        ifFalse: [ ^ obj ]
    ].
    ^ #_incompletePathTraversal
  ].

" get a stream over the entire NSC "
totalStream := RangeIndexReadStream on: self index.
" see if very first object is not equal "
(totalStream _peekKey _idxForCompareNotEqualTo: stream _peekKey)
  ifTrue: [ ^ totalStream getNext ].

" see if end of original stream is the very last object "
(totalStream _hasSameEndAs: stream )
  ifTrue: [ ^ #_incompletePathTraversal ]
  ifFalse: [
    " advance the stream to the last object "
    totalStream _positionToEnd.
    ^ totalStream getNext
  ]
%
category: 'Accessing'
method: EqualityIndexQueryEvaluator
readStreamClass

"Returns the class of read stream to create for query results."

^ RangeIndexReadStream
%
category: 'Searching'
method: EqualityIndexQueryEvaluator
_findAllValuesGreaterThan: val1 andEquals: bool1
andLessThan: val2 andEquals: bool2 using: aComparison

"Returns a RangeIndexReadStream that iterates over all objects in the index
 that satisfy the query."

| array1 array2 stream doNext |
( (self index _canCompareWith: val1) _and: [ self index _canCompareWith: val2 ] )
    ifFalse: [ self _error: #assocErrBadComparison ].

stream := self readStreamClass new rangeIndex: self index.
" check to see if the query is even satisfiable "
(aComparison satisfiableQueryGreaterThan: val1 
                   andEquals: bool1
                   andLessThan: val2 
                   andEquals: bool2)
    ifFalse: [
        stream currentStack: (Array with: 0).
        ^ stream
    ].

doNext := false.
array1 := Array new.
" see if querying > or >= "
bool1
    ifTrue: [ " if >=, perform < and do an '_advance' operation later "
        (self btreeRoot _findAllValuesLessThanKey: val1 andEquals: false into: array1 using: aComparison)
            ifTrue: [ doNext := true ]
            ifFalse: [ " all were greater than or equal to "
                self btreeRoot _putFirstIndexOfFirstChildInto: array1 ifGreaterThanOrEqualTo: val1 using: aComparison
            ]
    ]
    ifFalse: [ " if >, ask the B-tree specifically for > "
        (self btreeRoot _findAllValuesGreaterThanKey: val1 into: array1 using: aComparison)
            ifFalse: [ " none were greater than "
                stream currentStack: (Array with: 0).
                ^ stream
            ]
    ].

array2 := Array new.
" ask the B-tree for the second boundary of the query result "
(self btreeRoot _findAllValuesLessThanKey: val2 andEquals: bool2 into: array2 using: aComparison)
    ifFalse: [ " none were found less than "
        stream currentStack: (Array with: 0).
        ^ stream
    ].

stream currentStack: array1.
stream endIndex: (array2 at: 1).
stream endNode: (array2 at: 2).

(stream endNode == (array1 at: 2) _and:
[ stream endIndex < (array1 at: 1) ] )
    ifTrue: [
        array1 at: 1 put: 0.
        ^ stream
    ].

doNext
    ifTrue: [ " advance the B-tree positioning "
        stream _advance.
    ].

^ stream
%
category: 'Searching'
method: EqualityIndexQueryEvaluator
_findAllValuesGreaterThanKey: aKey andEquals: aBoolean

"Returns a RangeIndexReadStream that iterates over all objects in the index
 that satisfy the query."

^ self _findAllValuesGreaterThanKey: aKey andEquals: aBoolean using: BtreeComparisonForCompare
%
category: 'Searching'
method: EqualityIndexQueryEvaluator
_findAllValuesGreaterThanKey: aKey andEquals: aBoolean using: aComparison

"Returns a RangeIndexReadStream that iterates over all objects in the index
 that satisfy the query."

| array1 array2 stream doNext |
(self index _canCompareWith: aKey)
    ifFalse: [ self _error: #assocErrBadComparison ].

stream := self readStreamClass new rangeIndex: self index.

doNext := false.
array1 := Array new.
" see if querying > or >= "
aBoolean
    ifTrue: [ " if >=, perform < and do a 'next' operation later "
        (self btreeRoot _findAllValuesLessThanKey: aKey andEquals: false into: array1 using: aComparison)
            ifTrue: [ doNext := true ]
            ifFalse: [ " all were greater than or equal to "
                self btreeRoot _putFirstIndexOfFirstChildInto: array1 ifGreaterThanOrEqualTo: aKey using: aComparison
            ]
    ]
    ifFalse: [ " if >, ask the B-tree specifically for > "
        (self btreeRoot _findAllValuesGreaterThanKey: aKey into: array1 using: aComparison)
            ifFalse: [ " none were greater than "
                stream currentStack: (Array with: 0).
                ^ stream
            ]
    ].

array2 := Array new.
self btreeRoot _putLastIndexOfLastChildInto: array2.

stream currentStack: array1.
stream endIndex: (array2 at: 1).
stream endNode: (array2 at: 2).

doNext ifTrue: [ stream _advance ].

^ stream
%
category: 'Searching'
method: EqualityIndexQueryEvaluator
_findAllValuesIdenticalTo: aValue

"Returns a set of all values that satisfy the query.  Since this is an identity
 comparison on a range index (which supports equality comparison), this
 method creates a B-tree read stream for equal values, then iterates through the
 values making the identity comparison."

| array1 array2 stream |

" if can't make the comparison, then none are identical "
(self index _canCompareWith: aValue)
    ifFalse: [ ^ nil ].

" get boundary entries in the B-tree "
array1 := Array new.
" >=, perform < and do an 'next' operation later "
(self btreeRoot _findAllValuesLessThanKey: aValue andEquals: false into: array1 using: self comparisonForCompare)
    ifFalse: [ " all were greater than or equal to "
        self btreeRoot _putFirstIndexOfFirstChildInto: array1 ifGreaterThanOrEqualTo: aValue using: self comparisonForCompare
    ].

array2 := Array new.
(self btreeRoot _findAllValuesLessThanKey: aValue andEquals: true into: array2 using: self comparisonForCompare)
    ifFalse: [ " none were found less than "
        ^ nil
    ].

" create the read stream "
stream := RangeIndexReadStream new rangeIndex: self index.
stream currentStack: array1.
stream endIndex: (array2 at: 1).
stream endNode: (array2 at: 2).

^stream
%
category: 'Searching'
method: EqualityIndexQueryEvaluator
_findAllValuesLessThanKey: aKey andEquals: aBoolean using: aComparison

"Returns a RangeIndexReadStream that iterates over all objects in the index
 that satisfy the query."

| array1 array2 stream |
(self index _canCompareWith: aKey)
    ifFalse: [ self _error: #assocErrBadComparison ].

stream := self readStreamClass new rangeIndex: self index.
array2 := Array new.
" ask the B-tree to make the search and put the result path into array2 "
(self btreeRoot _findAllValuesLessThanKey: aKey andEquals: aBoolean into: array2 using: aComparison)
    ifTrue: [
        array1 := Array new.
        " put path to first entry of the B-tree into array1 "
        self btreeRoot _putFirstIndexOfFirstChildInto: array1.
        stream currentStack: array1.
        stream endIndex: (array2 at: 1).
        stream endNode: (array2 at: 2)
    ]
    ifFalse: [ " none were found "
        stream currentStack: (Array with: 0)
    ].

^ stream
%
category: 'Searching'
method: EqualityIndexQueryEvaluator
_findFirstKeyNotIdenticalTo: aKey atTerm: pathTerm

"Returns the first key in the receiver's B-tree that is not identical to the
 given key."

| stream key |
stream := BtreeReadStream on: self btreeRoot.
[ stream atEnd ] whileFalse: [
  key := stream _peekKey.
  (key == aKey)
    ifFalse: [ ^ key ].
  stream _btreeNext
].
^ #_incompletePathTraversal
%

