#TUNING by exept
class: Heap
changed:
#downHeap: (send #== instead of #=)
#downHeapSingle: (send #== instead of #=)
#firstOrNil (send #== instead of #=)
#isEmpty (send #== instead of #=)
#upHeap: (send #== instead of #=)
--- a/Heap.st Sun Sep 08 14:23:13 2019 +0200
+++ b/Heap.st Sun Sep 08 15:30:23 2019 +0200
@@ -1,3 +1,5 @@
+"{ Encoding: utf8 }"
+
"{ Package: 'stx:libbasic2' }"
"{ NameSpace: Smalltalk }"
@@ -156,7 +158,7 @@
!
firstOrNil
- tally = 0 ifTrue:[^nil] ifFalse:[^array at: 1]
+ tally == 0 ifTrue:[^nil] ifFalse:[^array at: 1]
!
reSort
@@ -274,67 +276,67 @@
!Heap methodsFor:'private-heap'!
downHeap: anIndex
- "Check the heap downwards for correctness starting at anIndex.
- Everything above (i.e. left of) anIndex is ok."
- | value k n j |
- anIndex = 0 ifTrue:[^self].
- n := tally bitShift: -1.
- k := anIndex.
- value := array at: anIndex.
- [k <= n] whileTrue:[
- j := k + k.
- "use max(j,j+1)"
- (j < tally and:[self sorts: (array at: j+1) before: (array at: j)])
- ifTrue:[ j := j + 1].
- "check if position k is ok"
- (self sorts: value before: (array at: j))
- ifTrue:[ "yes -> break loop"
- n := k - 1]
- ifFalse:[ "no -> make room at j by moving j-th element to k-th position"
- array at: k put: (array at: j).
- "and try again with j"
- k := j]].
- array at: k put: value.
+ "Check the heap downwards for correctness starting at anIndex.
+ Everything above (i.e. left of) anIndex is ok."
+ | value k n j |
+ anIndex == 0 ifTrue:[^self].
+ n := tally bitShift: -1.
+ k := anIndex.
+ value := array at: anIndex.
+ [k <= n] whileTrue:[
+ j := k + k.
+ "use max(j,j+1)"
+ (j < tally and:[self sorts: (array at: j+1) before: (array at: j)])
+ ifTrue:[ j := j + 1].
+ "check if position k is ok"
+ (self sorts: value before: (array at: j))
+ ifTrue:[ "yes -> break loop"
+ n := k - 1]
+ ifFalse:[ "no -> make room at j by moving j-th element to k-th position"
+ array at: k put: (array at: j).
+ "and try again with j"
+ k := j]].
+ array at: k put: value.
!
downHeapSingle: anIndex
- "This version is optimized for the case when only one element in the receiver can be at a wrong position. It avoids one comparison at each node when travelling down the heap and checks the heap upwards after the element is at a bottom position. Since the probability for being at the bottom of the heap is much larger than for being somewhere in the middle this version should be faster."
- | value k n j |
- anIndex = 0 ifTrue:[^self].
- n := tally bitShift: -1.
- k := anIndex.
- value := array at: anIndex.
- [k <= n] whileTrue:[
- j := k + k.
- "use max(j,j+1)"
- (j < tally and:[self sorts: (array at: j+1) before: (array at: j)])
- ifTrue:[ j := j + 1].
- array at: k put: (array at: j).
- "and try again with j"
- k := j].
- array at: k put: value.
- self upHeap: k
+ "This version is optimized for the case when only one element in the receiver can be at a wrong position. It avoids one comparison at each node when travelling down the heap and checks the heap upwards after the element is at a bottom position. Since the probability for being at the bottom of the heap is much larger than for being somewhere in the middle this version should be faster."
+ | value k n j |
+ anIndex == 0 ifTrue:[^self].
+ n := tally bitShift: -1.
+ k := anIndex.
+ value := array at: anIndex.
+ [k <= n] whileTrue:[
+ j := k + k.
+ "use max(j,j+1)"
+ (j < tally and:[self sorts: (array at: j+1) before: (array at: j)])
+ ifTrue:[ j := j + 1].
+ array at: k put: (array at: j).
+ "and try again with j"
+ k := j].
+ array at: k put: value.
+ self upHeap: k
!
upHeap: anIndex
- "Check the heap upwards for correctness starting at anIndex.
- Everything below anIndex is ok."
- | value k kDiv2 tmp |
- anIndex = 0 ifTrue:[^self].
- k := anIndex.
- value := array at: anIndex.
- [ (k > 1) and:[self sorts: value before: (tmp := array at: (kDiv2 := k bitShift: -1))] ]
- whileTrue:[
- array at: k put: tmp.
- k := kDiv2].
- array at: k put: value.
+ "Check the heap upwards for correctness starting at anIndex.
+ Everything below anIndex is ok."
+ | value k kDiv2 tmp |
+ anIndex == 0 ifTrue:[^self].
+ k := anIndex.
+ value := array at: anIndex.
+ [ (k > 1) and:[self sorts: value before: (tmp := array at: (kDiv2 := k bitShift: -1))] ]
+ whileTrue:[
+ array at: k put: tmp.
+ k := kDiv2].
+ array at: k put: value.
! !
!Heap methodsFor:'queries'!
isEmpty
- "Answer whether the receiver contains any elements."
- ^tally = 0
+ "Answer whether the receiver contains any elements."
+ ^tally == 0
!
sorts: element1 before: element2