2 * Copyright 2004-2010 Brian S O'Neill
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 package org.cojen.util;
19 import java.util.Arrays;
22 * KeyFactory generates keys which can be hashed or compared for any kind of
23 * object including arrays, arrays of arrays, and null. All hashcode
24 * computations, equality tests, and ordering comparsisons fully recurse into
27 * @author Brian S O'Neill
29 @SuppressWarnings({ "rawtypes", "unused", "unchecked", "serial" })
30 public class KeyFactory {
31 static final Object NULL = new Comparable() {
32 public int compareTo(Object obj) {
33 return obj == this || obj == null ? 0 : 1;
37 public static Object createKey(boolean[] obj) {
38 return obj == null ? NULL : new BooleanArrayKey(obj);
41 public static Object createKey(byte[] obj) {
42 return obj == null ? NULL : new ByteArrayKey(obj);
45 public static Object createKey(char[] obj) {
46 return obj == null ? NULL : new CharArrayKey(obj);
49 public static Object createKey(double[] obj) {
50 return obj == null ? NULL : new DoubleArrayKey(obj);
53 public static Object createKey(float[] obj) {
54 return obj == null ? NULL : new FloatArrayKey(obj);
57 public static Object createKey(int[] obj) {
58 return obj == null ? NULL : new IntArrayKey(obj);
61 public static Object createKey(long[] obj) {
62 return obj == null ? NULL : new LongArrayKey(obj);
65 public static Object createKey(short[] obj) {
66 return obj == null ? NULL : new ShortArrayKey(obj);
69 public static Object createKey(Object[] obj) {
70 return obj == null ? NULL : new ObjectArrayKey(obj);
73 public static Object createKey(Object obj) {
77 if (!obj.getClass().isArray()) {
80 if (obj instanceof Object[]) {
81 return createKey((Object[])obj);
82 } else if (obj instanceof int[]) {
83 return createKey((int[])obj);
84 } else if (obj instanceof float[]) {
85 return createKey((float[])obj);
86 } else if (obj instanceof long[]) {
87 return createKey((long[])obj);
88 } else if (obj instanceof double[]) {
89 return createKey((double[])obj);
90 } else if (obj instanceof byte[]) {
91 return createKey((byte[])obj);
92 } else if (obj instanceof char[]) {
93 return createKey((char[])obj);
94 } else if (obj instanceof boolean[]) {
95 return createKey((boolean[])obj);
96 } else if (obj instanceof short[]) {
97 return createKey((short[])obj);
103 static int hashCode(boolean[] a) {
105 for (int i = a.length; --i >= 0; ) {
106 hash = (hash << 1) + (a[i] ? 0 : 1);
108 return hash == 0 ? -1 : hash;
111 static int hashCode(byte[] a) {
113 for (int i = a.length; --i >= 0; ) {
114 hash = (hash << 1) + a[i];
116 return hash == 0 ? -1 : hash;
119 static int hashCode(char[] a) {
121 for (int i = a.length; --i >= 0; ) {
122 hash = (hash << 1) + a[i];
124 return hash == 0 ? -1 : hash;
127 static int hashCode(double[] a) {
129 for (int i = a.length; --i >= 0; ) {
130 long v = Double.doubleToLongBits(a[i]);
131 hash = hash * 31 + (int)(v ^ v >>> 32);
133 return hash == 0 ? -1 : hash;
136 static int hashCode(float[] a) {
138 for (int i = a.length; --i >= 0; ) {
139 hash = hash * 31 + Float.floatToIntBits(a[i]);
141 return hash == 0 ? -1 : hash;
144 static int hashCode(int[] a) {
146 for (int i = a.length; --i >= 0; ) {
147 hash = (hash << 1) + a[i];
149 return hash == 0 ? -1 : hash;
152 static int hashCode(long[] a) {
154 for (int i = a.length; --i >= 0; ) {
156 hash = hash * 31 + (int)(v ^ v >>> 32);
158 return hash == 0 ? -1 : hash;
161 static int hashCode(short[] a) {
163 for (int i = a.length; --i >= 0; ) {
164 hash = (hash << 1) + a[i];
166 return hash == 0 ? -1 : hash;
169 static int hashCode(Object[] a) {
171 for (int i = a.length; --i >= 0; ) {
172 hash = hash * 31 + hashCode(a[i]);
174 return hash == 0 ? -1 : hash;
177 // Compute object or array hashcode and recurses into arrays within.
178 static int hashCode(Object a) {
182 if (!a.getClass().isArray()) {
185 if (a instanceof Object[]) {
186 return hashCode((Object[])a);
187 } else if (a instanceof int[]) {
188 return hashCode((int[])a);
189 } else if (a instanceof float[]) {
190 return hashCode((float[])a);
191 } else if (a instanceof long[]) {
192 return hashCode((long[])a);
193 } else if (a instanceof double[]) {
194 return hashCode((double[])a);
195 } else if (a instanceof byte[]) {
196 return hashCode((byte[])a);
197 } else if (a instanceof char[]) {
198 return hashCode((char[])a);
199 } else if (a instanceof boolean[]) {
200 return hashCode((boolean[])a);
201 } else if (a instanceof short[]) {
202 return hashCode((short[])a);
204 int hash = a.getClass().hashCode();
205 return hash == 0 ? -1 : hash;
209 // Compares object arrays and recurses into arrays within.
210 static boolean equals(Object[] a, Object[] b) {
214 if (a == null || b == null) {
218 if ((i = a.length) != b.length) {
222 if (!equals(a[i], b[i])) {
229 // Compares objects or arrays and recurses into arrays within.
230 static boolean equals(Object a, Object b) {
234 if (a == null || b == null) {
237 Class ac = a.getClass();
238 if (!(ac.isArray())) {
241 if (ac != b.getClass()) {
244 if (a instanceof Object[]) {
245 return equals((Object[])a, (Object[])b);
246 } else if (a instanceof int[]) {
247 return Arrays.equals((int[])a, (int[])b);
248 } else if (a instanceof float[]) {
249 return Arrays.equals((float[])a, (float[])b);
250 } else if (a instanceof long[]) {
251 return Arrays.equals((long[])a, (long[])b);
252 } else if (a instanceof double[]) {
253 return Arrays.equals((double[])a, (double[])b);
254 } else if (a instanceof byte[]) {
255 return Arrays.equals((byte[])a, (byte[])b);
256 } else if (a instanceof char[]) {
257 return Arrays.equals((char[])a, (char[])b);
258 } else if (a instanceof boolean[]) {
259 return Arrays.equals((boolean[])a, (boolean[])b);
260 } else if (a instanceof short[]) {
261 return Arrays.equals((short[])a, (short[])b);
267 static int compare(boolean[] a, boolean[] b) {
277 int length = Math.min(a.length, b.length);
278 for (int i=0; i<length; i++) {
279 int av = a[i] ? 0 : 1;
280 int bv = b[i] ? 0 : 1;
281 return av < bv ? -1 : (av > bv ? 1 : 0);
283 return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
286 static int compare(byte[] a, byte[] b) {
296 int length = Math.min(a.length, b.length);
297 for (int i=0; i<length; i++) {
300 return av < bv ? -1 : (av > bv ? 1 : 0);
302 return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
305 static int compare(char[] a, char[] b) {
315 int length = Math.min(a.length, b.length);
316 for (int i=0; i<length; i++) {
319 return av < bv ? -1 : (av > bv ? 1 : 0);
321 return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
324 static int compare(double[] a, double[] b) {
334 int length = Math.min(a.length, b.length);
335 for (int i=0; i<length; i++) {
336 int v = Double.compare(a[i], b[i]);
341 return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
344 static int compare(float[] a, float[] b) {
354 int length = Math.min(a.length, b.length);
355 for (int i=0; i<length; i++) {
356 int v = Float.compare(a[i], b[i]);
361 return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
364 static int compare(int[] a, int[] b) {
374 int length = Math.min(a.length, b.length);
375 for (int i=0; i<length; i++) {
378 return av < bv ? -1 : (av > bv ? 1 : 0);
380 return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
383 static int compare(long[] a, long[] b) {
393 int length = Math.min(a.length, b.length);
394 for (int i=0; i<length; i++) {
397 return av < bv ? -1 : (av > bv ? 1 : 0);
399 return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
402 static int compare(short[] a, short[] b) {
412 int length = Math.min(a.length, b.length);
413 for (int i=0; i<length; i++) {
416 return av < bv ? -1 : (av > bv ? 1 : 0);
418 return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
421 // Compares object arrays and recurses into arrays within.
422 static int compare(Object[] a, Object[] b) {
432 int length = Math.min(a.length, b.length);
433 for (int i=0; i<length; i++) {
434 int v = compare(a[i], b[i]);
439 return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
442 // Compares objects or arrays and recurses into arrays within.
443 static int compare(Object a, Object b) {
453 Class ac = a.getClass();
454 if (!(ac.isArray())) {
455 return ((Comparable)a).compareTo(b);
457 if (ac != b.getClass()) {
458 throw new ClassCastException();
460 if (a instanceof Object[]) {
461 return compare((Object[])a, (Object[])b);
462 } else if (a instanceof int[]) {
463 return compare((int[])a, (int[])b);
464 } else if (a instanceof float[]) {
465 return compare((float[])a, (float[])b);
466 } else if (a instanceof long[]) {
467 return compare((long[])a, (long[])b);
468 } else if (a instanceof double[]) {
469 return compare((double[])a, (double[])b);
470 } else if (a instanceof byte[]) {
471 return compare((byte[])a, (byte[])b);
472 } else if (a instanceof char[]) {
473 return compare((char[])a, (char[])b);
474 } else if (a instanceof boolean[]) {
475 return compare((boolean[])a, (boolean[])b);
476 } else if (a instanceof short[]) {
477 return compare((short[])a, (short[])b);
479 throw new ClassCastException();
483 protected KeyFactory() {
486 private static interface ArrayKey extends Comparable, java.io.Serializable {
489 boolean equals(Object obj);
491 int compareTo(Object obj);
494 private static class BooleanArrayKey implements ArrayKey {
495 protected final boolean[] mArray;
496 private transient int mHash;
498 BooleanArrayKey(boolean[] array) {
502 public int hashCode() {
504 return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
507 public boolean equals(Object obj) {
508 return this == obj ? true :
509 (obj instanceof BooleanArrayKey ?
510 Arrays.equals(mArray, ((BooleanArrayKey) obj).mArray) : false);
513 public int compareTo(Object obj) {
514 return compare(mArray, ((BooleanArrayKey) obj).mArray);
518 private static class ByteArrayKey implements ArrayKey {
519 protected final byte[] mArray;
520 private transient int mHash;
522 ByteArrayKey(byte[] array) {
526 public int hashCode() {
528 return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
531 public boolean equals(Object obj) {
532 return this == obj ? true :
533 (obj instanceof ByteArrayKey ?
534 Arrays.equals(mArray, ((ByteArrayKey) obj).mArray) : false);
537 public int compareTo(Object obj) {
538 return compare(mArray, ((ByteArrayKey) obj).mArray);
542 private static class CharArrayKey implements ArrayKey {
543 protected final char[] mArray;
544 private transient int mHash;
546 CharArrayKey(char[] array) {
550 public int hashCode() {
552 return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
555 public boolean equals(Object obj) {
556 return this == obj ? true :
557 (obj instanceof CharArrayKey ?
558 Arrays.equals(mArray, ((CharArrayKey) obj).mArray) : false);
561 public int compareTo(Object obj) {
562 return compare(mArray, ((CharArrayKey) obj).mArray);
566 private static class DoubleArrayKey implements ArrayKey {
567 protected final double[] mArray;
568 private transient int mHash;
570 DoubleArrayKey(double[] array) {
574 public int hashCode() {
576 return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
579 public boolean equals(Object obj) {
580 return this == obj ? true :
581 (obj instanceof DoubleArrayKey ?
582 Arrays.equals(mArray, ((DoubleArrayKey) obj).mArray) : false);
585 public int compareTo(Object obj) {
586 return compare(mArray, ((DoubleArrayKey) obj).mArray);
590 private static class FloatArrayKey implements ArrayKey {
591 protected final float[] mArray;
592 private transient int mHash;
594 FloatArrayKey(float[] array) {
598 public int hashCode() {
600 return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
603 public boolean equals(Object obj) {
604 return this == obj ? true :
605 (obj instanceof FloatArrayKey ?
606 Arrays.equals(mArray, ((FloatArrayKey) obj).mArray) : false);
609 public int compareTo(Object obj) {
610 return compare(mArray, ((FloatArrayKey) obj).mArray);
614 private static class IntArrayKey implements ArrayKey {
615 protected final int[] mArray;
616 private transient int mHash;
618 IntArrayKey(int[] array) {
622 public int hashCode() {
624 return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
627 public boolean equals(Object obj) {
628 return this == obj ? true :
629 (obj instanceof IntArrayKey ?
630 Arrays.equals(mArray, ((IntArrayKey) obj).mArray) : false);
633 public int compareTo(Object obj) {
634 return compare(mArray, ((IntArrayKey) obj).mArray);
638 private static class LongArrayKey implements ArrayKey {
639 protected final long[] mArray;
640 private transient int mHash;
642 LongArrayKey(long[] array) {
646 public int hashCode() {
648 return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
651 public boolean equals(Object obj) {
652 return this == obj ? true :
653 (obj instanceof LongArrayKey ?
654 Arrays.equals(mArray, ((LongArrayKey) obj).mArray) : false);
657 public int compareTo(Object obj) {
658 return compare(mArray, ((LongArrayKey) obj).mArray);
662 private static class ShortArrayKey implements ArrayKey {
663 protected final short[] mArray;
664 private transient int mHash;
666 ShortArrayKey(short[] array) {
670 public int hashCode() {
672 return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
675 public boolean equals(Object obj) {
676 return this == obj ? true :
677 (obj instanceof ShortArrayKey ?
678 Arrays.equals(mArray, ((ShortArrayKey) obj).mArray) : false);
681 public int compareTo(Object obj) {
682 return compare(mArray, ((ShortArrayKey) obj).mArray);
686 private static class ObjectArrayKey implements ArrayKey {
687 protected final Object[] mArray;
688 private transient int mHash;
690 ObjectArrayKey(Object[] array) {
694 public int hashCode() {
696 return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
699 public boolean equals(Object obj) {
700 return this == obj ? true :
701 (obj instanceof ObjectArrayKey ?
702 KeyFactory.equals(mArray, ((ObjectArrayKey) obj).mArray) : false);
705 public int compareTo(Object obj) {
706 return compare(mArray, ((ObjectArrayKey) obj).mArray);