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() {
 120     minAngle = 180.0;
 121     yada.Assert(numCoordinate == 2 || numCoordinate == 3);
 122     isReferenced = false;
 123     isSkinny = false;
 124     encroachedEdgePtr = null;
 125
 126     if (numCoordinate == 3) {
 127       for (int i = 0; i < 3; i++) {
 128         double angle = coordinate.coordinate_angle(coordinates[i],
 129                                                    coordinates[(i + 1) % 3],
 130                                                    coordinates[(i + 2) % 3]);
 131         yada.Assert(angle > 0.0);
 132         yada.Assert(angle < 180.0);
 133         if (angle > 90.0) {
 134           encroachedEdgePtr = edges[(i + 1) % 3];
 135         }
 136         if (angle < angleConstraint) {
 137           isSkinny = true;
 138         }
 139         if (angle < minAngle) {
 140           minAngle = angle;
 141         }
 142       }
 143       yada.Assert(minAngle < 180.0);
 144     }
 145   }
 146
 147
 148 /* =============================================================================
 149  * calculateCircumCenter
 150  *
 151  * Given three points A(ax,ay), B(bx,by), C(cx,cy), circumcenter R(rx,ry):
 152  *
 153  *              |                         |
 154  *              | by - ay   (||b - a||)^2 |
 155  *              |                         |
 156  *              | cy - ay   (||c - a||)^2 |
 157  *              |                         |
 158  *   rx = ax - -----------------------------
 159  *                   |                   |
 160  *                   | bx - ax   by - ay |
 161  *               2 * |                   |
 162  *                   | cx - ax   cy - ay |
 163  *                   |                   |
 164  *
 165  *              |                         |
 166  *              | bx - ax   (||b - a||)^2 |
 167  *              |                         |
 168  *              | cx - ax   (||c - a||)^2 |
 169  *              |                         |
 170  *   ry = ay + -----------------------------
 171  *                   |                   |
 172  *                   | bx - ax   by - ay |
 173  *               2 * |                   |
 174  *                   | cx - ax   cy - ay |
 175  *                   |                   |
 176  *
 177  * =============================================================================
 178  */
 179   void calculateCircumCircle() {
 180     coordinate circumCenterPtr = this.circumCenter;
 181     yada.Assert(numCoordinate == 2 || numCoordinate == 3);
 182
 183     if (numCoordinate == 2) {
 184       circumCenterPtr.x = (coordinates[0].x + coordinates[1].x) / 2.0;
 185       circumCenterPtr.y = (coordinates[0].y + coordinates[1].y) / 2.0;
 186     } else {
 187       double ax = coordinates[0].x;
 188       double ay = coordinates[0].y;
 189       double bx = coordinates[1].x;
 190       double by = coordinates[1].y;
 191       double cx = coordinates[2].x;
 192       double cy = coordinates[2].y;
 193       double bxDelta = bx - ax;
 194       double byDelta = by - ay;
 195       double cxDelta = cx - ax;
 196       double cyDelta = cy - ay;
 197       double bDistance2 = (bxDelta * bxDelta) + (byDelta * byDelta);
 198       double cDistance2 = (cxDelta * cxDelta) + (cyDelta * cyDelta);
 199       double xNumerator = (byDelta * cDistance2) - (cyDelta * bDistance2);
 200       double yNumerator = (bxDelta * cDistance2) - (cxDelta * bDistance2);
 201       double denominator = 2 * ((bxDelta * cyDelta) - (cxDelta * byDelta));
 202       double rx = ax - (xNumerator / denominator);
 203       double ry = ay + (yNumerator / denominator);
 204       yada.Assert(Math.fabs(denominator) > 2.2250738585072014e-308); /* make sure not colinear */
 205       circumCenterPtr.x = rx;
 206       circumCenterPtr.y = ry;
 207     }
 208
 209     circumRadius = coordinate.coordinate_distance(circumCenterPtr,
 210                                                   coordinates[0]);
 211   }
 212
 213
 214 /* =============================================================================
 215  * setEdge
 216  *
 217   * Note: Makes pairPtr sorted; i.e., coordinate_compare(first, second) < 0
 218  * =============================================================================
 219  */
 220   public void setEdge(int i) {
 221     coordinate firstPtr = coordinates[i];
 222     coordinate secondPtr = coordinates[(i + 1) % numCoordinate];
 223
 224     edge edgePtr = edges[i];
 225     int cmp = coordinate.coordinate_compare(firstPtr, secondPtr);
 226     yada.Assert(cmp != 0);
 227     if (cmp < 0) {
 228       edgePtr.firstPtr  = firstPtr;
 229       edgePtr.secondPtr = secondPtr;
 230     } else {
 231       edgePtr.firstPtr  = secondPtr;
 232       edgePtr.secondPtr = firstPtr;
 233     }
 234
 235     coordinate midpointPtr = midpoints[i];
 236     midpointPtr.x = (firstPtr.x + secondPtr.x) / 2.0;
 237     midpointPtr.y = (firstPtr.y + secondPtr.y) / 2.0;
 238
 239     radii[i] = coordinate.coordinate_distance(firstPtr, midpointPtr);
 240   }
 241
 242
 243 /* =============================================================================
 244  * initEdges
 245  * =============================================================================
 246  */
 247   void initEdges(coordinate[] coordinates, int numCoordinate) {
 248     numEdge = ((numCoordinate * (numCoordinate - 1)) / 2);
 249
 250     for (int e = 0; e < numEdge; e++) {
 251       setEdge(e);
 252     }
 253   }
 254
 255
 256 /* =============================================================================
 257  * element_compare
 258  * =============================================================================
 259  */
 260 static int element_compare (element aElementPtr, element bElementPtr) {
 261   int aNumCoordinate = aElementPtr.numCoordinate;
 262   int bNumCoordinate = bElementPtr.numCoordinate;
 263   coordinate aCoordinates[] = aElementPtr.coordinates;
 264   coordinate bCoordinates[] = bElementPtr.coordinates;
 265
 266   if (aNumCoordinate < bNumCoordinate) {
 267     return -1;
 268   } else if (aNumCoordinate > bNumCoordinate) {
 269     return 1;
 270   }
 271
 272   for (int i = 0; i < aNumCoordinate; i++) {
 273     int compareCoordinate =
 274       coordinate.coordinate_compare(aCoordinates[i], bCoordinates[i]);
 275     if (compareCoordinate != 0) {
 276       return compareCoordinate;
 277     }
 278   }
 279
 280   return 0;
 281 }
 282
 283
 284 /* =============================================================================
 285  * element_listCompare
 286  *
 287  * For use in list_t
 288  * =============================================================================
 289  */
 290   int element_listCompare (Object aPtr, Object  bPtr) {
 291     element aElementPtr = (element)aPtr;
 292     element bElementPtr = (element)bPtr;
 293
 294     return element_compare(aElementPtr, bElementPtr);
 295   }
 296
 297
 298 /* =============================================================================
 299  * element_mapCompare
 300  *
 301  * For use in MAP_T
 302  * =============================================================================
 303  */
 304   static int element_mapCompare(Object aPtr, Object bPtr) {
 305     element aElementPtr = (element)(((edge)aPtr).firstPtr);
 306     element bElementPtr = (element)(((edge)bPtr).firstPtr);
 307
 308     return element_compare(aElementPtr, bElementPtr);
 309   }
 310
 311
 312   /* =============================================================================
 313    * TMelement_alloc
 314    *
 315    * Contains a copy of input arg 'coordinates'
 316    * =============================================================================
 317    */
 318
 319   double angleConstraint;
 320   public element(coordinate[] coordinates, int numCoordinate, double angle) {
 321     this.circumCenter=new coordinate();
 322     this.coordinates=new coordinate[3];
 323     this.midpoints=new coordinate[3]; /* midpoint of each edge */
 324     this.radii=new double[3];           /* half of edge length */
 325     this.edges=new edge[3];
 326     for (int i = 0; i < 3; i++) {
 327       this.midpoints[i] = new coordinate();
 328       this.edges[i]=new edge();
 329     }
 330     for (int i = 0; i < numCoordinate; i++) {
 331       this.coordinates[i] = coordinates[i];
 332     }
 333     this.numCoordinate = numCoordinate;
 334     this.angleConstraint=angle;
 335     minimizeCoordinates();
 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   static 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 element_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 }