<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<style type="text/css" style="display:none;"><!-- P {margin-top:0;margin-bottom:0;} --></style>
</head>
<body dir="ltr">
<div id="divtagdefaultwrapper" dir="ltr" style="font-size:12pt; color:rgb(0,0,0); font-family:Calibri,Helvetica,sans-serif,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols">
<p>Hi all,</p>
<p><br>
</p>
<p>please find the attached changeset in which I'm proposing a set of new methods on SequenceableCollection that implement interpolation search in Squeak. Interpolation search works similar for linear search, but it is supplied a number indicating distance
rather than a binary/ternary information like binary search. Interpolation search is a bit slower for small collections because handling the distance value introduces some overhead, but it outperforms the other in the case of a) very large collections and
b) expensive block operations. In addition, the changeset contains tests for both all #findBinary: and all #findDelta: overloads.</p>
<p><br>
</p>
<p>The following example demonstrates usage + benchmarks of the new methods:</p>
<p><br>
</p>
<p></p>
<blockquote style="margin:0 0 0 40px; border:none; padding:0px">
<p></p>
<div>data := (1 to: 10000000) select: [:i | i isPrime].</div>
<div>probe := (1 to: 10000) collect: [:i | data atRandom].</div>
<div><br>
</div>
<div>[probe collect: [:p |</div>
<div><span style="white-space:pre"></span>data findBinaryIndex: [:d | p <=> d]]] benchFor: 10 seconds. "--> <span style="font-family:Calibri,Helvetica,sans-serif,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols; font-size:16px">'107
per second. 9.37 milliseconds per run. 5.21896 % GC time.'"</span></div>
<div>[probe collect: [:p |</div>
<div><span style="white-space:pre"></span>data findDeltaIndex: [:d | p - d]]] <span style="font-size:12pt">benchFor: 10 seconds. "--> </span><span style="font-size:12pt">'196 per second. 5.1 milliseconds per run. 9.89901 % GC time.'"</span></div>
<div><span style="font-size:12pt"><br>
</span></div>
<div><span style="font-size:12pt"><span>(9.37 milliSeconds / 5.1 milliSeconds) asScaledDecimal reciprocal "--> <span>0.54429028s8"</span></span></span></div>
<p></p>
</blockquote>
<p></p>
<p><br>
</p>
<p>Looking forward to your review! :-)</p>
<p>In particular, I already wondered whether #findDelta: is the best name for this feature. Does anyone know a better one?</p>
<p>We could also add a fourth parameter for specifying a custom interpolation function. However, I could not find any real-world example for this, so this would probably be speculative generality.</p>
<p><br>
</p>
<p>Best,</p>
<p>Christoph</p>
<div><br>
</div>
<div>
<hr style="font-family: Calibri, Helvetica, sans-serif, EmojiFont, "Apple Color Emoji", "Segoe UI Emoji", NotoColorEmoji, "Segoe UI Symbol", "Android Emoji", EmojiSymbols; font-size: 16px; display: inline-block; width: 1021.69px;" tabindex="-1">
<span style="font-family: Calibri, Helvetica, sans-serif, EmojiFont, "Apple Color Emoji", "Segoe UI Emoji", NotoColorEmoji, "Segoe UI Symbol", "Android Emoji", EmojiSymbols; font-size: 16px;"></span>
<div id="x_divRplyFwdMsg" dir="ltr" style="font-family: Calibri, Helvetica, sans-serif, EmojiFont, "Apple Color Emoji", "Segoe UI Emoji", NotoColorEmoji, "Segoe UI Symbol", "Android Emoji", EmojiSymbols; font-size: 16px;">
<br>
</div>
</div>
<p></p>
<div id="Signature">
<div id="divtagdefaultwrapper" dir="ltr" style="font-size:12pt; color:rgb(0,0,0); font-family:Calibri,Helvetica,sans-serif,EmojiFont,"Apple Color Emoji","Segoe UI Emoji",NotoColorEmoji,"Segoe UI Symbol","Android Emoji",EmojiSymbols">
<div name="divtagdefaultwrapper" style="font-family:Calibri,Arial,Helvetica,sans-serif; font-size:; margin:0">
<div>
<div class="_rp_T4" id="Item.MessagePartBody">
<div>
<div><span style="font-size: 10pt;">'From Squeak6.0alpha of 1 October 2020 [latest update: #19893] on 6 October 2020 at 1:53:27 pm'!</span></div>
<div><br>
</div>
<div><span style="font-size: 10pt;">!SequenceableCollection methodsFor: 'enumerating' stamp: 'ct 10/4/2020 15:46'!</span></div>
<div><span style="font-size: 10pt;">findBinary: aBlock do: actionBlock ifNone: exceptionBlock</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">"Search for an element in the receiver using binary search.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">The argument aBlock is a one-element block returning</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">0
</span><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">- if the element is the one searched for;</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;"><0</span><span style="white-space: pre; font-size: 10pt;">
</span><span style="font-size: 10pt;">- if the search should continue in the first half;</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">>0</span><span style="white-space: pre; font-size: 10pt;">
</span><span style="font-size: 10pt;">- if the search should continue in the second half.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">If found, evaluate actionBlock with the found element as argument. If no matching element is found, evaluate exceptionBlock, with the 'bounding' elements (or nil) as
optional arguments.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">If aBlock performs expensive operations, also consider using #findDelta:do:ifNone: instead.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">Examples:</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">#(1 3 5 7 11 15 23)</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findBinary: [ :arg | 11 <=> arg ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">do: [ :found | found ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [ :a :b | ('between: ', {a. b} printString) ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">#(1 3 5 7 11 15 23)</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findBinary: [ :arg | 12 <=> arg ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">do: [ :found | found ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [ :a :b | ('between: ', {a. b} printString) ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">#(1 3 5 7 11 15 23)</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findBinary: [ :arg | 0.5 - arg ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">do: [ :found | found ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [ :a :b | ('between: ', {a. b} printString) ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">#(1 3 5 7 11 15 23)</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findBinary: [ :arg | 25 - arg ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">do: [ :found | found ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [ :a :b | ('between: ',{a. b} printString) ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">"</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">^self</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findBinaryIndex: aBlock</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">do: [ :foundIndex | actionBlock value: (self at: foundIndex) ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [ :prevIndex :nextIndex |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">exceptionBlock</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">cull: (prevIndex > 0 ifTrue: [ self at: prevIndex ])</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">cull: (nextIndex <= self size ifTrue: [ self at: nextIndex ]) ]! !</span></div>
<div><br>
</div>
<div><span style="font-size: 10pt;">!SequenceableCollection methodsFor: 'enumerating' stamp: 'ct 10/4/2020 15:46'!</span></div>
<div><span style="font-size: 10pt;">findBinaryIndex: aBlock</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">"Search for an element in the receiver using binary search.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">The argument aBlock is a one-element block returning</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">0
</span><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">- if the element is the one searched for;</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;"><0</span><span style="white-space: pre; font-size: 10pt;">
</span><span style="font-size: 10pt;">- if the search should continue in the first half;</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">>0</span><span style="white-space: pre; font-size: 10pt;">
</span><span style="font-size: 10pt;">- if the search should continue in the second half.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">If no matching element is found, raise an error.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">If aBlock performs expensive operations, also consider using #findDeltaIndex: instead.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">Example:</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">#(1 3 5 7 11 15 23) findBinaryIndex: [ :arg | 11 <=> arg ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">"</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">^self findBinaryIndex: aBlock do: [ :found | found ] ifNone: [ self errorNotFound: aBlock]! !</span></div>
<div><br>
</div>
<div><span style="font-size: 10pt;">!SequenceableCollection methodsFor: 'enumerating' stamp: 'ct 10/4/2020 15:47'!</span></div>
<div><span style="font-size: 10pt;">findBinaryIndex: aBlock do: actionBlock ifNone: exceptionBlock</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">"Search for an element in the receiver using binary search.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">The argument aBlock is a one-element block returning</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">0
</span><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">- if the element is the one searched for;</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;"><0</span><span style="white-space: pre; font-size: 10pt;">
</span><span style="font-size: 10pt;">- if the search should continue in the first half;</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">>0</span><span style="white-space: pre; font-size: 10pt;">
</span><span style="font-size: 10pt;">- if the search should continue in the second half.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">If found, evaluate actionBlock with the index as argument. If no matching element is found, evaluate exceptionBlock, with the indexes of the 'bounding' elements as optional
arguments.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">Warning: Might give invalid indexes, see examples below.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">If aBlock performs expensive operations, also consider using #findDeltaIndex:do:ifNone: instead.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">Examples:</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">#(1 3 5 7 11 15 23)</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findBinaryIndex: [ :arg | 11 <=> arg ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">do: [ :found | found ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [ :a :b | ('between: ', {a. b} printString)]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">#(1 3 5 7 11 15 23)</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findBinaryIndex: [ :arg | 1 <=> arg ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">do: [ :found | found ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [ :a :b | ('between: ', {a. b} printString) ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">#(1 3 5 7 11 15 23) d</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findBinaryIndex: [ :arg | 0.5 - arg ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">do: [ :found | found ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [ :a :b | ('between: ', {a. b} printString) ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">#(1 3 5 7 11 15 23)</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findBinaryIndex: [ :arg | 25 - arg ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">do: [ :found | found ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [ :a :b | ('between: ',{a. b} printString) ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">"</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">| index low high test |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">low := 1.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">high := self size.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">[ high < low ] whileFalse: [</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">index := high + low // 2.</span><span style="white-space: pre; font-size: 10pt;">
</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">(test := aBlock value: (self at: index)) < 0</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifTrue: [ high := index - 1 ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifFalse: [</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">0 < test</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifTrue: [ low := index + 1 ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifFalse: [ "test = 0"</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">^actionBlock value: index ] ] ].</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">^exceptionBlock cull: high cull: low! !</span></div>
<div><br>
</div>
<div><span style="font-size: 10pt;">!SequenceableCollection methodsFor: 'enumerating' stamp: 'ct 10/4/2020 15:47'!</span></div>
<div><span style="font-size: 10pt;">findBinaryIndex: aBlock ifNone: exceptionBlock</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">"Search for an element in the receiver using binary search.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">The argument aBlock is a one-element block returning</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">0
</span><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">- if the element is the one searched for;</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;"><0</span><span style="white-space: pre; font-size: 10pt;">
</span><span style="font-size: 10pt;">- if the search should continue in the first half;</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">>0</span><span style="white-space: pre; font-size: 10pt;">
</span><span style="font-size: 10pt;">- if the search should continue in the second half.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">If no matching element is found, evaluate exceptionBlock, with the indexes of the 'bounding' elements as optional arguments.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">Warning: Might give invalid indexes.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">If aBlock performs expensive operations, also consider using #findDeltaIndex:ifNone: instead."</span></div>
<div><br>
</div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">^self findBinaryIndex: aBlock do: [ :found | found ] ifNone: exceptionBlock! !</span></div>
<div><br>
</div>
<div><span style="font-size: 10pt;">!SequenceableCollection methodsFor: 'enumerating' stamp: 'ct 10/4/2020 15:47'!</span></div>
<div><span style="font-size: 10pt;">findBinary: aBlock</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">"Search for an element in the receiver using binary search.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">The argument aBlock is a one-element block returning</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">0
</span><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">- if the element is the one searched for;</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;"><0</span><span style="white-space: pre; font-size: 10pt;">
</span><span style="font-size: 10pt;">- if the search should continue in the first half;</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">>0</span><span style="white-space: pre; font-size: 10pt;">
</span><span style="font-size: 10pt;">- if the search should continue in the second half.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">If no matching element is found, raise an error.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">If aBlock performs expensive operations, also consider using #findDelta: instead.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">Example:</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">#(1 3 5 7 11 15 23) findBinary: [ :arg | 11 <=> arg ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">"</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">^self findBinary: aBlock do: [ :found | found ] ifNone: [ self errorNotFound: aBlock ]! !</span></div>
<div><br>
</div>
<div><span style="font-size: 10pt;">!SequenceableCollection methodsFor: 'enumerating' stamp: 'ct 10/4/2020 15:47'!</span></div>
<div><span style="font-size: 10pt;">findBinary: aBlock ifNone: exceptionBlock</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">"Search for an element in the receiver using binary search.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">The argument aBlock is a one-element block returning</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">0
</span><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">- if the element is the one searched for;</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;"><0</span><span style="white-space: pre; font-size: 10pt;">
</span><span style="font-size: 10pt;">- if the search should continue in the first half;</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">>0</span><span style="white-space: pre; font-size: 10pt;">
</span><span style="font-size: 10pt;">- if the search should continue in the second half.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">If no matching element is found, evaluate exceptionBlock, with the 'bounding' elements (or nil) as optional arguments.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">If aBlock performs expensive operations, also consider using #findDelta:ifNone: instead."</span></div>
<div><br>
</div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">^self findBinary: aBlock do: [ :found | found ] ifNone: exceptionBlock! !</span></div>
<div><br>
</div>
<div><span style="font-size: 10pt;">!SequenceableCollection methodsFor: 'enumerating' stamp: 'ct 10/4/2020 15:45'!</span></div>
<div><span style="font-size: 10pt;">findDelta: aBlock</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">"Search for an element in the receiver using interpolation search with a linear interpolation function.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">The argument aBlock is a one-element block returning</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">0
</span><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">- if the element is the one searched for;</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;"><0</span><span style="white-space: pre; font-size: 10pt;">
</span><span style="font-size: 10pt;">- the distance to the searched value, if the search should continue in the first half;</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">>0</span><span style="white-space: pre; font-size: 10pt;">
</span><span style="font-size: 10pt;">- the distance to the searched, if the search should continue in the second half.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">Practical performance of interpolation search depends on whether the reduced number of probes is outweighed by the more complicated calculations needed for each probe.
For more information, read the Wikipedia article (which the previous sentence was cited from).</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">Example:</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">#(1 3 5 7 11 15 23) findDelta: [ :arg | 11 - arg ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">"</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">^ self findDelta: aBlock do: [ :found | found ] ifNone: [ self errorNotFound: aBlock ]! !</span></div>
<div><br>
</div>
<div><span style="font-size: 10pt;">!SequenceableCollection methodsFor: 'enumerating' stamp: 'ct 10/4/2020 15:45'!</span></div>
<div><span style="font-size: 10pt;">findDelta: aBlock do: actionBlock ifNone: exceptionBlock</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">"Search for an element in the receiver using interpolation search with a linear interpolation function.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">The argument aBlock is a one-element block returning</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">0
</span><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">- if the element is the one searched for;</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;"><0</span><span style="white-space: pre; font-size: 10pt;">
</span><span style="font-size: 10pt;">- the distance to the searched value, if the search should continue in the first half;</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">>0</span><span style="white-space: pre; font-size: 10pt;">
</span><span style="font-size: 10pt;">- the distance to the searched, if the search should continue in the second half.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">If found, evaluate actionBlock with the found element as argument. If no matching element is found, evaluate exceptionBlock, with the 'bounding' elements (or nil) as
optional arguments.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">Practical performance of interpolation search depends on whether the reduced number of probes is outweighed by the more complicated calculations needed for each probe.
For more information, read the Wikipedia article (which the previous sentence was cited from).</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">Examples:</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">#(1 3 5 7 11 15 23)</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findDelta: [ :arg | 11 - arg ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">do: [ :found | found ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [ :a :b | ('between: ', {a. b} printString) ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">#(1 3 5 7 11 15 23)</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findDelta: [ :arg | 12 - arg ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">do: [ :found | found ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [ :a :b | ('between: ', {a. b} printString) ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">#(1 3 5 7 11 15 23)</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findDelta: [ :arg | 0.5 - arg ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">do: [ :found | found ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [ :a :b | ('between: ', {a. b} printString) ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">#(1 3 5 7 11 15 23)</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findDelta: [ :arg | 25 - arg ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">do: [ :found | found ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [ :a :b | ('between: ',{a. b} printString) ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">"</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">^ self</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findDeltaIndex: aBlock</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">do: [ :foundIndex | actionBlock value: (self at: foundIndex) ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [ :prevIndex :nextIndex |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">exceptionBlock</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">cull: (prevIndex > 0 ifTrue: [ self at: prevIndex ])</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">cull: (nextIndex <= self size ifTrue: [ self at: nextIndex ]) ]! !</span></div>
<div><br>
</div>
<div><span style="font-size: 10pt;">!SequenceableCollection methodsFor: 'enumerating' stamp: 'ct 10/4/2020 15:45'!</span></div>
<div><span style="font-size: 10pt;">findDelta: aBlock ifNone: exceptionBlock</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">"Search for an element in the receiver using interpolation search with a linear interpolation function.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">The argument aBlock is a one-element block returning</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">0
</span><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">- if the element is the one searched for;</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;"><0</span><span style="white-space: pre; font-size: 10pt;">
</span><span style="font-size: 10pt;">- the distance to the searched value, if the search should continue in the first half;</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">>0</span><span style="white-space: pre; font-size: 10pt;">
</span><span style="font-size: 10pt;">- the distance to the searched, if the search should continue in the second half.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">If no matching element is found, evaluate exceptionBlock, with the 'bounding' elements (or nil) as optional arguments.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">Practical performance of interpolation search depends on whether the reduced number of probes is outweighed by the more complicated calculations needed for each probe.
For more information, read the Wikipedia article (which the previous sentence was cited from)."</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">^ self findDelta: aBlock do: [ :found | found ] ifNone: exceptionBlock! !</span></div>
<div><br>
</div>
<div><span style="font-size: 10pt;">!SequenceableCollection methodsFor: 'enumerating' stamp: 'ct 10/4/2020 15:45'!</span></div>
<div><span style="font-size: 10pt;">findDeltaIndex: aBlock</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">"Search for an element in the receiver using interpolation search with a linear interpolation function.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">The argument aBlock is a one-element block returning</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">0
</span><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">- if the element is the one searched for;</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;"><0</span><span style="white-space: pre; font-size: 10pt;">
</span><span style="font-size: 10pt;">- the distance to the searched value, if the search should continue in the first half;</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">>0</span><span style="white-space: pre; font-size: 10pt;">
</span><span style="font-size: 10pt;">- the distance to the searched, if the search should continue in the second half.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">If no matching element is found, raise an error.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">Warning: Might give invalid indexes.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">Practical performance of interpolation search depends on whether the reduced number of probes is outweighed by the more complicated calculations needed for each probe.
For more information, read the Wikipedia article (which the previous sentence was cited from).</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">Example:</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">#(1 3 5 7 11 15 23) findDeltaIndex: [ :arg | 11 - arg ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">"</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">^ self</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findDeltaIndex: aBlock</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">do: [ :found | found ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [ self errorNotFound: aBlock ]! !</span></div>
<div><br>
</div>
<div><span style="font-size: 10pt;">!SequenceableCollection methodsFor: 'enumerating' stamp: 'ct 10/6/2020 13:52'!</span></div>
<div><span style="font-size: 10pt;">findDeltaIndex: aBlock do: actionBlock ifNone: exceptionBlock</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">"Search for an element in the receiver using interpolation search with a linear interpolation function.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">The argument aBlock is a one-element block returning</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">0
</span><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">- if the element is the one searched for;</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;"><0</span><span style="white-space: pre; font-size: 10pt;">
</span><span style="font-size: 10pt;">- the distance to the searched value, if the search should continue in the first half;</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">>0</span><span style="white-space: pre; font-size: 10pt;">
</span><span style="font-size: 10pt;">- the distance to the searched, if the search should continue in the second half.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">If found, evaluate actionBlock with the index as argument. If no matching element is found, evaluate exceptionBlock, with the indexes of the 'bounding' elements as optional
arguments.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">Warning: Might give invalid indexes, see examples below.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">Practical performance of interpolation search depends on whether the reduced number of probes is outweighed by the more complicated calculations needed for each probe.
For more information, read the Wikipedia article (which the previous sentence was cited from).</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">Examples:</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">#(1 3 5 7 11 15 23)</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findDeltaIndex: [ :arg | 11 - arg ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">do: [ :found | found ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [ :a :b | ('between: ', {a. b} printString)]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">#(1 3 5 7 11 15 23)</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findDeltaIndex: [ :arg | 12 - arg ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">do: [ :found | found ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [ :a :b | ('between: ', {a. b} printString) ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">#(1 3 5 7 11 15 23) d</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findDeltaIndex: [ :arg | 0.5 - arg ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">do: [ :found | found ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [ :a :b | ('between: ', {a. b} printString) ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">#(1 3 5 7 11 15 23)</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findDeltaIndex: [ :arg | 25 - arg ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">do: [ :found | found ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [ :a :b | ('between: ',{a. b} printString) ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">"</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">| index low high delta |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">low := 1.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">high := self size.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">index := low + high // 2.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">[ index between: low and: high ] whileTrue: [ | range |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">index := ((delta := aBlock value: (self at: index)) < 0</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifTrue: [</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">high := index - 1.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">(range := (self at: index) - (self at: low)) = 0</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifTrue: [ high ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifFalse: [ high + (high - low * delta // range) ] ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifFalse: [ 0 < delta ifTrue: [</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">low := index + 1.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">(range := (self at: high) - (self at: index)) = 0</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifTrue: [ low ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifFalse: [ low + (high - low * delta // range) ] ]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifFalse: [ "delta = 0"</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">^ actionBlock value: index ] ]) min: high max: low.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">].</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">^ exceptionBlock cull: high cull: low! !</span></div>
<div><br>
</div>
<div><span style="font-size: 10pt;">!SequenceableCollection methodsFor: 'enumerating' stamp: 'ct 10/4/2020 15:45'!</span></div>
<div><span style="font-size: 10pt;">findDeltaIndex: aBlock ifNone: exceptionBlock</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">"Search for an element in the receiver using interpolation search with a linear interpolation function.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">The argument aBlock is a one-element block returning</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">0
</span><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">- if the element is the one searched for;</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;"><0</span><span style="white-space: pre; font-size: 10pt;">
</span><span style="font-size: 10pt;">- the distance to the searched value, if the search should continue in the first half;</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">>0</span><span style="white-space: pre; font-size: 10pt;">
</span><span style="font-size: 10pt;">- the distance to the searched, if the search should continue in the second half.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">If no matching element is found, evaluate exceptionBlock, with the indexes of the 'bounding' elements as optional arguments.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">Warning: Might give invalid indexes.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">Practical performance of interpolation search depends on whether the reduced number of probes is outweighed by the more complicated calculations needed for each probe.
For more information, read the Wikipedia article (which the previous sentence was cited from)."</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">^ self findDeltaIndex: aBlock do: [ :found | found ] ifNone: exceptionBlock! !</span></div>
<div><br>
</div>
<div><br>
</div>
<div><span style="font-size: 10pt;">!SequenceableCollectionTest methodsFor: 'tests - enumerating' stamp: 'ct 10/2/2020 22:47'!</span></div>
<div><span style="font-size: 10pt;">testFindBinary</span></div>
<div><br>
</div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">| values |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">values := (1 to: 100) select: #isPrime.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">1 to: 100 do: [:every |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">every isPrime</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifTrue: [</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">self assert: every equals: (</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">values findBinary: [:each | every <=> each])]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifFalse: [</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">self</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">should: [values findBinary: [:each | every <=> each]]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">raise: NotFound]].! !</span></div>
<div><br>
</div>
<div><span style="font-size: 10pt;">!SequenceableCollectionTest methodsFor: 'tests - enumerating' stamp: 'ct 10/2/2020 22:48'!</span></div>
<div><span style="font-size: 10pt;">testFindBinaryDoIfNone</span></div>
<div><br>
</div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">| values |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">values := (1 to: 100) select: #isPrime.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">1 to: 100 do: [:every |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">every isPrime</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifTrue: [</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">self assert: every negated equals: (values</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findBinary: [:each | every <=> each]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">do: [:each | each negated]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [self fail])]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifFalse: [</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">self assert: self equals: (values</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findBinary: [:each | every <=> each]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">do: [self fail]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [self])]].! !</span></div>
<div><br>
</div>
<div><span style="font-size: 10pt;">!SequenceableCollectionTest methodsFor: 'tests - enumerating' stamp: 'ct 10/2/2020 22:49'!</span></div>
<div><span style="font-size: 10pt;">testFindBinaryIfNone</span></div>
<div><br>
</div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">| values |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">values := (1 to: 100) select: #isPrime.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">1 to: 100 do: [:every |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">every isPrime</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifTrue: [</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">self assert: every equals: (values</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findBinary: [:each | every <=> each]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [self fail])]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifFalse: [</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">self assert: self equals: (values</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findBinary: [:each | every <=> each]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [self])]].! !</span></div>
<div><br>
</div>
<div><span style="font-size: 10pt;">!SequenceableCollectionTest methodsFor: 'tests - enumerating' stamp: 'ct 10/2/2020 22:51'!</span></div>
<div><span style="font-size: 10pt;">testFindBinaryIndex</span></div>
<div><br>
</div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">| values |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">values := (1 to: 100) select: #isPrime.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">1 to: 100 do: [:every |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">every isPrime</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifTrue: [</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">self assert: (values indexOf: every) equals: (</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">values findBinaryIndex: [:each | every <=> each])]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifFalse: [</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">self</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">should: [values findBinaryIndex: [:each | every <=> each]]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">raise: NotFound]].! !</span></div>
<div><br>
</div>
<div><span style="font-size: 10pt;">!SequenceableCollectionTest methodsFor: 'tests - enumerating' stamp: 'ct 10/2/2020 22:52'!</span></div>
<div><span style="font-size: 10pt;">testFindBinaryIndexDoIfNone</span></div>
<div><br>
</div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">| values |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">values := (1 to: 100) select: #isPrime.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">1 to: 100 do: [:every |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">every isPrime</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifTrue: [</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">self assert: (values indexOf: every) negated equals: ((values</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findBinaryIndex: [:each | every <=> each]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">do: [:result | result negated]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [self fail]))]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifFalse: [</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">self assert: self equals: (values</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findBinaryIndex: [:each | every <=> each]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">do: [:result | self fail]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [self])]].! !</span></div>
<div><br>
</div>
<div><span style="font-size: 10pt;">!SequenceableCollectionTest methodsFor: 'tests - enumerating' stamp: 'ct 10/2/2020 22:52'!</span></div>
<div><span style="font-size: 10pt;">testFindBinaryIndexIfNone</span></div>
<div><br>
</div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">| values |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">values := (1 to: 100) select: #isPrime.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">1 to: 100 do: [:every |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">every isPrime</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifTrue: [</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">self assert: (values indexOf: every) equals: (values</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findBinaryIndex: [:each | every <=> each]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [self fail])]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifFalse: [</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">self assert: self equals: (values</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findBinaryIndex: [:each | every <=> each]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [self])]].! !</span></div>
<div><br>
</div>
<div><span style="font-size: 10pt;">!SequenceableCollectionTest methodsFor: 'tests - enumerating' stamp: 'ct 10/2/2020 23:03'!</span></div>
<div><span style="font-size: 10pt;">testFindDelta</span></div>
<div><br>
</div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">| values |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">values := (1 to: 100) select: #isPrime.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">1 to: 100 do: [:every |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">every isPrime</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifTrue: [</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">self assert: every equals: (</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">values findDelta: [:each | every - each])]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifFalse: [</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">self</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">should: [values findDelta: [:each | every - each]]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">raise: NotFound]].! !</span></div>
<div><br>
</div>
<div><span style="font-size: 10pt;">!SequenceableCollectionTest methodsFor: 'tests - enumerating' stamp: 'ct 10/3/2020 00:12'!</span></div>
<div><span style="font-size: 10pt;">testFindDeltaDoIfNone</span></div>
<div><br>
</div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">| values |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">values := (1 to: 100) select: #isPrime.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">1 to: 100 do: [:every |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">every isPrime</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifTrue: [</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">self assert: every negated equals: (values</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findDelta: [:each | every - each]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">do: [:each | each negated]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [self fail])]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifFalse: [</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">self assert: self equals: (values</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findDelta: [:each | every - each]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">do: [self fail]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [self])]].! !</span></div>
<div><br>
</div>
<div><span style="font-size: 10pt;">!SequenceableCollectionTest methodsFor: 'tests - enumerating' stamp: 'ct 10/3/2020 00:13'!</span></div>
<div><span style="font-size: 10pt;">testFindDeltaIfNone</span></div>
<div><br>
</div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">| values |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">values := (1 to: 100) select: #isPrime.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">1 to: 100 do: [:every |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">every isPrime</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifTrue: [</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">self assert: every equals: (values</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findDelta: [:each | every - each]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [self fail])]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifFalse: [</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">self assert: self equals: (values</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findDelta: [:each | every - each]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [self])]].! !</span></div>
<div><br>
</div>
<div><span style="font-size: 10pt;">!SequenceableCollectionTest methodsFor: 'tests - enumerating' stamp: 'ct 10/3/2020 00:13'!</span></div>
<div><span style="font-size: 10pt;">testFindDeltaIndex</span></div>
<div><br>
</div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">| values |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">values := (1 to: 100) select: #isPrime.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">1 to: 100 do: [:every |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">every isPrime</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifTrue: [</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">self assert: (values indexOf: every) equals: (</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">values findDeltaIndex: [:each | every - each])]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifFalse: [</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">self</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">should: [values findDeltaIndex: [:each | every - each]]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">raise: NotFound]].! !</span></div>
<div><br>
</div>
<div><span style="font-size: 10pt;">!SequenceableCollectionTest methodsFor: 'tests - enumerating' stamp: 'ct 10/3/2020 00:13'!</span></div>
<div><span style="font-size: 10pt;">testFindDeltaIndexDoIfNone</span></div>
<div><br>
</div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">| values |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">values := (1 to: 100) select: #isPrime.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">1 to: 100 do: [:every |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">every isPrime</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifTrue: [</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">self assert: (values indexOf: every) negated equals: ((values</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findDeltaIndex: [:each | every - each]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">do: [:result | result negated]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [self fail]))]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifFalse: [</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">self assert: self equals: (values</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findDeltaIndex: [:each | every - each]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">do: [:result | self fail]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [self])]].! !</span></div>
<div><br>
</div>
<div><span style="font-size: 10pt;">!SequenceableCollectionTest methodsFor: 'tests - enumerating' stamp: 'ct 10/3/2020 00:14'!</span></div>
<div><span style="font-size: 10pt;">testFindDeltaIndexIfNone</span></div>
<div><br>
</div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">| values |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">values := (1 to: 100) select: #isPrime.</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">1 to: 100 do: [:every |</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">every isPrime</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifTrue: [</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">self assert: (values indexOf: every) equals: (values</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findDeltaIndex: [:each | every - each]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [self fail])]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifFalse: [</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">self assert: self equals: (values</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">findDeltaIndex: [:each | every - each]</span></div>
<div><span style="white-space: pre; font-size: 10pt;"></span><span style="font-size: 10pt;">ifNone: [self])]].! !</span></div>
</div>
<div class="_rp_U4 ms-font-weight-regular ms-font-color-neutralDark rpHighlightAllClass rpHighlightBodyClass" id="Item.MessageUniqueBody" style="font-family:wf_segoe-ui_normal,"Segoe UI","Segoe WP",Tahoma,Arial,sans-serif,serif,EmojiFont">
<div dir="ltr">
<div id="divtagdefaultwrapper"><font face="Calibri,Helvetica,sans-serif,EmojiFont,Apple Color Emoji,Segoe UI Emoji,NotoColorEmoji,Segoe UI Symbol,Android Emoji,EmojiSymbols">
<div id="Signature">
<div style="margin:0px"><font style="font-family:Calibri,Arial,Helvetica,sans-serif,serif,EmojiFont"></font></div>
</div>
</font></div>
</div>
</div>
</div>
</div>
<div><font size="2" color="#808080"></font></div>
</div>
</div>
</div>
</div>
</body>
</html>