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.

Since Sets never shrink, it does make sense to have the relatively prime scanning for large capacity, nearly empty sets.

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.

So, this version checks, and does the optimization if it will do any good.

If you want that optimization of an optimazation to be enabled for new Sets then change sizeFor as well. 

sizeFor: nElements
 "Large enough size to hold nElements with some slop (see fullCheck)"
 nElements <= 0 ifTrue: [^ 1].
 ^ nElements*2


atRandom: aGenerator
  | ind entry i span foundrelativeprime |
    self emptyCheck.
    entry _ nil.
    i_1.
    "try 30 times with random samples"
    [ entry == nil and: [i<30] ] whileTrue: [
          ind _ aGenerator nextInt: array size.
          entry _ array at: ind.
           i _ i+1
    ].
    entry == nil  ifTrue: [
        "failed 30 random samples - the array must be almost empty"
        "pick a random, relatively prime span and scan every entry"
 
  "Special case for Sets that are powers of two in size. "
  "If you make a Set that's a power of two in size > 1 then it will"
  "always be a power of two in size"
  
  (array size bitAnd: ((array size) - 1)) = 0 ifTrue: [
     span _ (aGenerator nextInt: (((array size) + 1) // 2)) * 2 - 1.
  ] ifFalse: [ 
   "not a power of two - find any number that's relatively prime"
          foundrelativeprime _ false.
          [ foundrelativeprime] whileFalse: [
              span _ 1 + (aGenerator nextInt: ((array size)-1)).
           foundrelativeprime _ (1 = ((array size) gcd: span)).
   ].
  ].
         i _ array size.
         [i > 1] whileTrue: [
            ind _ (ind+span-1) \\ (array size) + 1.
            entry _ array at: ind.
            entry == nil ifFalse:[^entry].
            i _ i-1.
        ].
        self errorEmptyCollection.
    ].
    ^entry.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20041129/6aa9edf4/attachment.htm