SYSTEM WARNING: Creating default object from empty value

SYSTEM WARNING: Creating default object from empty value

Mantis - Squeak
Viewing Issue Advanced Details
1603 Collections minor always 08-03-05 23:25 04-18-10 22:04
nicolas cellier  
none trunk  
0001603: [BUG][FIX] Interval method includes:
This bug report is for Squeak 3.7beta latest update 5954
This is NOT a dramatic bug

The inclusion test does not work for intervals with a negative
step. To see the problem, you can try this:

 (-1 to: -111 by: -1) includes: -100

This answers false.

To find the element, you can evaluate this statement:
 (-1 to: -111 by: -1) indexOf: -100

This answers 100, which is obviously the right answer.
The test
   (-1 to: -111 by: -1) at: 100
confirms this.

The bug is in method valuesInclude: where we use the signed step,
scale it and compare it with an absolute value. We have to use the
absolute value of the step, too.
related to 0001602closed KenCausey [ENH] Interval method indexOf: 
related to 0006456closed andreas [BUG] Interval of Float do: infinite loop 
child of 0007180closed andreas Interval method indexOf: / includes: incomplete fix in squeak3.10 
child of 0007002new  The Mother of all issues involving interval 
 IntervalInclusionFix.2.cs.gz [^] (476 bytes) 08-03-05 23:25
 IntervalInclusionFix-gm.cs.gz [^] (290 bytes) 08-03-05 23:32
 IntervalIndexFix-bg.1.cs.gz [^] (812 bytes) 08-03-05 23:35
 Interval-Includes-Test.1.cs [^] (454 bytes) 04-29-07 19:29
 Interval-Includes-M1603-Test-nice.1.cs [^] (1,160 bytes) 02-03-08 20:46

08-03-05 23:31

"-the fix by Boris efectively removes the bug it describes.

-while doing the fix, an #asFloat is removed from the calculation; so
far I see no side effects, but perhaps someone put it in there for some
special case I can't imagine now, so this could be problematic

-reviewing the original implementation, I see that while it pretends to
avoid going through the list of possible values, this leads to extrange
answers like the following one:

(1 to: 5 by: 1) includes: 2 --> obvioulsy true
(1 to: 5 by: 1) includes: 2.5 --> obvioulsy false
(100000000000000 to: 500000000000000 by: 100000000000000)
   includes: 200000000000000 --> true as before, I just put some zeros
behind, so what?
(100000000000000 to: 500000000000000 by: 100000000000000)
   includes: 250000000000000 --> true! what? yes, try it yourself!

I'm attaching a version that fixes this problem and the previous one,
but perhaps introduces new failing cases, please someone (less asleep
than me) review it."

(attaching IntervalInclusionFix-gm.cs.gz)
08-03-05 23:33   
"Boris Gaertner" <>:

took the time to review a proposed fix and found
a new problem:

Thank you a lot for this review, German!

I will rewrite your example as a test case and post
it separately with the [TEST] prefix.

The bug that you reported is also present in my
proposed method #indexOf:startingAt:ifAbsent:
but more about that later.

It is very obvious that you found a bug, but this
morning I found it surprisingly difficult to explain
  * what is wrong
  * and why your fix is correct.
I even wonder whether I am less clever than the
average of Smalltalkers, but for the benefit of
those interested in the topic (and for my own
benefit, of course) I write down what I
think is an understandable reasoning:

Interval>>includes: does two checks:
1. First, the given number is checked against the
    interval bounds.
2. If the number is within the interval bounds,
    the method #valuesInclude: checks whether
    aNumber is an element of the infinite set:

    { val*step + start | val isInteger }

So we have to aske whether there exists an
integer val that satisfies the equation:

     aNumber = (val *step + start).

We can easily solve this equation for val
and obtain - now already written in Smalltalk:

   | val |
  val := (aNumber - self first) / self increment.
  ^val isInteger

This is the correct solution for as long as no floats
are involved. The test 'isInteger' is really simple
and in the absence of floats it is sufficient.

I had this in mind why I removed the #asFloat
from the original version, but I understand now
that I did not enough. I failed to elaborate a
correct algorithm that identifies floats
that are close to an integer value.

    val fractionPart abs < 1.0e-10

is such an algorithm and we can conclude
that your proposal is correct. The method
#fractionPart is also available for integers
and fractions and therefore your proposal
remains correct when we avoid early conversion
to floats.

Usually I try to avoid floats, but that is a matter
of personal preferences. However, when we prefer
to compute without floats for as long as possible,
we have to compute with fractions and the
computation of the fractional part of a fraction
of two large integers is perhaps a bit time consuming.

I think now that it is perhaps best to write:

valuesInclude: aNumber
    | val |
 val _ (aNumber - self first) / self increment.
 ^val isFloat
   ifTrue: [val fractionPart abs < 1.0e-10]
   ifFalse: [val isInteger]

This version uses exact calculation without
floats whenever that is possible. It also
avois unnecessary computations with

As mentioned earlier, Germans fix is also
needed for the method
that I proposed yesterday.

Looking a bit closer into the collection
hierarchy, I found that SequenceableCollection,
the direct superclass of Interval, implements
#includes: in this way:

  includes: anElement
      ^(self indexOf: anElement) ~= 0
That's it!
We do not really have to redefine #includes:
in Interval for speed, it is sufficient to have a fast
definition for computation of the element index.
This is easy to do, because we can
reuse parts of #valuesInclude:
which computes a zero-based index.

The attached change set is a proposal for the
use of the inherited #includes: It contains a
new version of
and it drops the methods
 #includes: and #valuesInclude:

So we improved #valuesInclude: just to
drop it after using its essence in a different method!"

(attaching IntervalIndexFix-bg.1.cs.gz)
08-03-05 23:36   
Wolfgang Eder <>:

how about adding a protocol like #fractionPartIsZero
or #isFractionPartZero, with implementations
in Integer, Fraction, and Float?
Just my 2c.."
08-03-05 23:39   
"Boris Gaertner" <>:

"Yes, you are right. The key point of your argumentation is
that, in Fraction, we can define


because we know that a fraction like 4/2 is automatically
converted into an integer. The definition in Float
is a bit more problematic,

  ^self fractionPart abs <1.0e-10

would do for the purpose of the method

The question is whether this is also a suitable definition
for other purposes.

Note that the test for exact zeroness is not appropriate:

(0.0 to: 1000 by: 0.1) inject: 0
    into: [ :sumOfIntegerValues :item |
             item fractionPart isZero
                 [Transcript show: item printString; cr.
                   sumOfIntegerValues := sumOfIntegerValues + 1]
              ifFalse: [sumOfIntegerValues]]

answers 2

because 0.1 has no exact binary representation and therefore
almost all interval elements have a non-zero fraction part.

By contrast, the expression

 ((0.0 to: 1000 by: 0.1) select:
    [ :item | item fractionPart isZero]) size

answers 1001

This is a surprise, but it is not too difficult to find the
#inject:into: uses Interval>>do: to enumerate the
interval elements, but select: does not use
Interval>>do: for element enumeration.
(The used definition of #select: is that in
SequenceableCollection. SequenceableCollection
uses #at: to access an collection element and
Interval>>at: uses multiplication to compute
the element for a given collection index.)

The use of two different algorithms for element
computation is of course not optimal, but this is
a different problem.

The closer I look to the definition of Interval,
the more I think that a careful code revision is
really desireable."
08-03-05 23:42   
I seperately filed in each of these changesets without errors but did not test them further.
nicolas cellier   
04-29-07 15:14   
Hello guys, sorry i have duplicated this bug report at [^]

However, I did check your proposals, and they do not seem to pass the case I submitted there.

valuesIncludes: fail when val is say 2.999999...
A more correct test would be
    val := (aNumber - self first) / self increment.
    (val - val rounded) abs < 1.0e-10

If we ever need a behaviour different from super. That is questionnable.

nicolas cellier   
02-02-08 23:38   
And good news, the problem you raised with select: (3 notes above) also has a solution...
You can also reconcile results of these constructs:

   1 to: self size do: [:i | (self at: i) doSomething].

  self do: [:each | each doSomething].

If you apply 0006456
nicolas cellier   
02-03-08 20:46   
"fix begin"
Installer mantis ensureFix: '1602 [ENH] Interval method indexOf:'.
"fix test"
Installer mantis bug: 1603 fix:'Interval-Includes-M1603-Test-nice.1.cs'.
"fix end"
nicolas cellier   
09-09-08 20:31   
See also 0007180 which is a new report making a synthesis of 0001602, 0001603 and 0006455.
nicolas cellier   
08-24-09 19:58   
Fixed in [^]