bundles/org.simantics.scl.compiler/src/org/cojen/util/KeyFactory.java

   1 /*
   2  *  Copyright 2004-2010 Brian S O'Neill
   3  *
   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
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  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.
  15  */
  16
  17 package org.cojen.util;
  18
  19 import java.util.Arrays;
  20
  21 /**
  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
  25  * arrays.
  26  *
  27  * @author Brian S O'Neill
  28  */
  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;
  34         }
  35     };
  36
  37     public static Object createKey(boolean[] obj) {
  38         return obj == null ? NULL : new BooleanArrayKey(obj);
  39     }
  40
  41     public static Object createKey(byte[] obj) {
  42         return obj == null ? NULL : new ByteArrayKey(obj);
  43     }
  44
  45     public static Object createKey(char[] obj) {
  46         return obj == null ? NULL : new CharArrayKey(obj);
  47     }
  48
  49     public static Object createKey(double[] obj) {
  50         return obj == null ? NULL : new DoubleArrayKey(obj);
  51     }
  52
  53     public static Object createKey(float[] obj) {
  54         return obj == null ? NULL : new FloatArrayKey(obj);
  55     }
  56
  57     public static Object createKey(int[] obj) {
  58         return obj == null ? NULL : new IntArrayKey(obj);
  59     }
  60
  61     public static Object createKey(long[] obj) {
  62         return obj == null ? NULL : new LongArrayKey(obj);
  63     }
  64
  65     public static Object createKey(short[] obj) {
  66         return obj == null ? NULL : new ShortArrayKey(obj);
  67     }
  68
  69     public static Object createKey(Object[] obj) {
  70         return obj == null ? NULL : new ObjectArrayKey(obj);
  71     }
  72
  73     public static Object createKey(Object obj) {
  74         if (obj == null) {
  75             return NULL;
  76         }
  77         if (!obj.getClass().isArray()) {
  78             return obj;
  79         }
  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);
  98         } else {
  99             return obj;
 100         }
 101     }
 102
 103     static int hashCode(boolean[] a) {
 104         int hash = 0;
 105         for (int i = a.length; --i >= 0; ) {
 106             hash = (hash << 1) + (a[i] ? 0 : 1);
 107         }
 108         return hash == 0 ? -1 : hash;
 109     }
 110
 111     static int hashCode(byte[] a) {
 112         int hash = 0;
 113         for (int i = a.length; --i >= 0; ) {
 114             hash = (hash << 1) + a[i];
 115         }
 116         return hash == 0 ? -1 : hash;
 117     }
 118
 119     static int hashCode(char[] a) {
 120         int hash = 0;
 121         for (int i = a.length; --i >= 0; ) {
 122             hash = (hash << 1) + a[i];
 123         }
 124         return hash == 0 ? -1 : hash;
 125     }
 126
 127     static int hashCode(double[] a) {
 128         int hash = 0;
 129         for (int i = a.length; --i >= 0; ) {
 130             long v = Double.doubleToLongBits(a[i]);
 131             hash = hash * 31 + (int)(v ^ v >>> 32);
 132         }
 133         return hash == 0 ? -1 : hash;
 134     }
 135
 136     static int hashCode(float[] a) {
 137         int hash = 0;
 138         for (int i = a.length; --i >= 0; ) {
 139             hash = hash * 31 + Float.floatToIntBits(a[i]);
 140         }
 141         return hash == 0 ? -1 : hash;
 142     }
 143
 144     static int hashCode(int[] a) {
 145         int hash = 0;
 146         for (int i = a.length; --i >= 0; ) {
 147             hash = (hash << 1) + a[i];
 148         }
 149         return hash == 0 ? -1 : hash;
 150     }
 151
 152     static int hashCode(long[] a) {
 153         int hash = 0;
 154         for (int i = a.length; --i >= 0; ) {
 155             long v = a[i];
 156             hash = hash * 31 + (int)(v ^ v >>> 32);
 157         }
 158         return hash == 0 ? -1 : hash;
 159     }
 160
 161     static int hashCode(short[] a) {
 162         int hash = 0;
 163         for (int i = a.length; --i >= 0; ) {
 164             hash = (hash << 1) + a[i];
 165         }
 166         return hash == 0 ? -1 : hash;
 167     }
 168
 169     static int hashCode(Object[] a) {
 170         int hash = 0;
 171         for (int i = a.length; --i >= 0; ) {
 172             hash = hash * 31 + hashCode(a[i]);
 173         }
 174         return hash == 0 ? -1 : hash;
 175     }
 176
 177     // Compute object or array hashcode and recurses into arrays within.
 178     static int hashCode(Object a) {
 179         if (a == null) {
 180             return -1;
 181         }
 182         if (!a.getClass().isArray()) {
 183             return a.hashCode();
 184         }
 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);
 203         } else {
 204             int hash = a.getClass().hashCode();
 205             return hash == 0 ? -1 : hash;
 206         }
 207     }
 208
 209     // Compares object arrays and recurses into arrays within.
 210     static boolean equals(Object[] a, Object[] b) {
 211         if (a == b) {
 212             return true;
 213         }
 214         if (a == null || b == null) {
 215             return false;
 216         }
 217         int i;
 218         if ((i = a.length) != b.length) {
 219             return false;
 220         }
 221         while (--i >= 0) {
 222             if (!equals(a[i], b[i])) {
 223                 return false;
 224             }
 225         }
 226         return true;
 227     }
 228
 229     // Compares objects or arrays and recurses into arrays within.
 230     static boolean equals(Object a, Object b) {
 231         if (a == b) {
 232             return true;
 233         }
 234         if (a == null || b == null) {
 235             return false;
 236         }
 237         Class ac = a.getClass();
 238         if (!(ac.isArray())) {
 239             return a.equals(b);
 240         }
 241         if (ac != b.getClass()) {
 242             return false;
 243         }
 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);
 262         } else {
 263             return a.equals(b);
 264         }
 265     }
 266
 267     static int compare(boolean[] a, boolean[] b) {
 268         if (a == b) {
 269             return 0;
 270         }
 271         if (a == null) {
 272             return 1;
 273         }
 274         if (b == null) {
 275             return -1;
 276         }
 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);
 282         }
 283         return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
 284     }
 285
 286     static int compare(byte[] a, byte[] b) {
 287         if (a == b) {
 288             return 0;
 289         }
 290         if (a == null) {
 291             return 1;
 292         }
 293         if (b == null) {
 294             return -1;
 295         }
 296         int length = Math.min(a.length, b.length);
 297         for (int i=0; i<length; i++) {
 298             byte av = a[i];
 299             byte bv = b[i];
 300             return av < bv ? -1 : (av > bv ? 1 : 0);
 301         }
 302         return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
 303     }
 304
 305     static int compare(char[] a, char[] b) {
 306         if (a == b) {
 307             return 0;
 308         }
 309         if (a == null) {
 310             return 1;
 311         }
 312         if (b == null) {
 313             return -1;
 314         }
 315         int length = Math.min(a.length, b.length);
 316         for (int i=0; i<length; i++) {
 317             char av = a[i];
 318             char bv = b[i];
 319             return av < bv ? -1 : (av > bv ? 1 : 0);
 320         }
 321         return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
 322     }
 323
 324     static int compare(double[] a, double[] b) {
 325         if (a == b) {
 326             return 0;
 327         }
 328         if (a == null) {
 329             return 1;
 330         }
 331         if (b == null) {
 332             return -1;
 333         }
 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]);
 337             if (v != 0) {
 338                 return v;
 339             }
 340         }
 341         return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
 342     }
 343
 344     static int compare(float[] a, float[] b) {
 345         if (a == b) {
 346             return 0;
 347         }
 348         if (a == null) {
 349             return 1;
 350         }
 351         if (b == null) {
 352             return -1;
 353         }
 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]);
 357             if (v != 0) {
 358                 return v;
 359             }
 360         }
 361         return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
 362     }
 363
 364     static int compare(int[] a, int[] b) {
 365         if (a == b) {
 366             return 0;
 367         }
 368         if (a == null) {
 369             return 1;
 370         }
 371         if (b == null) {
 372             return -1;
 373         }
 374         int length = Math.min(a.length, b.length);
 375         for (int i=0; i<length; i++) {
 376             int av = a[i];
 377             int bv = b[i];
 378             return av < bv ? -1 : (av > bv ? 1 : 0);
 379         }
 380         return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
 381     }
 382
 383     static int compare(long[] a, long[] b) {
 384         if (a == b) {
 385             return 0;
 386         }
 387         if (a == null) {
 388             return 1;
 389         }
 390         if (b == null) {
 391             return -1;
 392         }
 393         int length = Math.min(a.length, b.length);
 394         for (int i=0; i<length; i++) {
 395             long av = a[i];
 396             long bv = b[i];
 397             return av < bv ? -1 : (av > bv ? 1 : 0);
 398         }
 399         return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
 400     }
 401
 402     static int compare(short[] a, short[] b) {
 403         if (a == b) {
 404             return 0;
 405         }
 406         if (a == null) {
 407             return 1;
 408         }
 409         if (b == null) {
 410             return -1;
 411         }
 412         int length = Math.min(a.length, b.length);
 413         for (int i=0; i<length; i++) {
 414             short av = a[i];
 415             short bv = b[i];
 416             return av < bv ? -1 : (av > bv ? 1 : 0);
 417         }
 418         return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
 419     }
 420
 421     // Compares object arrays and recurses into arrays within.
 422     static int compare(Object[] a, Object[] b) {
 423         if (a == b) {
 424             return 0;
 425         }
 426         if (a == null) {
 427             return 1;
 428         }
 429         if (b == null) {
 430             return -1;
 431         }
 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]);
 435             if (v != 0) {
 436                 return v;
 437             }
 438         }
 439         return a.length < b.length ? -1 : (a.length > b.length ? 1 : 0);
 440     }
 441
 442     // Compares objects or arrays and recurses into arrays within.
 443     static int compare(Object a, Object b) {
 444         if (a == b) {
 445             return 0;
 446         }
 447         if (a == null) {
 448             return 1;
 449         }
 450         if (b == null) {
 451             return -1;
 452         }
 453         Class ac = a.getClass();
 454         if (!(ac.isArray())) {
 455             return ((Comparable)a).compareTo(b);
 456         }
 457         if (ac != b.getClass()) {
 458             throw new ClassCastException();
 459         }
 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);
 478         } else {
 479             throw new ClassCastException();
 480         }
 481     }
 482
 483     protected KeyFactory() {
 484     }
 485
 486     private static interface ArrayKey extends Comparable, 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) : hash;
 505         }
 506
 507         public boolean equals(Object obj) {
 508             return this == obj ? true :
 509                 (obj instanceof BooleanArrayKey ?
 510                  Arrays.equals(mArray, ((BooleanArrayKey) obj).mArray) : false);
 511         }
 512
 513         public int compareTo(Object obj) {
 514             return compare(mArray, ((BooleanArrayKey) obj).mArray);
 515         }
 516     }
 517
 518     private static class ByteArrayKey implements ArrayKey {
 519         protected final byte[] mArray;
 520         private transient int mHash;
 521
 522         ByteArrayKey(byte[] array) {
 523             mArray = array;
 524         }
 525
 526         public int hashCode() {
 527             int hash = mHash;
 528             return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
 529         }
 530
 531         public boolean equals(Object obj) {
 532             return this == obj ? true :
 533                 (obj instanceof ByteArrayKey ?
 534                  Arrays.equals(mArray, ((ByteArrayKey) obj).mArray) : false);
 535         }
 536
 537         public int compareTo(Object obj) {
 538             return compare(mArray, ((ByteArrayKey) obj).mArray);
 539         }
 540     }
 541
 542     private static class CharArrayKey implements ArrayKey {
 543         protected final char[] mArray;
 544         private transient int mHash;
 545
 546         CharArrayKey(char[] array) {
 547             mArray = array;
 548         }
 549
 550         public int hashCode() {
 551             int hash = mHash;
 552             return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
 553         }
 554
 555         public boolean equals(Object obj) {
 556             return this == obj ? true :
 557                 (obj instanceof CharArrayKey ?
 558                  Arrays.equals(mArray, ((CharArrayKey) obj).mArray) : false);
 559         }
 560
 561         public int compareTo(Object obj) {
 562             return compare(mArray, ((CharArrayKey) obj).mArray);
 563         }
 564     }
 565
 566     private static class DoubleArrayKey implements ArrayKey {
 567         protected final double[] mArray;
 568         private transient int mHash;
 569
 570         DoubleArrayKey(double[] array) {
 571             mArray = array;
 572         }
 573
 574         public int hashCode() {
 575             int hash = mHash;
 576             return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
 577         }
 578
 579         public boolean equals(Object obj) {
 580             return this == obj ? true :
 581                 (obj instanceof DoubleArrayKey ?
 582                  Arrays.equals(mArray, ((DoubleArrayKey) obj).mArray) : false);
 583         }
 584
 585         public int compareTo(Object obj) {
 586             return compare(mArray, ((DoubleArrayKey) obj).mArray);
 587         }
 588     }
 589
 590     private static class FloatArrayKey implements ArrayKey {
 591         protected final float[] mArray;
 592         private transient int mHash;
 593
 594         FloatArrayKey(float[] array) {
 595             mArray = array;
 596         }
 597
 598         public int hashCode() {
 599             int hash = mHash;
 600             return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
 601         }
 602
 603         public boolean equals(Object obj) {
 604             return this == obj ? true :
 605                 (obj instanceof FloatArrayKey ?
 606                  Arrays.equals(mArray, ((FloatArrayKey) obj).mArray) : false);
 607         }
 608
 609         public int compareTo(Object obj) {
 610             return compare(mArray, ((FloatArrayKey) obj).mArray);
 611         }
 612     }
 613
 614     private static class IntArrayKey implements ArrayKey {
 615         protected final int[] mArray;
 616         private transient int mHash;
 617
 618         IntArrayKey(int[] array) {
 619             mArray = array;
 620         }
 621
 622         public int hashCode() {
 623             int hash = mHash;
 624             return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
 625         }
 626
 627         public boolean equals(Object obj) {
 628             return this == obj ? true :
 629                 (obj instanceof IntArrayKey ?
 630                  Arrays.equals(mArray, ((IntArrayKey) obj).mArray) : false);
 631         }
 632
 633         public int compareTo(Object obj) {
 634             return compare(mArray, ((IntArrayKey) obj).mArray);
 635         }
 636     }
 637
 638     private static class LongArrayKey implements ArrayKey {
 639         protected final long[] mArray;
 640         private transient int mHash;
 641
 642         LongArrayKey(long[] array) {
 643             mArray = array;
 644         }
 645
 646         public int hashCode() {
 647             int hash = mHash;
 648             return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
 649         }
 650
 651         public boolean equals(Object obj) {
 652             return this == obj ? true :
 653                 (obj instanceof LongArrayKey ?
 654                  Arrays.equals(mArray, ((LongArrayKey) obj).mArray) : false);
 655         }
 656
 657         public int compareTo(Object obj) {
 658             return compare(mArray, ((LongArrayKey) obj).mArray);
 659         }
 660     }
 661
 662     private static class ShortArrayKey implements ArrayKey {
 663         protected final short[] mArray;
 664         private transient int mHash;
 665
 666         ShortArrayKey(short[] array) {
 667             mArray = array;
 668         }
 669
 670         public int hashCode() {
 671             int hash = mHash;
 672             return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
 673         }
 674
 675         public boolean equals(Object obj) {
 676             return this == obj ? true :
 677                 (obj instanceof ShortArrayKey ?
 678                  Arrays.equals(mArray, ((ShortArrayKey) obj).mArray) : false);
 679         }
 680
 681         public int compareTo(Object obj) {
 682             return compare(mArray, ((ShortArrayKey) obj).mArray);
 683         }
 684     }
 685
 686     private static class ObjectArrayKey implements ArrayKey {
 687         protected final Object[] mArray;
 688         private transient int mHash;
 689
 690         ObjectArrayKey(Object[] array) {
 691             mArray = array;
 692         }
 693
 694         public int hashCode() {
 695             int hash = mHash;
 696             return hash == 0 ? mHash = KeyFactory.hashCode(mArray) : hash;
 697         }
 698
 699         public boolean equals(Object obj) {
 700             return this == obj ? true :
 701                 (obj instanceof ObjectArrayKey ?
 702                  KeyFactory.equals(mArray, ((ObjectArrayKey) obj).mArray) : false);
 703         }
 704
 705         public int compareTo(Object obj) {
 706             return compare(mArray, ((ObjectArrayKey) obj).mArray);
 707         }
 708     }
 709 }