The Trunk: Collections-ul.819.mcz

Levente Uzonyi uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-ul.819.mcz

==================== Summary ====================

Name: Collections-ul.819
Author: ul
Time: 3 February 2019, 6:41:04.151586 pm
UUID: 73993c05-fb6d-497a-9d99-2087eff4e1a4
Ancestors: Collections-pre.818

- merge sort tweaks

=============== Diff against Collections-pre.818 ===============

Item was changed:
  ----- Method: ArrayedCollection>>mergeFirst:middle:last:into:by: (in category 'sorting') -----
  mergeFirst: first middle: middle last: last into: dst by: aBlock
  "Private. Merge the sorted ranges [first..middle] and [middle+1..last]
  of the receiver into the range [first..last] of dst."
 
  | i1 i2 val1 val2 out |
  i1 := first.
  i2 := middle + 1.
  val1 := self at: i1.
  val2 := self at: i2.
  out := first - 1.  "will be pre-incremented"
 
  "select 'lower' half of the elements based on comparator"
+ [ (i1 <= middle) and: [ i2 <= last ] ] whileTrue: [
- [ (i1 <= middle) and: [ i2 <= last ] ] whileTrue: [
  (aBlock
  ifNil: [ val1 <= val2 ]
  ifNotNil: [ aBlock value: val1 value: val2 ])
  ifTrue: [
  dst at: (out := out + 1) put: val1.
  val1 := self at: (i1 := i1 + 1)]
  ifFalse: [
  dst at: (out := out + 1) put: val2.
+ val2 := self atWrap: (i2 := i2 + 1) ] ].
- (i2 := i2 + 1) <= last ifTrue: [
- val2 := self at: i2 ] ] ].
 
  "copy the remaining elements"
  i1 <= middle
  ifTrue: [dst replaceFrom: out + 1 to: last with: self startingAt: i1]
  ifFalse: [dst replaceFrom: out + 1 to: last with: self startingAt: i2]!

Item was changed:
  ----- Method: ArrayedCollection>>mergeSortFrom:to:by: (in category 'sorting') -----
  mergeSortFrom: startIndex to: stopIndex by: aBlock
  "Sort the given range of indices using the mergesort algorithm.
  Mergesort is a worst-case O(N log N) sorting algorithm that usually
  does only half as many comparisons as heapsort or quicksort."
 
  "Details: recursively split the range to be sorted into two halves,
  mergesort each half, then merge the two halves together. An extra
  copy of the data is used as temporary storage and successive merge
  phases copy data back and forth between the receiver and this copy.
  The recursion is set up so that the final merge is performed into the
  receiver, resulting in the receiver being completely sorted."
 
  | size |
  (size := self size) <= 1 ifTrue: [^ self].  "nothing to do"
  startIndex = stopIndex ifTrue: [^ self].
  1 <= startIndex ifFalse: [ self errorSubscriptBounds: startIndex ].
  stopIndex <= size ifFalse: [ self errorSubscriptBounds: stopIndex ].
  startIndex < stopIndex ifFalse: [ self errorSubscriptBounds: startIndex ].
+ self shallowCopy
- self
  mergeSortFrom: startIndex
  to: stopIndex
+ into: self
- src: self shallowCopy
- dst: self
  by: aBlock!

Item was added:
+ ----- Method: ArrayedCollection>>mergeSortFrom:to:into:by: (in category 'sorting') -----
+ mergeSortFrom: firstIndex to: lastIndex into: destination by: aBlock
+ "Private. Split the range to be sorted in half, sort each half, and
+ merge the two half-ranges into destination."
+
+ | n firstObject lastObject |
+ "Precondition: firstIndex <= lastIndex, self and destination contain the same elements between firstIndex and lastIndex inclusively but not necessarily in the same order"
+ (n := lastIndex - firstIndex) <= 1 ifTrue: [ "Handle 1 and 2 sized ranges directly."
+ n = 0 ifTrue: [ ^self ].
+ firstObject := self at: firstIndex.
+ lastObject := self at: lastIndex.
+ (aBlock
+ ifNil: [ firstObject <= lastObject ]
+ ifNotNil: [ aBlock value: firstObject value: lastObject ])
+ ifFalse: [
+ destination
+ at: lastIndex put: firstObject;
+ at: firstIndex put: lastObject ]
+ ifTrue: [
+ destination
+ at: lastIndex put: lastObject;
+ at: firstIndex put: firstObject ].
+ ^self ].
+ n := firstIndex + lastIndex // 2.
+ destination mergeSortFrom: firstIndex to: n into: self by: aBlock.
+ destination mergeSortFrom: n + 1 to: lastIndex into: self by: aBlock.
+ self mergeFirst: firstIndex middle: n last: lastIndex into: destination by: aBlock!

Item was removed:
- ----- Method: ArrayedCollection>>mergeSortFrom:to:src:dst:by: (in category 'sorting') -----
- mergeSortFrom: first to: last src: src dst: dst by: aBlock
- "Private. Split the range to be sorted in half, sort each half, and
- merge the two half-ranges into dst."
-
- | middle |
- first = last ifTrue: [^ self].
- middle := (first + last) // 2.
- self mergeSortFrom: first to: middle src: dst dst: src by: aBlock.
- self mergeSortFrom: middle + 1 to: last src: dst dst: src by: aBlock.
- src mergeFirst: first middle: middle last: last into: dst by: aBlock!