Mantis Bugtracker
  

Viewing Issue Simple Details Jump to Notes ] View Advanced ] Issue History ] Print ]
ID Category Severity Reproducibility Date Submitted Last Update
0001602 [Squeak] Collections minor always 08-03-05 23:05 09-10-08 17:40
Reporter BGaertner View Status public  
Assigned To KenCausey
Priority normal Resolution fixed  
Status closed   Product Version
Summary 0001602: [ENH] Interval method indexOf:
Description "Change Set: IntervalIndexEnh
Date: 15 June 2004
Author: Boris Gaertner

Interval inherits #indexOf:startingAt:ifAbsent: from SequenceableCollection.
The inherited method enumerates all elements until it finds a hit. Try

 (1 to: 100000 by: 0.01) indexOf: 99999

to see that this can be extremely time consuming. For Intervals, we can do
better.

This enhancement assumes that the elements of an Interval are Numbers.
It is tempting to use intervals that contain instances of DataAndTime, but
this would require the generalization of some methods. "
Additional Information
Attached Files  IntervalIndexEnh.1.cs.gz [^] (749 bytes) 08-03-05 23:05
 IntervalIndexEnh.3.cs.gz [^] (785 bytes) 08-03-05 23:10
 Interval-indexOf-Test.1.cs [^] (454 bytes) 04-29-07 19:29
 IntervalIndexEnh.4.cs [^] (1,488 bytes) 04-30-07 17:08
 Interval-IndexOf-M1602-Patch-nice-BG.1.cs [^] (2,154 bytes) 02-03-08 20:25
 Interval-indexOf-M1602-Test-nice.1.cs [^] (1,160 bytes) 02-03-08 20:36

- Relationships

SYSTEM WARNING: Creating default object from empty value

SYSTEM WARNING: Creating default object from empty value

related to 0001603closed nicolas cellier [BUG][FIX] Interval method includes: 
related to 0006456closed andreas [BUG] Interval of Float do: infinite loop 
child of 0007002new  The Mother of all issues involving interval 

- Notes
(0002100 - 630 - 863 - 907 - 907 - 907 - 907)
KenCausey
08-03-05 23:09

"Boris Gaertner" <Boris.Gaertner@gmx.net>:

"The code that I posted earlier today is wrong:
For
   (1 to: 10 by: 0.1) indexOf: 1000
the correct answer is 0, but my code answers 9991,
This is a stupid mistake, because the check that is
needed here, is available - I simply did not use
what is available. The method
  indexOf:startingAt:ifAbsent:
has to check:

    (self rangeIncludes: anElement)
      ifFalse: [^0].

The attached change set contaisn a method that performs
that check.

In a separate mail, I will post two additional tests.

My apologies for my mistake"

(attaching IntervalIndexEnh.3.cs.gz)
 
(0002101 - 83 - 83 - 83 - 83 - 83 - 83)
KenCausey
08-03-05 23:11

I was able to load both changesets without errors, but I did not test them further.
 
(0010516 - 149 - 185 - 185 - 185 - 185 - 185)
edgardec
04-10-07 12:28

In a 3.10alpha.7083

Before the fileIn
MessageTally time: [(1 to: 100000 by: 0.01) indexOf: 99999] 53772
After 0

I collecting in a 3.10 update
 
(0010540 - 76 - 82 - 82 - 82 - 82 - 82)
edgardec
04-13-07 21:03

This now is 7084CollectionEnh.cs and was in updates for 3.10
Thanks Boris !
 
(0010628 - 1123 - 1342 - 1342 - 1857 - 1857 - 1857)
nicolas cellier
04-29-07 19:18
edited on: 02-03-08 20:38

As explained by german at 0001603 , this patch is wrong

(100000000000000 to: 500000000000000 by: 100000000000000)
   indexOf: 250000000000000
should answer 0

See uploaded test provided.

German said code should be (val fractionPart abs * 100000000 < 1)

This trick is there to answer true for Float that fall near one of the elements.
As explained by me at 0006455 ,
1) This is QUESTIONNABLE
2) This is still wrong

Code should rather test

(val - val rounded) abs * 100000000 < 1.

This is programmed in patch number 4.

And there, why 8 decimals? or 10 or whatever?

Interval-indexOf-M1602-Test-nice.1.cs contains tests for 0001602 and 0006455 .

Last thing, Boris patch must not be dissociated from 0001603. So Interval>>#includes: is also removed by Interval-IndexOf-M1602-Patch-nice-BG.1.cs.
Otherwise, you will have different results with includes: and indexOf:

If arithmetic is exact (Integer, Fraction, ScaledDecimal...), then no fuzzy inclusion test takes place.

Note that super indexOf: would behave better if 0006456 is applied, but with strict equality, as done by self asArray indexOf:.

 
(0011733 - 186 - 252 - 252 - 252 - 252 - 252)
nicolas cellier
02-03-08 19:40
edited on: 02-03-08 20:37

"fix begin"
Installer mantis bug: 1602 fix:'Interval-IndexOf-M1602-Patch-nice-BG.1.cs'.
"fix test"
Installer mantis bug: 1602 fix:'Interval-indexOf-M1602-Test-nice.1.cs'.
"fix end"

 
(0012392 - 833 - 947 - 947 - 947 - 947 - 947)
nicolas cellier
07-19-08 20:52

One more thing about Interval of Float: we know they are nasty things due to inexact arithmetic and should better be avoided.

Here, i exhibit an example of Float Interval that does not includes its elements, whatever the efforts to make the includes: test fuzzy...

| eps i |
eps := (1.0 timesTwoPower: -52) * 1.25.
i := (1 to: 1+(99*eps) by: eps).
^(i includes: (i at: 2))

How many elements are not in the collection?

| eps i |
eps := (1.0 timesTwoPower: -52) * 1.25.
i := (1 to: 1+(99*eps) by: eps).
(i count: [:e | (i includes: e) not]) / i size asFloat.

You see, 75% ...
Fuzziness efforts are vain...
You won't find a generic threshold deserving to be written in the Kernel stone.
Should be up to application to decide about the threshold and the policy if they really insist on using Interval of Floats...
 
(0012603 - 542 - 542 - 542 - 542 - 542 - 542)
KenCausey
09-09-08 14:58

Would someone familiar with this issue please consider opening a new report based on it's status now (post-3.10.2) or point to existing issues that cover it so that this issue can be closed? It gets very confusing to have long histories on these issues and we really need to change to a system where when an issue is harvested the issue is immediately marked resolved and discussion stops (with the exception of adding relationships and pointing out those relationships). And when a release is issued the issue should be immediately closed.
 
(0012620 - 241 - 265 - 265 - 381 - 381 - 381)
nicolas cellier
09-09-08 20:26

IMO, better a long history than no history.
However, yes, what a tedious job to read verbose notes!
A new issue has now be opened at 0007180 :
- because patch uploaded in 3.10 does not solve the problem.
- so that this issue can be closed.
 
(0012627 - 142 - 142 - 142 - 229 - 229 - 229)
KenCausey
09-10-08 17:40

Thanks again Nicolas. Partially harvested in update 7084, released with 3.10. The saga continues at 0001603, please continue discussion there.
 

- Issue History
Date Modified Username Field Change
08-03-05 23:05 KenCausey New Issue
08-03-05 23:05 KenCausey File Added: IntervalIndexEnh.1.cs.gz
08-03-05 23:07 KenCausey Reporter KenCausey => BGaertner
08-03-05 23:09 KenCausey Note Added: 0002100
08-03-05 23:10 KenCausey File Added: IntervalIndexEnh.3.cs.gz
08-03-05 23:11 KenCausey Note Added: 0002101
08-03-05 23:56 KenCausey Relationship added related to 0001603
10-25-05 20:53 BGaertner Issue Monitored: BGaertner
04-10-07 12:28 edgardec Note Added: 0010516
04-13-07 21:03 edgardec Note Added: 0010540
04-29-07 19:18 nicolas cellier Note Added: 0010628
04-29-07 19:29 nicolas cellier File Added: Interval-indexOf-Test.1.cs
04-30-07 17:08 nicolas cellier File Added: IntervalIndexEnh.4.cs
04-30-07 17:10 nicolas cellier Note Edited: 0010628
04-30-07 17:10 nicolas cellier Note Edited: 0010628
02-03-08 19:40 nicolas cellier Note Added: 0011733
02-03-08 19:42 nicolas cellier Note Edited: 0010628
02-03-08 19:43 nicolas cellier Note Edited: 0011733
02-03-08 20:25 nicolas cellier File Added: Interval-IndexOf-M1602-Patch-nice-BG.1.cs
02-03-08 20:25 nicolas cellier Note Edited: 0011733
02-03-08 20:27 nicolas cellier Note Edited: 0010628
02-03-08 20:36 nicolas cellier File Added: Interval-indexOf-M1602-Test-nice.1.cs
02-03-08 20:37 nicolas cellier Note Edited: 0011733
02-03-08 20:38 nicolas cellier Note Edited: 0010628
07-19-08 20:52 nicolas cellier Note Added: 0012392
09-09-08 14:58 KenCausey Note Added: 0012603
09-09-08 14:58 KenCausey Assigned To  => KenCausey
09-09-08 14:58 KenCausey Status new => feedback
09-09-08 20:26 nicolas cellier Note Added: 0012620
09-10-08 17:40 KenCausey Status feedback => closed
09-10-08 17:40 KenCausey Note Added: 0012627
09-10-08 17:40 KenCausey Resolution open => fixed
09-10-08 17:40 KenCausey Fixed in Version  => 3.10
10-03-09 20:28 nicolas cellier Relationship added related to 0006456
08-21-10 13:08 nicolas cellier Relationship added child of 0007002


Mantis 1.0.8[^]
Copyright © 2000 - 2007 Mantis Group
130 total queries executed.
61 unique queries executed.
Powered by Mantis Bugtracker