ArrayUtils.java

package io.github.chermehdi.lib;


import io.github.chermehdi.lib.ds.CountingMap;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;
import java.util.function.Function;
import java.util.function.IntPredicate;
import java.util.function.Predicate;
import java.util.function.Supplier;

public class ArrayUtils {


  public static final int dx8[] = new int[]{1, 1, 0, -1, -1, -1, 0, 1};
  public static final int dy8[] = new int[]{0, 1, 1, 1, 0, -1, -1, -1};
  public static final int dx4[] = new int[]{1, -1, 0, 0};
  public static final int dy4[] = new int[]{0, 0, 1, -1};

  public static void rotate(int[] arr, int times) {
    for (int i = 0; i < times; i++) {
      for (int j = arr.length - 1; j > 0; j--) {
        int temp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = temp;
      }
    }
  }

  public static long maxSubArraySum(long[] arr) {
    long max = -1 * (long) 1e15, maxHere = 0;
    for (int i = 0; i < arr.length; i++) {
      maxHere = maxHere + arr[i];
      if (max < maxHere) {
        max = maxHere;
      }
      if (maxHere < 0) {
        maxHere = 0;
      }
    }
    return max;
  }

  public static void rotate(long[] arr, int times) {
    for (int i = 0; i < times; i++) {
      for (int j = arr.length - 1; j > 0; j--) {
        long temp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = temp;
      }
    }
  }

  public static void reverse(int[] arr) {
    for (int i = 0; i < arr.length / 2; i++) {
      int temp = arr[i];
      arr[i] = arr[arr.length - i - 1];
      arr[arr.length - i - 1] = temp;
    }
  }

  public static <T> void reverse(T[] arr) {
    for (int i = 0; i < arr.length / 2; i++) {
      T temp = arr[i];
      arr[i] = arr[arr.length - i - 1];
      arr[arr.length - i - 1] = temp;
    }
  }

  public static void reverse(long[] arr) {
    for (int i = 0; i < arr.length / 2; i++) {
      long temp = arr[i];
      arr[i] = arr[arr.length - i - 1];
      arr[arr.length - i - 1] = temp;
    }
  }

  public static boolean isSorted(int[] a) {
    if (a.length == 1) {
      return true;
    }
    for (int i = 1; i < a.length; i++) {
      if (a[i] < a[i - 1]) {
        return false;
      }
    }
    return true;
  }

  public static int countMatching(boolean[] val, Predicate<Boolean> test) {
    int ret = 0;
    for (boolean temp : val) {
      if (test.test(temp)) {
        ++ret;
      }
    }
    return ret;
  }

  public static int countMatching(int[] val, Predicate<Integer> test) {
    int ret = 0;
    for (int temp : val) {
      if (test.test(temp)) {
        ++ret;
      }
    }
    return ret;
  }

  public static int countMatching(long[] val, Predicate<Long> test) {
    int ret = 0;
    for (long temp : val) {
      if (test.test(temp)) {
        ++ret;
      }
    }
    return ret;
  }

  public static boolean isSorted(long[] a) {
    if (a.length == 1) {
      return true;
    }
    for (int i = 1; i < a.length; i++) {
      if (a[i] < a[i - 1]) {
        return false;
      }
    }
    return true;
  }

  public static void radixSort(int[] a) {
    final int d = 8;
    final int w = 32;
    int[] t = new int[a.length];
    for (int p = 0; p < w / d; p++) {
      int[] cnt = new int[1 << d];
      for (int i = 0; i < a.length; i++) {
        ++cnt[((a[i] ^ Integer.MIN_VALUE) >>> (d * p)) & ((1 << d) - 1)];
      }
      for (int i = 1; i < cnt.length; i++) {
        cnt[i] += cnt[i - 1];
      }
      for (int i = a.length - 1; i >= 0; i--) {
        t[--cnt[((a[i] ^ Integer.MIN_VALUE) >>> (d * p)) & ((1 << d) - 1)]] = a[i];
      }
      System.arraycopy(t, 0, a, 0, a.length);
    }
  }

  public static int max(int[] arr) {
    int val = arr[0];
    for (int i = 1; i < arr.length; i++) {
      if (arr[i] > val) {
        val = arr[i];
      }
    }
    return val;
  }

  public static long max(long[] arr) {
    long val = 0;
    for (int i = 0; i < arr.length; i++) {
      if (arr[i] > val) {
        val = arr[i];
      }
    }
    return val;
  }

  public static long min(long[] arr) {
    long val = (long) 1e18;
    for (int i = 0; i < arr.length; i++) {
      if (arr[i] < val) {
        val = arr[i];
      }
    }
    return val;
  }

  public static int min(int[] arr) {
    int val = arr[0];
    for (int i = 1; i < arr.length; i++) {
      if (arr[i] < val) {
        val = arr[i];
      }
    }
    return val;
  }


  public static int countingInversions(int[] arr) {
    int n = arr.length;
    int[] temp = new int[n];
    return mergeSort(arr, temp, 0, n - 1);
  }

  public static int mergeSort(int[] arr, int[] temp, int left, int right) {
    int ret = 0;
    if (left < right) {
      int mid = (left + right) >> 1;
      ret = mergeSort(arr, temp, left, mid);
      ret += mergeSort(arr, temp, mid + 1, right);
      ret += merge(arr, temp, left, mid + 1, right);
    }
    return ret;
  }

  private static int merge(int[] arr, int[] temp, int left, int mid, int right) {
    int i = left;
    int j = mid;
    int k = left;
    int inv = 0;
    while (i < mid && j <= right) {
      if (arr[i] <= arr[j]) {
        temp[k++] = arr[i++];
      } else {
        temp[k++] = arr[j++];
        inv += (mid - i);
      }
    }
    while (i < mid) {
      temp[k++] = arr[i++];
    }
    while (j <= right) {
      temp[k++] = arr[j++];
    }
    for (i = left; i <= right; i++) {
      arr[i] = temp[i];
    }
    return inv;
  }

  public static int frequency(int[] arr, int key) {
    int ret = 0;
    for (int i = 0; i < arr.length; i++) {
      if (key == arr[i]) {
        ++ret;
      }
    }
    return ret;
  }

  public static <T> void reverse(T[] arr, int from, int to) {
    int i = from;
    int j = to;
    while (i < j) {
      T temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
      i++;
      j--;
    }
  }

  public static void reverse(char[] arr, int from, int to) {
    int i = from;
    int j = to;
    while (i < j) {
      char temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
      i++;
      j--;
    }
  }

  public static <T> void initialize(T[] arr, Supplier<T> f) {
    for (int i = 0; i < arr.length; i++) {
      arr[i] = f.get();
    }
  }

  public static int frequency(long[] arr, int key) {
    int ret = 0;
    for (int i = 0; i < arr.length; i++) {
      if (key == arr[i]) {
        ++ret;
      }
    }
    return ret;
  }

  public static int[] frequency(char[] arr) {
    return frequency(arr, 26);
  }

  public static int[] frequency(char[] arr, int size) {
    int[] freq = new int[size];
    for (int i = 0; i < arr.length; i++) {
      freq[arr[i] - 'a']++;
    }
    return freq;
  }

  public static long sum(int[] arr) {
    long ret = 0;
    for (int i = 0; i < arr.length; i++) {
      ret += arr[i];
    }
    return ret;
  }

  public static long sum(long[] arr) {
    long ret = 0;
    for (int i = 0; i < arr.length; i++) {
      ret += arr[i];
    }
    return ret;
  }

  public static int[] countingSort(int[] arr, int max) {
    int[] freq = new int[max + 1];
    for (int i = 0; i < arr.length; i++) {
      freq[arr[i]]++;
    }
    int[] ret = new int[arr.length];
    int j = 0;
    for (int i = 0; i < freq.length; i++) {
      if (freq[i] > 0) {
        for (int k = 0; k < freq[i]; k++) {
          ret[j++] = i;
        }
      }
    }
    return ret;
  }

  public static boolean nextPermutation(int[] array) {
    int i = array.length - 1;
    while (i > 0 && array[i - 1] >= array[i]) {
      i--;
    }
    if (i <= 0) {
      return false;
    }
    int j = array.length - 1;
    while (array[j] <= array[i - 1]) {
      j--;
    }
    int temp = array[i - 1];
    array[i - 1] = array[j];
    array[j] = temp;
    j = array.length - 1;
    while (i < j) {
      temp = array[i];
      array[i] = array[j];
      array[j] = temp;
      i++;
      j--;
    }
    return true;
  }

  public static boolean nextPermutation(char[] array) {
    int i = array.length - 1;
    while (i > 0 && array[i - 1] >= array[i]) {
      i--;
    }
    if (i <= 0) {
      return false;
    }
    int j = array.length - 1;
    while (array[j] <= array[i - 1]) {
      j--;
    }
    char temp = array[i - 1];
    array[i - 1] = array[j];
    array[j] = temp;
    j = array.length - 1;
    while (i < j) {
      temp = array[i];
      array[i] = array[j];
      array[j] = temp;
      i++;
      j--;
    }
    return true;
  }

  public static boolean nextPermutation(long[] array) {
    int i = array.length - 1;
    while (i > 0 && array[i - 1] >= array[i]) {
      i--;
    }
    if (i <= 0) {
      return false;
    }
    int j = array.length - 1;
    while (array[j] <= array[i - 1]) {
      j--;
    }
    long temp = array[i - 1];
    array[i - 1] = array[j];
    array[j] = temp;
    j = array.length - 1;
    while (i < j) {
      temp = array[i];
      array[i] = array[j];
      array[j] = temp;
      i++;
      j--;
    }
    return true;
  }

  static Random rnd = new Random(1);

  public static void qSort(int[] a, int low, int high) {
    if (low >= high) {
      return;
    }
    int separator = a[low + rnd.nextInt(high - low + 1)];
    int i = low;
    int j = high;
    do {
      while (a[i] < separator) {
        ++i;
      }
      while (a[j] > separator) {
        --j;
      }
      if (i > j) {
        break;
      }
      int t = a[i];
      a[i] = a[j];
      a[j] = t;
      ++i;
      --j;
    } while (i <= j);
    qSort(a, low, j);
    qSort(a, i, high);
  }

  public static void mergeSort(int[] a, int low, int high) {
    if (high - low < 2) {
      return;
    }
    int mid = (low + high) >>> 1;
    mergeSort(a, low, mid);
    mergeSort(a, mid, high);
    int[] b = Arrays.copyOfRange(a, low, mid);
    for (int i = low, j = mid, k = 0; k < b.length; i++) {
      if (j == high || b[k] <= a[j]) {
        a[i] = b[k++];
      } else {
        a[i] = a[j++];
      }
    }
  }

  public static void mergeSort2(int[] a, int low, int high) {
    int size = high - low;
    if (size < 2) {
      return;
    }
    int mid = (low + high) >>> 1;
    mergeSort2(a, low, mid);
    mergeSort2(a, mid, high);
    int[] b = new int[size];
    int i = low;
    int j = mid;
    for (int k = 0; k < size; k++) {
      if (i < mid && (j == high || a[i] <= a[j])) {
        b[k] = a[i++];
      } else {
        b[k] = a[j++];
      }
    }
    System.arraycopy(b, 0, a, low, size);
  }

  public static void inPlaceMergeSort(int[] a, int low, int high) {
    if (low < high - 1) {
      int mid = (low + high) >>> 1;
      mergeSort(a, low, mid);
      mergeSort(a, mid, high);
      inPlaceMerge(a, low, mid, high);
    }
  }

  static void inPlaceMerge(int[] a, int from, int mid, int to) {
    if (from >= mid || mid >= to) {
      return;
    }
    if (to - from == 2) {
      if (a[from] > a[mid]) {
        swap(a, from, mid);
      }
      return;
    }

    final int firstCut;
    final int secondCut;

    if (mid - from > to - mid) {
      firstCut = from + (mid - from) / 2;
      secondCut = binarySearchFirstTrue(i -> a[i] >= a[firstCut], mid, to);
    } else {
      secondCut = mid + (to - mid) / 2;
      firstCut = binarySearchFirstTrue(i -> a[i] > a[secondCut], from, mid);
    }

    if (mid != firstCut && mid != secondCut) {
      rotate(a, firstCut, mid, secondCut);
    }

    mid = firstCut + (secondCut - mid);
    inPlaceMerge(a, from, firstCut, mid);
    inPlaceMerge(a, mid, secondCut, to);
  }

  public static void swap(int[] a, int i, int j) {
    int t = a[j];
    a[j] = a[i];
    a[i] = t;
  }

  public static void swap(char[] a, int i, int j) {
    char
        t = a[j];
    a[j] = a[i];
    a[i] = t;
  }

  static void rotate(int[] a, int first, int middle, int last) {
    int next = middle;
    while (first != next) {
      swap(a, first++, next++);
      if (next == last) {
        next = middle;
      } else if (first == middle) {
        middle = next;
      }
    }
  }

  public static int binarySearchFirstTrue(IntPredicate predicate, int fromInclusive,
      int toExclusive) {
    int lo = fromInclusive - 1;
    int hi = toExclusive;
    while (lo < hi - 1) {
      int mid = (lo + hi) >>> 1;
      if (!predicate.test(mid)) {
        lo = mid;
      } else {
        hi = mid;
      }
    }
    return hi;
  }
  
  public static <T> int binarySearch(T[] arr, int from, int to, Predicate<T> predicate) {
    int lo = from, hi = to;
    int match = -1;
    while (lo <= hi) {
      int mid = (lo + hi) >>> 1;
      while (lo <= hi) {
        if (predicate.test(arr[mid])) {
          match = mid;
          hi = mid - 1;
        } else {
          lo = mid + 1;
        }
      }
    }
    return match;
  }

  public static <T> int binarySearch(T[] arr, Predicate<T> predicate) {
    return binarySearch(arr, 0, arr.length - 1, predicate);
  }

  public static void heapSort(int[] a) {
    int n = a.length;
    for (int i = n / 2 - 1; i >= 0; i--) {
      pushDown(a, i, n);
    }
    while (n > 1) {
      swap(a, 0, n - 1);
      pushDown(a, 0, --n);
    }
  }

  static void pushDown(int[] h, int pos, int size) {
    while (true) {
      int child = 2 * pos + 1;
      if (child >= size) {
        break;
      }
      if (child + 1 < size && h[child + 1] > h[child]) {
        child++;
      }
      if (h[pos] >= h[child]) {
        break;
      }
      swap(h, pos, child);
      pos = child;
    }
  }

  public static void bubbleSort(int[] a) {
    for (int i = 0; i + 1 < a.length; i++) {
      for (int j = 0; j + 1 < a.length; j++) {
        if (a[j] > a[j + 1]) {
          swap(a, j, j + 1);
        }
      }
    }
  }

  public static void selectionSort(int[] a) {
    int n = a.length;
    int[] p = new int[n];
    for (int i = 0; i < n; i++) {
      p[i] = i;
    }
    for (int i = 0; i < n - 1; i++) {
      for (int j = i + 1; j < n; j++) {
        if (a[p[i]] > a[p[j]]) {
          swap(p, i, j);
        }
      }
    }
    int[] b = a.clone();
    for (int i = 0; i < n; i++) {
      a[i] = b[p[i]];
    }
  }

  public static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
      for (int j = i; j > 0; j--) {
        if (a[j - 1] > a[j]) {
          swap(a, j - 1, j);
        }
      }
    }
  }

  public static void countingSort(int[] a) {
    int max = 0;
    for (int x : a) {
      max = Math.max(max, x);
    }
    int[] cnt = new int[max + 1];
    for (int x : a) {
      ++cnt[x];
    }
    for (int i = 1; i < cnt.length; i++) {
      cnt[i] += cnt[i - 1];
    }
    int n = a.length;
    int[] b = new int[n];
    for (int i = 0; i < n; i++) {
      b[--cnt[a[i]]] = a[i];
    }
    System.arraycopy(b, 0, a, 0, n);
  }


  public static void sort(int[] arr) {
    int n = arr.length;
    Random r = new Random();
    for (int i = 0; i < n; i++) {
      int p = r.nextInt(n + 1);
      if (p < n) {
        int temp = arr[i];
        arr[i] = arr[p];
        arr[p] = temp;
      }
    }
    Arrays.sort(arr);
  }

  public static void sort(long[] arr) {
    int n = arr.length;
    Random r = new Random();
    for (int i = 0; i < n; i++) {
      int p = r.nextInt(n + 1);
      if (p < n) {
        long temp = arr[i];
        arr[i] = arr[p];
        arr[p] = temp;
      }
    }
    Arrays.sort(arr);
  }

  public static int[] frequencyArray(int[] arr, int mx) {
    int[] f = new int[mx + 1];
    for (int c : arr) {
      f[c]++;
    }
    return f;
  }

  public static void fillMatrix(double[][] mat, double val) {
    for (double[] array : mat) {
      Arrays.fill(array, val);
    }
  }

  public static <T> void fillMatrix(T[][] mat, T val) {
    for (T[] array : mat) {
      Arrays.fill(array, val);
    }
  }

  public static void fillMatrix(int[][] mat, int val) {
    for (int[] array : mat) {
      Arrays.fill(array, val);
    }
  }

  public static void fillMatrix(long[][] mat, long val) {
    for (long[] array : mat) {
      Arrays.fill(array, val);
    }
  }

  public static void fillMatrix(boolean[][] mat, boolean val) {
    for (boolean[] array : mat) {
      Arrays.fill(array, val);
    }
  }

  public static void fillMatrix(char[][] mat, char c) {
    for (char[] cc : mat) {
      Arrays.fill(cc, c);
    }

  }

  public static int indexOfMax(int[] dist) {
    int max = dist[0];
    int index = 0;
    for (int i = 0; i < dist.length; i++) {
      if (dist[i] > max) {
        index = i;
        max = dist[i];
      }
    }
    return index;
  }

  public static int[][] copy(int[][] g) {
    if (g.length == 0) {
      return new int[0][];
    }
    int[][] ret = new int[g.length][];
    for (int i = 0; i < g.length; ++i) {
      ret[i] = new int[g[i].length];
      for (int j = 0; j < g[i].length; ++j) {
        ret[i][j] = g[i][j];
      }
    }
    return ret;
  }

  public static double[][] copy(double[][] g) {
    if (g.length == 0) {
      return new double[0][];
    }
    double[][] ret = new double[g.length][];
    for (int i = 0; i < g.length; ++i) {
      ret[i] = new double[g[i].length];
      for (int j = 0; j < g[i].length; ++j) {
        ret[i][j] = g[i][j];
      }
    }
    return ret;
  }

  public static long[][] copy(long[][] g) {
    if (g.length == 0) {
      return new long[0][];
    }
    long[][] ret = new long[g.length][];
    for (int i = 0; i < g.length; ++i) {
      ret[i] = new long[g[i].length];
      for (int j = 0; j < g[i].length; ++j) {
        ret[i][j] = g[i][j];
      }
    }
    return ret;
  }

  public static char[][] copy(char[][] g) {
    if (g.length == 0) {
      return new char[0][];
    }
    char[][] ret = new char[g.length][];
    for (int i = 0; i < g.length; ++i) {
      ret[i] = new char[g[i].length];
      for (int j = 0; j < g[i].length; ++j) {
        ret[i][j] = g[i][j];
      }
    }
    return ret;
  }

  public static int[][] createMatrix(int n, int m, int initialValue) {
    int[][] ret = new int[n][m];
    for (int[] a : ret) {
      Arrays.fill(a, initialValue);
    }
    return ret;
  }

  public static long[][] createMatrix(int n, int m, long initialValue) {
    long[][] ret = new long[n][m];
    for (long[] a : ret) {
      Arrays.fill(a, initialValue);
    }
    return ret;
  }

  public static <T> T[] remove(T[] arr, int index) {
    int length = arr.length;
    if (index < 0 || index > length) {
      throw new ArrayIndexOutOfBoundsException(
          index + " is bigger than the length of the array " + length);
    }
    Object arrObject = arr;
    Object resultArray = Array.newInstance(arrObject.getClass().getComponentType(), length - 1);
    System.arraycopy(arrObject, 0, resultArray, 0, index);
    if (index < length - 1) {
      System.arraycopy(arrObject, index + 1, resultArray, index, length - index - 1);
    }
    return (T[]) resultArray;
  }

  public static int[] distinct(int[] arr) {
    Set<Integer> set = new HashSet<>(arr.length / 2);
    for (int i = 0; i < arr.length; ++i) {
      set.add(arr[i]);
    }
    int[] result = new int[set.size()];
    int pt = 0;
    for (int val : set) {
      result[pt++] = val;
    }
    return result;
  }

  public <T> HashMap<T, Integer> frequencyMap(T[] arr) {
    HashMap<T, Integer> map = new HashMap<>();
    for (T el : arr) {
      map.merge(el, 1, Integer::sum);
    }
    return map;
  }

  public static void reduceBy(int[] arr, int val) {
    for (int i = 0; i < arr.length; i++) {
      arr[i] -= val;
    }
  }

  public static void reduceByOne(int[] arr) {
    reduceBy(arr, 1);
  }


  public static void reduceBy(long[] arr, long val) {
    for (int i = 0; i < arr.length; i++) {
      arr[i] -= val;
    }
  }

  public static void reduceByOne(long[] arr) {
    reduceBy(arr, 1);
  }

  public static int[] unique(int[] arr) {
    int n = arr.length;
    Set<Integer> set = new HashSet<>();
    int[] ret = new int[n];
    int pt = 0;
    for (int i = 0; i < arr.length; i++) {
      if (set.add(arr[i])) {
        ret[pt++] = arr[i];
      }
    }
    return Arrays.copyOf(ret, pt);
  }

  public static int[] prefixSum(int[] arr) {
    int[] acc = new int[arr.length + 1];
    for (int i = 1; i <= arr.length; ++i) {
      acc[i] = acc[i - 1] + arr[i - 1];
    }
    return acc;
  }

  public static long[] prefixSum(long[] arr) {
    long[] acc = new long[arr.length + 1];
    for (int i = 1; i <= arr.length; ++i) {
      acc[i] = acc[i - 1] + arr[i - 1];
    }
    return acc;
  }

  public static int upperBound(int[] arr, int key) {
    int n = arr.length;
    int lo = 0, hi = n - 1;
    int ret = n - 1;
    while (lo <= hi) {
      int mid = (lo + hi) >> 1;
      if (arr[mid] >= key) {
        ret = mid;
        hi = mid - 1;
      } else {
        lo = mid + 1;
      }
    }
    return ret;
  }

  public static int upperBoundStrict(int[] arr, int key) {
    int n = arr.length;
    int lo = 0, hi = n - 1;
    int ret = n - 1;
    while (lo <= hi) {
      int mid = (lo + hi) >> 1;
      if (arr[mid] > key) {
        ret = mid;
        hi = mid - 1;
      } else {
        lo = mid + 1;
      }
    }
    return ret;
  }

  public static int lowerBound(int[] arr, int key) {
    int n = arr.length;
    int lo = 0, hi = n - 1;
    int ret = n - 1;
    while (lo <= hi) {
      int mid = (lo + hi) >> 1;
      if (arr[mid] <= key) {
        ret = mid;
        lo = mid + 1;
      } else {
        hi = mid - 1;
      }
    }
    return ret;
  }

  public static int upperBound(long[] arr, long
      key) {
    int n = arr.length;
    int lo = 0, hi = n - 1;
    int ret = n - 1;
    while (lo <= hi) {
      int mid = (lo + hi) >> 1;
      if (arr[mid] >= key) {
        ret = mid;
        hi = mid - 1;
      } else {
        lo = mid + 1;
      }
    }
    return ret;
  }

  public static int upperBound(int[] arr, int from, int to, int key) {
    int n = arr.length;
    int lo = from, hi = to;
    int ret = to;
    while (lo <= hi) {
      int mid = (lo + hi) >> 1;
      if (arr[mid] >= key) {
        ret = mid;
        hi = mid - 1;
      } else {
        lo = mid + 1;
      }
    }
    return ret;
  }

  public static int upperBound(long[] arr, int from, int to, long key) {
    int n = arr.length;
    int lo = from, hi = to;
    int ret = to;
    while (lo <= hi) {
      int mid = (lo + hi) >> 1;
      if (arr[mid] >= key) {
        ret = mid;
        hi = mid - 1;
      } else {
        lo = mid + 1;
      }
    }
    return ret;
  }

  public static int upperBound(double[] arr, int from, int to, double key) {
    int n = arr.length;
    int lo = from, hi = to;
    int ret = to;
    while (lo <= hi) {
      int mid = (lo + hi) >> 1;
      if (arr[mid] >= key) {
        ret = mid;
        hi = mid - 1;
      } else {
        lo = mid + 1;
      }
    }
    return ret;
  }

  public static CountingMap<Integer> compressMap(int[] arr) {
    int n = arr.length;
    int pt = 1;
    CountingMap<Integer> mp = new CountingMap<>();
    int[] copy = arr.clone();
    ArrayUtils.sort(copy);
    for (int i = 0; i < n; i++) {
      if (!mp.containsKey(copy[i])) {
        mp.put(copy[i], pt++);
      }
    }
    return mp;
  }

  public static int[] compress(int[] arr) {
    int n = arr.length;
    int[] copy = arr.clone();
    ArrayUtils.sort(copy);
    int[] ret = new int[n];
    for (int i = 0; i < n; ++i) {
      ret[i] = Arrays.binarySearch(copy, arr[i]);
    }
    return ret;
  }

  public static int[] createArray(int count, int value) {
    int[] array = new int[count];
    Arrays.fill(array, value);
    return array;
  }

  public static long[] createArray(int count, long value) {
    long[] array = new long[count];
    Arrays.fill(array, value);
    return array;
  }

  public static boolean[] createArray(int count, boolean value) {
    boolean[] array = new boolean[count];
    Arrays.fill(array, value);
    return array;
  }

  public static int maxOf(int... arr) {
    int mx = arr[0];
    for (int other : arr) {
      mx = Math.max(mx, other);
    }
    return mx;
  }

  public static <T> void fill(T[] arr, Supplier<T> factory) {
    for (int i = 0; i < arr.length; ++i) {
      arr[i] = factory.get();
    }
  }

  public static <T> void fill(T[] arr, Function<Integer, T> factory) {
    for (int i = 0; i < arr.length; ++i) {
      arr[i] = factory.apply(i);
    }
  }

  public static void transform(int[] arr, Function<Integer, Integer> transformer) {
    for (int i = 0; i < arr.length; ++i) {
      arr[i] = transformer.apply(arr[i]);
    }
  }

  public static int[] flattenList(List<Integer> list) {
    int[] arr = new int[list.size()];
    for (int i = 0; i < arr.length; ++i) {
      arr[i] = list.get(i);
    }
    return arr;
  }

  public static <T> int firstIndexMatching(List<T> list, Predicate<T> test) {
    for (int i = 0; i < list.size(); ++i) {
      if (test.test(list.get(i))) {
        return i;
      }
    }
    return -1;
  }

  public static int firstIndexMatching(int[] val, Predicate<Integer> test) {
    for (int i = 0; i < val.length; ++i) {
      if (test.test(val[i])) {
        return i;
      }
    }
    return -1;
  }

  public static int firstIndexMatching(long[] val, Predicate<Long> test) {
    for (int i = 0; i < val.length; ++i) {
      if (test.test(val[i])) {
        return i;
      }
    }
    return -1;
  }

}