001: /*
002: * $RCSfile: Heap.java,v $
003: *
004: * Copyright (c) 2007 Sun Microsystems, Inc. All rights reserved.
005: *
006: * Redistribution and use in source and binary forms, with or without
007: * modification, are permitted provided that the following conditions
008: * are met:
009: *
010: * - Redistribution of source code must retain the above copyright
011: * notice, this list of conditions and the following disclaimer.
012: *
013: * - Redistribution in binary form must reproduce the above copyright
014: * notice, this list of conditions and the following disclaimer in
015: * the documentation and/or other materials provided with the
016: * distribution.
017: *
018: * Neither the name of Sun Microsystems, Inc. or the names of
019: * contributors may be used to endorse or promote products derived
020: * from this software without specific prior written permission.
021: *
022: * This software is provided "AS IS," without a warranty of any
023: * kind. ALL EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND
024: * WARRANTIES, INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY,
025: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY
026: * EXCLUDED. SUN MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL
027: * NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF
028: * USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS
029: * DERIVATIVES. IN NO EVENT WILL SUN OR ITS LICENSORS BE LIABLE FOR
030: * ANY LOST REVENUE, PROFIT OR DATA, OR FOR DIRECT, INDIRECT, SPECIAL,
031: * CONSEQUENTIAL, INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER CAUSED AND
032: * REGARDLESS OF THE THEORY OF LIABILITY, ARISING OUT OF THE USE OF OR
033: * INABILITY TO USE THIS SOFTWARE, EVEN IF SUN HAS BEEN ADVISED OF THE
034: * POSSIBILITY OF SUCH DAMAGES.
035: *
036: * You acknowledge that this software is not designed, licensed or
037: * intended for use in the design, construction, operation or
038: * maintenance of any nuclear facility.
039: *
040: * $Revision: 1.4 $
041: * $Date: 2007/02/09 17:20:19 $
042: * $State: Exp $
043: */
044:
045: // ----------------------------------------------------------------------
046: //
047: // The reference to Fast Industrial Strength Triangulation (FIST) code
048: // in this release by Sun Microsystems is related to Sun's rewrite of
049: // an early version of FIST. FIST was originally created by Martin
050: // Held and Joseph Mitchell at Stony Brook University and is
051: // incorporated by Sun under an agreement with The Research Foundation
052: // of SUNY (RFSUNY). The current version of FIST is available for
053: // commercial use under a license agreement with RFSUNY on behalf of
054: // the authors and Stony Brook University. Please contact the Office
055: // of Technology Licensing at Stony Brook, phone 631-632-9009, for
056: // licensing information.
057: //
058: // ----------------------------------------------------------------------
059: package com.sun.j3d.utils.geometry;
060:
061: import java.io.*;
062: import java.util.*;
063: import javax.vecmath.*;
064:
065: class Heap {
066:
067: static void printHeapData(Triangulator triRef) {
068: int i;
069: System.out.println("\nHeap Data : numZero " + triRef.numZero
070: + " numHeap " + triRef.numHeap);
071: for (i = 0; i < triRef.numHeap; i++)
072: System.out.println(i + " ratio " + triRef.heap[i].ratio
073: + ", index " + triRef.heap[i].index + ", prev "
074: + triRef.heap[i].prev + ", next "
075: + triRef.heap[i].next);
076:
077: System.out.println(" ");
078:
079: }
080:
081: static void initHeap(Triangulator triRef) {
082: // Calculate the maximum bounds : N + (N -2)* 2.
083: // triRef.maxNumHeap = triRef.numPoints * 3;
084: triRef.maxNumHeap = triRef.numPoints;
085: triRef.heap = new HeapNode[triRef.maxNumHeap];
086:
087: triRef.numHeap = 0;
088: triRef.numZero = 0;
089:
090: }
091:
092: static void storeHeapData(Triangulator triRef, int index,
093: double ratio, int ind, int prev, int next) {
094: triRef.heap[index] = new HeapNode();
095: triRef.heap[index].ratio = ratio;
096: triRef.heap[index].index = ind;
097: triRef.heap[index].prev = prev;
098: triRef.heap[index].next = next;
099: }
100:
101: static void dumpOnHeap(Triangulator triRef, double ratio, int ind,
102: int prev, int next) {
103: int index;
104:
105: if (triRef.numHeap >= triRef.maxNumHeap) {
106: // System.out.println("Heap:dumpOnHeap.Expanding heap array ...");
107: HeapNode old[] = triRef.heap;
108: triRef.maxNumHeap = triRef.maxNumHeap + triRef.numPoints;
109: triRef.heap = new HeapNode[triRef.maxNumHeap];
110: System.arraycopy(old, 0, triRef.heap, 0, old.length);
111: }
112: if (ratio == 0.0) {
113: if (triRef.numZero < triRef.numHeap)
114: if (triRef.heap[triRef.numHeap] == null)
115: storeHeapData(triRef, triRef.numHeap,
116: triRef.heap[triRef.numZero].ratio,
117: triRef.heap[triRef.numZero].index,
118: triRef.heap[triRef.numZero].prev,
119: triRef.heap[triRef.numZero].next);
120: else
121: triRef.heap[triRef.numHeap]
122: .copy(triRef.heap[triRef.numZero]);
123: /*
124: storeHeapData(triRef, triRef.numHeap, triRef.heap[triRef.numZero].ratio,
125: triRef.heap[triRef.numZero].index,
126: triRef.heap[triRef.numZero].prev,
127: triRef.heap[triRef.numZero].next);
128: */
129: index = triRef.numZero;
130: ++triRef.numZero;
131: } else {
132: index = triRef.numHeap;
133: }
134:
135: storeHeapData(triRef, index, ratio, ind, prev, next);
136: ++triRef.numHeap;
137:
138: }
139:
140: static void insertIntoHeap(Triangulator triRef, double ratio,
141: int ind, int prev, int next) {
142: dumpOnHeap(triRef, ratio, ind, prev, next);
143: }
144:
145: static boolean deleteFromHeap(Triangulator triRef, int[] ind,
146: int[] prev, int[] next) {
147: double rnd;
148: int rndInd;
149:
150: // earSorted is not implemented yet.
151:
152: if (triRef.numZero > 0) {
153: // assert(num_heap >= num_zero);
154: --triRef.numZero;
155: --triRef.numHeap;
156:
157: ind[0] = triRef.heap[triRef.numZero].index;
158: prev[0] = triRef.heap[triRef.numZero].prev;
159: next[0] = triRef.heap[triRef.numZero].next;
160: if (triRef.numZero < triRef.numHeap)
161: triRef.heap[triRef.numZero]
162: .copy(triRef.heap[triRef.numHeap]);
163: /*
164: storeHeapData( triRef, triRef.numZero, triRef.heap[triRef.numHeap].ratio,
165: triRef.heap[triRef.numHeap].index,
166: triRef.heap[triRef.numHeap].prev,
167: triRef.heap[triRef.numHeap].next);
168: */
169: return true;
170: } else if (triRef.earsRandom) {
171: if (triRef.numHeap <= 0) {
172: triRef.numHeap = 0;
173: return false;
174: }
175: rnd = triRef.randomGen.nextDouble();
176: rndInd = (int) (rnd * triRef.numHeap);
177: --triRef.numHeap;
178: if (rndInd > triRef.numHeap)
179: rndInd = triRef.numHeap;
180:
181: ind[0] = triRef.heap[rndInd].index;
182: prev[0] = triRef.heap[rndInd].prev;
183: next[0] = triRef.heap[rndInd].next;
184: if (rndInd < triRef.numHeap)
185: triRef.heap[rndInd].copy(triRef.heap[triRef.numHeap]);
186: /*
187: storeHeapData( triRef, rndInd, triRef.heap[triRef.numHeap].ratio,
188: triRef.heap[triRef.numHeap].index,
189: triRef.heap[triRef.numHeap].prev,
190: triRef.heap[triRef.numHeap].next);
191: */
192: return true;
193: } else {
194: if (triRef.numHeap <= 0) {
195: triRef.numHeap = 0;
196: return false;
197: }
198: --triRef.numHeap;
199: ind[0] = triRef.heap[triRef.numHeap].index;
200: prev[0] = triRef.heap[triRef.numHeap].prev;
201: next[0] = triRef.heap[triRef.numHeap].next;
202:
203: return true;
204: }
205:
206: // return false;
207: }
208:
209: }
|