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); + } + }