Java 类java.util.RandomAccess 实例源码

/**
 * Create a typesafe copy of a raw list.
 * @param rawList an unchecked list
 * @param type the desired supertype of the entries
 * @param strict true to throw a <code>ClassCastException</code> if the raw list has an invalid entry,
 *               false to skip over such entries (warnings may be logged)
 * @return a typed list guaranteed to contain only entries assignable
 *         to the named type (or they may be null)
 * @throws ClassCastException if some entry in the raw list was not well-typed, and only if <code>strict</code> was true
 */
public static <E> List<E> checkedListByCopy(List rawList, Class<E> type, boolean strict) throws ClassCastException {
    List<E> l = (rawList instanceof RandomAccess) ? new ArrayList<E>(rawList.size()) : new LinkedList<E>();
    Iterator it = rawList.iterator();
    while (it.hasNext()) {
        Object e = it.next();
        try {
            l.add(type.cast(e));
        } catch (ClassCastException x) {
            if (strict) {
                throw x;
            } else {
                LOG.log(Level.WARNING, "Element {0} not assignable to {1}", new Object[] {e, type});
            }
        }
    }
    return l;
}

public void testNewListMultimap() {
  CountingSupplier<LinkedList<Integer>> factory = new ListSupplier();
  Map<Color, Collection<Integer>> map = Maps.newTreeMap();
  ListMultimap<Color, Integer> multimap =
      Multimaps.newListMultimap(map, factory);
  assertEquals(0, factory.count);
  multimap.putAll(Color.BLUE, asList(3, 1, 4, 1));
  assertEquals(1, factory.count);
  multimap.putAll(Color.RED, asList(2, 7, 1, 8));
  assertEquals(2, factory.count);
  assertEquals("{BLUE=[3, 1, 4, 1], RED=[2, 7, 1, 8]}", multimap.toString());
  assertFalse(multimap.get(Color.BLUE) instanceof RandomAccess);

  assertTrue(multimap.keySet() instanceof SortedSet);
  assertTrue(multimap.asMap() instanceof SortedMap);
}

/**
 * An implementation of {@link List#subList(int, int)}.
 */
static <E> List<E> subListImpl(final List<E> list, int fromIndex, int toIndex) {
  List<E> wrapper;
  if (list instanceof RandomAccess) {
    wrapper =
        new RandomAccessListWrapper<E>(list) {
          @Override
          public ListIterator<E> listIterator(int index) {
            return backingList.listIterator(index);
          }

          private static final long serialVersionUID = 0;
        };
  } else {
    wrapper =
        new AbstractListWrapper<E>(list) {
          @Override
          public ListIterator<E> listIterator(int index) {
            return backingList.listIterator(index);
          }

          private static final long serialVersionUID = 0;
        };
  }
  return wrapper.subList(fromIndex, toIndex);
}

public void testAsList1Small() {
  List<String> list = Lists.asList("foo", new String[0]);
  assertThat(list).contains("foo");
  assertEquals(1, list.size());
  assertIndexIsOutOfBounds(list, -1);
  assertEquals("foo", list.get(0));
  assertIndexIsOutOfBounds(list, 1);
  assertTrue(list instanceof RandomAccess);

  new IteratorTester<String>(3, UNMODIFIABLE, singletonList("foo"),
      IteratorTester.KnownOrder.KNOWN_ORDER) {
    @Override protected Iterator<String> newTargetIterator() {
      return Lists.asList("foo", new String[0]).iterator();
    }
  }.test();
}

@GwtIncompatible // SerializableTester
public void testAsList2Small() {
  List<String> list = Lists.asList("foo", "bar", new String[0]);
  assertThat(list).containsExactly("foo", "bar").inOrder();
  assertEquals(2, list.size());
  assertIndexIsOutOfBounds(list, -1);
  assertEquals("foo", list.get(0));
  assertEquals("bar", list.get(1));
  assertIndexIsOutOfBounds(list, 2);
  SerializableTester.reserializeAndAssert(list);
  assertTrue(list instanceof RandomAccess);

  new IteratorTester<String>(5, UNMODIFIABLE, asList("foo", "bar"),
      IteratorTester.KnownOrder.KNOWN_ORDER) {
    @Override protected Iterator<String> newTargetIterator() {
      return Lists.asList("foo", "bar", new String[0]).iterator();
    }
  }.test();
}

@GwtIncompatible // ArrayList.subList doesn't implement RandomAccess in GWT.
public void testPartitionRandomAccessTrue() {
  List<Integer> source = asList(1, 2, 3);
  List<List<Integer>> partitions = Lists.partition(source, 2);

  assertTrue("partition should be RandomAccess, but not: "
      + partitions.getClass(),
      partitions instanceof RandomAccess);

  assertTrue("partition[0] should be RandomAccess, but not: "
      + partitions.get(0).getClass(),
      partitions.get(0) instanceof RandomAccess);

  assertTrue("partition[1] should be RandomAccess, but not: "
      + partitions.get(1).getClass(),
      partitions.get(1) instanceof RandomAccess);
}

/**
 * An implementation of {@link List#subList(int, int)}.
 */
static <E> List<E> subListImpl(
    final List<E> list, int fromIndex, int toIndex) {
  List<E> wrapper;
  if (list instanceof RandomAccess) {
    wrapper = new RandomAccessListWrapper<E>(list) {
      @Override public ListIterator<E> listIterator(int index) {
        return backingList.listIterator(index);
      }

      private static final long serialVersionUID = 0;
    };
  } else {
    wrapper = new AbstractListWrapper<E>(list) {
      @Override public ListIterator<E> listIterator(int index) {
        return backingList.listIterator(index);
      }

      private static final long serialVersionUID = 0;
    };
  }
  return wrapper.subList(fromIndex, toIndex);
}

/**
 * An implementation of {@link List#subList(int, int)}.
 */
static <E> List<E> subListImpl(final List<E> list, int fromIndex, int toIndex) {
  List<E> wrapper;
  if (list instanceof RandomAccess) {
    wrapper =
        new RandomAccessListWrapper<E>(list) {
          @Override
          public ListIterator<E> listIterator(int index) {
            return backingList.listIterator(index);
          }

          private static final long serialVersionUID = 0;
        };
  } else {
    wrapper =
        new AbstractListWrapper<E>(list) {
          @Override
          public ListIterator<E> listIterator(int index) {
            return backingList.listIterator(index);
          }

          private static final long serialVersionUID = 0;
        };
  }
  return wrapper.subList(fromIndex, toIndex);
}

/**
 * An implementation of {@link List#equals(Object)}.
 */
static boolean equalsImpl(List<?> thisList, @Nullable Object other) {
  if (other == checkNotNull(thisList)) {
    return true;
  }
  if (!(other instanceof List)) {
    return false;
  }
  List<?> otherList = (List<?>) other;
  int size = thisList.size();
  if (size != otherList.size()) {
    return false;
  }
  if (thisList instanceof RandomAccess && otherList instanceof RandomAccess) {
    // avoid allocation and use the faster loop
    for (int i = 0; i < size; i++) {
      if (!Objects.equal(thisList.get(i), otherList.get(i))) {
        return false;
      }
    }
    return true;
  } else {
    return Iterators.elementsEqual(thisList.iterator(), otherList.iterator());
  }
}

public void testUnmodifiableLinkedListMultimapRandomAccess() {
  ListMultimap<String, Integer> delegate = LinkedListMultimap.create();
  delegate.put("foo", 1);
  delegate.put("foo", 3);
  ListMultimap<String, Integer> multimap = Multimaps.unmodifiableListMultimap(delegate);
  assertFalse(multimap.get("foo") instanceof RandomAccess);
  assertFalse(multimap.get("bar") instanceof RandomAccess);
}

public void testPartitionRandomAccessFalse() {
  List<Integer> source = Lists.newLinkedList(asList(1, 2, 3));
  List<List<Integer>> partitions = Lists.partition(source, 2);
  assertFalse(partitions instanceof RandomAccess);
  assertFalse(partitions.get(0) instanceof RandomAccess);
  assertFalse(partitions.get(1) instanceof RandomAccess);
}

@GwtIncompatible // ?
// TODO: Figure out why this is failing in GWT.
public void testPartitionRandomAccess() {
  Iterator<Integer> source = asList(1, 2, 3).iterator();
  Iterator<List<Integer>> partitions = Iterators.partition(source, 2);
  assertTrue(partitions.next() instanceof RandomAccess);
  assertTrue(partitions.next() instanceof RandomAccess);
}

public void testLeastOfIterable_simple_n_withNullElement() {
  List<Integer> list = Arrays.asList(3, 4, 5, null, -1);
  List<Integer> result = Ordering.natural().nullsLast().leastOf(list, list.size());
  assertTrue(result instanceof RandomAccess);
  assertListImmutable(result);
  assertEquals(Arrays.asList(-1, 3, 4, 5, null), result);
}

public void testLeastOfIterator_empty_0() {
  List<Integer> result = numberOrdering.leastOf(
      Iterators.<Integer>emptyIterator(), 0);
  assertTrue(result instanceof RandomAccess);
  assertListImmutable(result);
  assertEquals(ImmutableList.<Integer>of(), result);
}

public void testLeastOfIterator_empty_0() {
  List<Integer> result = numberOrdering.leastOf(
      Iterators.<Integer>emptyIterator(), 0);
  assertTrue(result instanceof RandomAccess);
  assertListImmutable(result);
  assertEquals(ImmutableList.<Integer>of(), result);
}

public void testLeastOfIterator_simple_0() {
  List<Integer> result = numberOrdering.leastOf(
      Iterators.forArray(3, 4, 5, -1), 0);
  assertTrue(result instanceof RandomAccess);
  assertListImmutable(result);
  assertEquals(ImmutableList.<Integer>of(), result);
}

public void testLeastOfIterator_simple_1() {
  List<Integer> result = numberOrdering.leastOf(
      Iterators.forArray(3, 4, 5, -1), 1);
  assertTrue(result instanceof RandomAccess);
  assertListImmutable(result);
  assertEquals(ImmutableList.of(-1), result);
}

public void testLeastOfIterable_simple_nMinusOne_withNullElement() {
  List<Integer> list = Arrays.asList(3, null, 5, -1);
  List<Integer> result = Ordering.natural().nullsLast().leastOf(list, list.size() - 1);
  assertTrue(result instanceof RandomAccess);
  assertListImmutable(result);
  assertEquals(ImmutableList.of(-1, 3, 5), result);
}

public void testLeastOfIterator_simple_nMinusOne_withNullElement() {
  Iterator<Integer> itr = Iterators.forArray(3, null, 5, -1);
  List<Integer> result = Ordering.natural().nullsLast().leastOf(itr, 3);
  assertTrue(result instanceof RandomAccess);
  assertListImmutable(result);
  assertEquals(ImmutableList.of(-1, 3, 5), result);
}

public void testLeastOfIterable_simple_nMinusOne() {
  List<Integer> list = Arrays.asList(3, 4, 5, -1);
  List<Integer> result = numberOrdering.leastOf(list, list.size() - 1);
  assertTrue(result instanceof RandomAccess);
  assertListImmutable(result);
  assertEquals(ImmutableList.of(-1, 3, 4), result);
}

public void testLeastOfIterator_simple_n() {
  List<Integer> list = Arrays.asList(3, 4, 5, -1);
  List<Integer> result = numberOrdering.leastOf(list.iterator(), list.size());
  assertTrue(result instanceof RandomAccess);
  assertListImmutable(result);
  assertEquals(ImmutableList.of(-1, 3, 4, 5), result);
}

/**
 * Confirm that replaceValues() returns a List implementing RandomAccess.
 */
public void testReplaceValuesRandomAccess() {
  Multimap<String, Integer> multimap = create();
  multimap.put("foo", 1);
  multimap.put("foo", 3);
  assertTrue(multimap.replaceValues("foo", asList(2, 4))
      instanceof RandomAccess);
  assertTrue(multimap.replaceValues("bar", asList(2, 4))
      instanceof RandomAccess);
}

public void testLeastOfIterable_simple_nPlusOne() {
  List<Integer> list = Arrays.asList(3, 4, 5, -1);
  List<Integer> result = numberOrdering.leastOf(list, list.size() + 1);
  assertTrue(result instanceof RandomAccess);
  assertListImmutable(result);
  assertEquals(ImmutableList.of(-1, 3, 4, 5), result);
}

public void testLeastOfIterable_simple_n() {
  List<Integer> list = Arrays.asList(3, 4, 5, -1);
  List<Integer> result = numberOrdering.leastOf(list, list.size());
  assertTrue(result instanceof RandomAccess);
  assertListImmutable(result);
  assertEquals(ImmutableList.of(-1, 3, 4, 5), result);
}

public void testLeastOfIterator_simple_nMinusOne_withNullElement() {
  Iterator<Integer> itr = Iterators.forArray(3, null, 5, -1);
  List<Integer> result = Ordering.natural().nullsLast().leastOf(itr, 3);
  assertTrue(result instanceof RandomAccess);
  assertListImmutable(result);
  assertEquals(ImmutableList.of(-1, 3, 5), result);
}

public void testLeastOfIterator_singleton_0() {
  List<Integer> result = numberOrdering.leastOf(
      Iterators.singletonIterator(3), 0);
  assertTrue(result instanceof RandomAccess);
  assertListImmutable(result);
  assertEquals(ImmutableList.<Integer>of(), result);
}

public void testPartitionRandomAccessFalse() {
  List<Integer> source = Lists.newLinkedList(asList(1, 2, 3));
  List<List<Integer>> partitions = Lists.partition(source, 2);
  assertFalse(partitions instanceof RandomAccess);
  assertFalse(partitions.get(0) instanceof RandomAccess);
  assertFalse(partitions.get(1) instanceof RandomAccess);
}

@GwtIncompatible // ?
// TODO: Figure out why this is failing in GWT.
public void testPartitionRandomAccessInput() {
  Iterable<Integer> source = asList(1, 2, 3);
  Iterable<List<Integer>> partitions = Iterables.partition(source, 2);
  Iterator<List<Integer>> iterator = partitions.iterator();
  assertTrue(iterator.next() instanceof RandomAccess);
  assertTrue(iterator.next() instanceof RandomAccess);
}

@GwtIncompatible // ?
// TODO: Figure out why this is failing in GWT.
public void testPartitionNonRandomAccessInput() {
  Iterable<Integer> source = Lists.newLinkedList(asList(1, 2, 3));
  Iterable<List<Integer>> partitions = Iterables.partition(source, 2);
  Iterator<List<Integer>> iterator = partitions.iterator();
  // Even though the input list doesn't implement RandomAccess, the output
  // lists do.
  assertTrue(iterator.next() instanceof RandomAccess);
  assertTrue(iterator.next() instanceof RandomAccess);
}

private static void writeParameters(List<CharSequence> parameters, ByteBuf out) {
  if (parameters.isEmpty()) {
    return;
  }

  out.writeByte(SP);

  if (parameters instanceof RandomAccess) {
    int sizeMinusOne = parameters.size() - 1;
    for (int i = 0; i < sizeMinusOne; i++) {
      ByteBufUtil.writeUtf8(out, parameters.get(i));
      out.writeByte(SP);
    }

    ByteBufUtil.writeUtf8(out, parameters.get(sizeMinusOne));

  } else {
    Iterator<CharSequence> params = parameters.iterator();
    while (true) {
      ByteBufUtil.writeUtf8(out, params.next());
      if (params.hasNext()) {
        out.writeByte(SP);
      } else {
        break;
      }
    }
  }
}

public void testPaddedPartitionNonRandomAccessInput() {
  Iterable<Integer> source = Lists.newLinkedList(asList(1, 2, 3));
  Iterable<List<Integer>> partitions = Iterables.paddedPartition(source, 2);
  Iterator<List<Integer>> iterator = partitions.iterator();
  // Even though the input list doesn't implement RandomAccess, the output
  // lists do.
  assertTrue(iterator.next() instanceof RandomAccess);
  assertTrue(iterator.next() instanceof RandomAccess);
}

public void testSynchronizedArrayListMultimapRandomAccess() {
  ListMultimap<String, Integer> delegate = ArrayListMultimap.create();
  delegate.put("foo", 1);
  delegate.put("foo", 3);
  ListMultimap<String, Integer> multimap
      = Multimaps.synchronizedListMultimap(delegate);
  assertTrue(multimap.get("foo") instanceof RandomAccess);
  assertTrue(multimap.get("bar") instanceof RandomAccess);
}

/**
 * Confirm that get() returns a List that doesn't implement RandomAccess.
 */
public void testGetRandomAccess() {
  Multimap<String, Integer> multimap = create();
  multimap.put("foo", 1);
  multimap.put("foo", 3);
  assertFalse(multimap.get("foo") instanceof RandomAccess);
  assertFalse(multimap.get("bar") instanceof RandomAccess);
}

public void testLeastOfIterator_simple_n_withNullElement() {
  List<Integer> list = Arrays.asList(3, 4, 5, null, -1);
  List<Integer> result = Ordering.natural().nullsLast().leastOf(
      list.iterator(), list.size());
  assertTrue(result instanceof RandomAccess);
  assertListImmutable(result);
  assertEquals(Arrays.asList(-1, 3, 4, 5, null), result);
}

public void testUnmodifiableArrayListMultimapRandomAccess() {
  ListMultimap<String, Integer> delegate = ArrayListMultimap.create();
  delegate.put("foo", 1);
  delegate.put("foo", 3);
  ListMultimap<String, Integer> multimap
      = Multimaps.unmodifiableListMultimap(delegate);
  assertTrue(multimap.get("foo") instanceof RandomAccess);
  assertTrue(multimap.get("bar") instanceof RandomAccess);
}

public void testLeastOfIterator_simple_nPlusOne() {
  List<Integer> list = Arrays.asList(3, 4, 5, -1);
  List<Integer> result = numberOrdering.leastOf(list.iterator(), list.size() + 1);
  assertTrue(result instanceof RandomAccess);
  assertListImmutable(result);
  assertEquals(ImmutableList.of(-1, 3, 4, 5), result);
}

/**
 * Confirm that removeAll() returns a List implementing RandomAccess.
 */
public void testRemoveAllRandomAccess() {
  Multimap<String, Integer> multimap = create();
  multimap.put("foo", 1);
  multimap.put("foo", 3);
  assertTrue(multimap.removeAll("foo") instanceof RandomAccess);
  assertTrue(multimap.removeAll("bar") instanceof RandomAccess);
}

/**
 * Searches the specified list for the specified object using the binary search algorithm. The
 * list must be sorted into ascending order according to the specified comparator (as by the
 * {@link Collections#sort(List, Comparator) Collections.sort(List, Comparator)} method), prior
 * to making this call. If it is not sorted, the results are undefined.
 *
 * <p>If there are elements in the list which compare as equal to the key, the choice of
 * {@link KeyPresentBehavior} decides which index is returned. If no elements compare as equal to
 * the key, the choice of {@link KeyAbsentBehavior} decides which index is returned.
 *
 * <p>This method runs in log(n) time on random-access lists, which offer near-constant-time
 * access to each list element.
 *
 * @param list the list to be searched.
 * @param key the value to be searched for.
 * @param comparator the comparator by which the list is ordered.
 * @param presentBehavior the specification for what to do if at least one element of the list
 *        compares as equal to the key.
 * @param absentBehavior the specification for what to do if no elements of the list compare as
 *        equal to the key.
 * @return the index determined by the {@code KeyPresentBehavior}, if the key is in the list;
 *         otherwise the index determined by the {@code KeyAbsentBehavior}.
 */
public static <E> int binarySearch(List<? extends E> list, @Nullable E key,
    Comparator<? super E> comparator, KeyPresentBehavior presentBehavior,
    KeyAbsentBehavior absentBehavior) {
  checkNotNull(comparator);
  checkNotNull(list);
  checkNotNull(presentBehavior);
  checkNotNull(absentBehavior);
  if (!(list instanceof RandomAccess)) {
    list = Lists.newArrayList(list);
  }
  // TODO(user): benchmark when it's best to do a linear search

  int lower = 0;
  int upper = list.size() - 1;

  while (lower <= upper) {
    int middle = (lower + upper) >>> 1;
    int c = comparator.compare(key, list.get(middle));
    if (c < 0) {
      upper = middle - 1;
    } else if (c > 0) {
      lower = middle + 1;
    } else {
      return lower + presentBehavior.resultIndex(
          comparator, key, list.subList(lower, upper + 1), middle - lower);
    }
  }
  return absentBehavior.resultIndex(lower);
}

@Override
public void visitDependencies(TaskDependencyResolveContext context) {
    if (values.isEmpty()) {
        return;
    }
    Deque<Object> queue = new ArrayDeque<Object>(values);
    while (!queue.isEmpty()) {
        Object dependency = queue.removeFirst();
        if (dependency instanceof Buildable) {
            context.add(dependency);
        } else if (dependency instanceof Task) {
            context.add(dependency);
        } else if (dependency instanceof TaskDependency) {
            context.add(dependency);
        } else if (dependency instanceof Closure) {
            Closure closure = (Closure) dependency;
            Object closureResult = closure.call(context.getTask());
            if (closureResult != null) {
                queue.addFirst(closureResult);
            }
        } else if (dependency instanceof RealizableTaskCollection) {
            RealizableTaskCollection realizableTaskCollection = (RealizableTaskCollection) dependency;
            realizableTaskCollection.realizeRuleTaskTypes();
            addAllFirst(queue, realizableTaskCollection.toArray());
        } else if (dependency instanceof List) {
            List<?> list = (List) dependency;
            if (list instanceof RandomAccess) {
                for (int i = list.size() - 1; i >= 0; i--) {
                    queue.addFirst(list.get(i));
                }
            } else {
                ListIterator<?> iterator = list.listIterator(list.size());
                while (iterator.hasPrevious()) {
                    Object item = iterator.previous();
                    queue.addFirst(item);
                }
            }
        } else if (dependency instanceof Iterable) {
            Iterable<?> iterable = (Iterable) dependency;
            addAllFirst(queue, toArray(iterable, Object.class));
        } else if (dependency instanceof Map) {
            Map<?, ?> map = (Map) dependency;
            addAllFirst(queue, map.values().toArray());
        } else if (dependency instanceof Object[]) {
            Object[] array = (Object[]) dependency;
            addAllFirst(queue, array);
        } else if (dependency instanceof Callable) {
            Callable callable = (Callable) dependency;
            Object callableResult = uncheckedCall(callable);
            if (callableResult != null) {
                queue.addFirst(callableResult);
            }
        } else if (resolver != null && dependency instanceof TaskReference) {
            context.add(resolver.resolveTask((TaskReference) dependency));
        } else if (resolver != null && dependency instanceof CharSequence) {
            context.add(resolver.resolveTask(dependency.toString()));
        } else {
            List<String> formats = new ArrayList<String>();
            if (resolver != null) {
                formats.add("A String or CharSequence task name or path");
                formats.add("A TaskReference instance");
            }
            formats.add("A Task instance");
            formats.add("A Buildable instance");
            formats.add("A TaskDependency instance");
            formats.add("A Closure instance that returns any of the above types");
            formats.add("A Callable instance that returns any of the above types");
            formats.add("An Iterable, Collection, Map or array instance that contains any of the above types");
            throw new UnsupportedNotationException(dependency, String.format("Cannot convert %s to a task.", dependency), null, formats);
        }
    }
}

public void testTransformSequential() {
  List<String> list = Lists.transform(SOME_SEQUENTIAL_LIST, SOME_FUNCTION);
  assertFalse(list instanceof RandomAccess);
}