<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=iso-8859-1">
<META content="MSHTML 6.00.2800.1476" name=GENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY bgColor=#ffffff>
<DIV><FONT face=Arial size=2>Fix for Set atRandom: I'd make it a changeset
but I don't know how to make a changeset with a single entry. I told it to
save a ChangeSet and it saved out 26 megabytes.</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>Since Sets never shrink, it does make sense to have
the relatively prime scanning for large capacity, nearly empty
sets.</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>Note that there is a possible
optimization for generating relatively prime numbers. If the Set is a
power of two in length, then any odd number will do. Unfortunately Set's class
method "sizeFor" makes it impossible to make a set a power of two in
length.</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>So, this version checks, and does the optimization
if it will do any good.</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>If you want that optimization of an optimazation to
be enabled for new Sets then change sizeFor as
well. </FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>sizeFor: nElements<BR> "Large enough size to
hold nElements with some slop (see fullCheck)"<BR> nElements <= 0
ifTrue: [^ 1].<BR> ^ nElements*2</FONT></DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2></FONT> </DIV>
<DIV><FONT face=Arial size=2>atRandom: aGenerator<BR> | ind entry i span
foundrelativeprime |<BR> self
emptyCheck.<BR> entry _ nil.<BR>
i_1.<BR> "try 30 times with random
samples"<BR> [ entry == nil and: [i<30] ] whileTrue:
[<BR> ind _ aGenerator
nextInt: array size.<BR>
entry _ array at:
ind.<BR> i _
i+1<BR> ].<BR> entry == nil ifTrue:
[<BR> "failed 30 random samples - the
array must be almost empty"<BR> "pick
a random, relatively prime span and scan every
entry"<BR> <BR> "Special case for Sets that are powers of two in
size. "<BR> "If you make a Set that's a power of two in size > 1
then it will"<BR> "always be a power of two in
size"<BR> <BR> (array size bitAnd: ((array size) - 1)) = 0
ifTrue: [<BR> span _ (aGenerator nextInt: (((array size)
+ 1) // 2)) * 2 - 1.<BR> ] ifFalse: [ <BR> "not
a power of two - find any number that's relatively
prime"<BR>
foundrelativeprime _
false.<BR> [
foundrelativeprime] whileFalse:
[<BR>
span _ 1 + (aGenerator nextInt: ((array
size)-1)).<BR>
foundrelativeprime _ (1 = ((array size) gcd:
span)).<BR> ].<BR> ].<BR>
i _ array size.<BR> [i
> 1] whileTrue:
[<BR> ind _
(ind+span-1) \\ (array size) +
1.<BR> entry _
array at:
ind.<BR> entry
== nil
ifFalse:[^entry].<BR>
i _ i-1.<BR>
].<BR> self
errorEmptyCollection.<BR> ].<BR>
^entry.</FONT></DIV></BODY></HTML>