001/*
002 * Copyright (C) 2008 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 License
010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
011 * or implied. See the License for the specific language governing permissions and limitations under
012 * the License.
013 */
014
015package com.google.common.primitives;
016
017import static com.google.common.base.Preconditions.checkArgument;
018import static com.google.common.base.Preconditions.checkElementIndex;
019import static com.google.common.base.Preconditions.checkNotNull;
020import static com.google.common.base.Preconditions.checkPositionIndexes;
021import static java.lang.System.arraycopy;
022import static java.util.Arrays.sort;
023import static java.util.Collections.emptyList;
024
025import com.google.common.annotations.GwtCompatible;
026import com.google.common.annotations.GwtIncompatible;
027import com.google.common.annotations.J2ktIncompatible;
028import com.google.errorprone.annotations.InlineMe;
029import com.google.errorprone.annotations.InlineMeValidationDisabled;
030import java.io.Serializable;
031import java.util.AbstractList;
032import java.util.Arrays;
033import java.util.Collection;
034import java.util.Comparator;
035import java.util.List;
036import java.util.RandomAccess;
037import org.jspecify.annotations.Nullable;
038
039/**
040 * Static utility methods pertaining to {@code char} primitives, that are not already found in
041 * either {@link Character} or {@link Arrays}.
042 *
043 * <p>All the operations in this class treat {@code char} values strictly numerically; they are
044 * neither Unicode-aware nor locale-dependent.
045 *
046 * <p>See the Guava User Guide article on <a
047 * href="https://github.com/google/guava/wiki/PrimitivesExplained">primitive utilities</a>.
048 *
049 * @author Kevin Bourrillion
050 * @since 1.0
051 */
052@GwtCompatible
053public final class Chars {
054  private Chars() {}
055
056  /**
057   * The number of bytes required to represent a primitive {@code char} value.
058   *
059   * <p>Prefer {@link Character#BYTES} instead.
060   */
061  // We don't use Character.BYTES here because it's not available under J2KT.
062  public static final int BYTES = Character.SIZE / Byte.SIZE;
063
064  /**
065   * Returns a hash code for {@code value}; obsolete alternative to {@link
066   * Character#hashCode(char)}.
067   *
068   * @param value a primitive {@code char} value
069   * @return a hash code for the value
070   */
071  @InlineMe(replacement = "Character.hashCode(value)")
072  @InlineMeValidationDisabled(
073      "The hash code of a char is the int version of the char itself, so it's simplest to return"
074          + " that.")
075  public static int hashCode(char value) {
076    return value;
077  }
078
079  /**
080   * Returns the {@code char} value that is equal to {@code value}, if possible.
081   *
082   * @param value any value in the range of the {@code char} type
083   * @return the {@code char} value that equals {@code value}
084   * @throws IllegalArgumentException if {@code value} is greater than {@link Character#MAX_VALUE}
085   *     or less than {@link Character#MIN_VALUE}
086   */
087  public static char checkedCast(long value) {
088    char result = (char) value;
089    checkArgument(result == value, "Out of range: %s", value);
090    return result;
091  }
092
093  /**
094   * Returns the {@code char} nearest in value to {@code value}.
095   *
096   * @param value any {@code long} value
097   * @return the same value cast to {@code char} if it is in the range of the {@code char} type,
098   *     {@link Character#MAX_VALUE} if it is too large, or {@link Character#MIN_VALUE} if it is too
099   *     small
100   */
101  public static char saturatedCast(long value) {
102    if (value > Character.MAX_VALUE) {
103      return Character.MAX_VALUE;
104    }
105    if (value < Character.MIN_VALUE) {
106      return Character.MIN_VALUE;
107    }
108    return (char) value;
109  }
110
111  /**
112   * Compares the two specified {@code char} values. The sign of the value returned is the same as
113   * that of {@code ((Character) a).compareTo(b)}.
114   *
115   * <p><b>Note:</b> this method is now unnecessary and should be treated as deprecated; use the
116   * equivalent {@link Character#compare} method instead.
117   *
118   * @param a the first {@code char} to compare
119   * @param b the second {@code char} to compare
120   * @return a negative value if {@code a} is less than {@code b}; a positive value if {@code a} is
121   *     greater than {@code b}; or zero if they are equal
122   */
123  @InlineMe(replacement = "Character.compare(a, b)")
124  public static int compare(char a, char b) {
125    return Character.compare(a, b);
126  }
127
128  /**
129   * Returns {@code true} if {@code target} is present as an element anywhere in {@code array}.
130   *
131   * @param array an array of {@code char} values, possibly empty
132   * @param target a primitive {@code char} value
133   * @return {@code true} if {@code array[i] == target} for some value of {@code i}
134   */
135  public static boolean contains(char[] array, char target) {
136    for (char value : array) {
137      if (value == target) {
138        return true;
139      }
140    }
141    return false;
142  }
143
144  /**
145   * Returns the index of the first appearance of the value {@code target} in {@code array}.
146   *
147   * @param array an array of {@code char} values, possibly empty
148   * @param target a primitive {@code char} value
149   * @return the least index {@code i} for which {@code array[i] == target}, or {@code -1} if no
150   *     such index exists.
151   */
152  public static int indexOf(char[] array, char target) {
153    return indexOf(array, target, 0, array.length);
154  }
155
156  // TODO(kevinb): consider making this public
157  private static int indexOf(char[] array, char target, int start, int end) {
158    for (int i = start; i < end; i++) {
159      if (array[i] == target) {
160        return i;
161      }
162    }
163    return -1;
164  }
165
166  /**
167   * Returns the start position of the first occurrence of the specified {@code target} within
168   * {@code array}, or {@code -1} if there is no such occurrence.
169   *
170   * <p>More formally, returns the lowest index {@code i} such that {@code Arrays.copyOfRange(array,
171   * i, i + target.length)} contains exactly the same elements as {@code target}.
172   *
173   * @param array the array to search for the sequence {@code target}
174   * @param target the array to search for as a sub-sequence of {@code array}
175   */
176  public static int indexOf(char[] array, char[] target) {
177    checkNotNull(array, "array");
178    checkNotNull(target, "target");
179    if (target.length == 0) {
180      return 0;
181    }
182
183    outer:
184    for (int i = 0; i < array.length - target.length + 1; i++) {
185      for (int j = 0; j < target.length; j++) {
186        if (array[i + j] != target[j]) {
187          continue outer;
188        }
189      }
190      return i;
191    }
192    return -1;
193  }
194
195  /**
196   * Returns the index of the last appearance of the value {@code target} in {@code array}.
197   *
198   * @param array an array of {@code char} values, possibly empty
199   * @param target a primitive {@code char} value
200   * @return the greatest index {@code i} for which {@code array[i] == target}, or {@code -1} if no
201   *     such index exists.
202   */
203  public static int lastIndexOf(char[] array, char target) {
204    return lastIndexOf(array, target, 0, array.length);
205  }
206
207  // TODO(kevinb): consider making this public
208  private static int lastIndexOf(char[] array, char target, int start, int end) {
209    for (int i = end - 1; i >= start; i--) {
210      if (array[i] == target) {
211        return i;
212      }
213    }
214    return -1;
215  }
216
217  /**
218   * Returns the least value present in {@code array}.
219   *
220   * @param array a <i>nonempty</i> array of {@code char} values
221   * @return the value present in {@code array} that is less than or equal to every other value in
222   *     the array
223   * @throws IllegalArgumentException if {@code array} is empty
224   */
225  public static char min(char... array) {
226    checkArgument(array.length > 0);
227    char min = array[0];
228    for (int i = 1; i < array.length; i++) {
229      if (array[i] < min) {
230        min = array[i];
231      }
232    }
233    return min;
234  }
235
236  /**
237   * Returns the greatest value present in {@code array}.
238   *
239   * @param array a <i>nonempty</i> array of {@code char} values
240   * @return the value present in {@code array} that is greater than or equal to every other value
241   *     in the array
242   * @throws IllegalArgumentException if {@code array} is empty
243   */
244  public static char max(char... array) {
245    checkArgument(array.length > 0);
246    char max = array[0];
247    for (int i = 1; i < array.length; i++) {
248      if (array[i] > max) {
249        max = array[i];
250      }
251    }
252    return max;
253  }
254
255  /**
256   * Returns the value nearest to {@code value} which is within the closed range {@code [min..max]}.
257   *
258   * <p>If {@code value} is within the range {@code [min..max]}, {@code value} is returned
259   * unchanged. If {@code value} is less than {@code min}, {@code min} is returned, and if {@code
260   * value} is greater than {@code max}, {@code max} is returned.
261   *
262   * @param value the {@code char} value to constrain
263   * @param min the lower bound (inclusive) of the range to constrain {@code value} to
264   * @param max the upper bound (inclusive) of the range to constrain {@code value} to
265   * @throws IllegalArgumentException if {@code min > max}
266   * @since 21.0
267   */
268  public static char constrainToRange(char value, char min, char max) {
269    checkArgument(min <= max, "min (%s) must be less than or equal to max (%s)", min, max);
270    return value < min ? min : value < max ? value : max;
271  }
272
273  /**
274   * Returns the values from each provided array combined into a single array. For example, {@code
275   * concat(new char[] {a, b}, new char[] {}, new char[] {c}} returns the array {@code {a, b, c}}.
276   *
277   * @param arrays zero or more {@code char} arrays
278   * @return a single array containing all the values from the source arrays, in order
279   * @throws IllegalArgumentException if the total number of elements in {@code arrays} does not fit
280   *     in an {@code int}
281   */
282  public static char[] concat(char[]... arrays) {
283    long length = 0;
284    for (char[] array : arrays) {
285      length += array.length;
286    }
287    char[] result = new char[checkNoOverflow(length)];
288    int pos = 0;
289    for (char[] array : arrays) {
290      arraycopy(array, 0, result, pos, array.length);
291      pos += array.length;
292    }
293    return result;
294  }
295
296  private static int checkNoOverflow(long result) {
297    checkArgument(
298        result == (int) result,
299        "the total number of elements (%s) in the arrays must fit in an int",
300        result);
301    return (int) result;
302  }
303
304  /**
305   * Returns a big-endian representation of {@code value} in a 2-element byte array; equivalent to
306   * {@code ByteBuffer.allocate(2).putChar(value).array()}. For example, the input value {@code
307   * '\\u5432'} would yield the byte array {@code {0x54, 0x32}}.
308   *
309   * <p>If you need to convert and concatenate several values (possibly even of different types),
310   * use a shared {@link java.nio.ByteBuffer} instance, or use {@link
311   * com.google.common.io.ByteStreams#newDataOutput()} to get a growable buffer.
312   */
313  @GwtIncompatible // doesn't work
314  public static byte[] toByteArray(char value) {
315    return new byte[] {(byte) (value >> 8), (byte) value};
316  }
317
318  /**
319   * Returns the {@code char} value whose big-endian representation is stored in the first 2 bytes
320   * of {@code bytes}; equivalent to {@code ByteBuffer.wrap(bytes).getChar()}. For example, the
321   * input byte array {@code {0x54, 0x32}} would yield the {@code char} value {@code '\\u5432'}.
322   *
323   * <p>Arguably, it's preferable to use {@link java.nio.ByteBuffer}; that library exposes much more
324   * flexibility at little cost in readability.
325   *
326   * @throws IllegalArgumentException if {@code bytes} has fewer than 2 elements
327   */
328  @GwtIncompatible // doesn't work
329  public static char fromByteArray(byte[] bytes) {
330    checkArgument(bytes.length >= BYTES, "array too small: %s < %s", bytes.length, BYTES);
331    return fromBytes(bytes[0], bytes[1]);
332  }
333
334  /**
335   * Returns the {@code char} value whose byte representation is the given 2 bytes, in big-endian
336   * order; equivalent to {@code Chars.fromByteArray(new byte[] {b1, b2})}.
337   *
338   * @since 7.0
339   */
340  @GwtIncompatible // doesn't work
341  public static char fromBytes(byte b1, byte b2) {
342    return (char) ((b1 << 8) | (b2 & 0xFF));
343  }
344
345  /**
346   * Returns an array containing the same values as {@code array}, but guaranteed to be of a
347   * specified minimum length. If {@code array} already has a length of at least {@code minLength},
348   * it is returned directly. Otherwise, a new array of size {@code minLength + padding} is
349   * returned, containing the values of {@code array}, and zeroes in the remaining places.
350   *
351   * @param array the source array
352   * @param minLength the minimum length the returned array must guarantee
353   * @param padding an extra amount to "grow" the array by if growth is necessary
354   * @throws IllegalArgumentException if {@code minLength} or {@code padding} is negative
355   * @return an array containing the values of {@code array}, with guaranteed minimum length {@code
356   *     minLength}
357   */
358  public static char[] ensureCapacity(char[] array, int minLength, int padding) {
359    checkArgument(minLength >= 0, "Invalid minLength: %s", minLength);
360    checkArgument(padding >= 0, "Invalid padding: %s", padding);
361    return (array.length < minLength) ? Arrays.copyOf(array, minLength + padding) : array;
362  }
363
364  /**
365   * Returns a string containing the supplied {@code char} values separated by {@code separator}.
366   * For example, {@code join("-", '1', '2', '3')} returns the string {@code "1-2-3"}.
367   *
368   * @param separator the text that should appear between consecutive values in the resulting string
369   *     (but not at the start or end)
370   * @param array an array of {@code char} values, possibly empty
371   */
372  public static String join(String separator, char... array) {
373    checkNotNull(separator);
374    int len = array.length;
375    if (len == 0) {
376      return "";
377    }
378
379    StringBuilder builder = new StringBuilder(len + separator.length() * (len - 1));
380    builder.append(array[0]);
381    for (int i = 1; i < len; i++) {
382      builder.append(separator).append(array[i]);
383    }
384    return builder.toString();
385  }
386
387  /**
388   * Returns a comparator that compares two {@code char} arrays <a
389   * href="http://en.wikipedia.org/wiki/Lexicographical_order">lexicographically</a>; not advisable
390   * for sorting user-visible strings as the ordering may not match the conventions of the user's
391   * locale. That is, it compares, using {@link #compare(char, char)}), the first pair of values
392   * that follow any common prefix, or when one array is a prefix of the other, treats the shorter
393   * array as the lesser. For example, {@code [] < ['a'] < ['a', 'b'] < ['b']}.
394   *
395   * <p>The returned comparator is inconsistent with {@link Object#equals(Object)} (since arrays
396   * support only identity equality), but it is consistent with {@link Arrays#equals(char[],
397   * char[])}.
398   *
399   * @since 2.0
400   */
401  public static Comparator<char[]> lexicographicalComparator() {
402    return LexicographicalComparator.INSTANCE;
403  }
404
405  private enum LexicographicalComparator implements Comparator<char[]> {
406    INSTANCE;
407
408    @Override
409    public int compare(char[] left, char[] right) {
410      int minLength = Math.min(left.length, right.length);
411      for (int i = 0; i < minLength; i++) {
412        int result = Character.compare(left[i], right[i]);
413        if (result != 0) {
414          return result;
415        }
416      }
417      return left.length - right.length;
418    }
419
420    @Override
421    public String toString() {
422      return "Chars.lexicographicalComparator()";
423    }
424  }
425
426  /**
427   * Copies a collection of {@code Character} instances into a new array of primitive {@code char}
428   * values.
429   *
430   * <p>Elements are copied from the argument collection as if by {@code collection.toArray()}.
431   * Calling this method is as thread-safe as calling that method.
432   *
433   * @param collection a collection of {@code Character} objects
434   * @return an array containing the same values as {@code collection}, in the same order, converted
435   *     to primitives
436   * @throws NullPointerException if {@code collection} or any of its elements is null
437   */
438  public static char[] toArray(Collection<Character> collection) {
439    if (collection instanceof CharArrayAsList) {
440      return ((CharArrayAsList) collection).toCharArray();
441    }
442
443    Object[] boxedArray = collection.toArray();
444    int len = boxedArray.length;
445    char[] array = new char[len];
446    for (int i = 0; i < len; i++) {
447      // checkNotNull for GWT (do not optimize)
448      array[i] = (Character) checkNotNull(boxedArray[i]);
449    }
450    return array;
451  }
452
453  /**
454   * Sorts the elements of {@code array} in descending order.
455   *
456   * @since 23.1
457   */
458  public static void sortDescending(char[] array) {
459    checkNotNull(array);
460    sortDescending(array, 0, array.length);
461  }
462
463  /**
464   * Sorts the elements of {@code array} between {@code fromIndex} inclusive and {@code toIndex}
465   * exclusive in descending order.
466   *
467   * @since 23.1
468   */
469  public static void sortDescending(char[] array, int fromIndex, int toIndex) {
470    checkNotNull(array);
471    checkPositionIndexes(fromIndex, toIndex, array.length);
472    sort(array, fromIndex, toIndex);
473    reverse(array, fromIndex, toIndex);
474  }
475
476  /**
477   * Reverses the elements of {@code array}. This is equivalent to {@code
478   * Collections.reverse(Chars.asList(array))}, but is likely to be more efficient.
479   *
480   * @since 23.1
481   */
482  public static void reverse(char[] array) {
483    checkNotNull(array);
484    reverse(array, 0, array.length);
485  }
486
487  /**
488   * Reverses the elements of {@code array} between {@code fromIndex} inclusive and {@code toIndex}
489   * exclusive. This is equivalent to {@code
490   * Collections.reverse(Chars.asList(array).subList(fromIndex, toIndex))}, but is likely to be more
491   * efficient.
492   *
493   * @throws IndexOutOfBoundsException if {@code fromIndex < 0}, {@code toIndex > array.length}, or
494   *     {@code toIndex > fromIndex}
495   * @since 23.1
496   */
497  public static void reverse(char[] array, int fromIndex, int toIndex) {
498    checkNotNull(array);
499    checkPositionIndexes(fromIndex, toIndex, array.length);
500    for (int i = fromIndex, j = toIndex - 1; i < j; i++, j--) {
501      char tmp = array[i];
502      array[i] = array[j];
503      array[j] = tmp;
504    }
505  }
506
507  /**
508   * Performs a right rotation of {@code array} of "distance" places, so that the first element is
509   * moved to index "distance", and the element at index {@code i} ends up at index {@code (distance
510   * + i) mod array.length}. This is equivalent to {@code Collections.rotate(Chars.asList(array),
511   * distance)}, but is considerably faster and avoids allocation and garbage collection.
512   *
513   * <p>The provided "distance" may be negative, which will rotate left.
514   *
515   * @since 32.0.0
516   */
517  public static void rotate(char[] array, int distance) {
518    rotate(array, distance, 0, array.length);
519  }
520
521  /**
522   * Performs a right rotation of {@code array} between {@code fromIndex} inclusive and {@code
523   * toIndex} exclusive. This is equivalent to {@code
524   * Collections.rotate(Chars.asList(array).subList(fromIndex, toIndex), distance)}, but is
525   * considerably faster and avoids allocations and garbage collection.
526   *
527   * <p>The provided "distance" may be negative, which will rotate left.
528   *
529   * @throws IndexOutOfBoundsException if {@code fromIndex < 0}, {@code toIndex > array.length}, or
530   *     {@code toIndex > fromIndex}
531   * @since 32.0.0
532   */
533  public static void rotate(char[] array, int distance, int fromIndex, int toIndex) {
534    // See Ints.rotate for more details about possible algorithms here.
535    checkNotNull(array);
536    checkPositionIndexes(fromIndex, toIndex, array.length);
537    if (array.length <= 1) {
538      return;
539    }
540
541    int length = toIndex - fromIndex;
542    // Obtain m = (-distance mod length), a non-negative value less than "length". This is how many
543    // places left to rotate.
544    int m = -distance % length;
545    m = (m < 0) ? m + length : m;
546    // The current index of what will become the first element of the rotated section.
547    int newFirstIndex = m + fromIndex;
548    if (newFirstIndex == fromIndex) {
549      return;
550    }
551
552    reverse(array, fromIndex, newFirstIndex);
553    reverse(array, newFirstIndex, toIndex);
554    reverse(array, fromIndex, toIndex);
555  }
556
557  /**
558   * Returns a fixed-size list backed by the specified array, similar to {@link
559   * Arrays#asList(Object[])}. The list supports {@link List#set(int, Object)}, but any attempt to
560   * set a value to {@code null} will result in a {@link NullPointerException}.
561   *
562   * <p>The returned list maintains the values, but not the identities, of {@code Character} objects
563   * written to or read from it. For example, whether {@code list.get(0) == list.get(0)} is true for
564   * the returned list is unspecified.
565   *
566   * <p>The returned list is serializable.
567   *
568   * @param backingArray the array to back the list
569   * @return a list view of the array
570   */
571  public static List<Character> asList(char... backingArray) {
572    if (backingArray.length == 0) {
573      return emptyList();
574    }
575    return new CharArrayAsList(backingArray);
576  }
577
578  private static final class CharArrayAsList extends AbstractList<Character>
579      implements RandomAccess, Serializable {
580    final char[] array;
581    final int start;
582    final int end;
583
584    CharArrayAsList(char[] array) {
585      this(array, 0, array.length);
586    }
587
588    CharArrayAsList(char[] array, int start, int end) {
589      this.array = array;
590      this.start = start;
591      this.end = end;
592    }
593
594    @Override
595    public int size() {
596      return end - start;
597    }
598
599    @Override
600    public boolean isEmpty() {
601      return false;
602    }
603
604    @Override
605    public Character get(int index) {
606      checkElementIndex(index, size());
607      return array[start + index];
608    }
609
610    @Override
611    public boolean contains(@Nullable Object target) {
612      // Overridden to prevent a ton of boxing
613      return (target instanceof Character)
614          && Chars.indexOf(array, (Character) target, start, end) != -1;
615    }
616
617    @Override
618    public int indexOf(@Nullable Object target) {
619      // Overridden to prevent a ton of boxing
620      if (target instanceof Character) {
621        int i = Chars.indexOf(array, (Character) target, start, end);
622        if (i >= 0) {
623          return i - start;
624        }
625      }
626      return -1;
627    }
628
629    @Override
630    public int lastIndexOf(@Nullable Object target) {
631      // Overridden to prevent a ton of boxing
632      if (target instanceof Character) {
633        int i = Chars.lastIndexOf(array, (Character) target, start, end);
634        if (i >= 0) {
635          return i - start;
636        }
637      }
638      return -1;
639    }
640
641    @Override
642    public Character set(int index, Character element) {
643      checkElementIndex(index, size());
644      char oldValue = array[start + index];
645      // checkNotNull for GWT (do not optimize)
646      array[start + index] = checkNotNull(element);
647      return oldValue;
648    }
649
650    @Override
651    public List<Character> subList(int fromIndex, int toIndex) {
652      int size = size();
653      checkPositionIndexes(fromIndex, toIndex, size);
654      if (fromIndex == toIndex) {
655        return emptyList();
656      }
657      return new CharArrayAsList(array, start + fromIndex, start + toIndex);
658    }
659
660    @Override
661    public boolean equals(@Nullable Object object) {
662      if (object == this) {
663        return true;
664      }
665      if (object instanceof CharArrayAsList) {
666        CharArrayAsList that = (CharArrayAsList) object;
667        int size = size();
668        if (that.size() != size) {
669          return false;
670        }
671        for (int i = 0; i < size; i++) {
672          if (array[start + i] != that.array[that.start + i]) {
673            return false;
674          }
675        }
676        return true;
677      }
678      return super.equals(object);
679    }
680
681    @Override
682    public int hashCode() {
683      int result = 1;
684      for (int i = start; i < end; i++) {
685        result = 31 * result + Character.hashCode(array[i]);
686      }
687      return result;
688    }
689
690    @Override
691    public String toString() {
692      StringBuilder builder = new StringBuilder(size() * 3);
693      builder.append('[').append(array[start]);
694      for (int i = start + 1; i < end; i++) {
695        builder.append(", ").append(array[i]);
696      }
697      return builder.append(']').toString();
698    }
699
700    char[] toCharArray() {
701      return Arrays.copyOfRange(array, start, end);
702    }
703
704    @GwtIncompatible @J2ktIncompatible private static final long serialVersionUID = 0;
705  }
706}