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

   1 /* =============================================================================
   2  *
   3  * mesh.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 mesh {
  72   element rootElementPtr;
  73   Queue_t initBadQueuePtr;
  74   int size;
  75   RBTree boundarySetPtr;
  76   double angle;
  77 /* =============================================================================
  78  * mesh_alloc
  79  * =============================================================================
  80  */
  81   public mesh(double angle) {
  82     this.angle=angle;
  83     rootElementPtr = null;
  84     initBadQueuePtr = new Queue_t(-1);
  85     size = 0;
  86     boundarySetPtr = new RBTree(0);
  87   }
  88
  89
  90   /* =============================================================================
  91    * TMmesh_insert
  92    * =============================================================================
  93    */
  94   void TMmesh_insert (element elementPtr, avltree edgeMapPtr) {
  95     /*
  96      * Assuming fully connected graph, we just need to record one element.
  97      * The root element is not needed for the actual refining, but rather
  98      * for checking the validity of the final mesh.
  99      */
 100     if (rootElementPtr==null) {
 101       rootElementPtr=elementPtr;
 102   }
 103
 104     /*
 105      * Record existence of each of this element's edges
 106      */
 107   int numEdge = elementPtr.element_getNumEdge();
 108   for (int i = 0; i < numEdge; i++) {
 109     edge edgePtr = elementPtr.element_getEdge(i);
 110     if (!edgeMapPtr.contains(edgePtr)) {
 111       /* Record existance of this edge */
 112       boolean isSuccess =
 113         edgeMapPtr.insert(edgePtr, elementPtr);
 114       yada.Assert(isSuccess);
 115     } else {
 116       /*
 117        * Shared edge; update each element's neighborList
 118        */
 119       boolean isSuccess;
 120       element sharerPtr = (element)edgeMapPtr.find(edgePtr);
 121       yada.Assert(sharerPtr!=null); /* cannot be shared by >2 elements */
 122       elementPtr.element_addNeighbor(sharerPtr);
 123       sharerPtr.element_addNeighbor(elementPtr);
 124       isSuccess = edgeMapPtr.remove(edgePtr);
 125       yada.Assert(isSuccess);
 126       isSuccess = edgeMapPtr.insert(edgePtr,
 127                               null); /* marker to check >2 sharers */
 128       yada.Assert(isSuccess);
 129     }
 130   }
 131
 132   /*
 133    * Check if really encroached
 134    */
 135
 136   edge encroachedPtr = elementPtr.element_getEncroachedPtr();
 137   if (encroachedPtr!=null) {
 138     if (!boundarySetPtr.contains(encroachedPtr)) {
 139       elementPtr.element_clearEncroached();
 140     }
 141   }
 142 }
 143
 144
 145 /* =============================================================================
 146  * TMmesh_remove
 147  * =============================================================================
 148  */
 149 public void TMmesh_remove(element elementPtr) {
 150   yada.Assert(!elementPtr.element_isGarbage());
 151
 152   /*
 153    * If removing root, a new root is selected on the next mesh_insert, which
 154    * always follows a call a mesh_remove.
 155    */
 156   if (rootElementPtr == elementPtr) {
 157     rootElementPtr=null;
 158   }
 159
 160   /*
 161    * Remove from neighbors
 162    */
 163
 164   List_t neighborListPtr = elementPtr.element_getNeighborListPtr();
 165   List_Node it=neighborListPtr.head;
 166
 167   while (it.nextPtr!=null) {
 168     it=it.nextPtr;
 169     element neighborPtr = (element)it.dataPtr;
 170     List_t neighborNeighborListPtr = neighborPtr.element_getNeighborListPtr();
 171     boolean status = neighborNeighborListPtr.remove(elementPtr);
 172     yada.Assert(status);
 173   }
 174
 175   elementPtr.element_setIsGarbage(true);
 176 }
 177
 178
 179 /* =============================================================================
 180  * TMmesh_insertBoundary
 181  * =============================================================================
 182  */
 183 boolean TMmesh_insertBoundary(edge boundaryPtr) {
 184   return boundarySetPtr.insert(boundaryPtr,null);
 185 }
 186
 187
 188 /* =============================================================================
 189  * TMmesh_removeBoundary
 190  * =============================================================================
 191  */
 192 boolean TMmesh_removeBoundary(edge boundaryPtr) {
 193   return boundarySetPtr.deleteObjNode(boundaryPtr);
 194 }
 195
 196
 197 /* =============================================================================
 198  * createElement
 199  * =============================================================================
 200  */
 201   void createElement(coordinate[] coordinates, int numCoordinate,
 202                            avltree edgeMapPtr) {
 203   element elementPtr = new element(coordinates, numCoordinate, angle);
 204   yada.Assert(elementPtr!=null);
 205
 206   if (numCoordinate == 2) {
 207     edge boundaryPtr = elementPtr.element_getEdge(0);
 208     boolean status = boundarySetPtr.insert(boundaryPtr, null);
 209     yada.Assert(status);
 210   }
 211
 212   TMmesh_insert(elementPtr, edgeMapPtr);
 213
 214   if (elementPtr.element_isBad()) {
 215     boolean status = initBadQueuePtr.queue_push(elementPtr);
 216     yada.Assert(status);
 217   }
 218 }
 219
 220
 221 /* =============================================================================
 222  * mesh_read
 223  *
 224  * Returns number of elements read from file
 225  *
 226  * Refer to http://www.cs.cmu.edu/~quake/triangle.html for file formats.
 227  * =============================================================================
 228  */
 229 int mesh_read(String fileNamePrefix) {
 230     char inputBuff[]=new char[256];
 231     int i;
 232     int numElement = 0;
 233
 234     avltree edgeMapPtr = new avltree(0);
 235
 236     /*
 237      * Read .node file
 238      */
 239
 240     String fileName=fileNamePrefix+".node";
 241     FileInputStream inputFile = new FileInputStream(fileName);
 242     bytereader br=new bytereader(inputFile);
 243     int numEntry=br.getInt();
 244     int numDimension=br.getInt();
 245     yada.Assert(numDimension == 2); /* must be 2-D */
 246     int numCoordinate = numEntry + 1; /* numbering can start from 1 */
 247     coordinate coordinates[] = new coordinate[numCoordinate];
 248     for(i=0;i<numCoordinate;i++)
 249       coordinates[i]=new coordinate();
 250
 251     for (i = 0; i < numEntry; i++) {
 252       int id;
 253       double x;
 254       double y;
 255       id=br.getInt();
 256       x=br.getDouble();
 257       y=br.getDouble();
 258       coordinates[id].x = x;
 259       coordinates[id].y = y;
 260     }
 261     yada.Assert(i == numEntry);
 262     inputFile.close();
 263
 264     /*
 265      * Read .poly file, which contains boundary segments
 266      */
 267     fileName=fileNamePrefix+".poly";
 268     inputFile = new FileInputStream(fileName);
 269     br=new bytereader(inputFile);
 270     numEntry=br.getInt();
 271     numDimension=br.getInt();
 272     yada.Assert(numEntry == 0); /* .node file used for vertices */
 273     yada.Assert(numDimension == 2); /* must be edge */
 274     numEntry=br.getInt();
 275     for (i = 0; i < numEntry; i++) {
 276       int id;
 277       int a;
 278       int b;
 279       coordinate insertCoordinates[]=new coordinate[2];
 280       id=br.getInt();
 281       a=br.getInt();
 282       b=br.getInt();
 283       yada.Assert(a >= 0 && a < numCoordinate);
 284       yada.Assert(b >= 0 && b < numCoordinate);
 285       insertCoordinates[0] = coordinates[a];
 286       insertCoordinates[1] = coordinates[b];
 287       createElement(insertCoordinates, 2, edgeMapPtr);
 288     }
 289     yada.Assert(i == numEntry);
 290     numElement += numEntry;
 291     inputFile.close();
 292
 293     /*
 294      * Read .ele file, which contains triangles
 295      */
 296     fileName=fileNamePrefix+".ele";
 297     inputFile = new FileInputStream(fileName);
 298     br=new bytereader(inputFile);
 299     numEntry=br.getInt();
 300     numDimension=br.getInt();
 301     yada.Assert(numDimension == 3); /* must be triangle */
 302     for (i = 0; i < numEntry; i++) {
 303       int id;
 304       int a;
 305       int b;
 306       int c;
 307       coordinate insertCoordinates[]=new coordinate[3];
 308       id=br.getInt();
 309       a=br.getInt();
 310       b=br.getInt();
 311       c=br.getInt();
 312       yada.Assert(a >= 0 && a < numCoordinate);
 313       yada.Assert(b >= 0 && b < numCoordinate);
 314       yada.Assert(c >= 0 && c < numCoordinate);
 315       insertCoordinates[0] = coordinates[a];
 316       insertCoordinates[1] = coordinates[b];
 317       insertCoordinates[2] = coordinates[c];
 318       createElement(insertCoordinates, 3, edgeMapPtr);
 319     }
 320     yada.Assert(i == numEntry);
 321     numElement += numEntry;
 322     inputFile.close();
 323     return numElement;
 324 }
 325
 326
 327 /* =============================================================================
 328  * mesh_getBad
 329  * -- Returns NULL if none
 330  * =============================================================================
 331  */
 332 element mesh_getBad() {
 333   return (element)initBadQueuePtr.queue_pop();
 334 }
 335
 336
 337 /* =============================================================================
 338  * mesh_shuffleBad
 339  * =============================================================================
 340  */
 341 void mesh_shuffleBad (Random randomPtr) {
 342   initBadQueuePtr.queue_shuffle(randomPtr);
 343 }
 344
 345
 346 /* =============================================================================
 347  * mesh_check
 348  * =============================================================================
 349  */
 350 boolean mesh_check(int expectedNumElement) {
 351     int numBadTriangle = 0;
 352     int numFalseNeighbor = 0;
 353     int numElement = 0;
 354
 355     System.out.println("Checking final mesh:");
 356
 357     Queue_t searchQueuePtr = new Queue_t(-1);
 358     avltree visitedMapPtr = new avltree(1);
 359
 360     /*
 361      * Do breadth-first search starting from rootElementPtr
 362      */
 363     yada.Assert(rootElementPtr!=null);
 364     searchQueuePtr.queue_push(rootElementPtr);
 365     while (!searchQueuePtr.queue_isEmpty()) {
 366         List_t neighborListPtr;
 367
 368         element currentElementPtr = (element)searchQueuePtr.queue_pop();
 369         if (visitedMapPtr.contains(currentElementPtr)) {
 370             continue;
 371         }
 372         boolean isSuccess = visitedMapPtr.insert(currentElementPtr, null);
 373         yada.Assert(isSuccess);
 374         if (!currentElementPtr.checkAngles()) {
 375             numBadTriangle++;
 376         }
 377         neighborListPtr = currentElementPtr.element_getNeighborListPtr();
 378
 379         List_Node it=neighborListPtr.head;
 380         while (it.nextPtr!=null) {
 381           it=it.nextPtr;
 382           element neighborElementPtr =
 383             (element)it.dataPtr;
 384           /*
 385            * Continue breadth-first search
 386            */
 387           if (!visitedMapPtr.contains(neighborElementPtr)) {
 388             isSuccess = searchQueuePtr.queue_push(neighborElementPtr);
 389             yada.Assert(isSuccess);
 390           }
 391         } /* for each neighbor */
 392
 393         numElement++;
 394
 395     } /* breadth-first search */
 396
 397     System.out.println("Number of elements      = "+ numElement);
 398     System.out.println("Number of bad triangles = "+ numBadTriangle);
 399
 400     return (!(numBadTriangle > 0 ||
 401               numFalseNeighbor > 0 ||
 402               numElement != expectedNumElement));
 403 }
 404 }