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   static void minimizeCoordinates (element elementPtr) {
  95     coordinate[] coordinates = elementPtr.coordinates;
  96     int numCoordinate = elementPtr.numCoordinate;
  97     int minPosition = 0;
  98
  99     for (int i = 1; i < numCoordinate; i++) {
 100       if (coordinate.coordinate_compare(coordinates[i], coordinates[minPosition]) < 0) {
 101         minPosition = i;
 102       }
 103     }
 104
 105     while(minPosition != 0) {
 106       coordinate tmp = coordinates[0];
 107       for (int j = 0; j < (numCoordinate - 1); j++) {
 108         coordinates[j] = coordinates[j+1];
 109       }
 110       coordinates[numCoordinate-1] = tmp;
 111       minPosition--;
 112     }
 113   }
 114
 115
 116 /* =============================================================================
 117  * checkAngles
 118  * -- Sets isSkinny to TRUE if the angle constraint is not met
 119  * =============================================================================
 120  */
 121   void checkAngles (double angleConstraint) {
 122     //double angleConstraint = global_angleConstraint;
 123     minAngle = 180.0;
 124
 125     yada.Assert(numCoordinate == 2 || numCoordinate == 3);
 126     isReferenced = false;
 127     isSkinny = false;
 128     encroachedEdgePtr = null;
 129
 130     if (numCoordinate == 3) {
 131         int i;
 132         for (i = 0; i < 3; i++) {
 133           double angle = coordinate.coordinate_angle(coordinates[i],
 134                                           coordinates[(i + 1) % 3],
 135                                           coordinates[(i + 2) % 3]);
 136           yada.Assert(angle > 0.0);
 137           yada.Assert(angle < 180.0);
 138           if (angle > 90.0) {
 139             encroachedEdgePtr = edges[(i + 1) % 3];
 140           }
 141           if (angle < angleConstraint) {
 142             isSkinny = true;
 143           }
 144           if (angle < minAngle) {
 145             minAngle = angle;
 146           }
 147         }
 148         yada.Assert(minAngle < 180.0);
 149     }
 150 }
 151
 152
 153 /* =============================================================================
 154  * calculateCircumCenter
 155  *
 156  * Given three points A(ax,ay), B(bx,by), C(cx,cy), circumcenter R(rx,ry):
 157  *
 158  *              |                         |
 159  *              | by - ay   (||b - a||)^2 |
 160  *              |                         |
 161  *              | cy - ay   (||c - a||)^2 |
 162  *              |                         |
 163  *   rx = ax - -----------------------------
 164  *                   |                   |
 165  *                   | bx - ax   by - ay |
 166  *               2 * |                   |
 167  *                   | cx - ax   cy - ay |
 168  *                   |                   |
 169  *
 170  *              |                         |
 171  *              | bx - ax   (||b - a||)^2 |
 172  *              |                         |
 173  *              | cx - ax   (||c - a||)^2 |
 174  *              |                         |
 175  *   ry = ay + -----------------------------
 176  *                   |                   |
 177  *                   | bx - ax   by - ay |
 178  *               2 * |                   |
 179  *                   | cx - ax   cy - ay |
 180  *                   |                   |
 181  *
 182  * =============================================================================
 183  */
 184   void calculateCircumCircle() {
 185     coordinate circumCenterPtr = this.circumCenter;
 186
 187     yada.Assert(numCoordinate == 2 || numCoordinate == 3);
 188
 189     if (numCoordinate == 2) {
 190       circumCenterPtr.x = (coordinates[0].x + coordinates[1].x) / 2.0;
 191       circumCenterPtr.y = (coordinates[0].y + coordinates[1].y) / 2.0;
 192     } else {
 193       double ax = coordinates[0].x;
 194       double ay = coordinates[0].y;
 195       double bx = coordinates[1].x;
 196       double by = coordinates[1].y;
 197       double cx = coordinates[2].x;
 198       double cy = coordinates[2].y;
 199       double bxDelta = bx - ax;
 200       double byDelta = by - ay;
 201       double cxDelta = cx - ax;
 202       double cyDelta = cy - ay;
 203       double bDistance2 = (bxDelta * bxDelta) + (byDelta * byDelta);
 204       double cDistance2 = (cxDelta * cxDelta) + (cyDelta * cyDelta);
 205       double xNumerator = (byDelta * cDistance2) - (cyDelta * bDistance2);
 206       double yNumerator = (bxDelta * cDistance2) - (cxDelta * bDistance2);
 207       double denominator = 2 * ((bxDelta * cyDelta) - (cxDelta * byDelta));
 208       double rx = ax - (xNumerator / denominator);
 209       double ry = ay + (yNumerator / denominator);
 210       yada.Assert(fabs(denominator) > DBL_MIN); /* make sure not colinear */
 211       circumCenterPtr.x = rx;
 212       circumCenterPtr.y = ry;
 213     }
 214
 215     elementPtr.circumRadius = coordinate.coordinate_distance(circumCenterPtr,
 216                                                   coordinates[0]);
 217   }
 218
 219
 220 /* =============================================================================
 221  * setEdge
 222  *
 223   * Note: Makes pairPtr sorted; i.e., coordinate_compare(first, second) < 0
 224  * =============================================================================
 225  */
 226   public void setEdge(int i) {
 227     coordinate firstPtr = coordinates[i];
 228     coordinate secondPtr = coordinates[(i + 1) % numCoordinate];
 229
 230     edge edgePtr = edges[i];
 231     int cmp = coordinate.coordinate_compare(firstPtr, secondPtr);
 232     yada.Assert(cmp != 0);
 233     if (cmp < 0) {
 234       edgePtr.firstPtr  = firstPtr;
 235       edgePtr.secondPtr = secondPtr;
 236     } else {
 237       edgePtr.firstPtr  = secondPtr;
 238       edgePtr.secondPtr = firstPtr;
 239     }
 240
 241     coordinate midpointPtr = elementPtr.midpoints[i];
 242     midpointPtr.x = (firstPtr.x + secondPtr.x) / 2.0;
 243     midpointPtr.y = (firstPtr.y + secondPtr.y) / 2.0;
 244
 245     elementPtr.radii[i] = coordinate.coordinate_distance(firstPtr, midpointPtr);
 246   }
 247
 248
 249 /* =============================================================================
 250  * initEdges
 251  * =============================================================================
 252  */
 253   void initEdges(coordinate coordinates, int numCoordinate) {
 254     numEdge = ((numCoordinate * (numCoordinate - 1)) / 2);
 255
 256     for (int e = 0; e < numEdge; e++) {
 257       setEdge(e);
 258     }
 259   }
 260
 261
 262 /* =============================================================================
 263  * element_compare
 264  * =============================================================================
 265  */
 266 int element_compare (element aElementPtr, element bElementPtr) {
 267   int aNumCoordinate = aElementPtr.numCoordinate;
 268   int bNumCoordinate = bElementPtr.numCoordinate;
 269   coordinate aCoordinates[] = aElementPtr.coordinates;
 270   coordinate bCoordinates[] = bElementPtr.coordinates;
 271
 272   if (aNumCoordinate < bNumCoordinate) {
 273     return -1;
 274   } else if (aNumCoordinate > bNumCoordinate) {
 275     return 1;
 276   }
 277
 278   for (int i = 0; i < aNumCoordinate; i++) {
 279     int compareCoordinate =
 280       coordinate.coordinate_compare(aCoordinates[i], bCoordinates[i]);
 281     if (compareCoordinate != 0) {
 282       return compareCoordinate;
 283     }
 284   }
 285
 286   return 0;
 287 }
 288
 289
 290 /* =============================================================================
 291  * element_listCompare
 292  *
 293  * For use in list_t
 294  * =============================================================================
 295  */
 296   int element_listCompare (Object aPtr, Object  bPtr) {
 297     element aElementPtr = (element)aPtr;
 298     element bElementPtr = (element)bPtr;
 299
 300     return element_compare(aElementPtr, bElementPtr);
 301   }
 302
 303
 304 /* =============================================================================
 305  * element_mapCompare
 306  *
 307  * For use in MAP_T
 308  * =============================================================================
 309  */
 310   int element_mapCompare(Object aPtr, Object bPtr) {
 311     element aElementPtr = (element)(((edge)aPtr).firstPtr);
 312     element bElementPtr = (element)(((edge)bPtr).firstPtr);
 313
 314     return element_compare(aElementPtr, bElementPtr);
 315   }
 316
 317
 318   /* =============================================================================
 319    * TMelement_alloc
 320    *
 321    * Contains a copy of input arg 'coordinates'
 322    * =============================================================================
 323    */
 324   public element(coordinate[] coordinates, int numCoordinate) {
 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     checkAngles();
 336     calculateCircumCircle();
 337     initEdges(coordinates, numCoordinate);
 338     neighborListPtr = new List_t(0);//TMLIST_ALLOC(element_listCompare);
 339     isGarbage = false;
 340     isReferenced = false;
 341   }
 342
 343
 344 /* =============================================================================
 345  * element_getNumEdge
 346  * =============================================================================
 347  */
 348   int element_getNumEdge() {
 349     return numEdge;
 350   }
 351
 352
 353 /* =============================================================================
 354  * element_getEdge
 355  *
 356  * Returned edgePtr is sorted; i.e., coordinate_compare(first, second) < 0
 357  * =============================================================================
 358  */
 359   edge element_getEdge(int i) {
 360     if (i < 0 || i > numEdge)
 361       return null;
 362     return edges[i];
 363   }
 364
 365
 366 /* =============================================================================
 367  * element_compareEdge
 368  * =============================================================================
 369  */
 370   static int compareEdge(edge aEdgePtr, edge bEdgePtr) {
 371     int diffFirst = coordinate.coordinate_compare((coordinate)aEdgePtr.firstPtr,
 372                                         (coordinate)bEdgePtr.firstPtr);
 373
 374     return ((diffFirst != 0) ?
 375             (diffFirst) :
 376             (coordinate.coordinate_compare((coordinate)aEdgePtr.secondPtr,
 377                                 (coordinate)bEdgePtr.secondPtr)));
 378   }
 379
 380
 381 /* ============================================================================
 382  * element_listCompareEdge
 383  *
 384  * For use in list_t
 385  * ============================================================================
 386  */
 387   int element_listCompareEdge (Object aPtr, Object bPtr) {
 388     edge aEdgePtr = (edge)(aPtr);
 389     edge bEdgePtr = (edge)(bPtr);
 390
 391     return compareEdge(aEdgePtr, bEdgePtr);
 392   }
 393
 394
 395 /* =============================================================================
 396  * element_mapCompareEdge
 397  *
 398   * For use in MAP_T
 399  * =============================================================================
 400  */
 401   int element_mapCompareEdge (Object aPtr, Object bPtr) {
 402     edge aEdgePtr = (edge)(aPtr.firstPtr);
 403     edge bEdgePtr = (edge)(bPtr.firstPtr);
 404
 405     return compareEdge(aEdgePtr, bEdgePtr);
 406   }
 407
 408
 409 /* =============================================================================
 410  * element_heapCompare
 411  *
 412  * For use in heap_t. Consider using minAngle instead of "do not care".
 413  * =============================================================================
 414  */
 415   int element_heapCompare (Object aPtr, Object bPtr) {
 416     element aElementPtr = (element)aPtr;
 417     element bElementPtr = (element)bPtr;
 418
 419     if (aElementPtr.encroachedEdgePtr!=null) {
 420       if (bElementPtr.encroachedEdgePtr!=null) {
 421         return 0; /* do not care */
 422       } else {
 423         return 1;
 424       }
 425     }
 426
 427     if (bElementPtr.encroachedEdgePtr!=null) {
 428       return -1;
 429     }
 430
 431     return 0; /* do not care */
 432   }
 433
 434
 435 /* =============================================================================
 436  * element_isInCircumCircle
 437  * =============================================================================
 438  */
 439   boolean element_isInCircumCircle(coordinate coordinatePtr) {
 440     double distance = coordinate.coordinate_distance(coordinatePtr, circumCenter);
 441     return distance <= circumRadius;
 442   }
 443
 444
 445 /* =============================================================================
 446  * isEncroached
 447  * =============================================================================
 448  */
 449   boolean isEncroached() {
 450     return encroachedEdgePtr!=null;
 451   }
 452
 453
 454 /* =============================================================================
 455  * element_setEncroached
 456  * =============================================================================
 457  */
 458   void element_clearEncroached() {
 459     encroachedEdgePtr = null;
 460   }
 461
 462
 463 /* =============================================================================
 464  * element_getEncroachedPtr
 465  * =============================================================================
 466  */
 467   edge element_getEncroachedPtr() {
 468     return encroachedEdgePtr;
 469   }
 470
 471
 472 /* =============================================================================
 473  * element_isSkinny
 474  * =============================================================================
 475  */
 476   boolean element_isSkinny() {
 477     return isSkinny;
 478   }
 479
 480
 481 /* =============================================================================
 482  * element_isBad
 483  * -- Does it need to be refined?
 484  * =============================================================================
 485  */
 486   boolean element_isBad() {
 487     return (isEncroached() || element_isSkinny());
 488   }
 489
 490
 491 /* =============================================================================
 492  * TMelement_isReferenced
 493  * -- Held by another data structure?
 494  * =============================================================================
 495  */
 496   boolean element_isReferenced () {
 497     return isReferenced;
 498   }
 499
 500
 501 /* =============================================================================
 502  * TMelement_setIsReferenced
 503  * =============================================================================
 504  */
 505   void element_setIsReferenced(boolean status) {
 506     isReferenced= status;
 507   }
 508
 509
 510 /* =============================================================================
 511  * element_isGarbage
 512  * -- Can we deallocate?
 513  * =============================================================================
 514  */
 515
 516 /* =============================================================================
 517  * TMelement_isGarbage
 518  * -- Can we deallocate?
 519  * =============================================================================
 520  */
 521   boolean element_isGarbage() {
 522     return isGarbage;
 523   }
 524
 525
 526
 527 /* =============================================================================
 528  * TMelement_setIsGarbage
 529  * =============================================================================
 530  */
 531   void element_setIsGarbage(boolean status) {
 532     isGarbage=status;
 533   }
 534
 535
 536 /* =============================================================================
 537  * TMelement_addNeighbor
 538  * =============================================================================
 539  */
 540   void element_addNeighbor(element neighborPtr) {
 541     neighborListPtr.insert(neighborPtr);
 542   }
 543
 544
 545 /* =============================================================================
 546  * element_getNeighborListPtr
 547  * =============================================================================
 548  */
 549   List_t element_getNeighborListPtr () {
 550     return neighborListPtr;
 551   }
 552
 553
 554 /* =============================================================================
 555  * element_getCommonEdge
 556  *
 557  * Returns pointer to aElementPtr's shared edge
 558  * =============================================================================
 559  */
 560   edge element_getCommonEdge (element aElementPtr, element bElementPtr) {
 561     edge aEdges[] = aElementPtr.edges;
 562     edge bEdges[] = bElementPtr.edges;
 563     int aNumEdge = aElementPtr.numEdge;
 564     int bNumEdge = bElementPtr.numEdge;
 565
 566     for (int a = 0; a < aNumEdge; a++) {
 567       edge aEdgePtr = aEdges[a];
 568       for (int b = 0; b < bNumEdge; b++) {
 569         edge bEdgePtr = bEdges[b];
 570         if (compareEdge(aEdgePtr, bEdgePtr) == 0) {
 571           return aEdgePtr;
 572         }
 573       }
 574     }
 575
 576     return null;
 577   }
 578
 579
 580 /* =============================================================================
 581  * element_getNewPoint
 582  * -- Either the element is encroached or is skinny, so get the new point to add
 583  * =============================================================================
 584  */
 585   coordinate element_getNewPoint() {
 586     if (encroachedEdgePtr!=null) {
 587       for (int e = 0; e < numEdge; e++) {
 588         if (compareEdge(encroachedEdgePtr, edges[e]) == 0) {
 589           return midpoints[e];
 590         }
 591       }
 592       yada.Assert(0);
 593     }
 594     return circumCenter;
 595   }
 596
 597
 598 /* =============================================================================
 599  * element_checkAngles
 600  *
 601  * Return FALSE if minimum angle constraint not met
 602  * =============================================================================
 603  */
 604   boolean element_checkAngles(double angleConstraint) {
 605     //    double angleConstraint = global_angleConstraint;
 606     if (numCoordinate == 3) {
 607       for (int i = 0; i < 3; i++) {
 608         double angle = coordinate.coordinate_angle(coordinates[i],
 609                                         coordinates[(i + 1) % 3],
 610                                         coordinates[(i + 2) % 3]);
 611         if (angle < angleConstraint) {
 612           return false;
 613         }
 614       }
 615     }
 616     return true;
 617   }
 618
 619
 620 /* =============================================================================
 621  * element_print
 622  * =============================================================================
 623  */
 624   void element_print() {
 625     for (int c = 0; c < numCoordinate; c++) {
 626       coordinates[c].coordinate_print();
 627       System.out.println(" ");
 628     }
 629   }
 630
 631
 632 /* =============================================================================
 633  * element_printEdge
 634  * =============================================================================
 635  */
 636   void element_printEdge (edge edgePtr) {
 637     ((coordinate)edgePtr.firstPtr).coordinate_print();
 638     System.out.println(" -> ");
 639     ((coordinate)edgePtr.secondPtr).coordinate_print();
 640   }
 641
 642
 643 /* =============================================================================
 644  * element_printAngles
 645  * =============================================================================
 646  */
 647   void element_printAngles() {
 648     if (numCoordinate == 3) {
 649       for (int i = 0; i < 3; i++) {
 650         double angle = coordinate.coordinate_angle(coordinates[i],
 651                                         coordinates[(i + 1) % 3],
 652                                         coordinates[(i + 2) % 3]);
 653         System.out.println(angle);
 654       }
 655     }
 656   }
 657 }