--- /dev/null
+
+public class List_Node {
+ Object dataPtr;
+ List_Node nextPtr;
+
+ public List_Node() {
+ dataPtr = null;
+ nextPtr = null;
+ }
+}
--- /dev/null
+/* =============================================================================
+ *
+ * List_t.java
+ * -- Sorted singly linked list
+ * -- Options: duplicate allowed
+ * (DLIST_NO_DUPLICATES) is no implemented yet (default: allow duplicates)
+ *
+ * =============================================================================
+ *
+ * Copyright (C) Stanford University, 2006. All Rights Reserved.
+ * Author: Chi Cao Minh
+ *
+ * =============================================================================
+ *
+ * For the license of bayes/sort.h and bayes/sort.c, please see the header
+ * of the files.
+ *
+ * ------------------------------------------------------------------------
+ *
+ * For the license of kmeans, please see kmeans/LICENSE.kmeans
+ *
+ * ------------------------------------------------------------------------
+ *
+ * For the license of ssca2, please see ssca2/COPYRIGHT
+ *
+ * ------------------------------------------------------------------------
+ *
+ * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the
+ * header of the files.
+ *
+ * ------------------------------------------------------------------------
+ *
+ * For the license of lib/rbtree.h and lib/rbtree.c, please see
+ * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree
+ *
+ * ------------------------------------------------------------------------
+ *
+ * Unless otherwise noted, the following license applies to STAMP files:
+ *
+ * Copyright (c) 2007, Stanford University
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * * Neither the name of Stanford University nor the names of its
+ * contributors may be used to endorse or promote products derived
+ * from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * =============================================================================
+ */
+
+
+public class List_t {
+
+ public List_Node head;
+ int size;
+
+ public List_t() {
+ head = new List_Node();
+ }
+
+
+ /* =======================================================================
+ * allocNode
+ * -- Returns null on failure
+ * =======================================================================
+ */
+ private List_Node allocNode(Object dataPtr)
+ {
+ List_Node nodePtr = new List_Node();
+
+ if(nodePtr == null) {
+ return null;
+ }
+
+ nodePtr.dataPtr = dataPtr;
+ nodePtr.nextPtr = null;
+
+ return nodePtr;
+ }
+
+
+/* =============================================================================
+ * list_alloc
+ * -- If NULL passed for 'compare' function, will compare data pointer addresses
+ * -- Returns NULL on failure
+ * =============================================================================
+ * list_t* list_alloc (long (*compare)(const void*, const void*));
+ *
+ *
+ */
+
+ public static List_t alloc()
+ {
+ List_t listPtr = new List_t();
+
+ if(listPtr == null) {
+ return null;
+ }
+
+ listPtr.head.dataPtr = null;
+ listPtr.head.nextPtr = null;
+ listPtr.size = 0;
+
+ return listPtr;
+ }
+
+/* =============================================================================
+ * list_free
+ * -- If NULL passed for 'compare' function, will compare data pointer addresses
+ * -- Returns NULL on failure
+ * =============================================================================
+ * void list_free (list_t* listPtr);
+ */
+ public static void free(List_t listPtr)
+ {
+ listPtr = null;
+ }
+
+// privae freeList
+
+/* =============================================================================
+ * list_isEmpty
+ * -- Return TRUE if list is empty, else FALSE
+ * =============================================================================
+ * bool_t list_isEmpty (list_t* listPtr);
+ */
+ public boolean isEmpty()
+ {
+ return (head.nextPtr == null);
+ }
+
+/* =============================================================================
+ * list_getSize
+ * -- Returns size of list
+ * =============================================================================
+ * long list_getSize (list_t* listPtr);
+ */
+ public int getSize() {
+ return size;
+ }
+
+/* =============================================================================
+ * findPrevious
+ * =============================================================================
+ * void* list_find (list_t* listPtr, void* dataPtr);
+ */
+ private List_Node findPrevious(Object dataPtr)
+ {
+ List_Node prevPtr = head;
+ List_Node nodePtr = prevPtr.nextPtr;
+
+ for(; nodePtr != null; nodePtr = nodePtr.nextPtr) {
+ if (compare(nodePtr.dataPtr,dataPtr) >= 0) {
+ return prevPtr;
+ }
+ prevPtr = nodePtr;
+ }
+
+ return prevPtr;
+ }
+
+ /* =============================================================================
+ * list_find
+ * -- Returns NULL if not found, else returns pointer to data
+ * =============================================================================
+ * void* list_find (list_t* listPtr, void* dataPtr);
+ */
+ public Object find(Object dataPtr) {
+ List_Node nodePtr;
+ List_Node prevPtr = findPrevious(dataPtr);
+
+ nodePtr = prevPtr.nextPtr;
+
+ if((nodePtr == null) ||
+ (compare(nodePtr.dataPtr,dataPtr) != 0)) {
+ return null;
+ }
+
+ return (nodePtr.dataPtr);
+ }
+
+ public int compare(Object obj1,Object obj2)
+ {
+ Reservation_Info aPtr=(Reservation_Info)obj1;
+ Reservation_Info bPtr=(Reservation_Info)obj2;
+ int typeDiff;
+
+ typeDiff = aPtr.type - bPtr.type;
+
+ return ((typeDiff != 0) ? (typeDiff) : (aPtr.id - bPtr.id));
+ }
+
+/* =============================================================================
+ * list_insert
+ * -- Return TRUE on success, else FALSE
+ * =============================================================================
+ * bool_t list_insert (list_t* listPtr, void* dataPtr);
+ */
+ public boolean insert(Object dataPtr) {
+ List_Node prevPtr;
+ List_Node nodePtr;
+ List_Node currPtr;
+
+ prevPtr = findPrevious(dataPtr);
+ currPtr = prevPtr.nextPtr;
+
+ nodePtr = allocNode(dataPtr);
+ if (nodePtr == null) {
+ return false;
+ }
+
+ nodePtr.nextPtr = currPtr;
+ prevPtr.nextPtr = nodePtr;
+ size++;
+
+ return true;
+ }
+
+
+/* =============================================================================
+ * list_remove
+ * -- Returns TRUE if successful, else FALSE
+ * =============================================================================
+ * bool_t list_remove (list_t* listPtr, void* dataPtr);
+ */
+ public boolean remove(Object dataPtr)
+ {
+ List_Node prevPtr;
+ List_Node nodePtr;
+
+ prevPtr = findPrevious(dataPtr);
+
+ nodePtr = prevPtr.nextPtr;
+
+ if((nodePtr != null) &&
+ (compare(nodePtr.dataPtr,dataPtr) == 0))
+ {
+ prevPtr.nextPtr = nodePtr.nextPtr;
+ nodePtr.nextPtr = null;
+ nodePtr = null;
+ size--;
+
+ return true;
+ }
+
+ return false;
+ }
+
+ int compareObject(Object obj1,Object obj2) {
+ return 1;
+ }
+
+
+/* =============================================================================
+ * list_clear
+ * -- Removes all elements
+ * =============================================================================
+ * void list_clear (list_t* listPtr);
+ */
+ public void clear() {
+ head = new List_Node();
+ size = 0;
+ }
+
+/* =============================================================================
+ *
+ * End of list.java
+ *
+ * =============================================================================
+ */
+
+ /* Test list */
+
+ public static void main(String[] argv) {
+ List_t listPtr;
+ int[] data1 = new int[5];
+ int[] data2 = new int[6];
+
+ int i;
+
+ System.out.println("Starting...");
+ }
+
+}
+
+
+
--- /dev/null
+/* =============================================================================
+ *
+ * queue.java
+ *
+ * =============================================================================
+ *
+ * Copyright (C) Stanford University, 2006. All Rights Reserved.
+ * Author: Chi Cao Minh
+ *
+ * Ported to Java
+ * Author:Alokika Dash
+ * University of California, Irvine
+ *
+ * =============================================================================
+ *
+ * Unless otherwise noted, the following license applies to STAMP files:
+ *
+ * Copyright (c) 2007, Stanford University
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * * Neither the name of Stanford University nor the names of its
+ * contributors may be used to endorse or promote products derived
+ * from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * =============================================================================
+ */
+
+#define QUEUE_GROWTH_FACTOR 2
+
+public class Queue_t {
+ int pop; /* points before element to pop */
+ int push;
+ int capacity;
+ Object[] elements;
+
+ /* =============================================================================
+ * queue_alloc
+ * =============================================================================
+ */
+ public Queue_t(int initCapacity) {
+ int capacity = ((initCapacity < 2) ? 2 : initCapacity);
+ elements = new Object[capacity];
+ pop = capacity - 1;
+ push = 0;
+ this.capacity = capacity;
+ }
+
+
+ /* =============================================================================
+ * Pqueue_alloc
+ * =============================================================================
+ */
+ public Queue_t
+ Pqueue_alloc (int initCapacity)
+ {
+ Queue_t queuePtr = new Queue_t();
+
+ int capacity = ((initCapacity < 2) ? 2 : initCapacity);
+ queuePtr.elements = new Object[capacity];
+ if (queuePtr.elements == null) {
+ queuePtr = null;
+ return null;
+ }
+ queuePtr.pop = capacity - 1;
+ queuePtr.push = 0;
+ queuePtr.capacity = capacity;
+
+ return queuePtr;
+ }
+
+ /* =============================================================================
+ * queue_free
+ * =============================================================================
+ */
+ public void queue_free (Queue_t queuePtr) {
+ queuePtr.elements = null;
+ queuePtr = null;
+ }
+
+
+ /* =============================================================================
+ * Pqueue_free
+ * =============================================================================
+ */
+ public void
+ Pqueue_free (Queue_t queuePtr)
+ {
+ queuePtr.elements = null;
+ queuePtr = null;
+ }
+
+
+ /* =============================================================================
+ * TMqueue_free
+ * =============================================================================
+ *
+ public void
+ TMqueue_free (TM_ARGDECL Queue* queuePtr)
+ {
+ queuePtr.elements = null;
+ queuePtr = null;
+ }
+
+*/
+ /* =============================================================================
+ * queue_isEmpty
+ * =============================================================================
+ */
+ public boolean queue_isEmpty () {
+ //int pop = queuePtr.pop;
+ //int push = queuePtr.push;
+ //int capacity = queuePtr.capacity;
+
+ return (pop + 1) % capacity == push;
+ }
+
+
+ /* =============================================================================
+ * queue_clear
+ * =============================================================================
+ */
+ public void
+ queue_clear ()
+ {
+ pop = capacity - 1;
+ push = 0;
+ }
+
+
+ /* =============================================================================
+ * TMqueue_isEmpty
+ * =============================================================================
+ */
+
+
+
+ /* =============================================================================
+ * queue_push
+ * =============================================================================
+ */
+ public boolean queue_push (Object dataPtr) {
+ if(pop == push) {
+
+ System.out.println("push == pop in Queue.java");
+ return false;
+ }
+
+
+ /* Need to resize */
+ int newPush = (push + 1) % capacity;
+ if (newPush == pop) {
+
+ int newCapacity = capacity * QUEUE_GROWTH_FACTOR;
+ Object[] newElements = new Object[newCapacity];
+ if (newElements == null) {
+ return false;
+ }
+
+ int dst = 0;
+ Object[] tmpelements = elements;
+ if (pop < push) {
+ int src;
+ for (src = (pop + 1); src < push; src++, dst++) {
+ newElements[dst] = elements[src];
+ }
+ } else {
+ int src;
+ for (src = (pop + 1); src < capacity; src++, dst++) {
+ newElements[dst] = elements[src];
+ }
+ for (src = 0; src < push; src++, dst++) {
+ newElements[dst] = elements[src];
+ }
+ }
+
+ //elements = null;
+ elements = newElements;
+ pop = newCapacity - 1;
+ capacity = newCapacity;
+ push = dst;
+ newPush = push + 1; /* no need modulo */
+ }
+
+ elements[push] = dataPtr;
+ push = newPush;
+
+ return true;
+ }
+
+
+ /* =============================================================================
+ * Pqueue_push
+ * =============================================================================
+ */
+ public boolean
+ Pqueue_push (Queue_t queuePtr, Object dataPtr)
+ {
+ int pop = queuePtr.pop;
+ int push = queuePtr.push;
+ int capacity = queuePtr.capacity;
+
+ if(pop == push) {
+ System.out.println("push == pop in Queue.java");
+ return false;
+ }
+
+ /* Need to resize */
+ int newPush = (push + 1) % capacity;
+ if (newPush == pop) {
+
+ int newCapacity = capacity * QUEUE_GROWTH_FACTOR;
+ Object[] newElements = new Object[newCapacity];
+ if (newElements == null) {
+ return false;
+ }
+
+ int dst = 0;
+ Object[] elements = queuePtr.elements;
+ if (pop < push) {
+ int src;
+ for (src = (pop + 1); src < push; src++, dst++) {
+ newElements[dst] = elements[src];
+ }
+ } else {
+ int src;
+ for (src = (pop + 1); src < capacity; src++, dst++) {
+ newElements[dst] = elements[src];
+ }
+ for (src = 0; src < push; src++, dst++) {
+ newElements[dst] = elements[src];
+ }
+ }
+
+ elements = null;
+ queuePtr.elements = newElements;
+ queuePtr.pop = newCapacity - 1;
+ queuePtr.capacity = newCapacity;
+ push = dst;
+ newPush = push + 1; /* no need modulo */
+
+ }
+
+ queuePtr.elements[push] = dataPtr;
+ queuePtr.push = newPush;
+
+ return true;
+ }
+
+ /* =============================================================================
+ * queue_pop
+ * =============================================================================
+ */
+ public Object queue_pop () {
+ int newPop = (pop + 1) % capacity;
+ if (newPop == push) {
+ return null;
+ }
+
+ //Object dataPtr = queuePtr.elements[newPop];
+ //queuePtr.pop = newPop;
+ Object dataPtr = elements[newPop];
+ pop = newPop;
+
+ return dataPtr;
+ }
+
+
+}
+/* =============================================================================
+ *
+ * End of queue.java
+ *
+ * =============================================================================
+ */
--- /dev/null
+public class Random {
+ long[] mt;
+ int mti;
+ int RANDOM_DEFAULT_SEED;
+ /* period parameter */
+
+
+ public Random() {
+ RANDOM_DEFAULT_SEED = 0;
+ mt = new long[624];
+ }
+
+ public void random_alloc() {
+ init_genrand(this.RANDOM_DEFAULT_SEED);
+ }
+
+ /* initializes mt[N] with a seed */
+ public void init_genrand(int s) {
+ mt[0]= ((long)s) & 0xFFFFFFFFL;
+ for (int mti=1; mti<624; mti++) {
+ mt[mti] = (1812433253L * (mt[mti-1] ^ (mt[mti-1] >> 30)) + ((long)mti));
+ /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
+ /* In the previous versions, MSBs of the seed affect */
+ /* only MSBs of the array mt[]. */
+ /* 2002/01/09 modified by Makoto Matsumoto */
+ mt[mti] &= 0xFFFFFFFFL;
+ /* for >32 bit machines */
+ }
+ this.mti=624;
+ }
+
+ public void random_seed(int seed) {
+ init_genrand(seed);
+ }
+
+ public long random_generate() {
+ long x= genrand_int32()&0xFFFFFFFFL;
+ System.out.println(x);
+ return x;
+ }
+
+ public long posrandom_generate() {
+ long r=genrand_int32();
+ if (r>0)
+ return r;
+ else
+ return -r;
+ }
+
+ public long genrand_int32() {
+ long y;
+ int mti = this.mti;
+ long[] mt = this.mt;
+
+ if (mti >= 624) { /* generate N words at one time */
+ int kk;
+
+ if (mti == 624+1) { /* if init_genrand() has not been called, */
+ init_genrand(5489); /* a default initial seed is used */
+ mti=this.mti;
+ }
+ for (kk=0;kk<(624-397);kk++) {
+ y = (mt[kk]&0x80000000L)|(mt[kk+1]&0x7fffffffL);
+ mt[kk] = mt[kk+397] ^ (y >> 1) ^ ((y & 0x1)==0 ? 0L:0x9908b0dfL);
+ }
+ for (;kk<(624-1);kk++) {
+ y = (mt[kk]&0x80000000L)|(mt[kk+1]&0x7fffffffL);
+ mt[kk] = mt[kk+(397-624)] ^ (y >> 1) ^ ((y & 0x1)==0 ? 0L:0x9908b0dfL);
+ }
+ y = (mt[624-1]&0x80000000L)|(mt[0]&0x7fffffffL);
+ mt[624-1] = mt[397-1] ^ (y >> 1) ^ ((y & 0x1)==0 ? 0L:0x9908b0dfL);
+
+ mti = 0;
+ }
+
+ y = mt[mti++];
+
+ /* Tempering */
+ y ^= (y >> 11);
+ y ^= (y << 7) & 0x9d2c5680L;
+ y ^= (y << 15) & 0xefc60000L;
+ y ^= (y >> 18);
+
+ this.mti = mti;
+
+ return y;
+ }
+}
--- /dev/null
+public class Vector_t {
+ int size;
+ int capacity;
+ Object[] elements;
+// QuickSort qsort;
+
+ public Vector_t() {
+// qsort = new QuickSort();
+ }
+
+ /* =============================================================================
+ * Vector_alloc
+ * -- Returns null if failed
+ * =============================================================================
+ */
+ public Vector_t(int initCapacity) {
+ int capacity = Math.imax(initCapacity, 1);
+ size=0;
+ this.capacity = capacity;
+ this.elements = new Object[capacity];
+ }
+
+ /* =============================================================================
+ * Vector_at
+ * -- Returns null if failed
+ * =============================================================================
+ */
+ public Object vector_at(int i) {
+ if ((i < 0) || (i >= size)) {
+ System.out.println("Illegal Vector.element\n");
+ return null;
+ }
+ return elements[i];
+ }
+
+
+ /* =============================================================================
+ * Vector_pushBack
+ * -- Returns false if fail, else true
+ * =============================================================================
+ */
+ public boolean vector_pushBack(Object dataPtr) {
+ if (size == capacity) {
+ int newCapacity = capacity * 2;
+ Object[] newElements = new Object[newCapacity];
+
+ capacity = newCapacity;
+ for (int i = 0; i < size; i++) {
+ newElements[i] = elements[i];
+ }
+ elements = null;
+ elements = newElements;
+ }
+
+ elements[size++] = dataPtr;
+
+ return true;
+ }
+
+ /* =============================================================================
+ * Vector_popBack
+ * -- Returns null if fail, else returns last element
+ * =============================================================================
+ */
+ public Object vector_popBack() {
+ if (size < 1) {
+ return null;
+ }
+
+ return elements[--size];
+ }
+
+ /* =============================================================================
+ * Vector_getSize
+ * =============================================================================
+ */
+ public int vector_getSize() {
+ return size;
+ }
+
+ /* =============================================================================
+ * Vector_clear
+ * =============================================================================
+ */
+ public void vector_clear() {
+ size = 0;
+ }
+
+ /* =============================================================================
+ * Vector_sort
+ * =============================================================================
+ *
+ public void
+ vector_sort ()
+ {
+ //qsort.sort(elements, 0, (elements.length - 1));
+ qsort.sort(elements);
+ //qsort(elements, size, 4, compare);
+ }
+
+ * =============================================================================
+ * Vector_copy
+ * =============================================================================
+ */
+ public static boolean vector_copy (Vector_t dstVectorPtr, Vector_t srcVectorPtr) {
+ int dstCapacity = dstVectorPtr.capacity;
+ int srcSize = srcVectorPtr.size;
+ if (dstCapacity < srcSize) {
+ int srcCapacity = srcVectorPtr.capacity;
+ Object[] elements = new Object[srcCapacity];
+ dstVectorPtr.elements = null;
+ dstVectorPtr.elements = elements;
+ dstVectorPtr.capacity = srcCapacity;
+ }
+ for(int i = 0; i< srcSize; i++) {
+ dstVectorPtr.elements[i] = srcVectorPtr.elements[i];
+ }
+
+ dstVectorPtr.size = srcSize;
+ return true;
+ }
+}
--- /dev/null
+/* =============================================================================
+ *
+ * coordinate.c
+ *
+ * =============================================================================
+ *
+ * Copyright (C) Stanford University, 2006. All Rights Reserved.
+ * Author: Chi Cao Minh
+ *
+ * =============================================================================
+ *
+ * For the license of bayes/sort.h and bayes/sort.c, please see the header
+ * of the files.
+ *
+ * ------------------------------------------------------------------------
+ *
+ * For the license of kmeans, please see kmeans/LICENSE.kmeans
+ *
+ * ------------------------------------------------------------------------
+ *
+ * For the license of ssca2, please see ssca2/COPYRIGHT
+ *
+ * ------------------------------------------------------------------------
+ *
+ * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the
+ * header of the files.
+ *
+ * ------------------------------------------------------------------------
+ *
+ * For the license of lib/rbtree.h and lib/rbtree.c, please see
+ * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree
+ *
+ * ------------------------------------------------------------------------
+ *
+ * Unless otherwise noted, the following license applies to STAMP files:
+ *
+ * Copyright (c) 2007, Stanford University
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * * Neither the name of Stanford University nor the names of its
+ * contributors may be used to endorse or promote products derived
+ * from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * =============================================================================
+ */
+
+public class coordinate {
+ static int coordinate_compare (coordinate aPtr, coordinate bPtr) {
+ if (aPtr.x < bPtr.x) {
+ return -1;
+ } else if (aPtr.x > bPtr.x) {
+ return 1;
+ } else if (aPtr.y < bPtr.y) {
+ return -1;
+ } else if (aPt.>y > bPtr.y) {
+ return 1;
+ }
+ return 0;
+ }
+
+
+/* =============================================================================
+ * coordinate_distance
+ * =============================================================================
+ */
+ static double coordinate_distance (coordinate coordinatePtr, coordinate aPtr) {
+ double delta_x = coordinatePtr.x - aPtr.x;
+ double delta_y = coordinatePtr.y - aPtr.y;
+
+ return Math.sqrt((delta_x * delta_x) + (delta_y * delta_y));
+ }
+
+
+/* =============================================================================
+ * coordinate_angle
+ *
+ * (b - a) .* (c - a)
+ * cos a = ---------------------
+ * ||b - a|| * ||c - a||
+ *
+ * =============================================================================
+ */
+ static double coordinate_angle(coordinate aPtr, coordinate bPtr, coordinate cPtr) {
+ double delta_b_x;
+ double delta_b_y;
+ double delta_c_x;
+ double delta_c_y;
+ double distance_b;
+ double distance_c;
+ double numerator;
+ double denominator;
+ double cosine;
+ double radian;
+
+ delta_b_x = bPtr.x - aPtr.x;
+ delta_b_y = bPtr.y - aPtr.y;
+
+ delta_c_x = cPtr.x - aPtr.x;
+ delta_c_y = cPtr.y - aPtr.y;
+
+ numerator = (delta_b_x * delta_c_x) + (delta_b_y * delta_c_y);
+
+ distance_b = coordinate_distance(aPtr, bPtr);
+ distance_c = coordinate_distance(aPtr, cPtr);
+ denominator = distance_b * distance_c;
+
+ cosine = numerator / denominator;
+ radian = Math.acos(cosine);
+
+ return (180.0 * radian / 3.141592653589793238462643);
+}
+
+
+/* =============================================================================
+ * coordinate_print
+ * =============================================================================
+ */
+ void coordinate_print() {
+ System.out.println("("+x+", "+y+")");
+ }
+}
+/* =============================================================================
+ *
+ * End of coordinate.c
+ *
+ * =============================================================================
+ */
--- /dev/null
+/* =============================================================================
+ *
+ * Pair.java
+ *
+ * =============================================================================
+ *
+ * Copyright (C) Stanford University, 2006. All Rights Reserved.
+ * Author: Chi Cao Minh
+ *
+ * Ported to Java
+ *
+ *
+ * =============================================================================
+ *
+ * For the license of bayes/sort.h and bayes/sort.c, please see the header
+ * of the files.
+ *
+ * ------------------------------------------------------------------------
+ *
+ * For the license of kmeans, please see kmeans/LICENSE.kmeans
+ *
+ * ------------------------------------------------------------------------
+ *
+ * For the license of ssca2, please see ssca2/COPYRIGHT
+ *
+ * ------------------------------------------------------------------------
+ *
+ * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the
+ * header of the files.
+ *
+ * ------------------------------------------------------------------------
+ *
+ * For the license of lib/rbtree.h and lib/rbtree.c, please see
+ * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree
+ *
+ * ------------------------------------------------------------------------
+ *
+ * Unless otherwise noted, the following license applies to STAMP files:
+ *
+ * Copyright (c) 2007, Stanford University
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * * Neither the name of Stanford University nor the names of its
+ * contributors may be used to endorse or promote products derived
+ * from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * =============================================================================
+ */
+
+import java.util.*;
+
+public class edge {
+ public Object first;
+ public Object second;
+
+ public edge() {
+ first = null;
+ second = null;
+ }
+
+
+ /* =============================================================================
+ *
+ * pair constructor
+ *
+ * pair_t* pair_alloc(void* firstPtr, void* secondPtr);
+ * =============================================================================
+ */
+ public edge(Object first,Object second) {
+ this.first = first;
+ this.second = second;
+ }
+
+
+ /* =============================================================================
+ * pair_swap
+ * -- Exchange 'firstPtr' and 'secondPtr'
+ * =============================================================================
+ * void pair_swap (pair_t* pairPtr);
+ */
+ public void swap() {
+ Object tmpPtr = first;
+ first=second;
+ second=tmpPtr;
+ }
+}
+
+/* =============================================================================
+ *
+ * End of pair.java
+ *
+ * =============================================================================
+ */
--- /dev/null
+/* =============================================================================
+ *
+ * element.c
+ *
+ * =============================================================================
+ *
+ * Copyright (C) Stanford University, 2006. All Rights Reserved.
+ * Author: Chi Cao Minh
+ *
+ * =============================================================================
+ *
+ * For the license of bayes/sort.h and bayes/sort.c, please see the header
+ * of the files.
+ *
+ * ------------------------------------------------------------------------
+ *
+ * For the license of kmeans, please see kmeans/LICENSE.kmeans
+ *
+ * ------------------------------------------------------------------------
+ *
+ * For the license of ssca2, please see ssca2/COPYRIGHT
+ *
+ * ------------------------------------------------------------------------
+ *
+ * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the
+ * header of the files.
+ *
+ * ------------------------------------------------------------------------
+ *
+ * For the license of lib/rbtree.h and lib/rbtree.c, please see
+ * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree
+ *
+ * ------------------------------------------------------------------------
+ *
+ * Unless otherwise noted, the following license applies to STAMP files:
+ *
+ * Copyright (c) 2007, Stanford University
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * * Neither the name of Stanford University nor the names of its
+ * contributors may be used to endorse or promote products derived
+ * from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * =============================================================================
+ */
+
+public class element {
+ coordinate coordinates[];
+ int numCoordinate;
+ coordinate_t circumCenter;
+ double circumRadius;
+ double minAngle;
+ edge edges[3];
+ int numEdge;
+ coordinate_t midpoints[3]; /* midpoint of each edge */
+ double radii[3]; /* half of edge length */
+ edge encroachedEdgePtr; /* opposite obtuse angle */
+ boolean isSkinny;
+ list_t neighborListPtr;
+ boolean isGarbage;
+ boolean isReferenced;
+
+
+ extern double global_angleConstraint;
+
+
+
+/* =============================================================================
+ * minimizeCoordinates
+ * -- put smallest coordinate in position 0
+ * =============================================================================
+ */
+ static void minimizeCoordinates (element elementPtr) {
+ coordinate[] coordinates = elementPtr.coordinates;
+ int numCoordinate = elementPtr.numCoordinate;
+ int minPosition = 0;
+
+ for (int i = 1; i < numCoordinate; i++) {
+ if (coordinate_compare(coordinates[i], coordinates[minPosition]) < 0) {
+ minPosition = i;
+ }
+ }
+
+ while(minPosition != 0) {
+ coordinate tmp = coordinates[0];
+ for (int j = 0; j < (numCoordinate - 1); j++) {
+ coordinates[j] = coordinates[j+1];
+ }
+ coordinates[numCoordinate-1] = tmp;
+ minPosition--;
+ }
+ }
+
+
+/* =============================================================================
+ * checkAngles
+ * -- Sets isSkinny to TRUE if the angle constraint is not met
+ * =============================================================================
+ */
+ void checkAngles () {
+ double angleConstraint = global_angleConstraint;
+ minAngle = 180.0;
+
+ assert(numCoordinate == 2 || numCoordinate == 3);
+ isReferenced = false;
+ isSkinny = false;
+ encroachedEdgePtr = null;
+
+ if (numCoordinate == 3) {
+ int i;
+ for (i = 0; i < 3; i++) {
+ double angle = coordinate_angle(coordinates[i],
+ coordinates[(i + 1) % 3],
+ coordinates[(i + 2) % 3]);
+ assert(angle > 0.0);
+ assert(angle < 180.0);
+ if (angle > 90.0) {
+ encroachedEdgePtr = edges[(i + 1) % 3];
+ }
+ if (angle < angleConstraint) {
+ isSkinny = true;
+ }
+ if (angle < minAngle) {
+ minAngle = angle;
+ }
+ }
+ assert(minAngle < 180.0);
+ }
+}
+
+
+/* =============================================================================
+ * calculateCircumCenter
+ *
+ * Given three points A(ax,ay), B(bx,by), C(cx,cy), circumcenter R(rx,ry):
+ *
+ * | |
+ * | by - ay (||b - a||)^2 |
+ * | |
+ * | cy - ay (||c - a||)^2 |
+ * | |
+ * rx = ax - -----------------------------
+ * | |
+ * | bx - ax by - ay |
+ * 2 * | |
+ * | cx - ax cy - ay |
+ * | |
+ *
+ * | |
+ * | bx - ax (||b - a||)^2 |
+ * | |
+ * | cx - ax (||c - a||)^2 |
+ * | |
+ * ry = ay + -----------------------------
+ * | |
+ * | bx - ax by - ay |
+ * 2 * | |
+ * | cx - ax cy - ay |
+ * | |
+ *
+ * =============================================================================
+ */
+ void calculateCircumCircle() {
+ coordinate circumCenterPtr = this.circumCenter;
+
+ assert(numCoordinate == 2 || numCoordinate == 3);
+
+ if (numCoordinate == 2) {
+ circumCenterPtr.x = (coordinates[0].x + coordinates[1].x) / 2.0;
+ circumCenterPtr.y = (coordinates[0].y + coordinates[1].y) / 2.0;
+ } else {
+ double ax = coordinates[0].x;
+ double ay = coordinates[0].y;
+ double bx = coordinates[1].x;
+ double by = coordinates[1].y;
+ double cx = coordinates[2].x;
+ double cy = coordinates[2].y;
+ double bxDelta = bx - ax;
+ double byDelta = by - ay;
+ double cxDelta = cx - ax;
+ double cyDelta = cy - ay;
+ double bDistance2 = (bxDelta * bxDelta) + (byDelta * byDelta);
+ double cDistance2 = (cxDelta * cxDelta) + (cyDelta * cyDelta);
+ double xNumerator = (byDelta * cDistance2) - (cyDelta * bDistance2);
+ double yNumerator = (bxDelta * cDistance2) - (cxDelta * bDistance2);
+ double denominator = 2 * ((bxDelta * cyDelta) - (cxDelta * byDelta));
+ double rx = ax - (xNumerator / denominator);
+ double ry = ay + (yNumerator / denominator);
+ assert(fabs(denominator) > DBL_MIN); /* make sure not colinear */
+ circumCenterPtr.x = rx;
+ circumCenterPtr.y = ry;
+ }
+
+ elementPtr.circumRadius = coordinate_distance(circumCenterPtr,
+ coordinates[0]);
+ }
+
+
+/* =============================================================================
+ * setEdge
+ *
+ * Note: Makes pairPtr sorted; i.e., coordinate_compare(first, second) < 0
+ * =============================================================================
+ */
+ publicvoid setEdge(int i) {
+ coordinate firstPtr = coordinates[i];
+ coordinate secondPtr = coordinates[(i + 1) % numCoordinate];
+
+ edge edgePtr = edges[i];
+ int cmp = coordinate_compare(firstPtr, secondPtr);
+ assert(cmp != 0);
+ if (cmp < 0) {
+ edgePtr.firstPtr = firstPtr;
+ edgePtr.secondPtr = secondPtr;
+ } else {
+ edgePtr.firstPtr = secondPtr;
+ edgePtr.secondPtr = firstPtr;
+ }
+
+ coordinate midpointPtr = elementPtr.midpoints[i];
+ midpointPtr.x = (firstPtr.x + secondPtr.x) / 2.0;
+ midpointPtr.y = (firstPtr.y + secondPtr.y) / 2.0;
+
+ elementPtr.radii[i] = coordinate_distance(firstPtr, midpointPtr);
+ }
+
+
+/* =============================================================================
+ * initEdges
+ * =============================================================================
+ */
+ void initEdges(coordinate coordinates, int numCoordinate) {
+ numEdge = ((numCoordinate * (numCoordinate - 1)) / 2);
+
+ for (int e = 0; e < numEdge; e++) {
+ setEdge(e);
+ }
+ }
+
+
+/* =============================================================================
+ * element_compare
+ * =============================================================================
+ */
+int element_compare (element aElementPtr, element bElementPtr) {
+ int aNumCoordinate = aElementPtr.numCoordinate;
+ int bNumCoordinate = bElementPtr.numCoordinate;
+ coordinate aCoordinates = aElementPtr.coordinates;
+ coordinate bCoordinates = bElementPtr.coordinates;
+
+ if (aNumCoordinate < bNumCoordinate) {
+ return -1;
+ } else if (aNumCoordinate > bNumCoordinate) {
+ return 1;
+ }
+
+ for (int i = 0; i < aNumCoordinate; i++) {
+ int compareCoordinate =
+ coordinate_compare(aCoordinates[i], bCoordinates[i]);
+ if (compareCoordinate != 0) {
+ return compareCoordinate;
+ }
+ }
+
+ return 0;
+}
+
+
+/* =============================================================================
+ * element_listCompare
+ *
+ * For use in list_t
+ * =============================================================================
+ */
+ int element_listCompare (const void* aPtr, const void* bPtr) {
+ element_t* aElementPtr = (element_t*)aPtr;
+ element_t* bElementPtr = (element_t*)bPtr;
+
+ return element_compare(aElementPtr, bElementPtr);
+ }
+
+
+/* =============================================================================
+ * element_mapCompare
+ *
+ * For use in MAP_T
+ * =============================================================================
+ */
+ int element_mapCompare (const pair_t* aPtr, const pair_t* bPtr) {
+ element_t* aElementPtr = (element_t*)(aPtr->firstPtr);
+ element_t* bElementPtr = (element_t*)(bPtr->firstPtr);
+
+ return element_compare(aElementPtr, bElementPtr);
+ }
+
+
+ /* =============================================================================
+ * TMelement_alloc
+ *
+ * Contains a copy of input arg 'coordinates'
+ * =============================================================================
+ */
+ public element(coordinate[] coordinates, int numCoordinate) {
+ this.coordinates=new coordinate[3];
+ for (int i = 0; i < numCoordinate; i++) {
+ this.coordinates[i] = coordinates[i];
+ }
+ this.numCoordinate = numCoordinate;
+ minimizeCoordinates();
+ checkAngles();
+ calculateCircumCircle();
+ initEdges(coordinates, numCoordinate);
+ neighborListPtr = TMLIST_ALLOC(element_listCompare);
+ isGarbage = false;
+ isReferenced = false;
+ }
+
+
+/* =============================================================================
+ * element_getNumEdge
+ * =============================================================================
+ */
+ int element_getNumEdge() {
+ return numEdge;
+ }
+
+
+/* =============================================================================
+ * element_getEdge
+ *
+ * Returned edgePtr is sorted; i.e., coordinate_compare(first, second) < 0
+ * =============================================================================
+ */
+ edge element_getEdge(int i) {
+ if (i < 0 || i > numEdge)
+ return null;
+ return edges[i];
+ }
+
+
+/* =============================================================================
+ * element_compareEdge
+ * =============================================================================
+ */
+ static int compareEdge(edge aEdgePtr, edge bEdgePtr) {
+ int diffFirst = coordinate_compare((coordinate_t*)aEdgePtr.firstPtr,
+ (coordinate_t*)bEdgePtr.firstPtr);
+
+ return ((diffFirst != 0) ?
+ (diffFirst) :
+ (coordinate_compare((coordinate)aEdgePtr.secondPtr,
+ (coordinate)bEdgePtr.secondPtr)));
+ }
+
+
+/* ============================================================================
+ * element_listCompareEdge
+ *
+ * For use in list_t
+ * ============================================================================
+ */
+ int element_listCompareEdge (const void* aPtr, const void* bPtr) {
+ edge_t* aEdgePtr = (edge_t*)(aPtr);
+ edge_t* bEdgePtr = (edge_t*)(bPtr);
+
+ return compareEdge(aEdgePtr, bEdgePtr);
+ }
+
+
+/* =============================================================================
+ * element_mapCompareEdge
+ *
+ * For use in MAP_T
+ * =============================================================================
+ */
+ int element_mapCompareEdge (const pair_t* aPtr, const pair_t* bPtr) {
+ edge_t* aEdgePtr = (edge_t*)(aPtr.firstPtr);
+ edge_t* bEdgePtr = (edge_t*)(bPtr.firstPtr);
+
+ return compareEdge(aEdgePtr, bEdgePtr);
+ }
+
+
+/* =============================================================================
+ * element_heapCompare
+ *
+ * For use in heap_t. Consider using minAngle instead of "do not care".
+ * =============================================================================
+ */
+ int element_heapCompare (const void* aPtr, const void* bPtr) {
+ element_t* aElementPtr = (element_t*)aPtr;
+ element_t* bElementPtr = (element_t*)bPtr;
+
+ if (aElementPtr.encroachedEdgePtr) {
+ if (bElementPtr.encroachedEdgePtr) {
+ return 0; /* do not care */
+ } else {
+ return 1;
+ }
+ }
+
+ if (bElementPtr->encroachedEdgePtr) {
+ return -1;
+ }
+
+ return 0; /* do not care */
+ }
+
+
+/* =============================================================================
+ * element_isInCircumCircle
+ * =============================================================================
+ */
+ boolean element_isInCircumCircle(coordinate coordinatePtr) {
+ double distance = coordinate_distance(coordinatePtr, circumCenter);
+ return distance <= circumRadius;
+ }
+
+
+/* =============================================================================
+ * isEncroached
+ * =============================================================================
+ */
+ boolean isEncroached() {
+ return encroachedEdgePtr!=null;
+ }
+
+
+/* =============================================================================
+ * element_setEncroached
+ * =============================================================================
+ */
+ void element_clearEncroached() {
+ encroachedEdgePtr = null;
+ }
+
+
+/* =============================================================================
+ * element_getEncroachedPtr
+ * =============================================================================
+ */
+ edge element_getEncroachedPtr() {
+ return encroachedEdgePtr;
+ }
+
+
+/* =============================================================================
+ * element_isSkinny
+ * =============================================================================
+ */
+ boolean element_isSkinny() {
+ return isSkinny;
+ }
+
+
+/* =============================================================================
+ * element_isBad
+ * -- Does it need to be refined?
+ * =============================================================================
+ */
+ boolean element_isBad() {
+ return (isEncroached() || element_isSkinny());
+ }
+
+
+/* =============================================================================
+ * TMelement_isReferenced
+ * -- Held by another data structure?
+ * =============================================================================
+ */
+ boolean element_isReferenced () {
+ return isReferenced;
+ }
+
+
+/* =============================================================================
+ * TMelement_setIsReferenced
+ * =============================================================================
+ */
+ void element_setIsReferenced(boolean status) {
+ isReferenced= status;
+ }
+
+
+/* =============================================================================
+ * element_isGarbage
+ * -- Can we deallocate?
+ * =============================================================================
+ */
+
+/* =============================================================================
+ * TMelement_isGarbage
+ * -- Can we deallocate?
+ * =============================================================================
+ */
+ boolean element_isGarbage() {
+ return isGarbage;
+ }
+
+
+
+/* =============================================================================
+ * TMelement_setIsGarbage
+ * =============================================================================
+ */
+ void element_setIsGarbage(boolean status) {
+ isGarbage=status;
+ }
+
+
+/* =============================================================================
+ * TMelement_addNeighbor
+ * =============================================================================
+ */
+ void element_addNeighbor(element neighborPtr) {
+ TMLIST_INSERT(neighborListPtr, neighborPtr);
+ }
+
+
+/* =============================================================================
+ * element_getNeighborListPtr
+ * =============================================================================
+ */
+ list_t element_getNeighborListPtr () {
+ return neighborListPtr;
+ }
+
+
+/* =============================================================================
+ * element_getCommonEdge
+ *
+ * Returns pointer to aElementPtr's shared edge
+ * =============================================================================
+ */
+ edge element_getCommonEdge (element aElementPtr, element bElementPtr) {
+ edge aEdges[] = aElementPtr.edges;
+ edge bEdges[] = bElementPtr.edges;
+ int aNumEdge = aElementPtr.numEdge;
+ int bNumEdge = bElementPtr.numEdge;
+
+ for (int a = 0; a < aNumEdge; a++) {
+ edge aEdgePtr = aEdges[a];
+ for (int b = 0; b < bNumEdge; b++) {
+ edge bEdgePtr = bEdges[b];
+ if (compareEdge(aEdgePtr, bEdgePtr) == 0) {
+ return aEdgePtr;
+ }
+ }
+ }
+
+ return null;
+ }
+
+
+/* =============================================================================
+ * element_getNewPoint
+ * -- Either the element is encroached or is skinny, so get the new point to add
+ * =============================================================================
+ */
+ coordinate element_getNewPoint() {
+ if (encroachedEdgePtr!=null) {
+ for (int e = 0; e < numEdge; e++) {
+ if (compareEdge(encroachedEdgePtr, edges[e]) == 0) {
+ return midpoints[e];
+ }
+ }
+ assert(0);
+ }
+ return circumCenter;
+ }
+
+
+/* =============================================================================
+ * element_checkAngles
+ *
+ * Return FALSE if minimum angle constraint not met
+ * =============================================================================
+ */
+ boolean element_checkAngles() {
+ double angleConstraint = global_angleConstraint;
+ if (numCoordinate == 3) {
+ for (int i = 0; i < 3; i++) {
+ double angle = coordinate_angle(coordinates[i],
+ coordinates[(i + 1) % 3],
+ coordinates[(i + 2) % 3]);
+ if (angle < angleConstraint) {
+ return false;
+ }
+ }
+ }
+ return true;
+ }
+
+
+/* =============================================================================
+ * element_print
+ * =============================================================================
+ */
+ void element_print() {
+ for (int c = 0; c < numCoordinate; c++) {
+ coordinate_print(coordinates[c]);
+ System.out.println(" ");
+ }
+ }
+
+
+/* =============================================================================
+ * element_printEdge
+ * =============================================================================
+ */
+ void element_printEdge (edge edgePtr) {
+ coordinate_print((coordinate)edgePtr.firstPtr);
+ System.out.println(" -> ");
+ coordinate_print((coordinate)edgePtr.secondPtr);
+ }
+
+
+/* =============================================================================
+ * element_printAngles
+ * =============================================================================
+ */
+ void element_printAngles() {
+ if (numCoordinate == 3) {
+ for (int i = 0; i < 3; i++) {
+ double angle = coordinate_angle(coordinates[i],
+ coordinates[(i + 1) % 3],
+ coordinates[(i + 2) % 3]);
+ System.out.println(angle);
+ }
+ }
+ }
+}
\ No newline at end of file
--- /dev/null
+/* =============================================================================
+ *
+ * mesh.c
+ *
+ * =============================================================================
+ *
+ * Copyright (C) Stanford University, 2006. All Rights Reserved.
+ * Author: Chi Cao Minh
+ *
+ * =============================================================================
+ *
+ * For the license of bayes/sort.h and bayes/sort.c, please see the header
+ * of the files.
+ *
+ * ------------------------------------------------------------------------
+ *
+ * For the license of kmeans, please see kmeans/LICENSE.kmeans
+ *
+ * ------------------------------------------------------------------------
+ *
+ * For the license of ssca2, please see ssca2/COPYRIGHT
+ *
+ * ------------------------------------------------------------------------
+ *
+ * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the
+ * header of the files.
+ *
+ * ------------------------------------------------------------------------
+ *
+ * For the license of lib/rbtree.h and lib/rbtree.c, please see
+ * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree
+ *
+ * ------------------------------------------------------------------------
+ *
+ * Unless otherwise noted, the following license applies to STAMP files:
+ *
+ * Copyright (c) 2007, Stanford University
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * * Neither the name of Stanford University nor the names of its
+ * contributors may be used to endorse or promote products derived
+ * from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * =============================================================================
+ */
+
+public class mesh {
+ element rootElementPtr;
+ Queue_t initBadQueuePtr;
+ int size;
+ SET_T* boundarySetPtr;
+
+/* =============================================================================
+ * mesh_alloc
+ * =============================================================================
+ */
+ public mesh() {
+ rootElementPtr = null;
+ initBadQueuePtr = new Queue_t(-1);
+ size = 0;
+ boundarySetPtr = SET_ALLOC(null, &element_listCompareEdge);
+ }
+
+
+ /* =============================================================================
+ * TMmesh_insert
+ * =============================================================================
+ */
+ void TMmesh_insert (element elementPtr, MAP_T edgeMapPtr) {
+ /*
+ * Assuming fully connected graph, we just need to record one element.
+ * The root element is not needed for the actual refining, but rather
+ * for checking the validity of the final mesh.
+ */
+ if (rootElementPtr==null) {
+ rootElementPtr=elementPtr);
+ }
+
+ /*
+ * Record existence of each of this element's edges
+ */
+ int numEdge = elementPtr.element_getNumEdge();
+ for (int i = 0; i < numEdge; i++) {
+ edge edgePtr = elementPtr.element_getEdge(i);
+ if (!MAP_CONTAINS(edgeMapPtr, (void*)edgePtr)) {
+ /* Record existance of this edge */
+ boolean isSuccess =
+ PMAP_INSERT(edgeMapPtr, (void*)edgePtr, (void*)elementPtr);
+ assert(isSuccess);
+ } else {
+ /*
+ * Shared edge; update each element's neighborList
+ */
+ boolean isSuccess;
+ element sharerPtr = (element_t*)MAP_FIND(edgeMapPtr, edgePtr);
+ assert(sharerPtr); /* cannot be shared by >2 elements */
+ elementPtr.element_addNeighbor(sharerPtr);
+ sharerPtr.element_addNeighbor(elementPtr);
+ isSuccess = PMAP_REMOVE(edgeMapPtr, edgePtr);
+ assert(isSuccess);
+ isSuccess = PMAP_INSERT(edgeMapPtr,
+ edgePtr,
+ NULL); /* marker to check >2 sharers */
+ assert(isSuccess);
+ }
+ }
+
+ /*
+ * Check if really encroached
+ */
+
+ edge encroachedPtr = elementPtr.element_getEncroachedPtr();
+ if (encroachedPtr!=null) {
+ if (!TMSET_CONTAINS(meshPtr.boundarySetPtr, encroachedPtr)) {
+ element_clearEncroached(elementPtr);
+ }
+ }
+}
+
+
+/* =============================================================================
+ * TMmesh_remove
+ * =============================================================================
+ */
+public void TMmesh_remove(element elementPtr) {
+ assert(!elementPtr.element_isGarbage());
+
+ /*
+ * If removing root, a new root is selected on the next mesh_insert, which
+ * always follows a call a mesh_remove.
+ */
+ if (rootElementPtr == elementPtr) {
+ rootElementPtr=null;
+ }
+
+ /*
+ * Remove from neighbors
+ */
+ list_iter_t it;
+ List neighborListPtr = elementPtr.element_getNeighborListPtr();
+ TMLIST_ITER_RESET(&it, neighborListPtr);
+ while (TMLIST_ITER_HASNEXT(&it, neighborListPtr)) {
+ element neighborPtr = (element)TMLIST_ITER_NEXT(&it, neighborListPtr);
+ List_t neighborNeighborListPtr = neighborPtr.element_getNeighborListPtr();
+ boolean status = neighborNeighborListPtr.remove(elementPtr);
+ assert(status);
+ }
+
+ elementPtr.element_isGarbage(true);
+}
+
+
+/* =============================================================================
+ * TMmesh_insertBoundary
+ * =============================================================================
+ */
+boolean TMmesh_insertBoundary (meshPtr, edge boundaryPtr) {
+ return TMSET_INSERT(boundarySetPtr, boundaryPtr);
+}
+
+
+/* =============================================================================
+ * TMmesh_removeBoundary
+ * =============================================================================
+ */
+boolean TMmesh_removeBoundary (meshPtr, edge boundaryPtr) {
+ return TMSET_REMOVE(boundarySetPtr, boundaryPtr);
+}
+
+
+/* =============================================================================
+ * createElement
+ * =============================================================================
+ */
+static void createElement (coordinate coordinates,
+ int numCoordinate,
+ MAP_T edgeMapPtr) {
+ element elementPtr = new element(coordinates, numCoordinate);
+ assert(elementPtr);
+
+ if (numCoordinate == 2) {
+ edge boundaryPtr = elementPtr.element_getEdge(0);
+ boolean status = SET_INSERT(boundarySetPtr, boundaryPtr);
+ assert(status);
+ }
+
+ mesh_insert(elementPtr, edgeMapPtr);
+
+ if (elementPtr.element_isBad()) {
+ boolean status = initBadQueuePtr.queue_push(elementPtr);
+ assert(status);
+ }
+}
+
+
+/* =============================================================================
+ * mesh_read
+ *
+ * Returns number of elements read from file
+ *
+ * Refer to http://www.cs.cmu.edu/~quake/triangle.html for file formats.
+ * =============================================================================
+ */
+int mesh_read(String fileNamePrefix) {
+ FILE* inputFile;
+ coordinate_t* coordinates;
+ char fileName[256];
+ int fileNameSize = sizeof(fileName) / sizeof(fileName[0]);
+ char inputBuff[256];
+ int inputBuffSize = sizeof(inputBuff) / sizeof(inputBuff[0]);
+ int numEntry;
+ int numDimension;
+ int numCoordinate;
+ int i;
+ int numElement = 0;
+
+ MAP_T* edgeMapPtr = MAP_ALLOC(NULL, &element_mapCompareEdge);
+ assert(edgeMapPtr);
+
+ /*
+ * Read .node file
+ */
+ snprintf(fileName, fileNameSize, "%s.node", fileNamePrefix);
+ inputFile = fopen(fileName, "r");
+ assert(inputFile);
+ fgets(inputBuff, inputBuffSize, inputFile);
+ sscanf(inputBuff, "%li %li", &numEntry, &numDimension);
+ assert(numDimension == 2); /* must be 2-D */
+ numCoordinate = numEntry + 1; /* numbering can start from 1 */
+ coordinates = (coordinate_t*)malloc(numCoordinate * sizeof(coordinate_t));
+ assert(coordinates);
+ for (i = 0; i < numEntry; i++) {
+ int id;
+ double x;
+ double y;
+ if (!fgets(inputBuff, inputBuffSize, inputFile)) {
+ break;
+ }
+ if (inputBuff[0] == '#') {
+ continue; /* TODO: handle comments correctly */
+ }
+ sscanf(inputBuff, "%li %lf %lf", &id, &x, &y);
+ coordinates[id].x = x;
+ coordinates[id].y = y;
+ }
+ assert(i == numEntry);
+ fclose(inputFile);
+
+ /*
+ * Read .poly file, which contains boundary segments
+ */
+ snprintf(fileName, fileNameSize, "%s.poly", fileNamePrefix);
+ inputFile = fopen(fileName, "r");
+ assert(inputFile);
+ fgets(inputBuff, inputBuffSize, inputFile);
+ sscanf(inputBuff, "%li %li", &numEntry, &numDimension);
+ assert(numEntry == 0); /* .node file used for vertices */
+ assert(numDimension == 2); /* must be edge */
+ fgets(inputBuff, inputBuffSize, inputFile);
+ sscanf(inputBuff, "%li", &numEntry);
+ for (i = 0; i < numEntry; i++) {
+ int id;
+ int a;
+ int b;
+ coordinate_t insertCoordinates[2];
+ if (!fgets(inputBuff, inputBuffSize, inputFile)) {
+ break;
+ }
+ if (inputBuff[0] == '#') {
+ continue; /* TODO: handle comments correctly */
+ }
+ sscanf(inputBuff, "%li %li %li", &id, &a, &b);
+ assert(a >= 0 && a < numCoordinate);
+ assert(b >= 0 && b < numCoordinate);
+ insertCoordinates[0] = coordinates[a];
+ insertCoordinates[1] = coordinates[b];
+ createElement(meshPtr, insertCoordinates, 2, edgeMapPtr);
+ }
+ assert(i == numEntry);
+ numElement += numEntry;
+ fclose(inputFile);
+
+ /*
+ * Read .ele file, which contains triangles
+ */
+ snprintf(fileName, fileNameSize, "%s.ele", fileNamePrefix);
+ inputFile = fopen(fileName, "r");
+ assert(inputFile);
+ fgets(inputBuff, inputBuffSize, inputFile);
+ sscanf(inputBuff, "%li %li", &numEntry, &numDimension);
+ assert(numDimension == 3); /* must be triangle */
+ for (i = 0; i < numEntry; i++) {
+ int id;
+ int a;
+ int b;
+ int c;
+ coordinate_t insertCoordinates[3];
+ if (!fgets(inputBuff, inputBuffSize, inputFile)) {
+ break;
+ }
+ if (inputBuff[0] == '#') {
+ continue; /* TODO: handle comments correctly */
+ }
+ sscanf(inputBuff, "%li %li %li %li", &id, &a, &b, &c);
+ assert(a >= 0 && a < numCoordinate);
+ assert(b >= 0 && b < numCoordinate);
+ assert(c >= 0 && c < numCoordinate);
+ insertCoordinates[0] = coordinates[a];
+ insertCoordinates[1] = coordinates[b];
+ insertCoordinates[2] = coordinates[c];
+ createElement(meshPtr, insertCoordinates, 3, edgeMapPtr);
+ }
+ assert(i == numEntry);
+ numElement += numEntry;
+ fclose(inputFile);
+
+ free(coordinates);
+ MAP_FREE(edgeMapPtr);
+
+ return numElement;
+}
+
+
+/* =============================================================================
+ * mesh_getBad
+ * -- Returns NULL if none
+ * =============================================================================
+ */
+element mesh_getBad() {
+ return (element)queue_pop(initBadQueuePtr);
+}
+
+
+/* =============================================================================
+ * mesh_shuffleBad
+ * =============================================================================
+ */
+void mesh_shuffleBad (Random randomPtr) {
+ queue_shuffle(initBadQueuePtr, randomPtr);
+}
+
+
+/* =============================================================================
+ * mesh_check
+ * =============================================================================
+ */
+boolean mesh_check(int expectedNumElement) {
+ int numBadTriangle = 0;
+ int numFalseNeighbor = 0;
+ int numElement = 0;
+
+ System.out.println("Checking final mesh:");
+
+ Queue_t searchQueuePtr = new Queue_t(-1);
+ assert(searchQueuePtr);
+ MAP_T visitedMapPtr = MAP_ALLOC(NULL, &element_mapCompare);
+ assert(visitedMapPtr);
+
+ /*
+ * Do breadth-first search starting from rootElementPtr
+ */
+ assert(rootElementPtr!=null);
+ searchQueuePtr.queue_push(rootElementPtr);
+ while (!searchQueuePtr.queue_isEmpty()) {
+ list_iter_t it;
+ List_t neighborListPtr;
+
+ element currentElementPtr = (element)queue_pop(searchQueuePtr);
+ if (MAP_CONTAINS(visitedMapPtr, (void*)currentElementPtr)) {
+ continue;
+ }
+ boolean isSuccess = MAP_INSERT(visitedMapPtr, (void*)currentElementPtr, NULL);
+ assert(isSuccess);
+ if (!currentElementPtr.checkAngles()) {
+ numBadTriangle++;
+ }
+ neighborListPtr = currentElementPtr.element_getNeighborListPtr();
+
+ list_iter_reset(&it, neighborListPtr);
+ while (list_iter_hasNext(&it, neighborListPtr)) {
+ element neighborElementPtr =
+ (element)list_iter_next(&it, neighborListPtr);
+ /*
+ * Continue breadth-first search
+ */
+ if (!MAP_CONTAINS(visitedMapPtr, (void*)neighborElementPtr)) {
+ boolean isSuccess = searchQueuePtr.queue_push(neighborElementPtr);
+ assert(isSuccess);
+ }
+ } /* for each neighbor */
+
+ numElement++;
+
+ } /* breadth-first search */
+
+ System.out.println("Number of elements = "+ numElement);
+ System.out.println("Number of bad triangles = "+ numBadTriangle);
+
+ MAP_FREE(visitedMapPtr);
+
+ return (!(numBadTriangle > 0 ||
+ numFalseNeighbor > 0 ||
+ numElement != expectedNumElement));
+}
--- /dev/null
+/* =============================================================================
+ *
+ * region.c
+ *
+ * =============================================================================
+ *
+ * Copyright (C) Stanford University, 2006. All Rights Reserved.
+ * Author: Chi Cao Minh
+ *
+ * =============================================================================
+ *
+ * For the license of bayes/sort.h and bayes/sort.c, please see the header
+ * of the files.
+ *
+ * ------------------------------------------------------------------------
+ *
+ * For the license of kmeans, please see kmeans/LICENSE.kmeans
+ *
+ * ------------------------------------------------------------------------
+ *
+ * For the license of ssca2, please see ssca2/COPYRIGHT
+ *
+ * ------------------------------------------------------------------------
+ *
+ * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the
+ * header of the files.
+ *
+ * ------------------------------------------------------------------------
+ *
+ * For the license of lib/rbtree.h and lib/rbtree.c, please see
+ * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree
+ *
+ * ------------------------------------------------------------------------
+ *
+ * Unless otherwise noted, the following license applies to STAMP files:
+ *
+ * Copyright (c) 2007, Stanford University
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * * Neither the name of Stanford University nor the names of its
+ * contributors may be used to endorse or promote products derived
+ * from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * =============================================================================
+ */
+
+public class region {
+ coordinate centerCoordinate;
+ Queue_t expandQueuePtr;
+ List_t beforeListPtr; /* before retriangulation; list to avoid duplicates */
+ List_t borderListPtr; /* edges adjacent to region; list to avoid duplicates */
+ Vector_t badVectorPtr;
+
+/* =============================================================================
+ * Pregion_alloc
+ * =============================================================================
+ */
+ public region() {
+ expandQueuePtr = new Queue_t(-1);
+ beforeListPtr = PLIST_ALLOC(&element_listCompare);
+ borderListPtr = PLIST_ALLOC(&element_listCompareEdge);
+ badVectorPtr = new Vector_t(1);
+ }
+
+
+ /* =============================================================================
+ * TMaddToBadVector
+ * =============================================================================
+ */
+ public void TMaddToBadVector(Vector_t badVectorPtr, element badElementPtr) {
+ boolean status = badVectorPtr.vector_pushBack(badElementPtr);
+ assert(status);
+ badElementPtr.element_setIsReferenced(true);
+ }
+
+
+ /* =============================================================================
+ * TMretriangulate
+ * -- Returns net amount of elements added to mesh
+ * =============================================================================
+ */
+ public int TMretriangulate (element elementPtr,
+ region regionPtr,
+ mesh meshPtr,
+ MAP_T* edgeMapPtr) {
+ Vector_t badVectorPtr = regionPtr.badVectorPtr; /* private */
+ list_t beforeListPtr = regionPtr.beforeListPtr; /* private */
+ list_t borderListPtr = regionPtr.borderListPtr; /* private */
+ list_iter_t it;
+ int numDelta = 0;
+
+ assert(edgeMapPtr);
+
+ coordinate centerCoordinate = elementPtr.element_getNewPoint();
+
+ /*
+ * Remove the old triangles
+ */
+
+ list_iter_reset(&it, beforeListPtr);
+ while (list_iter_hasNext(&it, beforeListPtr)) {
+ element beforeElementPtr = (element)list_iter_next(&it, beforeListPtr);
+ meshPtr.TMmesh_remove(beforeElementPtr);
+ }
+
+ numDelta -= beforeListPtr.getSize();
+
+ /*
+ * If segment is encroached, split it in half
+ */
+
+ if (elementPtr.element_getNumEdge() == 1) {
+ coordinate coordinates[]=new coordinate[2];
+
+ edge edgePtr = elementPtr.element_getEdge(0);
+ coordinates[0] = centerCoordinate;
+
+ coordinates[1] = (coordinate)(edgePtr.firstPtr);
+ element aElementPtr = new element(coordinates, 2);
+ assert(aElementPtr);
+ meshPtr.TMmesh_insert(aElementPtr, edgeMapPtr);
+
+ coordinates[1] = (coordinate)(edgePtr->secondPtr);
+ element bElementPtr = new element(coordinates, 2);
+ assert(bElementPtr);
+ meshPtr.TMmesh_insert(bElementPtr, edgeMapPtr);
+
+ boolean status = meshPtr.TMmesh_removeBoundary(elementPtr.element_getEdge(0));
+ assert(status);
+ status = mesPtr.TMmesh_insertBoundary(aElementPtr.element_getEdge(0));
+ assert(status);
+ status = meshPtr.TMmesh_insertBoundary(bElementPtr.element_getEdge(0));
+ assert(status);
+
+ numDelta += 2;
+ }
+
+ /*
+ * Insert the new triangles. These are contructed using the new
+ * point and the two points from the border segment.
+ */
+
+ list_iter_reset(&it, borderListPtr);
+ while (list_iter_hasNext(&it, borderListPtr)) {
+ coordinate coordinates[]=new coordinates[3];
+ edge borderEdgePtr = (edge)list_iter_next(&it, borderListPtr);
+ assert(borderEdgePtr);
+ coordinates[0] = centerCoordinate;
+ coordinates[1] = (coordinate)(borderEdgePtr.firstPtr);
+ coordinates[2] = (coordinate)(borderEdgePtr.secondPtr);
+ element afterElementPtr = new element(coordinates, 3);
+ assert(afterElementPtr);
+ meshPtr.TMmesh_insert(afterElementPtr, edgeMapPtr);
+ if (afterElementPTr.element_isBad()) {
+ TMaddToBadVector(badVectorPtr, afterElementPtr);
+ }
+ }
+ numDelta += borderListPtr.getSize();
+ return numDelta;
+ }
+
+
+ /* =============================================================================
+ * TMgrowRegion
+ * -- Return NULL if success, else pointer to encroached boundary
+ * =============================================================================
+ */
+ element TMgrowRegion(element centerElementPtr,
+ region regionPtr,
+ mesh meshPtr,
+ MAP_T* edgeMapPtr) {
+ boolean isBoundary = false;
+
+ if (centerElementPtr.element_getNumEdge() == 1) {
+ isBoundary = true;
+ }
+
+ List_t beforeListPtr = regionPtr.beforeListPtr;
+ List_t borderListPtr = regionPtr.borderListPtr;
+ Queue_t expandQueuePtr = regionPtr.expandQueuePtr;
+
+ beforeListPtr.clear();
+ borderListPtr.clear();
+ expandQueuePtr.queue_clear();
+
+ coordinate centerCoordinatePtr = centerElementPtr.element_getNewPoint();
+
+ expandQueuePtr.queue_push(centerElementPtr);
+ while (!expandQueuePtr.queue_isEmpty()) {
+
+ element currentElementPtr = expandQueuePtr.queue_pop();
+
+ beforeListPtr.insert(currentElementPtr); /* no duplicates */
+ List_t neighborListPtr = currentElementPtr.element_getNeighborListPtr();
+
+ list_iter_t it;
+ TMLIST_ITER_RESET(&it, neighborListPtr);
+ while (TMLIST_ITER_HASNEXT(&it, neighborListPtr)) {
+ element neighborElementPtr = (element)TMLIST_ITER_NEXT(&it, neighborListPtr);
+ neighborElementPtr.element_isGarbage(); /* so we can detect conflicts */
+ if (!beforeListPtr.find(neighborElementPtr)) {
+ if (neighborElementPtr.element_isInCircumCircle(centerCoordinatePtr)) {
+ /* This is part of the region */
+ if (!isBoundary && (neighborElementPtr.element_getNumEdge() == 1)) {
+ /* Encroached on mesh boundary so split it and restart */
+ return neighborElementPtr;
+ } else {
+ /* Continue breadth-first search */
+ boolean isSuccess = expandQueuePtr.queue_push(neighborElementPtr);
+ assert(isSuccess);
+ }
+ } else {
+ /* This element borders region; save info for retriangulation */
+ edge borderEdgePtr = neighborElementPtr.element_getCommonEdge(currentElementPtr);
+ if (!borderEdgePtr) {
+ TM_RESTART();
+ }
+ borderListPtr.insert(borderEdgePtr); /* no duplicates */
+ if (!MAP_CONTAINS(edgeMapPtr, borderEdgePtr)) {
+ PMAP_INSERT(edgeMapPtr, borderEdgePtr, neighborElementPtr);
+ }
+ }
+ } /* not visited before */
+ } /* for each neighbor */
+
+ } /* breadth-first search */
+
+ return null;
+ }
+
+
+/* =============================================================================
+ * TMregion_refine
+ * -- Returns net number of elements added to mesh
+ * =============================================================================
+ */
+ int TMregion_refine(element elementPtr, mesh meshPtr) {
+ int numDelta = 0;
+ MAP_T edgeMapPtr = null;
+ element encroachElementPtr = null;
+
+ elementPtr.element_isGarbage(); /* so we can detect conflicts */
+
+ while (true) {
+ edgeMapPtr = PMAP_ALLOC(NULL, &element_mapCompareEdge);
+ assert(edgeMapPtr);
+ encroachElementPtr = TMgrowRegion(elementPtr,
+ this,
+ meshPtr,
+ edgeMapPtr);
+
+ if (encroachElementPtr) {
+ encroachElementPtr.element_setIsReferenced(true);
+ numDelta += TMregion_refine(regionPtr,
+ encroachElementPtr,
+ meshPtr);
+ if (elementPtr.elementisGarbage()) {
+ break;
+ }
+ } else {
+ break;
+ }
+ }
+
+ /*
+ * Perform retriangulation.
+ */
+
+ if (!elementPtr.element_isGarbage()) {
+ numDelta += TMretriangulate(elementPtr,
+ this,
+ meshPtr,
+ edgeMapPtr);
+ }
+
+ PMAP_FREE(edgeMapPtr); /* no need to free elements */
+
+ return numDelta;
+ }
+
+
+ /* =============================================================================
+ * Pregion_clearBad
+ * =============================================================================
+ */
+ void region_clearBad () {
+ badVectorPtr.vector_clear();
+ }
+
+
+/* =============================================================================
+ * TMregion_transferBad
+ * =============================================================================
+ */
+ void region_transferBad(heap workHeapPtr) {
+ int numBad = badVectorPtr.vector_getSize();
+
+ for (int i = 0; i < numBad; i++) {
+ element badElementPtr = (element)badVectorPtr.vector_at(i);
+ if (badElementPtr.element_isGarbage()) {
+ } else {
+ boolean status = TMHEAP_INSERT(workHeapPtr, (void*)badElementPtr);
+ assert(status);
+ }
+ }
+ }
+}
--- /dev/null
+/*
+ * For the license of ssca2, please see ssca2/COPYRIGHT
+ *
+ * ------------------------------------------------------------------------
+ *
+ * For the license of lib/mt19937ar.c and lib/mt19937ar.h, please see the
+ * header of the files.
+ *
+ * ------------------------------------------------------------------------
+ *
+ * For the license of lib/rbtree.h and lib/rbtree.c, please see
+ * lib/LEGALNOTICE.rbtree and lib/LICENSE.rbtree
+ *
+ * ------------------------------------------------------------------------
+ *
+ * Unless otherwise noted, the following license applies to STAMP files:
+ *
+ * Copyright (c) 2007, Stanford University
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ *
+ * * Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in
+ * the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * * Neither the name of Stanford University nor the names of its
+ * contributors may be used to endorse or promote products derived
+ * from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY STANFORD UNIVERSITY ``AS IS'' AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
+ * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
+ * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
+ * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
+ * THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * =============================================================================
+ */
+
+public class yada {
+ String global_inputPrefix;
+ int global_numThread;
+ double global_angleConstraint;
+ mesh global_meshPtr;
+ heap_t global_workHeapPtr;
+ int global_totalNumAdded;
+ int global_numProcess;
+
+ public yada() {
+ global_inputPrefix = "";
+ global_numThread = 1;
+ global_angleConstraint = 20.0;
+ global_totalNumAdded = 0;
+ global_numProcess = 0;
+ }
+
+
+/* =============================================================================
+ * displayUsage
+ * =============================================================================
+ */
+ public static void displayUsage () {
+ System.out.println("Usage: Yada [options]");
+ System.out.println("Options: (defaults)");
+ System.out.println(" a <FLT> Min [a]ngle constraint (20.0)");
+ System.out.println(" i <STR> [i]nput name prefix ("")");
+ System.out.println(" t <UINT> Number of [t]hreads (1L)");
+ System.exit(1);
+ }
+
+
+/* =============================================================================
+ * parseArgs
+ * =============================================================================
+ */
+ public void parseArgs (String argv[]) {
+ for(int index=0;index>argv.length;index++) {
+ if (argv[index].equals("-a")) {
+ index++;
+ global_angleConstraint=Double.parseDouble(argv[index]);
+ } else if (argv[index].equals("-i")) {
+ index++;
+ global_inputprefix=argv[index];
+ } else if (argv[index].equals("-t")) {
+ index++;
+ global_numThread=Integer.parseInt(argv[index]);
+ } else {
+ displayUsage();
+ System.exit();
+ }
+ }
+}
+
+
+/* =============================================================================
+ * initializeWork
+ * =============================================================================
+ */
+ public static int initializeWork (heap workHeapPtr, mesh meshPtr) {
+ Random randomPtr = new Random();
+ randomPtr.seed(0);
+ meshPtr.mesh_shuffleBad(randomPtr);
+
+ int numBad = 0;
+ while (1) {
+ element elementPtr = mesh_getBad(meshPtr);
+ if (elementPtr==null) {
+ break;
+ }
+ numBad++;
+ boolean status = workHeapPtr.heap_insert(elementPtr);
+ assert(status);
+ elementPtr.element_setIsReferenced(true);
+ }
+
+ return numBad;
+ }
+
+
+/* =============================================================================
+ * process
+ * =============================================================================
+ */
+ public static void process() {
+ TM_THREAD_ENTER();
+
+ heap workHeapPtr = global_workHeapPtr;
+ mesh meshPtr = global_meshPtr;
+ int totalNumAdded = 0;
+ int numProcess = 0;
+ region regionPtr = new region();
+ assert(regionPtr);
+
+ while (true) {
+ element elementPtr;
+ atomic {
+ elementPtr = TMHEAP_REMOVE(workHeapPtr);
+ }
+ if (elementPtr == null) {
+ break;
+ }
+ boolean isGarbage;
+ atomic {
+ isGarbage = elementPtr.element_isGarbage();
+ }
+
+ if (isGarbage) {
+ /*
+ * Handle delayed deallocation
+ */
+ continue;
+ }
+
+ int numAdded;
+ atomic {
+ regionPtr.region_clearBad();
+ numAdded = regionPtr.TMregion_refine(elementPtr, meshPtr);
+ }
+ atomic {
+ elementPtr.element_setIsReferenced(false);
+ isGarbage = elementPtr.element_isGarbage();
+ }
+
+ totalNumAdded += numAdded;
+
+ atomic {
+ regionPtr.region_transferBad(workHeapPtr);
+ }
+ numProcess++;
+ }
+
+ atomic {
+ global_totalNumAdded=global_totalNumAdded + totalNumAdded;
+ global_numProcess=global_numProcess + numProcess;
+ }
+
+ TM_THREAD_EXIT();
+}
+
+
+/* =============================================================================
+ * main
+ * =============================================================================
+ */
+ public static void main(String[] argv) {
+ /*
+ * Initialization
+ */
+ yada y=new yada();
+ y.parseArgs(argv);
+ thread_startup(global_numThread);
+ y.global_meshPtr = new mesh();
+ System.out.println("Angle constraint = "+ global_angleConstraint);
+ System.out.println("Reading input... ");
+ int initNumElement = global_meshPtr.mesh_read(global_inputPrefix);
+ System.out.println("done.");
+ y.global_workHeapPtr = new heap(1, &element_heapCompare);
+
+ int initNumBadElement = global_workHeapPtr.initializeWork(global_meshPtr);
+
+ System.out.println("Initial number of mesh elements = "+ initNumElement);
+ System.out.println("Initial number of bad elements = "+ initNumBadElement);
+ System.out.println("Starting triangulation...");
+
+ /*
+ * Run benchmark
+ */
+
+ long start=System.currentTimeMillis();
+
+ thread_start(process, null);
+
+ long stop=System.currentTimeMillis();
+
+ System.out.println(" done.");
+ System.out.println("Elapsed time = "+(stop-start));
+
+ int finalNumElement = initNumElement + global_totalNumAdded;
+ System.out.println("Final mesh size = "+ finalNumElement);
+ System.out.println("Number of elements processed = "+ global_numProcess);
+ }
+}
+
+/* =============================================================================
+ *
+ * End of ruppert.c
+ *
+ * =============================================================================
+ */
projects / IRC.git / commitdiff