PairLists.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to you under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.calcite.runtime;

import org.apache.calcite.linq4j.function.Functions;

import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMap;
import com.google.errorprone.annotations.CanIgnoreReturnValue;

import org.checkerframework.checker.nullness.qual.NonNull;
import org.checkerframework.checker.nullness.qual.Nullable;

import java.util.AbstractList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.RandomAccess;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.BiPredicate;

import static org.apache.calcite.linq4j.Nullness.castNonNull;
import static org.apache.calcite.linq4j.Nullness.castNonNullArray;
import static org.apache.calcite.linq4j.Nullness.castNonNullList;

import static java.util.Objects.requireNonNull;

/** Various implementations of {@link PairList}. */
class PairLists {
  static final ImmutablePairList<Object, Object> EMPTY =
      new EmptyImmutablePairList<>();

  private PairLists() {
  }

  @SuppressWarnings("unchecked")
  static <T, U> ImmutablePairList<T, U> immutableBackedBy(
      List<Object> list) {
    switch (list.size()) {
    case 0:
      return ImmutablePairList.of();
    case 2:
      return new SingletonImmutablePairList<>(
          castNonNull((T) list.get(0)),
          castNonNull((U) list.get(1)));
    default:
      return new ArrayImmutablePairList<>(list.toArray());
    }
  }

  @CanIgnoreReturnValue
  static @NonNull Object[] checkElementsNotNull(@Nullable Object... elements) {
    for (int i = 0; i < elements.length; i++) {
      checkElementNotNull(i, elements[i]);
    }
    return castNonNullArray(elements);
  }

  static void checkElementNotNull(int i, @Nullable Object element) {
    if (element == null) {
      throw new NullPointerException((i % 2 == 0 ? "key" : "value")
          + " at index " + (i / 2));
    }
  }

  /** Base class for all implementations of PairList.
   *
   * @param <T> First type
   * @param <U> Second type
   */
  abstract static class AbstractPairList<T, U>
      extends AbstractList<Map.Entry<T, U>>
      implements PairList<T, U> {
    /** Returns a list containing the alternating left and right elements
     * of each pair. */
    abstract List<@Nullable Object> backingList();

    @Override public abstract PairList<T, U> subList(int fromIndex,
        int toIndex);

    static void subListRangeCheck(int fromIndex, int toIndex, int size) {
      if (fromIndex < 0) {
        throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
      }
      if (toIndex > size) {
        throw new IndexOutOfBoundsException("toIndex = " + toIndex);
      }
      if (fromIndex > toIndex) {
        throw new IllegalArgumentException("fromIndex(" + fromIndex
            + ") > toIndex(" + toIndex + ")");
      }
    }
  }

  /** Mutable version of {@link PairList}.
   *
   * @param <T> First type
   * @param <U> Second type
   */
  static class MutablePairList<T, U> extends AbstractPairList<T, U> {
    final List<@Nullable Object> list;

    MutablePairList(List<@Nullable Object> list) {
      this.list = list;
    }

    @Override List<@Nullable Object> backingList() {
      return list;
    }

    @Override public void clear() {
      list.clear();
    }

    @Override public int size() {
      return list.size() / 2;
    }

    @Override public boolean isEmpty() {
      return list.isEmpty();
    }

    @SuppressWarnings("unchecked")
    @Override public Map.Entry<T, U> get(int index) {
      int x = index * 2;
      return new MapEntry<>((T) list.get(x), (U) list.get(x + 1));
    }

    @SuppressWarnings("unchecked")
    @Override public T left(int index) {
      int x = index * 2;
      return (T) list.get(x);
    }

    @SuppressWarnings("unchecked")
    @Override public U right(int index) {
      int x = index * 2;
      return (U) list.get(x + 1);
    }

    @Override public Map.Entry<T, U> set(int index,
        Map.@Nullable Entry<T, U> entry) {
      if (entry == null) {
        return set(index, castNonNull(null), castNonNull(null));
      }
      return set(index, entry.getKey(), entry.getValue());
    }

    @SuppressWarnings("unchecked")
    @Override public Map.Entry<T, U> set(int index, T t, U u) {
      int x = index * 2;
      T t0 = (T) list.set(x, t);
      U u0 = (U) list.set(x + 1, u);
      return new MapEntry<>(t0, u0);
    }

    @SuppressWarnings("unchecked")
    @Override public Map.Entry<T, U> remove(int index) {
      final int x = index * 2;
      T t = (T) list.remove(x);
      U u = (U) list.remove(x);
      return new MapEntry<>(t, u);
    }

    @SuppressWarnings("RedundantCast")
    @Override public boolean add(Map.Entry<T, U> entry) {
      list.add((Object) entry.getKey());
      list.add((Object) entry.getValue());
      return true;
    }

    @SuppressWarnings("RedundantCast")
    @Override public void add(int index, Map.Entry<T, U> entry) {
      int x = index * 2;
      list.add(x, (Object) entry.getKey());
      list.add(x + 1, (Object) entry.getValue());
    }

    @SuppressWarnings("RedundantCast")
    @Override public void add(T t, U u) {
      list.add((Object) t);
      list.add((Object) u);
    }

    @SuppressWarnings("RedundantCast")
    @Override public void add(int index, T t, U u) {
      int x = index * 2;
      list.add(x, (Object) t);
      list.add(x + 1, (Object) u);
    }

    @Override public boolean addAll(PairList<T, U> list2) {
      return list.addAll(((AbstractPairList<T, U>) list2).backingList());
    }

    @Override public boolean addAll(int index, PairList<T, U> list2) {
      int x = index * 2;
      return list.addAll(x, ((AbstractPairList<T, U>) list2).backingList());
    }

    @SuppressWarnings("unchecked")
    @Override public List<T> leftList() {
      final int size = list.size() / 2;
      return new RandomAccessList<T>() {
        @Override public int size() {
          return size;
        }

        @Override public T get(int index) {
          return (T) list.get(index * 2);
        }
      };
    }

    @SuppressWarnings("unchecked")
    @Override public List<U> rightList() {
      final int size = list.size() / 2;
      return new RandomAccessList<U>() {
        @Override public int size() {
          return size;
        }

        @Override public U get(int index) {
          return (U) list.get(index * 2 + 1);
        }
      };
    }

    @SuppressWarnings("unchecked")
    @Override public void forEach(BiConsumer<T, U> consumer) {
      requireNonNull(consumer, "consumer");
      for (int i = 0; i < list.size();) {
        T t = (T) list.get(i++);
        U u = (U) list.get(i++);
        consumer.accept(t, u);
      }
    }

    @SuppressWarnings("unchecked")
    @Override public void forEachIndexed(IndexedBiConsumer<T, U> consumer) {
      requireNonNull(consumer, "consumer");
      for (int i = 0, j = 0; i < list.size();) {
        T t = (T) list.get(i++);
        U u = (U) list.get(i++);
        consumer.accept(j++, t, u);
      }
    }

    @Override public ImmutableMap<T, U> toImmutableMap() {
      final ImmutableMap.Builder<T, U> b = ImmutableMap.builder();
      forEach((t, u) -> b.put(t, u));
      return b.build();
    }

    @Override public ImmutablePairList<T, U> immutable() {
      return immutableBackedBy(castNonNullList(list));
    }

    @SuppressWarnings("unchecked")
    @Override public <R> List<R> transform(BiFunction<T, U, R> function) {
      return Functions.generate(list.size() / 2, index -> {
        final int x = index * 2;
        final T t = (T) list.get(x);
        final U u = (U) list.get(x + 1);
        return function.apply(t, u);
      });
    }

    @SuppressWarnings("unchecked")
    @Override public <R> ImmutableList<R> transform2(
        BiFunction<T, U, R> function) {
      if (list.isEmpty()) {
        return ImmutableList.of();
      }
      final ImmutableList.Builder<R> builder = ImmutableList.builder();
      for (int i = 0, n = list.size(); i < n;) {
        final T t = (T) list.get(i++);
        final U u = (U) list.get(i++);
        builder.add(function.apply(t, u));
      }
      return builder.build();
    }

    @Override public PairList<T, U> subList(int fromIndex, int toIndex) {
      return new MutablePairList<>(list.subList(fromIndex * 2, toIndex * 2));
    }

    @SuppressWarnings("unchecked")
    @Override public boolean anyMatch(BiPredicate<T, U> predicate) {
      for (int i = 0; i < list.size();) {
        final T t = (T) list.get(i++);
        final U u = (U) list.get(i++);
        if (predicate.test(t, u)) {
          return true;
        }
      }
      return false;
    }

    @SuppressWarnings("unchecked")
    @Override public boolean allMatch(BiPredicate<T, U> predicate) {
      for (int i = 0; i < list.size();) {
        final T t = (T) list.get(i++);
        final U u = (U) list.get(i++);
        if (!predicate.test(t, u)) {
          return false;
        }
      }
      return true;
    }

    @SuppressWarnings("unchecked")
    @Override public boolean noMatch(BiPredicate<T, U> predicate) {
      for (int i = 0; i < list.size();) {
        final T t = (T) list.get(i++);
        final U u = (U) list.get(i++);
        if (predicate.test(t, u)) {
          return false;
        }
      }
      return true;
    }

    @Override public void reverse() {
      for (int i = 0, j = list.size() - 2; i < j;) {
        @Nullable Object o = list.get(i);
        list.set(i, list.get(j));
        list.set(j, o);
        o = list.get(i + 1);
        list.set(i + 1, list.get(j + 1));
        list.set(j + 1, o);
        i += 2;
        j -= 2;
      }
    }

    @Override public ImmutablePairList<T, U> reversed() {
      if (size() <= 1) {
        return immutable();
      }
      final ImmutableList.Builder<Object> b = ImmutableList.builder();
      final List<Object> nonNullList = castNonNullList(list);
      for (int j = list.size() - 2; j >= 0;) {
        b.add(nonNullList.get(j));
        b.add(nonNullList.get(j + 1));
        j -= 2;
      }
      return PairLists.immutableBackedBy(b.build());
    }
  }

  /** Empty immutable list of pairs.
   *
   * @param <T> First type
   * @param <U> Second type
   */
  static class EmptyImmutablePairList<T, U>
      extends AbstractPairList<T, U>
      implements ImmutablePairList<T, U> {
    @Override List<@Nullable Object> backingList() {
      return ImmutableList.of();
    }

    @Override public Map.Entry<T, U> get(int index) {
      throw new IndexOutOfBoundsException("Index out of range: " + index);
    }

    @Override public T left(int index) {
      throw new IndexOutOfBoundsException("Index out of range: " + index);
    }

    @Override public U right(int index) {
      throw new IndexOutOfBoundsException("Index out of range: " + index);
    }

    @Override public int size() {
      return 0;
    }

    @Override public List<T> leftList() {
      return ImmutableList.of();
    }

    @Override public List<U> rightList() {
      return ImmutableList.of();
    }

    @Override public void forEach(BiConsumer<T, U> consumer) {
    }

    @Override public void forEachIndexed(IndexedBiConsumer<T, U> consumer) {
    }

    @Override public <R> List<R> transform(BiFunction<T, U, R> function) {
      return ImmutableList.of();
    }

    @Override public <R> ImmutableList<R> transform2(
        BiFunction<T, U, R> function) {
      return ImmutableList.of();
    }

    @Override public ImmutablePairList<T, U> subList(int fromIndex,
        int toIndex) {
      subListRangeCheck(fromIndex, toIndex, size());
      return this;
    }

    @Override public ImmutablePairList<T, U> reversed() {
      return this;
    }

    @Override public boolean anyMatch(BiPredicate<T, U> predicate) {
      return false;
    }

    @Override public boolean allMatch(BiPredicate<T, U> predicate) {
      return true;
    }

    @Override public boolean noMatch(BiPredicate<T, U> predicate) {
      return true;
    }
  }

  /** Immutable list that contains one pair.
   *
   * @param <T> First type
   * @param <U> Second type
   */
  static class SingletonImmutablePairList<T, U>
      extends AbstractPairList<T, U>
      implements ImmutablePairList<T, U> {
    private final T t;
    private final U u;

    SingletonImmutablePairList(T t, U u) {
      this.t = t;
      this.u = u;
      checkElementNotNull(0, t);
      checkElementNotNull(1, u);
    }

    @Override List<@Nullable Object> backingList() {
      return ImmutableList.of(t, u);
    }

    @Override public Map.Entry<T, U> get(int index) {
      if (index != 0) {
        throw new IndexOutOfBoundsException("Index out of range: " + index);
      }
      return new MapEntry<>(t, u);
    }

    @Override public T left(int index) {
      if (index != 0) {
        throw new IndexOutOfBoundsException("Index out of range: " + index);
      }
      return t;
    }

    @Override public U right(int index) {
      if (index != 0) {
        throw new IndexOutOfBoundsException("Index out of range: " + index);
      }
      return u;
    }

    @Override public int size() {
      return 1;
    }

    @Override public List<T> leftList() {
      return ImmutableList.of(t);
    }

    @Override public List<U> rightList() {
      return ImmutableList.of(u);
    }

    @Override public void forEach(BiConsumer<T, U> consumer) {
      consumer.accept(t, u);
    }

    @Override public void forEachIndexed(IndexedBiConsumer<T, U> consumer) {
      consumer.accept(0, t, u);
    }

    @Override public <R> List<R> transform(BiFunction<T, U, R> function) {
      return ImmutableList.of(function.apply(t, u));
    }

    @Override public <R> ImmutableList<R> transform2(
        BiFunction<T, U, R> function) {
      return ImmutableList.of(function.apply(t, u));
    }

    @Override public ImmutablePairList<T, U> subList(int fromIndex,
        int toIndex) {
      subListRangeCheck(fromIndex, toIndex, size());
      return fromIndex > toIndex
          ? this
          : ImmutablePairList.of();
    }

    @Override public ImmutablePairList<T, U> reversed() {
      return this;
    }

    @Override public boolean anyMatch(BiPredicate<T, U> predicate) {
      return predicate.test(t, u);
    }

    @Override public boolean allMatch(BiPredicate<T, U> predicate) {
      return predicate.test(t, u);
    }

    @Override public boolean noMatch(BiPredicate<T, U> predicate) {
      return !predicate.test(t, u);
    }
  }

  /** Base class for a list that implements {@link RandomAccess}.
   *
   * @param <E> Element type */
  abstract static class RandomAccessList<E>
      extends AbstractList<E> implements RandomAccess {
  }

  /** Immutable list of pairs backed by an array.
   *
   * @param <T> First type
   * @param <U> Second type
   */
  static class ArrayImmutablePairList<T, U>
      extends AbstractPairList<T, U>
      implements ImmutablePairList<T, U> {
    private final Object[] elements;

    /** Creates an ArrayImmutablePairList.
     *
     * <p>Does not copy the {@code elements} array. Assumes that the caller has
     * made a copy, and will never modify the contents.
     *
     * <p>Assumes that {@code elements} is not null, but checks that none of
     * its elements are null. */
    ArrayImmutablePairList(@Nullable Object[] elements) {
      this.elements = checkElementsNotNull(elements);
    }

    @Override List<@Nullable Object> backingList() {
      return Arrays.asList(elements);
    }

    @SuppressWarnings("unchecked")
    @Override public Map.Entry<T, U> get(int index) {
      int x = index * 2;
      return new MapEntry<>((T) elements[x], (U) elements[x + 1]);
    }

    @SuppressWarnings("unchecked")
    @Override public T left(int index) {
      int x = index * 2;
      return (T) elements[x];
    }

    @SuppressWarnings("unchecked")
    @Override public U right(int index) {
      int x = index * 2;
      return (U) elements[x + 1];
    }

    @Override public int size() {
      return elements.length / 2;
    }

    @Override public List<T> leftList() {
      return new RandomAccessList<T>() {
        @Override public int size() {
          return elements.length / 2;
        }

        @SuppressWarnings("unchecked")
        @Override public T get(int index) {
          return (T) elements[index * 2];
        }
      };
    }

    @Override public List<U> rightList() {
      return new RandomAccessList<U>() {
        @Override public int size() {
          return elements.length / 2;
        }

        @SuppressWarnings("unchecked")
        @Override public U get(int index) {
          return (U) elements[index * 2 + 1];
        }
      };
    }

    @SuppressWarnings("unchecked")
    @Override public void forEach(BiConsumer<T, U> consumer) {
      for (int x = 0; x < elements.length;) {
        T t = (T) elements[x++];
        U u = (U) elements[x++];
        consumer.accept(t, u);
      }
    }

    @SuppressWarnings("unchecked")
    @Override public void forEachIndexed(IndexedBiConsumer<T, U> consumer) {
      for (int x = 0, i = 0; x < elements.length;) {
        T t = (T) elements[x++];
        U u = (U) elements[x++];
        consumer.accept(i++, t, u);
      }
    }

    @SuppressWarnings("unchecked")
    @Override public <R> List<R> transform(BiFunction<T, U, R> function) {
      return Functions.generate(elements.length / 2, index -> {
        final int x = index * 2;
        final T t = (T) elements[x];
        final U u = (U) elements[x + 1];
        return function.apply(t, u);
      });
    }

    @SuppressWarnings("unchecked")
    @Override public <R> ImmutableList<R> transform2(
        BiFunction<T, U, R> function) {
      final ImmutableList.Builder<R> builder = ImmutableList.builder();
      for (int i = 0; i < elements.length;) {
        final T t = (T) elements[i++];
        final U u = (U) elements[i++];
        builder.add(function.apply(t, u));
      }
      return builder.build();
    }

    @SuppressWarnings("unchecked")
    @Override public ImmutablePairList<T, U> subList(int fromIndex,
        int toIndex) {
      subListRangeCheck(fromIndex, toIndex, size());
      switch (toIndex - fromIndex) {
      case 0:
        return ImmutablePairList.of();
      case 2:
        return new SingletonImmutablePairList<>((T) elements[fromIndex * 2],
            (U) elements[fromIndex * 2 + 1]);
      default:
        return new ArrayImmutablePairList<>(
            Arrays.copyOfRange(elements, fromIndex * 2,
                toIndex * 2 - fromIndex * 2));
      }
    }

    @Override public ImmutablePairList<T, U> reversed() {
      if (size() <= 1) {
        return immutable();
      }
      final Object[] elements2 = new Object[elements.length];
      for (int j = elements.length - 2, i = 0; j >= 0;) {
        elements2[i++] = elements[j];
        elements2[i++] = elements[j + 1];
        j -= 2;
      }
      return new ArrayImmutablePairList<>(elements2);
    }

    @SuppressWarnings("unchecked")
    @Override public boolean anyMatch(BiPredicate<T, U> predicate) {
      for (int i = 0; i < elements.length;) {
        final T t = (T) elements[i++];
        final U u = (U) elements[i++];
        if (predicate.test(t, u)) {
          return true;
        }
      }
      return false;
    }

    @SuppressWarnings("unchecked")
    @Override public boolean allMatch(BiPredicate<T, U> predicate) {
      for (int i = 0; i < elements.length;) {
        final T t = (T) elements[i++];
        final U u = (U) elements[i++];
        if (!predicate.test(t, u)) {
          return false;
        }
      }
      return true;
    }

    @SuppressWarnings("unchecked")
    @Override public boolean noMatch(BiPredicate<T, U> predicate) {
      for (int i = 0; i < elements.length;) {
        final T t = (T) elements[i++];
        final U u = (U) elements[i++];
        if (predicate.test(t, u)) {
          return false;
        }
      }
      return true;
    }
  }
}