001: /*
002: * $RCSfile: NnuIdManager.java,v $
003: *
004: * Copyright 2001-2008 Sun Microsystems, Inc. All Rights Reserved.
005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
006: *
007: * This code is free software; you can redistribute it and/or modify it
008: * under the terms of the GNU General Public License version 2 only, as
009: * published by the Free Software Foundation. Sun designates this
010: * particular file as subject to the "Classpath" exception as provided
011: * by Sun in the LICENSE file that accompanied this code.
012: *
013: * This code is distributed in the hope that it will be useful, but WITHOUT
014: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
015: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
016: * version 2 for more details (a copy is included in the LICENSE file that
017: * accompanied this code).
018: *
019: * You should have received a copy of the GNU General Public License version
020: * 2 along with this work; if not, write to the Free Software Foundation,
021: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
022: *
023: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
024: * CA 95054 USA or visit www.sun.com if you need additional information or
025: * have any questions.
026: *
027: * $Revision: 1.7 $
028: * $Date: 2008/02/28 20:17:26 $
029: * $State: Exp $
030: */
031:
032: package javax.media.j3d;
033:
034: class NnuIdManager {
035: static int nnuId = 0;
036:
037: final static int getId() {
038: if (nnuId == Integer.MAX_VALUE) {
039: nnuId = 0;
040: }
041:
042: return nnuId++;
043: }
044:
045: final static int equals(NnuId nnuIdArr[], NnuId key, int start,
046: int end) {
047: int mid;
048:
049: mid = start + ((end - start) / 2);
050: if (nnuIdArr[mid] != null) {
051: int test = key.equal(nnuIdArr[mid]);
052:
053: if ((test < 0) && (start != mid))
054: return equals(nnuIdArr, key, start, mid);
055: else if ((test > 0) && (start != mid))
056: return equals(nnuIdArr, key, mid, end);
057: else if (test == 0) {
058: // Since id is not necessary unique, we've to do
059: // some extra check.
060:
061: // check for equal reference.
062: if (key == nnuIdArr[mid]) {
063: return mid;
064: }
065:
066: int temp = mid - 1;
067: // Look to the left.
068: while ((temp >= start)
069: && (key.equal(nnuIdArr[temp]) == 0)) {
070: if (key == nnuIdArr[temp]) {
071: return temp;
072: }
073: temp--;
074: }
075:
076: // Look to the right.
077: temp = mid + 1;
078: while ((temp < end) && (key.equal(nnuIdArr[temp]) == 0)) {
079: if (key == nnuIdArr[temp]) {
080: return temp;
081: }
082: temp++;
083: }
084:
085: // Fail equal reference check.
086: return -1;
087: } else
088: return -1;
089: }
090: // A null NnuId object encountered.
091: return -2;
092: }
093:
094: final static boolean equals(NnuId nnuIdArr[], NnuId key,
095: int[] index, int start, int end) {
096:
097: int mid;
098:
099: mid = start + ((end - start) / 2);
100:
101: if (nnuIdArr[mid] != null) {
102: int test = key.equal(nnuIdArr[mid]);
103:
104: if (start != mid) {
105: if (test < 0) {
106: return equals(nnuIdArr, key, index, start, mid);
107: } else if (test > 0) {
108: return equals(nnuIdArr, key, index, mid, end);
109: }
110: } else { // (start == mid)
111: if (test < 0) {
112: index[0] = mid;
113: return false;
114: } else if (test > 0) {
115: index[0] = mid + 1;
116: return false;
117: }
118: }
119:
120: // (test == 0)
121: // Since id is not necessary unique, we've to do
122: // some extra check.
123:
124: // check for equal reference.
125: if (key == nnuIdArr[mid]) {
126: index[0] = mid;
127: return true;
128: }
129:
130: int temp = mid - 1;
131: // Look to the left.
132: while ((temp >= start) && (key.equal(nnuIdArr[temp]) == 0)) {
133: if (key == nnuIdArr[temp]) {
134: index[0] = temp;
135: return true;
136: }
137: temp--;
138: }
139:
140: // Look to the right.
141: temp = mid + 1;
142: while ((temp < end) && (key.equal(nnuIdArr[temp]) == 0)) {
143: if (key == nnuIdArr[temp]) {
144: index[0] = temp;
145: return true;
146: }
147: temp++;
148: }
149:
150: // Fail equal reference check.
151: index[0] = temp;
152: return false;
153:
154: }
155: // A null entry encountered.
156: // But we still want to return the index where we encounter it.
157: index[0] = mid;
158: return false;
159: }
160:
161: final static void sort(NnuId nnuIdArr[]) {
162: if (nnuIdArr.length < 20) {
163: insertSort(nnuIdArr);
164: } else {
165: quicksort(nnuIdArr, 0, nnuIdArr.length - 1);
166: }
167: }
168:
169: // Insertion sort on smaller array
170: final static void insertSort(NnuId nnuIdArr[]) {
171:
172: for (int i = 0; i < nnuIdArr.length; i++) {
173: for (int j = i; j > 0
174: && (nnuIdArr[j - 1].getId() > nnuIdArr[j].getId()); j--) {
175: NnuId temp = nnuIdArr[j];
176: nnuIdArr[j] = nnuIdArr[j - 1];
177: nnuIdArr[j - 1] = temp;
178: }
179: }
180: }
181:
182: final static void quicksort(NnuId nnuIdArr[], int l, int r) {
183: int i = l;
184: int j = r;
185: int k = nnuIdArr[(l + r) / 2].getId();
186:
187: do {
188: while (nnuIdArr[i].getId() < k)
189: i++;
190: while (k < nnuIdArr[j].getId())
191: j--;
192: if (i <= j) {
193: NnuId tmp = nnuIdArr[i];
194: nnuIdArr[i] = nnuIdArr[j];
195: nnuIdArr[j] = tmp;
196:
197: i++;
198: j--;
199: }
200: } while (i <= j);
201:
202: if (l < j)
203: quicksort(nnuIdArr, l, j);
204: if (l < r)
205: quicksort(nnuIdArr, i, r);
206: }
207:
208: // This method assumes that nnuIdArr0 and nnuIdArr1 are sorted.
209: final static NnuId[] delete(NnuId nnuIdArr0[], NnuId nnuIdArr1[]) {
210:
211: int i, index, len;
212: int curStart = 0, newStart = 0;
213: boolean found = false;
214:
215: int size = nnuIdArr0.length - nnuIdArr1.length;
216:
217: if (size > 0) {
218: NnuId newNnuIdArr[] = new NnuId[size];
219:
220: for (i = 0; i < nnuIdArr1.length; i++) {
221: index = equals(nnuIdArr0, nnuIdArr1[i], 0,
222: nnuIdArr0.length);
223:
224: if (index >= 0) {
225: found = true;
226: if (index == curStart) {
227: curStart++;
228: } else {
229: len = index - curStart;
230: System.arraycopy(nnuIdArr0, curStart,
231: newNnuIdArr, newStart, len);
232:
233: curStart = index + 1;
234: newStart = newStart + len;
235: }
236: } else {
237: found = false;
238: MasterControl.getCoreLogger().severe(
239: "Can't Find matching nnuId.");
240: }
241: }
242:
243: if ((found == true) && (curStart < nnuIdArr0.length)) {
244: len = nnuIdArr0.length - curStart;
245: System.arraycopy(nnuIdArr0, curStart, newNnuIdArr,
246: newStart, len);
247: }
248:
249: return newNnuIdArr;
250: } else if (size == 0) {
251: // Remove all.
252: } else {
253: // We are in trouble !!!
254: }
255:
256: return null;
257:
258: }
259:
260: // This method assumes that nnuIdArr0 and nnuIdArr1 are sorted.
261: final static NnuId[] merge(NnuId nnuIdArr0[], NnuId nnuIdArr1[]) {
262:
263: int index[] = new int[1];
264: int indexPlus1, blkSize, i, j;
265:
266: int size = nnuIdArr0.length + nnuIdArr1.length;
267:
268: NnuId newNnuIdArr[] = new NnuId[size];
269:
270: // Copy the nnuIdArr0 data into the newly created newNnuIdArr.
271: System
272: .arraycopy(nnuIdArr0, 0, newNnuIdArr, 0,
273: nnuIdArr0.length);
274:
275: for (i = nnuIdArr0.length, j = 0; i < size; i++, j++) {
276: // True or false, it doesn't matter.
277: equals((NnuId[]) newNnuIdArr, nnuIdArr1[j], index, 0, i);
278:
279: if (index[0] == i) { // Append to last.
280: newNnuIdArr[i] = nnuIdArr1[j];
281: } else { // Insert in between array elements.
282: indexPlus1 = index[0] + 1;
283: blkSize = i - index[0];
284:
285: // Shift the later portion of array elements by one position.
286: // This is the make room for the new data entry.
287: System.arraycopy(newNnuIdArr, index[0], newNnuIdArr,
288: indexPlus1, blkSize);
289:
290: newNnuIdArr[index[0]] = nnuIdArr1[j];
291: }
292:
293: }
294:
295: return newNnuIdArr;
296:
297: }
298:
299: final static void replace(NnuId oldObj, NnuId newObj,
300: NnuId nnuIdArr[]) {
301:
302: int[] index = new int[1];
303: int lenLess1 = nnuIdArr.length - 1;
304: int blkSize;
305:
306: // delete old from nnuIdArr.
307: index[0] = equals(nnuIdArr, oldObj, 0, nnuIdArr.length);
308: if (index[0] == lenLess1) {
309: nnuIdArr[index[0]] = null;
310: } else if (index[0] >= 0) {
311: blkSize = lenLess1 - index[0];
312: System.arraycopy(nnuIdArr, index[0] + 1, nnuIdArr,
313: index[0], blkSize);
314: nnuIdArr[lenLess1] = null;
315: } else {
316: MasterControl.getCoreLogger().severe(
317: "Can't Find matching nnuId.");
318: }
319:
320: // insert new to nnuIdArr.
321: equals(nnuIdArr, newObj, index, 0, lenLess1);
322:
323: if (index[0] == lenLess1) { // Append to last.
324: nnuIdArr[index[0]] = newObj;
325: } else { // Insert in between array elements.
326: blkSize = lenLess1 - index[0];
327:
328: // Shift the later portion of array elements by one position.
329: // This is the make room for the new data entry.
330: System.arraycopy(nnuIdArr, index[0], nnuIdArr,
331: index[0] + 1, blkSize);
332:
333: nnuIdArr[index[0]] = newObj;
334: }
335:
336: }
337:
338: final static void printIds(NnuId nnuIdArr[]) {
339: for (int i = 0; i < nnuIdArr.length; i++) {
340: System.err.println("[" + i + "] is " + nnuIdArr[i].getId());
341: }
342:
343: }
344:
345: }
|