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.util;
  
  import org.checkerframework.checker.nullness.qual.Nullable;
  
  import java.util.AbstractSequentialList;
  import java.util.Arrays;
  import java.util.Collection;
  import java.util.LinkedList;
  import java.util.ListIterator;
  import java.util.NoSuchElementException;
  
  import static org.apache.calcite.linq4j.Nullness.castNonNull;
  
  import static java.util.Objects.requireNonNull;
  
  /**
   * Implementation of list similar to {@link LinkedList}, but stores elements
   * in chunks of 32 elements.
   *
   * <p>ArrayList has O(n) insertion and deletion into the middle of the list.
   * ChunkList insertion and deletion are O(1).
   *
   * @param <E> element type
   */
  public class ChunkList<E> extends AbstractSequentialList<E> {
    private static final int HEADER_SIZE = 3;
    private static final int CHUNK_SIZE = 64;
    private static final Integer[] INTEGERS = new Integer[CHUNK_SIZE + 3];
  
    static {
      for (int i = 0; i < INTEGERS.length; i++) {
        INTEGERS[i] = i;
      }
    }
  
    private int size;
    private E @Nullable [] first;
    private E @Nullable [] last;
  
    /**
     * Creates an empty ChunkList.
     */
    public ChunkList() {
    }
  
    /**
     * Creates a ChunkList whose contents are a given Collection.
     */
    public ChunkList(Collection<E> collection) {
      @SuppressWarnings({"method.invocation.invalid", "unused"})
      boolean ignore = addAll(collection);
    }
  
    /**
     * For debugging and testing.
     */
    boolean isValid(boolean fail) {
      if ((first == null) != (last == null)) {
        assert !fail;
        return false;
      }
      if ((first == null) != (size == 0)) {
        assert !fail;
        return false;
      }
      int n = 0;
      for (@SuppressWarnings("unused") E e : this) {
        if (n++ > size) {
          assert !fail;
          return false;
        }
      }
      if (n != size) {
        assert !fail;
        return false;
      }
      E[] prev = null;
      for (E[] chunk = first; chunk != null; chunk = next(chunk)) {
        if (prev(chunk) != prev) {
          assert !fail;
          return false;
        }
        prev = chunk;
        if (occupied(chunk) == 0) {
          assert !fail;
          return false;
        }
      }
      return true;
    }
  
    @Override public ListIterator<E> listIterator(int index) {
      return locate(index);
    }
  
    @Override public int size() {
      return size;
    }
  
    @Override public void clear() {
      // base class method works, but let's optimize
      size = 0;
      first = last = null;
    }
  
    @Override public boolean add(E element) {
      E[] chunk = last;
      int occupied;
      if (chunk == null) {
        //noinspection unchecked
        chunk = first = last = (E[]) new Object[CHUNK_SIZE + HEADER_SIZE];
        occupied = 0;
      } else {
        occupied = occupied(chunk);
        if (occupied == CHUNK_SIZE) {
          //noinspection unchecked
          chunk = (E[]) new Object[CHUNK_SIZE + HEADER_SIZE];
          setNext(requireNonNull(last, "last"), chunk);
          setPrev(chunk, last);
          occupied = 0;
          last = chunk;
        }
      }
      setOccupied(chunk, occupied + 1);
      setElement(chunk, HEADER_SIZE + occupied, element);
      ++size;
      return true;
    }
  
    @Override public void add(int index, E element) {
      if (index == size) {
        add(element);
      } else {
        super.add(index, element);
      }
    }
  
    private static <E> E @Nullable [] prev(E[] chunk) {
      //noinspection unchecked
      return (E @Nullable []) chunk[0];
    }
  
    private static <E> void setPrev(E[] chunk, E @Nullable [] prev) {
      //noinspection unchecked
      chunk[0] = (E) prev;
    }
  
    private static <E> E @Nullable [] next(E[] chunk) {
      //noinspection unchecked
      return (E @Nullable []) chunk[1];
    }
  
    private static <E> void setNext(E[] chunk, E @Nullable [] next) {
      assert chunk != next;
      //noinspection unchecked
      chunk[1] = (E) next;
    }
  
    private static <E> int occupied(E[] chunk) {
      return (Integer) requireNonNull(chunk[2], "chunk[2] (number of occupied entries)");
    }
  
    @SuppressWarnings("unchecked")
    private static <E> void setOccupied(E[] chunk, int size) {
      chunk[2] = (E) INTEGERS[size];
    }
  
    private static <E> E element(E[] chunk, int index) {
      return chunk[index];
    }
  
    private static <E> void setElement(E[] chunk, int index, @Nullable E element) {
      chunk[index] = castNonNull(element);
    }
  
    private ChunkListIterator locate(int index) {
      if (index < 0 || index > size) {
        throw new IndexOutOfBoundsException();
      }
      if (first == null) {
        // Create an iterator positioned before the first element.
        return new ChunkListIterator(null, 0, 0, -1, 0);
      }
      int n = 0;
      for (E[] chunk = first;;) {
        final int occupied = occupied(chunk);
        final int nextN = n + occupied;
        final E[] next = next(chunk);
        if (nextN >= index || next == null) {
          return new ChunkListIterator(chunk, n, index, -1, n + occupied);
        }
        n = nextN;
        chunk = next;
      }
    }
  
    /** Iterator over a {@link ChunkList}. */
    private class ChunkListIterator implements ListIterator<E> {
      private E @Nullable [] chunk;
      /** Offset in the list of the first element of this chunk. */
      private int start;
      /** Offset within current chunk of the next element to return. */
      private int cursor;
      /** Offset within the current chunk of the last element returned. -1 if
       * {@link #next} or {@link #previous()} has not been called. */
      private int lastRet;
      /** Offset of the first unoccupied location in the current chunk. */
      private int end;
  
      ChunkListIterator(E @Nullable [] chunk, int start, int cursor, int lastRet,
          int end) {
        this.chunk = chunk;
        this.start = start;
        this.cursor = cursor;
        this.lastRet = lastRet;
        this.end = end;
      }
  
      private E[] currentChunk() {
        return castNonNull(chunk);
      }
  
      @Override public boolean hasNext() {
        return cursor < size;
      }
  
      @Override public E next() {
        if (cursor >= size) {
          throw new NoSuchElementException();
        }
        if (cursor == end) {
          if (chunk == null) {
            chunk = first;
          } else {
            chunk = ChunkList.next(chunk);
          }
          start = end;
          if (chunk == null) {
            end = start;
          } else {
            end = start + occupied(chunk);
          }
        }
        @SuppressWarnings("unchecked")
        final E element =
            (E) element(currentChunk(), HEADER_SIZE + (lastRet = cursor++) - start);
        return element;
      }
  
      @Override public boolean hasPrevious() {
        return cursor > 0;
      }
  
      @Override public E previous() {
        lastRet = cursor--;
        if (cursor < start) {
          chunk = chunk == null ? last : ChunkList.prev(chunk);
          if (chunk == null) {
            throw new NoSuchElementException();
          }
          final int o = occupied(chunk);
          end = start;
          start -= o;
          assert cursor == end - 1;
        }
        //noinspection unchecked
        return (E) element(currentChunk(), cursor - start);
      }
  
      @Override public int nextIndex() {
        return cursor;
      }
  
      @Override public int previousIndex() {
        return cursor - 1;
      }
  
      @Override public void remove() {
        if (lastRet < 0) {
          throw new IllegalStateException();
        }
        --size;
        --cursor;
        if (end == start + 1) {
          // Chunk is now empty.
          final E[] prev = prev(currentChunk());
          final E[] next = ChunkList.next(currentChunk());
          if (next == null) {
            last = prev;
            if (prev == null) {
              first = null;
            } else {
              setNext(prev, null);
            }
            chunk = null;
            end = HEADER_SIZE;
          } else {
            if (prev == null) {
              chunk = first = next;
              setPrev(next, null);
              end = occupied(requireNonNull(chunk, "chunk"));
            } else {
              setNext(prev, next);
              setPrev(next, prev);
              chunk = prev;
              end = start;
              start -= occupied(requireNonNull(chunk, "chunk"));
            }
          }
          lastRet = -1;
          return;
        }
        final int r = lastRet;
        lastRet = -1;
        if (r < start) {
          // Element we wish to eliminate is the last element in the previous
          // block.
          E[] c = chunk;
          if (c == null) {
            c = last;
          }
          int o = occupied(castNonNull(c));
          if (o == 1) {
            // Block is now empty; remove it
            final E[] prev = prev(c);
            if (prev == null) {
              if (chunk == null) {
                first = last = null;
              } else {
                first = chunk;
                setPrev(requireNonNull(chunk, "chunk"), null);
              }
            } else {
              setNext(requireNonNull(prev, "prev"), chunk);
              setPrev(requireNonNull(chunk, "chunk"), prev);
            }
          } else {
            --o;
            setElement(c, HEADER_SIZE + o, null); // allow gc
            setOccupied(c, o);
          }
        } else {
          // Move existing contents down one.
          System.arraycopy(currentChunk(), HEADER_SIZE + r - start + 1,
              currentChunk(), HEADER_SIZE + r - start, end - r - 1);
          --end;
          final int o = end - start;
          setElement(currentChunk(), HEADER_SIZE + o, null); // allow gc
          setOccupied(currentChunk(), o);
        }
      }
  
      @Override public void set(E e) {
        if (lastRet < 0) {
          throw new IllegalStateException();
        }
        E[] c = currentChunk();
        int p = lastRet;
        int s = start;
        if (p < start) {
          // The element is at the end of the previous chunk
          c = prev(c);
          s -= occupied(castNonNull(c));
        }
        setElement(c, HEADER_SIZE + p - s, e);
      }
  
      @Override public void add(E e) {
        if (chunk == null) {
          //noinspection unchecked
          E[] newChunk = (E[]) new Object[CHUNK_SIZE + HEADER_SIZE];
          if (first != null) {
            setNext(newChunk, first);
            setPrev(requireNonNull(first, "first"), newChunk);
          }
          first = newChunk;
          if (last == null) {
            last = newChunk;
          }
          chunk = newChunk;
          end = start;
        } else if (end == start + CHUNK_SIZE) {
          // FIXME We create a new chunk, but the next chunk might be
          // less than half full. We should consider using it.
          //noinspection unchecked
          E[] newChunk = (E[]) new Object[CHUNK_SIZE + HEADER_SIZE];
          final E[] next = ChunkList.next(chunk);
          setPrev(newChunk, chunk);
          setNext(requireNonNull(chunk, "chunk"), newChunk);
  
          if (next == null) {
            last = newChunk;
          } else {
            setPrev(next, newChunk);
            setNext(newChunk, next);
          }
  
          setOccupied(requireNonNull(chunk, "chunk"), CHUNK_SIZE / 2);
          setOccupied(newChunk, CHUNK_SIZE / 2);
          System.arraycopy(requireNonNull(chunk, "chunk"), HEADER_SIZE + CHUNK_SIZE / 2,
              newChunk, HEADER_SIZE, CHUNK_SIZE / 2);
          Arrays.fill(chunk, HEADER_SIZE + CHUNK_SIZE / 2,
              HEADER_SIZE + CHUNK_SIZE, null);
  
          if (cursor - start < CHUNK_SIZE / 2) {
            end -= CHUNK_SIZE / 2;
          } else {
            start += CHUNK_SIZE / 2;
            chunk = newChunk;
          }
        }
        // Move existing contents up one.
        System.arraycopy(chunk, HEADER_SIZE + cursor - start,
            chunk, HEADER_SIZE + cursor - start + 1, end - cursor);
        ++end;
        setElement(chunk, HEADER_SIZE + cursor - start, e);
        setOccupied(chunk, end - start);
        ++size;
      }
    }
  }
  