!=========================================================================
! Copyright (C) VMware, Inc. 1986-2011.  All Rights Reserved.
!
! $Id: rangeindex.gs,v 1.23 2008-01-09 22:50:13 stever Exp $
!
! Superclass Hierarchy:
!   RangeEqualityIndex, IdentityIndex, Array, SequenceableCollection,
!   Collection, Object.
!
! class created in idxclasses.topaz
!=========================================================================

removeallmethods RangeEqualityIndex
removeallclassmethods RangeEqualityIndex

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

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

txt := (GsDocText new) details:
''.

doc documentClassWith: txt.

self description: doc.
%

! ------------------- Class methods for RangeEqualityIndex
category: 'Constants'
classmethod: RangeEqualityIndex
isBasicClass: aClass

"Returns whether the given class should use BtreeBasicLeafNodes to store
 B-tree mappings."

aClass == nil
    ifTrue: [ ^ false ].

aClass isSpecial
    ifTrue: [ ^ true ].

#[ String, 
   DoubleByteString,   
           "EUCString no longer supported by encryption"
   Number, "all kernel subclasses of Number" 
   Date,
   Time, 
   AbstractCharacter "Character and JISCharacter handled here" 
  ] do: [ :basicClass |
        (aClass == basicClass _or: [ aClass inheritsFrom: basicClass ] )
            ifTrue: [ ^ true ]
        ].

^ false
%

category: 'Constants'
classmethod: RangeEqualityIndex
_maxCharsForStringComparison

"Returns the maximum number of Characters in a String used to differentiate in
 comparison operations (if Strings differ after this number of Characters, they
 are considered equal)."

<primitive: 161>
self _primitiveFailed: #_maxCharsForStringComparison .
self _uncontinuableError
%

category: 'Instance Creation'
classmethod: RangeEqualityIndex
newWithLastElementClass: aClass

"Create a new instance and initialize its B-tree root."

| newOne |
newOne := super new.
newOne lastElementClass: aClass.
newOne btreeRoot: aClass btreeLeafNodeClass new.
^ newOne
%

category: 'Accessing'
method: RangeEqualityIndex
lastElementClassVersion: versionNum

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

(versionNum == 50)
  ifTrue: [ ^ lastElementClass ].

(versionNum == 41)
  ifTrue: [ ^ progress ].

self halt: 'invalid version num specified'.
%


! ------------------- Instance methods for RangeEqualityIndex
category: 'Error Handling'
method: RangeEqualityIndex
_errorObjectNotInBtree: key value: value

"An entry for the key/value was not present in the B-tree."

^ self _error: #rtErrRangeEqualityIndexObjectNotInBtree args: #[ key, value ]
%


category: 'Removing'
method: RangeEqualityIndex
_removeBtreeEntriesForKey: aKey

"Removes all entries in the B-tree that have a key identical to aKey.
 Returns an Array of values corresponding to each entry that was removed."

| stream vals |
" first we need to find all values that have aKey as the key "
stream := self asQueryEvaluator _findAllValuesGreaterThanKey: aKey andEquals: true.
vals := Array new.

[ stream _btreeAtEnd not _and:
[ stream _peekKey _idxForSortEqualTo: aKey ] ] whileTrue: [
    aKey == stream _peekKey
        ifTrue: [ vals add: stream _peekValue ].
    stream _btreeNext
].
" now remove the entry for each value "
1 to: vals size do: [ :i |
  (self btreeRemoveKey: aKey value: (vals at: i))
  "  ifFalse: [ self _errorObjectNotInBtree: aKey value: (vals at: i) ] "
].

^ vals
%

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

"Insert the key/value pair into the root B-tree node.  Must check to see if a
 split occurred.  If so, create a new root node and put the old root and the
 new split node into the new root."

| returnNode node |
(self _canCompareWith: aKey)
    ifFalse: [
      ^ self _error: #rtErrRangeEqualityIndexInvalidClassKindForBtree
        args: #[ aKey, lastElementClass ]
    ].

returnNode := btreeRoot btreeAt: aKey put: aValue.

" see if a split occurred "
returnNode == btreeRoot
    ifFalse: [ " returnNode is the second half of the split "
        " create the new parent node "
        node := btreeRoot parentNodeClass new.
        node lastValue: returnNode lastValue.

        " insert the first half (the original root) "
        node
            _insertKey: (btreeRoot _at: btreeRoot _lastKeyIndex)
            value: btreeRoot
            atIndex: 1.
        " insert the second half "
        node
            _insertKey: (returnNode _at: returnNode _lastKeyIndex)
            value: returnNode
            atIndex: (node entrySize + 1).

        btreeRoot := node.
    ]
%

category: 'Updating'
method: RangeEqualityIndex
btreeRemoveKey: aKey value: aValue

"Removes the key and value from the B-tree root node.  Must check to see if
 a merge occurred in the root such that the root only contains a single
 entry.  If so, make the single entry the new root.  Returns whether the
 removal occurred."

(btreeRoot removeKey: aKey value: aValue)
    ifTrue: [
        ((btreeRoot numElements == 1) _and: [ btreeRoot isLeaf not ] )
            ifTrue: [ btreeRoot := btreeRoot at: (btreeRoot _lastKeyIndex - 1) ].
        ^ true
    ]
    ifFalse: [ ^ false ].
%

category: 'Accessing'
method: RangeEqualityIndex
btreeRoot

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

^btreeRoot
%

category: 'Updating'
method: RangeEqualityIndex
btreeRoot: newValue

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

btreeRoot := newValue
%

! deleted RangeEqualityIndex>>changingSizeOfByteObject:to:

! deleted RangeEqualityIndex>>findAllValuesEqualTo: (see EqualityIndexQueryEvaluator)

! deleted RangeEqualityIndex>>findAllValuesGreaterThan:andEquals:andLessThan:andEquals: (see EqualityIndexQueryEvaluator)

! deleted RangeEqualityIndex>>findAllValuesGreaterThan:andEquals: (see EqualityIndexQueryEvaluator)

! deleted RangeEqualityIndex>>findAllValuesIdenticalTo: (see EqualityIndexQueryEvaluator)

! deleted RangeEqualityIndex>>findAllValuesLessThanKey:andEquals: (see EqualityIndexQueryEvaluator)

! deleted RangeEqualityIndex>>findAllValuesNotEqualTo: (see EqualityIndexQueryEvaluator)

! deleted RangeEqualityIndex>>findFirstValueEqualTo: (see EqualityIndexQueryEvaluator)

! deleted RangeEqualityIndex>>findFirstValueGreaterThanKey:andEquals: (see EqualityIndexQueryEvaluator)

! deleted RangeEqualityIndex>>findFirstValueGreaterThan:andEquals:andLessThan:andEquals: (see EqualityIndexQueryEvaluator)

! deleted RangeEqualityIndex>>findFirstValueIdenticalTo: (see EqualityIndexQueryEvaluator)

! deleted RangeEqualityIndex>>findFirstValueLessThanKey:andEquals: (see EqualityIndexQueryEvaluator)

! deleted RangeEqualityIndex>>findFirstValueNotEqualTo: (see EqualityIndexQueryEvaluator)

category: 'Testing'
method: RangeEqualityIndex
isIdentityIndex

"Returns false."

^ false
%

category: 'Testing'
method: RangeEqualityIndex
isRangeEqualityIndex

"Returns true."

^ true
%

category: 'Accessing'
method: RangeEqualityIndex
lastElementClass

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

^lastElementClass
%

category: 'Repository Conversion'
method: RangeEqualityIndex
lastElementClass41

"This method is a kludge.  The right way would be to have corresponding
 obsolete classes because instance variables were added going from 4.1 to 5.0."

^progress
%

category: 'Repository Conversion'
method: RangeEqualityIndex
pathComponentsString41

"This method is a kludge.  The right way would be to have corresponding
 obsolete classes because instance variables were added going from 4.1 to 5.0."

| objSize newRangeIndex numInstVars |

newRangeIndex := RangeEqualityIndex new.

numInstVars := RangeEqualityIndex allInstVarNames size.
objSize := self _primitiveSize.

(objSize > numInstVars)
  ifTrue: [
    6 to: numInstVars do: [ :i |
      newRangeIndex add: (self instVarAt: i).
      ].

    1 to: self size do: [ :i |
      newRangeIndex add: (self at: i).
      ].
    ]
  ifFalse: [
    6 to: objSize do:  [ :i |
      newRangeIndex add: (self instVarAt: i).
      ].
    ].

^ newRangeIndex pathComponentsString.
%

category: 'Repository Conversion'
method: RangeEqualityIndex
pathComponentsString41

"This method is a kludge.  The right way would be to have corresponding
 obsolete classes because instance variables were added going from 4.1 to 5.0."

| objSize newRangeIndex numInstVars |

newRangeIndex := RangeEqualityIndex new.

numInstVars := RangeEqualityIndex allInstVarNames size.
objSize := self _primitiveSize.

(objSize > numInstVars)
  ifTrue: [
    6 to: numInstVars do: [ :i |
      newRangeIndex add: (self instVarAt: i).
      ].

    1 to: self size do: [ :i |
      newRangeIndex add: (self at: i).
      ].
    ]
  ifFalse: [
    6 to: objSize do:  [ :i |
      newRangeIndex add: (self instVarAt: i).
      ].
    ].

^ newRangeIndex pathComponentsString.
%

category: 'Updating'
method: RangeEqualityIndex
lastElementClass: newValue

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

lastElementClass := newValue
%

category: 'Accessing'
method: RangeEqualityIndex
lastPathComponentsDictionaryOffset

"Returns the last index into the path components list that is mapped in the
 index dictionary (as opposed to the B-tree)."

^ self size - 1
%

category: 'Accessing'
method: RangeEqualityIndex
readStreamClass

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

^ RangeIndexReadStream
%

! delete updatingByteObject:startingAt:withNewValue: v2.0

category: 'Updating Indexes'
method: RangeEqualityIndex
addDirectMappingsFor: aBag
indexList: iList
updateIndexListSegments: aBoolean

"Add an entry for an index on the elements of the NSC."

| anObject firstPathTerm indexMgr |

indexMgr := self indexManager.

firstPathTerm := self firstPathTerm.
indexMgr autoCommit
  ifTrue: [ nscRoot _lockForIndexCreation ].

self lastPathTerm needsDepList
  ifTrue: [
    aBoolean
      ifTrue: [
        1 to: aBag size do: [ :i |
          " Add an entry for an index on the elements of the NSC. "
          nil ~~ (anObject := aBag _at: i)
            ifTrue: [ " add an entry in the dependency list "
              anObject
                getDepListAndAddPathTerm: firstPathTerm
                withIVOffset: 1
                logging: false.
            ].
          self btreeAt: anObject put: anObject.
          indexMgr commitIndexMaintenance: self at: i.
        ]
      ]
      ifFalse: [
        1 to: aBag size do: [ :i |
          " Add an entry for an index on the elements of the NSC. "
          nil ~~ (anObject := aBag _at: i)
            ifTrue: [ " add an entry in the dependency list "
              anObject
                getDepListAndAddPathTerm: firstPathTerm
                withIVOffset: 1
                logging: false
            ].
          self btreeAt: anObject put: anObject.
          indexMgr commitIndexMaintenance: self at: i.
        ]
      ]
  ]
  ifFalse: [
    aBoolean
      ifTrue: [
        1 to: aBag size do: [ :i |
          anObject := aBag _at: i.
          self btreeAt: anObject put: anObject.
          indexMgr commitIndexMaintenance: self at: i.
        ]
      ]
      ifFalse: [
        1 to: aBag size do: [ :i |
          anObject := aBag _at: i.
          self btreeAt: anObject put: anObject.
        ]
      ]
  ].
%

category: 'Updating Indexes'
method: RangeEqualityIndex
preIndexCreation

"Determine if a merge sort is necessary.  If so, place a path sorter
 as the btreeRoot (will be replaced with a B-tree node after the merge
 sort).  Returns the original btreeRoot node. "

| saveNode |
super preIndexCreation.

" check if all mappings will fit in a single B-tree node "
nscRoot size > btreeRoot class maxNumberOfElements
  ifTrue: [
    saveNode := btreeRoot.
    btreeRoot := PathSorter on: #[ self ] directions: #( true ).
    " initialize offset of current node to update in sort node Array "
    btreeRoot lastNodeOffset: 1.
    ^ saveNode
  ].
^ btreeRoot
%

category: 'Updating Indexes'
method: RangeEqualityIndex
postIndexCreation: originalBtreeRoot

"Use a merge sort to create a complete B-tree from a PathSorter
stored in the btreeRoot instance variable."

" see if merge sort necessary "
btreeRoot isBtreeNode
	ifFalse: [ | leafNodes pathSorter |
		" create an Array containing an empty B-tree node "
		leafNodes := #[ originalBtreeRoot ].

		pathSorter := btreeRoot. 
        "per bug 36147, we need the leafNodes array to be persistent
         to avoid some out-of-memory conditions during index creation"
		btreeRoot := #[ leafNodes, pathSorter ]. 

		" produce an Array containing many B-tree leaf nodes, all sorted "
		pathSorter sortIntoBtreeNodes: leafNodes.
		" now build up interior nodes for the leaves "
		btreeRoot := pathSorter createInteriorNodesFor: leafNodes.
	].

super postIndexCreation: originalBtreeRoot.
%

! deleted _count v2.0

! deleted _max v2.0

! deleted _mean v2.0

! deleted _median v2.0

! deleted _min v2.0

! deleted _nonNilCount v2.0

! deleted _sum v2.0

category: 'Testing'
method: RangeEqualityIndex
_canCompareWith: aKey

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

aKey == nil
    ifTrue: [ ^ true ].

^ btreeRoot _canCompare: aKey withClass: lastElementClass
%

category: 'Updating'
method: RangeEqualityIndex
_setPathTermState

"For each path term but the last, indicate the need to update the index
 dictionary.  For the last path term, indicate the need to update the B-tree.
 Indicate if the last object along the path needs a dependency list."

| lastPathTerm |
1 to: self size - 1 do: [ :i |
    (self at: i) updateDict: indexDictionary.
].
lastPathTerm := self at: self size.
lastPathTerm updateBtree: self.

"If any of the instances could be byteIndexable or nonInvariant, then
 a dependencyList is needed. (bug 36599)."
(lastElementClass allSubclasses, #[ lastElementClass ]) do: [:cl |
  (cl isBytes _and: [ cl instancesInvariant not])
    ifTrue: [ 
      lastPathTerm needsDepList: true.
      ^self 
    ].
].
%
category: 'Sorting'
method: RangeEqualityIndex
_getSecondarySorterOn: indexObjs directions: theBooleans

"Returns a PathSorter if one is needed to perform secondary sorting;
 otherwise returns nil."

| directions traversers |

indexObjs size > 1
  ifTrue: [
    directions := Array new: indexObjs size - 1.
    theBooleans copyFrom: 2 to: indexObjs size into: directions startingAt: 1.
    traversers := Array new: indexObjs size - 1.
    indexObjs copyFrom: 2 to: indexObjs size into: traversers startingAt: 1.
    ^ PathSorter on: traversers directions: directions.
  ]
  ifFalse: [ ^ nil ].
%

category: 'Sorting'
method: RangeEqualityIndex
_getObjectsWithNilOnPath

"Returns an Array containing each object that has a nil value along the path."

| array |
" gather the root objects with nil on the path "
array := Array new.
1 to: self size - 1 do: [ :i |
    self _addAllFor: nil
        into: array
        offset: i
        pathTerm: (self at: i)
].
^ array
%

category: 'Sorting'
method: RangeEqualityIndex
_sortAscendingOn: indexObjs directions: theBooleans

""

| array cnt prevKey prevVal marker sorter btreeOnly offset pathTerm tmpArray 
  stream val |

prevKey := #_incompletePathTraversal.
prevVal := #_incompletePathTraversal.

" create the Array to hold the objects "
array := Array new: nscRoot size.

" build a sorter to be used for secondary sorts "
sorter := self _getSecondarySorterOn: indexObjs directions: theBooleans.

" start the insertion into the Array at the beginning "
self isIndexOnRootNsc
    ifTrue: [ cnt := 0 ]
    ifFalse: [ cnt := nscRoot _idxOccurrencesOf: nil ].

" gather objects with nil along the path "
tmpArray := self _getObjectsWithNilOnPath.
1 to: tmpArray size do: [ :i |
    cnt := cnt + 1.
    array at: cnt put: (tmpArray at: i)
].

btreeOnly := self size == 1.
" if no secondary sorts "
sorter == nil
  ifTrue: [
    " if path length of one "
    btreeOnly
      ifTrue: [
        btreeRoot _putAscendingValuesInto: array startingAt: cnt + 1.
      ]
      ifFalse: [
        offset := self lastPathComponentsDictionaryOffset max: 1.
        pathTerm := self at: offset.
        tmpArray := Array new.

        stream := BtreeReadStream on: btreeRoot.
        [ stream atEnd ] whileFalse: [
          val := stream _btreeNext.
         (val == prevVal)
            ifFalse: [
              self _addAllFor: val into: tmpArray offset: offset pathTerm: pathTerm.
              1 to: tmpArray size do: [ :i |
                cnt := cnt + 1.
                array at: cnt put: (tmpArray at: i)
              ].
              tmpArray size: 0
            ].
          prevVal := val
        ]
      ].
    ^ array
  ].

" must check for possibility of duplicate keys (there is a secondary sort) "
marker := cnt max: 1.
offset := self lastPathComponentsDictionaryOffset max: 1.
pathTerm := self at: offset.
tmpArray := Array new.

" Iterate over the key/values in the B-tree leaf nodes "
btreeRoot _leafKeysAndValuesDo: [ :key :value |

  btreeOnly
    ifTrue: [
      cnt := cnt + 1.
      array at: cnt put: value.
    ]
    ifFalse: [
     (value == prevVal)
        ifFalse: [
          self _addAllFor: value into: tmpArray offset: offset pathTerm: pathTerm.
          1 to: tmpArray size do: [ :i |
            cnt := cnt + 1.
            array at: cnt put: (tmpArray at: i)
          ].
          tmpArray size: 0
        ]
    ].

    " see if finished a run of duplicate keys "
    key ~= prevKey
      ifTrue: [
        marker < (cnt - 1)
          ifTrue: [ " sort on secondary keys "
            marker to: cnt - 1 do: [ :i | sorter addObject: (array at: i) ].
            sorter sortInto: array startingAt: marker.
            sorter clear
          ].
        marker := cnt
      ].
    prevKey := key.
    prevVal := value
].
" see if ending with duplicate keys "
( sorter ~~ nil _and: [ marker < cnt ] )
    ifTrue: [ " sort on secondary keys "
       marker to: cnt do: [ :i | sorter addObject: (array at: i) ].
       sorter sortInto: array startingAt: marker.
       sorter clear
    ].

^ array
%

category: 'Sorting'
method: RangeEqualityIndex
_sortDescendingOn: indexObjs directions: theBooleans

""

| array cnt prevKey prevVal marker sorter btreeOnly offset pathTerm tmpArray 
  stream val |

prevKey := #_incompletePathTraversal.
prevVal := #_incompletePathTraversal.

" create the Array to hold the objects "
array := Array new: nscRoot size.

" build a sorter to be used for secondary sorts "
sorter := self _getSecondarySorterOn: indexObjs directions: theBooleans.

" start the insertion into the Array at the beginning "
self isIndexOnRootNsc
    ifTrue: [ cnt := array size  ]
    ifFalse: [ cnt := array size - (nscRoot _idxOccurrencesOf: nil) ].

" gather objects with nil along the path "
tmpArray := self _getObjectsWithNilOnPath.
1 to: tmpArray size do: [ :i |
    array at: cnt put: (tmpArray at: i).
    cnt := cnt - 1.
].

" if path length of one and no secondary sorts,
  optimize putting objects in the result Array "
btreeOnly := self size == 1.
sorter == nil
  ifTrue: [
    btreeOnly
      ifTrue: [
        btreeRoot _putDescendingValuesInto: array startingAt: cnt.
      ]
      ifFalse: [
        offset := self lastPathComponentsDictionaryOffset max: 1.
        pathTerm := self at: offset.
        tmpArray := Array new.

        stream := BtreeReadStream on: btreeRoot.
        [ stream atEnd ] whileFalse: [
          val := stream _btreeNext.

          (val == prevVal)
            ifFalse: [
              self _addAllFor: val into: tmpArray offset: offset pathTerm: pathTerm.
              1 to: tmpArray size do: [ :i |
                array at: cnt put: (tmpArray at: i).
                cnt := cnt - 1.
              ].
              tmpArray size: 0
            ].
          prevVal := val.
        ]
      ].
    ^ array
  ].

" iterate over the receiver looking for duplicate keys "
marker := cnt.
offset := self lastPathComponentsDictionaryOffset max: 1.
pathTerm := self at: offset.
tmpArray := Array new.

" iterate over the key/values in the B-tree leaf nodes "
btreeRoot _leafKeysAndValuesDo: [ :key :value |
  btreeOnly
    ifTrue: [ 
      array at: cnt put: value.
      cnt := cnt - 1.
    ]
    ifFalse: [
      (value == prevVal)
        ifFalse: [
          self _addAllFor: value into: tmpArray offset: offset pathTerm: pathTerm.
            1 to: tmpArray size do: [ :i |
              array at: cnt put: (tmpArray at: i).
              cnt := cnt - 1.
            ].
            tmpArray size: 0
        ]
    ].

    " see if finished a run of duplicate keys "
    key ~= prevKey
      ifTrue: [
        marker > (cnt + 1)
          ifTrue: [ " sort on secondary keys "
            cnt + 2 to: marker do: [ :i | sorter addObject: (array at: i) ].
            sorter sortInto: array startingAt: cnt + 2.
            sorter clear
          ].
        marker := cnt + 1
      ].
    prevKey := key.
    prevVal := value.
].

" see if ending with duplicate keys "
( sorter ~~ nil _and: [ marker > 1 ] )
  ifTrue: [ " sort on secondary keys "
   1 to: marker do: [ :i | sorter addObject: (array at: i) ].
   sorter sortInto: array startingAt: 1.
     sorter clear
    ].
^ array
%

category: 'Sorting'
method: RangeEqualityIndex
_sortOn: indexObjs directions: theBooleans persistentRoot: persistentArrayOrNil

"Returns an Array of objects from the root NSC that is sorted according to the
 paths traversed by indexObjs (with the direction of the sort specified in
 theBooleans)."

(theBooleans at: 1)
    ifTrue: [ ^ self _sortAscendingOn: indexObjs directions: theBooleans ]
    ifFalse: [ ^ self _sortDescendingOn: indexObjs directions: theBooleans ]
%

category: 'Statistics'
method: RangeEqualityIndex
_statisticsInto: dict

"Puts statistical information into the given dictionary."

| arr arr1 arr2 |
arr := dict at: #BtreeSpaceUtilization ifAbsent: [
  dict
    at: #BtreeSpaceUtilization
    put: (Array with: Array new with: Array new)
].

arr1 := arr at: 1.
arr2 := arr at: 2.

btreeRoot _preOrderDo: [ :node |
  arr1 add: node numElements.
  arr2 add: node class maxNumberOfElements.
].
%

category: 'Accessing'
method: RangeEqualityIndex
nwayMergeProgress

"Returns the progress count of the n-way merge during index creation.
 Returns nil if index creation is complete."

btreeRoot isBtreeNode
  ifTrue: [ ^ nil ].

^ btreeRoot sortNodes progress
%

category: 'Updating'
method: RangeEqualityIndex
_clear

"Assigns nil to important instance variables."

btreeRoot := nil.
lastElementClass := nil.
super _clear.
%

category: 'Converting'
method: RangeEqualityIndex
asQueryEvaluator

  ^EqualityIndexQueryEvaluator on: self
%

category: 'Updating'
method: RangeEqualityIndex
changeToSegment: aSegment

"Assign the receiver and its B-tree to the given segment."

self assignToSegment: aSegment.
btreeRoot changeToSegment: aSegment
%

