001    /*
002     * Copyright (C) 2011 The Guava Authors
003     * 
004     * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
005     * in compliance with the License. You may obtain a copy of the License at
006     * 
007     * http://www.apache.org/licenses/LICENSE-2.0
008     * 
009     * Unless required by applicable law or agreed to in writing, software distributed under the
010     * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
011     * express or implied. See the License for the specific language governing permissions and
012     * limitations under the License.
013     */
014    
015    package com.google.common.primitives;
016    
017    import static com.google.common.base.Preconditions.checkArgument;
018    import static com.google.common.base.Preconditions.checkNotNull;
019    
020    import java.math.BigInteger;
021    import java.util.Arrays;
022    import java.util.Comparator;
023    
024    import com.google.common.annotations.Beta;
025    import com.google.common.annotations.GwtCompatible;
026    
027    /**
028     * Static utility methods pertaining to {@code long} primitives that interpret values as
029     * <i>unsigned</i> (that is, any negative value {@code x} is treated as the positive value
030     * {@code 2^64 + x}). The methods for which signedness is not an issue are in {@link Longs}, as
031     * well as signed versions of methods for which signedness is an issue.
032     * 
033     * <p>In addition, this class provides several static methods for converting a {@code long} to a
034     * {@code String} and a {@code String} to a {@code long} that treat the {@code long} as an unsigned
035     * number.
036     * 
037     * <p>Users of these utilities must be <i>extremely careful</i> not to mix up signed and unsigned
038     * {@code long} values. When possible, it is recommended that the {@link UnsignedLong} wrapper 
039     * class be used, at a small efficiency penalty, to enforce the distinction in the type system.
040     * 
041     * @author Louis Wasserman
042     * @author Brian Milch
043     * @author Colin Evans
044     * @since 10.0
045     */
046    @Beta
047    @GwtCompatible
048    public final class UnsignedLongs {
049      private UnsignedLongs() {}
050    
051      public static final long MAX_VALUE = -1L; // Equivalent to 2^64 - 1
052    
053      /**
054       * A (self-inverse) bijection which converts the ordering on unsigned longs to the ordering on
055       * longs, that is, {@code a <= b} as unsigned longs if and only if {@code rotate(a) <= rotate(b)}
056       * as signed longs.
057       */
058      private static long flip(long a) {
059        return a ^ Long.MIN_VALUE;
060      }
061    
062      /**
063       * Compares the two specified {@code long} values, treating them as unsigned values between
064       * {@code 0} and {@code 2^64 - 1} inclusive.
065       * 
066       * @param a the first unsigned {@code long} to compare
067       * @param b the second unsigned {@code long} to compare
068       * @return a negative value if {@code a} is less than {@code b}; a positive value if {@code a} is
069       *         greater than {@code b}; or zero if they are equal
070       */
071      public static int compare(long a, long b) {
072        return Longs.compare(flip(a), flip(b));
073      }
074    
075      /**
076       * Returns the least value present in {@code array}.
077       * 
078       * @param array a <i>nonempty</i> array of unsigned {@code long} values
079       * @return the value present in {@code array} that is less than or equal to every other value in
080       *         the array according to {@link #compare}
081       * @throws IllegalArgumentException if {@code array} is empty
082       */
083      public static long min(long... array) {
084        checkArgument(array.length > 0);
085        long min = flip(array[0]);
086        for (int i = 1; i < array.length; i++) {
087          long next = flip(array[i]);
088          if (next < min) {
089            min = next;
090          }
091        }
092        return flip(min);
093      }
094    
095      /**
096       * Returns the greatest value present in {@code array}.
097       * 
098       * @param array a <i>nonempty</i> array of unsigned {@code long} values
099       * @return the value present in {@code array} that is greater than or equal to every other value
100       *         in the array according to {@link #compare}
101       * @throws IllegalArgumentException if {@code array} is empty
102       */
103      public static long max(long... array) {
104        checkArgument(array.length > 0);
105        long max = flip(array[0]);
106        for (int i = 1; i < array.length; i++) {
107          long next = flip(array[i]);
108          if (next > max) {
109            max = next;
110          }
111        }
112        return flip(max);
113      }
114    
115      /**
116       * Returns a string containing the supplied unsigned {@code long} values separated by
117       * {@code separator}. For example, {@code join("-", 1, 2, 3)} returns the string {@code "1-2-3"}.
118       * 
119       * @param separator the text that should appear between consecutive values in the resulting
120       *        string (but not at the start or end)
121       * @param array an array of unsigned {@code long} values, possibly empty
122       */
123      public static String join(String separator, long... array) {
124        checkNotNull(separator);
125        if (array.length == 0) {
126          return "";
127        }
128    
129        // For pre-sizing a builder, just get the right order of magnitude
130        StringBuilder builder = new StringBuilder(array.length * 5);
131        builder.append(array[0]);
132        for (int i = 1; i < array.length; i++) {
133          builder.append(separator).append(toString(array[i]));
134        }
135        return builder.toString();
136      }
137    
138      /**
139       * Returns a comparator that compares two {@code long} arrays lexicographically. That is, it
140       * compares, using {@link #compare(long, long)}), the first pair of values that follow any common
141       * prefix, or when one array is a prefix of the other, treats the shorter array as the lesser.
142       * For example, {@code [] < [1L] < [1L, 2L] < [2L]}. Values are treated as unsigned.
143       * 
144       * <p>
145       * The returned comparator is inconsistent with {@link Object#equals(Object)} (since arrays
146       * support only identity equality), but it is consistent with
147       * {@link Arrays#equals(long[], long[])}.
148       * 
149       * @see <a href="http://en.wikipedia.org/wiki/Lexicographical_order">Lexicographical order
150       *      article at Wikipedia</a>
151       */
152      public static Comparator<long[]> lexicographicalComparator() {
153        return LexicographicalComparator.INSTANCE;
154      }
155    
156      enum LexicographicalComparator implements Comparator<long[]> {
157        INSTANCE;
158    
159        @Override
160        public int compare(long[] left, long[] right) {
161          int minLength = Math.min(left.length, right.length);
162          for (int i = 0; i < minLength; i++) {
163            if (left[i] != right[i]) {
164              return UnsignedLongs.compare(left[i], right[i]);
165            }
166          }
167          return left.length - right.length;
168        }
169      }
170    
171      /**
172       * Returns dividend / divisor, where the dividend and divisor are treated as unsigned 64-bit
173       * quantities.
174       * 
175       * @param dividend the dividend (numerator)
176       * @param divisor the divisor (denominator)
177       * @throws ArithmeticException if divisor is 0
178       */
179      public static long divide(long dividend, long divisor) {
180        if (divisor < 0) { // i.e., divisor >= 2^63:
181          if (compare(dividend, divisor) < 0) {
182            return 0; // dividend < divisor
183          } else {
184            return 1; // dividend >= divisor
185          }
186        }
187    
188        // Optimization - use signed division if dividend < 2^63
189        if (dividend >= 0) {
190          return dividend / divisor;
191        }
192    
193        /*
194         * Otherwise, approximate the quotient, check, and correct if necessary. Our approximation is
195         * guaranteed to be either exact or one less than the correct value. This follows from fact
196         * that floor(floor(x)/i) == floor(x/i) for any real x and integer i != 0. The proof is not
197         * quite trivial.
198         */
199        long quotient = ((dividend >>> 1) / divisor) << 1;
200        long rem = dividend - quotient * divisor;
201        return quotient + (compare(rem, divisor) >= 0 ? 1 : 0);
202      }
203    
204      /**
205       * Returns dividend % divisor, where the dividend and divisor are treated as unsigned 64-bit
206       * quantities.
207       * 
208       * @param dividend the dividend (numerator)
209       * @param divisor the divisor (denominator)
210       * @throws ArithmeticException if divisor is 0
211       */
212      public static long remainder(long dividend, long divisor) {
213        if (divisor < 0) { // i.e., divisor >= 2^63:
214          if (compare(dividend, divisor) < 0) {
215            return dividend; // dividend < divisor
216          } else {
217            return dividend - divisor; // dividend >= divisor
218          }
219        }
220    
221        // Optimization - use signed modulus if dividend < 2^63
222        if (dividend >= 0) {
223          return dividend % divisor;
224        }
225    
226        /*
227         * Otherwise, approximate the quotient, check, and correct if necessary. Our approximation is
228         * guaranteed to be either exact or one less than the correct value. This follows from fact
229         * that floor(floor(x)/i) == floor(x/i) for any real x and integer i != 0. The proof is not
230         * quite trivial.
231         */
232        long quotient = ((dividend >>> 1) / divisor) << 1;
233        long rem = dividend - quotient * divisor;
234        return rem - (compare(rem, divisor) >= 0 ? divisor : 0);
235      }
236    
237      /**
238       * Returns the unsigned {@code long} value represented by the given decimal string.
239       * 
240       * @throws NumberFormatException if the string does not contain a valid unsigned {@code long}
241       *         value
242       */
243      public static long parseUnsignedLong(String s) {
244        return parseUnsignedLong(s, 10);
245      }
246    
247      /**
248       * Returns the unsigned {@code long} value represented by a string with the given radix.
249       * 
250       * @param s the string containing the unsigned {@code long} representation to be parsed.
251       * @param radix the radix to use while parsing {@code s}
252       * @throws NumberFormatException if the string does not contain a valid unsigned {@code long}
253       *         with the given radix, or if {@code radix} is not between {@link Character#MIN_RADIX}
254       *         and {@link Character#MAX_RADIX}.
255       */
256      public static long parseUnsignedLong(String s, int radix) {
257        checkNotNull(s);
258        if (s.length() == 0) {
259          throw new NumberFormatException("empty string");
260        }
261        if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX) {
262          throw new NumberFormatException("illegal radix:" + radix);
263        }
264    
265        int max_safe_pos = maxSafeDigits[radix] - 1;
266        long value = 0;
267        for (int pos = 0; pos < s.length(); pos++) {
268          int digit = Character.digit(s.charAt(pos), radix);
269          if (digit == -1) {
270            throw new NumberFormatException(s);
271          }
272          if (pos > max_safe_pos && overflowInParse(value, digit, radix)) {
273            throw new NumberFormatException("Too large for unsigned long: " + s);
274          }
275          value = (value * radix) + digit;
276        }
277    
278        return value;
279      }
280    
281      /**
282       * Returns true if (current * radix) + digit is a number too large to be represented by an
283       * unsigned long. This is useful for detecting overflow while parsing a string representation of
284       * a number. Does not verify whether supplied radix is valid, passing an invalid radix will give
285       * undefined results or an ArrayIndexOutOfBoundsException.
286       */
287      private static boolean overflowInParse(long current, int digit, int radix) {
288        if (current >= 0) {
289          if (current < maxValueDivs[radix]) {
290            return false;
291          }
292          if (current > maxValueDivs[radix]) {
293            return true;
294          }
295          // current == maxValueDivs[radix]
296          return (digit > maxValueMods[radix]);
297        }
298    
299        // current < 0: high bit is set
300        return true;
301      }
302    
303      /**
304       * Returns a string representation of x, where x is treated as unsigned.
305       */
306      public static String toString(long x) {
307        return toString(x, 10);
308      }
309    
310      /**
311       * Returns a string representation of {@code x} for the given radix, where {@code x} is treated
312       * as unsigned.
313       * 
314       * @param x the value to convert to a string.
315       * @param radix the radix to use while working with {@code x}
316       * @throws IllegalArgumentException if {@code radix} is not between {@link Character#MIN_RADIX}
317       *         and {@link Character#MAX_RADIX}.
318       */
319      public static String toString(long x, int radix) {
320        checkArgument(radix >= Character.MIN_RADIX && radix <= Character.MAX_RADIX,
321            "radix (%s) must be between Character.MIN_RADIX and Character.MAX_RADIX", radix);
322        if (x == 0) {
323          // Simply return "0"
324          return "0";
325        } else {
326          char[] buf = new char[64];
327          int i = buf.length;
328          if (x < 0) {
329            // Split x into high-order and low-order halves.
330            // Individual digits are generated from the bottom half into which
331            // bits are moved continously from the top half.
332            long top = x >>> 32;
333            long bot = (x & 0xffffffffl) + ((top % radix) << 32);
334            top /= radix;
335            while ((bot > 0) || (top > 0)) {
336              buf[--i] = Character.forDigit((int) (bot % radix), radix);
337              bot = (bot / radix) + ((top % radix) << 32);
338              top /= radix;
339            }
340          } else {
341            // Simple modulo/division approach
342            while (x > 0) {
343              buf[--i] = Character.forDigit((int) (x % radix), radix);
344              x /= radix;
345            }
346          }
347          // Generate string
348          return new String(buf, i, buf.length - i);
349        }
350      }
351    
352      // calculated as 0xffffffffffffffff / radix
353      private static final long[] maxValueDivs = new long[Character.MAX_RADIX + 1];
354      private static final int[] maxValueMods = new int[Character.MAX_RADIX + 1];
355      private static final int[] maxSafeDigits = new int[Character.MAX_RADIX + 1];
356      static {
357        BigInteger overflow = new BigInteger("10000000000000000", 16);
358        for (int i = Character.MIN_RADIX; i <= Character.MAX_RADIX; i++) {
359          maxValueDivs[i] = divide(MAX_VALUE, i);
360          maxValueMods[i] = (int) remainder(MAX_VALUE, i);
361          maxSafeDigits[i] = overflow.toString(i).length() - 1;
362        }
363      }
364    }