src/main/java/com/google/devtools/build/lib/util/GroupedList.java - bazel - Git at Google

 // Copyright 2014 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 static com.google.common.base.Preconditions.checkArgument;
 import static com.google.common.base.Preconditions.checkState;

 import com.google.common.base.MoreObjects;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.ImmutableSet;
 import com.google.common.collect.Iterables;
 import com.google.common.collect.Lists;
 import com.google.devtools.build.lib.collect.compacthashset.CompactHashSet;
 import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadHostile;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
 import com.google.devtools.build.lib.skyframe.serialization.autocodec.SerializationConstant;
 import java.lang.annotation.ElementType;
 import java.lang.annotation.Target;
 import java.util.AbstractCollection;
 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Set;
 import javax.annotation.Nullable;
 import org.checkerframework.framework.qual.DefaultQualifierInHierarchy;
 import org.checkerframework.framework.qual.LiteralKind;
 import org.checkerframework.framework.qual.QualifierForLiterals;
 import org.checkerframework.framework.qual.SubtypeOf;

 /**
  * Encapsulates a list of groups.
  *
  * <p>Despite the "list" name, it is an error for the same element to appear multiple times in the
  * list. Users are responsible for not trying to add the same element to a GroupedList twice.
  *
  * <p>Groups are implemented as lists to minimize memory use. However, {@link #equals} is defined to
  * treat groups as unordered.
  *
  * <p>The generic type {@code T} <em>must not</em> be a {@link List}.
  */
 public final class GroupedList<T> implements Iterable<List<T>> {

   /**
    * Indicates that the annotated element is a compressed {@link GroupedList}, so that it can be
    * safely passed to {@link #create} and friends.
    */
   @SubtypeOf(DefaultObject.class)
   @Target({ElementType.TYPE_USE, ElementType.TYPE_PARAMETER})
   @QualifierForLiterals(LiteralKind.NULL)
   public @interface Compressed {}

   /** Default annotation for type-safety checks of {@link Compressed}. */
   @DefaultQualifierInHierarchy
   @SubtypeOf({})
   @Target({ElementType.TYPE_USE, ElementType.TYPE_PARAMETER})
   private @interface DefaultObject {}

   // Total number of items in the list. At least elements.size(), but might be larger if there are
   // any nested lists.
   private int size = 0;
   // Items in this GroupedList. Each element is either of type T or List<T>.
   private final ArrayList<Object> elements;

   private final CollectionView collectionView = new CollectionView();

   public GroupedList() {
     // We optimize for small lists.
     this.elements = new ArrayList<>(1);
   }

   private GroupedList(int size, Object[] elements) {
     this.size = size;
     this.elements = Lists.newArrayList(elements);
   }

   /**
    * Increases the capacity of the backing list to accommodate the given number of additional
    * groups.
    */
   public void ensureCapacityForAdditionalGroups(int additionalGroups) {
     elements.ensureCapacity(elements.size() + additionalGroups);
   }

   /**
    * Adds a new group with a single element.
    *
    * <p>The caller must ensure that the given element is not already present.
    */
   public void appendSingleton(T t) {
     checkArgument(!(t instanceof List), "Cannot created GroupedList of lists: %s", t);
     elements.add(t);
     size++;
   }

   /**
    * Adds a new group.
    *
    * <p>The caller must ensure that the new group is duplicate-free and does not contain any
    * elements which are already present.
    */
   public void appendGroup(ImmutableList<T> group) {
     addGroup(group, elements);
     size += group.size();
   }

   /**
    * Removes the elements in toRemove from this list. Takes time proportional to the size of the
    * list, so should not be called often.
    */
   public void remove(Set<T> toRemove) {
     if (!toRemove.isEmpty()) {
       size = removeAndGetNewSize(elements, toRemove);
     }
   }

   /**
    * Removes everything in {@code toRemove} from the list of lists, {@code elements}. Returns the
    * new number of elements.
    */
   private static int removeAndGetNewSize(List<Object> elements, Set<?> toRemove) {
     int removedCount = 0;
     int newSize = 0;
     // elements.size is an upper bound of the needed size. Since normally removal happens just
     // before the list is finished and compressed, optimizing this size isn't a concern.
     List<Object> newElements = new ArrayList<>(elements.size());
     for (Object obj : elements) {
       if (obj instanceof List) {
         ImmutableList.Builder<Object> newGroup = new ImmutableList.Builder<>();
         List<?> oldGroup = (List<?>) obj;
         for (Object elt : oldGroup) {
           if (toRemove.contains(elt)) {
             removedCount++;
           } else {
             newGroup.add(elt);
             newSize++;
           }
         }
         addGroup(newGroup.build(), newElements);
       } else if (toRemove.contains(obj)) {
         removedCount++;
       } else {
         newElements.add(obj);
         newSize++;
       }
     }
     // removedCount can be larger if elements had duplicates and the duplicate was also in toRemove.
     checkState(
         removedCount >= toRemove.size(),
         "Requested removal of absent element(s) (toRemove=%s, elements=%s)",
         toRemove,
         elements);
     elements.clear();
     elements.addAll(newElements);
     return newSize;
   }

   /** Returns the group at position {@code i}. {@code i} must be less than {@link #listSize()}. */
   @SuppressWarnings("unchecked") // Cast of Object to List<T> or T.
   public ImmutableList<T> get(int i) {
     Object obj = elements.get(i);
     if (obj instanceof List) {
       return (ImmutableList<T>) obj;
     }
     return ImmutableList.of((T) obj);
   }

   /** Returns the number of groups in this list. */
   public int listSize() {
     return elements.size();
   }

   /**
    * Returns the number of individual elements of type {@code T} in this list, as opposed to the
    * number of groups -- equivalent to adding up the sizes of each group in this list.
    */
   public int numElements() {
     return size;
   }

   public static int numElements(@Compressed Object compressed) {
     if (compressed == EMPTY_LIST) {
       return 0;
     }
     if (compressed.getClass().isArray()) {
       int size = 0;
       for (Object item : (Object[]) compressed) {
         size += sizeOf(item);
       }
       return size;
     }
     // Just a single element.
     return 1;
   }

   /** Returns the number of groups in a compressed {@code GroupedList}. */
   public static int numGroups(@Compressed Object compressed) {
     if (compressed == EMPTY_LIST) {
       return 0;
     }
     if (compressed.getClass().isArray()) {
       return ((Object[]) compressed).length;
     }
     return 1;
   }

   /**
    * Expands a compressed {@code GroupedList} into an {@link Iterable}. Equivalent to {@link
    * #getAllElementsAsIterable()} but potentially more efficient.
    */
   @SuppressWarnings("unchecked")
   public static <T> Iterable<T> compressedToIterable(@Compressed Object compressed) {
     if (compressed == EMPTY_LIST) {
       return ImmutableList.of();
     }
     if (compressed.getClass().isArray()) {
       return GroupedList.<T>create(compressed).getAllElementsAsIterable();
     }
     checkState(!(compressed instanceof List), compressed);
     return ImmutableList.of((T) compressed);
   }

   /**
    * Casts an {@code Object} which is known to be {@link Compressed}.
    *
    * <p>This method should only be used when it is not possible to enforce the type via annotations.
    */
   public static @Compressed Object castAsCompressed(Object obj) {
     checkArgument(!(obj instanceof GroupedList), obj);
     return (@Compressed Object) obj;
   }

   /** Returns true if this list contains no elements. */
   public boolean isEmpty() {
     return elements.isEmpty();
   }

   /**
    * Returns true if this list contains {@code needle}. Takes time proportional to list size. Call
    * {@link #toSet} instead and use the result if doing multiple contains checks.
    */
   public boolean expensiveContains(T needle) {
     return contains(elements, needle);
   }

   private static boolean contains(List<Object> elements, Object needle) {
     for (Object obj : elements) {
       if (obj instanceof List) {
         if (((List<?>) obj).contains(needle)) {
           return true;
         }
       } else if (obj.equals(needle)) {
         return true;
       }
     }
     return false;
   }

   @SerializationConstant @AutoCodec.VisibleForSerialization
   static final @Compressed Object EMPTY_LIST = new Object();

   public @Compressed Object compress() {
     switch (numElements()) {
       case 0:
         return EMPTY_LIST;
       case 1:
         return Iterables.getOnlyElement(elements);
       default:
         return elements.toArray();
     }
   }

   @SuppressWarnings("unchecked")
   public ImmutableSet<T> toSet() {
     ImmutableSet.Builder<T> builder = ImmutableSet.builderWithExpectedSize(size);
     for (Object obj : elements) {
       if (obj instanceof List) {
         builder.addAll((List<T>) obj);
       } else {
         builder.add((T) obj);
       }
     }
     return builder.build();
   }

   private static int sizeOf(Object obj) {
     return obj instanceof List ? ((List<?>) obj).size() : 1;
   }

   public static <E> GroupedList<E> create(@Compressed Object compressed) {
     if (compressed == EMPTY_LIST) {
       return new GroupedList<>();
     }
     if (compressed.getClass().isArray()) {
       int size = 0;
       Object[] compressedArray = ((Object[]) compressed);
       for (Object item : compressedArray) {
         size += sizeOf(item);
       }
       return new GroupedList<>(size, compressedArray);
     }
     // Just a single element.
     return new GroupedList<>(1, new Object[] {compressed});
   }

   @Override
   public int hashCode() {
     // Hashing requires getting an order-independent hash for each element of this.elements. That
     // is too expensive for a hash code.
     throw new UnsupportedOperationException("Should not need to get hash for " + this);
   }

   /**
    * Checks that two lists, neither of which may contain duplicates, have the same elements,
    * regardless of order.
    */
   private static boolean checkUnorderedEqualityWithoutDuplicates(List<?> first, List<?> second) {
     if (first.size() != second.size()) {
       return false;
     }
     // The order-sensitive comparison usually returns true. When it does, the CompactHashSet
     // doesn't need to be constructed.
     return first.equals(second) || CompactHashSet.create(first).containsAll(second);
   }

   /**
    * A grouping-unaware view of a {@code GroupedList} which does not support modifications.
    *
    * <p>This is implemented as a {@code Collection} so that calling {@link Iterables#size} on the
    * return value of {@link #getAllElementsAsIterable} will take constant time.
    */
   private final class CollectionView extends AbstractCollection<T> {

     @Override
     public Iterator<T> iterator() {
       return new UngroupedIterator<>(elements);
     }

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

   /** An iterator that loops through every element in each group. */
   private static final class UngroupedIterator<T> implements Iterator<T> {
     private final List<Object> elements;
     private int outerIndex = 0;
     @Nullable private List<T> currentGroup;
     private int innerIndex = 0;

     private UngroupedIterator(List<Object> elements) {
       this.elements = elements;
     }

     @Override
     public boolean hasNext() {
       return outerIndex < elements.size();
     }

     @SuppressWarnings("unchecked") // Cast of Object to List<T> or T.
     @Override
     public T next() {
       if (currentGroup != null) {
         return nextFromCurrentGroup();
       }
       Object next = elements.get(outerIndex);
       if (next instanceof List) {
         currentGroup = (List<T>) next;
         innerIndex = 0;
         return nextFromCurrentGroup();
       }
       return (T) elements.get(outerIndex++);
     }

     private T nextFromCurrentGroup() {
       T next = currentGroup.get(innerIndex++);
       if (innerIndex == currentGroup.size()) {
         outerIndex++;
         currentGroup = null;
       }
       return next;
     }
   }

   @ThreadHostile
   public Collection<T> getAllElementsAsIterable() {
     return collectionView;
   }

   @Override
   public boolean equals(Object other) {
     if (this == other) {
       return true;
     }
     if (!(other instanceof GroupedList)) {
       return false;
     }
     GroupedList<?> that = (GroupedList<?>) other;
     // We must check the deps, ignoring the ordering of deps in the same group.
     if (this.size != that.size || this.elements.size() != that.elements.size()) {
       return false;
     }
     for (int i = 0; i < this.elements.size(); i++) {
       Object thisElt = this.elements.get(i);
       Object thatElt = that.elements.get(i);
       if (thisElt == thatElt) {
         continue;
       }
       if (thisElt instanceof List) {
         // Recall that each inner item is either a List or a singleton element.
         if (!(thatElt instanceof List)) {
           return false;
         }
         if (!checkUnorderedEqualityWithoutDuplicates((List<?>) thisElt, (List<?>) thatElt)) {
           return false;
         }
       } else if (!thisElt.equals(thatElt)) {
         return false;
       }
     }
     return true;
   }

   @Override
   public String toString() {
     return MoreObjects.toStringHelper(this).add("elements", elements).add("size", size).toString();
   }

   /**
    * Iterator that returns the next group in elements for each call to {@link #next}. A custom
    * iterator is needed here because, to optimize memory, we store single-element lists as elements
    * internally, and so they must be wrapped before they're returned.
    */
   private class GroupedIterator implements Iterator<List<T>> {
     private final Iterator<Object> iter = elements.iterator();

     @Override
     public boolean hasNext() {
       return iter.hasNext();
     }

     @SuppressWarnings("unchecked") // Cast of Object to List<T> or T.
     @Override
     public List<T> next() {
       Object obj = iter.next();
       if (obj instanceof List) {
         return (List<T>) obj;
       }
       return ImmutableList.of((T) obj);
     }
   }

   @Override
   public Iterator<List<T>> iterator() {
     return new GroupedIterator();
   }

   /**
    * If {@code group} is empty, this function does nothing.
    *
    * <p>If it contains a single element, then that element is added to {@code elements}.
    *
    * <p>If it contains more than one element, then it is added as the next element of {@code
    * elements} (this means {@code elements} may contain both raw objects and {@link
    * ImmutableList}s).
    *
    * <p>Use with caution as there are no checks in place for the integrity of the resulting object
    * (no de-duping or verifying there are no nested lists).
    */
   private static void addGroup(ImmutableList<?> group, List<Object> elements) {
     switch (group.size()) {
       case 0:
         return;
       case 1:
         elements.add(group.get(0));
         return;
       default:
         elements.add(group);
     }
   }
 }
	// Copyright 2014 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 static com.google.common.base.Preconditions.checkArgument;
	import static com.google.common.base.Preconditions.checkState;

	import com.google.common.base.MoreObjects;
	import com.google.common.collect.ImmutableList;
	import com.google.common.collect.ImmutableSet;
	import com.google.common.collect.Iterables;
	import com.google.common.collect.Lists;
	import com.google.devtools.build.lib.collect.compacthashset.CompactHashSet;
	import com.google.devtools.build.lib.concurrent.ThreadSafety.ThreadHostile;
	import com.google.devtools.build.lib.skyframe.serialization.autocodec.AutoCodec;
	import com.google.devtools.build.lib.skyframe.serialization.autocodec.SerializationConstant;
	import java.lang.annotation.ElementType;
	import java.lang.annotation.Target;
	import java.util.AbstractCollection;
	import java.util.ArrayList;
	import java.util.Collection;
	import java.util.Iterator;
	import java.util.List;
	import java.util.Set;
	import javax.annotation.Nullable;
	import org.checkerframework.framework.qual.DefaultQualifierInHierarchy;
	import org.checkerframework.framework.qual.LiteralKind;
	import org.checkerframework.framework.qual.QualifierForLiterals;
	import org.checkerframework.framework.qual.SubtypeOf;

	/**
	* Encapsulates a list of groups.
	*
	* <p>Despite the "list" name, it is an error for the same element to appear multiple times in the
	* list. Users are responsible for not trying to add the same element to a GroupedList twice.
	*
	* <p>Groups are implemented as lists to minimize memory use. However, {@link #equals} is defined to
	* treat groups as unordered.
	*
	* <p>The generic type {@code T} <em>must not</em> be a {@link List}.
	*/
	public final class GroupedList<T> implements Iterable<List<T>> {

	/**
	* Indicates that the annotated element is a compressed {@link GroupedList}, so that it can be
	* safely passed to {@link #create} and friends.
	*/
	@SubtypeOf(DefaultObject.class)
	@Target({ElementType.TYPE_USE, ElementType.TYPE_PARAMETER})
	@QualifierForLiterals(LiteralKind.NULL)
	public @interface Compressed {}

	/** Default annotation for type-safety checks of {@link Compressed}. */
	@DefaultQualifierInHierarchy
	@SubtypeOf({})
	@Target({ElementType.TYPE_USE, ElementType.TYPE_PARAMETER})
	private @interface DefaultObject {}

	// Total number of items in the list. At least elements.size(), but might be larger if there are
	// any nested lists.
	private int size = 0;
	// Items in this GroupedList. Each element is either of type T or List<T>.
	private final ArrayList<Object> elements;

	private final CollectionView collectionView = new CollectionView();

	public GroupedList() {
	// We optimize for small lists.
	this.elements = new ArrayList<>(1);
	}

	private GroupedList(int size, Object[] elements) {
	this.size = size;
	this.elements = Lists.newArrayList(elements);
	}

	/**
	* Increases the capacity of the backing list to accommodate the given number of additional
	* groups.
	*/
	public void ensureCapacityForAdditionalGroups(int additionalGroups) {
	elements.ensureCapacity(elements.size() + additionalGroups);
	}

	/**
	* Adds a new group with a single element.
	*
	* <p>The caller must ensure that the given element is not already present.
	*/
	public void appendSingleton(T t) {
	checkArgument(!(t instanceof List), "Cannot created GroupedList of lists: %s", t);
	elements.add(t);
	size++;
	}

	/**
	* Adds a new group.
	*
	* <p>The caller must ensure that the new group is duplicate-free and does not contain any
	* elements which are already present.
	*/
	public void appendGroup(ImmutableList<T> group) {
	addGroup(group, elements);
	size += group.size();
	}

	/**
	* Removes the elements in toRemove from this list. Takes time proportional to the size of the
	* list, so should not be called often.
	*/
	public void remove(Set<T> toRemove) {
	if (!toRemove.isEmpty()) {
	size = removeAndGetNewSize(elements, toRemove);
	}
	}

	/**
	* Removes everything in {@code toRemove} from the list of lists, {@code elements}. Returns the
	* new number of elements.
	*/
	private static int removeAndGetNewSize(List<Object> elements, Set<?> toRemove) {
	int removedCount = 0;
	int newSize = 0;
	// elements.size is an upper bound of the needed size. Since normally removal happens just
	// before the list is finished and compressed, optimizing this size isn't a concern.
	List<Object> newElements = new ArrayList<>(elements.size());
	for (Object obj : elements) {
	if (obj instanceof List) {
	ImmutableList.Builder<Object> newGroup = new ImmutableList.Builder<>();
	List<?> oldGroup = (List<?>) obj;
	for (Object elt : oldGroup) {
	if (toRemove.contains(elt)) {
	removedCount++;
	} else {
	newGroup.add(elt);
	newSize++;
	}
	}
	addGroup(newGroup.build(), newElements);
	} else if (toRemove.contains(obj)) {
	removedCount++;
	} else {
	newElements.add(obj);
	newSize++;
	}
	}
	// removedCount can be larger if elements had duplicates and the duplicate was also in toRemove.
	checkState(
	removedCount >= toRemove.size(),
	"Requested removal of absent element(s) (toRemove=%s, elements=%s)",
	toRemove,
	elements);
	elements.clear();
	elements.addAll(newElements);
	return newSize;
	}

	/** Returns the group at position {@code i}. {@code i} must be less than {@link #listSize()}. */
	@SuppressWarnings("unchecked") // Cast of Object to List<T> or T.
	public ImmutableList<T> get(int i) {
	Object obj = elements.get(i);
	if (obj instanceof List) {
	return (ImmutableList<T>) obj;
	}
	return ImmutableList.of((T) obj);
	}

	/** Returns the number of groups in this list. */
	public int listSize() {
	return elements.size();
	}

	/**
	* Returns the number of individual elements of type {@code T} in this list, as opposed to the
	* number of groups -- equivalent to adding up the sizes of each group in this list.
	*/
	public int numElements() {
	return size;
	}

	public static int numElements(@Compressed Object compressed) {
	if (compressed == EMPTY_LIST) {
	return 0;
	}
	if (compressed.getClass().isArray()) {
	int size = 0;
	for (Object item : (Object[]) compressed) {
	size += sizeOf(item);
	}
	return size;
	}
	// Just a single element.
	return 1;
	}

	/** Returns the number of groups in a compressed {@code GroupedList}. */
	public static int numGroups(@Compressed Object compressed) {
	if (compressed == EMPTY_LIST) {
	return 0;
	}
	if (compressed.getClass().isArray()) {
	return ((Object[]) compressed).length;
	}
	return 1;
	}

	/**
	* Expands a compressed {@code GroupedList} into an {@link Iterable}. Equivalent to {@link
	* #getAllElementsAsIterable()} but potentially more efficient.
	*/
	@SuppressWarnings("unchecked")
	public static <T> Iterable<T> compressedToIterable(@Compressed Object compressed) {
	if (compressed == EMPTY_LIST) {
	return ImmutableList.of();
	}
	if (compressed.getClass().isArray()) {
	return GroupedList.<T>create(compressed).getAllElementsAsIterable();
	}
	checkState(!(compressed instanceof List), compressed);
	return ImmutableList.of((T) compressed);
	}

	/**
	* Casts an {@code Object} which is known to be {@link Compressed}.
	*
	* <p>This method should only be used when it is not possible to enforce the type via annotations.
	*/
	public static @Compressed Object castAsCompressed(Object obj) {
	checkArgument(!(obj instanceof GroupedList), obj);
	return (@Compressed Object) obj;
	}

	/** Returns true if this list contains no elements. */
	public boolean isEmpty() {
	return elements.isEmpty();
	}

	/**
	* Returns true if this list contains {@code needle}. Takes time proportional to list size. Call
	* {@link #toSet} instead and use the result if doing multiple contains checks.
	*/
	public boolean expensiveContains(T needle) {
	return contains(elements, needle);
	}

	private static boolean contains(List<Object> elements, Object needle) {
	for (Object obj : elements) {
	if (obj instanceof List) {
	if (((List<?>) obj).contains(needle)) {
	return true;
	}
	} else if (obj.equals(needle)) {
	return true;
	}
	}
	return false;
	}

	@SerializationConstant @AutoCodec.VisibleForSerialization
	static final @Compressed Object EMPTY_LIST = new Object();

	public @Compressed Object compress() {
	switch (numElements()) {
	case 0:
	return EMPTY_LIST;
	case 1:
	return Iterables.getOnlyElement(elements);
	default:
	return elements.toArray();
	}
	}

	@SuppressWarnings("unchecked")
	public ImmutableSet<T> toSet() {
	ImmutableSet.Builder<T> builder = ImmutableSet.builderWithExpectedSize(size);
	for (Object obj : elements) {
	if (obj instanceof List) {
	builder.addAll((List<T>) obj);
	} else {
	builder.add((T) obj);
	}
	}
	return builder.build();
	}

	private static int sizeOf(Object obj) {
	return obj instanceof List ? ((List<?>) obj).size() : 1;
	}

	public static <E> GroupedList<E> create(@Compressed Object compressed) {
	if (compressed == EMPTY_LIST) {
	return new GroupedList<>();
	}
	if (compressed.getClass().isArray()) {
	int size = 0;
	Object[] compressedArray = ((Object[]) compressed);
	for (Object item : compressedArray) {
	size += sizeOf(item);
	}
	return new GroupedList<>(size, compressedArray);
	}
	// Just a single element.
	return new GroupedList<>(1, new Object[] {compressed});
	}

	@Override
	public int hashCode() {
	// Hashing requires getting an order-independent hash for each element of this.elements. That
	// is too expensive for a hash code.
	throw new UnsupportedOperationException("Should not need to get hash for " + this);
	}

	/**
	* Checks that two lists, neither of which may contain duplicates, have the same elements,
	* regardless of order.
	*/
	private static boolean checkUnorderedEqualityWithoutDuplicates(List<?> first, List<?> second) {
	if (first.size() != second.size()) {
	return false;
	}
	// The order-sensitive comparison usually returns true. When it does, the CompactHashSet
	// doesn't need to be constructed.
	return first.equals(second) \|\| CompactHashSet.create(first).containsAll(second);
	}

	/**
	* A grouping-unaware view of a {@code GroupedList} which does not support modifications.
	*
	* <p>This is implemented as a {@code Collection} so that calling {@link Iterables#size} on the
	* return value of {@link #getAllElementsAsIterable} will take constant time.
	*/
	private final class CollectionView extends AbstractCollection<T> {

	@Override
	public Iterator<T> iterator() {
	return new UngroupedIterator<>(elements);
	}

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

	/** An iterator that loops through every element in each group. */
	private static final class UngroupedIterator<T> implements Iterator<T> {
	private final List<Object> elements;
	private int outerIndex = 0;
	@Nullable private List<T> currentGroup;
	private int innerIndex = 0;

	private UngroupedIterator(List<Object> elements) {
	this.elements = elements;
	}

	@Override
	public boolean hasNext() {
	return outerIndex < elements.size();
	}

	@SuppressWarnings("unchecked") // Cast of Object to List<T> or T.
	@Override
	public T next() {
	if (currentGroup != null) {
	return nextFromCurrentGroup();
	}
	Object next = elements.get(outerIndex);
	if (next instanceof List) {
	currentGroup = (List<T>) next;
	innerIndex = 0;
	return nextFromCurrentGroup();
	}
	return (T) elements.get(outerIndex++);
	}

	private T nextFromCurrentGroup() {
	T next = currentGroup.get(innerIndex++);
	if (innerIndex == currentGroup.size()) {
	outerIndex++;
	currentGroup = null;
	}
	return next;
	}
	}

	@ThreadHostile
	public Collection<T> getAllElementsAsIterable() {
	return collectionView;
	}

	@Override
	public boolean equals(Object other) {
	if (this == other) {
	return true;
	}
	if (!(other instanceof GroupedList)) {
	return false;
	}
	GroupedList<?> that = (GroupedList<?>) other;
	// We must check the deps, ignoring the ordering of deps in the same group.
	if (this.size != that.size \|\| this.elements.size() != that.elements.size()) {
	return false;
	}
	for (int i = 0; i < this.elements.size(); i++) {
	Object thisElt = this.elements.get(i);
	Object thatElt = that.elements.get(i);
	if (thisElt == thatElt) {
	continue;
	}
	if (thisElt instanceof List) {
	// Recall that each inner item is either a List or a singleton element.
	if (!(thatElt instanceof List)) {
	return false;
	}
	if (!checkUnorderedEqualityWithoutDuplicates((List<?>) thisElt, (List<?>) thatElt)) {
	return false;
	}
	} else if (!thisElt.equals(thatElt)) {
	return false;
	}
	}
	return true;
	}

	@Override
	public String toString() {
	return MoreObjects.toStringHelper(this).add("elements", elements).add("size", size).toString();
	}

	/**
	* Iterator that returns the next group in elements for each call to {@link #next}. A custom
	* iterator is needed here because, to optimize memory, we store single-element lists as elements
	* internally, and so they must be wrapped before they're returned.
	*/
	private class GroupedIterator implements Iterator<List<T>> {
	private final Iterator<Object> iter = elements.iterator();

	@Override
	public boolean hasNext() {
	return iter.hasNext();
	}

	@SuppressWarnings("unchecked") // Cast of Object to List<T> or T.
	@Override
	public List<T> next() {
	Object obj = iter.next();
	if (obj instanceof List) {
	return (List<T>) obj;
	}
	return ImmutableList.of((T) obj);
	}
	}

	@Override
	public Iterator<List<T>> iterator() {
	return new GroupedIterator();
	}

	/**
	* If {@code group} is empty, this function does nothing.
	*
	* <p>If it contains a single element, then that element is added to {@code elements}.
	*
	* <p>If it contains more than one element, then it is added as the next element of {@code
	* elements} (this means {@code elements} may contain both raw objects and {@link
	* ImmutableList}s).
	*
	* <p>Use with caution as there are no checks in place for the integrity of the resulting object
	* (no de-duping or verifying there are no nested lists).
	*/
	private static void addGroup(ImmutableList<?> group, List<Object> elements) {
	switch (group.size()) {
	case 0:
	return;
	case 1:
	elements.add(group.get(0));
	return;
	default:
	elements.add(group);
	}
	}
	}