util/kvstore/ArrayWrappers.java

0001 /*
0002  * Licensed to the Apache Software Foundation (ASF) under one or more
0003  * contributor license agreements.  See the NOTICE file distributed with
0004  * this work for additional information regarding copyright ownership.
0005  * The ASF licenses this file to You under the Apache License, Version 2.0
0006  * (the "License"); you may not use this file except in compliance with
0007  * the License.  You may obtain a copy of the License at
0008  *
0009  *    http://www.apache.org/licenses/LICENSE-2.0
0010  *
0011  * Unless required by applicable law or agreed to in writing, software
0012  * distributed under the License is distributed on an "AS IS" BASIS,
0013  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0014  * See the License for the specific language governing permissions and
0015  * limitations under the License.
0016  */
0017
0018 package org.apache.spark.util.kvstore;
0019
0020 import java.util.Arrays;
0021
0022 import com.google.common.base.Preconditions;
0023
0024 /**
0025  * A factory for array wrappers so that arrays can be used as keys in a map, sorted or not.
0026  *
0027  * The comparator implementation makes two assumptions:
0028  * - All elements are instances of Comparable
0029  * - When comparing two arrays, they both contain elements of the same type in corresponding
0030  *   indices.
0031  *
0032  * Otherwise, ClassCastExceptions may occur. The equality method can compare any two arrays.
0033  *
0034  * This class is not efficient and is mostly meant to compare really small arrays, like those
0035  * generally used as indices and keys in a KVStore.
0036  */
0037 class ArrayWrappers {
0038
0039   @SuppressWarnings("unchecked")
0040   public static Comparable<Object> forArray(Object a) {
0041     Preconditions.checkArgument(a.getClass().isArray());
0042     Comparable<?> ret;
0043     if (a instanceof int[]) {
0044       ret = new ComparableIntArray((int[]) a);
0045     } else if (a instanceof long[]) {
0046       ret = new ComparableLongArray((long[]) a);
0047     } else if (a instanceof byte[]) {
0048       ret = new ComparableByteArray((byte[]) a);
0049     } else {
0050       Preconditions.checkArgument(!a.getClass().getComponentType().isPrimitive());
0051       ret = new ComparableObjectArray((Object[]) a);
0052     }
0053     return (Comparable<Object>) ret;
0054   }
0055
0056   private static class ComparableIntArray implements Comparable<ComparableIntArray> {
0057
0058     private final int[] array;
0059
0060     ComparableIntArray(int[] array) {
0061       this.array = array;
0062     }
0063
0064     @Override
0065     public boolean equals(Object other) {
0066       if (!(other instanceof ComparableIntArray)) {
0067         return false;
0068       }
0069       return Arrays.equals(array, ((ComparableIntArray) other).array);
0070     }
0071
0072     @Override
0073     public int hashCode() {
0074       int code = 0;
0075       for (int i = 0; i < array.length; i++) {
0076         code = (code * 31) + array[i];
0077       }
0078       return code;
0079     }
0080
0081     @Override
0082     public int compareTo(ComparableIntArray other) {
0083       int len = Math.min(array.length, other.array.length);
0084       for (int i = 0; i < len; i++) {
0085         int diff = array[i] - other.array[i];
0086         if (diff != 0) {
0087           return diff;
0088         }
0089       }
0090
0091       return array.length - other.array.length;
0092     }
0093   }
0094
0095   private static class ComparableLongArray implements Comparable<ComparableLongArray> {
0096
0097     private final long[] array;
0098
0099     ComparableLongArray(long[] array) {
0100       this.array = array;
0101     }
0102
0103     @Override
0104     public boolean equals(Object other) {
0105       if (!(other instanceof ComparableLongArray)) {
0106         return false;
0107       }
0108       return Arrays.equals(array, ((ComparableLongArray) other).array);
0109     }
0110
0111     @Override
0112     public int hashCode() {
0113       int code = 0;
0114       for (int i = 0; i < array.length; i++) {
0115         code = (code * 31) + (int) array[i];
0116       }
0117       return code;
0118     }
0119
0120     @Override
0121     public int compareTo(ComparableLongArray other) {
0122       int len = Math.min(array.length, other.array.length);
0123       for (int i = 0; i < len; i++) {
0124         long diff = array[i] - other.array[i];
0125         if (diff != 0) {
0126           return diff > 0 ? 1 : -1;
0127         }
0128       }
0129
0130       return array.length - other.array.length;
0131     }
0132   }
0133
0134   private static class ComparableByteArray implements Comparable<ComparableByteArray> {
0135
0136     private final byte[] array;
0137
0138     ComparableByteArray(byte[] array) {
0139       this.array = array;
0140     }
0141
0142     @Override
0143     public boolean equals(Object other) {
0144       if (!(other instanceof ComparableByteArray)) {
0145         return false;
0146       }
0147       return Arrays.equals(array, ((ComparableByteArray) other).array);
0148     }
0149
0150     @Override
0151     public int hashCode() {
0152       int code = 0;
0153       for (int i = 0; i < array.length; i++) {
0154         code = (code * 31) + array[i];
0155       }
0156       return code;
0157     }
0158
0159     @Override
0160     public int compareTo(ComparableByteArray other) {
0161       int len = Math.min(array.length, other.array.length);
0162       for (int i = 0; i < len; i++) {
0163         int diff = array[i] - other.array[i];
0164         if (diff != 0) {
0165           return diff;
0166         }
0167       }
0168
0169       return array.length - other.array.length;
0170     }
0171   }
0172
0173   private static class ComparableObjectArray implements Comparable<ComparableObjectArray> {
0174
0175     private final Object[] array;
0176
0177     ComparableObjectArray(Object[] array) {
0178       this.array = array;
0179     }
0180
0181     @Override
0182     public boolean equals(Object other) {
0183       if (!(other instanceof ComparableObjectArray)) {
0184         return false;
0185       }
0186       return Arrays.equals(array, ((ComparableObjectArray) other).array);
0187     }
0188
0189     @Override
0190     public int hashCode() {
0191       int code = 0;
0192       for (int i = 0; i < array.length; i++) {
0193         code = (code * 31) + array[i].hashCode();
0194       }
0195       return code;
0196     }
0197
0198     @Override
0199     @SuppressWarnings("unchecked")
0200     public int compareTo(ComparableObjectArray other) {
0201       int len = Math.min(array.length, other.array.length);
0202       for (int i = 0; i < len; i++) {
0203         int diff = ((Comparable<Object>) array[i]).compareTo((Comparable<Object>) other.array[i]);
0204         if (diff != 0) {
0205           return diff;
0206         }
0207       }
0208
0209       return array.length - other.array.length;
0210     }
0211   }
0212
0213 }