001: /*
002: * Copyright 2004 Brian S O'Neill
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016:
017: package org.cojen.util;
018:
019: import java.util.Arrays;
020:
021: /**
022: * KeyFactory generates keys which can be hashed or compared for any kind of
023: * object including arrays, arrays of arrays, and null. All hashcode
024: * computations, equality tests, and ordering comparsisons fully recurse into
025: * arrays.
026: *
027: * @author Brian S O'Neill
028: */
029: public class KeyFactory {
030: static final Object NULL = new Comparable() {
031: public int compareTo(Object obj) {
032: return obj == this || obj == null ? 0 : 1;
033: }
034: };
035:
036: public static Object createKey(boolean[] obj) {
037: return obj == null ? NULL : new BooleanArrayKey(obj);
038: }
039:
040: public static Object createKey(byte[] obj) {
041: return obj == null ? NULL : new ByteArrayKey(obj);
042: }
043:
044: public static Object createKey(char[] obj) {
045: return obj == null ? NULL : new CharArrayKey(obj);
046: }
047:
048: public static Object createKey(double[] obj) {
049: return obj == null ? NULL : new DoubleArrayKey(obj);
050: }
051:
052: public static Object createKey(float[] obj) {
053: return obj == null ? NULL : new FloatArrayKey(obj);
054: }
055:
056: public static Object createKey(int[] obj) {
057: return obj == null ? NULL : new IntArrayKey(obj);
058: }
059:
060: public static Object createKey(long[] obj) {
061: return obj == null ? NULL : new LongArrayKey(obj);
062: }
063:
064: public static Object createKey(short[] obj) {
065: return obj == null ? NULL : new ShortArrayKey(obj);
066: }
067:
068: public static Object createKey(Object[] obj) {
069: return obj == null ? NULL : new ObjectArrayKey(obj);
070: }
071:
072: public static Object createKey(Object obj) {
073: if (obj == null) {
074: return NULL;
075: }
076: if (!obj.getClass().isArray()) {
077: return obj;
078: }
079: if (obj instanceof Object[]) {
080: return createKey((Object[]) obj);
081: } else if (obj instanceof int[]) {
082: return createKey((int[]) obj);
083: } else if (obj instanceof float[]) {
084: return createKey((float[]) obj);
085: } else if (obj instanceof long[]) {
086: return createKey((long[]) obj);
087: } else if (obj instanceof double[]) {
088: return createKey((double[]) obj);
089: } else if (obj instanceof byte[]) {
090: return createKey((byte[]) obj);
091: } else if (obj instanceof char[]) {
092: return createKey((char[]) obj);
093: } else if (obj instanceof boolean[]) {
094: return createKey((boolean[]) obj);
095: } else if (obj instanceof short[]) {
096: return createKey((short[]) obj);
097: } else {
098: return obj;
099: }
100: }
101:
102: static int hashCode(boolean[] a) {
103: int hash = 0;
104: for (int i = a.length; --i >= 0;) {
105: hash = (hash << 1) + (a[i] ? 0 : 1);
106: }
107: return hash == 0 ? -1 : hash;
108: }
109:
110: static int hashCode(byte[] a) {
111: int hash = 0;
112: for (int i = a.length; --i >= 0;) {
113: hash = (hash << 1) + a[i];
114: }
115: return hash == 0 ? -1 : hash;
116: }
117:
118: static int hashCode(char[] a) {
119: int hash = 0;
120: for (int i = a.length; --i >= 0;) {
121: hash = (hash << 1) + a[i];
122: }
123: return hash == 0 ? -1 : hash;
124: }
125:
126: static int hashCode(double[] a) {
127: int hash = 0;
128: for (int i = a.length; --i >= 0;) {
129: long v = Double.doubleToLongBits(a[i]);
130: hash = hash * 31 + (int) (v ^ v >>> 32);
131: }
132: return hash == 0 ? -1 : hash;
133: }
134:
135: static int hashCode(float[] a) {
136: int hash = 0;
137: for (int i = a.length; --i >= 0;) {
138: hash = hash * 31 + Float.floatToIntBits(a[i]);
139: }
140: return hash == 0 ? -1 : hash;
141: }
142:
143: static int hashCode(int[] a) {
144: int hash = 0;
145: for (int i = a.length; --i >= 0;) {
146: hash = (hash << 1) + a[i];
147: }
148: return hash == 0 ? -1 : hash;
149: }
150:
151: static int hashCode(long[] a) {
152: int hash = 0;
153: for (int i = a.length; --i >= 0;) {
154: long v = a[i];
155: hash = hash * 31 + (int) (v ^ v >>> 32);
156: }
157: return hash == 0 ? -1 : hash;
158: }
159:
160: static int hashCode(short[] a) {
161: int hash = 0;
162: for (int i = a.length; --i >= 0;) {
163: hash = (hash << 1) + a[i];
164: }
165: return hash == 0 ? -1 : hash;
166: }
167:
168: static int hashCode(Object[] a) {
169: int hash = 0;
170: for (int i = a.length; --i >= 0;) {
171: hash = hash * 31 + hashCode(a[i]);
172: }
173: return hash == 0 ? -1 : hash;
174: }
175:
176: // Compute object or array hashcode and recurses into arrays within.
177: static int hashCode(Object a) {
178: if (a == null) {
179: return -1;
180: }
181: if (!a.getClass().isArray()) {
182: return a.hashCode();
183: }
184: if (a instanceof Object[]) {
185: return hashCode((Object[]) a);
186: } else if (a instanceof int[]) {
187: return hashCode((int[]) a);
188: } else if (a instanceof float[]) {
189: return hashCode((float[]) a);
190: } else if (a instanceof long[]) {
191: return hashCode((long[]) a);
192: } else if (a instanceof double[]) {
193: return hashCode((double[]) a);
194: } else if (a instanceof byte[]) {
195: return hashCode((byte[]) a);
196: } else if (a instanceof char[]) {
197: return hashCode((char[]) a);
198: } else if (a instanceof boolean[]) {
199: return hashCode((boolean[]) a);
200: } else if (a instanceof short[]) {
201: return hashCode((short[]) a);
202: } else {
203: int hash = a.getClass().hashCode();
204: return hash == 0 ? -1 : hash;
205: }
206: }
207:
208: // Compares object arrays and recurses into arrays within.
209: static boolean equals(Object[] a, Object[] b) {
210: if (a == b) {
211: return true;
212: }
213: if (a == null || b == null) {
214: return false;
215: }
216: int i;
217: if ((i = a.length) != b.length) {
218: return false;
219: }
220: while (--i >= 0) {
221: if (!equals(a[i], b[i])) {
222: return false;
223: }
224: }
225: return true;
226: }
227:
228: // Compares objects or arrays and recurses into arrays within.
229: static boolean equals(Object a, Object b) {
230: if (a == b) {
231: return true;
232: }
233: if (a == null || b == null) {
234: return false;
235: }
236: Class ac = a.getClass();
237: if (!(ac.isArray())) {
238: return a.equals(b);
239: }
240: if (ac != b.getClass()) {
241: return false;
242: }
243: if (a instanceof Object[]) {
244: return equals((Object[]) a, (Object[]) b);
245: } else if (a instanceof int[]) {
246: return Arrays.equals((int[]) a, (int[]) b);
247: } else if (a instanceof float[]) {
248: return Arrays.equals((float[]) a, (float[]) b);
249: } else if (a instanceof long[]) {
250: return Arrays.equals((long[]) a, (long[]) b);
251: } else if (a instanceof double[]) {
252: return Arrays.equals((double[]) a, (double[]) b);
253: } else if (a instanceof byte[]) {
254: return Arrays.equals((byte[]) a, (byte[]) b);
255: } else if (a instanceof char[]) {
256: return Arrays.equals((char[]) a, (char[]) b);
257: } else if (a instanceof boolean[]) {
258: return Arrays.equals((boolean[]) a, (boolean[]) b);
259: } else if (a instanceof short[]) {
260: return Arrays.equals((short[]) a, (short[]) b);
261: } else {
262: return a.equals(b);
263: }
264: }
265:
266: static int compare(boolean[] a, boolean[] b) {
267: if (a == b) {
268: return 0;
269: }
270: if (a == null) {
271: return 1;
272: }
273: if (b == null) {
274: return -1;
275: }
276: int length = Math.min(a.length, b.length);
277: for (int i = 0; i < length; i++) {
278: int av = a[i] ? 0 : 1;
279: int bv = b[i] ? 0 : 1;
280: return av < bv ? -1 : (av > bv ? 1 : 0);
281: }
282: return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
283: }
284:
285: static int compare(byte[] a, byte[] b) {
286: if (a == b) {
287: return 0;
288: }
289: if (a == null) {
290: return 1;
291: }
292: if (b == null) {
293: return -1;
294: }
295: int length = Math.min(a.length, b.length);
296: for (int i = 0; i < length; i++) {
297: byte av = a[i];
298: byte bv = b[i];
299: return av < bv ? -1 : (av > bv ? 1 : 0);
300: }
301: return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
302: }
303:
304: static int compare(char[] a, char[] b) {
305: if (a == b) {
306: return 0;
307: }
308: if (a == null) {
309: return 1;
310: }
311: if (b == null) {
312: return -1;
313: }
314: int length = Math.min(a.length, b.length);
315: for (int i = 0; i < length; i++) {
316: char av = a[i];
317: char bv = b[i];
318: return av < bv ? -1 : (av > bv ? 1 : 0);
319: }
320: return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
321: }
322:
323: static int compare(double[] a, double[] b) {
324: if (a == b) {
325: return 0;
326: }
327: if (a == null) {
328: return 1;
329: }
330: if (b == null) {
331: return -1;
332: }
333: int length = Math.min(a.length, b.length);
334: for (int i = 0; i < length; i++) {
335: int v = Double.compare(a[i], b[i]);
336: if (v != 0) {
337: return v;
338: }
339: }
340: return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
341: }
342:
343: static int compare(float[] a, float[] b) {
344: if (a == b) {
345: return 0;
346: }
347: if (a == null) {
348: return 1;
349: }
350: if (b == null) {
351: return -1;
352: }
353: int length = Math.min(a.length, b.length);
354: for (int i = 0; i < length; i++) {
355: int v = Float.compare(a[i], b[i]);
356: if (v != 0) {
357: return v;
358: }
359: }
360: return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
361: }
362:
363: static int compare(int[] a, int[] b) {
364: if (a == b) {
365: return 0;
366: }
367: if (a == null) {
368: return 1;
369: }
370: if (b == null) {
371: return -1;
372: }
373: int length = Math.min(a.length, b.length);
374: for (int i = 0; i < length; i++) {
375: int av = a[i];
376: int bv = b[i];
377: return av < bv ? -1 : (av > bv ? 1 : 0);
378: }
379: return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
380: }
381:
382: static int compare(long[] a, long[] b) {
383: if (a == b) {
384: return 0;
385: }
386: if (a == null) {
387: return 1;
388: }
389: if (b == null) {
390: return -1;
391: }
392: int length = Math.min(a.length, b.length);
393: for (int i = 0; i < length; i++) {
394: long av = a[i];
395: long bv = b[i];
396: return av < bv ? -1 : (av > bv ? 1 : 0);
397: }
398: return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
399: }
400:
401: static int compare(short[] a, short[] b) {
402: if (a == b) {
403: return 0;
404: }
405: if (a == null) {
406: return 1;
407: }
408: if (b == null) {
409: return -1;
410: }
411: int length = Math.min(a.length, b.length);
412: for (int i = 0; i < length; i++) {
413: short av = a[i];
414: short bv = b[i];
415: return av < bv ? -1 : (av > bv ? 1 : 0);
416: }
417: return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
418: }
419:
420: // Compares object arrays and recurses into arrays within.
421: static int compare(Object[] a, Object[] b) {
422: if (a == b) {
423: return 0;
424: }
425: if (a == null) {
426: return 1;
427: }
428: if (b == null) {
429: return -1;
430: }
431: int length = Math.min(a.length, b.length);
432: for (int i = 0; i < length; i++) {
433: int v = compare(a[i], b[i]);
434: if (v != 0) {
435: return v;
436: }
437: }
438: return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
439: }
440:
441: // Compares objects or arrays and recurses into arrays within.
442: static int compare(Object a, Object b) {
443: if (a == b) {
444: return 0;
445: }
446: if (a == null) {
447: return 1;
448: }
449: if (b == null) {
450: return -1;
451: }
452: Class ac = a.getClass();
453: if (!(ac.isArray())) {
454: return ((Comparable) a).compareTo(b);
455: }
456: if (ac != b.getClass()) {
457: throw new ClassCastException();
458: }
459: if (a instanceof Object[]) {
460: return compare((Object[]) a, (Object[]) b);
461: } else if (a instanceof int[]) {
462: return compare((int[]) a, (int[]) b);
463: } else if (a instanceof float[]) {
464: return compare((float[]) a, (float[]) b);
465: } else if (a instanceof long[]) {
466: return compare((long[]) a, (long[]) b);
467: } else if (a instanceof double[]) {
468: return compare((double[]) a, (double[]) b);
469: } else if (a instanceof byte[]) {
470: return compare((byte[]) a, (byte[]) b);
471: } else if (a instanceof char[]) {
472: return compare((char[]) a, (char[]) b);
473: } else if (a instanceof boolean[]) {
474: return compare((boolean[]) a, (boolean[]) b);
475: } else if (a instanceof short[]) {
476: return compare((short[]) a, (short[]) b);
477: } else {
478: throw new ClassCastException();
479: }
480: }
481:
482: protected KeyFactory() {
483: }
484:
485: private static interface ArrayKey extends Comparable,
486: java.io.Serializable {
487: int hashCode();
488:
489: boolean equals(Object obj);
490:
491: int compareTo(Object obj);
492: }
493:
494: private static class BooleanArrayKey implements ArrayKey {
495: protected final boolean[] mArray;
496: private transient int mHash;
497:
498: BooleanArrayKey(boolean[] array) {
499: mArray = array;
500: }
501:
502: public int hashCode() {
503: int hash = mHash;
504: return hash == 0 ? mHash = KeyFactory.hashCode(mArray)
505: : hash;
506: }
507:
508: public boolean equals(Object obj) {
509: return this == obj ? true
510: : (obj instanceof BooleanArrayKey ? Arrays.equals(
511: mArray, ((BooleanArrayKey) obj).mArray)
512: : false);
513: }
514:
515: public int compareTo(Object obj) {
516: return compare(mArray, ((BooleanArrayKey) obj).mArray);
517: }
518: }
519:
520: private static class ByteArrayKey implements ArrayKey {
521: protected final byte[] mArray;
522: private transient int mHash;
523:
524: ByteArrayKey(byte[] array) {
525: mArray = array;
526: }
527:
528: public int hashCode() {
529: int hash = mHash;
530: return hash == 0 ? mHash = KeyFactory.hashCode(mArray)
531: : hash;
532: }
533:
534: public boolean equals(Object obj) {
535: return this == obj ? true
536: : (obj instanceof ByteArrayKey ? Arrays.equals(
537: mArray, ((ByteArrayKey) obj).mArray)
538: : false);
539: }
540:
541: public int compareTo(Object obj) {
542: return compare(mArray, ((ByteArrayKey) obj).mArray);
543: }
544: }
545:
546: private static class CharArrayKey implements ArrayKey {
547: protected final char[] mArray;
548: private transient int mHash;
549:
550: CharArrayKey(char[] array) {
551: mArray = array;
552: }
553:
554: public int hashCode() {
555: int hash = mHash;
556: return hash == 0 ? mHash = KeyFactory.hashCode(mArray)
557: : hash;
558: }
559:
560: public boolean equals(Object obj) {
561: return this == obj ? true
562: : (obj instanceof CharArrayKey ? Arrays.equals(
563: mArray, ((CharArrayKey) obj).mArray)
564: : false);
565: }
566:
567: public int compareTo(Object obj) {
568: return compare(mArray, ((CharArrayKey) obj).mArray);
569: }
570: }
571:
572: private static class DoubleArrayKey implements ArrayKey {
573: protected final double[] mArray;
574: private transient int mHash;
575:
576: DoubleArrayKey(double[] array) {
577: mArray = array;
578: }
579:
580: public int hashCode() {
581: int hash = mHash;
582: return hash == 0 ? mHash = KeyFactory.hashCode(mArray)
583: : hash;
584: }
585:
586: public boolean equals(Object obj) {
587: return this == obj ? true
588: : (obj instanceof DoubleArrayKey ? Arrays.equals(
589: mArray, ((DoubleArrayKey) obj).mArray)
590: : false);
591: }
592:
593: public int compareTo(Object obj) {
594: return compare(mArray, ((DoubleArrayKey) obj).mArray);
595: }
596: }
597:
598: private static class FloatArrayKey implements ArrayKey {
599: protected final float[] mArray;
600: private transient int mHash;
601:
602: FloatArrayKey(float[] array) {
603: mArray = array;
604: }
605:
606: public int hashCode() {
607: int hash = mHash;
608: return hash == 0 ? mHash = KeyFactory.hashCode(mArray)
609: : hash;
610: }
611:
612: public boolean equals(Object obj) {
613: return this == obj ? true
614: : (obj instanceof FloatArrayKey ? Arrays.equals(
615: mArray, ((FloatArrayKey) obj).mArray)
616: : false);
617: }
618:
619: public int compareTo(Object obj) {
620: return compare(mArray, ((FloatArrayKey) obj).mArray);
621: }
622: }
623:
624: private static class IntArrayKey implements ArrayKey {
625: protected final int[] mArray;
626: private transient int mHash;
627:
628: IntArrayKey(int[] array) {
629: mArray = array;
630: }
631:
632: public int hashCode() {
633: int hash = mHash;
634: return hash == 0 ? mHash = KeyFactory.hashCode(mArray)
635: : hash;
636: }
637:
638: public boolean equals(Object obj) {
639: return this == obj ? true
640: : (obj instanceof IntArrayKey ? Arrays.equals(
641: mArray, ((IntArrayKey) obj).mArray) : false);
642: }
643:
644: public int compareTo(Object obj) {
645: return compare(mArray, ((IntArrayKey) obj).mArray);
646: }
647: }
648:
649: private static class LongArrayKey implements ArrayKey {
650: protected final long[] mArray;
651: private transient int mHash;
652:
653: LongArrayKey(long[] array) {
654: mArray = array;
655: }
656:
657: public int hashCode() {
658: int hash = mHash;
659: return hash == 0 ? mHash = KeyFactory.hashCode(mArray)
660: : hash;
661: }
662:
663: public boolean equals(Object obj) {
664: return this == obj ? true
665: : (obj instanceof LongArrayKey ? Arrays.equals(
666: mArray, ((LongArrayKey) obj).mArray)
667: : false);
668: }
669:
670: public int compareTo(Object obj) {
671: return compare(mArray, ((LongArrayKey) obj).mArray);
672: }
673: }
674:
675: private static class ShortArrayKey implements ArrayKey {
676: protected final short[] mArray;
677: private transient int mHash;
678:
679: ShortArrayKey(short[] array) {
680: mArray = array;
681: }
682:
683: public int hashCode() {
684: int hash = mHash;
685: return hash == 0 ? mHash = KeyFactory.hashCode(mArray)
686: : hash;
687: }
688:
689: public boolean equals(Object obj) {
690: return this == obj ? true
691: : (obj instanceof ShortArrayKey ? Arrays.equals(
692: mArray, ((ShortArrayKey) obj).mArray)
693: : false);
694: }
695:
696: public int compareTo(Object obj) {
697: return compare(mArray, ((ShortArrayKey) obj).mArray);
698: }
699: }
700:
701: private static class ObjectArrayKey implements ArrayKey {
702: protected final Object[] mArray;
703: private transient int mHash;
704:
705: ObjectArrayKey(Object[] array) {
706: mArray = array;
707: }
708:
709: public int hashCode() {
710: int hash = mHash;
711: return hash == 0 ? mHash = KeyFactory.hashCode(mArray)
712: : hash;
713: }
714:
715: public boolean equals(Object obj) {
716: return this == obj ? true
717: : (obj instanceof ObjectArrayKey ? KeyFactory
718: .equals(mArray,
719: ((ObjectArrayKey) obj).mArray)
720: : false);
721: }
722:
723: public int compareTo(Object obj) {
724: return compare(mArray, ((ObjectArrayKey) obj).mArray);
725: }
726: }
727: }
|