Add Collections.rotate method emulation
The rotate method implementation based on the Android libcore
implementation picked from j2objc project.
Change-Id: I6b5564545e8112d6e3e1ef4192383969a9c67929
Improvement: issue 9140
diff --git a/user/super/com/google/gwt/emul/java/util/Collections.java b/user/super/com/google/gwt/emul/java/util/Collections.java
index c042f5b..8f6dd2b 100644
--- a/user/super/com/google/gwt/emul/java/util/Collections.java
+++ b/user/super/com/google/gwt/emul/java/util/Collections.java
@@ -1106,6 +1106,58 @@
};
}
+ /**
+ * Rotates the elements in {@code list} by the distance {@code dist}
+ * <p>
+ * e.g. for a given list with elements [1, 2, 3, 4, 5, 6, 7, 8, 9, 0], calling rotate(list, 3) or
+ * rotate(list, -7) would modify the list to look like this: [8, 9, 0, 1, 2, 3, 4, 5, 6, 7]
+ *
+ * @param lst the list whose elements are to be rotated.
+ * @param dist is the distance the list is rotated. This can be any valid integer. Negative values
+ * rotate the list backwards.
+ */
+ @SuppressWarnings("unchecked")
+ public static void rotate(List<?> lst, int dist) {
+ int size = lst.size();
+
+ // Rotating an empty collection results in the same empty collection
+ if (size == 0) {
+ return;
+ }
+
+ // Normalize the distance
+ int normdist = dist % size;
+ if (normdist == 0) {
+ return;
+ }
+ // Transform a rotation to the left into the equivalent rotation to the right.
+ if (normdist < 0) {
+ normdist += size;
+ }
+
+ if (lst instanceof RandomAccess) {
+ List<Object> list = (List<Object>) lst;
+ // Move each element to the new location.
+ Object temp = list.get(0);
+ int index = 0, beginIndex = 0;
+ for (int i = 0; i < size; i++) {
+ index = (index + normdist) % size;
+ temp = list.set(index, temp);
+ if (index == beginIndex) {
+ index = ++beginIndex;
+ temp = list.get(beginIndex);
+ }
+ }
+ } else {
+ int divideIndex = size - normdist;
+ List<?> sublist1 = lst.subList(0, divideIndex);
+ List<?> sublist2 = lst.subList(divideIndex, size);
+ reverse(sublist1);
+ reverse(sublist2);
+ reverse(lst);
+ }
+ }
+
public static <T> Set<T> singleton(T o) {
HashSet<T> set = new HashSet<T>(1);
set.add(o);
diff --git a/user/test/com/google/gwt/emultest/java/util/CollectionsTest.java b/user/test/com/google/gwt/emultest/java/util/CollectionsTest.java
index 4aae793..77c2e1a 100644
--- a/user/test/com/google/gwt/emultest/java/util/CollectionsTest.java
+++ b/user/test/com/google/gwt/emultest/java/util/CollectionsTest.java
@@ -1,12 +1,12 @@
/*
* Copyright 2008 Google Inc.
- *
+ *
* 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
@@ -15,8 +15,11 @@
*/
package com.google.gwt.emultest.java.util;
+import com.google.gwt.core.client.JavaScriptException;
+
import java.util.ArrayList;
import java.util.Arrays;
+import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
@@ -33,6 +36,10 @@
*/
public class CollectionsTest extends EmulTestBase {
+ private interface ListImplProvider {
+ List<Integer> copyOf(Collection<Integer> data);
+ }
+
public static List<Integer> createRandomList() {
ArrayList<Integer> l = new ArrayList<Integer>();
l.add(new Integer(5));
@@ -118,7 +125,7 @@
/**
* Test Collections.binarySearch(List, Object).
- *
+ *
* Verify the following cases: empty List odd numbers of elements even numbers
* of elements not found value larger than all elements not found value
* smaller than all elements
@@ -145,7 +152,7 @@
/**
* Test Collections.binarySearch(List, Object, Comparator).
- *
+ *
* Verify the following cases: empty List odd numbers of elements even numbers
* of elements not found value larger than all elements not found value
* smaller than all elements null Comparator uses natural ordering
@@ -276,6 +283,30 @@
assertEquals(b, createRandomList());
}
+ /**
+ * @tests java.util.Collections#rotate(java.util.List, int)
+ */
+ public void testRotate() {
+ try {
+ Collections.rotate(null, 0);
+ fail("Collections.rotate(null, distance) should throw NullPointerException");
+ } catch (NullPointerException | JavaScriptException expected) {
+ // Expected
+ }
+ // Test optimized RandomAccess code path
+ testRotateImpl(new ListImplProvider() {
+ public List<Integer> copyOf(Collection<Integer> data) {
+ return new ArrayList<>(data);
+ }
+ });
+ // Test sequential List code path
+ testRotateImpl(new ListImplProvider() {
+ public List<Integer> copyOf(Collection<Integer> data) {
+ return new LinkedList<>(data);
+ }
+ });
+ }
+
public void testSort() {
List<String> a = createSortedList();
Collections.reverse(a);
@@ -306,4 +337,35 @@
assertEquals(val, testArray[i]);
}
}
+
+ private void testRotateImpl(ListImplProvider listImpl) {
+ // rotating empty list should not throw exception
+ List<Integer> list = listImpl.copyOf(Collections.<Integer> emptyList());
+ Collections.rotate(list, 2);
+
+ List<Integer> original = Arrays.asList(0, 1, 2, 3, 4);
+ list = listImpl.copyOf(original);
+
+ Collections.rotate(list, 0);
+ assertEquals(original, list);
+
+ Collections.rotate(list, 3);
+ assertEquals(Arrays.asList(2, 3, 4, 0, 1), list);
+
+ Collections.rotate(list, list.size());
+ assertEquals(Arrays.asList(2, 3, 4, 0, 1), list);
+
+ Collections.rotate(list, list.size() + 3);
+ assertEquals(Arrays.asList(4, 0, 1, 2, 3), list);
+
+ Collections.rotate(list, -(list.size() + 3));
+ assertEquals(Arrays.asList(2, 3, 4, 0, 1), list);
+
+ Collections.rotate(list, -list.size());
+ assertEquals(Arrays.asList(2, 3, 4, 0, 1), list);
+
+ Collections.rotate(list, -3);
+ assertEquals(original, list);
+ }
+
}
