unsafe/sort/PrefixComparators.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.collection.unsafe.sort;
0019
0020 import com.google.common.primitives.UnsignedLongs;
0021
0022 import org.apache.spark.annotation.Private;
0023 import org.apache.spark.unsafe.types.ByteArray;
0024 import org.apache.spark.unsafe.types.UTF8String;
0025
0026 @Private
0027 public class PrefixComparators {
0028   private PrefixComparators() {}
0029
0030   public static final PrefixComparator STRING = new UnsignedPrefixComparator();
0031   public static final PrefixComparator STRING_DESC = new UnsignedPrefixComparatorDesc();
0032   public static final PrefixComparator STRING_NULLS_LAST = new UnsignedPrefixComparatorNullsLast();
0033   public static final PrefixComparator STRING_DESC_NULLS_FIRST =
0034     new UnsignedPrefixComparatorDescNullsFirst();
0035
0036   public static final PrefixComparator BINARY = new UnsignedPrefixComparator();
0037   public static final PrefixComparator BINARY_DESC = new UnsignedPrefixComparatorDesc();
0038   public static final PrefixComparator BINARY_NULLS_LAST = new UnsignedPrefixComparatorNullsLast();
0039   public static final PrefixComparator BINARY_DESC_NULLS_FIRST =
0040     new UnsignedPrefixComparatorDescNullsFirst();
0041
0042   public static final PrefixComparator LONG = new SignedPrefixComparator();
0043   public static final PrefixComparator LONG_DESC = new SignedPrefixComparatorDesc();
0044   public static final PrefixComparator LONG_NULLS_LAST = new SignedPrefixComparatorNullsLast();
0045   public static final PrefixComparator LONG_DESC_NULLS_FIRST =
0046     new SignedPrefixComparatorDescNullsFirst();
0047
0048   public static final PrefixComparator DOUBLE = new UnsignedPrefixComparator();
0049   public static final PrefixComparator DOUBLE_DESC = new UnsignedPrefixComparatorDesc();
0050   public static final PrefixComparator DOUBLE_NULLS_LAST = new UnsignedPrefixComparatorNullsLast();
0051   public static final PrefixComparator DOUBLE_DESC_NULLS_FIRST =
0052     new UnsignedPrefixComparatorDescNullsFirst();
0053
0054   public static final class StringPrefixComparator {
0055     public static long computePrefix(UTF8String value) {
0056       return value == null ? 0L : value.getPrefix();
0057     }
0058   }
0059
0060   public static final class BinaryPrefixComparator {
0061     public static long computePrefix(byte[] bytes) {
0062       return ByteArray.getPrefix(bytes);
0063     }
0064   }
0065
0066   public static final class DoublePrefixComparator {
0067     /**
0068      * Converts the double into a value that compares correctly as an unsigned long. For more
0069      * details see http://stereopsis.com/radix.html.
0070      */
0071     public static long computePrefix(double value) {
0072       // normalize -0.0 to 0.0, as they should be equal
0073       value = value == -0.0 ? 0.0 : value;
0074       // Java's doubleToLongBits already canonicalizes all NaN values to the smallest possible
0075       // positive NaN, so there's nothing special we need to do for NaNs.
0076       long bits = Double.doubleToLongBits(value);
0077       // Negative floats compare backwards due to their sign-magnitude representation, so flip
0078       // all the bits in this case.
0079       long mask = -(bits >>> 63) | 0x8000000000000000L;
0080       return bits ^ mask;
0081     }
0082   }
0083
0084   /**
0085    * Provides radix sort parameters. Comparators implementing this also are indicating that the
0086    * ordering they define is compatible with radix sort.
0087    */
0088   public abstract static class RadixSortSupport extends PrefixComparator {
0089     /** @return Whether the sort should be descending in binary sort order. */
0090     public abstract boolean sortDescending();
0091
0092     /** @return Whether the sort should take into account the sign bit. */
0093     public abstract boolean sortSigned();
0094
0095     /** @return Whether the sort should put nulls first or last. */
0096     public abstract boolean nullsFirst();
0097   }
0098
0099   //
0100   // Standard prefix comparator implementations
0101   //
0102
0103   public static final class UnsignedPrefixComparator extends RadixSortSupport {
0104     @Override public boolean sortDescending() { return false; }
0105     @Override public boolean sortSigned() { return false; }
0106     @Override public boolean nullsFirst() { return true; }
0107     public int compare(long aPrefix, long bPrefix) {
0108       return UnsignedLongs.compare(aPrefix, bPrefix);
0109     }
0110   }
0111
0112   public static final class UnsignedPrefixComparatorNullsLast extends RadixSortSupport {
0113     @Override public boolean sortDescending() { return false; }
0114     @Override public boolean sortSigned() { return false; }
0115     @Override public boolean nullsFirst() { return false; }
0116     public int compare(long aPrefix, long bPrefix) {
0117       return UnsignedLongs.compare(aPrefix, bPrefix);
0118     }
0119   }
0120
0121   public static final class UnsignedPrefixComparatorDescNullsFirst extends RadixSortSupport {
0122     @Override public boolean sortDescending() { return true; }
0123     @Override public boolean sortSigned() { return false; }
0124     @Override public boolean nullsFirst() { return true; }
0125     public int compare(long bPrefix, long aPrefix) {
0126       return UnsignedLongs.compare(aPrefix, bPrefix);
0127     }
0128   }
0129
0130   public static final class UnsignedPrefixComparatorDesc extends RadixSortSupport {
0131     @Override public boolean sortDescending() { return true; }
0132     @Override public boolean sortSigned() { return false; }
0133     @Override public boolean nullsFirst() { return false; }
0134     public int compare(long bPrefix, long aPrefix) {
0135       return UnsignedLongs.compare(aPrefix, bPrefix);
0136     }
0137   }
0138
0139   public static final class SignedPrefixComparator extends RadixSortSupport {
0140     @Override public boolean sortDescending() { return false; }
0141     @Override public boolean sortSigned() { return true; }
0142     @Override public boolean nullsFirst() { return true; }
0143     public int compare(long a, long b) {
0144       return (a < b) ? -1 : (a > b) ? 1 : 0;
0145     }
0146   }
0147
0148   public static final class SignedPrefixComparatorNullsLast extends RadixSortSupport {
0149     @Override public boolean sortDescending() { return false; }
0150     @Override public boolean sortSigned() { return true; }
0151     @Override public boolean nullsFirst() { return false; }
0152     public int compare(long a, long b) {
0153       return (a < b) ? -1 : (a > b) ? 1 : 0;
0154     }
0155   }
0156
0157   public static final class SignedPrefixComparatorDescNullsFirst extends RadixSortSupport {
0158     @Override public boolean sortDescending() { return true; }
0159     @Override public boolean sortSigned() { return true; }
0160     @Override public boolean nullsFirst() { return true; }
0161     public int compare(long b, long a) {
0162       return (a < b) ? -1 : (a > b) ? 1 : 0;
0163     }
0164   }
0165
0166   public static final class SignedPrefixComparatorDesc extends RadixSortSupport {
0167     @Override public boolean sortDescending() { return true; }
0168     @Override public boolean sortSigned() { return true; }
0169     @Override public boolean nullsFirst() { return false; }
0170     public int compare(long b, long a) {
0171       return (a < b) ? -1 : (a > b) ? 1 : 0;
0172     }
0173   }
0174 }