#TUNING by exept
authorClaus Gittinger <cg@exept.de>
Sun, 08 Sep 2019 15:30:23 +0200
changeset 5206 dcadf2efcee0
parent 5205 c56119676a9c
child 5207 9c132367790a
#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 #=)
Heap.st
--- 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