Issue 3345 in pharo: findBinary: from Cuis as integrated in Squeak

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!

Updates:
        Status: Duplicate
        Mergedinto: 3950

Comment #1 on issue 3345 by [hidden email]: findBinary: from Cuis as  
integrated in Squeak
http://code.google.com/p/pharo/issues/detail?id=3345

Pls Discuss in Issue 3950