Robust/src/Benchmarks/SingleTM/Yada/element.java

   1 /* =============================================================================
   2  *
   3  * element.c
   4  *
   5  * =============================================================================
   6  *
   7  * Copyright (C) Stanford University, 2006.  All Rights Reserved.
   8  * Author: Chi Cao Minh
   9  *
  10  * =============================================================================
  11  *
  12  * For the license of bayes/sort.h and bayes/sort.c, please see the header
  13  * of the files.
  14  *
  15  * ------------------------------------------------------------------------
  16  *
  17  * For the license of kmeans, please see kmeans/LICENSE.kmeans
  18  *
  19  * ------------------------------------------------------------------------
  20  *
  21  * For the license of ssca2, please see ssca2/COPYRIGHT
  22  *
  23  * ------------------------------------------------------------------------
  24  *
  25  * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the
  26  * header of the files.
  27  *
  28  * ------------------------------------------------------------------------
  29  *
  30  * For the license of lib/rbtree.h and lib/rbtree.c, please see
  31  * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree
  32  *
  33  * ------------------------------------------------------------------------
  34  *
  35  * Unless otherwise noted, the following license applies to STAMP files:
  36  *
  37  * Copyright (c) 2007, Stanford University
  38  * All rights reserved.
  39  *
  40  * Redistribution and use in source and binary forms, with or without
  41  * modification, are permitted provided that the following conditions are
  42  * met:
  43  *
  44  *     * Redistributions of source code must retain the above copyright
  45  *       notice, this list of conditions and the following disclaimer.
  46  *
  47  *     * Redistributions in binary form must reproduce the above copyright
  48  *       notice, this list of conditions and the following disclaimer in
  49  *       the documentation and/or other materials provided with the
  50  *       distribution.
  51  *
  52  *     * Neither the name of Stanford University nor the names of its
  53  *       contributors may be used to endorse or promote products derived
  54  *       from this software without specific prior written permission.
  55  *
  56  * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
  57  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  58  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  59  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
  60  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  61  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  62  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  63  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  64  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  65  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
  66  * THE POSSIBILITY OF SUCH DAMAGE.
  67  *
  68  * =============================================================================
  69  */
  70
  71 public class element {
  72   coordinate coordinates[];
  73   int numCoordinate;
  74   coordinate circumCenter;
  75   double circumRadius;
  76   double minAngle;
  77   edge edges[];
  78   int numEdge;
  79   coordinate midpoints[]; /* midpoint of each edge */
  80   double radii[];           /* half of edge length */
  81   edge encroachedEdgePtr; /* opposite obtuse angle */
  82   boolean isSkinny;
  83   List_t neighborListPtr;
  84   boolean isGarbage;
  85   boolean isReferenced;
  86
  87
  88
  89 /* =============================================================================
  90  * minimizeCoordinates
  91  * -- put smallest coordinate in position 0
  92  * =============================================================================
  93  */
  94   void minimizeCoordinates() {
  95     int minPosition = 0;
  96
  97     for (int i = 1; i < numCoordinate; i++) {
  98       if (coordinate.coordinate_compare(coordinates[i], coordinates[minPosition]) < 0) {
  99         minPosition = i;
 100       }
 101     }
 102
 103     while(minPosition != 0) {
 104       coordinate tmp = coordinates[0];
 105       for (int j = 0; j < (numCoordinate - 1); j++) {
 106         coordinates[j] = coordinates[j+1];
 107       }
 108       coordinates[numCoordinate-1] = tmp;
 109       minPosition--;
 110     }
 111   }
 112
 113
 114 /* =============================================================================
 115  * checkAngles
 116  * -- Sets isSkinny to TRUE if the angle constraint is not met
 117  * =============================================================================
 118  */
 119   void checkAngles (double angleConstraint) {
 120     //double angleConstraint = global_angleConstraint;
 121     minAngle = 180.0;
 122
 123     yada.Assert(numCoordinate == 2 || numCoordinate == 3);
 124     isReferenced = false;
 125     isSkinny = false;
 126     encroachedEdgePtr = null;
 127
 128     if (numCoordinate == 3) {
 129         int i;
 130         for (i = 0; i < 3; i++) {
 131           double angle = coordinate.coordinate_angle(coordinates[i],
 132                                           coordinates[(i + 1) % 3],
 133                                           coordinates[(i + 2) % 3]);
 134           yada.Assert(angle > 0.0);
 135           yada.Assert(angle < 180.0);
 136           if (angle > 90.0) {
 137             encroachedEdgePtr = edges[(i + 1) % 3];
 138           }
 139           if (angle < angleConstraint) {
 140             isSkinny = true;
 141           }
 142           if (angle < minAngle) {
 143             minAngle = angle;
 144           }
 145         }
 146         yada.Assert(minAngle < 180.0);
 147     }
 148 }
 149
 150
 151 /* =============================================================================
 152  * calculateCircumCenter
 153  *
 154  * Given three points A(ax,ay), B(bx,by), C(cx,cy), circumcenter R(rx,ry):
 155  *
 156  *              |                         |
 157  *              | by - ay   (||b - a||)^2 |
 158  *              |                         |
 159  *              | cy - ay   (||c - a||)^2 |
 160  *              |                         |
 161  *   rx = ax - -----------------------------
 162  *                   |                   |
 163  *                   | bx - ax   by - ay |
 164  *               2 * |                   |
 165  *                   | cx - ax   cy - ay |
 166  *                   |                   |
 167  *
 168  *              |                         |
 169  *              | bx - ax   (||b - a||)^2 |
 170  *              |                         |
 171  *              | cx - ax   (||c - a||)^2 |
 172  *              |                         |
 173  *   ry = ay + -----------------------------
 174  *                   |                   |
 175  *                   | bx - ax   by - ay |
 176  *               2 * |                   |
 177  *                   | cx - ax   cy - ay |
 178  *                   |                   |
 179  *
 180  * =============================================================================
 181  */
 182   void calculateCircumCircle() {
 183     coordinate circumCenterPtr = this.circumCenter;
 184
 185     yada.Assert(numCoordinate == 2 || numCoordinate == 3);
 186
 187     if (numCoordinate == 2) {
 188       circumCenterPtr.x = (coordinates[0].x + coordinates[1].x) / 2.0;
 189       circumCenterPtr.y = (coordinates[0].y + coordinates[1].y) / 2.0;
 190     } else {
 191       double ax = coordinates[0].x;
 192       double ay = coordinates[0].y;
 193       double bx = coordinates[1].x;
 194       double by = coordinates[1].y;
 195       double cx = coordinates[2].x;
 196       double cy = coordinates[2].y;
 197       double bxDelta = bx - ax;
 198       double byDelta = by - ay;
 199       double cxDelta = cx - ax;
 200       double cyDelta = cy - ay;
 201       double bDistance2 = (bxDelta * bxDelta) + (byDelta * byDelta);
 202       double cDistance2 = (cxDelta * cxDelta) + (cyDelta * cyDelta);
 203       double xNumerator = (byDelta * cDistance2) - (cyDelta * bDistance2);
 204       double yNumerator = (bxDelta * cDistance2) - (cxDelta * bDistance2);
 205       double denominator = 2 * ((bxDelta * cyDelta) - (cxDelta * byDelta));
 206       double rx = ax - (xNumerator / denominator);
 207       double ry = ay + (yNumerator / denominator);
 208       yada.Assert(Math.fabs(denominator) > 2.2250738585072014e-308); /* make sure not colinear */
 209       circumCenterPtr.x = rx;
 210       circumCenterPtr.y = ry;
 211     }
 212
 213     circumRadius = coordinate.coordinate_distance(circumCenterPtr,
 214                                                   coordinates[0]);
 215   }
 216
 217
 218 /* =============================================================================
 219  * setEdge
 220  *
 221   * Note: Makes pairPtr sorted; i.e., coordinate_compare(first, second) < 0
 222  * =============================================================================
 223  */
 224   public void setEdge(int i) {
 225     coordinate firstPtr = coordinates[i];
 226     coordinate secondPtr = coordinates[(i + 1) % numCoordinate];
 227
 228     edge edgePtr = edges[i];
 229     int cmp = coordinate.coordinate_compare(firstPtr, secondPtr);
 230     yada.Assert(cmp != 0);
 231     if (cmp < 0) {
 232       edgePtr.firstPtr  = firstPtr;
 233       edgePtr.secondPtr = secondPtr;
 234     } else {
 235       edgePtr.firstPtr  = secondPtr;
 236       edgePtr.secondPtr = firstPtr;
 237     }
 238
 239     coordinate midpointPtr = midpoints[i];
 240     midpointPtr.x = (firstPtr.x + secondPtr.x) / 2.0;
 241     midpointPtr.y = (firstPtr.y + secondPtr.y) / 2.0;
 242
 243     radii[i] = coordinate.coordinate_distance(firstPtr, midpointPtr);
 244   }
 245
 246
 247 /* =============================================================================
 248  * initEdges
 249  * =============================================================================
 250  */
 251   void initEdges(coordinate[] coordinates, int numCoordinate) {
 252     numEdge = ((numCoordinate * (numCoordinate - 1)) / 2);
 253
 254     for (int e = 0; e < numEdge; e++) {
 255       setEdge(e);
 256     }
 257   }
 258
 259
 260 /* =============================================================================
 261  * element_compare
 262  * =============================================================================
 263  */
 264 int element_compare (element aElementPtr, element bElementPtr) {
 265   int aNumCoordinate = aElementPtr.numCoordinate;
 266   int bNumCoordinate = bElementPtr.numCoordinate;
 267   coordinate aCoordinates[] = aElementPtr.coordinates;
 268   coordinate bCoordinates[] = bElementPtr.coordinates;
 269
 270   if (aNumCoordinate < bNumCoordinate) {
 271     return -1;
 272   } else if (aNumCoordinate > bNumCoordinate) {
 273     return 1;
 274   }
 275
 276   for (int i = 0; i < aNumCoordinate; i++) {
 277     int compareCoordinate =
 278       coordinate.coordinate_compare(aCoordinates[i], bCoordinates[i]);
 279     if (compareCoordinate != 0) {
 280       return compareCoordinate;
 281     }
 282   }
 283
 284   return 0;
 285 }
 286
 287
 288 /* =============================================================================
 289  * element_listCompare
 290  *
 291  * For use in list_t
 292  * =============================================================================
 293  */
 294   int element_listCompare (Object aPtr, Object  bPtr) {
 295     element aElementPtr = (element)aPtr;
 296     element bElementPtr = (element)bPtr;
 297
 298     return element_compare(aElementPtr, bElementPtr);
 299   }
 300
 301
 302 /* =============================================================================
 303  * element_mapCompare
 304  *
 305  * For use in MAP_T
 306  * =============================================================================
 307  */
 308   int element_mapCompare(Object aPtr, Object bPtr) {
 309     element aElementPtr = (element)(((edge)aPtr).firstPtr);
 310     element bElementPtr = (element)(((edge)bPtr).firstPtr);
 311
 312     return element_compare(aElementPtr, bElementPtr);
 313   }
 314
 315
 316   /* =============================================================================
 317    * TMelement_alloc
 318    *
 319    * Contains a copy of input arg 'coordinates'
 320    * =============================================================================
 321    */
 322
 323   double angleConstraint;
 324   public element(coordinate[] coordinates, int numCoordinate, double angle) {
 325     this.coordinates=new coordinate[3];
 326     this.midpoints=new coordinate[3]; /* midpoint of each edge */
 327     this.radii=new double[3];           /* half of edge length */
 328
 329     this.edges=new edge[3];
 330     for (int i = 0; i < numCoordinate; i++) {
 331       this.coordinates[i] = coordinates[i];
 332     }
 333     this.numCoordinate = numCoordinate;
 334     minimizeCoordinates();
 335     this.angleConstraint=angle;
 336     checkAngles();
 337     calculateCircumCircle();
 338     initEdges(coordinates, numCoordinate);
 339     neighborListPtr = new List_t(0);//TMLIST_ALLOC(element_listCompare);
 340     isGarbage = false;
 341     isReferenced = false;
 342   }
 343
 344
 345 /* =============================================================================
 346  * element_getNumEdge
 347  * =============================================================================
 348  */
 349   int element_getNumEdge() {
 350     return numEdge;
 351   }
 352
 353
 354 /* =============================================================================
 355  * element_getEdge
 356  *
 357  * Returned edgePtr is sorted; i.e., coordinate_compare(first, second) < 0
 358  * =============================================================================
 359  */
 360   edge element_getEdge(int i) {
 361     if (i < 0 || i > numEdge)
 362       return null;
 363     return edges[i];
 364   }
 365
 366
 367 /* =============================================================================
 368  * element_compareEdge
 369  * =============================================================================
 370  */
 371   static int compareEdge(edge aEdgePtr, edge bEdgePtr) {
 372     int diffFirst = coordinate.coordinate_compare((coordinate)aEdgePtr.firstPtr,
 373                                         (coordinate)bEdgePtr.firstPtr);
 374
 375     return ((diffFirst != 0) ?
 376             (diffFirst) :
 377             (coordinate.coordinate_compare((coordinate)aEdgePtr.secondPtr,
 378                                 (coordinate)bEdgePtr.secondPtr)));
 379   }
 380
 381
 382 /* ============================================================================
 383  * element_listCompareEdge
 384  *
 385  * For use in list_t
 386  * ============================================================================
 387  */
 388   int element_listCompareEdge (Object aPtr, Object bPtr) {
 389     edge aEdgePtr = (edge)(aPtr);
 390     edge bEdgePtr = (edge)(bPtr);
 391
 392     return compareEdge(aEdgePtr, bEdgePtr);
 393   }
 394
 395
 396 /* =============================================================================
 397  * element_mapCompareEdge
 398  *
 399   * For use in MAP_T
 400  * =============================================================================
 401  */
 402   int element_mapCompareEdge (edge aPtr, edge bPtr) {
 403     edge aEdgePtr = (edge)(aPtr.firstPtr);
 404     edge bEdgePtr = (edge)(bPtr.firstPtr);
 405
 406     return compareEdge(aEdgePtr, bEdgePtr);
 407   }
 408
 409
 410 /* =============================================================================
 411  * element_heapCompare
 412  *
 413  * For use in heap_t. Consider using minAngle instead of "do not care".
 414  * =============================================================================
 415  */
 416   int element_heapCompare (Object aPtr, Object bPtr) {
 417     element aElementPtr = (element)aPtr;
 418     element bElementPtr = (element)bPtr;
 419
 420     if (aElementPtr.encroachedEdgePtr!=null) {
 421       if (bElementPtr.encroachedEdgePtr!=null) {
 422         return 0; /* do not care */
 423       } else {
 424         return 1;
 425       }
 426     }
 427
 428     if (bElementPtr.encroachedEdgePtr!=null) {
 429       return -1;
 430     }
 431
 432     return 0; /* do not care */
 433   }
 434
 435
 436 /* =============================================================================
 437  * element_isInCircumCircle
 438  * =============================================================================
 439  */
 440   boolean element_isInCircumCircle(coordinate coordinatePtr) {
 441     double distance = coordinate.coordinate_distance(coordinatePtr, circumCenter);
 442     return distance <= circumRadius;
 443   }
 444
 445
 446 /* =============================================================================
 447  * isEncroached
 448  * =============================================================================
 449  */
 450   boolean isEncroached() {
 451     return encroachedEdgePtr!=null;
 452   }
 453
 454
 455 /* =============================================================================
 456  * element_setEncroached
 457  * =============================================================================
 458  */
 459   void element_clearEncroached() {
 460     encroachedEdgePtr = null;
 461   }
 462
 463
 464 /* =============================================================================
 465  * element_getEncroachedPtr
 466  * =============================================================================
 467  */
 468   edge element_getEncroachedPtr() {
 469     return encroachedEdgePtr;
 470   }
 471
 472
 473 /* =============================================================================
 474  * element_isSkinny
 475  * =============================================================================
 476  */
 477   boolean element_isSkinny() {
 478     return isSkinny;
 479   }
 480
 481
 482 /* =============================================================================
 483  * element_isBad
 484  * -- Does it need to be refined?
 485  * =============================================================================
 486  */
 487   boolean element_isBad() {
 488     return (isEncroached() || element_isSkinny());
 489   }
 490
 491
 492 /* =============================================================================
 493  * TMelement_isReferenced
 494  * -- Held by another data structure?
 495  * =============================================================================
 496  */
 497   boolean element_isReferenced () {
 498     return isReferenced;
 499   }
 500
 501
 502 /* =============================================================================
 503  * TMelement_setIsReferenced
 504  * =============================================================================
 505  */
 506   void element_setIsReferenced(boolean status) {
 507     isReferenced= status;
 508   }
 509
 510
 511 /* =============================================================================
 512  * element_isGarbage
 513  * -- Can we deallocate?
 514  * =============================================================================
 515  */
 516
 517 /* =============================================================================
 518  * TMelement_isGarbage
 519  * -- Can we deallocate?
 520  * =============================================================================
 521  */
 522   public boolean element_isGarbage() {
 523     return isGarbage;
 524   }
 525
 526
 527
 528 /* =============================================================================
 529  * TMelement_setIsGarbage
 530  * =============================================================================
 531  */
 532   void element_setIsGarbage(boolean status) {
 533     isGarbage=status;
 534   }
 535
 536
 537 /* =============================================================================
 538  * TMelement_addNeighbor
 539  * =============================================================================
 540  */
 541   void element_addNeighbor(element neighborPtr) {
 542     neighborListPtr.insert(neighborPtr);
 543   }
 544
 545
 546 /* =============================================================================
 547  * element_getNeighborListPtr
 548  * =============================================================================
 549  */
 550   List_t element_getNeighborListPtr () {
 551     return neighborListPtr;
 552   }
 553
 554
 555 /* =============================================================================
 556  * element_getCommonEdge
 557  *
 558  * Returns pointer to aElementPtr's shared edge
 559  * =============================================================================
 560  */
 561   static edge element_getCommonEdge (element aElementPtr, element bElementPtr) {
 562     edge aEdges[] = aElementPtr.edges;
 563     edge bEdges[] = bElementPtr.edges;
 564     int aNumEdge = aElementPtr.numEdge;
 565     int bNumEdge = bElementPtr.numEdge;
 566
 567     for (int a = 0; a < aNumEdge; a++) {
 568       edge aEdgePtr = aEdges[a];
 569       for (int b = 0; b < bNumEdge; b++) {
 570         edge bEdgePtr = bEdges[b];
 571         if (compareEdge(aEdgePtr, bEdgePtr) == 0) {
 572           return aEdgePtr;
 573         }
 574       }
 575     }
 576
 577     return null;
 578   }
 579
 580
 581 /* =============================================================================
 582  * element_getNewPoint
 583  * -- Either the element is encroached or is skinny, so get the new point to add
 584  * =============================================================================
 585  */
 586   coordinate element_getNewPoint() {
 587     if (encroachedEdgePtr!=null) {
 588       for (int e = 0; e < numEdge; e++) {
 589         if (compareEdge(encroachedEdgePtr, edges[e]) == 0) {
 590           return midpoints[e];
 591         }
 592       }
 593       yada.Assert(false);
 594     }
 595     return circumCenter;
 596   }
 597
 598
 599 /* =============================================================================
 600  * element_checkAngles
 601  *
 602  * Return FALSE if minimum angle constraint not met
 603  * =============================================================================
 604  */
 605   boolean checkAngles() {
 606     //    double angleConstraint = global_angleConstraint;
 607     if (numCoordinate == 3) {
 608       for (int i = 0; i < 3; i++) {
 609         double angle = coordinate.coordinate_angle(coordinates[i],
 610                                         coordinates[(i + 1) % 3],
 611                                         coordinates[(i + 2) % 3]);
 612         if (angle < angleConstraint) {
 613           return false;
 614         }
 615       }
 616     }
 617     return true;
 618   }
 619
 620
 621 /* =============================================================================
 622  * element_print
 623  * =============================================================================
 624  */
 625   void element_print() {
 626     for (int c = 0; c < numCoordinate; c++) {
 627       coordinates[c].coordinate_print();
 628       System.out.println(" ");
 629     }
 630   }
 631
 632
 633 /* =============================================================================
 634  * element_printEdge
 635  * =============================================================================
 636  */
 637   void element_printEdge (edge edgePtr) {
 638     ((coordinate)edgePtr.firstPtr).coordinate_print();
 639     System.out.println(" -> ");
 640     ((coordinate)edgePtr.secondPtr).coordinate_print();
 641   }
 642
 643
 644 /* =============================================================================
 645  * element_printAngles
 646  * =============================================================================
 647  */
 648   void element_printAngles() {
 649     if (numCoordinate == 3) {
 650       for (int i = 0; i < 3; i++) {
 651         double angle = coordinate.coordinate_angle(coordinates[i],
 652                                         coordinates[(i + 1) % 3],
 653                                         coordinates[(i + 2) % 3]);
 654         System.out.println(angle);
 655       }
 656     }
 657   }
 658 }