Smalltalk › Pharo › Pharo Smalltalk Users

Has anyone got some binary search code they like for the Collection class they want to share?

_‹ Previous Topic Next Topic _›

Classic

List

Threaded

8 messages Options

Paul DeBruicker

Has anyone got some binary search code they like for the Collection class they want to share?

I didn't see one in the image & I'm happy to implement one but thought I'd ask before I did.

Thanks

Paul

Sven Van Caekenberghe-2

Re: Has anyone got some binary search code they like for the Collection class they want to share?

It is already in the image: SequenceableCollection>>#findBinary:do:ifNone: & friends ;-)

> On 18 May 2017, at 20:22, PAUL DEBRUICKER <[hidden email]> wrote:
>
> I didn't see one in the image & I'm happy to implement one but thought I'd ask before I did.
>
> Thanks
>
> Paul

Esteban A. Maringolo

Re: Has anyone got some binary search code they like for the Collection class they want to share?

Great! How long has it been there? :)

And why is it in SequenceableCollection and not SortedCollection?

Regards!
Esteban A. Maringolo

2017-05-18 16:01 GMT-03:00 Sven Van Caekenberghe <[hidden email]>:

> It is already in the image: SequenceableCollection>>#findBinary:do:ifNone: & friends ;-)
>
>> On 18 May 2017, at 20:22, PAUL DEBRUICKER <[hidden email]> wrote:
>>
>> I didn't see one in the image & I'm happy to implement one but thought I'd ask before I did.
>>
>> Thanks
>>
>> Paul
>
>

Sven Van Caekenberghe-2

Re: Has anyone got some binary search code they like for the Collection class they want to share?

> On 18 May 2017, at 21:08, Esteban A. Maringolo <[hidden email]> wrote:
>
> Great! How long has it been there? :)

Apparently since 2012 - can't really remember

> And why is it in SequenceableCollection and not SortedCollection?

Hmm, probably because any SequenceableCollection could be sorted up front, like in

((1 to: 100) collect: [ :i | 100 atRandom ]) sort.

BTW, we also have #threeWayCompareTo: (the spaceship operator, aka <=>)

(((1 to: 100) collect: [ :i | 100 atRandom ]) , #(66)) sort
findBinaryIndex: [ :x | 66 threeWayCompareTo: x ]

> Regards!
> Esteban A. Maringolo
>
>
> 2017-05-18 16:01 GMT-03:00 Sven Van Caekenberghe <[hidden email]>:
>> It is already in the image: SequenceableCollection>>#findBinary:do:ifNone: & friends ;-)
>>
>>> On 18 May 2017, at 20:22, PAUL DEBRUICKER <[hidden email]> wrote:
>>>
>>> I didn't see one in the image & I'm happy to implement one but thought I'd ask before I did.
>>>
>>> Thanks
>>>
>>> Paul
>>
>>
>

Esteban A. Maringolo

Re: Has anyone got some binary search code they like for the Collection class they want to share?

2017-05-18 17:18 GMT-03:00 Sven Van Caekenberghe <[hidden email]>:
>> On 18 May 2017, at 21:08, Esteban A. Maringolo <[hidden email]> wrote:

>> Great! How long has it been there? :)
> Apparently since 2012 - can't really remember

My gosh, I remember searching for that years ago.

>> And why is it in SequenceableCollection and not SortedCollection?
> Hmm, probably because any SequenceableCollection could be sorted up front, like in
> ((1 to: 100) collect: [ :i | 100 atRandom ]) sort.

Ok, makes sense.

> BTW, we also have #threeWayCompareTo: (the spaceship operator, aka <=>)
>
> (((1 to: 100) collect: [ :i | 100 atRandom ]) , #(66)) sort
> findBinaryIndex: [ :x | 66 threeWayCompareTo: x ]

I think that method is part of the SortFunctions package I ported. It
is not in my Pharo 5 image at least.

Regards!

Esteban A. Maringolo

Sven Van Caekenberghe-2

Re: Has anyone got some binary search code they like for the Collection class they want to share?

> On 18 May 2017, at 22:47, Esteban A. Maringolo <[hidden email]> wrote:
>
> 2017-05-18 17:18 GMT-03:00 Sven Van Caekenberghe <[hidden email]>:
>>> On 18 May 2017, at 21:08, Esteban A. Maringolo <[hidden email]> wrote:
>
>>> Great! How long has it been there? :)
>> Apparently since 2012 - can't really remember
>
> My gosh, I remember searching for that years ago.
>
>>> And why is it in SequenceableCollection and not SortedCollection?
>> Hmm, probably because any SequenceableCollection could be sorted up front, like in
>> ((1 to: 100) collect: [ :i | 100 atRandom ]) sort.
>
> Ok, makes sense.
>
>> BTW, we also have #threeWayCompareTo: (the spaceship operator, aka <=>)
>>
>> (((1 to: 100) collect: [ :i | 100 atRandom ]) , #(66)) sort
>> findBinaryIndex: [ :x | 66 threeWayCompareTo: x ]
>
> I think that method is part of the SortFunctions package I ported. It
> is not in my Pharo 5 image at least.

Haha, yes, indeed: https://pharo.fogbugz.com/f/cases/17728/Integrate-Travis-Griggs-TAG-SortFunctions

One of the many new things in Pharo 6

> Regards!
>
> Esteban A. Maringolo
>

David T. Lewis

Re: Has anyone got some binary search code they like for the Collection class they want to share?

In reply to this post by Sven Van Caekenberghe-2

On Thu, May 18, 2017 at 10:18:34PM +0200, Sven Van Caekenberghe wrote:
>
> > On 18 May 2017, at 21:08, Esteban A. Maringolo <[hidden email]> wrote:
> >
> > Great! How long has it been there? :)
>
> Apparently since 2012 - can't really remember
>

Looking at a Squeak 3.0 image I would say that they were introduced in 2000,
and the author was Andreas Raab.

Dave

Sven Van Caekenberghe-2

Re: Has anyone got some binary search code they like for the Collection class they want to share?

> On 19 May 2017, at 00:47, David T. Lewis <[hidden email]> wrote:
>
> On Thu, May 18, 2017 at 10:18:34PM +0200, Sven Van Caekenberghe wrote:
>>
>>> On 18 May 2017, at 21:08, Esteban A. Maringolo <[hidden email]> wrote:
>>>
>>> Great! How long has it been there? :)
>>
>> Apparently since 2012 - can't really remember
>>
>
> Looking at a Squeak 3.0 image I would say that they were introduced in 2000,
> and the author was Andreas Raab.

Makes sense, I knew that code was older ...

> Dave
>
>