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!