Status: FixedWaitingToBePharoed
Owner: stephane.ducasse
Labels: Milestone-1.3 Difficulty-Easy
New issue 3345 by stephane.ducasse: findBinary: from Cuis as integrated in
Squeak
http://code.google.com/p/pharo/issues/detail?id=3345
It would be nice to have a look at that and write some tests
Levente Uzonyi uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-ul.408.mcz
==================== Summary ====================
Name: Collections-ul.408
Author: ul
Time: 17 November 2010, 12:25:59.364 pm
UUID: 1520a654-9c34-734d-ae16-a600d1a2b948
Ancestors: Collections-ul.407
- findBinary* enhancements from Cuis.
=============== Diff against Collections-ul.407 ===============
Item was changed:
----- Method: SequenceableCollection>>findBinary: (in
category 'enumerating') -----
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.
Examples:
+ #(1 3 5 7 11 15 23) findBinary: [ :arg | 11 - arg ]
- #(1 3 5 7 11 15 23) findBinary:[:arg| 11 - arg]
"
+ ^self findBinary: aBlock do: [ :found | found ] ifNone: [ self
errorNotFound: aBlock ]!
- ^self findBinary: aBlock ifNone: [self errorNotFound: aBlock]!
Item was added:
+ ----- Method: SequenceableCollection>>findBinary:do:ifNone: (in
category 'enumerating') -----
+ 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.
+ 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 ]) ]!
Item was changed:
----- Method: SequenceableCollection>>findBinary:ifNone: (in
category 'enumerating') -----
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."
+
+ ^self findBinary: aBlock do: [ :found | found ] ifNone:
exceptionBlock!
- If no matching element is found, evaluate exceptionBlock."
- | index low high test item |
- low := 1.
- high := self size.
- [index := high + low // 2.
- low > high] whileFalse:[
- test := aBlock value: (item := self at: index).
- test = 0
- ifTrue:[^item]
- ifFalse:[test > 0
- ifTrue: [low := index + 1]
- ifFalse: [high := index - 1]]].
- ^exceptionBlock value!
Item was changed:
----- Method: SequenceableCollection>>findBinaryIndex: (in
category 'enumerating') -----
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.
Examples:
+ #(1 3 5 7 11 15 23) findBinaryIndex: [ :arg | 11 - arg ]
- #(1 3 5 7 11 15 23) findBinaryIndex:[:arg| 11 - arg]
"
+ ^self findBinaryIndex: aBlock do: [ :found | found ] ifNone: [ self
errorNotFound: aBlock]!
- ^self findBinaryIndex: aBlock ifNone: [self errorNotFound: aBlock]!
Item was added:
+ ----- Method: SequenceableCollection>>findBinaryIndex:do:ifNone: (in
category 'enumerating') -----
+ 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.
+ 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 | 12 - 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 |
+ low := 1.
+ high := self size.
+ [
+ index := high + low // 2.
+ low > high ] whileFalse: [
+ | test |
+ test := aBlock value: (self at: index).
+ test = 0
+ ifTrue: [ ^actionBlock value: index ]
+ ifFalse: [ test > 0
+ ifTrue: [ low := index + 1 ]
+ ifFalse: [ high := index - 1 ] ] ].
+ ^exceptionBlock cull: high cull: low!
Item was changed:
----- Method: SequenceableCollection>>findBinaryIndex:ifNone: (in
category 'enumerating') -----
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."
+
+ ^self findBinaryIndex: aBlock do: [ :found | found ] ifNone:
exceptionBlock!
- If no matching element is found, evaluate exceptionBlock."
- | index low high test |
- low := 1.
- high := self size.
- [index := high + low // 2.
- low > high] whileFalse:[
- test := aBlock value: (self at: index).
- test = 0
- ifTrue:[^index]
- ifFalse:[test > 0
- ifTrue: [low := index + 1]
- ifFalse: [high := index - 1]]].
- ^exceptionBlock value!
