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

   1 /* =============================================================================
   2  *
   3  * region.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 region {
  72   coordinate centerCoordinate;
  73   Queue_t expandQueuePtr;
  74   List_t beforeListPtr; /* before retriangulation; list to avoid duplicates */
  75   List_t borderListPtr; /* edges adjacent to region; list to avoid duplicates */
  76   Vector_t badVectorPtr;
  77
  78 /* =============================================================================
  79  * Pregion_alloc
  80  * =============================================================================
  81  */
  82   public region() {
  83     expandQueuePtr = new Queue_t(-1);
  84     beforeListPtr = new List_t(0);//PLIST_ALLOC(element_listCompare);
  85     borderListPtr = new List_t(1);//PLIST_ALLOC(element_listCompareEdge);
  86     badVectorPtr = new Vector_t(1);
  87   }
  88
  89
  90   /* =============================================================================
  91    * TMaddToBadVector
  92    * =============================================================================
  93    */
  94   public void TMaddToBadVector(Vector_t badVectorPtr, element badElementPtr) {
  95     boolean status = badVectorPtr.vector_pushBack(badElementPtr);
  96     yada.Assert(status);
  97     badElementPtr.element_setIsReferenced(true);
  98   }
  99
 100
 101   /* =============================================================================
 102    * TMretriangulate
 103    * -- Returns net amount of elements added to mesh
 104    * =============================================================================
 105    */
 106   public int TMretriangulate (element elementPtr,
 107                               region regionPtr,
 108                               mesh meshPtr,
 109                               avltree edgeMapPtr) {
 110     Vector_t badVectorPtr = regionPtr.badVectorPtr; /* private */
 111     List_t beforeListPtr = regionPtr.beforeListPtr; /* private */
 112     List_t borderListPtr = regionPtr.borderListPtr; /* private */
 113     list_iter_t it;
 114     int numDelta = 0;
 115
 116     yada.Assert(edgeMapPtr);
 117
 118     coordinate centerCoordinate = elementPtr.element_getNewPoint();
 119
 120     /*
 121      * Remove the old triangles
 122      */
 123
 124     list_iter_reset(it, beforeListPtr);
 125     while (list_iter_hasNext(it, beforeListPtr)) {
 126       element beforeElementPtr = (element)list_iter_next(it, beforeListPtr);
 127       meshPtr.TMmesh_remove(beforeElementPtr);
 128     }
 129
 130     numDelta -= beforeListPtr.getSize();
 131
 132     /*
 133      * If segment is encroached, split it in half
 134      */
 135
 136     if (elementPtr.element_getNumEdge() == 1) {
 137       coordinate coordinates[]=new coordinate[2];
 138
 139       edge edgePtr = elementPtr.element_getEdge(0);
 140       coordinates[0] = centerCoordinate;
 141
 142       coordinates[1] = (coordinate)(edgePtr.firstPtr);
 143       element aElementPtr = new element(coordinates, 2);
 144       yada.Assert(aElementPtr);
 145       meshPtr.TMmesh_insert(aElementPtr, edgeMapPtr);
 146
 147       coordinates[1] = (coordinate)edgePtr.secondPtr;
 148       element bElementPtr = new element(coordinates, 2);
 149       yada.Assert(bElementPtr);
 150       meshPtr.TMmesh_insert(bElementPtr, edgeMapPtr);
 151
 152       boolean status = meshPtr.TMmesh_removeBoundary(elementPtr.element_getEdge(0));
 153       yada.Assert(status);
 154       status = mesPtr.TMmesh_insertBoundary(aElementPtr.element_getEdge(0));
 155       yada.Assert(status);
 156       status = meshPtr.TMmesh_insertBoundary(bElementPtr.element_getEdge(0));
 157       yada.Assert(status);
 158
 159       numDelta += 2;
 160     }
 161
 162     /*
 163      * Insert the new triangles. These are contructed using the new
 164      * point and the two points from the border segment.
 165      */
 166
 167     list_iter_reset(it, borderListPtr);
 168     while (list_iter_hasNext(it, borderListPtr)) {
 169       coordinate coordinates[]=new coordinates[3];
 170       edge borderEdgePtr = (edge)list_iter_next(it, borderListPtr);
 171       yada.Assert(borderEdgePtr);
 172       coordinates[0] = centerCoordinate;
 173       coordinates[1] = (coordinate)(borderEdgePtr.firstPtr);
 174       coordinates[2] = (coordinate)(borderEdgePtr.secondPtr);
 175       element afterElementPtr = new element(coordinates, 3);
 176       yada.Assert(afterElementPtr!=null);
 177       meshPtr.TMmesh_insert(afterElementPtr, edgeMapPtr);
 178       if (afterElementPTr.element_isBad()) {
 179         TMaddToBadVector(badVectorPtr, afterElementPtr);
 180       }
 181     }
 182     numDelta += borderListPtr.getSize();
 183     return numDelta;
 184   }
 185
 186
 187   /* =============================================================================
 188    * TMgrowRegion
 189    * -- Return NULL if success, else pointer to encroached boundary
 190    * =============================================================================
 191    */
 192   element TMgrowRegion(element centerElementPtr,
 193                        region regionPtr,
 194                        mesh meshPtr,
 195                        avltree edgeMapPtr) {
 196     boolean isBoundary = false;
 197
 198     if (centerElementPtr.element_getNumEdge() == 1) {
 199       isBoundary = true;
 200     }
 201
 202     List_t beforeListPtr = regionPtr.beforeListPtr;
 203     List_t borderListPtr = regionPtr.borderListPtr;
 204     Queue_t expandQueuePtr = regionPtr.expandQueuePtr;
 205
 206     beforeListPtr.clear();
 207     borderListPtr.clear();
 208     expandQueuePtr.queue_clear();
 209
 210     coordinate centerCoordinatePtr = centerElementPtr.element_getNewPoint();
 211
 212     expandQueuePtr.queue_push(centerElementPtr);
 213     while (!expandQueuePtr.queue_isEmpty()) {
 214
 215       element currentElementPtr = (element) expandQueuePtr.queue_pop();
 216
 217       beforeListPtr.insert(currentElementPtr); /* no duplicates */
 218       List_t neighborListPtr = currentElementPtr.element_getNeighborListPtr();
 219
 220       list_iter_t it;
 221       TMLIST_ITER_RESET(it, neighborListPtr);
 222       while (TMLIST_ITER_HASNEXT(it, neighborListPtr)) {
 223         element neighborElementPtr = (element)TMLIST_ITER_NEXT(it, neighborListPtr);
 224         neighborElementPtr.element_isGarbage(); /* so we can detect conflicts */
 225         if (!beforeListPtr.find(neighborElementPtr)) {
 226           if (neighborElementPtr.element_isInCircumCircle(centerCoordinatePtr)) {
 227             /* This is part of the region */
 228             if (!isBoundary && (neighborElementPtr.element_getNumEdge() == 1)) {
 229               /* Encroached on mesh boundary so split it and restart */
 230               return neighborElementPtr;
 231             } else {
 232               /* Continue breadth-first search */
 233               boolean isSuccess = expandQueuePtr.queue_push(neighborElementPtr);
 234               yada.Assert(isSuccess);
 235             }
 236           } else {
 237             /* This element borders region; save info for retriangulation */
 238             edge borderEdgePtr = neighborElementPtr.element_getCommonEdge(currentElementPtr);
 239             if (!borderEdgePtr) {
 240               TM_RESTART();
 241             }
 242             borderListPtr.insert(borderEdgePtr); /* no duplicates */
 243             if (!edgeMapPtr.contains(borderEdgePtr)) {
 244               edgeMapPtr.insert(borderEdgePtr, neighborElementPtr);
 245             }
 246           }
 247         } /* not visited before */
 248       } /* for each neighbor */
 249
 250     } /* breadth-first search */
 251
 252     return null;
 253   }
 254
 255
 256 /* =============================================================================
 257  * TMregion_refine
 258  * -- Returns net number of elements added to mesh
 259  * =============================================================================
 260  */
 261   int TMregion_refine(element elementPtr, mesh meshPtr) {
 262     int numDelta = 0;
 263     avltree edgeMapPtr = null;
 264     element encroachElementPtr = null;
 265
 266     elementPtr.element_isGarbage(); /* so we can detect conflicts */
 267
 268     while (true) {
 269       edgeMapPtr = new avltree(1);
 270       yada.Assert(edgeMapPtr!=null);
 271       encroachElementPtr = TMgrowRegion(elementPtr,
 272                                         this,
 273                                         meshPtr,
 274                                         edgeMapPtr);
 275
 276       if (encroachElementPtr!=null) {
 277         encroachElementPtr.element_setIsReferenced(true);
 278         numDelta += TMregion_refine(regionPtr,
 279                                     encroachElementPtr,
 280                                     meshPtr);
 281         if (elementPtr.elementisGarbage()) {
 282           break;
 283         }
 284       } else {
 285         break;
 286       }
 287     }
 288
 289     /*
 290      * Perform retriangulation.
 291      */
 292
 293     if (!elementPtr.element_isGarbage()) {
 294       numDelta += TMretriangulate(elementPtr,
 295                                   this,
 296                                   meshPtr,
 297                                   edgeMapPtr);
 298     }
 299
 300     return numDelta;
 301   }
 302
 303
 304   /* =============================================================================
 305    * Pregion_clearBad
 306    * =============================================================================
 307    */
 308   void region_clearBad () {
 309     badVectorPtr.vector_clear();
 310   }
 311
 312
 313 /* =============================================================================
 314  * TMregion_transferBad
 315  * =============================================================================
 316  */
 317   void region_transferBad(heap workHeapPtr) {
 318     int numBad = badVectorPtr.vector_getSize();
 319
 320     for (int i = 0; i < numBad; i++) {
 321       element badElementPtr = (element)badVectorPtr.vector_at(i);
 322       if (badElementPtr.element_isGarbage()) {
 323       } else {
 324         boolean status = workHeapPtr.heap_insert(badElementPtr);
 325         yada.Assert(status);
 326       }
 327     }
 328   }
 329 }