View Issue Details

IDProjectCategoryView StatusLast Update
0035250LazarusTAChartpublic2019-03-22 19:04
ReporterMarcin WiazowskiAssigned Towp 
PrioritynormalSeverityminorReproducibilityalways
Status closedResolutionfixed 
Product Version2.1 (SVN)Product Build60720 
Target Version2.2Fixed in Version 
Summary0035250: TAChart: various problems with TIntervalList.Epsilon, and possible solutions
DescriptionTIntervalList is an internal helper object, currently used by four series:
- TExpressionSeries,
- TFuncSeries,
- TCubicSplineSeries,
- TFitSeries.

All these series have a Step property. When drawing the series, for every pixel on the horizontal axis (when Step = 1) / every second pixel on the horizontal axis (when Step = 2) / etc. / etc., function's Y value is calculated, and a straight line is drawn to the last calculated (X, Y) point.

The internal TIntervalList object implements this behavior. In Addition, some ranges can be omitted when drawing: for example, when we have Y := cotan(X), we may wish to exclude X = 0 from drawing, along with some range around - for example X values between -0.2 and 0.2. Excluded points and ranges give us an exclusion list.

The interesting TIntervalList's methods / properties are:
- procedure AddPoint(APoint: Double)
- procedure AddRange(AStart, AEnd: Double)
- function Intersect(var ALeft, ARight: Double): Boolean
- property Epsilon: Double

AddPoint() adds a point to the exclusion list - for example AddPoint(0).
AddRange() adds a range to the exclusion list - for example AddRange(-0.2, 0.2).
Intersect() is used internally, to check if, between X = ALeft and X = ARight, there is some excluded point or range.
Epsilon is used internally to enlarge excluded points / ranges - in both sides, by the Epsilon value. Default Epsilon value is 1E-6.



The attached Algorithm.png shows the idea of TIntervalList's work. Let's assume, that we want to draw some function in the X = 1 .. 5 range, and our chart's width is 101 pixels. For AStep = 1, we need to calculate function values for the following X values (in case when there are no excluded ranges in the middle):

X = 1 (pixel 1)
X = 1.04 (pixel 2)
X = 1.08 (pixel 3)
X = 1.12 (pixel 4)
...
X = 4.88 (pixel 98)
X = 4.92 (pixel 99)
X = 4.96 (pixel 100)
X = 5 (pixel 101)



Now let's assume that, for some reason, we requested excluding the X = 1.15 .. 1.25 range (red area on the image), and we have Epsilon set to 0.02 - in this case, the final excluded area will be 1.13 .. 1.27 (pink area on the image). The drawing algorithm will be:

- initialize X to 1 and Delta to 0.04

- call Intersect(X, X+Delta) to see if the X .. X+Delta = 1 .. 1.04 range intersects some excluded region -> no ->
  draw a line from (X, func(X)) to (X+Delta, func(X+Delta)) -> set X to X+Delta, i.e. to 1.04

- call Intersect(X, X+Delta) to see if the X .. X+Delta = 1.04 .. 1.08 range intersects some excluded region -> no ->
  draw a line from (X, func(X)) to (X+Delta, func(X+Delta)) -> set X to X+Delta, i.e. to 1.08

- call Intersect(X, X+Delta) to see if the X .. X+Delta = 1.08 .. 1.12 range intersects some excluded region -> no ->
  draw a line from (X, func(X)) to (X+Delta, func(X+Delta)) -> set X to X+Delta, i.e. to 1.12

- call Intersect(X, X+Delta) to see if the X .. X+Delta = 1.12 .. 1.16 range intersects some excluded region -> YES, the 1.15 .. 1.25 region is intersected ->
  draw a line from (X, func(X)) to (RangeLo-Epsilon=1.13, func(RangeLo-Epsilon=1.13)) -> set X to RangeHi+Epsilon, i.e. to 1.27 ->
  move to (X, func(X)) to start a new line there

- call Intersect(X, X+Delta) to see if the X .. X+Delta = 1.27 .. 1.31 range intersects some excluded region -> no ->
  draw a line from (X, func(X)) to (X+Delta, func(X+Delta)) -> set X to X+Delta, i.e. to 1.31

- ...




Now let's take a look at problems with the current TIntervalList implementation:




PROBLEM 1:

a) Launch Reproduce1 application and press the button 4 times. Application hangs forever.

b) Load Reproduce1 application in IDE, select ListChartSource, launch DataPoints editor, change first X value from -1000 to -1E15 and close the DataPoints editor by pressing Ok. Lazarus IDE hangs forever.




PROBLEM 2:

Launch Reproduce2 application. Series line is drawn NOT from the first point - there is a gap between the first point and the line's beginning.




PROBLEM 3:

Launch Reproduce3 application and press the button 3 times. Series' line disappears. Press the button 4 more times - series is drawn in a completely improper way.




PROBLEM 4:

Launch Reproduce4 application. Series line is drawn from X ~= -2.5 to X ~= 0, and then back to X = -0.3.




PROBLEM 5:

Launch Reproduce5 application and press the button - an exception "Epsilon <= 0" is raised, although documentation (at http://wiki.freepascal.org/TAChart_Tutorial:_Function_Series) says, that Epsilon can be set to 0: "you can show this point in the chart by setting Epsilon = 0".




PROBLEM 6:

Load Reproduce6 application in IDE, select Chart1ExpressionSeries, go to the DomainEpsilon property and try to change it to any value different than 1E-6. It always immediately reverts back to 1E-6. This isn't in fact a problem in the TIntervalList itself, but it's related.




For explanations, see below.
TagsNo tags attached.
Fixed in Revision60740
LazTarget2.2
WidgetsetWin32/Win64
Attached Files
  • Algorithm.png (5,008 bytes)
    Algorithm.png (5,008 bytes)
  • Reproduce1.zip (2,632 bytes)
  • Reproduce2.zip (2,499 bytes)
  • Reproduce3.zip (2,634 bytes)
  • Reproduce4.zip (2,404 bytes)
  • Reproduce5.zip (2,453 bytes)
  • Reproduce6.zip (2,331 bytes)
  • solution1.diff (11,526 bytes)
    Index: components/tachart/tachartutils.pas
    ===================================================================
    --- components/tachart/tachartutils.pas	(revision 60720)
    +++ components/tachart/tachartutils.pas	(working copy)
    @@ -121,25 +121,21 @@
     
       TIntervalList = class
       private
    -    FEpsilon: Double;
         FIntervals: array of TDoubleInterval;
         FOnChange: TNotifyEvent;
         procedure Changed;
         function GetInterval(AIndex: Integer): TDoubleInterval;
         function GetIntervalCount: Integer;
    -    procedure SetEpsilon(AValue: Double);
         procedure SetOnChange(AValue: TNotifyEvent);
       public
         procedure Assign(ASource: TIntervalList);
    -    constructor Create;
       public
    -    procedure AddPoint(APoint: Double); inline;
    +    procedure AddPoint(APoint: Double; AEpsilon: Double = 1e-6);
         procedure AddRange(AStart, AEnd: Double);
         procedure Clear;
         function Intersect(
           var ALeft, ARight: Double; var AHint: Integer): Boolean;
       public
    -    property Epsilon: Double read FEpsilon write SetEpsilon;
         property Interval[AIndex: Integer]: TDoubleInterval read GetInterval;
         property IntervalCount: Integer read GetIntervalCount;
         property OnChange: TNotifyEvent read FOnChange write SetOnChange;
    @@ -699,9 +695,10 @@
     
     { TIntervalList }
     
    -procedure TIntervalList.AddPoint(APoint: Double); inline;
    +procedure TIntervalList.AddPoint(APoint: Double; AEpsilon: Double = 1e-6); deprecated 'Use AddRange instead';
     begin
    -  AddRange(APoint, APoint);
    +  AEpsilon := abs(AEpsilon);
    +  AddRange(APoint - AEpsilon, APoint + AEpsilon);
     end;
     
     procedure TIntervalList.AddRange(AStart, AEnd: Double);
    @@ -710,6 +707,7 @@
       j: Integer;
       k: Integer;
     begin
    +  if AStart >= AEnd then exit;
       i := 0;
       while (i <= High(FIntervals)) and (FIntervals[i].FEnd < AStart) do
         i += 1;
    @@ -736,7 +734,6 @@
     
     procedure TIntervalList.Assign(ASource: TIntervalList);
     begin
    -  FEpsilon := ASource.FEpsilon;
       FIntervals := Copy(ASource.FIntervals);
     end;
     
    @@ -752,11 +749,6 @@
       Changed;
     end;
     
    -constructor TIntervalList.Create;
    -begin
    -  FEpsilon := DEFAULT_EPSILON;
    -end;
    -
     function TIntervalList.GetInterval(AIndex: Integer): TDoubleInterval;
     begin
       Result := FIntervals[AIndex];
    @@ -776,13 +768,13 @@
       if Length(FIntervals) = 0 then exit;
     
       AHint := EnsureRange(AHint, 0, High(FIntervals));
    -  while (AHint > 0) and (FIntervals[AHint].FStart > ARight) do
    +  while (AHint > 0) and (FIntervals[AHint].FStart >= ARight) do
         Dec(AHint);
     
       while
    -    (AHint <= High(FIntervals)) and (FIntervals[AHint].FStart <= ARight)
    +    (AHint <= High(FIntervals)) and (FIntervals[AHint].FStart < ARight)
       do begin
    -    if FIntervals[AHint].FEnd >= ALeft then begin
    +    if FIntervals[AHint].FEnd > ALeft then begin
           if not Result then fi := AHint;
           li := AHint;
           Result := true;
    @@ -791,20 +783,11 @@
       end;
     
       if Result then begin
    -    ALeft := FIntervals[fi].FStart - Epsilon;
    -    ARight := FIntervals[li].FEnd + Epsilon;
    +    ALeft := FIntervals[fi].FStart;
    +    ARight := FIntervals[li].FEnd;
       end;
     end;
     
    -procedure TIntervalList.SetEpsilon(AValue: Double);
    -begin
    -  if FEpsilon = AValue then exit;
    -  if AValue <= 0 then
    -    raise EChartIntervalError.Create('Epsilon <= 0');
    -  FEpsilon := AValue;
    -  Changed;
    -end;
    -
     procedure TIntervalList.SetOnChange(AValue: TNotifyEvent);
     begin
       if TMethod(FOnChange) = TMethod(AValue) then exit;
    Index: components/tachart/taexpressionseries.pas
    ===================================================================
    --- components/tachart/taexpressionseries.pas	(revision 60720)
    +++ components/tachart/taexpressionseries.pas	(working copy)
    @@ -89,7 +89,6 @@
       TExpressionSeries = class(TCustomFuncSeries)
       private
         FDomain: String;
    -    FDomainEpsilon: Double;
         FDomainScanner: TChartDomainScanner;
         FExpression: String;
         FParams: TChartExprParams;
    @@ -97,6 +96,7 @@
         FVariable: String;
         FX: TFPExprIdentifierDef;
         FDirty: Boolean;
    +    function GetDomainEpsilon: Double;
         procedure SetDomain(const AValue: String);
         procedure SetDomainEpsilon(const AValue: Double);
         procedure SetExpression(const AValue: string);
    @@ -115,7 +115,7 @@
         function IsEmpty: Boolean; override;
         procedure RequestParserUpdate; inline;
       published
    -    property DomainEpsilon: Double read FDomainEpsilon write SetDomainEpsilon;
    +    property DomainEpsilon: Double read GetDomainEpsilon write SetDomainEpsilon;
         property Params: TChartExprParams read FParams write SetParams;
         property Variable: String read FVariable write SetVariable;
         property Domain: String read FDomain write SetDomain;
    @@ -271,6 +271,7 @@
     begin
       FSeries := ASeries;
       FParser := ASeries.FParser;
    +  FEpsilon := DEFAULT_EPSILON;
     end;
     
     { Analyzes the parts of the domain expression and extract the intervals on
    @@ -290,10 +291,10 @@
         FParser.Expression := AParts[4];
         b := ArgToFloat(FParser.Evaluate);
         if (AParts[1][1] = '<') and (AParts[3][1] = '<') and (a < b) then
    -      ADomain.AddRange(a, b)
    +      ADomain.AddRange(a + FEpsilon, b - FEpsilon)
         else
         if (AParts[1][1] = '>') and (AParts[3][1] = '>') and (a > b) then
    -      ADomain.AddRange(b, a);
    +      ADomain.AddRange(b + FEpsilon, a - FEpsilon);
       end else
       // one-sided interval, variable is at left
       if (AParts[0] = Variable) and (AParts[3] = '') and (AParts[4] = '') then
    @@ -301,9 +302,9 @@
         FParser.Expression := AParts[2];
         a := ArgToFloat(FParser.Evaluate);
         case AParts[1] of
    -      '<>'      : AList.AddPoint(a);                    //  x <> a
    -      '<', '<=' : ADomain.AddRange(-Infinity, a);       //  x < a, x <= a
    -      '>', '>=' : ADomain.AddRange(a, Infinity);        //  x > a, x >= a
    +      '<>'      : AList.AddRange(a - FEpsilon, a + FEpsilon);   //  x <> a
    +      '<', '<=' : ADomain.AddRange(-Infinity, a - FEpsilon);    //  x < a, x <= a
    +      '>', '>=' : ADomain.AddRange(a + FEpsilon, Infinity);     //  x > a, x >= a
           else  Expressionerror;
         end;
       end else
    @@ -313,9 +314,9 @@
         FParser.Expression := AParts[0];
         a := ArgToFloat(FParser.Evaluate);
         case AParts[1] of
    -      '<>'      : AList.AddPoint(a);                    //  a <> x
    -      '<', '<=' : ADomain.AddRange(a, Infinity);        //  a < x, a <= x
    -      '>', '>=' : ADomain.AddRange(-Infinity, a);       //  a > x, a >= x
    +      '<>'      : AList.AddRange(a - FEpsilon, a + FEpsilon);   //  a <> x
    +      '<', '<=' : ADomain.AddRange(a + FEpsilon, Infinity);     //  a < x, a <= x
    +      '>', '>=' : ADomain.AddRange(-Infinity, a - FEpsilon);    //  a > x, a >= x
           else   ExpressionError;
         end;
       end else
    @@ -325,23 +326,10 @@
     { Converts the intervals in ADomain on which the function is defined to
       intervals in AList in which the function is NOT defined (= DomainExclusion) }
     procedure TChartDomainScanner.ConvertToExclusions(AList, ADomain: TIntervalList);
    -
    -  function IsPoint(i: Integer): Boolean;
    -  begin
    -    Result := (i >= 0) and (i < ADomain.IntervalCount) and
    -      (ADomain.Interval[i].FStart = ADomain.Interval[i].FEnd);
    -  end;
    -
    -type
    -  TIntervalPoint = record
    -    Value: Double;
    -    Contained: Boolean;
    -  end;
    -
     var
       a, b: Double;
       i, j: Integer;
    -  points: array of TIntervalPoint;
    +  points: array of Double;
     begin
       if ADomain.IntervalCount = 0 then
         exit;
    @@ -350,16 +338,12 @@
       SetLength(points, ADomain.IntervalCount*2);
     
       for i:=0 to ADomain.IntervalCount-1 do begin
    -    if IsPoint(i) then
    -      Continue;
         if ADomain.Interval[i].FStart <> -Infinity then begin
    -      points[j].Value := ADomain.Interval[i].FStart;
    -      points[j].Contained := IsPoint(i-1);
    +      points[j] := ADomain.Interval[i].FStart;
           inc(j);
         end;
         if ADomain.Interval[i].FEnd <> +Infinity then begin
    -      points[j].Value := ADomain.Interval[i].FEnd;
    -      points[j].Contained := IsPoint(i+1);
    +      points[j] := ADomain.Interval[i].FEnd;
           inc(j);
         end;
       end;
    @@ -376,25 +360,17 @@
       //                0        1      2
       begin
         a := -Infinity;
    -    b := points[0].Value;
    +    b := points[0];
         AList.AddRange(a, b);
    -    if not points[0].Contained then
    -      AList.AddPoint(b);
         j := 1;
       end;
       while j < Length(points) do begin
    -    a := points[j].Value;
    -    if not points[j].Contained then
    -      AList.AddPoint(a);
    -    if j = High(points) then begin
    -      AList.AddRange(a, Infinity);
    -    end else
    -    begin
    -      b := points[j+1].Value;
    -      AList.AddRange(a, b);
    -      if not points[j+1].Contained then
    -        AList.AddPoint(b);
    -    end;
    +    a := points[j];
    +    if j = High(points) then
    +      b := Infinity
    +    else
    +      b := points[j+1];
    +    AList.AddRange(a, b);
         inc(j, 2);
       end;
     end;
    @@ -418,8 +394,6 @@
       savedExpr := FParser.Expression;
       domains := TIntervalList.Create;
       try
    -    AList.Epsilon := FEpsilon;
    -    domains.Epsilon := FEpsilon;
         ParseExpression(AList, domains);
         ConvertToExclusions(AList, domains);
       finally
    @@ -500,7 +474,6 @@
       FX := FParser.Identifiers.AddFloatVariable(FVariable, 0.0);
     
       FDomainScanner := TChartDomainScanner.Create(self);
    -  FDomainEpsilon := DEFAULT_EPSILON;
     
       FParams := TChartExprParams.Create(FParser, @OnChangedHandler);
     end;
    @@ -577,9 +550,17 @@
       UpdateParentChart;
     end;
     
    +function TExpressionSeries.GetDomainEpsilon: Double;
    +begin
    +  Result := FDomainScanner.Epsilon;
    +end;
    +
     procedure TExpressionSeries.SetDomainEpsilon(const AValue: Double);
     begin
    -  FDomainScanner.Epsilon := AValue;
    +  if FDomainScanner.Epsilon = abs(AValue) then exit;
    +  FDomainScanner.Epsilon := abs(AValue);
    +  RequestParserUpdate;
    +  UpdateParentChart;
     end;
     
     procedure TExpressionSeries.SetExpression(const AValue: String);
    @@ -613,7 +594,6 @@
         FParser.Identifiers.AddFloatVariable(p.Name, p.Value);
       end;
     
    -  FDomainScanner.Epsilon := FDomainEpsilon;
       FDomainScanner.Expression := FDomain;
       FDomainScanner.ExtractDomainExclusions(DomainExclusions);
     
    Index: components/tachart/tafuncseries.pas
    ===================================================================
    --- components/tachart/tafuncseries.pas	(revision 60720)
    +++ components/tachart/tafuncseries.pas	(working copy)
    @@ -327,7 +327,7 @@
         procedure InvalidateFitResults; virtual;
         procedure Loaded; override;
         function PrepareFitParams: boolean;
    -    function PrepareIntervals: TIntervalList;
    +    function PrepareIntervals: TIntervalList; virtual;
         procedure SourceChanged(ASender: TObject); override;
       public
         procedure Assign(ASource: TPersistent); override;
    Index: components/tachart/test/SourcesTest.pas
    ===================================================================
    --- components/tachart/test/SourcesTest.pas	(revision 60720)
    +++ components/tachart/test/SourcesTest.pas	(working copy)
    @@ -450,8 +450,6 @@
     end;
     
     procedure TListSourceTest.Multi;
    -var
    -  L: TStrings;
     begin
       FSource.Clear;
       AssertEquals(1, FSource.YCount);
    Index: components/tachart/test/UtilsTest.pas
    ===================================================================
    --- components/tachart/test/UtilsTest.pas	(revision 60720)
    +++ components/tachart/test/UtilsTest.pas	(working copy)
    @@ -118,12 +118,6 @@
       r := 6.0;
       AssertTrue(FIList.Intersect(l, r, hint));
       AssertEquals(2.0, r);
    -  FIList.Epsilon := 0.1;
    -  l := 0.5;
    -  r := 2.5;
    -  AssertTrue(FIList.Intersect(l, r, hint));
    -  AssertEquals(0.9, l);
    -  AssertEquals(2.1, r);
     end;
     
     procedure TIntervalListTest.Merge;
    
    solution1.diff (11,526 bytes)
  • solution2.diff (14,785 bytes)
    Index: components/tachart/tachartutils.pas
    ===================================================================
    --- components/tachart/tachartutils.pas	(revision 60720)
    +++ components/tachart/tachartutils.pas	(working copy)
    @@ -127,7 +127,6 @@
         procedure Changed;
         function GetInterval(AIndex: Integer): TDoubleInterval;
         function GetIntervalCount: Integer;
    -    procedure SetEpsilon(AValue: Double);
         procedure SetOnChange(AValue: TNotifyEvent);
       public
         procedure Assign(ASource: TIntervalList);
    @@ -139,7 +138,7 @@
         function Intersect(
           var ALeft, ARight: Double; var AHint: Integer): Boolean;
       public
    -    property Epsilon: Double read FEpsilon write SetEpsilon;
    +    property Epsilon: Double read FEpsilon write FEpsilon;
         property Interval[AIndex: Integer]: TDoubleInterval read GetInterval;
         property IntervalCount: Integer read GetIntervalCount;
         property OnChange: TNotifyEvent read FOnChange write SetOnChange;
    @@ -710,6 +709,9 @@
       j: Integer;
       k: Integer;
     begin
    +  AStart -= FEpsilon;
    +  AEnd += FEpsilon;
    +  if AStart >= AEnd then exit;
       i := 0;
       while (i <= High(FIntervals)) and (FIntervals[i].FEnd < AStart) do
         i += 1;
    @@ -776,13 +778,13 @@
       if Length(FIntervals) = 0 then exit;
     
       AHint := EnsureRange(AHint, 0, High(FIntervals));
    -  while (AHint > 0) and (FIntervals[AHint].FStart > ARight) do
    +  while (AHint > 0) and (FIntervals[AHint].FStart >= ARight) do
         Dec(AHint);
     
       while
    -    (AHint <= High(FIntervals)) and (FIntervals[AHint].FStart <= ARight)
    +    (AHint <= High(FIntervals)) and (FIntervals[AHint].FStart < ARight)
       do begin
    -    if FIntervals[AHint].FEnd >= ALeft then begin
    +    if FIntervals[AHint].FEnd > ALeft then begin
           if not Result then fi := AHint;
           li := AHint;
           Result := true;
    @@ -791,20 +793,11 @@
       end;
     
       if Result then begin
    -    ALeft := FIntervals[fi].FStart - Epsilon;
    -    ARight := FIntervals[li].FEnd + Epsilon;
    +    ALeft := FIntervals[fi].FStart;
    +    ARight := FIntervals[li].FEnd;
       end;
     end;
     
    -procedure TIntervalList.SetEpsilon(AValue: Double);
    -begin
    -  if FEpsilon = AValue then exit;
    -  if AValue <= 0 then
    -    raise EChartIntervalError.Create('Epsilon <= 0');
    -  FEpsilon := AValue;
    -  Changed;
    -end;
    -
     procedure TIntervalList.SetOnChange(AValue: TNotifyEvent);
     begin
       if TMethod(FOnChange) = TMethod(AValue) then exit;
    Index: components/tachart/taexpressionseries.pas
    ===================================================================
    --- components/tachart/taexpressionseries.pas	(revision 60720)
    +++ components/tachart/taexpressionseries.pas	(working copy)
    @@ -89,7 +89,6 @@
       TExpressionSeries = class(TCustomFuncSeries)
       private
         FDomain: String;
    -    FDomainEpsilon: Double;
         FDomainScanner: TChartDomainScanner;
         FExpression: String;
         FParams: TChartExprParams;
    @@ -97,6 +96,7 @@
         FVariable: String;
         FX: TFPExprIdentifierDef;
         FDirty: Boolean;
    +    function GetDomainEpsilon: Double;
         procedure SetDomain(const AValue: String);
         procedure SetDomainEpsilon(const AValue: Double);
         procedure SetExpression(const AValue: string);
    @@ -115,7 +115,7 @@
         function IsEmpty: Boolean; override;
         procedure RequestParserUpdate; inline;
       published
    -    property DomainEpsilon: Double read FDomainEpsilon write SetDomainEpsilon;
    +    property DomainEpsilon: Double read GetDomainEpsilon write SetDomainEpsilon;
         property Params: TChartExprParams read FParams write SetParams;
         property Variable: String read FVariable write SetVariable;
         property Domain: String read FDomain write SetDomain;
    @@ -271,6 +271,7 @@
     begin
       FSeries := ASeries;
       FParser := ASeries.FParser;
    +  FEpsilon := DEFAULT_EPSILON;
     end;
     
     { Analyzes the parts of the domain expression and extract the intervals on
    @@ -280,68 +281,67 @@
     procedure TChartDomainScanner.Analyze(AList, ADomain: TIntervalList;
       const AParts: TDomainParts);
     var
    +  SaveListEpsilon, SaveDomainEpsilon: Double;
       a, b: Double;
     begin
    -  // two-sided interval, e.g. "0 < x <= 1", or "2 > x >= 1"
    -  if (AParts[2] = Variable) and (AParts[3] <> '') and (AParts[4] <> '') then
    -  begin
    -    FParser.Expression := AParts[0];
    -    a := ArgToFloat(FParser.Evaluate);
    -    FParser.Expression := AParts[4];
    -    b := ArgToFloat(FParser.Evaluate);
    -    if (AParts[1][1] = '<') and (AParts[3][1] = '<') and (a < b) then
    -      ADomain.AddRange(a, b)
    -    else
    -    if (AParts[1][1] = '>') and (AParts[3][1] = '>') and (a > b) then
    -      ADomain.AddRange(b, a);
    -  end else
    -  // one-sided interval, variable is at left
    -  if (AParts[0] = Variable) and (AParts[3] = '') and (AParts[4] = '') then
    -  begin
    -    FParser.Expression := AParts[2];
    -    a := ArgToFloat(FParser.Evaluate);
    -    case AParts[1] of
    -      '<>'      : AList.AddPoint(a);                    //  x <> a
    -      '<', '<=' : ADomain.AddRange(-Infinity, a);       //  x < a, x <= a
    -      '>', '>=' : ADomain.AddRange(a, Infinity);        //  x > a, x >= a
    -      else  Expressionerror;
    -    end;
    -  end else
    -  // one-sided interval, variable is at right
    -  if (AParts[2] = Variable) and (AParts[3] = '') and (AParts[4] = '') then
    -  begin
    -    FParser.Expression := AParts[0];
    -    a := ArgToFloat(FParser.Evaluate);
    -    case AParts[1] of
    -      '<>'      : AList.AddPoint(a);                    //  a <> x
    -      '<', '<=' : ADomain.AddRange(a, Infinity);        //  a < x, a <= x
    -      '>', '>=' : ADomain.AddRange(-Infinity, a);       //  a > x, a >= x
    -      else   ExpressionError;
    -    end;
    -  end else
    -    ExpressionError;
    +  SaveListEpsilon := AList.Epsilon;
    +  SaveDomainEpsilon := ADomain.Epsilon;
    +  try
    +    AList.Epsilon := FEpsilon; // list of excluded ranges should be widened by Epsilon
    +    ADomain.Epsilon := -FEpsilon; // list of included ranges should be narrowed by Epsilon
    +
    +    // two-sided interval, e.g. "0 < x <= 1", or "2 > x >= 1"
    +    if (AParts[2] = Variable) and (AParts[3] <> '') and (AParts[4] <> '') then
    +    begin
    +      FParser.Expression := AParts[0];
    +      a := ArgToFloat(FParser.Evaluate);
    +      FParser.Expression := AParts[4];
    +      b := ArgToFloat(FParser.Evaluate);
    +      if (AParts[1][1] = '<') and (AParts[3][1] = '<') and (a < b) then
    +        ADomain.AddRange(a, b)
    +      else
    +      if (AParts[1][1] = '>') and (AParts[3][1] = '>') and (a > b) then
    +        ADomain.AddRange(b, a);
    +    end else
    +    // one-sided interval, variable is at left
    +    if (AParts[0] = Variable) and (AParts[3] = '') and (AParts[4] = '') then
    +    begin
    +      FParser.Expression := AParts[2];
    +      a := ArgToFloat(FParser.Evaluate);
    +      case AParts[1] of
    +        '<>'      : AList.AddPoint(a);                    //  x <> a
    +        '<', '<=' : ADomain.AddRange(-Infinity, a);       //  x < a, x <= a
    +        '>', '>=' : ADomain.AddRange(a, Infinity);        //  x > a, x >= a
    +        else  Expressionerror;
    +      end;
    +    end else
    +    // one-sided interval, variable is at right
    +    if (AParts[2] = Variable) and (AParts[3] = '') and (AParts[4] = '') then
    +    begin
    +      FParser.Expression := AParts[0];
    +      a := ArgToFloat(FParser.Evaluate);
    +      case AParts[1] of
    +        '<>'      : AList.AddPoint(a);                    //  a <> x
    +        '<', '<=' : ADomain.AddRange(a, Infinity);        //  a < x, a <= x
    +        '>', '>=' : ADomain.AddRange(-Infinity, a);       //  a > x, a >= x
    +        else   ExpressionError;
    +      end;
    +    end else
    +      ExpressionError;
    +  finally
    +    AList.Epsilon := SaveListEpsilon;
    +    ADomain.Epsilon := SaveDomainEpsilon;
    +  end;
     end;
     
     { Converts the intervals in ADomain on which the function is defined to
       intervals in AList in which the function is NOT defined (= DomainExclusion) }
     procedure TChartDomainScanner.ConvertToExclusions(AList, ADomain: TIntervalList);
    -
    -  function IsPoint(i: Integer): Boolean;
    -  begin
    -    Result := (i >= 0) and (i < ADomain.IntervalCount) and
    -      (ADomain.Interval[i].FStart = ADomain.Interval[i].FEnd);
    -  end;
    -
    -type
    -  TIntervalPoint = record
    -    Value: Double;
    -    Contained: Boolean;
    -  end;
    -
     var
    +  SaveListEpsilon: Double;
       a, b: Double;
       i, j: Integer;
    -  points: array of TIntervalPoint;
    +  points: array of Double;
     begin
       if ADomain.IntervalCount = 0 then
         exit;
    @@ -350,52 +350,49 @@
       SetLength(points, ADomain.IntervalCount*2);
     
       for i:=0 to ADomain.IntervalCount-1 do begin
    -    if IsPoint(i) then
    -      Continue;
         if ADomain.Interval[i].FStart <> -Infinity then begin
    -      points[j].Value := ADomain.Interval[i].FStart;
    -      points[j].Contained := IsPoint(i-1);
    +      points[j] := ADomain.Interval[i].FStart;
           inc(j);
         end;
         if ADomain.Interval[i].FEnd <> +Infinity then begin
    -      points[j].Value := ADomain.Interval[i].FEnd;
    -      points[j].Contained := IsPoint(i+1);
    +      points[j] := ADomain.Interval[i].FEnd;
           inc(j);
         end;
       end;
       SetLength(points, j);
     
    -  // Case 1: domain extends to neg infinity
    -  // -INF <---------|xxxxxxxx|------|xxxx> INF     with - = allowed, x = forbidden
    -  //                0        1      2
    -  if ADomain.Interval[0].FStart = -Infinity then
    -    j := 0
    -  else
    -  // Case 2: domain begins at finite value
    -  // -INF <xxxxxxxxx|--------|xxxxxx|------>INF
    -  //                0        1      2
    -  begin
    -    a := -Infinity;
    -    b := points[0].Value;
    -    AList.AddRange(a, b);
    -    if not points[0].Contained then
    -      AList.AddPoint(b);
    -    j := 1;
    -  end;
    -  while j < Length(points) do begin
    -    a := points[j].Value;
    -    if not points[j].Contained then
    -      AList.AddPoint(a);
    -    if j = High(points) then begin
    -      AList.AddRange(a, Infinity);
    -    end else
    +  SaveListEpsilon := AList.Epsilon;
    +  try
    +    AList.Epsilon := 0; // provide direct ADomain to AList conversion - all the
    +                        // required epsilons have already been applied earlier,
    +                        // in the Analyze() call
    +
    +    // Case 1: domain extends to neg infinity
    +    // -INF <---------|xxxxxxxx|------|xxxx> INF     with - = allowed, x = forbidden
    +    //                0        1      2
    +    if ADomain.Interval[0].FStart = -Infinity then
    +      j := 0
    +    else
    +    // Case 2: domain begins at finite value
    +    // -INF <xxxxxxxxx|--------|xxxxxx|------>INF
    +    //                0        1      2
         begin
    -      b := points[j+1].Value;
    +      a := -Infinity;
    +      b := points[0];
           AList.AddRange(a, b);
    -      if not points[j+1].Contained then
    -        AList.AddPoint(b);
    +      j := 1;
         end;
    -    inc(j, 2);
    +    while j < Length(points) do begin
    +      a := points[j];
    +      if j = High(points) then
    +        b := Infinity
    +      else
    +        b := points[j+1];
    +      AList.AddRange(a, b);
    +      inc(j, 2);
    +    end;
    +  finally
    +    AList.Epsilon := SaveListEpsilon;
       end;
     end;
     
    @@ -418,8 +415,6 @@
       savedExpr := FParser.Expression;
       domains := TIntervalList.Create;
       try
    -    AList.Epsilon := FEpsilon;
    -    domains.Epsilon := FEpsilon;
         ParseExpression(AList, domains);
         ConvertToExclusions(AList, domains);
       finally
    @@ -500,7 +495,6 @@
       FX := FParser.Identifiers.AddFloatVariable(FVariable, 0.0);
     
       FDomainScanner := TChartDomainScanner.Create(self);
    -  FDomainEpsilon := DEFAULT_EPSILON;
     
       FParams := TChartExprParams.Create(FParser, @OnChangedHandler);
     end;
    @@ -577,9 +571,17 @@
       UpdateParentChart;
     end;
     
    +function TExpressionSeries.GetDomainEpsilon: Double;
    +begin
    +  Result := FDomainScanner.Epsilon;
    +end;
    +
     procedure TExpressionSeries.SetDomainEpsilon(const AValue: Double);
     begin
    -  FDomainScanner.Epsilon := AValue;
    +  if FDomainScanner.Epsilon = abs(AValue) then exit;
    +  FDomainScanner.Epsilon := abs(AValue);
    +  RequestParserUpdate;
    +  UpdateParentChart;
     end;
     
     procedure TExpressionSeries.SetExpression(const AValue: String);
    @@ -613,7 +615,6 @@
         FParser.Identifiers.AddFloatVariable(p.Name, p.Value);
       end;
     
    -  FDomainScanner.Epsilon := FDomainEpsilon;
       FDomainScanner.Expression := FDomain;
       FDomainScanner.ExtractDomainExclusions(DomainExclusions);
     
    Index: components/tachart/tafuncseries.pas
    ===================================================================
    --- components/tachart/tafuncseries.pas	(revision 60720)
    +++ components/tachart/tafuncseries.pas	(working copy)
    @@ -327,7 +327,7 @@
         procedure InvalidateFitResults; virtual;
         procedure Loaded; override;
         function PrepareFitParams: boolean;
    -    function PrepareIntervals: TIntervalList;
    +    function PrepareIntervals: TIntervalList; virtual;
         procedure SourceChanged(ASender: TObject); override;
       public
         procedure Assign(ASource: TPersistent); override;
    @@ -1315,6 +1315,7 @@
     begin
       FIntervals := TIntervalList.Create;
       try
    +    FIntervals.Epsilon := 0;
         if not (csoExtrapolateLeft in FOwner.Options) then
           FIntervals.AddRange(NegInfinity, FX[0]);
         if not (csoExtrapolateRight in FOwner.Options) then
    @@ -2156,6 +2157,7 @@
     
     function TFitSeries.PrepareIntervals: TIntervalList;
     var
    +  SaveEpsilon: Double;
       xmin, xmax: Double;
     begin
       Result := TIntervalList.Create;
    @@ -2162,8 +2164,12 @@
       try
         CalcXRange(xmin, xmax);
         if DrawFitRangeOnly then begin
    +      SaveEpsilon := Result.Epsilon;
    +      Result.Epsilon := 0;
           Result.AddRange(NegInfinity, xmin);
           Result.AddRange(xmax, SafeInfinity);
    +      Result.Epsilon := SaveEpsilon; // Result may by used by TFitSeries descendants,
    +                                     // so revert to the default Epsilon value
         end;
       except
         Result.Free;
    Index: components/tachart/test/SourcesTest.pas
    ===================================================================
    --- components/tachart/test/SourcesTest.pas	(revision 60720)
    +++ components/tachart/test/SourcesTest.pas	(working copy)
    @@ -450,8 +450,6 @@
     end;
     
     procedure TListSourceTest.Multi;
    -var
    -  L: TStrings;
     begin
       FSource.Clear;
       AssertEquals(1, FSource.YCount);
    Index: components/tachart/test/UtilsTest.pas
    ===================================================================
    --- components/tachart/test/UtilsTest.pas	(revision 60720)
    +++ components/tachart/test/UtilsTest.pas	(working copy)
    @@ -119,11 +119,19 @@
       AssertTrue(FIList.Intersect(l, r, hint));
       AssertEquals(2.0, r);
       FIList.Epsilon := 0.1;
    -  l := 0.5;
    -  r := 2.5;
    +  FIList.AddRange(101.0, 102.0);
    +  l := 100.5;
    +  r := 102.5;
       AssertTrue(FIList.Intersect(l, r, hint));
    -  AssertEquals(0.9, l);
    -  AssertEquals(2.1, r);
    +  AssertEquals(100.9, l);
    +  AssertEquals(102.1, r);
    +  FIList.Epsilon := -0.1;
    +  FIList.AddRange(201.0, 202.0);
    +  l := 200.5;
    +  r := 202.5;
    +  AssertTrue(FIList.Intersect(l, r, hint));
    +  AssertEquals(201.1, l);
    +  AssertEquals(201.9, r);
     end;
     
     procedure TIntervalListTest.Merge;
    
    solution2.diff (14,785 bytes)
  • Reproduce1.gif (12,674 bytes)
    Reproduce1.gif (12,674 bytes)
  • Reproduce2.png (5,686 bytes)
    Reproduce2.png (5,686 bytes)
  • Reproduce3.gif (11,154 bytes)
    Reproduce3.gif (11,154 bytes)
  • Reproduce4.png (4,617 bytes)
    Reproduce4.png (4,617 bytes)
  • Reproduce5.png (8,479 bytes)
    Reproduce5.png (8,479 bytes)
  • Reproduce6.gif (18,055 bytes)
    Reproduce6.gif (18,055 bytes)
  • Reproduce1verB.zip (2,703 bytes)
  • Reproduce2verB.zip (2,556 bytes)
  • Reproduce3verB.zip (2,662 bytes)
  • open_interval.zip (2,191 bytes)
  • open_interval.png (11,161 bytes)
    open_interval.png (11,161 bytes)
  • Epsilons1.zip (2,450 bytes)
  • Epsilons2.zip (2,395 bytes)
  • Epsilons3.zip (2,441 bytes)
  • solution2b.diff (16,881 bytes)
    Index: components/tachart/tachartutils.pas
    ===================================================================
    --- components/tachart/tachartutils.pas	(revision 60742)
    +++ components/tachart/tachartutils.pas	(working copy)
    @@ -101,6 +101,9 @@
         smsLabelPercentTotal, { Cars 12 % of 1234 }
         smsXValue);        { 21/6/1996 }
     
    +  TIntervalOption = (ioOpenStart, ioOpenEnd);
    +  TIntervalOptions = set of TIntervalOption;
    +
       TDoubleInterval = record
         FStart, FEnd: Double;
       end;
    @@ -122,14 +125,11 @@
       TIntervalList = class
       private
         FEpsilon: Double;
    -    FEpsilonScale: Double;
    -    FAbsoluteEpsilon: Double;
         FIntervals: array of TDoubleInterval;
         FOnChange: TNotifyEvent;
         procedure Changed;
         function GetInterval(AIndex: Integer): TDoubleInterval;
         function GetIntervalCount: Integer;
    -    procedure SetEpsilon(AValue: Double);
         procedure SetOnChange(AValue: TNotifyEvent);
       public
         procedure Assign(ASource: TIntervalList);
    @@ -136,12 +136,12 @@
         constructor Create;
       public
         procedure AddPoint(APoint: Double); inline;
    -    procedure AddRange(AStart, AEnd: Double);
    +    procedure AddRange(AStart, AEnd: Double; ALimits: TIntervalOptions = []);
         procedure Clear;
         function Intersect(
           var ALeft, ARight: Double; var AHint: Integer): Boolean;
       public
    -    property Epsilon: Double read FEpsilon write SetEpsilon;
    +    property Epsilon: Double read FEpsilon write FEpsilon;
         property Interval[AIndex: Integer]: TDoubleInterval read GetInterval;
         property IntervalCount: Integer read GetIntervalCount;
         property OnChange: TNotifyEvent read FOnChange write SetOnChange;
    @@ -706,12 +706,15 @@
       AddRange(APoint, APoint);
     end;
     
    -procedure TIntervalList.AddRange(AStart, AEnd: Double);
    +procedure TIntervalList.AddRange(AStart, AEnd: Double; ALimits: TIntervalOptions = []);
     var
       i: Integer;
       j: Integer;
       k: Integer;
     begin
    +  if not (ioOpenStart in ALimits) then AStart -= FEpsilon;
    +  if not (ioOpenEnd in ALimits) then AEnd += FEpsilon;
    +  if AStart > AEnd then exit;
       i := 0;
       while (i <= High(FIntervals)) and (FIntervals[i].FEnd < AStart) do
         i += 1;
    @@ -733,11 +736,6 @@
           FIntervals[k] := FIntervals[k - 1];
       end;
       FIntervals[i] := DoubleInterval(AStart, AEnd);
    -  if (abs(FIntervals[i].FStart) <> Infinity) and (abs(FIntervals[i].FStart) > FEpsilonScale) then
    -    FEpsilonScale := abs(FIntervals[i].FStart);
    -  if (abs(FIntervals[i].FEnd) <> Infinity) and (abs(FIntervals[i].FEnd) > FEpsilonScale) then
    -    FEpsilonScale := abs(FIntervals[i].FEnd);
    -  FAbsoluteEpsilon := IfThen(FEpsilonScale = 0, FEpsilon, FEpsilon * FEpsilonScale);
       Changed;
     end;
     
    @@ -762,7 +760,6 @@
     constructor TIntervalList.Create;
     begin
       FEpsilon := DEFAULT_EPSILON;
    -  FEpsilonScale := 0.0
     end;
     
     function TIntervalList.GetInterval(AIndex: Integer): TDoubleInterval;
    @@ -784,13 +781,13 @@
       if Length(FIntervals) = 0 then exit;
     
       AHint := EnsureRange(AHint, 0, High(FIntervals));
    -  while (AHint > 0) and (FIntervals[AHint].FStart - FAbsoluteEpsilon > ARight) do
    +  while (AHint > 0) and (FIntervals[AHint].FStart >= ARight) do
         Dec(AHint);
     
       while
    -    (AHint <= High(FIntervals)) and (FIntervals[AHint].FStart - FAbsoluteEpsilon <= ARight)
    +    (AHint <= High(FIntervals)) and (FIntervals[AHint].FStart < ARight)
       do begin
    -    if FIntervals[AHint].FEnd >= ALeft then begin
    +    if FIntervals[AHint].FEnd > ALeft then begin
           if not Result then fi := AHint;
           li := AHint;
           Result := true;
    @@ -799,24 +796,11 @@
       end;
     
       if Result then begin
    -    ALeft := FIntervals[fi].FStart - FAbsoluteEpsilon;
    -    ARight := FIntervals[li].FEnd + FAbsoluteEpsilon;
    +    ALeft := FIntervals[fi].FStart;
    +    ARight := FIntervals[li].FEnd;
       end;
     end;
     
    -procedure TIntervalList.SetEpsilon(AValue: Double);
    -begin
    -  if FEpsilon = AValue then exit;
    -  if AValue <= 0 then
    -    raise EChartIntervalError.Create('Epsilon <= 0');
    -  FEpsilon := AValue;
    -  if FEpsilonScale = 0 then
    -    FAbsoluteEpsilon := FEpsilon
    -  else
    -    FAbsoluteEpsilon := FEpsilon * FEpsilonScale;
    -  Changed;
    -end;
    -
     procedure TIntervalList.SetOnChange(AValue: TNotifyEvent);
     begin
       if TMethod(FOnChange) = TMethod(AValue) then exit;
    Index: components/tachart/taexpressionseries.pas
    ===================================================================
    --- components/tachart/taexpressionseries.pas	(revision 60742)
    +++ components/tachart/taexpressionseries.pas	(working copy)
    @@ -89,7 +89,6 @@
       TExpressionSeries = class(TCustomFuncSeries)
       private
         FDomain: String;
    -    FDomainEpsilon: Double;
         FDomainScanner: TChartDomainScanner;
         FExpression: String;
         FParams: TChartExprParams;
    @@ -97,6 +96,7 @@
         FVariable: String;
         FX: TFPExprIdentifierDef;
         FDirty: Boolean;
    +    function GetDomainEpsilon: Double;
         procedure SetDomain(const AValue: String);
         procedure SetDomainEpsilon(const AValue: Double);
         procedure SetExpression(const AValue: string);
    @@ -115,7 +115,7 @@
         function IsEmpty: Boolean; override;
         procedure RequestParserUpdate; inline;
       published
    -    property DomainEpsilon: Double read FDomainEpsilon write SetDomainEpsilon;
    +    property DomainEpsilon: Double read GetDomainEpsilon write SetDomainEpsilon;
         property Params: TChartExprParams read FParams write SetParams;
         property Variable: String read FVariable write SetVariable;
         property Domain: String read FDomain write SetDomain;
    @@ -271,6 +271,7 @@
     begin
       FSeries := ASeries;
       FParser := ASeries.FParser;
    +  FEpsilon := DEFAULT_EPSILON;
     end;
     
     { Analyzes the parts of the domain expression and extract the intervals on
    @@ -280,68 +281,67 @@
     procedure TChartDomainScanner.Analyze(AList, ADomain: TIntervalList;
       const AParts: TDomainParts);
     var
    +  SaveListEpsilon, SaveDomainEpsilon: Double;
       a, b: Double;
     begin
    -  // two-sided interval, e.g. "0 < x <= 1", or "2 > x >= 1"
    -  if (AParts[2] = Variable) and (AParts[3] <> '') and (AParts[4] <> '') then
    -  begin
    -    FParser.Expression := AParts[0];
    -    a := ArgToFloat(FParser.Evaluate);
    -    FParser.Expression := AParts[4];
    -    b := ArgToFloat(FParser.Evaluate);
    -    if (AParts[1][1] = '<') and (AParts[3][1] = '<') and (a < b) then
    -      ADomain.AddRange(a, b)
    -    else
    -    if (AParts[1][1] = '>') and (AParts[3][1] = '>') and (a > b) then
    -      ADomain.AddRange(b, a);
    -  end else
    -  // one-sided interval, variable is at left
    -  if (AParts[0] = Variable) and (AParts[3] = '') and (AParts[4] = '') then
    -  begin
    -    FParser.Expression := AParts[2];
    -    a := ArgToFloat(FParser.Evaluate);
    -    case AParts[1] of
    -      '<>'      : AList.AddPoint(a);                    //  x <> a
    -      '<', '<=' : ADomain.AddRange(-Infinity, a);       //  x < a, x <= a
    -      '>', '>=' : ADomain.AddRange(a, Infinity);        //  x > a, x >= a
    -      else  Expressionerror;
    -    end;
    -  end else
    -  // one-sided interval, variable is at right
    -  if (AParts[2] = Variable) and (AParts[3] = '') and (AParts[4] = '') then
    -  begin
    -    FParser.Expression := AParts[0];
    -    a := ArgToFloat(FParser.Evaluate);
    -    case AParts[1] of
    -      '<>'      : AList.AddPoint(a);                    //  a <> x
    -      '<', '<=' : ADomain.AddRange(a, Infinity);        //  a < x, a <= x
    -      '>', '>=' : ADomain.AddRange(-Infinity, a);       //  a > x, a >= x
    -      else   ExpressionError;
    -    end;
    -  end else
    -    ExpressionError;
    +  SaveListEpsilon := AList.Epsilon;
    +  SaveDomainEpsilon := ADomain.Epsilon;
    +  try
    +    AList.Epsilon := FEpsilon; // list of excluded ranges should be widened by Epsilon
    +    ADomain.Epsilon := -FEpsilon; // list of included ranges should be narrowed by Epsilon
    +
    +    // two-sided interval, e.g. "0 < x <= 1", or "2 > x >= 1"
    +    if (AParts[2] = Variable) and (AParts[3] <> '') and (AParts[4] <> '') then
    +    begin
    +      FParser.Expression := AParts[0];
    +      a := ArgToFloat(FParser.Evaluate);
    +      FParser.Expression := AParts[4];
    +      b := ArgToFloat(FParser.Evaluate);
    +      if (AParts[1][1] = '<') and (AParts[3][1] = '<') and (a < b) then
    +        ADomain.AddRange(a, b)
    +      else
    +      if (AParts[1][1] = '>') and (AParts[3][1] = '>') and (a > b) then
    +        ADomain.AddRange(b, a);
    +    end else
    +    // one-sided interval, variable is at left
    +    if (AParts[0] = Variable) and (AParts[3] = '') and (AParts[4] = '') then
    +    begin
    +      FParser.Expression := AParts[2];
    +      a := ArgToFloat(FParser.Evaluate);
    +      case AParts[1] of
    +        '<>'      : AList.AddPoint(a);                    //  x <> a
    +        '<', '<=' : ADomain.AddRange(-Infinity, a);       //  x < a, x <= a
    +        '>', '>=' : ADomain.AddRange(a, Infinity);        //  x > a, x >= a
    +        else  Expressionerror;
    +      end;
    +    end else
    +    // one-sided interval, variable is at right
    +    if (AParts[2] = Variable) and (AParts[3] = '') and (AParts[4] = '') then
    +    begin
    +      FParser.Expression := AParts[0];
    +      a := ArgToFloat(FParser.Evaluate);
    +      case AParts[1] of
    +        '<>'      : AList.AddPoint(a);                    //  a <> x
    +        '<', '<=' : ADomain.AddRange(a, Infinity);        //  a < x, a <= x
    +        '>', '>=' : ADomain.AddRange(-Infinity, a);       //  a > x, a >= x
    +        else   ExpressionError;
    +      end;
    +    end else
    +      ExpressionError;
    +  finally
    +    AList.Epsilon := SaveListEpsilon;
    +    ADomain.Epsilon := SaveDomainEpsilon;
    +  end;
     end;
     
     { Converts the intervals in ADomain on which the function is defined to
       intervals in AList in which the function is NOT defined (= DomainExclusion) }
     procedure TChartDomainScanner.ConvertToExclusions(AList, ADomain: TIntervalList);
    -
    -  function IsPoint(i: Integer): Boolean;
    -  begin
    -    Result := (i >= 0) and (i < ADomain.IntervalCount) and
    -      (ADomain.Interval[i].FStart = ADomain.Interval[i].FEnd);
    -  end;
    -
    -type
    -  TIntervalPoint = record
    -    Value: Double;
    -    Contained: Boolean;
    -  end;
    -
     var
    +  SaveListEpsilon: Double;
       a, b: Double;
       i, j: Integer;
    -  points: array of TIntervalPoint;
    +  points: array of Double;
     begin
       if ADomain.IntervalCount = 0 then
         exit;
    @@ -350,52 +350,49 @@
       SetLength(points, ADomain.IntervalCount*2);
     
       for i:=0 to ADomain.IntervalCount-1 do begin
    -    if IsPoint(i) then
    -      Continue;
         if ADomain.Interval[i].FStart <> -Infinity then begin
    -      points[j].Value := ADomain.Interval[i].FStart;
    -      points[j].Contained := IsPoint(i-1);
    +      points[j] := ADomain.Interval[i].FStart;
           inc(j);
         end;
         if ADomain.Interval[i].FEnd <> +Infinity then begin
    -      points[j].Value := ADomain.Interval[i].FEnd;
    -      points[j].Contained := IsPoint(i+1);
    +      points[j] := ADomain.Interval[i].FEnd;
           inc(j);
         end;
       end;
       SetLength(points, j);
     
    -  // Case 1: domain extends to neg infinity
    -  // -INF <---------|xxxxxxxx|------|xxxx> INF     with - = allowed, x = forbidden
    -  //                0        1      2
    -  if ADomain.Interval[0].FStart = -Infinity then
    -    j := 0
    -  else
    -  // Case 2: domain begins at finite value
    -  // -INF <xxxxxxxxx|--------|xxxxxx|------>INF
    -  //                0        1      2
    -  begin
    -    a := -Infinity;
    -    b := points[0].Value;
    -    AList.AddRange(a, b);
    -    if not points[0].Contained then
    -      AList.AddPoint(b);
    -    j := 1;
    -  end;
    -  while j < Length(points) do begin
    -    a := points[j].Value;
    -    if not points[j].Contained then
    -      AList.AddPoint(a);
    -    if j = High(points) then begin
    -      AList.AddRange(a, Infinity);
    -    end else
    +  SaveListEpsilon := AList.Epsilon;
    +  try
    +    AList.Epsilon := 0; // provide direct ADomain to AList conversion - all the
    +                        // required epsilons have already been applied earlier,
    +                        // in the Analyze() call
    +
    +    // Case 1: domain extends to neg infinity
    +    // -INF <---------|xxxxxxxx|------|xxxx> INF     with - = allowed, x = forbidden
    +    //                0        1      2
    +    if ADomain.Interval[0].FStart = -Infinity then
    +      j := 0
    +    else
    +    // Case 2: domain begins at finite value
    +    // -INF <xxxxxxxxx|--------|xxxxxx|------>INF
    +    //                0        1      2
         begin
    -      b := points[j+1].Value;
    +      a := -Infinity;
    +      b := points[0];
           AList.AddRange(a, b);
    -      if not points[j+1].Contained then
    -        AList.AddPoint(b);
    +      j := 1;
         end;
    -    inc(j, 2);
    +    while j < Length(points) do begin
    +      a := points[j];
    +      if j = High(points) then
    +        b := Infinity
    +      else
    +        b := points[j+1];
    +      AList.AddRange(a, b);
    +      inc(j, 2);
    +    end;
    +  finally
    +    AList.Epsilon := SaveListEpsilon;
       end;
     end;
     
    @@ -418,8 +415,6 @@
       savedExpr := FParser.Expression;
       domains := TIntervalList.Create;
       try
    -    AList.Epsilon := FEpsilon;
    -    domains.Epsilon := FEpsilon;
         ParseExpression(AList, domains);
         ConvertToExclusions(AList, domains);
       finally
    @@ -500,7 +495,6 @@
       FX := FParser.Identifiers.AddFloatVariable(FVariable, 0.0);
     
       FDomainScanner := TChartDomainScanner.Create(self);
    -  FDomainEpsilon := DEFAULT_EPSILON;
     
       FParams := TChartExprParams.Create(FParser, @OnChangedHandler);
     end;
    @@ -577,9 +571,17 @@
       UpdateParentChart;
     end;
     
    +function TExpressionSeries.GetDomainEpsilon: Double;
    +begin
    +  Result := FDomainScanner.Epsilon;
    +end;
    +
     procedure TExpressionSeries.SetDomainEpsilon(const AValue: Double);
     begin
    -  FDomainScanner.Epsilon := AValue;
    +  if FDomainScanner.Epsilon = abs(AValue) then exit;
    +  FDomainScanner.Epsilon := abs(AValue);
    +  RequestParserUpdate;
    +  UpdateParentChart;
     end;
     
     procedure TExpressionSeries.SetExpression(const AValue: String);
    @@ -613,7 +615,6 @@
         FParser.Identifiers.AddFloatVariable(p.Name, p.Value);
       end;
     
    -  FDomainScanner.Epsilon := FDomainEpsilon;
       FDomainScanner.Expression := FDomain;
       FDomainScanner.ExtractDomainExclusions(DomainExclusions);
     
    Index: components/tachart/tafuncseries.pas
    ===================================================================
    --- components/tachart/tafuncseries.pas	(revision 60742)
    +++ components/tachart/tafuncseries.pas	(working copy)
    @@ -327,7 +327,7 @@
         procedure InvalidateFitResults; virtual;
         procedure Loaded; override;
         function PrepareFitParams: boolean;
    -    function PrepareIntervals: TIntervalList;
    +    function PrepareIntervals: TIntervalList; virtual;
         procedure SourceChanged(ASender: TObject); override;
       public
         procedure Assign(ASource: TPersistent); override;
    @@ -1316,9 +1316,9 @@
       FIntervals := TIntervalList.Create;
       try
         if not (csoExtrapolateLeft in FOwner.Options) then
    -      FIntervals.AddRange(NegInfinity, FX[0]);
    +      FIntervals.AddRange(NegInfinity, FX[0], [ioOpenStart, ioOpenEnd]);
         if not (csoExtrapolateRight in FOwner.Options) then
    -      FIntervals.AddRange(FX[High(FX)], SafeInfinity);
    +      FIntervals.AddRange(FX[High(FX)], SafeInfinity, [ioOpenStart, ioOpenEnd]);
       except
         FreeAndNil(FIntervals);
         raise;
    @@ -2162,8 +2162,8 @@
       try
         CalcXRange(xmin, xmax);
         if DrawFitRangeOnly then begin
    -      Result.AddRange(NegInfinity, xmin);
    -      Result.AddRange(xmax, SafeInfinity);
    +      Result.AddRange(NegInfinity, xmin, [ioOpenStart, ioOpenEnd]);
    +      Result.AddRange(xmax, SafeInfinity, [ioOpenStart, ioOpenEnd]);
         end;
       except
         Result.Free;
    Index: components/tachart/test/UtilsTest.pas
    ===================================================================
    --- components/tachart/test/UtilsTest.pas	(revision 60742)
    +++ components/tachart/test/UtilsTest.pas	(working copy)
    @@ -118,12 +118,39 @@
       r := 6.0;
       AssertTrue(FIList.Intersect(l, r, hint));
       AssertEquals(2.0, r);
    -  FIList.Epsilon := 0.1;  // Meaning 10% of max exclusion edge, i.e. 0.2
    -  l := 0.5;
    -  r := 2.5;
    +  FIList.Epsilon := 0.1;
    +  FIList.AddRange(101.0, 102.0);
    +  l := 100.5;
    +  r := 102.5;
       AssertTrue(FIList.Intersect(l, r, hint));
    -  AssertEquals(0.8, l);
    -  AssertEquals(2.2, r);
    +  AssertEquals(100.9, l);
    +  AssertEquals(102.1, r);
    +  FIList.Epsilon := -0.1;
    +  FIList.AddRange(201.0, 202.0);
    +  l := 200.5;
    +  r := 202.5;
    +  AssertTrue(FIList.Intersect(l, r, hint));
    +  AssertEquals(201.1, l);
    +  AssertEquals(201.9, r);
    +  FIList.Epsilon := 0.1;
    +  FIList.AddRange(301.0, 302.0, [ioOpenStart]);
    +  l := 300.5;
    +  r := 302.5;
    +  AssertTrue(FIList.Intersect(l, r, hint));
    +  AssertEquals(301.0, l);
    +  AssertEquals(302.1, r);
    +  FIList.AddRange(401.0, 402.0, [ioOpenEnd]);
    +  l := 400.5;
    +  r := 402.5;
    +  AssertTrue(FIList.Intersect(l, r, hint));
    +  AssertEquals(400.9, l);
    +  AssertEquals(402.0, r);
    +  FIList.AddRange(501.0, 502.0, [ioOpenStart, ioOpenEnd]);
    +  l := 500.5;
    +  r := 502.5;
    +  AssertTrue(FIList.Intersect(l, r, hint));
    +  AssertEquals(501.0, l);
    +  AssertEquals(502.0, r);
     end;
     
     procedure TIntervalListTest.Merge;
    
    solution2b.diff (16,881 bytes)

Activities

Marcin Wiazowski

2019-03-19 22:24

reporter   ~0114931

EXPLANATION 1:

Regions to be excluded include their bounds. For example, when we define excluded region 1.15 .. 1.25, values 1.15 and 1.25 belong to this region - so calling Intersect(1.25, 1.29) returns True.

Now take a look at the Algorithm.png and let's try the following (Epsilon = 0.02, Delta = 0.04):

  ALeft := 1.12
  ARight := ALeft+Delta = 1.16

  Intersect(ALeft, ARight) -> True -> so, after the call, we get:

  ALeft = RangeLo-Epsilon = 1.15 - 0.02 = 1.13
  ARight = RangeHi+Epsilon = 1.25 + 0.02 = 1.27

  This means that we should finish drawing the current line at X = 1.13, and then start drawing a new line at X = 1.27.

At the next loop iteration, we have:

  ALeft := ARight = 1.27
  ARight := ALeft+Delta = 1.31

  Intersect(ALeft, ARight) -> False

At the next loop iteration, we have:

  ALeft := ARight = 1.31
  ARight := ALeft+Delta = 1.35

  Intersect(ALeft, ARight) -> False

----

Now let's imagine, that Epsilon is set to 0:
  
  ALeft := 1.12
  ARight := ALeft+Delta = 1.16

  Intersect(ALeft, ARight) -> True -> so, after the call, we get:

  ALeft = RangeLo-Epsilon = 1.15 - 0 = 1.15
  ARight = RangeHi+Epsilon = 1.25 + 0 = 1.25

  This means that we should finish drawing the current line at X = 1.15, and then start drawing a new line at X = 1.25.

At the next loop iteration, we have:

  ALeft := ARight = 1.25
  ARight := ALeft+Delta = 1.29

  Intersect(ALeft, ARight) -> True -> so, after the call, we get:

  ALeft = RangeLo-Epsilon = 1.15 - 0 = 1.15
  ARight = RangeHi+Epsilon = 1.25 + 0 = 1.25 (once again)

At the next loop iteration, we have:

  ALeft := ARight = 1.25
  ARight := ALeft+Delta = 1.29

  Intersect(ALeft, ARight) -> True -> so, after the call, we get:

  ALeft = RangeLo-Epsilon = 1.15 - 0 = 1.15
  ARight = RangeHi+Epsilon = 1.25 + 0 = 1.25 (once again)
  
As we can see, we are trapped in an infinite loop now.

----

But, in the Reproduce1 application, Epsilon is not set 0, but has its default value 1E-6 instead, so how is this possible to stuck in an infinite loop?

Reproduce1 uses two excluded ranges, that are initialized in TCubicSplineSeries.TSpline.PrepareIntervals(): -INF .. FirstPointX and LastPointX .. +INF. After clicking the button 4 times, first data point's X becomes -1E15. In this case, we have:

  First excluded range is: -INF .. -1E15

  ALeft := -1E15
  ARight := ...

  Intersect(ALeft, ARight) -> True -> so, after the call, we get:

  ALeft = RangeLo-Epsilon = -INF - 1E-6
  ARight = RangeHi+Epsilon = -1E15 + 1E-6

The problem is in fact that: -1E15 + 1E-6 = -1000000000000000 + 0.000001 = -999999999999999,999999

But we operate on Double values, which can hold only up to 16 decimal digits, so finally we have: -999999999999999,999999 = -1000000000000000, which means that RangeHi + Epsilon = RangeHi (which is exactly as for Epsilon set to 0):

  ARight = RangeHi+Epsilon = -1E15 + 1E-6 = -1E15

At the next loop iteration, we have:

  ALeft := ARight = -1E15
  ARight := ...

  Intersect(ALeft, ARight) -> True -> so, after the call, we get:

  ALeft = ...
  ARight = RangeHi+Epsilon = -1E15 + 1E-6 = -1E15 (once again)

At the next loop iteration, we have:

  ALeft := ARight = -1E15
  ARight := ...

  Intersect(ALeft, ARight) -> True -> so, after the call, we get:

  ALeft = ...
  ARight = RangeHi+Epsilon = -1E15 + 1E-6 = -1E15 (once again)

So, in this case, Epsilon = 1E-6 is so small, that it behaves like Epsilon set to 0 - so the application hangs forever.




EXPLANATION 2:

In this case, the first excluded range is -INF .. -4E-6, and Epsilon has its default value 1E-6. So we have:

  First excluded range is: -INF .. -4E-6

  ALeft := -4E-6
  ARight := ...

  Intersect(ALeft, ARight) -> True -> so, after the call, we get:

  ALeft = RangeLo-Epsilon = -INF - 1E-6
  ARight = RangeHi+Epsilon = -4E-6 + 1E-6 = -3E-6

So drawing the line starts at X = -3E-6, but, in this case, -3E-6 is in the middle between the first (X = -4E-6) and second (X = -2E-6) data point, so there is a large gap between the first data point and the beginning of the series line.




EXPLANATION 3:

Epsilon has its default value 1E-6. After clicking the button 3 times, first data point's X becomes -1E-9, and last data point's X becomes 1E-9. So we have:

  ALeft := -1E-9
  ARight := ...

  Intersect(ALeft, ARight) -> True -> so, after the call, we get:

  ALeft = RangeLo-Epsilon = -INF - 1E-6
  ARight = RangeHi+Epsilon = -1E-9 + 1E-6 = 999E-9

So drawing the line starts at X = 999E-9, but the last point's X is 1E-9, so, in fact, drawing starts far above the chart's end...




EXPLANATION 4:

The problem occurs, because Epsilon is set to so large value, that causes drawing the series line in the reverse direction. This can be explained by using the following example:

Let's assume, that the current X is 1.12. Now try the following (Epsilon = 0.05, Delta = 0.04):

  ALeft := 1.12
  ARight := ALeft+Delta = 1.16

  Intersect(ALeft, ARight) -> True -> so, after the call, we get:

  ALeft = RangeLo-Epsilon = 1.15 - 0.05 = 1.1
  ARight = RangeHi+Epsilon = 1.25 + 0.05 = 1.3

  This means that we should finish drawing the current line at X = 1.1, and then start drawing a new line at X = 1.3.

As can be seen, our previous point was X = 1.12, and the point, where the line should be finished, is X = 1.1 - so we draw the line in the reverse direction.




EXPLANATION 5:

Currently, Epsilon can't be set to 0, because this would cause an infinite loop, as described in EXPLANATION 1.




EXPLANATION 6:

A nature of the problem is rather obvious.




For additional notices, see below.

Marcin Wiazowski

2019-03-19 22:24

reporter   ~0114932

Let's make now some observation: Epsilon plays two roles, which are:

ROLE 1: Provides additional space around each excluded range and point

ROLE 2: By having non-zero values, prevents from stucking in an infinite loop when calling Intersect() - see the EXPLANATION 1 for more details (the example with Epsilon set to 0).




To exclude some range, we need to call TIntervalList.AddRange(). To exclude a single point, we need to call TIntervalList.AddPoint() - which, in fact, creates a range having same left and right bound:

  procedure TIntervalList.AddPoint(APoint: Double);
  begin
    AddRange(APoint, APoint);
  end;




As already mentioned above, excluded range contains its bounds. The intention was probably to allow excluding single points - for example, when excluding a [10 .. 10] range, only the point X = 10 is excluded.

But, in fact, in the current implementation, it's impossible to exclude a single point - we always exclude the point along with its additional -Epsilon .. +Epsilon range (where Epsilon is always non-zero). This means, that single points on the exclusion list never exist: although they can be added by calling AddPoint(), they are internally handled as X-Epsilon .. X+Epsilon ranges.

Thanks to this observation, we can stop supporting single points in the exclusion list - i.e. we can remove range's bounds from the range itself, without any functionality loss - this automatically solves PROBLEM 1, and also leads to solving PROBLEM 5.




For possible solutions, see below.

Marcin Wiazowski

2019-03-19 22:24

reporter   ~0114933

SOLUTION 1: Remove TIntervalList.Epsilon completely and fix TExpressionSeries.DomainEpsilon.

Details:

a) range's bounds are no more included in the range itself, so hanging in a loop with Intersect() calls is no more possible

b) thanks to that, TIntervalList.Intersect() no longer needs to enlarge returned ranges by -Epsilon / +Epsilon (Intersect() should behave like for Epsilon = 0)

c) instead, the user is required to subtract/add needed epsilons directly in AddRange() calls

d) since Epsilon is effectively used only in TIntervalList.Intersect(), is becomes useless and can be completely removed

e) TIntervalList.AddPoint() should get an additional, optional parameter, and should be made deprecated:

  procedure TIntervalList.AddPoint(APoint: Double; AEpsilon: Double = 1e-6); deprecated 'Use AddRange instead';
  begin
    AEpsilon := abs(AEpsilon);
    AddRange(APoint - AEpsilon, APoint + AEpsilon);
  end;

f) TIntervalList.AddRange(AStart, AEnd) call should verify the received ranges:

  procedure TIntervalList.AddRange(AStart, AEnd: Double);
  begin
    if AStart >= AEnd then exit;
    ...


Summary:

- Problem 1: solved
- Problem 2: solved
- Problem 3: solved
- Problem 4: solved - requires calling "AddPoint(0, 0.3)" in the code
- Problem 5: outdated
- Problem 6: solved


Consequences / Disadvantages:

- The user should use AddRange() calls instead of AddPoint() calls, thus clearly giving the range that is to be excluded.

- The user is required to subtract/add needed epsilons directly in AddRange() calls.


Disadvantages:

- TIntervalList.Epsilon no longer exists - so changes to the already existing code may be required. However, due to PROBLEM 4 (drawing line in the reverse order for too large Epsilon values), changing the Epsilon value had limited usefulness, so probably nobody changed the default Epsilon value (i.e. used the Epsilon property in the code).


Advantages:

- Implementing this solution allows setting TExpressionSeries.DomainEpsilon - in particular - to 0, which may be useful. For example, it's useful to set DomainEpsilon to some non-zero value when using Domain = 'x <> 0', but it's useful to set DomainEpsilon to 0 when using many exclusion ranges of different width, like Domain = 'x < 3 ; 3.1 < x < 100 ; 110 < x < 300 ; x > 350'.

- Some other problems in TChartDomainScanner.Analyze() and TChartDomainScanner.ConvertToExclusions() can now be solved, as described below:

  TChartDomainScanner.Analyze() and TChartDomainScanner.ConvertToExclusions() use two interval list:
  - first is for domain EXCLUSIONS (named AList)
  - second is for domain INCLUSIONS (named ADomain)

  In TChartDomainScanner.Analyze(): since TIntervalList.Epsilon has been removed, epsilons must be applied directly in AddRange() calls:
  - EXCLUDED ranges (AList) should be WIDENED by FEpsilon: AddRange(X1 - FEpsilon, X2 + FEpsilon)
  - so, inversely, INCLUDED ranges (ADomain) should be NARROWED by FEpsilon: AddRange(X1 + FEpsilon, X2 - FEpsilon)

  In TChartDomainScanner.ConvertToExclusions():
  - because adding a single point is no longer needed or working, all the single-point operations have been removed
  - no epsilons should be applied in ConvertToExclusions(), because all the needed epsilons have already been applied earlier, in the Analyze() call - so only a simple conversion from ADomain to AList should be performed






SOLUTION 2: Fix TIntervalList.Epsilon and fix TExpressionSeries.DomainEpsilon.

Details:

a) range's bounds are no more included in the range itself, so hanging in a loop with Intersect() calls is no more possible

b) thanks to that, TIntervalList.Intersect() no longer needs - or should - enlarge the returned range by -Epsilon / +Epsilon (should behave like for Epsilon = 0)

c) instead, epsilons should be applied at the beginning of the AddRange() call:

  procedure TIntervalList.AddRange(AStart, AEnd: Double);
  begin
    AStart -= FEpsilon;
    AEnd += FEpsilon;
    if AStart >= AEnd then exit;
    ...

d) TIntervalList.Epsilon can be now positive, zero or negative (negative values are useful for narrowing ranges - as for ADomain described above; zero value is useful when solving PROBLEM 2)

e) changing Epsilon no longer needs calling the "Changed" method, because the new value is applied only to ranges added after the change - but not to ranges already existing


Patch for TChartDomainScanner.Analyze() and TChartDomainScanner.ConvertToExclusions() works in the same way as in SOLUTION 1, but - instead of adding epsilons in each AddRange() call - epsilons are applied by using AList.Epsilon and ADomain.Epsilon properties.


Summary:

- Problem 1: solved
- Problem 2: solved
- Problem 3: solved
- Problem 4: solved
- Problem 5: solved
- Problem 6: solved


Advantages:

- Full functional compatibility is retained - no changes to the already existing code are required (the only requirement is: Epsilon must be set BEFORE calling AddPoint() or AddRange())





SUMMARY:

The attached solution1.diff and solution2.diff implement fixes described above.

Solution 1 has minor incompatibility.

Solution 2 is fully compatible (the only requirement is: Epsilon must be set BEFORE calling AddPoint() or AddRange()). Additionally, fixed TChartDomainScanner.Analyze() code is much simpler when using Solution 2 instead of Solution 1.

So Solution 2 is better.



Additional note: both patches add "virtual" to the protected TFitSeries.PrepareIntervals() declaration. This is because PrepareIntervals() is called only internally, and prepared intervals are then immediately freed. Because of this, standalone calls to PrepareIntervals() in TFitSeries' descendants are useless - but overriding is useful, since it allows modifying the just-created intervals before they are used by TFitSeries internals.

Marcin Wiazowski

2019-03-19 22:25

reporter  

Algorithm.png (5,008 bytes)
Algorithm.png (5,008 bytes)

Marcin Wiazowski

2019-03-19 22:26

reporter  

Reproduce1.zip (2,632 bytes)

Marcin Wiazowski

2019-03-19 22:26

reporter  

Reproduce2.zip (2,499 bytes)

Marcin Wiazowski

2019-03-19 22:26

reporter  

Reproduce3.zip (2,634 bytes)

Marcin Wiazowski

2019-03-19 22:26

reporter  

Reproduce4.zip (2,404 bytes)

Marcin Wiazowski

2019-03-19 22:26

reporter  

Reproduce5.zip (2,453 bytes)

Marcin Wiazowski

2019-03-19 22:27

reporter  

Reproduce6.zip (2,331 bytes)

Marcin Wiazowski

2019-03-19 22:27

reporter  

solution1.diff (11,526 bytes)
Index: components/tachart/tachartutils.pas
===================================================================
--- components/tachart/tachartutils.pas	(revision 60720)
+++ components/tachart/tachartutils.pas	(working copy)
@@ -121,25 +121,21 @@
 
   TIntervalList = class
   private
-    FEpsilon: Double;
     FIntervals: array of TDoubleInterval;
     FOnChange: TNotifyEvent;
     procedure Changed;
     function GetInterval(AIndex: Integer): TDoubleInterval;
     function GetIntervalCount: Integer;
-    procedure SetEpsilon(AValue: Double);
     procedure SetOnChange(AValue: TNotifyEvent);
   public
     procedure Assign(ASource: TIntervalList);
-    constructor Create;
   public
-    procedure AddPoint(APoint: Double); inline;
+    procedure AddPoint(APoint: Double; AEpsilon: Double = 1e-6);
     procedure AddRange(AStart, AEnd: Double);
     procedure Clear;
     function Intersect(
       var ALeft, ARight: Double; var AHint: Integer): Boolean;
   public
-    property Epsilon: Double read FEpsilon write SetEpsilon;
     property Interval[AIndex: Integer]: TDoubleInterval read GetInterval;
     property IntervalCount: Integer read GetIntervalCount;
     property OnChange: TNotifyEvent read FOnChange write SetOnChange;
@@ -699,9 +695,10 @@
 
 { TIntervalList }
 
-procedure TIntervalList.AddPoint(APoint: Double); inline;
+procedure TIntervalList.AddPoint(APoint: Double; AEpsilon: Double = 1e-6); deprecated 'Use AddRange instead';
 begin
-  AddRange(APoint, APoint);
+  AEpsilon := abs(AEpsilon);
+  AddRange(APoint - AEpsilon, APoint + AEpsilon);
 end;
 
 procedure TIntervalList.AddRange(AStart, AEnd: Double);
@@ -710,6 +707,7 @@
   j: Integer;
   k: Integer;
 begin
+  if AStart >= AEnd then exit;
   i := 0;
   while (i <= High(FIntervals)) and (FIntervals[i].FEnd < AStart) do
     i += 1;
@@ -736,7 +734,6 @@
 
 procedure TIntervalList.Assign(ASource: TIntervalList);
 begin
-  FEpsilon := ASource.FEpsilon;
   FIntervals := Copy(ASource.FIntervals);
 end;
 
@@ -752,11 +749,6 @@
   Changed;
 end;
 
-constructor TIntervalList.Create;
-begin
-  FEpsilon := DEFAULT_EPSILON;
-end;
-
 function TIntervalList.GetInterval(AIndex: Integer): TDoubleInterval;
 begin
   Result := FIntervals[AIndex];
@@ -776,13 +768,13 @@
   if Length(FIntervals) = 0 then exit;
 
   AHint := EnsureRange(AHint, 0, High(FIntervals));
-  while (AHint > 0) and (FIntervals[AHint].FStart > ARight) do
+  while (AHint > 0) and (FIntervals[AHint].FStart >= ARight) do
     Dec(AHint);
 
   while
-    (AHint <= High(FIntervals)) and (FIntervals[AHint].FStart <= ARight)
+    (AHint <= High(FIntervals)) and (FIntervals[AHint].FStart < ARight)
   do begin
-    if FIntervals[AHint].FEnd >= ALeft then begin
+    if FIntervals[AHint].FEnd > ALeft then begin
       if not Result then fi := AHint;
       li := AHint;
       Result := true;
@@ -791,20 +783,11 @@
   end;
 
   if Result then begin
-    ALeft := FIntervals[fi].FStart - Epsilon;
-    ARight := FIntervals[li].FEnd + Epsilon;
+    ALeft := FIntervals[fi].FStart;
+    ARight := FIntervals[li].FEnd;
   end;
 end;
 
-procedure TIntervalList.SetEpsilon(AValue: Double);
-begin
-  if FEpsilon = AValue then exit;
-  if AValue <= 0 then
-    raise EChartIntervalError.Create('Epsilon <= 0');
-  FEpsilon := AValue;
-  Changed;
-end;
-
 procedure TIntervalList.SetOnChange(AValue: TNotifyEvent);
 begin
   if TMethod(FOnChange) = TMethod(AValue) then exit;
Index: components/tachart/taexpressionseries.pas
===================================================================
--- components/tachart/taexpressionseries.pas	(revision 60720)
+++ components/tachart/taexpressionseries.pas	(working copy)
@@ -89,7 +89,6 @@
   TExpressionSeries = class(TCustomFuncSeries)
   private
     FDomain: String;
-    FDomainEpsilon: Double;
     FDomainScanner: TChartDomainScanner;
     FExpression: String;
     FParams: TChartExprParams;
@@ -97,6 +96,7 @@
     FVariable: String;
     FX: TFPExprIdentifierDef;
     FDirty: Boolean;
+    function GetDomainEpsilon: Double;
     procedure SetDomain(const AValue: String);
     procedure SetDomainEpsilon(const AValue: Double);
     procedure SetExpression(const AValue: string);
@@ -115,7 +115,7 @@
     function IsEmpty: Boolean; override;
     procedure RequestParserUpdate; inline;
   published
-    property DomainEpsilon: Double read FDomainEpsilon write SetDomainEpsilon;
+    property DomainEpsilon: Double read GetDomainEpsilon write SetDomainEpsilon;
     property Params: TChartExprParams read FParams write SetParams;
     property Variable: String read FVariable write SetVariable;
     property Domain: String read FDomain write SetDomain;
@@ -271,6 +271,7 @@
 begin
   FSeries := ASeries;
   FParser := ASeries.FParser;
+  FEpsilon := DEFAULT_EPSILON;
 end;
 
 { Analyzes the parts of the domain expression and extract the intervals on
@@ -290,10 +291,10 @@
     FParser.Expression := AParts[4];
     b := ArgToFloat(FParser.Evaluate);
     if (AParts[1][1] = '<') and (AParts[3][1] = '<') and (a < b) then
-      ADomain.AddRange(a, b)
+      ADomain.AddRange(a + FEpsilon, b - FEpsilon)
     else
     if (AParts[1][1] = '>') and (AParts[3][1] = '>') and (a > b) then
-      ADomain.AddRange(b, a);
+      ADomain.AddRange(b + FEpsilon, a - FEpsilon);
   end else
   // one-sided interval, variable is at left
   if (AParts[0] = Variable) and (AParts[3] = '') and (AParts[4] = '') then
@@ -301,9 +302,9 @@
     FParser.Expression := AParts[2];
     a := ArgToFloat(FParser.Evaluate);
     case AParts[1] of
-      '<>'      : AList.AddPoint(a);                    //  x <> a
-      '<', '<=' : ADomain.AddRange(-Infinity, a);       //  x < a, x <= a
-      '>', '>=' : ADomain.AddRange(a, Infinity);        //  x > a, x >= a
+      '<>'      : AList.AddRange(a - FEpsilon, a + FEpsilon);   //  x <> a
+      '<', '<=' : ADomain.AddRange(-Infinity, a - FEpsilon);    //  x < a, x <= a
+      '>', '>=' : ADomain.AddRange(a + FEpsilon, Infinity);     //  x > a, x >= a
       else  Expressionerror;
     end;
   end else
@@ -313,9 +314,9 @@
     FParser.Expression := AParts[0];
     a := ArgToFloat(FParser.Evaluate);
     case AParts[1] of
-      '<>'      : AList.AddPoint(a);                    //  a <> x
-      '<', '<=' : ADomain.AddRange(a, Infinity);        //  a < x, a <= x
-      '>', '>=' : ADomain.AddRange(-Infinity, a);       //  a > x, a >= x
+      '<>'      : AList.AddRange(a - FEpsilon, a + FEpsilon);   //  a <> x
+      '<', '<=' : ADomain.AddRange(a + FEpsilon, Infinity);     //  a < x, a <= x
+      '>', '>=' : ADomain.AddRange(-Infinity, a - FEpsilon);    //  a > x, a >= x
       else   ExpressionError;
     end;
   end else
@@ -325,23 +326,10 @@
 { Converts the intervals in ADomain on which the function is defined to
   intervals in AList in which the function is NOT defined (= DomainExclusion) }
 procedure TChartDomainScanner.ConvertToExclusions(AList, ADomain: TIntervalList);
-
-  function IsPoint(i: Integer): Boolean;
-  begin
-    Result := (i >= 0) and (i < ADomain.IntervalCount) and
-      (ADomain.Interval[i].FStart = ADomain.Interval[i].FEnd);
-  end;
-
-type
-  TIntervalPoint = record
-    Value: Double;
-    Contained: Boolean;
-  end;
-
 var
   a, b: Double;
   i, j: Integer;
-  points: array of TIntervalPoint;
+  points: array of Double;
 begin
   if ADomain.IntervalCount = 0 then
     exit;
@@ -350,16 +338,12 @@
   SetLength(points, ADomain.IntervalCount*2);
 
   for i:=0 to ADomain.IntervalCount-1 do begin
-    if IsPoint(i) then
-      Continue;
     if ADomain.Interval[i].FStart <> -Infinity then begin
-      points[j].Value := ADomain.Interval[i].FStart;
-      points[j].Contained := IsPoint(i-1);
+      points[j] := ADomain.Interval[i].FStart;
       inc(j);
     end;
     if ADomain.Interval[i].FEnd <> +Infinity then begin
-      points[j].Value := ADomain.Interval[i].FEnd;
-      points[j].Contained := IsPoint(i+1);
+      points[j] := ADomain.Interval[i].FEnd;
       inc(j);
     end;
   end;
@@ -376,25 +360,17 @@
   //                0        1      2
   begin
     a := -Infinity;
-    b := points[0].Value;
+    b := points[0];
     AList.AddRange(a, b);
-    if not points[0].Contained then
-      AList.AddPoint(b);
     j := 1;
   end;
   while j < Length(points) do begin
-    a := points[j].Value;
-    if not points[j].Contained then
-      AList.AddPoint(a);
-    if j = High(points) then begin
-      AList.AddRange(a, Infinity);
-    end else
-    begin
-      b := points[j+1].Value;
-      AList.AddRange(a, b);
-      if not points[j+1].Contained then
-        AList.AddPoint(b);
-    end;
+    a := points[j];
+    if j = High(points) then
+      b := Infinity
+    else
+      b := points[j+1];
+    AList.AddRange(a, b);
     inc(j, 2);
   end;
 end;
@@ -418,8 +394,6 @@
   savedExpr := FParser.Expression;
   domains := TIntervalList.Create;
   try
-    AList.Epsilon := FEpsilon;
-    domains.Epsilon := FEpsilon;
     ParseExpression(AList, domains);
     ConvertToExclusions(AList, domains);
   finally
@@ -500,7 +474,6 @@
   FX := FParser.Identifiers.AddFloatVariable(FVariable, 0.0);
 
   FDomainScanner := TChartDomainScanner.Create(self);
-  FDomainEpsilon := DEFAULT_EPSILON;
 
   FParams := TChartExprParams.Create(FParser, @OnChangedHandler);
 end;
@@ -577,9 +550,17 @@
   UpdateParentChart;
 end;
 
+function TExpressionSeries.GetDomainEpsilon: Double;
+begin
+  Result := FDomainScanner.Epsilon;
+end;
+
 procedure TExpressionSeries.SetDomainEpsilon(const AValue: Double);
 begin
-  FDomainScanner.Epsilon := AValue;
+  if FDomainScanner.Epsilon = abs(AValue) then exit;
+  FDomainScanner.Epsilon := abs(AValue);
+  RequestParserUpdate;
+  UpdateParentChart;
 end;
 
 procedure TExpressionSeries.SetExpression(const AValue: String);
@@ -613,7 +594,6 @@
     FParser.Identifiers.AddFloatVariable(p.Name, p.Value);
   end;
 
-  FDomainScanner.Epsilon := FDomainEpsilon;
   FDomainScanner.Expression := FDomain;
   FDomainScanner.ExtractDomainExclusions(DomainExclusions);
 
Index: components/tachart/tafuncseries.pas
===================================================================
--- components/tachart/tafuncseries.pas	(revision 60720)
+++ components/tachart/tafuncseries.pas	(working copy)
@@ -327,7 +327,7 @@
     procedure InvalidateFitResults; virtual;
     procedure Loaded; override;
     function PrepareFitParams: boolean;
-    function PrepareIntervals: TIntervalList;
+    function PrepareIntervals: TIntervalList; virtual;
     procedure SourceChanged(ASender: TObject); override;
   public
     procedure Assign(ASource: TPersistent); override;
Index: components/tachart/test/SourcesTest.pas
===================================================================
--- components/tachart/test/SourcesTest.pas	(revision 60720)
+++ components/tachart/test/SourcesTest.pas	(working copy)
@@ -450,8 +450,6 @@
 end;
 
 procedure TListSourceTest.Multi;
-var
-  L: TStrings;
 begin
   FSource.Clear;
   AssertEquals(1, FSource.YCount);
Index: components/tachart/test/UtilsTest.pas
===================================================================
--- components/tachart/test/UtilsTest.pas	(revision 60720)
+++ components/tachart/test/UtilsTest.pas	(working copy)
@@ -118,12 +118,6 @@
   r := 6.0;
   AssertTrue(FIList.Intersect(l, r, hint));
   AssertEquals(2.0, r);
-  FIList.Epsilon := 0.1;
-  l := 0.5;
-  r := 2.5;
-  AssertTrue(FIList.Intersect(l, r, hint));
-  AssertEquals(0.9, l);
-  AssertEquals(2.1, r);
 end;
 
 procedure TIntervalListTest.Merge;
solution1.diff (11,526 bytes)

Marcin Wiazowski

2019-03-19 22:27

reporter  

solution2.diff (14,785 bytes)
Index: components/tachart/tachartutils.pas
===================================================================
--- components/tachart/tachartutils.pas	(revision 60720)
+++ components/tachart/tachartutils.pas	(working copy)
@@ -127,7 +127,6 @@
     procedure Changed;
     function GetInterval(AIndex: Integer): TDoubleInterval;
     function GetIntervalCount: Integer;
-    procedure SetEpsilon(AValue: Double);
     procedure SetOnChange(AValue: TNotifyEvent);
   public
     procedure Assign(ASource: TIntervalList);
@@ -139,7 +138,7 @@
     function Intersect(
       var ALeft, ARight: Double; var AHint: Integer): Boolean;
   public
-    property Epsilon: Double read FEpsilon write SetEpsilon;
+    property Epsilon: Double read FEpsilon write FEpsilon;
     property Interval[AIndex: Integer]: TDoubleInterval read GetInterval;
     property IntervalCount: Integer read GetIntervalCount;
     property OnChange: TNotifyEvent read FOnChange write SetOnChange;
@@ -710,6 +709,9 @@
   j: Integer;
   k: Integer;
 begin
+  AStart -= FEpsilon;
+  AEnd += FEpsilon;
+  if AStart >= AEnd then exit;
   i := 0;
   while (i <= High(FIntervals)) and (FIntervals[i].FEnd < AStart) do
     i += 1;
@@ -776,13 +778,13 @@
   if Length(FIntervals) = 0 then exit;
 
   AHint := EnsureRange(AHint, 0, High(FIntervals));
-  while (AHint > 0) and (FIntervals[AHint].FStart > ARight) do
+  while (AHint > 0) and (FIntervals[AHint].FStart >= ARight) do
     Dec(AHint);
 
   while
-    (AHint <= High(FIntervals)) and (FIntervals[AHint].FStart <= ARight)
+    (AHint <= High(FIntervals)) and (FIntervals[AHint].FStart < ARight)
   do begin
-    if FIntervals[AHint].FEnd >= ALeft then begin
+    if FIntervals[AHint].FEnd > ALeft then begin
       if not Result then fi := AHint;
       li := AHint;
       Result := true;
@@ -791,20 +793,11 @@
   end;
 
   if Result then begin
-    ALeft := FIntervals[fi].FStart - Epsilon;
-    ARight := FIntervals[li].FEnd + Epsilon;
+    ALeft := FIntervals[fi].FStart;
+    ARight := FIntervals[li].FEnd;
   end;
 end;
 
-procedure TIntervalList.SetEpsilon(AValue: Double);
-begin
-  if FEpsilon = AValue then exit;
-  if AValue <= 0 then
-    raise EChartIntervalError.Create('Epsilon <= 0');
-  FEpsilon := AValue;
-  Changed;
-end;
-
 procedure TIntervalList.SetOnChange(AValue: TNotifyEvent);
 begin
   if TMethod(FOnChange) = TMethod(AValue) then exit;
Index: components/tachart/taexpressionseries.pas
===================================================================
--- components/tachart/taexpressionseries.pas	(revision 60720)
+++ components/tachart/taexpressionseries.pas	(working copy)
@@ -89,7 +89,6 @@
   TExpressionSeries = class(TCustomFuncSeries)
   private
     FDomain: String;
-    FDomainEpsilon: Double;
     FDomainScanner: TChartDomainScanner;
     FExpression: String;
     FParams: TChartExprParams;
@@ -97,6 +96,7 @@
     FVariable: String;
     FX: TFPExprIdentifierDef;
     FDirty: Boolean;
+    function GetDomainEpsilon: Double;
     procedure SetDomain(const AValue: String);
     procedure SetDomainEpsilon(const AValue: Double);
     procedure SetExpression(const AValue: string);
@@ -115,7 +115,7 @@
     function IsEmpty: Boolean; override;
     procedure RequestParserUpdate; inline;
   published
-    property DomainEpsilon: Double read FDomainEpsilon write SetDomainEpsilon;
+    property DomainEpsilon: Double read GetDomainEpsilon write SetDomainEpsilon;
     property Params: TChartExprParams read FParams write SetParams;
     property Variable: String read FVariable write SetVariable;
     property Domain: String read FDomain write SetDomain;
@@ -271,6 +271,7 @@
 begin
   FSeries := ASeries;
   FParser := ASeries.FParser;
+  FEpsilon := DEFAULT_EPSILON;
 end;
 
 { Analyzes the parts of the domain expression and extract the intervals on
@@ -280,68 +281,67 @@
 procedure TChartDomainScanner.Analyze(AList, ADomain: TIntervalList;
   const AParts: TDomainParts);
 var
+  SaveListEpsilon, SaveDomainEpsilon: Double;
   a, b: Double;
 begin
-  // two-sided interval, e.g. "0 < x <= 1", or "2 > x >= 1"
-  if (AParts[2] = Variable) and (AParts[3] <> '') and (AParts[4] <> '') then
-  begin
-    FParser.Expression := AParts[0];
-    a := ArgToFloat(FParser.Evaluate);
-    FParser.Expression := AParts[4];
-    b := ArgToFloat(FParser.Evaluate);
-    if (AParts[1][1] = '<') and (AParts[3][1] = '<') and (a < b) then
-      ADomain.AddRange(a, b)
-    else
-    if (AParts[1][1] = '>') and (AParts[3][1] = '>') and (a > b) then
-      ADomain.AddRange(b, a);
-  end else
-  // one-sided interval, variable is at left
-  if (AParts[0] = Variable) and (AParts[3] = '') and (AParts[4] = '') then
-  begin
-    FParser.Expression := AParts[2];
-    a := ArgToFloat(FParser.Evaluate);
-    case AParts[1] of
-      '<>'      : AList.AddPoint(a);                    //  x <> a
-      '<', '<=' : ADomain.AddRange(-Infinity, a);       //  x < a, x <= a
-      '>', '>=' : ADomain.AddRange(a, Infinity);        //  x > a, x >= a
-      else  Expressionerror;
-    end;
-  end else
-  // one-sided interval, variable is at right
-  if (AParts[2] = Variable) and (AParts[3] = '') and (AParts[4] = '') then
-  begin
-    FParser.Expression := AParts[0];
-    a := ArgToFloat(FParser.Evaluate);
-    case AParts[1] of
-      '<>'      : AList.AddPoint(a);                    //  a <> x
-      '<', '<=' : ADomain.AddRange(a, Infinity);        //  a < x, a <= x
-      '>', '>=' : ADomain.AddRange(-Infinity, a);       //  a > x, a >= x
-      else   ExpressionError;
-    end;
-  end else
-    ExpressionError;
+  SaveListEpsilon := AList.Epsilon;
+  SaveDomainEpsilon := ADomain.Epsilon;
+  try
+    AList.Epsilon := FEpsilon; // list of excluded ranges should be widened by Epsilon
+    ADomain.Epsilon := -FEpsilon; // list of included ranges should be narrowed by Epsilon
+
+    // two-sided interval, e.g. "0 < x <= 1", or "2 > x >= 1"
+    if (AParts[2] = Variable) and (AParts[3] <> '') and (AParts[4] <> '') then
+    begin
+      FParser.Expression := AParts[0];
+      a := ArgToFloat(FParser.Evaluate);
+      FParser.Expression := AParts[4];
+      b := ArgToFloat(FParser.Evaluate);
+      if (AParts[1][1] = '<') and (AParts[3][1] = '<') and (a < b) then
+        ADomain.AddRange(a, b)
+      else
+      if (AParts[1][1] = '>') and (AParts[3][1] = '>') and (a > b) then
+        ADomain.AddRange(b, a);
+    end else
+    // one-sided interval, variable is at left
+    if (AParts[0] = Variable) and (AParts[3] = '') and (AParts[4] = '') then
+    begin
+      FParser.Expression := AParts[2];
+      a := ArgToFloat(FParser.Evaluate);
+      case AParts[1] of
+        '<>'      : AList.AddPoint(a);                    //  x <> a
+        '<', '<=' : ADomain.AddRange(-Infinity, a);       //  x < a, x <= a
+        '>', '>=' : ADomain.AddRange(a, Infinity);        //  x > a, x >= a
+        else  Expressionerror;
+      end;
+    end else
+    // one-sided interval, variable is at right
+    if (AParts[2] = Variable) and (AParts[3] = '') and (AParts[4] = '') then
+    begin
+      FParser.Expression := AParts[0];
+      a := ArgToFloat(FParser.Evaluate);
+      case AParts[1] of
+        '<>'      : AList.AddPoint(a);                    //  a <> x
+        '<', '<=' : ADomain.AddRange(a, Infinity);        //  a < x, a <= x
+        '>', '>=' : ADomain.AddRange(-Infinity, a);       //  a > x, a >= x
+        else   ExpressionError;
+      end;
+    end else
+      ExpressionError;
+  finally
+    AList.Epsilon := SaveListEpsilon;
+    ADomain.Epsilon := SaveDomainEpsilon;
+  end;
 end;
 
 { Converts the intervals in ADomain on which the function is defined to
   intervals in AList in which the function is NOT defined (= DomainExclusion) }
 procedure TChartDomainScanner.ConvertToExclusions(AList, ADomain: TIntervalList);
-
-  function IsPoint(i: Integer): Boolean;
-  begin
-    Result := (i >= 0) and (i < ADomain.IntervalCount) and
-      (ADomain.Interval[i].FStart = ADomain.Interval[i].FEnd);
-  end;
-
-type
-  TIntervalPoint = record
-    Value: Double;
-    Contained: Boolean;
-  end;
-
 var
+  SaveListEpsilon: Double;
   a, b: Double;
   i, j: Integer;
-  points: array of TIntervalPoint;
+  points: array of Double;
 begin
   if ADomain.IntervalCount = 0 then
     exit;
@@ -350,52 +350,49 @@
   SetLength(points, ADomain.IntervalCount*2);
 
   for i:=0 to ADomain.IntervalCount-1 do begin
-    if IsPoint(i) then
-      Continue;
     if ADomain.Interval[i].FStart <> -Infinity then begin
-      points[j].Value := ADomain.Interval[i].FStart;
-      points[j].Contained := IsPoint(i-1);
+      points[j] := ADomain.Interval[i].FStart;
       inc(j);
     end;
     if ADomain.Interval[i].FEnd <> +Infinity then begin
-      points[j].Value := ADomain.Interval[i].FEnd;
-      points[j].Contained := IsPoint(i+1);
+      points[j] := ADomain.Interval[i].FEnd;
       inc(j);
     end;
   end;
   SetLength(points, j);
 
-  // Case 1: domain extends to neg infinity
-  // -INF <---------|xxxxxxxx|------|xxxx> INF     with - = allowed, x = forbidden
-  //                0        1      2
-  if ADomain.Interval[0].FStart = -Infinity then
-    j := 0
-  else
-  // Case 2: domain begins at finite value
-  // -INF <xxxxxxxxx|--------|xxxxxx|------>INF
-  //                0        1      2
-  begin
-    a := -Infinity;
-    b := points[0].Value;
-    AList.AddRange(a, b);
-    if not points[0].Contained then
-      AList.AddPoint(b);
-    j := 1;
-  end;
-  while j < Length(points) do begin
-    a := points[j].Value;
-    if not points[j].Contained then
-      AList.AddPoint(a);
-    if j = High(points) then begin
-      AList.AddRange(a, Infinity);
-    end else
+  SaveListEpsilon := AList.Epsilon;
+  try
+    AList.Epsilon := 0; // provide direct ADomain to AList conversion - all the
+                        // required epsilons have already been applied earlier,
+                        // in the Analyze() call
+
+    // Case 1: domain extends to neg infinity
+    // -INF <---------|xxxxxxxx|------|xxxx> INF     with - = allowed, x = forbidden
+    //                0        1      2
+    if ADomain.Interval[0].FStart = -Infinity then
+      j := 0
+    else
+    // Case 2: domain begins at finite value
+    // -INF <xxxxxxxxx|--------|xxxxxx|------>INF
+    //                0        1      2
     begin
-      b := points[j+1].Value;
+      a := -Infinity;
+      b := points[0];
       AList.AddRange(a, b);
-      if not points[j+1].Contained then
-        AList.AddPoint(b);
+      j := 1;
     end;
-    inc(j, 2);
+    while j < Length(points) do begin
+      a := points[j];
+      if j = High(points) then
+        b := Infinity
+      else
+        b := points[j+1];
+      AList.AddRange(a, b);
+      inc(j, 2);
+    end;
+  finally
+    AList.Epsilon := SaveListEpsilon;
   end;
 end;
 
@@ -418,8 +415,6 @@
   savedExpr := FParser.Expression;
   domains := TIntervalList.Create;
   try
-    AList.Epsilon := FEpsilon;
-    domains.Epsilon := FEpsilon;
     ParseExpression(AList, domains);
     ConvertToExclusions(AList, domains);
   finally
@@ -500,7 +495,6 @@
   FX := FParser.Identifiers.AddFloatVariable(FVariable, 0.0);
 
   FDomainScanner := TChartDomainScanner.Create(self);
-  FDomainEpsilon := DEFAULT_EPSILON;
 
   FParams := TChartExprParams.Create(FParser, @OnChangedHandler);
 end;
@@ -577,9 +571,17 @@
   UpdateParentChart;
 end;
 
+function TExpressionSeries.GetDomainEpsilon: Double;
+begin
+  Result := FDomainScanner.Epsilon;
+end;
+
 procedure TExpressionSeries.SetDomainEpsilon(const AValue: Double);
 begin
-  FDomainScanner.Epsilon := AValue;
+  if FDomainScanner.Epsilon = abs(AValue) then exit;
+  FDomainScanner.Epsilon := abs(AValue);
+  RequestParserUpdate;
+  UpdateParentChart;
 end;
 
 procedure TExpressionSeries.SetExpression(const AValue: String);
@@ -613,7 +615,6 @@
     FParser.Identifiers.AddFloatVariable(p.Name, p.Value);
   end;
 
-  FDomainScanner.Epsilon := FDomainEpsilon;
   FDomainScanner.Expression := FDomain;
   FDomainScanner.ExtractDomainExclusions(DomainExclusions);
 
Index: components/tachart/tafuncseries.pas
===================================================================
--- components/tachart/tafuncseries.pas	(revision 60720)
+++ components/tachart/tafuncseries.pas	(working copy)
@@ -327,7 +327,7 @@
     procedure InvalidateFitResults; virtual;
     procedure Loaded; override;
     function PrepareFitParams: boolean;
-    function PrepareIntervals: TIntervalList;
+    function PrepareIntervals: TIntervalList; virtual;
     procedure SourceChanged(ASender: TObject); override;
   public
     procedure Assign(ASource: TPersistent); override;
@@ -1315,6 +1315,7 @@
 begin
   FIntervals := TIntervalList.Create;
   try
+    FIntervals.Epsilon := 0;
     if not (csoExtrapolateLeft in FOwner.Options) then
       FIntervals.AddRange(NegInfinity, FX[0]);
     if not (csoExtrapolateRight in FOwner.Options) then
@@ -2156,6 +2157,7 @@
 
 function TFitSeries.PrepareIntervals: TIntervalList;
 var
+  SaveEpsilon: Double;
   xmin, xmax: Double;
 begin
   Result := TIntervalList.Create;
@@ -2162,8 +2164,12 @@
   try
     CalcXRange(xmin, xmax);
     if DrawFitRangeOnly then begin
+      SaveEpsilon := Result.Epsilon;
+      Result.Epsilon := 0;
       Result.AddRange(NegInfinity, xmin);
       Result.AddRange(xmax, SafeInfinity);
+      Result.Epsilon := SaveEpsilon; // Result may by used by TFitSeries descendants,
+                                     // so revert to the default Epsilon value
     end;
   except
     Result.Free;
Index: components/tachart/test/SourcesTest.pas
===================================================================
--- components/tachart/test/SourcesTest.pas	(revision 60720)
+++ components/tachart/test/SourcesTest.pas	(working copy)
@@ -450,8 +450,6 @@
 end;
 
 procedure TListSourceTest.Multi;
-var
-  L: TStrings;
 begin
   FSource.Clear;
   AssertEquals(1, FSource.YCount);
Index: components/tachart/test/UtilsTest.pas
===================================================================
--- components/tachart/test/UtilsTest.pas	(revision 60720)
+++ components/tachart/test/UtilsTest.pas	(working copy)
@@ -119,11 +119,19 @@
   AssertTrue(FIList.Intersect(l, r, hint));
   AssertEquals(2.0, r);
   FIList.Epsilon := 0.1;
-  l := 0.5;
-  r := 2.5;
+  FIList.AddRange(101.0, 102.0);
+  l := 100.5;
+  r := 102.5;
   AssertTrue(FIList.Intersect(l, r, hint));
-  AssertEquals(0.9, l);
-  AssertEquals(2.1, r);
+  AssertEquals(100.9, l);
+  AssertEquals(102.1, r);
+  FIList.Epsilon := -0.1;
+  FIList.AddRange(201.0, 202.0);
+  l := 200.5;
+  r := 202.5;
+  AssertTrue(FIList.Intersect(l, r, hint));
+  AssertEquals(201.1, l);
+  AssertEquals(201.9, r);
 end;
 
 procedure TIntervalListTest.Merge;
solution2.diff (14,785 bytes)

Marcin Wiazowski

2019-03-19 22:27

reporter  

Reproduce1.gif (12,674 bytes)
Reproduce1.gif (12,674 bytes)

Marcin Wiazowski

2019-03-19 22:28

reporter  

Reproduce2.png (5,686 bytes)
Reproduce2.png (5,686 bytes)

Marcin Wiazowski

2019-03-19 22:28

reporter  

Reproduce3.gif (11,154 bytes)
Reproduce3.gif (11,154 bytes)

Marcin Wiazowski

2019-03-19 22:28

reporter  

Reproduce4.png (4,617 bytes)
Reproduce4.png (4,617 bytes)

Marcin Wiazowski

2019-03-19 22:28

reporter  

Reproduce5.png (8,479 bytes)
Reproduce5.png (8,479 bytes)

Marcin Wiazowski

2019-03-19 22:29

reporter  

Reproduce6.gif (18,055 bytes)
Reproduce6.gif (18,055 bytes)

wp

2019-03-20 17:42

developer   ~0114944

Last edited: 2019-03-20 18:10

View 3 revisions

Fixed issue # 1 to 4 by a different approach.

The issue is that Epsilon has been assumed to be an absolute number while is should be considered to be relative. The reference value to which Epsilon is relative is collected during the AddRange calls, and only in the case that the reference value is 0 Epsilon is used literally (because the product would be zero, too).

I don't like the idea of abondoning AddPoint and passing the burden of finding the correct epsilon to the user. The purpose of epsilon is to protect from running into the interval where the function cannot be calculated due to rounding error. Epsilon is not a parameter to be changed by the user freely, it is accessible only because there may be cases to adjust the default value. Selecting Epsilon as large as 0.2 is something the user should not do (it is allowed for testing and demonstration purposes, of course). Allowing a negative value is non-sense.

My solution is a bit slower than yours because the outer exclusion limits (after apply epsilon) have to be calculated each time.

Issue # 5 is a documentation issue. Epsilon = 0 has been forbidden already since the very commit of TIntervalList by Alexander Klenin although he himself mentioned this case in a forum thread, obviously without testing it.

Marcin Wiazowski

2019-03-20 22:17

reporter  

Reproduce1verB.zip (2,703 bytes)

Marcin Wiazowski

2019-03-20 22:17

reporter  

Reproduce2verB.zip (2,556 bytes)

Marcin Wiazowski

2019-03-20 22:17

reporter  

Reproduce3verB.zip (2,662 bytes)

Marcin Wiazowski

2019-03-20 22:21

reporter   ~0114950

I attached some additional test applications. I'm afraid, that problems 1, 2 and 3 still exist.

I can see some advantages of the absolute epsilon, instead of a relative one: the epsilon value, that is applied to ranges, is directly known - while the relative value must be calculated back from the ranges. In particular, when using TExpressionSeries, both Domain and DomainEpsilon properties must be used in order to obtain the value, that will be finally applied to ranges (and a knowledge of the internal algorithm is needed).

As you wrote, zero (or even negative) epsilons doesn't have much sense when excluding domain ranges. However, TIntervalList is not named TExclusionList - i.e. its name suggests any intervals, and not only exclusions. In case, when we need inclusions instead of exclusions (as in solution2.diff in TChartDomainScanner.Analyze()), a negative epsilon value is a practical solution.

A possibility of setting epsilon to zero is useful when defining TExpressionSeries.Domain - if we can't set DomainEpsilon to zero, it's hard to define the needed domains precisely - i.e. in case of absolute epsilon this can be done by manually narrowing ranges given in Domain by the DomainEpsilon value, while in case of relative epsilon this is very hard. Please also note that solution2.diff doesn't allow setting negative DomainEpsilon values - this possibility is available only in a low-level TIntervalList object. And setting TIntervalList.Epsilon to zero, or to some negative value (as allowed by solution2.diff), is only a possibility, it doesn't change the fact, that the current code still works properly.

Problems 2 and 3 occur, because line is drawn not exactly from the first to the last point. Well, drawing the line exactly needs zero epsilons...

wp

2019-03-20 23:52

developer   ~0114951

> TIntervalList is not named TExclusionList - i.e. its name suggests any intervals, and not only exclusions.

Right, I ignored this. But this puts up the question: Why do TCubicSplineSeries, TBSplineSeries and TFitSeries use the IntervalList at all? I think it should be enough to pass the limits of the drawing range as simple numbers - all the code provided for merging/intersection of intervals is just overkill here. I don't see any reason why these series should not be painted on a single interval (ok - TFitSeries with custom functions could use it, but this is a very over-stressed use case for me).

-----

> In case, when we need inclusions instead of exclusions (as in solution2.diff in TChartDomainScanner.Analyze()), a negative epsilon value is a practical solution.

But very confusing, a horrible user interface. I will not accept this. If you want to support open excluded intervals (and this would be welcome) you should work with an additional parameter for AddRange:

  type
    TIntervalOption = (ioWithoutStart, ioWithoutEnd);
    TIntervalOptionss = set of TIntervalOption;

  procedure AddRange(AStart, AEnd: Double; ALimits: TIntervalOptions = []);

Marcin Wiazowski

2019-03-21 00:52

reporter   ~0114954

> the question: Why do TCubicSplineSeries, TBSplineSeries and TFitSeries use the IntervalList at all

This is because TDrawFuncHelper - which is used for drawing series with some X step (one pixel for Step = 1, two pixels for Step = 2, etc) - requires TIntervalList for its work. In particular, TDrawFuncHelper.DrawFunction() performs drawing by using TIntervalList, and TDrawFuncHelper.CalcAxisExtentY() performs extent calculation by using TIntervalList. Adding some exclusions is - man could say - an additional feature...



> a horrible user interface

Well, yes. Name "Epsilon" suggest the purpose. I think that "Delta" would be better. (However, let's remember, that TIntervalList is an internal object, so naming may be not a matter of the greatest importance)



> you should work with an additional parameter for AddRange:

From the functional point of view, it's not needed - it's enough to change ">" to ">=", "<=" to "<" and ">=" to ">" in TIntervalList.Intersect() - and that's all; everything works exactly as it was earlier, and - additionally - open intervals are supported.



What would you say for:
- Epsilon stays as it is now, i.e. can be only > 0
- a new Delta property is introduced, which can be < 0, = 0 or > 0; if the user wants deliberately to use negative intervals (like in the TChartDomainScanner.Analyze() fix), then he sets the Delta property and cannot then get confused about AddRange() behavior.

wp

2019-03-21 13:57

developer   ~0114960

Last edited: 2019-03-21 13:59

View 2 revisions

>> the question: Why do TCubicSplineSeries, TBSplineSeries and TFitSeries use the
>> IntervalList at all
>
> This is because TDrawFuncHelper - which is used for drawing series with some X step
> (one pixel for Step = 1, two pixels for Step = 2, etc) - requires TIntervalList for its
> work. In particular, TDrawFuncHelper.DrawFunction() performs drawing by using
> TIntervalList, and TDrawFuncHelper.CalcAxisExtentY() performs extent calculation by
> using TIntervalList. Adding some exclusions is - man could say - an additional
> feature...

Sure, I know. I mean: shouldn't the TDrawFuncHelper be given a second constructor which has the overall interval limits as parameters, instead of the IntervalList? With a minor adjustment of ForEachPoint and XRange the DrawFuncHelper could step through the interval without the overkill of the IntervalList machinery.

---

>> you should work with an additional parameter for AddRange:
>
> From the functional point of view, it's not needed - it's enough to change ">"
> to ">=", > "<=" to "<" and ">=" to ">" in TIntervalList.Intersect() - and
> that's all; everything works exactly as it was earlier, and - additionally -
> open intervals are supported.

It is needed from a practical point of view. The user must be able to define open-ended intervals. The domain exclusion -INF to 0 is well-suited for y = log(x), but wrong for y = sqrt(x) where the point x = 0 must be allowed.

And the requirements for the Epsilon may be different from one domain exclusion to the other: Look at attached demo ("open_interval"): it plots the function y = sqrt(x - 1/(x-10)). Using Wolfram Alpha it can be shown easily (or less easily by manual calculation) that it has a zero at x = 5 - sqrt(26) and a pole/zero at x = 5 + sqrt(26). The function is defined for all x except for x < 5 - sqrt(26) and x = 5 + sqrt(26). For plotting the function in a TFuncSeries, therefore, you would add these domain exclusions
  
  Chart1FuncSeries1.DomainExclusions.AddRange(-Infinity, 5 - sqrt(26));
  Chart1FuncSeries1.DomainExclusions.AddPoint(5 + sqrt(26));

However, the function IS defined at 5 - sqrt(26), the first domain exclusion therefore should be open at the right side - TAChart, however, creates only closed intervals (at least on the finite end).

The combined screenshot "open_interval.png" shows in the top-left corner the result with default Epsilon (1E-6) - looks very nice at first, but when you zoom in around the zero point you will see that the curve does not start exactly at y = 0 (top-right figure) - because the function is not allowed to be calculated at 5 - sqrt(26).

Your solution for the open interval by setting Epsilon to 0 does make the curve start at y = 0 (bottom right figure), but now results in an overall poor plot (bottom left curve) because the exclusion at 5 + sqrt(26) cannot be found any more due to the zero epsilon.

---

> a new Delta property is introduced, which can be < 0, = 0 or > 0; if the user
> wants deliberately to use negative intervals (like in the
> TChartDomainScanner.Analyze() fix), then he sets the Delta property and cannot
> then get confused about AddRange() behavior.

I would like to keep all this stuff away from the user.

wp

2019-03-21 14:17

developer  

open_interval.zip (2,191 bytes)

wp

2019-03-21 14:17

developer  

open_interval.png (11,161 bytes)
open_interval.png (11,161 bytes)

Marcin Wiazowski

2019-03-21 18:54

reporter   ~0114966

> shouldn't the TDrawFuncHelper be given a second constructor which has the overall interval limits as parameters, instead of the IntervalList?

This could be done, however, there are some advantages of the current solution:
- in TFitSeries, interval list can be obtained by a protected method and used by TFitSeries descendants
- in TCubicSplineSeries, also some other problem exists (I'll create a separate bug report when we are finished here) - it can be solved only by using an interval list (which is already there).

TFitSeries and TCubicSplineSeries use only two ranges, i.e. -INF .. FirstPointX and LastPointX .. +INF (or one of them, or even none, depending on settings) - so checking two interval limits given in a constructor, instead of two ranges in interval list, won't give us neither much simpler code, nor a noticeable gain in speed...





You gave a good example with y = sqrt(x - 1/(x-10)) - now I understand. I haven't explained one thing (well, sometimes something is obvious for author of some code/modification, and only for him...).

Thanks to the fact, that changing Epsilon in solution2.diff no longer recalculates the already existing ranges, we can just call:

  Chart1FuncSeries1.DomainExclusions.Epsilon := 0;
  Chart1FuncSeries1.DomainExclusions.AddRange(-Infinity, 5-sqrt(26));
  Chart1FuncSeries1.DomainExclusions.Epsilon := 1E-6;
  Chart1FuncSeries1.DomainExclusions.AddPoint(5 + sqrt(26));

This solves the problem.





BUT: Your example paid my attention to something else. Try in Wolfram Alpha:

  discontinuities y = ln(abs(x-3)-10) + sqrt(abs(x)-10)

The returned domain is: x <= -10 or x > 13.

This means, that our excluded range should be: -10 < x <= 13

Even in solution2.diff, this still cannot be done by manipulating Epsilon's value.





So I have the following idea:

- the user should be able set Epsilon to >= 0 values (zero for cases like y = sqrt(x), non-zero for cases like y = log(x))

- the following change should be made:

  procedure TIntervalList.AddRange(AStart, AEnd: Double; AStartDirectEpsilon: Double = NaN; AEndDirectEpsilon: Double = NaN);
  begin
    if not IsNan(AStartDirectEpsilon) then
      AStart -= AStartDirectEpsilon
    else
      AStart -= FEpsilon;

    if not IsNan(AEndDirectEpsilon) then
      AEnd += AEndDirectEpsilon
    else
      AEnd += FEpsilon;

   ....

So, in the example above, we could call:

  AddRange(-10, 13, 0, 1E-6)

In this case, line will be drawn to X = -10, and then from X = 13 + 1E-6.

wp

2019-03-21 19:20

developer   ~0114968

> procedure TIntervalList.AddRange(AStart, AEnd: Double; AStartDirectEpsilon: Double = NaN; AEndDirectEpsilon: Double = NaN);

We're getting closer. But I don't want to expose the Epsilon details to the user too much. An interface like the one I gave above is much clearer, or maybe
 
  procedure TIntervalList.AddRange(AStart, AEnd: Double; WithoutStart: Boolean = false; WithoutEnd: Boolean = false);

I also don't see a real reason why there should be different Epsilons beyond default and zero. Maybe when the chart covers a wide range of numbers, but it will probably be plotted logarithmically in this case, otherwise details in the regions of small numbers are lost. In a log plot, however, the epsilons must be expressed in graph units and will be difficult to understand. Or return to relative Epsilons as shown above.

Marcin Wiazowski

2019-03-21 21:51

reporter  

Epsilons1.zip (2,450 bytes)

Marcin Wiazowski

2019-03-21 21:51

reporter  

Epsilons2.zip (2,395 bytes)

Marcin Wiazowski

2019-03-21 21:52

reporter  

Epsilons3.zip (2,441 bytes)

Marcin Wiazowski

2019-03-21 21:54

reporter   ~0114970

> don't want to expose the Epsilon details to the user too much

Maybe:

  procedure TIntervalList.AddRange(AStart, AEnd: Double; NoEpsilonAtStart: Boolean = false; NoEpsilonAtEnd: Boolean = false);




But it's still an advantage to allow Epsilon to be set to zero, in particular because of the TExpressionSeries.DomainEpsilon - it's useful to set DomainEpsilon to zero, when Domain is 'y = sqrt(x)'. Of course, when defining ranges manually (not by using Object Inspector), we can use:

  IntervalList.AddRange(X1 + IntervalList.Epsilon, X2 - IntervalList.Epsilon)

which simulates Epsilon being zero, but do we need hacks like this?




I can see some advantages of adjusting epsilons (all demos tested with r60736 with applied solution2.diff):

- when drawing a truncated sine wave (see the attached Epsilons1 demo),

- when drawing y = tan(x) with ExtentAutoY = True (see the attached Epsilons2 demo),

- to provide same Y range when displaying both y = cotan(x) and y = cotan(2*x) on the same chart (see the attached Epsilons3 demo).

wp

2019-03-21 23:42

developer   ~0114971

> procedure TIntervalList.AddRange(AStart, AEnd: Double; NoEpsilonAtStart: Boolean = false; NoEpsilonAtEnd: Boolean = false);

Sorry - nobody will understand this. If I would not know the background I would not understand either...

Why mention "Epsilon" here? It is not needed. Maybe I should present pseudo-code for "my" AddRange:


  procedure TIntervalList.AddRange(AStart, AEnd: Double;
    WithoutStart: Boolean = false; WithoutEnd: Boolean = false);
  begin
    if not WithoutStart then AStart := AStart - FEpsilon;
    if not WithoutEnd then AEnd := AEnd + FEpsilon;
    ...
  end;

This makes Epsilon effectively 0 when WithoutStart/WithoutEnd is true

I prefer the set parameters, though, because it allows to user to specify an open end without having to type the WithoutStart parameter:

  IntervalList.AddRange(AStart, AEnd, [ioWithoutEnd]);

Or name it "OpenStart", "OpenEnd"?

----

> I can see some advantages of adjusting epsilons...

I have no objection against changing of Epsilon in user code to get some effect (although there are more direct ways to set the y axis range for the tan(x) series...) - it is a published property, and the user can modify it at will - of course, he must know what he is doing (*). And this is for me the turning point: I am rather sure that most users do not know what they are doing when they change epsilon. In most cases they leave the published property alone and it works for almost 100% of all charts. But when Epsilon becomes a parameter in the AddRange method which is rather essential for TFuncSeries, they cannot leave it alone. Ok - you gave it a default value, but they must set it to 0 to create the open end of the interval, and they must understand what this means (and I guarantee: nobody reads the manual, at least not up to the chapter explaining it). I am against this kind of explicit usage of Epsilon to implement features of the series, and much prefer a "hidden" usage as shown above.

---

(*) Having said that I think it's time to give up my resistance against Epsilon < 0... (although I still feel that it is wrong).

Marcin Wiazowski

2019-03-22 00:24

reporter   ~0114972

> NoEpsilonAtStart: Boolean = false; NoEpsilonAtEnd: Boolean = false

I must have had a brain fade. Surely, when calling AddRange(), the user thinks about the range, so naming convention should refer to start / end of this range, not to epsilons...


So it seems that the last thing to think over are names for AddRange() options. In all the currently existing code, the user will use AddRange() to add exclusions.

With default settings, calling AddRange(10, 20) will create an exclusion range [10 - 1e-6 .. 20 + 1e-6], so line will be drawn to X = 10 - 1e-6 and then from X = 20 + 1e-6 - so the requested 10 .. 20 range will be excluded along with its bounds - i.e. we received a closed exclusion interval.

With the newly introduced options, calling AddRange(10, 20, [OptionName1, OptionName2]) will create an exclusion range exactly as [10 .. 20], so the range will be excluded without its bounds when drawing - i.e. we will receive an open exclusion interval.

Since we get a closed interval by default, our options should specify an open interval. So TIntervalOption = (ioOpenStart, ioOpenEnd) seems to be right. Could it be? If so, I will update Solution 2 accordingly.


Your considerations about using epsilons in AddRange() and the users not reading manuals sound reasonable to me.

wp

2019-03-22 00:38

developer   ~0114973

Fine. If you modify Solution 2 accordingly I'll apply it.

BTW: I see you are not listed in contributors.txt (in folder (lazarus)/dos) which is played in the Lazarus About box. Do you want your name to be added? (no obligations, no rights either, just a thank you for your contributions)

Marcin Wiazowski

2019-03-22 02:22

reporter  

solution2b.diff (16,881 bytes)
Index: components/tachart/tachartutils.pas
===================================================================
--- components/tachart/tachartutils.pas	(revision 60742)
+++ components/tachart/tachartutils.pas	(working copy)
@@ -101,6 +101,9 @@
     smsLabelPercentTotal, { Cars 12 % of 1234 }
     smsXValue);        { 21/6/1996 }
 
+  TIntervalOption = (ioOpenStart, ioOpenEnd);
+  TIntervalOptions = set of TIntervalOption;
+
   TDoubleInterval = record
     FStart, FEnd: Double;
   end;
@@ -122,14 +125,11 @@
   TIntervalList = class
   private
     FEpsilon: Double;
-    FEpsilonScale: Double;
-    FAbsoluteEpsilon: Double;
     FIntervals: array of TDoubleInterval;
     FOnChange: TNotifyEvent;
     procedure Changed;
     function GetInterval(AIndex: Integer): TDoubleInterval;
     function GetIntervalCount: Integer;
-    procedure SetEpsilon(AValue: Double);
     procedure SetOnChange(AValue: TNotifyEvent);
   public
     procedure Assign(ASource: TIntervalList);
@@ -136,12 +136,12 @@
     constructor Create;
   public
     procedure AddPoint(APoint: Double); inline;
-    procedure AddRange(AStart, AEnd: Double);
+    procedure AddRange(AStart, AEnd: Double; ALimits: TIntervalOptions = []);
     procedure Clear;
     function Intersect(
       var ALeft, ARight: Double; var AHint: Integer): Boolean;
   public
-    property Epsilon: Double read FEpsilon write SetEpsilon;
+    property Epsilon: Double read FEpsilon write FEpsilon;
     property Interval[AIndex: Integer]: TDoubleInterval read GetInterval;
     property IntervalCount: Integer read GetIntervalCount;
     property OnChange: TNotifyEvent read FOnChange write SetOnChange;
@@ -706,12 +706,15 @@
   AddRange(APoint, APoint);
 end;
 
-procedure TIntervalList.AddRange(AStart, AEnd: Double);
+procedure TIntervalList.AddRange(AStart, AEnd: Double; ALimits: TIntervalOptions = []);
 var
   i: Integer;
   j: Integer;
   k: Integer;
 begin
+  if not (ioOpenStart in ALimits) then AStart -= FEpsilon;
+  if not (ioOpenEnd in ALimits) then AEnd += FEpsilon;
+  if AStart > AEnd then exit;
   i := 0;
   while (i <= High(FIntervals)) and (FIntervals[i].FEnd < AStart) do
     i += 1;
@@ -733,11 +736,6 @@
       FIntervals[k] := FIntervals[k - 1];
   end;
   FIntervals[i] := DoubleInterval(AStart, AEnd);
-  if (abs(FIntervals[i].FStart) <> Infinity) and (abs(FIntervals[i].FStart) > FEpsilonScale) then
-    FEpsilonScale := abs(FIntervals[i].FStart);
-  if (abs(FIntervals[i].FEnd) <> Infinity) and (abs(FIntervals[i].FEnd) > FEpsilonScale) then
-    FEpsilonScale := abs(FIntervals[i].FEnd);
-  FAbsoluteEpsilon := IfThen(FEpsilonScale = 0, FEpsilon, FEpsilon * FEpsilonScale);
   Changed;
 end;
 
@@ -762,7 +760,6 @@
 constructor TIntervalList.Create;
 begin
   FEpsilon := DEFAULT_EPSILON;
-  FEpsilonScale := 0.0
 end;
 
 function TIntervalList.GetInterval(AIndex: Integer): TDoubleInterval;
@@ -784,13 +781,13 @@
   if Length(FIntervals) = 0 then exit;
 
   AHint := EnsureRange(AHint, 0, High(FIntervals));
-  while (AHint > 0) and (FIntervals[AHint].FStart - FAbsoluteEpsilon > ARight) do
+  while (AHint > 0) and (FIntervals[AHint].FStart >= ARight) do
     Dec(AHint);
 
   while
-    (AHint <= High(FIntervals)) and (FIntervals[AHint].FStart - FAbsoluteEpsilon <= ARight)
+    (AHint <= High(FIntervals)) and (FIntervals[AHint].FStart < ARight)
   do begin
-    if FIntervals[AHint].FEnd >= ALeft then begin
+    if FIntervals[AHint].FEnd > ALeft then begin
       if not Result then fi := AHint;
       li := AHint;
       Result := true;
@@ -799,24 +796,11 @@
   end;
 
   if Result then begin
-    ALeft := FIntervals[fi].FStart - FAbsoluteEpsilon;
-    ARight := FIntervals[li].FEnd + FAbsoluteEpsilon;
+    ALeft := FIntervals[fi].FStart;
+    ARight := FIntervals[li].FEnd;
   end;
 end;
 
-procedure TIntervalList.SetEpsilon(AValue: Double);
-begin
-  if FEpsilon = AValue then exit;
-  if AValue <= 0 then
-    raise EChartIntervalError.Create('Epsilon <= 0');
-  FEpsilon := AValue;
-  if FEpsilonScale = 0 then
-    FAbsoluteEpsilon := FEpsilon
-  else
-    FAbsoluteEpsilon := FEpsilon * FEpsilonScale;
-  Changed;
-end;
-
 procedure TIntervalList.SetOnChange(AValue: TNotifyEvent);
 begin
   if TMethod(FOnChange) = TMethod(AValue) then exit;
Index: components/tachart/taexpressionseries.pas
===================================================================
--- components/tachart/taexpressionseries.pas	(revision 60742)
+++ components/tachart/taexpressionseries.pas	(working copy)
@@ -89,7 +89,6 @@
   TExpressionSeries = class(TCustomFuncSeries)
   private
     FDomain: String;
-    FDomainEpsilon: Double;
     FDomainScanner: TChartDomainScanner;
     FExpression: String;
     FParams: TChartExprParams;
@@ -97,6 +96,7 @@
     FVariable: String;
     FX: TFPExprIdentifierDef;
     FDirty: Boolean;
+    function GetDomainEpsilon: Double;
     procedure SetDomain(const AValue: String);
     procedure SetDomainEpsilon(const AValue: Double);
     procedure SetExpression(const AValue: string);
@@ -115,7 +115,7 @@
     function IsEmpty: Boolean; override;
     procedure RequestParserUpdate; inline;
   published
-    property DomainEpsilon: Double read FDomainEpsilon write SetDomainEpsilon;
+    property DomainEpsilon: Double read GetDomainEpsilon write SetDomainEpsilon;
     property Params: TChartExprParams read FParams write SetParams;
     property Variable: String read FVariable write SetVariable;
     property Domain: String read FDomain write SetDomain;
@@ -271,6 +271,7 @@
 begin
   FSeries := ASeries;
   FParser := ASeries.FParser;
+  FEpsilon := DEFAULT_EPSILON;
 end;
 
 { Analyzes the parts of the domain expression and extract the intervals on
@@ -280,68 +281,67 @@
 procedure TChartDomainScanner.Analyze(AList, ADomain: TIntervalList;
   const AParts: TDomainParts);
 var
+  SaveListEpsilon, SaveDomainEpsilon: Double;
   a, b: Double;
 begin
-  // two-sided interval, e.g. "0 < x <= 1", or "2 > x >= 1"
-  if (AParts[2] = Variable) and (AParts[3] <> '') and (AParts[4] <> '') then
-  begin
-    FParser.Expression := AParts[0];
-    a := ArgToFloat(FParser.Evaluate);
-    FParser.Expression := AParts[4];
-    b := ArgToFloat(FParser.Evaluate);
-    if (AParts[1][1] = '<') and (AParts[3][1] = '<') and (a < b) then
-      ADomain.AddRange(a, b)
-    else
-    if (AParts[1][1] = '>') and (AParts[3][1] = '>') and (a > b) then
-      ADomain.AddRange(b, a);
-  end else
-  // one-sided interval, variable is at left
-  if (AParts[0] = Variable) and (AParts[3] = '') and (AParts[4] = '') then
-  begin
-    FParser.Expression := AParts[2];
-    a := ArgToFloat(FParser.Evaluate);
-    case AParts[1] of
-      '<>'      : AList.AddPoint(a);                    //  x <> a
-      '<', '<=' : ADomain.AddRange(-Infinity, a);       //  x < a, x <= a
-      '>', '>=' : ADomain.AddRange(a, Infinity);        //  x > a, x >= a
-      else  Expressionerror;
-    end;
-  end else
-  // one-sided interval, variable is at right
-  if (AParts[2] = Variable) and (AParts[3] = '') and (AParts[4] = '') then
-  begin
-    FParser.Expression := AParts[0];
-    a := ArgToFloat(FParser.Evaluate);
-    case AParts[1] of
-      '<>'      : AList.AddPoint(a);                    //  a <> x
-      '<', '<=' : ADomain.AddRange(a, Infinity);        //  a < x, a <= x
-      '>', '>=' : ADomain.AddRange(-Infinity, a);       //  a > x, a >= x
-      else   ExpressionError;
-    end;
-  end else
-    ExpressionError;
+  SaveListEpsilon := AList.Epsilon;
+  SaveDomainEpsilon := ADomain.Epsilon;
+  try
+    AList.Epsilon := FEpsilon; // list of excluded ranges should be widened by Epsilon
+    ADomain.Epsilon := -FEpsilon; // list of included ranges should be narrowed by Epsilon
+
+    // two-sided interval, e.g. "0 < x <= 1", or "2 > x >= 1"
+    if (AParts[2] = Variable) and (AParts[3] <> '') and (AParts[4] <> '') then
+    begin
+      FParser.Expression := AParts[0];
+      a := ArgToFloat(FParser.Evaluate);
+      FParser.Expression := AParts[4];
+      b := ArgToFloat(FParser.Evaluate);
+      if (AParts[1][1] = '<') and (AParts[3][1] = '<') and (a < b) then
+        ADomain.AddRange(a, b)
+      else
+      if (AParts[1][1] = '>') and (AParts[3][1] = '>') and (a > b) then
+        ADomain.AddRange(b, a);
+    end else
+    // one-sided interval, variable is at left
+    if (AParts[0] = Variable) and (AParts[3] = '') and (AParts[4] = '') then
+    begin
+      FParser.Expression := AParts[2];
+      a := ArgToFloat(FParser.Evaluate);
+      case AParts[1] of
+        '<>'      : AList.AddPoint(a);                    //  x <> a
+        '<', '<=' : ADomain.AddRange(-Infinity, a);       //  x < a, x <= a
+        '>', '>=' : ADomain.AddRange(a, Infinity);        //  x > a, x >= a
+        else  Expressionerror;
+      end;
+    end else
+    // one-sided interval, variable is at right
+    if (AParts[2] = Variable) and (AParts[3] = '') and (AParts[4] = '') then
+    begin
+      FParser.Expression := AParts[0];
+      a := ArgToFloat(FParser.Evaluate);
+      case AParts[1] of
+        '<>'      : AList.AddPoint(a);                    //  a <> x
+        '<', '<=' : ADomain.AddRange(a, Infinity);        //  a < x, a <= x
+        '>', '>=' : ADomain.AddRange(-Infinity, a);       //  a > x, a >= x
+        else   ExpressionError;
+      end;
+    end else
+      ExpressionError;
+  finally
+    AList.Epsilon := SaveListEpsilon;
+    ADomain.Epsilon := SaveDomainEpsilon;
+  end;
 end;
 
 { Converts the intervals in ADomain on which the function is defined to
   intervals in AList in which the function is NOT defined (= DomainExclusion) }
 procedure TChartDomainScanner.ConvertToExclusions(AList, ADomain: TIntervalList);
-
-  function IsPoint(i: Integer): Boolean;
-  begin
-    Result := (i >= 0) and (i < ADomain.IntervalCount) and
-      (ADomain.Interval[i].FStart = ADomain.Interval[i].FEnd);
-  end;
-
-type
-  TIntervalPoint = record
-    Value: Double;
-    Contained: Boolean;
-  end;
-
 var
+  SaveListEpsilon: Double;
   a, b: Double;
   i, j: Integer;
-  points: array of TIntervalPoint;
+  points: array of Double;
 begin
   if ADomain.IntervalCount = 0 then
     exit;
@@ -350,52 +350,49 @@
   SetLength(points, ADomain.IntervalCount*2);
 
   for i:=0 to ADomain.IntervalCount-1 do begin
-    if IsPoint(i) then
-      Continue;
     if ADomain.Interval[i].FStart <> -Infinity then begin
-      points[j].Value := ADomain.Interval[i].FStart;
-      points[j].Contained := IsPoint(i-1);
+      points[j] := ADomain.Interval[i].FStart;
       inc(j);
     end;
     if ADomain.Interval[i].FEnd <> +Infinity then begin
-      points[j].Value := ADomain.Interval[i].FEnd;
-      points[j].Contained := IsPoint(i+1);
+      points[j] := ADomain.Interval[i].FEnd;
       inc(j);
     end;
   end;
   SetLength(points, j);
 
-  // Case 1: domain extends to neg infinity
-  // -INF <---------|xxxxxxxx|------|xxxx> INF     with - = allowed, x = forbidden
-  //                0        1      2
-  if ADomain.Interval[0].FStart = -Infinity then
-    j := 0
-  else
-  // Case 2: domain begins at finite value
-  // -INF <xxxxxxxxx|--------|xxxxxx|------>INF
-  //                0        1      2
-  begin
-    a := -Infinity;
-    b := points[0].Value;
-    AList.AddRange(a, b);
-    if not points[0].Contained then
-      AList.AddPoint(b);
-    j := 1;
-  end;
-  while j < Length(points) do begin
-    a := points[j].Value;
-    if not points[j].Contained then
-      AList.AddPoint(a);
-    if j = High(points) then begin
-      AList.AddRange(a, Infinity);
-    end else
+  SaveListEpsilon := AList.Epsilon;
+  try
+    AList.Epsilon := 0; // provide direct ADomain to AList conversion - all the
+                        // required epsilons have already been applied earlier,
+                        // in the Analyze() call
+
+    // Case 1: domain extends to neg infinity
+    // -INF <---------|xxxxxxxx|------|xxxx> INF     with - = allowed, x = forbidden
+    //                0        1      2
+    if ADomain.Interval[0].FStart = -Infinity then
+      j := 0
+    else
+    // Case 2: domain begins at finite value
+    // -INF <xxxxxxxxx|--------|xxxxxx|------>INF
+    //                0        1      2
     begin
-      b := points[j+1].Value;
+      a := -Infinity;
+      b := points[0];
       AList.AddRange(a, b);
-      if not points[j+1].Contained then
-        AList.AddPoint(b);
+      j := 1;
     end;
-    inc(j, 2);
+    while j < Length(points) do begin
+      a := points[j];
+      if j = High(points) then
+        b := Infinity
+      else
+        b := points[j+1];
+      AList.AddRange(a, b);
+      inc(j, 2);
+    end;
+  finally
+    AList.Epsilon := SaveListEpsilon;
   end;
 end;
 
@@ -418,8 +415,6 @@
   savedExpr := FParser.Expression;
   domains := TIntervalList.Create;
   try
-    AList.Epsilon := FEpsilon;
-    domains.Epsilon := FEpsilon;
     ParseExpression(AList, domains);
     ConvertToExclusions(AList, domains);
   finally
@@ -500,7 +495,6 @@
   FX := FParser.Identifiers.AddFloatVariable(FVariable, 0.0);
 
   FDomainScanner := TChartDomainScanner.Create(self);
-  FDomainEpsilon := DEFAULT_EPSILON;
 
   FParams := TChartExprParams.Create(FParser, @OnChangedHandler);
 end;
@@ -577,9 +571,17 @@
   UpdateParentChart;
 end;
 
+function TExpressionSeries.GetDomainEpsilon: Double;
+begin
+  Result := FDomainScanner.Epsilon;
+end;
+
 procedure TExpressionSeries.SetDomainEpsilon(const AValue: Double);
 begin
-  FDomainScanner.Epsilon := AValue;
+  if FDomainScanner.Epsilon = abs(AValue) then exit;
+  FDomainScanner.Epsilon := abs(AValue);
+  RequestParserUpdate;
+  UpdateParentChart;
 end;
 
 procedure TExpressionSeries.SetExpression(const AValue: String);
@@ -613,7 +615,6 @@
     FParser.Identifiers.AddFloatVariable(p.Name, p.Value);
   end;
 
-  FDomainScanner.Epsilon := FDomainEpsilon;
   FDomainScanner.Expression := FDomain;
   FDomainScanner.ExtractDomainExclusions(DomainExclusions);
 
Index: components/tachart/tafuncseries.pas
===================================================================
--- components/tachart/tafuncseries.pas	(revision 60742)
+++ components/tachart/tafuncseries.pas	(working copy)
@@ -327,7 +327,7 @@
     procedure InvalidateFitResults; virtual;
     procedure Loaded; override;
     function PrepareFitParams: boolean;
-    function PrepareIntervals: TIntervalList;
+    function PrepareIntervals: TIntervalList; virtual;
     procedure SourceChanged(ASender: TObject); override;
   public
     procedure Assign(ASource: TPersistent); override;
@@ -1316,9 +1316,9 @@
   FIntervals := TIntervalList.Create;
   try
     if not (csoExtrapolateLeft in FOwner.Options) then
-      FIntervals.AddRange(NegInfinity, FX[0]);
+      FIntervals.AddRange(NegInfinity, FX[0], [ioOpenStart, ioOpenEnd]);
     if not (csoExtrapolateRight in FOwner.Options) then
-      FIntervals.AddRange(FX[High(FX)], SafeInfinity);
+      FIntervals.AddRange(FX[High(FX)], SafeInfinity, [ioOpenStart, ioOpenEnd]);
   except
     FreeAndNil(FIntervals);
     raise;
@@ -2162,8 +2162,8 @@
   try
     CalcXRange(xmin, xmax);
     if DrawFitRangeOnly then begin
-      Result.AddRange(NegInfinity, xmin);
-      Result.AddRange(xmax, SafeInfinity);
+      Result.AddRange(NegInfinity, xmin, [ioOpenStart, ioOpenEnd]);
+      Result.AddRange(xmax, SafeInfinity, [ioOpenStart, ioOpenEnd]);
     end;
   except
     Result.Free;
Index: components/tachart/test/UtilsTest.pas
===================================================================
--- components/tachart/test/UtilsTest.pas	(revision 60742)
+++ components/tachart/test/UtilsTest.pas	(working copy)
@@ -118,12 +118,39 @@
   r := 6.0;
   AssertTrue(FIList.Intersect(l, r, hint));
   AssertEquals(2.0, r);
-  FIList.Epsilon := 0.1;  // Meaning 10% of max exclusion edge, i.e. 0.2
-  l := 0.5;
-  r := 2.5;
+  FIList.Epsilon := 0.1;
+  FIList.AddRange(101.0, 102.0);
+  l := 100.5;
+  r := 102.5;
   AssertTrue(FIList.Intersect(l, r, hint));
-  AssertEquals(0.8, l);
-  AssertEquals(2.2, r);
+  AssertEquals(100.9, l);
+  AssertEquals(102.1, r);
+  FIList.Epsilon := -0.1;
+  FIList.AddRange(201.0, 202.0);
+  l := 200.5;
+  r := 202.5;
+  AssertTrue(FIList.Intersect(l, r, hint));
+  AssertEquals(201.1, l);
+  AssertEquals(201.9, r);
+  FIList.Epsilon := 0.1;
+  FIList.AddRange(301.0, 302.0, [ioOpenStart]);
+  l := 300.5;
+  r := 302.5;
+  AssertTrue(FIList.Intersect(l, r, hint));
+  AssertEquals(301.0, l);
+  AssertEquals(302.1, r);
+  FIList.AddRange(401.0, 402.0, [ioOpenEnd]);
+  l := 400.5;
+  r := 402.5;
+  AssertTrue(FIList.Intersect(l, r, hint));
+  AssertEquals(400.9, l);
+  AssertEquals(402.0, r);
+  FIList.AddRange(501.0, 502.0, [ioOpenStart, ioOpenEnd]);
+  l := 500.5;
+  r := 502.5;
+  AssertTrue(FIList.Intersect(l, r, hint));
+  AssertEquals(501.0, l);
+  AssertEquals(502.0, r);
 end;
 
 procedure TIntervalListTest.Merge;
solution2b.diff (16,881 bytes)

Marcin Wiazowski

2019-03-22 02:23

reporter   ~0114974

I'm attaching solution2b.diff. As I tested, all the "Reproduce" and "Epsilon" applications attached here work now properly. Thanks to ioOpenStart and ioOpenEnd options, fixes in tafuncseries.pas look now neat; I like it.

If you wish to add my name to the contributors' list, here it is:

const
  MyName = 'Marcin Wi'#$C4#$85'zowski'; // UTF-8

Thanks.

wp

2019-03-22 09:53

developer   ~0114977

Applied, thank you.

I hope I got the spelling of your name right. If not change it yourself and post the patch as usual.

Marcin Wiazowski

2019-03-22 19:04

reporter   ~0114984

Everything is ok. Thanks!

Issue History

Date Modified Username Field Change
2019-03-19 22:23 Marcin Wiazowski New Issue
2019-03-19 22:24 Marcin Wiazowski Note Added: 0114931
2019-03-19 22:24 Marcin Wiazowski Note Added: 0114932
2019-03-19 22:24 Marcin Wiazowski Note Added: 0114933
2019-03-19 22:25 Marcin Wiazowski File Added: Algorithm.png
2019-03-19 22:26 Marcin Wiazowski File Added: Reproduce1.zip
2019-03-19 22:26 Marcin Wiazowski File Added: Reproduce2.zip
2019-03-19 22:26 Marcin Wiazowski File Added: Reproduce3.zip
2019-03-19 22:26 Marcin Wiazowski File Added: Reproduce4.zip
2019-03-19 22:26 Marcin Wiazowski File Added: Reproduce5.zip
2019-03-19 22:27 Marcin Wiazowski File Added: Reproduce6.zip
2019-03-19 22:27 Marcin Wiazowski File Added: solution1.diff
2019-03-19 22:27 Marcin Wiazowski File Added: solution2.diff
2019-03-19 22:27 Marcin Wiazowski File Added: Reproduce1.gif
2019-03-19 22:28 Marcin Wiazowski File Added: Reproduce2.png
2019-03-19 22:28 Marcin Wiazowski File Added: Reproduce3.gif
2019-03-19 22:28 Marcin Wiazowski File Added: Reproduce4.png
2019-03-19 22:28 Marcin Wiazowski File Added: Reproduce5.png
2019-03-19 22:29 Marcin Wiazowski File Added: Reproduce6.gif
2019-03-20 15:50 wp Assigned To => wp
2019-03-20 15:50 wp Status new => assigned
2019-03-20 17:42 wp Note Added: 0114944
2019-03-20 18:09 wp Note Edited: 0114944 View Revisions
2019-03-20 18:10 wp Note Edited: 0114944 View Revisions
2019-03-20 22:17 Marcin Wiazowski File Added: Reproduce1verB.zip
2019-03-20 22:17 Marcin Wiazowski File Added: Reproduce2verB.zip
2019-03-20 22:17 Marcin Wiazowski File Added: Reproduce3verB.zip
2019-03-20 22:21 Marcin Wiazowski Note Added: 0114950
2019-03-20 23:52 wp Note Added: 0114951
2019-03-21 00:52 Marcin Wiazowski Note Added: 0114954
2019-03-21 13:57 wp Note Added: 0114960
2019-03-21 13:59 wp Note Edited: 0114960 View Revisions
2019-03-21 14:17 wp File Added: open_interval.zip
2019-03-21 14:17 wp File Added: open_interval.png
2019-03-21 18:54 Marcin Wiazowski Note Added: 0114966
2019-03-21 19:20 wp Note Added: 0114968
2019-03-21 21:51 Marcin Wiazowski File Added: Epsilons1.zip
2019-03-21 21:51 Marcin Wiazowski File Added: Epsilons2.zip
2019-03-21 21:52 Marcin Wiazowski File Added: Epsilons3.zip
2019-03-21 21:54 Marcin Wiazowski Note Added: 0114970
2019-03-21 23:42 wp Note Added: 0114971
2019-03-22 00:24 Marcin Wiazowski Note Added: 0114972
2019-03-22 00:38 wp Note Added: 0114973
2019-03-22 02:22 Marcin Wiazowski File Added: solution2b.diff
2019-03-22 02:23 Marcin Wiazowski Note Added: 0114974
2019-03-22 09:53 wp Fixed in Revision => 60740
2019-03-22 09:53 wp LazTarget => 2.2
2019-03-22 09:53 wp Note Added: 0114977
2019-03-22 09:53 wp Status assigned => resolved
2019-03-22 09:53 wp Resolution open => fixed
2019-03-22 09:53 wp Target Version => 2.2
2019-03-22 19:04 Marcin Wiazowski Note Added: 0114984
2019-03-22 19:04 Marcin Wiazowski Status resolved => closed