content: /*
   * 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.util.ImmutableNullableList;
  
  import com.google.common.collect.ImmutableList;
  import com.google.common.collect.ImmutableMap;
  
  import org.checkerframework.checker.nullness.qual.NonNull;
  import org.checkerframework.checker.nullness.qual.Nullable;
  import org.checkerframework.checker.nullness.qual.PolyNull;
  
  import java.util.AbstractList;
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.Collections;
  import java.util.Iterator;
  import java.util.List;
  import java.util.Map;
  import java.util.Objects;
  import java.util.RandomAccess;
  
  import static org.apache.calcite.linq4j.Nullness.castNonNull;
  
  /**
   * Space-efficient, comparable, immutable lists.
   */
  public class FlatLists {
    private FlatLists() {
    }
  
    public static final ComparableEmptyList COMPARABLE_EMPTY_LIST =
        new ComparableEmptyList();
  
    /** Creates a flat list with 0 elements. */
    public static <T> ComparableList<T> of() {
      //noinspection unchecked
      return COMPARABLE_EMPTY_LIST;
    }
  
    /** Creates a flat list with 1 element. */
    public static <T> List<T> of(T t0) {
      return new Flat1List<>(t0);
    }
  
    /** Creates a flat list with 2 elements. */
    public static <T> List<T> of(T t0, T t1) {
      return new Flat2List<>(t0, t1);
    }
  
    /** Creates a flat list with 3 elements. */
    public static <T> List<T> of(T t0, T t1, T t2) {
      return new Flat3List<>(t0, t1, t2);
    }
  
    /** Creates a flat list with 4 elements. */
    public static <T> List<T> of(T t0, T t1, T t2, T t3) {
      return new Flat4List<>(t0, t1, t2, t3);
    }
  
    /** Creates a flat list with 6 elements. */
    public static <T> List<T> of(T t0, T t1, T t2, T t3, T t4) {
      return new Flat5List<>(t0, t1, t2, t3, t4);
    }
  
    /** Creates a flat list with 6 elements. */
    public static <T> List<T> of(T t0, T t1, T t2, T t3, T t4, T t5) {
      return new Flat6List<>(t0, t1, t2, t3, t4, t5);
    }
  
    /**
     * Creates a memory-, CPU- and cache-efficient immutable list.
     *
     * @param t Array of members of list
     * @param <T> Element type
     * @return List containing the given members
     */
    public static <T extends Comparable> List<T> of(T... t) {
      return flatList_(t, false);
    }
  
    /**
     * Creates a memory-, CPU- and cache-efficient immutable list,
     * always copying the contents.
     *
     * @param t Array of members of list
     * @param <T> Element type
     * @return List containing the given members
     */
    @Deprecated // to be removed before 2.0
    public static <T> List<T> copy(T... t) {
      return flatListNotComparable(t);
    }
  
    /**
     * Creates a memory-, CPU- and cache-efficient comparable immutable list,
     * always copying the contents.
     *
     * <p>The elements are comparable, and so is the returned list.
     * Elements may be null.
     *
     * @param t Array of members of list
     * @param <T> Element type
     * @return List containing the given members
     */
    public static <T extends Comparable> List<T> copyOf(T... t) {
      return flatList_(t, true);
    }
  
    /**
     * Creates a memory-, CPU- and cache-efficient immutable list,
     * always copying the contents.
     *
     * <p>The elements need not be comparable,
     * and the returned list may not implement {@link Comparable}.
     * Elements may be null.
     *
     * @param t Array of members of list
     * @param <T> Element type
     * @return List containing the given members
     */
    public static <T> List<T> copyOf(T... t) {
      return flatListNotComparable(t);
    }
  
    /**
     * Creates a memory-, CPU- and cache-efficient comparable immutable list,
     * optionally copying the list.
     *
     * @param copy Whether to always copy the list
     * @param t Array of members of list
     * @return List containing the given members
     */
    private static <T extends Comparable> ComparableList<T> flatList_(
        T[] t, boolean copy) {
      switch (t.length) {
      case 0:
        //noinspection unchecked
        return COMPARABLE_EMPTY_LIST;
      case 1:
        return new Flat1List<>(t[0]);
      case 2:
        return new Flat2List<>(t[0], t[1]);
      case 3:
        return new Flat3List<>(t[0], t[1], t[2]);
      case 4:
        return new Flat4List<>(t[0], t[1], t[2], t[3]);
      case 5:
        return new Flat5List<>(t[0], t[1], t[2], t[3], t[4]);
      case 6:
        return new Flat6List<>(t[0], t[1], t[2], t[3], t[4], t[5]);
      default:
        // REVIEW: AbstractList contains a modCount field; we could
        //   write our own implementation and reduce creation overhead a
        //   bit.
        if (copy) {
          return new ComparableListImpl<>(Arrays.asList(t.clone()));
        } else {
          return new ComparableListImpl<>(Arrays.asList(t));
        }
      }
    }
  
    /**
     * Creates a memory-, CPU- and cache-efficient immutable list,
     * always copying the list.
     *
     * @param t Array of members of list
     * @return List containing the given members
     */
    private static <T> List<T> flatListNotComparable(T[] t) {
      switch (t.length) {
      case 0:
        //noinspection unchecked
        return COMPARABLE_EMPTY_LIST;
      case 1:
        return new Flat1List<>(t[0]);
      case 2:
        return new Flat2List<>(t[0], t[1]);
      case 3:
        return new Flat3List<>(t[0], t[1], t[2]);
      case 4:
        return new Flat4List<>(t[0], t[1], t[2], t[3]);
      case 5:
        return new Flat5List<>(t[0], t[1], t[2], t[3], t[4]);
      case 6:
        return new Flat6List<>(t[0], t[1], t[2], t[3], t[4], t[5]);
      default:
        return ImmutableNullableList.copyOf(t);
      }
    }
  
    /**
     * Creates a memory-, CPU- and cache-efficient immutable list from an
     * existing list. The list is always copied.
     *
     * @param t Array of members of list
     * @param <T> Element type
     * @return List containing the given members
     */
    public static <T> List<T> of(List<T> t) {
      return of_(t);
    }
  
    public static <T extends Comparable> ComparableList<T> ofComparable(
        List<T> t) {
      return of_(t);
    }
  
    private static <T> ComparableList<T> of_(List<T> t) {
      switch (t.size()) {
      case 0:
        //noinspection unchecked
        return COMPARABLE_EMPTY_LIST;
      case 1:
        return new Flat1List<>(t.get(0));
      case 2:
        return new Flat2List<>(t.get(0), t.get(1));
      case 3:
        return new Flat3List<>(t.get(0), t.get(1), t.get(2));
      case 4:
        return new Flat4List<>(t.get(0), t.get(1), t.get(2), t.get(3));
      case 5:
        return new Flat5List<>(t.get(0), t.get(1), t.get(2), t.get(3), t.get(4));
      case 6:
        return new Flat6List<>(t.get(0), t.get(1), t.get(2), t.get(3), t.get(4),
            t.get(5));
      default:
        // REVIEW: AbstractList contains a modCount field; we could
        //   write our own implementation and reduce creation overhead a
        //   bit.
        //noinspection unchecked
        return new ComparableListImpl(Arrays.asList(t.toArray()));
      }
    }
  
    /** Returns a list that consists of a given list plus an element. */
    public static <E extends Object> List<E> append(List<E> list, E e) {
      if (list instanceof AbstractFlatList) {
        //noinspection unchecked
        return ((AbstractFlatList) list).append(e);
      }
      final List<E> newList = new ArrayList<>(list);
      newList.add(e);
      return FlatLists.of(newList);
    }
  
    /** Returns a list that consists of a given list plus an element, guaranteed
     * to be an {@link ImmutableList}. */
    public static <E extends Object> ImmutableList<E> append(ImmutableList<E> list, E e) {
      return ImmutableList.<E>builder().addAll(list).add(e).build();
    }
  
    /** Returns a map that consists of a given map plus an (key, value),
     * guaranteed to be an {@link ImmutableMap}. */
    public static <K extends Object, V extends Object> ImmutableMap<K, V> append(
        Map<K, V> map, K k, V v) {
      final ImmutableMap.Builder<K, V> builder = ImmutableMap.builder();
      builder.put(k, v);
      map.forEach((k2, v2) -> {
        if (!k.equals(k2)) {
          builder.put(k2, v2);
        }
      });
      return builder.build();
    }
  
    /** Base class for flat lists.
     *
     * @param <T> element type */
    public abstract static class AbstractFlatList<T>
        extends AbstractImmutableList<T> implements RandomAccess {
      @Override protected final List<T> toList() {
        //noinspection unchecked
        return Arrays.asList((T[]) toArray());
      }
  
      /** Returns a list that consists of a this list's elements plus a given
       * element. */
      public abstract List<T> append(T e);
    }
  
    /**
     * List that stores its one elements in the one members of the class.
     * Unlike {@link java.util.ArrayList} or
     * {@link java.util.Arrays#asList(Object[])} there is
     * no array, only one piece of memory allocated, therefore is very compact
     * and cache and CPU efficient.
     *
     * <p>The list is read-only and cannot be modified or re-sized.
     * The element may be null.
     *
     * <p>The list is created via {@link FlatLists#of}.
     *
     * @param <T> Element type
     */
    protected static class Flat1List<T>
        extends AbstractFlatList<T>
        implements ComparableList<T> {
      private final T t0;
  
      Flat1List(T t0) {
        this.t0 = t0;
      }
  
      @Override public String toString() {
        return "[" + t0 + "]";
      }
  
      @Override public T get(int index) {
        switch (index) {
        case 0:
          return t0;
        default:
          throw new IndexOutOfBoundsException("index " + index);
        }
      }
  
      @Override public int size() {
        return 1;
      }
  
      @Override public Iterator<T> iterator() {
        return Collections.singletonList(t0).iterator();
      }
  
      @Override public boolean equals(@Nullable Object o) {
        if (this == o) {
          return true;
        }
        if (o instanceof Flat1List) {
          Flat1List that = (Flat1List) o;
          return Objects.equals(this.t0, that.t0);
        }
        return o instanceof List
            && ((List) o).size() == 1
            && Objects.equals(t0, ((List) o).get(0));
      }
  
      @Override public int hashCode() {
        int h = 1;
        h = h * 31 + Utilities.hash(t0);
        return h;
      }
  
      @Override public int indexOf(@Nullable Object o) {
        if (o == null) {
          if (t0 == null) {
            return 0;
          }
        } else {
          if (o.equals(t0)) {
            return 0;
          }
        }
        return -1;
      }
  
      @Override public int lastIndexOf(@Nullable Object o) {
        if (o == null) {
          if (t0 == null) {
            return 0;
          }
        } else {
          if (o.equals(t0)) {
            return 0;
          }
        }
        return -1;
      }
  
      @SuppressWarnings({"unchecked" })
      @Override public <T2> @Nullable T2[] toArray(T2 @Nullable [] a) {
        if (castNonNull(a).length < 1) {
          // Make a new array of a's runtime type, but my contents:
          return (T2[]) Arrays.copyOf(toArray(), 1, a.getClass());
        }
        a[0] = (T2) t0;
        return a;
      }
  
      @Override public @PolyNull Object[] toArray(Flat1List<@PolyNull T> this) {
        return new Object[] {castNonNull(t0)};
      }
  
      @Override public int compareTo(List o) {
        return ComparableListImpl.compare((List) this, o);
      }
  
      @Override public List<T> append(T e) {
        return new Flat2List<>(t0, e);
      }
    }
  
    /**
     * List that stores its two elements in the two members of the class.
     * Unlike {@link java.util.ArrayList} or
     * {@link java.util.Arrays#asList(Object[])} there is
     * no array, only one piece of memory allocated, therefore is very compact
     * and cache and CPU efficient.
     *
     * <p>The list is read-only and cannot be modified or re-sized.
     * The elements may be null.
     *
     * <p>The list is created via {@link FlatLists#of}.
     *
     * @param <T> Element type
     */
    protected static class Flat2List<T>
        extends AbstractFlatList<T>
        implements ComparableList<T> {
      private final T t0;
      private final T t1;
  
      Flat2List(T t0, T t1) {
        this.t0 = t0;
        this.t1 = t1;
      }
  
      @Override public String toString() {
        return "[" + t0 + ", " + t1 + "]";
      }
  
      @Override public T get(int index) {
        switch (index) {
        case 0:
          return t0;
        case 1:
          return t1;
        default:
          throw new IndexOutOfBoundsException("index " + index);
        }
      }
  
      @Override public int size() {
        return 2;
      }
  
      @Override public Iterator<T> iterator() {
        return Arrays.asList(t0, t1).iterator();
      }
  
      @Override public boolean equals(@Nullable Object o) {
        if (this == o) {
          return true;
        }
        if (o instanceof Flat2List) {
          Flat2List that = (Flat2List) o;
          return Objects.equals(this.t0, that.t0)
              && Objects.equals(this.t1, that.t1);
        }
        if (o instanceof List) {
          List lo = (List) o;
          return lo.size() == 2 && o.equals(this);
        }
        return false;
      }
  
      @Override public int hashCode() {
        int h = 1;
        h = h * 31 + Utilities.hash(t0);
        h = h * 31 + Utilities.hash(t1);
        return h;
      }
  
      @Override public int indexOf(@Nullable Object o) {
        if (o == null) {
          if (t0 == null) {
            return 0;
          }
          if (t1 == null) {
            return 1;
          }
        } else {
          if (o.equals(t0)) {
            return 0;
          }
          if (o.equals(t1)) {
            return 1;
          }
        }
        return -1;
      }
  
      @Override public int lastIndexOf(@Nullable Object o) {
        if (o == null) {
          if (t1 == null) {
            return 1;
          }
          if (t0 == null) {
            return 0;
          }
        } else {
          if (o.equals(t1)) {
            return 1;
          }
          if (o.equals(t0)) {
            return 0;
          }
        }
        return -1;
      }
  
      @SuppressWarnings({"unchecked" })
      @Override public <T2> @Nullable T2[] toArray(T2 @Nullable [] a) {
        if (castNonNull(a).length < 2) {
          // Make a new array of a's runtime type, but my contents:
          return (T2[]) Arrays.copyOf(toArray(), 2, a.getClass());
        }
        a[0] = (T2) t0;
        a[1] = (T2) t1;
        return a;
      }
  
      @Override public @PolyNull Object[] toArray(Flat2List<@PolyNull T> this) {
        return new Object[] {castNonNull(t0), castNonNull(t1)};
      }
  
      @Override public int compareTo(List o) {
        return ComparableListImpl.compare((List) this, o);
      }
  
      @Override public List<T> append(T e) {
        return new Flat3List<>(t0, t1, e);
      }
    }
  
    /**
     * List that stores its three elements in the three members of the class.
     * Unlike {@link java.util.ArrayList} or
     * {@link java.util.Arrays#asList(Object[])} there is
     * no array, only one piece of memory allocated, therefore is very compact
     * and cache and CPU efficient.
     *
     * <p>The list is read-only, cannot be modified or re-sized.
     * The elements may be null.
     *
     * <p>The list is created via {@link FlatLists#of(java.util.List)}.
     *
     * @param <T> Element type
     */
    protected static class Flat3List<T>
        extends AbstractFlatList<T>
        implements ComparableList<T> {
      private final T t0;
      private final T t1;
      private final T t2;
  
      Flat3List(T t0, T t1, T t2) {
        this.t0 = t0;
        this.t1 = t1;
        this.t2 = t2;
      }
  
      @Override public String toString() {
        return "[" + t0 + ", " + t1 + ", " + t2 + "]";
      }
  
      @Override public T get(int index) {
        switch (index) {
        case 0:
          return t0;
        case 1:
          return t1;
        case 2:
          return t2;
        default:
          throw new IndexOutOfBoundsException("index " + index);
        }
      }
  
      @Override public int size() {
        return 3;
      }
  
      @Override public Iterator<T> iterator() {
        return Arrays.asList(t0, t1, t2).iterator();
      }
  
      @Override public boolean equals(@Nullable Object o) {
        if (this == o) {
          return true;
        }
        if (o instanceof Flat3List) {
          Flat3List that = (Flat3List) o;
          return Objects.equals(this.t0, that.t0)
              && Objects.equals(this.t1, that.t1)
              && Objects.equals(this.t2, that.t2);
        }
        return o instanceof List
            && ((List) o).size() == 3
            && Arrays.asList(t0, t1, t2).equals(o);
      }
  
      @Override public int hashCode() {
        int h = 1;
        h = h * 31 + Utilities.hash(t0);
        h = h * 31 + Utilities.hash(t1);
        h = h * 31 + Utilities.hash(t2);
        return h;
      }
  
      @Override public int indexOf(@Nullable Object o) {
        if (o == null) {
          if (t0 == null) {
            return 0;
          }
          if (t1 == null) {
            return 1;
          }
          if (t2 == null) {
            return 2;
          }
        } else {
          if (o.equals(t0)) {
            return 0;
          }
          if (o.equals(t1)) {
            return 1;
          }
          if (o.equals(t2)) {
            return 2;
          }
        }
        return -1;
      }
  
      @Override public int lastIndexOf(@Nullable Object o) {
        if (o == null) {
          if (t2 == null) {
            return 2;
          }
          if (t1 == null) {
            return 1;
          }
          if (t0 == null) {
            return 0;
          }
        } else {
          if (o.equals(t2)) {
            return 2;
          }
          if (o.equals(t1)) {
            return 1;
          }
          if (o.equals(t0)) {
            return 0;
          }
        }
        return -1;
      }
  
      @SuppressWarnings({"unchecked" })
      @Override public <T2> @Nullable T2[] toArray(T2 @Nullable [] a) {
        if (castNonNull(a).length < 3) {
          // Make a new array of a's runtime type, but my contents:
          return (T2[]) Arrays.copyOf(toArray(), 3, a.getClass());
        }
        a[0] = (T2) t0;
        a[1] = (T2) t1;
        a[2] = (T2) t2;
        return a;
      }
  
      @Override public @PolyNull Object[] toArray(Flat3List<@PolyNull T> this) {
        return new Object[] {castNonNull(t0), castNonNull(t1), castNonNull(t2)};
      }
  
      @Override public int compareTo(List o) {
        return ComparableListImpl.compare((List) this, o);
      }
  
      @Override public List<T> append(T e) {
        return new Flat4List<>(t0, t1, t2, e);
      }
    }
  
    /**
     * List that stores its four elements in the four members of the class.
     * Unlike {@link java.util.ArrayList} or
     * {@link java.util.Arrays#asList(Object[])} there is
     * no array, only one piece of memory allocated, therefore is very compact
     * and cache and CPU efficient.
     *
     * <p>The list is read-only, cannot be modified or re-sized.
     * The elements may be null.
     *
     * <p>The list is created via {@link FlatLists#of(java.util.List)}.
     *
     * @param <T> Element type
     */
    protected static class Flat4List<T>
        extends AbstractFlatList<T>
        implements ComparableList<T> {
      private final T t0;
      private final T t1;
      private final T t2;
      private final T t3;
  
      Flat4List(T t0, T t1, T t2, T t3) {
        this.t0 = t0;
        this.t1 = t1;
        this.t2 = t2;
        this.t3 = t3;
      }
  
      @Override public String toString() {
        return "[" + t0 + ", " + t1 + ", " + t2 + ", " + t3 + "]";
      }
  
      @Override public T get(int index) {
        switch (index) {
        case 0:
          return t0;
        case 1:
          return t1;
        case 2:
          return t2;
        case 3:
          return t3;
        default:
          throw new IndexOutOfBoundsException("index " + index);
        }
      }
  
      @Override public int size() {
        return 4;
      }
  
      @Override public Iterator<T> iterator() {
        return Arrays.asList(t0, t1, t2, t3).iterator();
      }
  
      @Override public boolean equals(@Nullable Object o) {
        if (this == o) {
          return true;
        }
        if (o instanceof Flat4List) {
          Flat4List that = (Flat4List) o;
          return Objects.equals(this.t0, that.t0)
              && Objects.equals(this.t1, that.t1)
              && Objects.equals(this.t2, that.t2)
              && Objects.equals(this.t3, that.t3);
        }
        return o instanceof List
            && ((List) o).size() == 4
            && Arrays.asList(t0, t1, t2, t3).equals(o);
      }
  
      @Override public int hashCode() {
        int h = 1;
        h = h * 31 + Utilities.hash(t0);
        h = h * 31 + Utilities.hash(t1);
        h = h * 31 + Utilities.hash(t2);
        h = h * 31 + Utilities.hash(t3);
        return h;
      }
  
      @Override public int indexOf(@Nullable Object o) {
        if (o == null) {
          if (t0 == null) {
            return 0;
          }
          if (t1 == null) {
            return 1;
          }
          if (t2 == null) {
            return 2;
          }
          if (t3 == null) {
            return 3;
          }
        } else {
          if (o.equals(t0)) {
            return 0;
          }
          if (o.equals(t1)) {
            return 1;
          }
          if (o.equals(t2)) {
            return 2;
          }
          if (o.equals(t3)) {
            return 3;
          }
        }
        return -1;
      }
  
      @Override public int lastIndexOf(@Nullable Object o) {
        if (o == null) {
          if (t3 == null) {
            return 3;
          }
          if (t2 == null) {
            return 2;
          }
          if (t1 == null) {
            return 1;
          }
          if (t0 == null) {
            return 0;
          }
        } else {
          if (o.equals(t3)) {
            return 3;
          }
          if (o.equals(t2)) {
            return 2;
          }
          if (o.equals(t1)) {
            return 1;
          }
          if (o.equals(t0)) {
            return 0;
          }
        }
        return -1;
      }
  
      @SuppressWarnings({"unchecked" })
      @Override public <T2> @Nullable T2[] toArray(T2 @Nullable [] a) {
        if (castNonNull(a).length < 4) {
          // Make a new array of a's runtime type, but my contents:
          return (T2[]) Arrays.copyOf(toArray(), 4, a.getClass());
        }
        a[0] = (T2) t0;
        a[1] = (T2) t1;
        a[2] = (T2) t2;
        a[3] = (T2) t3;
        return a;
      }
  
      @Override public @PolyNull Object[] toArray(Flat4List<@PolyNull T> this) {
        return new Object[] {castNonNull(t0), castNonNull(t1), castNonNull(t2),
            castNonNull(t3)};
      }
  
      @Override public int compareTo(List o) {
        return ComparableListImpl.compare((List) this, o);
      }
  
      @Override public List<T> append(T e) {
        return new Flat5List<>(t0, t1, t2, t3, e);
      }
    }
  
    /**
     * List that stores its five elements in the five members of the class.
     * Unlike {@link java.util.ArrayList} or
     * {@link java.util.Arrays#asList(Object[])} there is
     * no array, only one piece of memory allocated, therefore is very compact
     * and cache and CPU efficient.
     *
     * <p>The list is read-only, cannot be modified or re-sized.
     * The elements may be null.
     *
     * <p>The list is created via {@link FlatLists#of(java.util.List)}.
     *
     * @param <T> Element type
     */
    protected static class Flat5List<T>
        extends AbstractFlatList<T>
        implements ComparableList<T> {
      private final T t0;
      private final T t1;
      private final T t2;
      private final T t3;
      private final T t4;
  
      Flat5List(T t0, T t1, T t2, T t3, T t4) {
        this.t0 = t0;
        this.t1 = t1;
        this.t2 = t2;
        this.t3 = t3;
        this.t4 = t4;
      }
  
      @Override public String toString() {
        return "[" + t0 + ", " + t1 + ", " + t2 + ", " + t3 + ", " + t4 + "]";
      }
  
      @Override public T get(int index) {
        switch (index) {
        case 0:
          return t0;
        case 1:
          return t1;
        case 2:
          return t2;
        case 3:
          return t3;
        case 4:
          return t4;
        default:
          throw new IndexOutOfBoundsException("index " + index);
        }
      }
  
      @Override public int size() {
        return 5;
      }
  
      @Override public Iterator<T> iterator() {
        return Arrays.asList(t0, t1, t2, t3, t4).iterator();
      }
  
      @Override public boolean equals(@Nullable Object o) {
        if (this == o) {
          return true;
        }
        if (o instanceof Flat5List) {
          Flat5List that = (Flat5List) o;
          return Objects.equals(this.t0, that.t0)
              && Objects.equals(this.t1, that.t1)
              && Objects.equals(this.t2, that.t2)
              && Objects.equals(this.t3, that.t3)
              && Objects.equals(this.t4, that.t4);
        }
        return o instanceof List
            && ((List) o).size() == 5
            && Arrays.asList(t0, t1, t2, t3, t4).equals(o);
      }
  
      @Override public int hashCode() {
        int h = 1;
        h = h * 31 + Utilities.hash(t0);
        h = h * 31 + Utilities.hash(t1);
        h = h * 31 + Utilities.hash(t2);
        h = h * 31 + Utilities.hash(t3);
        h = h * 31 + Utilities.hash(t4);
        return h;
      }
  
      @Override public int indexOf(@Nullable Object o) {
        if (o == null) {
          if (t0 == null) {
            return 0;
          }
          if (t1 == null) {
            return 1;
          }
          if (t2 == null) {
            return 2;
          }
          if (t3 == null) {
            return 3;
          }
          if (t4 == null) {
            return 4;
          }
        } else {
          if (o.equals(t0)) {
            return 0;
          }
          if (o.equals(t1)) {
            return 1;
          }
          if (o.equals(t2)) {
            return 2;
          }
          if (o.equals(t3)) {
            return 3;
          }
          if (o.equals(t4)) {
            return 4;
          }
        }
        return -1;
      }
  
      @Override public int lastIndexOf(@Nullable Object o) {
        if (o == null) {
          if (t4 == null) {
            return 4;
          }
          if (t3 == null) {
            return 3;
          }
          if (t2 == null) {
            return 2;
          }
          if (t1 == null) {
            return 1;
          }
          if (t0 == null) {
            return 0;
          }
        } else {
          if (o.equals(t4)) {
            return 4;
          }
          if (o.equals(t3)) {
            return 3;
          }
          if (o.equals(t2)) {
            return 2;
          }
          if (o.equals(t1)) {
            return 1;
          }
          if (o.equals(t0)) {
            return 0;
          }
        }
        return -1;
      }
  
      @SuppressWarnings({"unchecked" })
      @Override public <T2> @Nullable T2[] toArray(T2 @Nullable [] a) {
        if (castNonNull(a).length < 5) {
          // Make a new array of a's runtime type, but my contents:
          return (T2[]) Arrays.copyOf(toArray(), 5, a.getClass());
        }
        a[0] = (T2) t0;
        a[1] = (T2) t1;
        a[2] = (T2) t2;
        a[3] = (T2) t3;
        a[4] = (T2) t4;
        return a;
      }
  
      @Override public @PolyNull Object[] toArray(Flat5List<@PolyNull T> this) {
        return new Object[] {castNonNull(t0), castNonNull(t1), castNonNull(t2),
            castNonNull(t3), castNonNull(t4)};
      }
  
      @Override public int compareTo(List o) {
        return ComparableListImpl.compare((List) this, o);
      }
  
      @Override public List<T> append(T e) {
        return new Flat6List<>(t0, t1, t2, t3, t4, e);
      }
    }
  
    /**
     * List that stores its six elements in the six members of the class.
     * Unlike {@link java.util.ArrayList} or
     * {@link java.util.Arrays#asList(Object[])} there is
     * no array, only one piece of memory allocated, therefore is very compact
     * and cache and CPU efficient.
     *
     * <p>The list is read-only, cannot be modified or re-sized.
     * The elements may be null.
     *
     * <p>The list is created via {@link FlatLists#of(java.util.List)}.
     *
     * @param <T> Element type
     */
    protected static class Flat6List<T>
        extends AbstractFlatList<T>
        implements ComparableList<T> {
      private final T t0;
      private final T t1;
      private final T t2;
      private final T t3;
      private final T t4;
      private final T t5;
  
      Flat6List(T t0, T t1, T t2, T t3, T t4, T t5) {
        this.t0 = t0;
        this.t1 = t1;
        this.t2 = t2;
        this.t3 = t3;
        this.t4 = t4;
        this.t5 = t5;
      }
  
      @Override public String toString() {
        return "[" + t0 + ", " + t1 + ", " + t2 + ", " + t3 + ", " + t4
            + ", " + t5 + "]";
      }
  
      @Override public T get(int index) {
        switch (index) {
        case 0:
          return t0;
        case 1:
          return t1;
        case 2:
          return t2;
        case 3:
          return t3;
        case 4:
          return t4;
        case 5:
          return t5;
        default:
          throw new IndexOutOfBoundsException("index " + index);
        }
      }
  
      @Override public int size() {
        return 6;
      }
  
      @Override public Iterator<T> iterator() {
        return Arrays.asList(t0, t1, t2, t3, t4, t5).iterator();
      }
  
      @Override public boolean equals(@Nullable Object o) {
        if (this == o) {
          return true;
        }
        if (o instanceof Flat6List) {
          Flat6List that = (Flat6List) o;
          return Objects.equals(this.t0, that.t0)
              && Objects.equals(this.t1, that.t1)
              && Objects.equals(this.t2, that.t2)
              && Objects.equals(this.t3, that.t3)
              && Objects.equals(this.t4, that.t4)
              && Objects.equals(this.t5, that.t5);
        }
        return o instanceof List
            && ((List) o).size() == 6
            && Arrays.asList(t0, t1, t2, t3, t4, t5).equals(o);
      }
  
      @Override public int hashCode() {
        int h = 1;
        h = h * 31 + Utilities.hash(t0);
        h = h * 31 + Utilities.hash(t1);
        h = h * 31 + Utilities.hash(t2);
        h = h * 31 + Utilities.hash(t3);
        h = h * 31 + Utilities.hash(t4);
        h = h * 31 + Utilities.hash(t5);
        return h;
      }
  
      @Override public int indexOf(@Nullable Object o) {
        if (o == null) {
          if (t0 == null) {
            return 0;
          }
          if (t1 == null) {
            return 1;
          }
          if (t2 == null) {
            return 2;
          }
          if (t3 == null) {
            return 3;
          }
          if (t4 == null) {
            return 4;
          }
          if (t5 == null) {
            return 5;
          }
        } else {
          if (o.equals(t0)) {
            return 0;
          }
          if (o.equals(t1)) {
            return 1;
          }
          if (o.equals(t2)) {
            return 2;
          }
          if (o.equals(t3)) {
            return 3;
          }
          if (o.equals(t4)) {
            return 4;
          }
          if (o.equals(t5)) {
            return 5;
          }
        }
        return -1;
      }
  
      @Override public int lastIndexOf(@Nullable Object o) {
        if (o == null) {
          if (t5 == null) {
            return 5;
          }
          if (t4 == null) {
            return 4;
          }
          if (t3 == null) {
            return 3;
          }
          if (t2 == null) {
            return 2;
          }
          if (t1 == null) {
            return 1;
          }
          if (t0 == null) {
            return 0;
          }
        } else {
          if (o.equals(t5)) {
            return 5;
          }
          if (o.equals(t4)) {
            return 4;
          }
          if (o.equals(t3)) {
            return 3;
          }
          if (o.equals(t2)) {
            return 2;
          }
          if (o.equals(t1)) {
            return 1;
          }
          if (o.equals(t0)) {
            return 0;
          }
        }
        return -1;
      }
  
      @SuppressWarnings({"unchecked" })
      @Override public <T2> @Nullable T2[] toArray(T2 @Nullable [] a) {
        if (castNonNull(a).length < 6) {
          // Make a new array of a's runtime type, but my contents:
          return (T2[]) Arrays.copyOf(toArray(), 6, a.getClass());
        }
        a[0] = (T2) t0;
        a[1] = (T2) t1;
        a[2] = (T2) t2;
        a[3] = (T2) t3;
        a[4] = (T2) t4;
        a[5] = (T2) t5;
        return a;
      }
  
      @Override public @PolyNull Object[] toArray(Flat6List<@PolyNull T> this) {
        return new Object[] {castNonNull(t0), castNonNull(t1), castNonNull(t2),
            castNonNull(t3), castNonNull(t4), castNonNull(t5)};
      }
  
      @Override public int compareTo(List o) {
        return ComparableListImpl.compare((List) this, o);
      }
  
      @Override public List<T> append(T e) {
        return ImmutableNullableList.of(t0, t1, t2, t3, t5, e);
      }
    }
  
    /** Empty list that implements the {@link Comparable} interface.
     *
     * @param <T> element type */
    private static class ComparableEmptyList<T>
        extends AbstractList<T>
        implements ComparableList<T> {
      private ComparableEmptyList() {
      }
  
      @Override public T get(int index) {
        throw new IndexOutOfBoundsException();
      }
  
      @Override public int hashCode() {
        return 1; // same as Collections.emptyList()
      }
  
      @Override public boolean equals(@Nullable Object o) {
        return o == this
            || o instanceof List && ((List) o).isEmpty();
      }
  
      @Override public int size() {
        return 0;
      }
  
      @Override public int compareTo(List o) {
        return ComparableListImpl.compare((List) this, o);
      }
    }
  
    /** List that is also comparable.
     *
     * <p>You can create an instance whose type
     * parameter {@code T} does not extend {@link Comparable}, but you will get a
     * {@link ClassCastException} at runtime when you call
     * {@link #compareTo(Object)} if the elements of the list do not implement
     * {@code Comparable}.
     *
     * @param <T> element type
     */
    @SuppressWarnings("ComparableType")
    public interface ComparableList<T> extends List<T>, Comparable<List> {
    }
  
    /** Wrapper around a list that makes it implement the {@link Comparable}
     * interface using lexical ordering. The elements must be comparable.
     *
     * @param <T> element type */
    static class ComparableListImpl<T extends Comparable<T>>
        extends AbstractList<T>
        implements ComparableList<T> {
      private final List<T> list;
  
      protected ComparableListImpl(List<T> list) {
        this.list = list;
      }
  
      @Override public T get(int index) {
        return list.get(index);
      }
  
      @Override public int size() {
        return list.size();
      }
  
      @Override @NonNull public Object[] toArray(@NonNull ComparableListImpl<T> this) {
        return this.list.toArray();
      }
  
      @Override public int compareTo(List o) {
        return compare(list, o);
      }
  
      static <T extends Comparable<T>> int compare(List<T> list0, List<T> list1) {
        final int size0 = list0.size();
        final int size1 = list1.size();
        if (size1 == size0) {
          return compare(list0, list1, size0);
        }
        final int c = compare(list0, list1, Math.min(size0, size1));
        if (c != 0) {
          return c;
        }
        return size0 - size1;
      }
  
      static <T extends Comparable<T>> int compare(List<T> list0, List<T> list1,
          int size) {
        for (int i = 0; i < size; i++) {
          Comparable o0 = list0.get(i);
          Comparable o1 = list1.get(i);
          int c = compare(o0, o1);
          if (c != 0) {
            return c;
          }
        }
        return 0;
      }
  
      static <T extends Comparable<T>> int compare(T a, T b) {
        if (a == b) {
          return 0;
        }
        if (a == null) {
          return -1;
        }
        if (b == null) {
          return 1;
        }
        return a.compareTo(b);
      }
    }
  
  }
  