src/main/java/com/google/devtools/build/lib/util/LongArrayList.java

// Copyright 2015 The Bazel Authors. All rights reserved.
//
// Licensed 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 com.google.devtools.build.lib.util;

import com.google.common.base.Preconditions;
import java.util.Arrays;

/**
 * A list of primitive long values.
 *
 * <p>Grows its backing array internally when necessary and such that constant amortized addition of
 * elements is guaranteed.
 *
 * <p>Does not shrink its array except by explicit calls to {@link #trim}.
 */
public class LongArrayList {

  private static final int DEFAULT_CAPACITY = 12;

  private long[] array;
  private int size;

  /**
   * Initialize a new LongArrayList with default capacity.
   */
  public LongArrayList() {
    this.array = new long[DEFAULT_CAPACITY];
  }

  /**
   * Initialize a new LongArrayList with space for elements equal to the given capacity.
   * @throws IndexOutOfBoundsException if the capacity is negative
   */
  public LongArrayList(int capacity) {
    Preconditions.checkArgument(capacity >= 0, "Initial capacity must not be negative.");
    this.array = new long[capacity];
  }

  /**
   * Create a new LongArrayList backed by the given array. No copy is made.
   */
  public LongArrayList(long[] array) {
    Preconditions.checkNotNull(array);
    this.array = array;
    this.size = array.length;
  }

  /**
   * Add a value at a specific position to this list. All elements at larger indices will
   * shift to the right by one.
   * @param position may be any index within the array or equal to the size, to append at the end
   * @throws IndexOutOfBoundsException if the index is outside the interval [0, {@link #size()})
   */
  public void add(int position, long value) {
    Preconditions.checkPositionIndex(position, size);
    copyBackAndGrow(position, 1);
    set(position, value);
  }

  /**
   * Add a value to the end of this list.
   */
  public void add(long value) {
    add(size, value);
  }

  /**
   * Add all elements from another LongArrayList at the end of this one.
   * @see #addAll(LongArrayList, int)
   */
  public boolean addAll(LongArrayList other) {
    return addAll(other.array, 0, other.size, size);
  }

  /**
   * Add all elements from another LongArrayList at a certain position within or at the end of
   * this one.
   * @param other
   * @param position at which position to add these elements, adds at the end if equal to the size
   * @return whether this list changed
   * @throws IndexOutOfBoundsException if the index is outside the interval [0, {@link #size()}]
   */
  public boolean addAll(LongArrayList other, int position) {
    return addAll(other.array, 0, other.size, position);
  }

  /**
   * Add all elements from the given array to the end of this array.
   * @see #addAll(long[], int, int, int)
   */
  public boolean addAll(long[] array) {
    return addAll(array, 0, array.length, size);
  }

  /**
   * Add certain elements from the given array to the end of this array.
   * @see #addAll(long[], int, int, int)
   */
  public boolean addAll(long[] array, int fromIndex, int length) {
    return addAll(array, fromIndex, length, size);
  }

  /**
   * Add certain elements from the given array at a certain position in this list.
   * @param array the array from which to take the elements
   * @param fromIndex the position of the first element to add
   * @param length how many elements to add
   * @param position at which position to add these elements, adds at the end if equal to the size
   * @return whether this list has changed
   * @throws IndexOutOfBoundsException if fromIndex and length violate the boundaries of the given
   *    array or atIndex is not a valid index in this array or equal to the size
   */
  public boolean addAll(long[] array, int fromIndex, int length, int position) {
    Preconditions.checkNotNull(array);
    Preconditions.checkPositionIndex(fromIndex + length, array.length);
    if (length == 0) {
      return false;
    }
    // check other positions later to allow "adding" empty arrays anywhere within this array
    Preconditions.checkElementIndex(fromIndex, array.length);
    Preconditions.checkPositionIndex(position, size);
    copyBackAndGrow(position, length);
    System.arraycopy(array, fromIndex, this.array, position, length);
    return true;
  }

  /**
   * Resize the backing array to fit at least this many elements if necessary.
   */
  public void ensureCapacity(int capacity) {
    if (capacity > array.length) {
      long[] newArray = new long[growCapacity(capacity)];
      System.arraycopy(array, 0, newArray, 0, size);
      array = newArray;
    }
  }

  /**
   * @return the element at the specified index
   * @throws IndexOutOfBoundsException if the index is outside the interval [0, {@link #size()})
   */
  public long get(int index) {
    Preconditions.checkElementIndex(index, size);
    return array[index];
  }

  /**
   * Search for the first index at which the given value is found.
   * @return -1 if the value is not found, the index at which it was found otherwise
   */
  public int indexOf(long value) {
    for (int index = 0; index < size; index++) {
      if (array[index] == value) {
        return index;
      }
    }
    return -1;
  }

  /**
   * Remove the element at the specified index and shift all elements at higher indices down by
   * one.
   * @return the removed element
   * @throws IndexOutOfBoundsException if the index is outside the interval [0, {@link #size()})
   */
  public long remove(int index) {
    Preconditions.checkElementIndex(index, size);
    long previous = array[index];
    System.arraycopy(array, index + 1, array, index, size - index - 1);
    size--;
    return previous;
  }

  /**
   * Remove the first occurrence of a value and shift all elements at higher indices down by one.
   * @return true, if the list changed and thus contained the value, false otherwise
   */
  public boolean remove(long value) {
    int index = indexOf(value);
    if (index == -1) {
      return false;
    }
    remove(index);
    return true;
  }

  /**
   * Overwrites the element at a certain index with the given value and returns the previous
   * element.
   * @throws IndexOutOfBoundsException if the index is outside the interval [0, {@link #size()})
   */
  public long set(int index, long value) {
    Preconditions.checkElementIndex(index, size);
    long previous = array[index];
    array[index] = value;
    return previous;
  }

  /**
   * @return the amount of elements in this list
   */
  public int size() {
    return size;
  }

  /**
   * Sort the list in ascending order.
   */
  public void sort() {
    Arrays.sort(array, 0, size);
  }

  /**
   * Sort the sub list from the first index (inclusive) to the second index (exclusive) in
   * ascending order.
   * @see Arrays#sort(long[], int, int)
   * @throws IndexOutOfBoundsException if fromIndex is outside the interval [0, {@link #size()})
   * or toIndex is outside [0, {@link #size()}]
   */
  public void sort(int fromIndex, int toIndex) {
    Arrays.sort(array, fromIndex, toIndex);
  }

  /**
   * Build a String of the form [0, 1, 2]
   */
  @Override
  public String toString() {
    final StringBuilder sb = new StringBuilder("[");
    String separator = "";
    for (int index = 0; index < size; index++) {
      sb.append(separator);
      sb.append(array[index]);
      separator = ", ";
    }
    sb.append("]");
    return sb.toString();
  }

  /**
   * Remove any excess capacity to save space.
   */
  public void trim() {
    if (size < array.length) {
      long[] newArray = new long[size];
      System.arraycopy(array, 0, newArray, 0, size);
      array = newArray;
    }
  }

  /**
   * Copy the end of the array from a certain index back to make room for length many items and
   * adds length to the size.
   *
   * @param fromIndex may be equal to the current size, then no element needs to be copied, but the
   *    array may grow
   */
  private void copyBackAndGrow(int fromIndex, int length) {
    int newSize = size + length;
    ensureCapacity(newSize);
    System.arraycopy(array, fromIndex, array, fromIndex + length, size - fromIndex);
    size = newSize;
  }

  /**
   * The new capacity when growing the array to contain at least newSize many elements.
   * Uses a growth factor of 1.5.
   */
  private int growCapacity(int newSize) {
    return newSize + (newSize >> 1);
  }
}