org.eclipse.linuxtools.tmf.core/src/org/eclipse/linuxtools/internal/tmf/core/synchronization/SyncAlgorithmFullyIncremental.java

   1 /*******************************************************************************
   2  * Copyright (c) 2013 École Polytechnique de Montréal
   3  *
   4  * All rights reserved. This program and the accompanying materials are made
   5  * available under the terms of the Eclipse Public License v1.0 which
   6  * accompanies this distribution, and is available at
   7  * http://www.eclipse.org/legal/epl-v10.html
   8  *
   9  * Contributors:
  10  *   Geneviève Bastien - Initial implementation and API
  11  *   Francis Giraldeau - Transform computation using synchronization graph
  12  *******************************************************************************/
  13
  14 package org.eclipse.linuxtools.internal.tmf.core.synchronization;
  15
  16 import java.io.IOException;
  17 import java.io.ObjectOutputStream;
  18 import java.io.Serializable;
  19 import java.math.BigDecimal;
  20 import java.math.MathContext;
  21 import java.util.Collection;
  22 import java.util.LinkedHashMap;
  23 import java.util.LinkedList;
  24 import java.util.List;
  25 import java.util.Map;
  26
  27 import org.eclipse.linuxtools.internal.tmf.core.synchronization.graph.SyncSpanningTree;
  28 import org.eclipse.linuxtools.tmf.core.event.ITmfEvent;
  29 import org.eclipse.linuxtools.tmf.core.event.matching.TmfEventDependency;
  30 import org.eclipse.linuxtools.tmf.core.synchronization.ITmfTimestampTransform;
  31 import org.eclipse.linuxtools.tmf.core.synchronization.Messages;
  32 import org.eclipse.linuxtools.tmf.core.synchronization.SynchronizationAlgorithm;
  33 import org.eclipse.linuxtools.tmf.core.synchronization.TimestampTransformFactory;
  34 import org.eclipse.linuxtools.tmf.core.timestamp.ITmfTimestamp;
  35 import org.eclipse.linuxtools.tmf.core.trace.ITmfTrace;
  36
  37 /**
  38  * Class implementing fully incremental trace synchronization approach as
  39  * described in
  40  *
  41  * Masoume Jabbarifar, Michel Dagenais and Alireza Shameli-Sendi,
  42  * "Streaming Mode Incremental Clock Synchronization"
  43  *
  44  * Since the algorithm itself applies to two traces, it is implemented in a
  45  * private class, while this public class manages the synchronization between
  46  * all traces.
  47  *
  48  * @author Geneviève Bastien
  49  */
  50 public class SyncAlgorithmFullyIncremental extends SynchronizationAlgorithm {
  51
  52     /**
  53      * Auto-generated serial UID
  54      */
  55     private static final long serialVersionUID = -1782788842774838830L;
  56
  57     private static final MathContext fMc = MathContext.DECIMAL128;
  58
  59     /** @Serial */
  60     private final List<ConvexHull> fSyncs;
  61
  62     private SyncSpanningTree fTree = null;
  63
  64     /**
  65      * Initialization of the attributes
  66      */
  67     public SyncAlgorithmFullyIncremental() {
  68         fSyncs = new LinkedList<>();
  69     }
  70
  71     /**
  72      * Function called after all matching has been done, to do any post-match
  73      * treatment. For this class, it calculates stats, while the data is
  74      * available
  75      */
  76     @Override
  77     public void matchingEnded() {
  78         getStats();
  79     }
  80
  81     @Override
  82     public void init(Collection<ITmfTrace> traces) {
  83         ITmfTrace[] traceArr = traces.toArray(new ITmfTrace[traces.size()]);
  84         fSyncs.clear();
  85         /* Create a convex hull for all trace pairs */
  86         // FIXME: is it necessary to make ConvexHull for every pairs up-front?
  87         // The ConvexHull seems to be created on the fly in processMatch().
  88         for (int i = 0; i < traceArr.length; i++) {
  89             for (int j = i + 1; j < traceArr.length; j++) {
  90                 if (!traceArr[i].getHostId().equals(traceArr[j].getHostId())) {
  91                     ConvexHull algo = new ConvexHull(traceArr[i].getHostId(), traceArr[j].getHostId());
  92                     fSyncs.add(algo);
  93                 }
  94             }
  95         }
  96     }
  97
  98     @Override
  99     protected void processMatch(TmfEventDependency match) {
 100         String host1 = match.getSourceEvent().getTrace().getHostId();
 101         String host2 = match.getDestinationEvent().getTrace().getHostId();
 102
 103         /* Process only if source and destination are different */
 104         if (host1.equals(host2)) {
 105             return;
 106         }
 107
 108         /* Check if a convex hull algorithm already exists for these 2 hosts */
 109         ConvexHull algo = null;
 110         for (ConvexHull traceSync : fSyncs) {
 111             if (traceSync.isForHosts(host1, host2)) {
 112                 algo = traceSync;
 113             }
 114         }
 115         if (algo == null) {
 116             algo = new ConvexHull(host1, host2);
 117             fSyncs.add(algo);
 118         }
 119         algo.processMatch(match);
 120         invalidateSyncGraph();
 121     }
 122
 123     private void invalidateSyncGraph() {
 124         fTree = null;
 125     }
 126
 127     @Override
 128     public ITmfTimestampTransform getTimestampTransform(ITmfTrace trace) {
 129         return getTimestampTransform(trace.getHostId());
 130     }
 131
 132     @Override
 133     public ITmfTimestampTransform getTimestampTransform(String hostId) {
 134         SyncSpanningTree tree = getSyncTree();
 135         return tree.getTimestampTransform(hostId);
 136     }
 137
 138     /**
 139      * Each convex hull computes the synchronization between 2 given hosts. A
 140      * synchronization can be done on multiple hosts that may not all
 141      * communicate with each other. We must use another algorithm to determine
 142      * which host will be the reference node and what synchronization formula
 143      * will be used between each host and this reference node.
 144      *
 145      * For example, take traces a, b and c where a and c talk to b but do not
 146      * know each other ({@literal a <-> b <-> c}). The convex hulls will contain
 147      * the formulae between their 2 traces, but if a is the reference node, then
 148      * the resulting formula of c would be the composition of {@literal a <-> b}
 149      * and {@literal b <-> c}
 150      *
 151      * @return The synchronization spanning tree for this synchronization
 152      */
 153     private SyncSpanningTree getSyncTree() {
 154         if (fTree == null) {
 155             fTree = new SyncSpanningTree();
 156             for (ConvexHull traceSync : fSyncs) {
 157                 SyncQuality q = traceSync.getQuality();
 158                 if (q == SyncQuality.ACCURATE || q == SyncQuality.APPROXIMATE) {
 159                     String from = traceSync.getReferenceHost();
 160                     String to = traceSync.getOtherHost();
 161                     fTree.addSynchronization(from, to, traceSync.getTimestampTransform(to), traceSync.getAccuracy());
 162                 }
 163             }
 164         }
 165         return fTree;
 166     }
 167
 168     @Override
 169     public SyncQuality getSynchronizationQuality(ITmfTrace trace1, ITmfTrace trace2) {
 170         for (ConvexHull traceSync : fSyncs) {
 171             if (traceSync.isForHosts(trace1.getHostId(), trace2.getHostId())) {
 172                 return traceSync.getQuality();
 173             }
 174         }
 175         return SyncQuality.ABSENT;
 176     }
 177
 178     @Override
 179     public boolean isTraceSynced(String hostId) {
 180         ITmfTimestampTransform t = getTimestampTransform(hostId);
 181         return !t.equals(TimestampTransformFactory.getDefaultTransform());
 182     }
 183
 184     @Override
 185     public Map<String, Map<String, Object>> getStats() {
 186         /*
 187          * TODO: Stats, while still accurate, may be misleading now that the
 188          * sync tree changes synchronization formula. The stats should use the
 189          * tree instead
 190          */
 191         Map<String, Map<String, Object>> statmap = new LinkedHashMap<>();
 192         for (ConvexHull traceSync : fSyncs) {
 193             statmap.put(traceSync.getReferenceHost() + " <==> " + traceSync.getOtherHost(), traceSync.getStats()); //$NON-NLS-1$
 194         }
 195         return statmap;
 196     }
 197
 198     @Override
 199     public String toString() {
 200         StringBuilder b = new StringBuilder();
 201         b.append(getClass().getSimpleName() + " "); //$NON-NLS-1$
 202         b.append(fSyncs);
 203         return b.toString();
 204     }
 205
 206     /**
 207      * This is the actual synchronization algorithm between two traces using
 208      * convex hull
 209      */
 210     private class ConvexHull implements Serializable {
 211
 212         private static final long serialVersionUID = 8309351175030935291L;
 213
 214         /**
 215          * The list of meaningful points on the upper hull (received by the
 216          * reference trace, below in a graph)
 217          */
 218         private final LinkedList<SyncPoint> fUpperBoundList = new LinkedList<>();
 219
 220         /**
 221          * The list of meaninful points on the lower hull (sent by the reference
 222          * trace, above in a graph)
 223          */
 224         private final LinkedList<SyncPoint> fLowerBoundList = new LinkedList<>();
 225
 226         /** Points forming the line with maximum slope */
 227         private final SyncPoint[] fLmax;
 228
 229         /** Points forming the line with minimum slope */
 230         private final SyncPoint[] fLmin;
 231
 232         /**
 233          * Slopes and ordinate at origin of respectively fLmin, fLmax and the
 234          * bisector
 235          */
 236         private BigDecimal fAlphamin, fBetamax, fAlphamax, fBetamin, fAlpha, fBeta;
 237
 238         private int fNbMatches, fNbAccurateMatches;
 239         private String fReferenceHost = "", fOtherHost = ""; //$NON-NLS-1$//$NON-NLS-2$
 240         private SyncQuality fQuality;
 241
 242         private Map<String, Object> fStats = new LinkedHashMap<>();
 243
 244         /**
 245          * Initialization of the attributes
 246          *
 247          * @param host1
 248          *            ID of the first host
 249          * @param host2
 250          *            ID of the second host
 251          */
 252         public ConvexHull(String host1, String host2) {
 253             if (host1.compareTo(host2) > 0) {
 254                 fReferenceHost = host2;
 255                 fOtherHost = host1;
 256             } else {
 257                 fReferenceHost = host1;
 258                 fOtherHost = host2;
 259             }
 260             fLmax = new SyncPoint[2];
 261             fLmin = new SyncPoint[2];
 262             fAlpha = BigDecimal.ONE;
 263             fAlphamax = BigDecimal.ONE;
 264             fAlphamin = BigDecimal.ONE;
 265             fBeta = BigDecimal.ZERO;
 266             fBetamax = BigDecimal.ZERO;
 267             fBetamin = BigDecimal.ZERO;
 268             fNbMatches = 0;
 269             fNbAccurateMatches = 0;
 270             fQuality = SyncQuality.ABSENT; // default quality
 271         }
 272
 273         protected void processMatch(TmfEventDependency match) {
 274
 275             LinkedList<SyncPoint> boundList, otherBoundList;
 276
 277             SyncPoint[] line, otherLine;
 278             SyncPoint p;
 279             int inversionFactor = 1;
 280             boolean qualify = false;
 281             fNbMatches++;
 282
 283             /* Initialize data depending on the which hull the match is part of */
 284             if (match.getSourceEvent().getTrace().getHostId().compareTo(match.getDestinationEvent().getTrace().getHostId()) > 0) {
 285                 boundList = fUpperBoundList;
 286                 otherBoundList = fLowerBoundList;
 287                 line = fLmin;
 288                 otherLine = fLmax;
 289                 p = new SyncPoint(match.getDestinationEvent(), match.getSourceEvent());
 290                 inversionFactor = 1;
 291             } else {
 292                 boundList = fLowerBoundList;
 293                 otherBoundList = fUpperBoundList;
 294                 line = fLmax;
 295                 otherLine = fLmin;
 296                 p = new SyncPoint(match.getSourceEvent(), match.getDestinationEvent());
 297                 inversionFactor = -1;
 298             }
 299
 300             /*
 301              * Does the message qualify for the hull, or is in on the wrong side
 302              * of the reference line
 303              */
 304             if ((line[0] == null) || (line[1] == null) || (p.crossProduct(line[0], line[1]) * inversionFactor > 0)) {
 305                 /*
 306                  * If message qualifies, verify if points need to be removed
 307                  * from the hull and add the new point as the maximum reference
 308                  * point for the line. Also clear the stats that are not good
 309                  * anymore
 310                  */
 311                 fNbAccurateMatches++;
 312                 qualify = true;
 313                 removeUselessPoints(p, boundList, inversionFactor);
 314                 line[1] = p;
 315                 fStats.clear();
 316             }
 317
 318             /*
 319              * Adjust the boundary of the reference line and if one of the
 320              * reference point of the other line was removed from the hull, also
 321              * adjust the other line
 322              */
 323             adjustBound(line, otherBoundList, inversionFactor);
 324             if ((otherLine[1] != null) && !boundList.contains(otherLine[0])) {
 325                 adjustBound(otherLine, boundList, inversionFactor * -1);
 326             }
 327
 328             if (qualify) {
 329                 approximateSync();
 330             }
 331
 332         }
 333
 334         /**
 335          * Calculates slopes and ordinate at origin of fLmax and fLmin to obtain
 336          * and approximation of the synchronization at this time
 337          */
 338         private void approximateSync() {
 339
 340             /**
 341              * Line slopes functions
 342              *
 343              * Lmax = alpha_max T + beta_min
 344              *
 345              * Lmin = alpha_min T + beta_max
 346              */
 347             if ((fLmax[0] != null) || (fLmin[0] != null)) {
 348                 /**
 349                  * Do not recalculate synchronization after it is failed. We
 350                  * keep the last not failed result.
 351                  */
 352                 if (getQuality() != SyncQuality.FAIL) {
 353                     BigDecimal alphamax = fLmax[1].getAlpha(fLmax[0]);
 354                     BigDecimal alphamin = fLmin[1].getAlpha(fLmin[0]);
 355                     SyncQuality quality = null;
 356
 357                     if ((fLmax[0] == null) || (fLmin[0] == null)) {
 358                         quality = SyncQuality.APPROXIMATE;
 359                     }
 360                     else if (alphamax.compareTo(alphamin) > 0) {
 361                         quality = SyncQuality.ACCURATE;
 362                     } else {
 363                         /* Lines intersect, not good */
 364                         quality = SyncQuality.FAIL;
 365                     }
 366                     /*
 367                      * Only calculate sync if this match does not cause failure
 368                      * of synchronization
 369                      */
 370                     if (quality != SyncQuality.FAIL) {
 371                         fAlphamax = alphamax;
 372                         fBetamin = fLmax[1].getBeta(fAlphamax);
 373                         fAlphamin = alphamin;
 374                         fBetamax = fLmin[1].getBeta(fAlphamin);
 375                         fAlpha = fAlphamax.add(fAlphamin).divide(BigDecimal.valueOf(2), fMc);
 376                         fBeta = fBetamin.add(fBetamax).divide(BigDecimal.valueOf(2), fMc);
 377                     }
 378                     setQuality(quality);
 379                 }
 380             } else if (((fLmax[0] == null) && (fLmin[1] == null))
 381                     || ((fLmax[1] == null) && (fLmin[0] == null))) {
 382                 /* Either there is no upper hull point or no lower hull */
 383                 setQuality(SyncQuality.INCOMPLETE);
 384             }
 385         }
 386
 387         /*
 388          * Verify if the line should be adjusted to be more accurate give the
 389          * hull
 390          */
 391         private void adjustBound(SyncPoint[] line, LinkedList<SyncPoint> otherBoundList, int inversionFactor) {
 392             SyncPoint minPoint = null, nextPoint;
 393             boolean finishedSearch = false;
 394
 395             /*
 396              * Find in the other bound, the origin point of the line, start from
 397              * the beginning if the point was lost
 398              */
 399             int i = Math.max(0, otherBoundList.indexOf(line[0]));
 400
 401             while ((i < otherBoundList.size() - 1) && !finishedSearch) {
 402                 minPoint = otherBoundList.get(i);
 403                 nextPoint = otherBoundList.get(i + 1);
 404
 405                 /*
 406                  * If the rotation (cross-product) is not optimal, move to next
 407                  * point as reference for the line (if available)
 408                  *
 409                  * Otherwise, the current minPoint is the minPoint of the line
 410                  */
 411                 if (minPoint.crossProduct(nextPoint, line[1]) * inversionFactor > 0) {
 412                     if (nextPoint.getTimeX() < line[1].getTimeX()) {
 413                         i++;
 414                     } else {
 415                         line[0] = null;
 416                         finishedSearch = true;
 417                     }
 418                 } else {
 419                     line[0] = minPoint;
 420                     finishedSearch = true;
 421                 }
 422             }
 423
 424             if (line[0] == null) {
 425                 line[0] = minPoint;
 426             }
 427
 428             /* Make sure point 0 is before point 1 */
 429             if ((line[0] != null) && (line[0].getTimeX() > line[1].getTimeX())) {
 430                 line[0] = null;
 431             }
 432         }
 433
 434         /*
 435          * When a point qualifies to be in a hull, we verify if any of the
 436          * existing points need to be removed from the hull
 437          */
 438         private void removeUselessPoints(final SyncPoint p, final LinkedList<SyncPoint> boundList, final int inversionFactor) {
 439
 440             boolean checkRemove = true;
 441
 442             while (checkRemove && boundList.size() >= 2) {
 443                 if (p.crossProduct(boundList.get(boundList.size() - 2), boundList.getLast()) * inversionFactor > 0) {
 444                     boundList.removeLast();
 445                 } else {
 446                     checkRemove = false;
 447                 }
 448             }
 449             boundList.addLast(p);
 450         }
 451
 452         public ITmfTimestampTransform getTimestampTransform(String hostId) {
 453             if (hostId.equals(fOtherHost) && (getQuality() == SyncQuality.ACCURATE || getQuality() == SyncQuality.APPROXIMATE || getQuality() == SyncQuality.FAIL)) {
 454                 /* alpha: beta => 1 / fAlpha, -1 * fBeta / fAlpha); */
 455                 return TimestampTransformFactory.createLinear(BigDecimal.ONE.divide(fAlpha, fMc), BigDecimal.valueOf(-1).multiply(fBeta).divide(fAlpha, fMc));
 456             }
 457             return TimestampTransformFactory.getDefaultTransform();
 458         }
 459
 460         public SyncQuality getQuality() {
 461             return fQuality;
 462         }
 463
 464         public BigDecimal getAccuracy() {
 465             return fAlphamax.subtract(fAlphamin);
 466         }
 467
 468         public Map<String, Object> getStats() {
 469             if (fStats.size() == 0) {
 470                 String syncQuality;
 471                 switch (getQuality()) {
 472                 case ABSENT:
 473                     syncQuality = Messages.SyncAlgorithmFullyIncremental_absent;
 474                     break;
 475                 case ACCURATE:
 476                     syncQuality = Messages.SyncAlgorithmFullyIncremental_accurate;
 477                     break;
 478                 case APPROXIMATE:
 479                     syncQuality = Messages.SyncAlgorithmFullyIncremental_approx;
 480                     break;
 481                 case INCOMPLETE:
 482                     syncQuality = Messages.SyncAlgorithmFullyIncremental_incomplete;
 483                     break;
 484                 case FAIL:
 485                 default:
 486                     syncQuality = Messages.SyncAlgorithmFullyIncremental_fail;
 487                     break;
 488                 }
 489
 490                 fStats.put(Messages.SyncAlgorithmFullyIncremental_refhost, fReferenceHost);
 491                 fStats.put(Messages.SyncAlgorithmFullyIncremental_otherhost, fOtherHost);
 492                 fStats.put(Messages.SyncAlgorithmFullyIncremental_quality, syncQuality);
 493                 fStats.put(Messages.SyncAlgorithmFullyIncremental_alpha, fAlpha);
 494                 fStats.put(Messages.SyncAlgorithmFullyIncremental_beta, fBeta);
 495                 fStats.put(Messages.SyncAlgorithmFullyIncremental_ub, (fUpperBoundList.size() == 0) ? Messages.SyncAlgorithmFullyIncremental_NA : fUpperBoundList.size());
 496                 fStats.put(Messages.SyncAlgorithmFullyIncremental_lb, (fLowerBoundList.size() == 0) ? Messages.SyncAlgorithmFullyIncremental_NA : fLowerBoundList.size());
 497                 fStats.put(Messages.SyncAlgorithmFullyIncremental_accuracy, getAccuracy().doubleValue());
 498                 fStats.put(Messages.SyncAlgorithmFullyIncremental_nbmatch, (fNbMatches == 0) ? Messages.SyncAlgorithmFullyIncremental_NA : fNbMatches);
 499                 fStats.put(Messages.SyncAlgorithmFullyIncremental_nbacc, (fNbAccurateMatches == 0) ? Messages.SyncAlgorithmFullyIncremental_NA : fNbAccurateMatches);
 500                 fStats.put(Messages.SyncAlgorithmFullyIncremental_refformula, Messages.SyncAlgorithmFullyIncremental_T_ + fReferenceHost);
 501                 fStats.put(Messages.SyncAlgorithmFullyIncremental_otherformula, fAlpha + Messages.SyncAlgorithmFullyIncremental_mult + Messages.SyncAlgorithmFullyIncremental_T_ + fReferenceHost + Messages.SyncAlgorithmFullyIncremental_add + fBeta);
 502             }
 503             return fStats;
 504
 505         }
 506
 507         public String getReferenceHost() {
 508             return fReferenceHost;
 509         }
 510
 511         public String getOtherHost() {
 512             return fOtherHost;
 513         }
 514
 515         public boolean isForHosts(String hostId1, String hostId2) {
 516             return ((fReferenceHost.equals(hostId1) && fOtherHost.equals(hostId2)) || (fReferenceHost.equals(hostId2) && fOtherHost.equals(hostId1)));
 517         }
 518
 519         private void writeObject(ObjectOutputStream s)
 520                 throws IOException {
 521             /*
 522              * Remove calculation data because most of it is not serializable.
 523              * We have the statistics anyway
 524              */
 525             fUpperBoundList.clear();
 526             fLowerBoundList.clear();
 527             fLmin[0] = null;
 528             fLmin[1] = null;
 529             fLmax[0] = null;
 530             fLmax[1] = null;
 531             s.defaultWriteObject();
 532         }
 533
 534         @SuppressWarnings("nls")
 535         @Override
 536         public String toString() {
 537             StringBuilder b = new StringBuilder();
 538             b.append("Between " + fReferenceHost + " and " + fOtherHost + " [");
 539             b.append(" alpha " + fAlpha + " beta " + fBeta + " ]");
 540             return b.toString();
 541         }
 542
 543         private void setQuality(SyncQuality fQuality) {
 544             this.fQuality = fQuality;
 545         }
 546
 547     }
 548
 549     /**
 550      * Private class representing a point to synchronize on a graph. The x axis
 551      * is the timestamp of the event from the reference trace while the y axis
 552      * is the timestamp of the event on the other trace
 553      */
 554     private class SyncPoint {
 555         private final ITmfTimestamp x, y;
 556
 557         public SyncPoint(ITmfEvent ex, ITmfEvent ey) {
 558             x = ex.getTimestamp();
 559             y = ey.getTimestamp();
 560         }
 561
 562         public long getTimeX() {
 563             return x.getValue();
 564         }
 565
 566         /**
 567          * Calculate a cross product of 3 points:
 568          *
 569          * If the cross-product < 0, then p, pa, pb are clockwise
 570          *
 571          * If the cross-product > 0, then p, pa, pb are counter-clockwise
 572          *
 573          * If cross-product == 0, then they are in a line
 574          *
 575          * @param pa
 576          *            First point
 577          * @param pb
 578          *            Second point
 579          * @return The cross product
 580          */
 581         public long crossProduct(SyncPoint pa, SyncPoint pb) {
 582             long cp = ((pa.x.getValue() - x.getValue()) * (pb.y.getValue() - y.getValue()) - (pa.y.getValue() - y.getValue()) * (pb.x.getValue() - x.getValue()));
 583             return cp;
 584         }
 585
 586         /*
 587          * Gets the alpha (slope) between two points
 588          */
 589         public BigDecimal getAlpha(SyncPoint p1) {
 590             if (p1 == null) {
 591                 return BigDecimal.ONE;
 592             }
 593             BigDecimal deltay = BigDecimal.valueOf(y.getValue() - p1.y.getValue());
 594             BigDecimal deltax = BigDecimal.valueOf(x.getValue() - p1.x.getValue());
 595             if (deltax.equals(BigDecimal.ZERO)) {
 596                 return BigDecimal.ONE;
 597             }
 598             return deltay.divide(deltax, fMc);
 599         }
 600
 601         /*
 602          * Get the beta value (when x = 0) of the line given alpha
 603          */
 604         public BigDecimal getBeta(BigDecimal alpha) {
 605             return BigDecimal.valueOf(y.getValue()).subtract(alpha.multiply(BigDecimal.valueOf(x.getValue()), fMc));
 606         }
 607
 608         @Override
 609         public String toString() {
 610             return String.format("%s (%s,  %s)", this.getClass().getCanonicalName(), x, y); //$NON-NLS-1$
 611         }
 612     }
 613
 614     private void writeObject(ObjectOutputStream s)
 615             throws IOException {
 616         /*
 617          * Remove the tree because it is not serializable
 618          */
 619         fTree = null;
 620         s.defaultWriteObject();
 621     }
 622
 623 }