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

removeallmethods PathSorter
removeallclassmethods PathSorter

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

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

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

doc documentClassWith: txt.

self description: doc.
%

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

"Disallowed.  To create a new instance, use the on:directions: method."

self shouldNotImplement: #new
%

category: 'Instance Creation'
classmethod: PathSorter
on: traversers directions: directions

"Returns a new initialized instance."

| newOne sortNode incompletes traverser |

newOne := super new.

1 to: traversers size do: [ :i |
    newOne add: (traversers at: i)
].

traverser := traversers at: 1.
incompletes := Array new.
traverser size timesRepeat: [ incompletes add: Array new ].

sortNode := (newOne sortNodeClassForSortLevel: 1) new: traverser nscRoot size.
sortNode sortLevel: 1.
sortNode pathSorter: newOne.

newOne sortNodes: (SortNodeArray with: sortNode).
newOne directions: directions.
newOne incompletes: incompletes.

^ newOne
%

! ------------------- Instance methods for PathSorter

category: 'Updating'
method: PathSorter
_addObject: anObject
inNodes: nodeArray
hasSecondarySort: hasSecondarySort
incompletes: incompleteArrays
incomplete: incomplete

"Adds anObject to the last sort node in nodeArray.  The key used to sort
 anObject is derived by traversing anObject on the receivers path specified by
 the last sort node in the node Array."

| node key sortLevel index sz lastNode |

hasSecondarySort
  ifTrue: [
    lastNode := nodeArray at: nodeArray size.

    key := (self at: lastNode sortLevel) _traverseObject: anObject
      incompletesInto: incompleteArrays
      incomplete: incomplete.
    incomplete == key
      ifTrue: [ ^ self ].

    " if last node is full, check for duplicate keys in all nodes,
      otherwise check in all but the last node "
    lastNode isFull
      ifTrue: [ sz := nodeArray size ]
      ifFalse: [ sz := nodeArray size - 1 ].

    1 to: sz do: [ :i |
      node := nodeArray at: i.
      index := node _findCoveringIndexForKey: key totalOrder: false.
      ( index > 0 _and:
      [ node _compareKey: key equalToEntryAt: (index + 1) ] )
        ifTrue: [ " found it "
          node totalElements: node totalElements + 1.
          ^ node _insertDuplicateKey: key value: anObject atIndex: index
        ]
    ].

    lastNode isFull
      ifTrue: [
        sortLevel := lastNode sortLevel.
        lastNode := lastNode class new: lastNode class maxNumberOfElements.
        lastNode sortLevel: sortLevel.
        lastNode pathSorter: self.
        nodeArray add: lastNode
      ].

    " add an entry to the sort node "
    lastNode _at: key
      put: anObject
      forBtree: false
      hasSecondarySort: hasSecondarySort
  ]
  ifFalse: [
    lastNode := nodeArray at: nodeArray size.
    " if the last sort node is full, create a new one "
    lastNode isFull
      ifTrue: [
        sortLevel := lastNode sortLevel.
        lastNode := lastNode class new: lastNode class maxNumberOfElements.
        lastNode sortLevel: sortLevel.
        lastNode pathSorter: self.
        nodeArray add: lastNode
      ].

    " traverse the object to get a key to sort by "
    incomplete == (key := (self at: lastNode sortLevel)
      _traverseObject: anObject
      incompletesInto: incompleteArrays
      incomplete: incomplete)
      ifFalse: [
        " add an entry to the sort node "
        lastNode _at: key
          put: anObject
          forBtree: false
          hasSecondarySort: hasSecondarySort
        ]
  ]
%

category: 'Updating'
method: PathSorter
_addObject: anObject
inNodes: nodeArray
hasSecondarySort: hasSecondarySort

"Adds anObject to the last sort node in nodeArray.  The key used to sort
 anObject is derived by traversing anObject on the receivers path specified by
 the last sort node in the node Array."

| node sortLevel index sz lastNode |

hasSecondarySort
  ifTrue: [
    lastNode := nodeArray at: nodeArray size.

    " if last node is full, check for duplicate keys in all nodes,
      otherwise check in all but the last node "
    lastNode isFull
      ifTrue: [ sz := nodeArray size ]
      ifFalse: [ sz := nodeArray size - 1 ].

    " see if any previous sort nodes contain this object "
    1 to: sz do: [ :i |
      node := nodeArray at: i.
      index := node _findCoveringIndexForKey: anObject totalOrder: false.
      ( index > 0 _and:
      [ node _compareKey: anObject equalToEntryAt: (index + 1) ] )
        ifTrue: [ " found it "
          node totalElements: node totalElements + 1.
          ^ node _insertDuplicateKey: anObject value: anObject atIndex: index
        ]
    ].

    lastNode isFull
      ifTrue: [
        sortLevel := lastNode sortLevel.
        lastNode := lastNode class new: lastNode class maxNumberOfElements.
        lastNode sortLevel: sortLevel.
        lastNode pathSorter: self.
        nodeArray add: lastNode
      ].

    " add an entry to the sort node "
    lastNode _at: anObject
      put: anObject
      forBtree: false
      hasSecondarySort: hasSecondarySort
  ]
  ifFalse: [
    lastNode := nodeArray at: nodeArray size.
    " if the last sort node is full, create a new one "
    lastNode isFull
      ifTrue: [
        sortLevel := lastNode sortLevel.
        lastNode := lastNode class new: lastNode numElements.
        lastNode sortLevel: sortLevel.
        lastNode pathSorter: self.
        nodeArray add: lastNode
    ].

  " add an entry to the sort node "
  lastNode _at: anObject
    put: anObject
    forBtree: false
    hasSecondarySort: hasSecondarySort
  ]
%

category: 'Updating'
method: PathSorter
addObject: anObject

"Adds anObject to the sort nodes maintained by the receiver."

self _addObject: anObject
  inNodes: sortNodes
  hasSecondarySort: (self size > 1)
  incompletes: incompletes
  incomplete: #_incompletePathTraversal
%

category: 'Updating'
method: PathSorter
clear

"Sets the state of the receiver so that no objects have been added to the sort
 node."

sortNodes size: 1.
(sortNodes at: 1) numElements: 0.
(sortNodes at: 1) totalElements: 0.
1 to: incompletes size do: [ :i |
  (incompletes at: i) size: 0
]
%

category: 'Accessing'
method: PathSorter
directions

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

^directions
%

category: 'Updating'
method: PathSorter
directions: newValue

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

directions := newValue
%

category: 'Accessing'
method: PathSorter
incompletes

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

^incompletes
%

category: 'Updating'
method: PathSorter
incompletes: newValue

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

incompletes := newValue
%

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

"Returns anArray filled with objects that have been added to the receiver, in
 sorted order."

sortNodes sortInto: anArray startingAt: index incompletes: incompletes.
^ anArray
%

category: 'Accessing'
method: PathSorter
sortNodes

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

^sortNodes
%

category: 'Updating'
method: PathSorter
sortNodes: newValue

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

sortNodes := newValue
%

category: 'Accessing'
method: PathSorter
sortNodeClassForSortLevel: anInteger

"Returns the class of SortNode to create for the given sort level."

| aClass |

aClass := (self at: anInteger) lastElementClass.
aClass == nil
    ifTrue: [ ^ SortNode ].

^ aClass sortNodeClass
%

category: 'Testing'
method: PathSorter
isBtreeNode

"Returns false, the receiver is not a B-tree node."

^ false
%

category: 'Indexing Support'
method: PathSorter
createInteriorNodesFor: nodeArray

"Construct B-tree interior nodes for the given Array of leaf nodes.
 Returns the root B-tree node."

| intNode eSize k node max nodeClass m n end array sz aSegment |

nodeArray size == 1
    ifTrue: [ ^ nodeArray at: 1 ].

node := nodeArray at: 1.
aSegment := node segment.

nodeClass := node parentNodeClass.
max := node maxNumWhenMerging.
eSize := node entrySize.
m := eSize - 2.
array := Array new.
sz := nodeArray size.

1 to: sz by: max do: [ :i |
    intNode := nodeClass new.
    intNode assignToSegment: aSegment.
    n := 1.
    end := (i + max - 1) min: sz.
    i to: end do: [ :j |
        node := nodeArray at: j.
        k := node numElements * eSize.  " offset of last slot "
        k > 0
            ifTrue: [
                node copyFrom: k - m to: k into: intNode startingAt: n + 1.
                intNode _at: n put: node.
                n := n + eSize
            ]
    ].
    n > 1
        ifTrue: [
            intNode numElements: end - i + 1.
            intNode lastValue: (intNode _at: n - eSize) lastValue.
            array add: intNode
        ]
].
array size == 1
    ifTrue: [ ^ array at: 1 ]
    ifFalse: [ ^ self createInteriorNodesFor: array ]
%

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

"Returns anArray filled with B-tree leaf nodes, in which all
 entries are in sorted order."

sortNodes sortIntoBtreeNodes: anArray.
^ anArray
%

category: 'Indexing Support'
method: PathSorter
btreeAt: aKey put: aValue for: anIndexObj logging: aBoolean

"Add key/value to the sort nodes maintained by the receiver. Compatability for Rc equality indexes."

^ self btreeAt: aKey put: aValue
%

category: 'Indexing Support'
method: PathSorter
btreeAt: aKey put: aValue

"Add key/value to the sort nodes maintained by the receiver."

| lastNode sortLevel |

lastNode := sortNodes at: self lastNodeOffset.
" if the last sort node is full, create a new one "
lastNode isFull
  ifTrue: [ | i |
    i := self lastNodeOffset + 1.
    self lastNodeOffset: i.
    sortLevel := lastNode sortLevel.
    lastNode := lastNode class new: lastNode numElements.
    lastNode sortLevel: sortLevel.
    lastNode pathSorter: self.
    sortNodes at: i put: lastNode
  ].

" add an entry to the sort node "
lastNode btreeAt: aKey put: aValue
%

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

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

^ (sortNodes at: 1) _canCompare: aKey withClass: aClass
%

category: 'Private'
method: PathSorter
_findAllValuesLessThanKey: aKey andEquals: bool into: array

"Raises an error because the receiver is currently in use building an index."

self _errorIndexCreationInProgress
%

category: 'Private'
method: PathSorter
_findAllValuesGreaterThanKey: aKey into: array

"Raises an error because the receiver is currently in use building an index."

self _errorIndexCreationInProgress
%

category: 'Private'
method: PathSorter
removeKey: aKey value: aValue

"Raises an error because the receiver is currently in use building an index."

self _errorIndexCreationInProgress
%

category: 'Private'
method: PathSorter
_findAllValuesForIdenticalKey: key into: array

"Raises an error because the receiver is currently in use building an index."

self _errorIndexCreationInProgress
%

category: 'Accessing'
method: PathSorter
lastNodeOffset

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

^lastNodeOffset
%

category: 'Updating'
method: PathSorter
lastNodeOffset: newValue

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

lastNodeOffset := newValue
%
