0001603: [BUG][FIX] Interval method includes:

Notes
(0002102 - 1078 - 1274 - 1274 - 1274 - 1274 - 1274) KenCausey 08-03-05 23:31	germanmorales@delta-sys.com: "-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)

(0002103 - 3750 - 4833 - 4926 - 4926 - 4926 - 4926) KenCausey 08-03-05 23:33	"Boris Gaertner" <Boris.Gaertner@gmx.net>: "<germanmorales@delta-sys.com> 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: { valstep + 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 fractions. ======================== As mentioned earlier, Germans fix is also needed for the method indexOf:startingAt:ifAbsent: 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 indexOf:startingAt:ifAbsent: 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)

(0002104 - 196 - 248 - 289 - 289 - 289 - 289) KenCausey 08-03-05 23:36	Wolfgang Eder <edw@generalmagic.at>: "Boris, how about adding a protocol like #fractionPartIsZero or #isFractionPartZero, with implementations in Integer, Fraction, and Float? Just my 2c.."

(0002105 - 1855 - 2751 - 2795 - 2795 - 2795 - 2795) KenCausey 08-03-05 23:39	"Boris Gaertner" <Boris.Gaertner@gmx.net>: "Yes, you are right. The key point of your argumentation is that, in Fraction, we can define fractionPartIsZero ^false because we know that a fraction like 4/2 is automatically converted into an integer. The definition in Float is a bit more problematic, fractionPartIsZero ^self fractionPart abs <1.0e-10 would do for the purpose of the method Interval>>includes: 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 ifTrue: [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 reason: #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."

(0002106 - 92 - 92 - 92 - 92 - 92 - 92) KenCausey 08-03-05 23:42	I seperately filed in each of these changesets without errors but did not test them further.

(0010627 - 444 - 553 - 681 - 681 - 681 - 681) nicolas cellier 04-29-07 15:14 edited on: 04-29-07 15:16	Hello guys, sorry i have duplicated this bug report at http://bugs.squeak.org/view.php?id=6455 [^] 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.

(0011732 - 275 - 359 - 359 - 451 - 451 - 451) 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]. with: self do: [:each \| each doSomething]. If you apply 0006456

(0011734 - 176 - 230 - 230 - 230 - 230 - 230) 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"

(0012621 - 82 - 82 - 82 - 450 - 450 - 450) nicolas cellier 09-09-08 20:31	See also 0007180 which is a new report making a synthesis of 0001602, 0001603 and 0006455.

(0013258 - 64 - 64 - 224 - 224 - 224 - 224) nicolas cellier 08-24-09 19:58	Fixed in http://source.squeak.org/trunk/Collections-nice.100.mcz [^]

Issue History
Date Modified	Username	Field	Change
08-03-05 23:25	KenCausey	New Issue
08-03-05 23:25	KenCausey	File Added: IntervalInclusionFix.2.cs.gz
08-03-05 23:26	KenCausey	Reporter	KenCausey => BGaertner
08-03-05 23:31	KenCausey	Note Added: 0002102
08-03-05 23:32	KenCausey	File Added: IntervalInclusionFix-gm.cs.gz
08-03-05 23:33	KenCausey	Note Added: 0002103
08-03-05 23:35	KenCausey	File Added: IntervalIndexFix-bg.1.cs.gz
08-03-05 23:36	KenCausey	Note Added: 0002104
08-03-05 23:39	KenCausey	Note Added: 0002105
08-03-05 23:42	KenCausey	Note Added: 0002106
08-03-05 23:56	KenCausey	Relationship added	related to 0001602
10-25-05 20:53	BGaertner	Issue Monitored: BGaertner
04-29-07 15:14	nicolas cellier	Note Added: 0010627
04-29-07 15:16	nicolas cellier	Note Edited: 0010627
04-29-07 19:29	nicolas cellier	File Added: Interval-Includes-Test.1.cs
02-02-08 23:38	nicolas cellier	Note Added: 0011732
02-03-08 20:46	nicolas cellier	Note Added: 0011734
02-03-08 20:46	nicolas cellier	File Added: Interval-Includes-M1603-Test-nice.1.cs
09-09-08 20:31	nicolas cellier	Note Added: 0012621
12-08-08 22:39	Keith_Hodges	Relationship added	child of 0007180
12-17-08 03:35	Keith_Hodges	Status	new => acknowledged
01-09-09 23:51	Keith_Hodges	Status	acknowledged => testing
01-10-09 03:39	Keith_Hodges	Status	testing => resolved
01-10-09 03:39	Keith_Hodges	Fixed in Version	=> 3.11
01-10-09 03:39	Keith_Hodges	Resolution	open => fixed
01-10-09 03:39	Keith_Hodges	Assigned To	=> Keith_Hodges
01-10-09 03:41	Keith_Hodges	Status	resolved => testing
08-24-09 19:58	nicolas cellier	Note Added: 0013258
10-03-09 19:33	Keith_Hodges	Status	testing => assigned
10-03-09 19:33	Keith_Hodges	Assigned To	Keith_Hodges => andreas
10-03-09 20:07	nicolas cellier	Status	assigned => resolved
10-03-09 20:07	nicolas cellier	Fixed in Version	3.11 => trunk
10-03-09 20:28	nicolas cellier	Relationship added	related to 0006456
10-04-09 17:20	KenCausey	Assigned To	andreas => nicolas cellier
04-18-10 22:04	andreas	Status	resolved => closed
08-21-10 13:07	nicolas cellier	Relationship added	related to 0007002
08-21-10 13:08	nicolas cellier	Relationship deleted	related to 0007002
08-21-10 13:08	nicolas cellier	Relationship added	child of 0007002