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