| /* |
| * 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.hadoop.util; |
| |
| import org.apache.hadoop.classification.InterfaceAudience; |
| |
| import java.util.ArrayList; |
| import java.util.Arrays; |
| import java.util.Collection; |
| import java.util.Collections; |
| import java.util.Iterator; |
| import java.util.LinkedList; |
| import java.util.List; |
| |
| /** |
| * Static utility methods pertaining to {@link List} instances. |
| * This class is Hadoop's internal use alternative to Guava's Lists |
| * utility class. |
| * Javadocs for majority of APIs in this class are taken from Guava's Lists |
| * class from Guava release version 27.0-jre. |
| */ |
| @InterfaceAudience.Private |
| public final class Lists { |
| |
| private Lists() { |
| // empty |
| } |
| |
| /** |
| * Creates a <i>mutable</i>, empty {@code ArrayList} instance. |
| */ |
| public static <E> ArrayList<E> newArrayList() { |
| return new ArrayList<>(); |
| } |
| |
| /** |
| * Creates a <i>mutable</i> {@code ArrayList} instance containing the given |
| * elements. |
| * |
| * <p>Note that even when you do need the ability to add or remove, |
| * this method provides only a tiny bit of syntactic sugar for |
| * {@code newArrayList(} |
| * {@link Arrays#asList asList} |
| * {@code (...))}, or for creating an empty list then calling |
| * {@link Collections#addAll}. |
| */ |
| @SafeVarargs |
| public static <E> ArrayList<E> newArrayList(E... elements) { |
| if (elements == null) { |
| throw new NullPointerException(); |
| } |
| // Avoid integer overflow when a large array is passed in |
| int capacity = computeArrayListCapacity(elements.length); |
| ArrayList<E> list = new ArrayList<>(capacity); |
| Collections.addAll(list, elements); |
| return list; |
| } |
| |
| /** |
| * Creates a <i>mutable</i> {@code ArrayList} instance containing the |
| * given elements; a very thin shortcut for creating an empty list then |
| * calling Iterables#addAll. |
| */ |
| public static <E> ArrayList<E> newArrayList(Iterable<? extends E> elements) { |
| if (elements == null) { |
| throw new NullPointerException(); |
| } |
| return (elements instanceof Collection) |
| ? new ArrayList<>(cast(elements)) |
| : newArrayList(elements.iterator()); |
| } |
| |
| /** |
| * Creates a <i>mutable</i> {@code ArrayList} instance containing the |
| * given elements; a very thin shortcut for creating an empty list |
| * and then calling Iterators#addAll. |
| */ |
| public static <E> ArrayList<E> newArrayList(Iterator<? extends E> elements) { |
| ArrayList<E> list = newArrayList(); |
| addAll(list, elements); |
| return list; |
| } |
| |
| /** |
| * Creates an {@code ArrayList} instance backed by an array with the |
| * specified initial size; |
| * simply delegates to {@link ArrayList#ArrayList(int)}. |
| * |
| * @param initialArraySize the exact size of the initial backing array for |
| * the returned array list |
| * ({@code ArrayList} documentation calls this value the "capacity"). |
| * @return a new, empty {@code ArrayList} which is guaranteed not to |
| * resize itself unless its size reaches {@code initialArraySize + 1}. |
| * @throws IllegalArgumentException if {@code initialArraySize} is negative. |
| */ |
| public static <E> ArrayList<E> newArrayListWithCapacity( |
| int initialArraySize) { |
| checkNonnegative(initialArraySize, "initialArraySize"); |
| return new ArrayList<>(initialArraySize); |
| } |
| |
| /** |
| * Creates an {@code ArrayList} instance to hold {@code estimatedSize} |
| * elements, <i>plus</i> an unspecified amount of padding; |
| * you almost certainly mean to call {@link |
| * #newArrayListWithCapacity} (see that method for further advice on usage). |
| * |
| * @param estimatedSize an estimate of the eventual {@link List#size()} |
| * of the new list. |
| * @return a new, empty {@code ArrayList}, sized appropriately to hold the |
| * estimated number of elements. |
| * @throws IllegalArgumentException if {@code estimatedSize} is negative. |
| */ |
| public static <E> ArrayList<E> newArrayListWithExpectedSize( |
| int estimatedSize) { |
| return new ArrayList<>(computeArrayListCapacity(estimatedSize)); |
| } |
| |
| /** |
| * Creates a <i>mutable</i>, empty {@code LinkedList} instance. |
| * |
| * <p><b>Performance note:</b> {@link ArrayList} and |
| * {@link java.util.ArrayDeque} consistently |
| * outperform {@code LinkedList} except in certain rare and specific |
| * situations. Unless you have |
| * spent a lot of time benchmarking your specific needs, use one of those |
| * instead. |
| */ |
| public static <E> LinkedList<E> newLinkedList() { |
| return new LinkedList<>(); |
| } |
| |
| /** |
| * Creates a <i>mutable</i> {@code LinkedList} instance containing the given |
| * elements; a very thin shortcut for creating an empty list then calling |
| * Iterables#addAll. |
| * |
| * <p><b>Performance note:</b> {@link ArrayList} and |
| * {@link java.util.ArrayDeque} consistently |
| * outperform {@code LinkedList} except in certain rare and specific |
| * situations. Unless you have spent a lot of time benchmarking your |
| * specific needs, use one of those instead. |
| */ |
| public static <E> LinkedList<E> newLinkedList( |
| Iterable<? extends E> elements) { |
| LinkedList<E> list = newLinkedList(); |
| addAll(list, elements); |
| return list; |
| } |
| |
| private static int computeArrayListCapacity(int arraySize) { |
| checkNonnegative(arraySize, "arraySize"); |
| return saturatedCast(5L + arraySize + (arraySize / 10)); |
| } |
| |
| private static int checkNonnegative(int value, String name) { |
| if (value < 0) { |
| throw new IllegalArgumentException(name + " cannot be negative but was: " |
| + value); |
| } |
| return value; |
| } |
| |
| /** |
| * Returns the {@code int} nearest in value to {@code value}. |
| * |
| * @param value any {@code long} value. |
| * @return the same value cast to {@code int} if it is in the range of the |
| * {@code int} type, {@link Integer#MAX_VALUE} if it is too large, |
| * or {@link Integer#MIN_VALUE} if it is too small. |
| */ |
| private static int saturatedCast(long value) { |
| if (value > Integer.MAX_VALUE) { |
| return Integer.MAX_VALUE; |
| } |
| if (value < Integer.MIN_VALUE) { |
| return Integer.MIN_VALUE; |
| } |
| return (int) value; |
| } |
| |
| private static <T> boolean addAll(Collection<T> addTo, |
| Iterator<? extends T> iterator) { |
| if (addTo == null) { |
| throw new NullPointerException(); |
| } |
| if (iterator == null) { |
| throw new NullPointerException(); |
| } |
| boolean wasModified = false; |
| while (iterator.hasNext()) { |
| wasModified |= addTo.add(iterator.next()); |
| } |
| return wasModified; |
| } |
| |
| private static <T> Collection<T> cast(Iterable<T> iterable) { |
| return (Collection<T>) iterable; |
| } |
| |
| /** |
| * Adds all elements in {@code iterable} to {@code collection}. |
| * |
| * @return {@code true} if {@code collection} was modified as a result of |
| * this operation. |
| */ |
| private static <T> boolean addAll(Collection<T> addTo, |
| Iterable<? extends T> elementsToAdd) { |
| if (elementsToAdd instanceof Collection) { |
| Collection<? extends T> c = cast(elementsToAdd); |
| return addTo.addAll(c); |
| } |
| if (elementsToAdd == null) { |
| throw new NullPointerException(); |
| } |
| return addAll(addTo, elementsToAdd.iterator()); |
| } |
| |
| } |