'From Squeak6.0alpha of 1 October 2020 [latest update: #19893] on 6 October 2020 at 1:53:27 pm'!

!SequenceableCollection methodsFor: 'enumerating' stamp: 'ct 10/4/2020 15:46'!
findBinary: aBlock do: actionBlock ifNone: exceptionBlock
	"Search for an element in the receiver using binary search.
	The argument aBlock is a one-element block returning
		0 	- if the element is the one searched for;
		<0	- if the search should continue in the first half;
		>0	- if the search should continue in the second half.
	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.
	If aBlock performs expensive operations, also consider using #findDelta:do:ifNone: instead.
	
	Examples:
		#(1 3 5 7 11 15 23)
			findBinary: [ :arg | 11 <=> arg ]
			do: [ :found | found ]
			ifNone: [ :a :b | ('between: ', {a. b} printString) ]
		#(1 3 5 7 11 15 23)
			findBinary: [ :arg | 12 <=> arg ]
			do: [ :found | found ]
			ifNone: [ :a :b | ('between: ', {a. b} printString) ]
		#(1 3 5 7 11 15 23)
			findBinary: [ :arg | 0.5 - arg ]
			do: [ :found | found ]
			ifNone: [ :a :b | ('between: ', {a. b} printString) ]
		#(1 3 5 7 11 15 23)
			findBinary: [ :arg | 25 - arg ]
			do: [ :found | found ]
			ifNone: [ :a :b | ('between: ',{a. b} printString) ]
	"
	^self
		findBinaryIndex: aBlock
		do: [ :foundIndex | actionBlock value: (self at: foundIndex) ]
		ifNone: [ :prevIndex :nextIndex |
			exceptionBlock
				cull: (prevIndex > 0 ifTrue: [ self at: prevIndex ])
				cull: (nextIndex <= self size ifTrue: [ self at: nextIndex ]) ]! !

!SequenceableCollection methodsFor: 'enumerating' stamp: 'ct 10/4/2020 15:46'!
findBinaryIndex: aBlock
	"Search for an element in the receiver using binary search.
	The argument aBlock is a one-element block returning
		0 	- if the element is the one searched for;
		<0	- if the search should continue in the first half;
		>0	- if the search should continue in the second half.
	If no matching element is found, raise an error.
	If aBlock performs expensive operations, also consider using #findDeltaIndex: instead.
	
	Example:
		#(1 3 5 7 11 15 23) findBinaryIndex: [ :arg | 11 <=> arg ]
	"
	^self findBinaryIndex: aBlock do: [ :found | found ] ifNone: [ self errorNotFound: aBlock]! !

!SequenceableCollection methodsFor: 'enumerating' stamp: 'ct 10/4/2020 15:47'!
findBinaryIndex: aBlock do: actionBlock ifNone: exceptionBlock
	"Search for an element in the receiver using binary search.
	The argument aBlock is a one-element block returning
		0 	- if the element is the one searched for;
		<0	- if the search should continue in the first half;
		>0	- if the search should continue in the second half.
	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.
	Warning: Might give invalid indexes, see examples below.
	If aBlock performs expensive operations, also consider using #findDeltaIndex:do:ifNone: instead.
	
	Examples:
		#(1 3 5 7 11 15 23)
			findBinaryIndex: [ :arg | 11 <=> arg ]
			do: [ :found | found ]
			ifNone: [ :a :b | ('between: ', {a. b} printString)]
		#(1 3 5 7 11 15 23)
			findBinaryIndex: [ :arg | 1 <=> arg ]
			do: [ :found | found ]
			ifNone: [ :a :b | ('between: ', {a. b} printString) ]
		#(1 3 5 7 11 15 23) d
			findBinaryIndex: [ :arg | 0.5 - arg ]
			do: [ :found | found ]
			ifNone: [ :a :b | ('between: ', {a. b} printString) ]
		#(1 3 5 7 11 15 23)
			findBinaryIndex: [ :arg | 25 - arg ]
			do: [ :found | found ]
			ifNone: [ :a :b | ('between: ',{a. b} printString) ]
	"
	| index low high test |
	low := 1.
	high := self size.
	[ high < low ] whileFalse: [
		index := high + low // 2.	
		(test := aBlock value: (self at: index)) < 0
			ifTrue: [ high := index - 1 ]
			ifFalse: [
				0 < test
					ifTrue: [ low := index + 1 ]
					ifFalse: [ "test = 0"
						^actionBlock value: index ] ] ].
	^exceptionBlock cull: high cull: low! !

!SequenceableCollection methodsFor: 'enumerating' stamp: 'ct 10/4/2020 15:47'!
findBinaryIndex: aBlock ifNone: exceptionBlock
	"Search for an element in the receiver using binary search.
	The argument aBlock is a one-element block returning
		0 	- if the element is the one searched for;
		<0	- if the search should continue in the first half;
		>0	- if the search should continue in the second half.
	If no matching element is found, evaluate exceptionBlock, with the indexes of the 'bounding' elements as optional arguments.
	Warning: Might give invalid indexes.
	If aBlock performs expensive operations, also consider using #findDeltaIndex:ifNone: instead."

	^self findBinaryIndex: aBlock do: [ :found | found ] ifNone: exceptionBlock! !

!SequenceableCollection methodsFor: 'enumerating' stamp: 'ct 10/4/2020 15:47'!
findBinary: aBlock
	"Search for an element in the receiver using binary search.
	The argument aBlock is a one-element block returning
		0 	- if the element is the one searched for;
		<0	- if the search should continue in the first half;
		>0	- if the search should continue in the second half.
	If no matching element is found, raise an error.
	If aBlock performs expensive operations, also consider using #findDelta: instead.
	
	Example:
		#(1 3 5 7 11 15 23) findBinary: [ :arg | 11 <=> arg ]
	"
	^self findBinary: aBlock do: [ :found | found ] ifNone: [ self errorNotFound: aBlock ]! !

!SequenceableCollection methodsFor: 'enumerating' stamp: 'ct 10/4/2020 15:47'!
findBinary: aBlock ifNone: exceptionBlock
	"Search for an element in the receiver using binary search.
	The argument aBlock is a one-element block returning
		0 	- if the element is the one searched for;
		<0	- if the search should continue in the first half;
		>0	- if the search should continue in the second half.
	If no matching element is found, evaluate exceptionBlock, with the 'bounding' elements (or nil) as optional arguments.
	If aBlock performs expensive operations, also consider using #findDelta:ifNone: instead."

	^self findBinary: aBlock do: [ :found | found ] ifNone: exceptionBlock! !

!SequenceableCollection methodsFor: 'enumerating' stamp: 'ct 10/4/2020 15:45'!
findDelta: aBlock
	"Search for an element in the receiver using interpolation search with a linear interpolation function.
	The argument aBlock is a one-element block returning
		0 	- if the element is the one searched for;
		<0	- the distance to the searched value, if the search should continue in the first half;
		>0	- the distance to the searched, if the search should continue in the second half.
	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).
	
	Example:
		#(1 3 5 7 11 15 23) findDelta: [ :arg | 11 - arg ]
	"
	^ self findDelta: aBlock do: [ :found | found ] ifNone: [ self errorNotFound: aBlock ]! !

!SequenceableCollection methodsFor: 'enumerating' stamp: 'ct 10/4/2020 15:45'!
findDelta: aBlock do: actionBlock ifNone: exceptionBlock
	"Search for an element in the receiver using interpolation search with a linear interpolation function.
	The argument aBlock is a one-element block returning
		0 	- if the element is the one searched for;
		<0	- the distance to the searched value, if the search should continue in the first half;
		>0	- the distance to the searched, if the search should continue in the second half.
	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.
	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).
	
	Examples:
		#(1 3 5 7 11 15 23)
			findDelta: [ :arg | 11 - arg ]
			do: [ :found | found ]
			ifNone: [ :a :b | ('between: ', {a. b} printString) ]
		#(1 3 5 7 11 15 23)
			findDelta: [ :arg | 12 - arg ]
			do: [ :found | found ]
			ifNone: [ :a :b | ('between: ', {a. b} printString) ]
		#(1 3 5 7 11 15 23)
			findDelta: [ :arg | 0.5 - arg ]
			do: [ :found | found ]
			ifNone: [ :a :b | ('between: ', {a. b} printString) ]
		#(1 3 5 7 11 15 23)
			findDelta: [ :arg | 25 - arg ]
			do: [ :found | found ]
			ifNone: [ :a :b | ('between: ',{a. b} printString) ]
	"
	^ self
		findDeltaIndex: aBlock
		do: [ :foundIndex | actionBlock value: (self at: foundIndex) ]
		ifNone: [ :prevIndex :nextIndex |
			exceptionBlock
				cull: (prevIndex > 0 ifTrue: [ self at: prevIndex ])
				cull: (nextIndex <= self size ifTrue: [ self at: nextIndex ]) ]! !

!SequenceableCollection methodsFor: 'enumerating' stamp: 'ct 10/4/2020 15:45'!
findDelta: aBlock ifNone: exceptionBlock
	"Search for an element in the receiver using interpolation search with a linear interpolation function.
	The argument aBlock is a one-element block returning
		0 	- if the element is the one searched for;
		<0	- the distance to the searched value, if the search should continue in the first half;
		>0	- the distance to the searched, if the search should continue in the second half.
	If no matching element is found, evaluate exceptionBlock, with the 'bounding' elements (or nil) as optional arguments.
	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)."
	^ self findDelta: aBlock do: [ :found | found ] ifNone: exceptionBlock! !

!SequenceableCollection methodsFor: 'enumerating' stamp: 'ct 10/4/2020 15:45'!
findDeltaIndex: aBlock
	"Search for an element in the receiver using interpolation search with a linear interpolation function.
	The argument aBlock is a one-element block returning
		0 	- if the element is the one searched for;
		<0	- the distance to the searched value, if the search should continue in the first half;
		>0	- the distance to the searched, if the search should continue in the second half.
	If no matching element is found, raise an error.
	Warning: Might give invalid indexes.
	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).
	
	Example:
		#(1 3 5 7 11 15 23) findDeltaIndex: [ :arg | 11 - arg ]
	"
	^ self
		findDeltaIndex: aBlock
		do: [ :found | found ]
		ifNone: [ self errorNotFound: aBlock ]! !

!SequenceableCollection methodsFor: 'enumerating' stamp: 'ct 10/6/2020 13:52'!
findDeltaIndex: aBlock do: actionBlock ifNone: exceptionBlock
	"Search for an element in the receiver using interpolation search with a linear interpolation function.
	The argument aBlock is a one-element block returning
		0 	- if the element is the one searched for;
		<0	- the distance to the searched value, if the search should continue in the first half;
		>0	- the distance to the searched, if the search should continue in the second half.
	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.
	Warning: Might give invalid indexes, see examples below.
	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).
	
	Examples:
		#(1 3 5 7 11 15 23)
			findDeltaIndex: [ :arg | 11 - arg ]
			do: [ :found | found ]
			ifNone: [ :a :b | ('between: ', {a. b} printString)]
		#(1 3 5 7 11 15 23)
			findDeltaIndex: [ :arg | 12 - arg ]
			do: [ :found | found ]
			ifNone: [ :a :b | ('between: ', {a. b} printString) ]
		#(1 3 5 7 11 15 23) d
			findDeltaIndex: [ :arg | 0.5 - arg ]
			do: [ :found | found ]
			ifNone: [ :a :b | ('between: ', {a. b} printString) ]
		#(1 3 5 7 11 15 23)
			findDeltaIndex: [ :arg | 25 - arg ]
			do: [ :found | found ]
			ifNone: [ :a :b | ('between: ',{a. b} printString) ]
	"
	| index low high delta |
	low := 1.
	high := self size.
	index := low + high // 2.
	[ index between: low and: high ] whileTrue: [ | range |
		index := ((delta := aBlock value: (self at: index)) < 0
			ifTrue: [
				high := index - 1.
				(range := (self at: index) - (self at: low)) = 0
					ifTrue: [ high ]
					ifFalse: [ high + (high - low * delta // range) ] ]
			ifFalse: [ 0 < delta ifTrue: [
				low := index + 1.
				(range := (self at: high) - (self at: index)) = 0
					ifTrue: [ low ]
					ifFalse: [ low + (high - low * delta // range) ] ]
			ifFalse: [ "delta = 0"
				^ actionBlock value: index ] ]) min: high max: low.
		].
	^ exceptionBlock cull: high cull: low! !

!SequenceableCollection methodsFor: 'enumerating' stamp: 'ct 10/4/2020 15:45'!
findDeltaIndex: aBlock ifNone: exceptionBlock
	"Search for an element in the receiver using interpolation search with a linear interpolation function.
	The argument aBlock is a one-element block returning
		0 	- if the element is the one searched for;
		<0	- the distance to the searched value, if the search should continue in the first half;
		>0	- the distance to the searched, if the search should continue in the second half.
	If no matching element is found, evaluate exceptionBlock, with the indexes of the 'bounding' elements as optional arguments.
	Warning: Might give invalid indexes.
	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)."
	^ self findDeltaIndex: aBlock do: [ :found | found ] ifNone: exceptionBlock! !


!SequenceableCollectionTest methodsFor: 'tests - enumerating' stamp: 'ct 10/2/2020 22:47'!
testFindBinary

	| values |
	values := (1 to: 100) select: #isPrime.
	
	1 to: 100 do: [:every |
		every isPrime
			ifTrue: [
				self assert: every equals: (
					values findBinary: [:each | every <=> each])]
			ifFalse: [
				self
					should: [values findBinary: [:each | every <=> each]]
					raise: NotFound]].! !

!SequenceableCollectionTest methodsFor: 'tests - enumerating' stamp: 'ct 10/2/2020 22:48'!
testFindBinaryDoIfNone

	| values |
	values := (1 to: 100) select: #isPrime.
	
	1 to: 100 do: [:every |
		every isPrime
			ifTrue: [
				self assert: every negated equals: (values
					findBinary: [:each | every <=> each]
					do: [:each | each negated]
					ifNone: [self fail])]
			ifFalse: [
				self assert: self equals: (values
						findBinary: [:each | every <=> each]
						do: [self fail]
						ifNone: [self])]].! !

!SequenceableCollectionTest methodsFor: 'tests - enumerating' stamp: 'ct 10/2/2020 22:49'!
testFindBinaryIfNone

	| values |
	values := (1 to: 100) select: #isPrime.
	
	1 to: 100 do: [:every |
		every isPrime
			ifTrue: [
				self assert: every equals: (values
					findBinary: [:each | every <=> each]
					ifNone: [self fail])]
			ifFalse: [
				self assert: self equals: (values
					findBinary: [:each | every <=> each]
					ifNone: [self])]].! !

!SequenceableCollectionTest methodsFor: 'tests - enumerating' stamp: 'ct 10/2/2020 22:51'!
testFindBinaryIndex

	| values |
	values := (1 to: 100) select: #isPrime.
	
	1 to: 100 do: [:every |
		every isPrime
			ifTrue: [
				self assert: (values indexOf: every) equals: (
					values findBinaryIndex: [:each | every <=> each])]
			ifFalse: [
				self
					should: [values findBinaryIndex: [:each | every <=> each]]
					raise: NotFound]].! !

!SequenceableCollectionTest methodsFor: 'tests - enumerating' stamp: 'ct 10/2/2020 22:52'!
testFindBinaryIndexDoIfNone

	| values |
	values := (1 to: 100) select: #isPrime.
	
	1 to: 100 do: [:every |
		every isPrime
			ifTrue: [
				self assert: (values indexOf: every) negated equals: ((values
					findBinaryIndex: [:each | every <=> each]
					do: [:result | result negated]
					ifNone: [self fail]))]
			ifFalse: [
				self assert: self equals: (values
					findBinaryIndex: [:each | every <=> each]
					do: [:result | self fail]
					ifNone: [self])]].! !

!SequenceableCollectionTest methodsFor: 'tests - enumerating' stamp: 'ct 10/2/2020 22:52'!
testFindBinaryIndexIfNone

	| values |
	values := (1 to: 100) select: #isPrime.
	
	1 to: 100 do: [:every |
		every isPrime
			ifTrue: [
				self assert: (values indexOf: every) equals: (values
					findBinaryIndex: [:each | every <=> each]
					ifNone: [self fail])]
			ifFalse: [
				self assert: self equals: (values
					findBinaryIndex: [:each | every <=> each]
					ifNone: [self])]].! !

!SequenceableCollectionTest methodsFor: 'tests - enumerating' stamp: 'ct 10/2/2020 23:03'!
testFindDelta

	| values |
	values := (1 to: 100) select: #isPrime.
	
	1 to: 100 do: [:every |
		every isPrime
			ifTrue: [
				self assert: every equals: (
					values findDelta: [:each | every - each])]
			ifFalse: [
				self
					should: [values findDelta: [:each | every - each]]
					raise: NotFound]].! !

!SequenceableCollectionTest methodsFor: 'tests - enumerating' stamp: 'ct 10/3/2020 00:12'!
testFindDeltaDoIfNone

	| values |
	values := (1 to: 100) select: #isPrime.
	
	1 to: 100 do: [:every |
		every isPrime
			ifTrue: [
				self assert: every negated equals: (values
					findDelta: [:each | every - each]
					do: [:each | each negated]
					ifNone: [self fail])]
			ifFalse: [
				self assert: self equals: (values
						findDelta: [:each | every - each]
						do: [self fail]
						ifNone: [self])]].! !

!SequenceableCollectionTest methodsFor: 'tests - enumerating' stamp: 'ct 10/3/2020 00:13'!
testFindDeltaIfNone

	| values |
	values := (1 to: 100) select: #isPrime.
	
	1 to: 100 do: [:every |
		every isPrime
			ifTrue: [
				self assert: every equals: (values
					findDelta: [:each | every - each]
					ifNone: [self fail])]
			ifFalse: [
				self assert: self equals: (values
					findDelta: [:each | every - each]
					ifNone: [self])]].! !

!SequenceableCollectionTest methodsFor: 'tests - enumerating' stamp: 'ct 10/3/2020 00:13'!
testFindDeltaIndex

	| values |
	values := (1 to: 100) select: #isPrime.
	
	1 to: 100 do: [:every |
		every isPrime
			ifTrue: [
				self assert: (values indexOf: every) equals: (
					values findDeltaIndex: [:each | every - each])]
			ifFalse: [
				self
					should: [values findDeltaIndex: [:each | every - each]]
					raise: NotFound]].! !

!SequenceableCollectionTest methodsFor: 'tests - enumerating' stamp: 'ct 10/3/2020 00:13'!
testFindDeltaIndexDoIfNone

	| values |
	values := (1 to: 100) select: #isPrime.
	
	1 to: 100 do: [:every |
		every isPrime
			ifTrue: [
				self assert: (values indexOf: every) negated equals: ((values
					findDeltaIndex: [:each | every - each]
					do: [:result | result negated]
					ifNone: [self fail]))]
			ifFalse: [
				self assert: self equals: (values
					findDeltaIndex: [:each | every - each]
					do: [:result | self fail]
					ifNone: [self])]].! !

!SequenceableCollectionTest methodsFor: 'tests - enumerating' stamp: 'ct 10/3/2020 00:14'!
testFindDeltaIndexIfNone

	| values |
	values := (1 to: 100) select: #isPrime.
	
	1 to: 100 do: [:every |
		every isPrime
			ifTrue: [
				self assert: (values indexOf: every) equals: (values
					findDeltaIndex: [:each | every - each]
					ifNone: [self fail])]
			ifFalse: [
				self assert: self equals: (values
					findDeltaIndex: [:each | every - each]
					ifNone: [self])]].! !

