!=========================================================================
! Copyright (C) VMware, Inc. 1986-2011.  All Rights Reserved.
!
! $Id: sortnodearray.gs,v 1.12 2008-01-09 22:50:19 stever Exp $
!
! Superclass Hierarchy:
!   SortNodeArray, Array, SequenceableCollection, Collection, Object.
!
!=========================================================================

! class created in idxclasses.topaz

removeallmethods SortNodeArray
removeallclassmethods SortNodeArray

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

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

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

doc documentClassWith: txt.

self description: doc.
%

! ------------------- Class methods for SortNodeArray
! ------------------- Instance methods for SortNodeArray
category: 'Sorting'
method: SortNodeArray
binaryMergeAscendingInto: anArray startingAt: index

"Performs a binary merge sort on the sort nodes in the receiver, placing the
 sorted objects in anArray beginning at the given index.  Returns the number
 inserted."

| i1 i2 j eSize sz1 sz2 node1 node2 val snarray indexManager |
j := index.
node1 := self _at: 1.
node2 := self _at: 2.
eSize := node1 entrySize.
i1 := 2.
sz1 := node1 numElements * eSize.
i2 := 2.
sz2 := node2 numElements * eSize.
snarray := SortNodeArray.

" while both nodes have entries not in the result Array "
indexManager := self indexManager.
[ i1 <= sz1 _and: [ i2 <= sz2 ] ] whileTrue: [
  " find which node has the lesser entry "
  (node1 _compareEntryAt: i1
    lessThanNode: node2
    entryAt: i2
    useValue: false)
    ifTrue: [
      val := node1 _at: i1 - 1.
      i1 := i1 + eSize
    ]
    ifFalse: [
      val := node2 _at: i2 - 1.
      i2 := i2 + eSize
    ].
  " if it is an Array of nodes, then a merge sort is needed "
  (val isKindOf: snarray)
    ifTrue: [
      val sortInto: anArray startingAt: j.
      j := j + val totalElements
    ]
    ifFalse: [
      anArray at: j put: val.
      j := j + 1
    ].
  indexManager commitIndexMaintenance: self at: j.
].
" put remaining entries from either node1 or node2 into anArray "
i1 <= sz1
  ifTrue: [
    i1 - 1 to: sz1 by: eSize do: [ :i |
      val := node1 _at: i.
      (val isKindOf: snarray)
        ifTrue: [
          val sortInto: anArray startingAt: j.
          j := j + val totalElements
        ]
        ifFalse: [
          anArray at: j put: val.
          j := j + 1
        ].
    indexManager commitIndexMaintenance: self at: i.
    ]
  ]
  ifFalse: [
    i2 - 1 to: sz2 by: eSize do: [ :i |
      val := node2 _at: i.
      (val isKindOf: snarray)
        ifTrue: [
          val sortInto: anArray startingAt: j.
          j := j + val totalElements
        ]
        ifFalse: [
          anArray at: j put: val.
          j := j + 1
        ].
    indexManager commitIndexMaintenance: self at: i.
    ]
  ].
^ j - index
%

category: 'Sorting'
method: SortNodeArray
binaryMergeDescendingInto: anArray startingAt: index

"Perform a binary merge sort on the sort nodes in the receiver, placing the
 sorted objects in anArray beginning at the given index.  Returns the number
 inserted."

| i1 i2 j k eSize sz1 sz2 node1 node2 val snarray num indexManager |
node1 := self _at: 1.
node2 := self _at: 2.
eSize := node1 entrySize.
i1 := 2.
sz1 := node1 numElements * eSize.
i2 := 2.
sz2 := node2 numElements * eSize.
num := node1 totalElements + node2 totalElements.
j := index + num - 1.
snarray := SortNodeArray.

" while both nodes have entries not in the result Array "
indexManager := self indexManager.
[ i1 <= sz1 _and: [ i2 <= sz2 ] ] whileTrue: [
  " find which node has the lesser entry "
  (node1 _compareEntryAt: i1
    lessThanNode: node2
    entryAt: i2
    useValue: false)
    ifTrue: [
      val := node1 _at: i1 - 1.
      i1 := i1 + eSize
    ]
    ifFalse: [
      val := node2 _at: i2 - 1.
      i2 := i2 + eSize
    ].
  " if it is an Array of nodes, then a merge sort is needed "
  (val isKindOf: snarray)
    ifTrue: [
      k := j - val totalElements + 1.
      val sortInto: anArray startingAt: k.
      j := k - 1
    ]
    ifFalse: [
      anArray at: j put: val.
      j := j - 1
    ].
  indexManager commitIndexMaintenance: self at: j.
].
" put remaining entries from either node1 or node2 into anArray "
i1 <= sz1
  ifTrue: [
    i1 - 1 to: sz1 by: eSize do: [ :i |
      val := node1 _at: i.
      (val isKindOf: snarray)
        ifTrue: [
          k := j - val totalElements + 1.
          val sortInto: anArray startingAt: k.
          j := k - 1
        ]
        ifFalse: [
          anArray at: j put: val.
          j := j - 1
        ].
    indexManager commitIndexMaintenance: self at: i.
    ]
  ]
  ifFalse: [
    i2 - 1 to: sz2 by: eSize do: [ :i |
      val := node2 _at: i.
      (val isKindOf: snarray)
        ifTrue: [
          k := j - val totalElements + 1.
          val sortInto: anArray startingAt: k.
          j := k - 1
        ]
        ifFalse: [
          anArray at: j put: val.
          j := j - 1
        ].
    indexManager commitIndexMaintenance: self at: i.
    ]
  ].
^ num
%

category: 'Sorting'
method: SortNodeArray
nwayMergeAscendingInto: anArray startingAt: index

"Perform a simple n-way merge sort on the sort nodes in the receiver, placing
 the sorted objects in anArray beginning at the given index.  Returns the number
 inserted."

| offsets sizes j k eSize total sz minIndex val root leafArray minRun
nodeClass snarray indexManager |
nodeClass := (self _at: 1) class.
total := 0.
sz := self size.
offsets := Array new: sz.
sizes := Array new: sz.
leafArray := Array new: sz.
1 to: sz do: [ :i |
    " initial offsets into the entry in each run (a SortNode) "
    offsets at: i put: 2.
    " the size of each run "
    sizes at: i put: (self at: i) _lastIndex.
    " the selection tree leaf node for each run "
     leafArray at: i put: #[ i, nil ].
    " total number of entries (for all runs) "
    total := total + (self at: i) totalElements
].
eSize := (self at: 1) entrySize.
snarray := SortNodeArray.

" build the selection tree and get the root "
root := self _buildInteriorSelectionTreeNodesFor: leafArray.

" j is the offset in anArray in which to insert entries "
j := index.
indexManager := self indexManager.
1 to: total do: [ :count |
    " root of selection tree points to the run with the minimum entry "
    minIndex := root at: 1.
    " get the run that contains the minimum entry "
    minRun := self at: minIndex.
    " k points to the entry in the run "
    k := offsets at: minIndex.

    k == nil
      ifTrue: [ ^ self ].

    val := (self at: minIndex) _at: k - 1.
    (val isKindOf: snarray)
        ifTrue: [ " if it is an Array of nodes, then a merge sort is needed "
            val sortInto: anArray startingAt: j.
            j := j + val totalElements
        ]
        ifFalse: [
            anArray at: j put: val.
            j := j + 1
        ].

    " if reached the end of this run "
    (k + eSize) > (sizes at: minIndex)
        " put nil in the Array of offsets "
        ifTrue: [ offsets at: minIndex put: nil ]
        " otherwise, increment the offset "
        ifFalse: [ offsets at: minIndex put: k + eSize ].

    " reorganize the selection tree and get the root "
    nodeClass recalculateSelectionTree: self
      for: (leafArray at: minIndex)
      offsets: offsets.
    indexManager commitIndexMaintenance: self at: count.
].
^ total
%

category: 'Sorting'
method: SortNodeArray
nwayMergeDescendingInto: anArray startingAt: index

"Perform a simple n-way merge sort on the sort nodes in the receiver, placing
 the sorted objects in anArray beginning at the given index.  Returns the number
 inserted."

| offsets sizes j k m eSize total sz minIndex val root leafArray minRun
nodeClass snarray indexManager |
nodeClass := (self _at: 1) class.
total := 0.
sz := self size.
offsets := Array new: sz.
sizes := Array new: sz.
leafArray := Array new: sz.
1 to: sz do: [ :i |
    " initial offsets into the entry in each run (a SortNode) "
    offsets at: i put: 2.
    " the size of each run "
    sizes at: i put: (self at: i) _lastIndex.
    " the selection tree leaf node for each run "
     leafArray at: i put: #[ i, nil ].
    " total number of entries (for all runs) "
    total := total + (self at: i) totalElements
].
j := index + total - 1.
eSize := (self at: 1) entrySize.
snarray := SortNodeArray.

" build the selection tree and get the root "
root := self _buildInteriorSelectionTreeNodesFor: leafArray.

" j is the offset in anArray in which to insert entries "
j := index + total - 1.

indexManager := self indexManager.
1 to: total do: [ :count |
    " root of selection tree points to the run with the minimum entry "
    minIndex := root at: 1.
    " get the run that contains the minimum entry "
    minRun := self at: minIndex.
    " k points to the entry in the run "
    k := offsets at: minIndex.

    k == nil
      ifTrue: [ ^ self ].

    val := (self at: minIndex) _at: k - 1.
    (val isKindOf: snarray)
        ifTrue: [ " if it is an Array of nodes, then a merge sort is needed "
            m := j - val totalElements + 1.
            val sortInto: anArray startingAt: m.
            j := m - 1
        ]
        ifFalse: [
            anArray at: j put: val.
            j := j - 1
        ].

    " if reached the end of this run "
    (k + eSize) > (sizes at: minIndex)
        " put nil in the Array of offsets "
        ifTrue: [ offsets at: minIndex put: nil ]
        " otherwise, increment the offset "
        ifFalse: [ offsets at: minIndex put: k + eSize ].

    " reorganize the selection tree and get the root "
    nodeClass recalculateSelectionTree: self
      for: (leafArray at: minIndex)
      offsets: offsets.
    indexManager commitIndexMaintenance: self at: count.
].
^ total
%

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

"Perform a merge sort on the sort nodes contained in the receiver.  Returns
 the number of entries that were copied."

| firstNode sortAscending |
firstNode := self at: 1.

self size == 1
  ifTrue: [ ^ firstNode sortInto: anArray startingAt: index ].

sortAscending := firstNode pathSorter directions at: firstNode sortLevel.

self size == 2
  ifTrue: [
    sortAscending
      ifTrue: [ ^ self binaryMergeAscendingInto: anArray startingAt: index ]
      ifFalse: [ ^ self binaryMergeDescendingInto: anArray startingAt: index ]
  ].

sortAscending
  ifTrue: [ ^ self nwayMergeAscendingInto: anArray startingAt: index ]
  ifFalse: [ ^ self nwayMergeDescendingInto: anArray startingAt: index ]
%

category: 'Accessing'
method: SortNodeArray
totalElements

"Returns the sum of the totalElements of the receiver's contents."

| total |
total := 0.
1 to: self size do: [ :i |
    total := total + (self at: i) totalElements
].
^ total
%

category: 'Indexing Support'
method: SortNodeArray
nwayMergeIntoBtreeNodes: anArray

"Put all of the receiver's entries in the B-tree leaf nodes contained
 in anArray using an n-way merge.  If there are not enough B-tree
 leaf nodes, create more."

| offsets sizes j k delta eSize total sz minIndex currNode entryLimit 
root leafArray minRun aSegment nodeClass indexManager |
nodeClass := (self _at: 1) class.
total := 0.
sz := self size.
offsets := Array new: sz.
sizes := Array new: sz.
leafArray := Array new: sz.
1 to: sz do: [ :i |
    " initial offsets into the entry in each run (a SortNode) "
    offsets at: i put: 2. "key offset"
    " the size of each run "
    sizes at: i put: (self at: i) _lastIndex.
    " the selection tree leaf node for each run "
    leafArray at: i put: #[ i, nil ].
    " total number of entries (for all runs) "
    total := total + (self at: i) totalElements
].
eSize := (self at: 1) entrySize.
delta := eSize - 2.

" Current B-tree node to insert entries "
currNode := anArray at: 1.
aSegment := currNode segment.
entryLimit := currNode maxNumWhenMerging * eSize.

" build the selection tree and get the root "
root := self _buildInteriorSelectionTreeNodesFor: leafArray.

" j is the offset in the current interior node in which to insert entries "
j := 1.
indexManager := self indexManager.
1 to: total do: [ :i |
    " root of selection tree points to the run with the minimum entry "
    minIndex := root at: 1.
    " get the run that contains the minimum entry "
    minRun := self at: minIndex.
    " k points to the entry in the run "
    k := offsets at: minIndex.

    k == nil
      ifTrue: [ ^ self ].

    " put entry in B-tree node "
    minRun copyFrom: k - 1 to: k + delta into: currNode startingAt: j.

    j := j + eSize.
    currNode _incrementNumElements.

    " if filled up the current node and more elements remaining, get a new one "
    ((j > entryLimit) & (i < total))
        ifTrue: [
            currNode := currNode class new.
            currNode assignToSegment: aSegment.
            anArray add: currNode.
            j := 1
        ].

    " if reached the end of this run "
    (k + eSize) > (sizes at: minIndex)
        " put nil in the Array of offsets "
        ifTrue: [ offsets at: minIndex put: nil ]
        " otherwise, increment the offset "
        ifFalse: [ offsets at: minIndex put: k + eSize ].

    " reorganize the selection tree and get the root "
    nodeClass recalculateSelectionTree: self
      for: (leafArray at: minIndex)
      offsets: offsets.

    indexManager commitIndexMaintenance: self at: i.
]
%

category: 'Indexing Support'
method: SortNodeArray
_buildInteriorSelectionTreeNodesFor: nodeArray

"Build the interior nodes for a selection tree from the given Array of
 nodes.  Returns the root of the selection tree."

"A selection tree is used to determine the run with the minimum entry
 for an n-way merge sort.  See page 394, 'Fundamentals of Data Structures' by
 Horowitz and Sahni, Computer Science Press, 1976, ISBN 0-914894-20 for
 an explanation of how they are used."

"For this implementation, the nodes in the tree are represented as
 nested Arrays.

A leaf node consists of 3 elements:
#[ anInteger, < the offset in the SortNodeArray of the corresponding SortNode >
anArray ]     < its parent node >

An interior node consists of 5 elements:
#[ anInteger, < the offset in the SortNodeArray of the minimum child node's
                corresponding SortNode >
anArray,      < its parent node >
anArray,      < its left child >
anArray ]     < its right child >
"

| array node1 node2 offset1 offset2 newNode sz |

" if only one node in the Array, it is the root "
(sz := nodeArray size) == 1
    ifTrue: [ ^ nodeArray at: 1 ].

array := Array new.
" for each pair of nodes in the node Array "
1 to: (sz // 2) * 2 by: 2 do: [ :i |
    node1 := nodeArray at: i.
    node2 := nodeArray at: i + 1.
    " get the offset in the receiver of the corresponding run "
    offset1 := node1 at: 1.
    offset2 := node2 at: 1.

    " determine which run contains the minimum entry "
    ( (self at: offset1)
        _compareEntryAt: 2
        lessThanNode: (self at: offset2)
        entryAt: 2
        useValue: true)
        ifTrue: [ newNode := #[ offset1, nil, node1, node2 ] ]
        ifFalse: [ newNode := #[ offset2, nil, node1, node2 ] ].

    array add: newNode.
    " set the parent of each selection tree node "
    node1 at: 2 put: newNode.
    node2 at: 2 put: newNode.
].

" if there is a lone entry at the end "
sz odd
    ifTrue: [ array add: (nodeArray at: sz) ].

^ self _buildInteriorSelectionTreeNodesFor: array
%

category: 'Indexing Support'
method: SortNodeArray
sortIntoBtreeNodes: leafNodes

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

self size == 1
  ifTrue: [
    ^ (self at: 1) sortIntoBtreeNodes: leafNodes
  ].

^ self nwayMergeIntoBtreeNodes: leafNodes
%

category: 'Sorting'
method: SortNodeArray
sortInto: anArray startingAt: index incompletes: incompletes

"Perform a merge sort on the sort nodes contained in the receiver.  Returns
 the number of entries that were copied."

| firstNode sortAscending iArray offset num |
firstNode := self at: 1.
sortAscending := firstNode pathSorter directions at: firstNode sortLevel.

offset := index.

"if sort ascending, put objects that could not be traversed first in the Array"
sortAscending
  ifTrue: [ 
    | indexManager |
    indexManager := self indexManager.
    1 to: incompletes size do: [ :i |
      iArray := incompletes at: i.
      1 to: iArray size do: [ :j |
        anArray at: offset put: (iArray at: j).
        offset := offset + 1.
        indexManager commitIndexMaintenance: self at: j.
      ]
    ]
  ].

num := (self size == 1)
  ifTrue: [ firstNode sortInto: anArray startingAt: offset ]
  ifFalse: [
    self size == 2
      ifTrue: [
        sortAscending
          ifTrue: [ self binaryMergeAscendingInto: anArray startingAt: offset ]
          ifFalse: [ self binaryMergeDescendingInto: anArray startingAt: offset ]
      ]
      ifFalse: [
        sortAscending
            ifTrue: [ self nwayMergeAscendingInto: anArray startingAt: offset ]
            ifFalse: [ self nwayMergeDescendingInto: anArray startingAt: offset ].
      ]
  ].

"if sort descending, put objects that could not be traversed last in the Array"
sortAscending
  ifFalse: [
    | indexManager |
    indexManager := self indexManager.
    offset := offset + num.
    incompletes size downTo: 1 do: [ :i |
      iArray := incompletes at: i.
      1 to: iArray size do: [ :j |
        anArray at: offset put: (iArray at: j).
        offset := offset + 1.
        indexManager commitIndexMaintenance: self at: j.
      ]
    ]
  ]
%

category: 'Accessing'
method: SortNodeArray
progress

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

^progress
%

category: 'Updating'
method: SortNodeArray
progress: anInteger

"Sets the value of the instance variable 'progress'."

progress := anInteger
%
