1 /*
2  * Copyright (C) 2023 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package com.android.launcher3.celllayout;
17 
18 import static androidx.test.core.app.ApplicationProvider.getApplicationContext;
19 
20 import static org.junit.Assert.assertEquals;
21 import static org.junit.Assert.assertTrue;
22 
23 import android.content.Context;
24 import android.graphics.Point;
25 import android.util.Log;
26 import android.view.View;
27 
28 import androidx.test.ext.junit.runners.AndroidJUnit4;
29 import androidx.test.filters.SmallTest;
30 
31 import com.android.launcher3.CellLayout;
32 import com.android.launcher3.MultipageCellLayout;
33 import com.android.launcher3.celllayout.board.CellLayoutBoard;
34 import com.android.launcher3.celllayout.board.IconPoint;
35 import com.android.launcher3.celllayout.board.PermutedBoardComparator;
36 import com.android.launcher3.celllayout.board.WidgetRect;
37 import com.android.launcher3.celllayout.testgenerator.RandomBoardGenerator;
38 import com.android.launcher3.celllayout.testgenerator.RandomMultiBoardGenerator;
39 import com.android.launcher3.util.ActivityContextWrapper;
40 import com.android.launcher3.views.DoubleShadowBubbleTextView;
41 
42 import org.junit.Rule;
43 import org.junit.Test;
44 import org.junit.runner.RunWith;
45 
46 import java.io.IOException;
47 import java.util.ArrayList;
48 import java.util.Arrays;
49 import java.util.Comparator;
50 import java.util.Iterator;
51 import java.util.List;
52 import java.util.Random;
53 
54 @SmallTest
55 @RunWith(AndroidJUnit4.class)
56 public class ReorderAlgorithmUnitTest {
57 
58     private static final String TAG = "ReorderAlgorithmUnitTest";
59     private static final char MAIN_WIDGET_TYPE = 'z';
60 
61     // There is nothing special about this numbers, the random seed is just to be able to reproduce
62     // the test cases and the height and width is a random number similar to what users expect on
63     // their devices
64     private static final int SEED = 897;
65     private static final int MAX_BOARD_SIZE = 13;
66 
67     private static final int TOTAL_OF_CASES_GENERATED = 300;
68     private Context mApplicationContext;
69 
70     @Rule
71     public UnitTestCellLayoutBuilderRule mCellLayoutBuilder = new UnitTestCellLayoutBuilderRule();
72 
73     /**
74      * This test reads existing test cases and makes sure the CellLayout produces the same
75      * output for each of them for a given input.
76      */
77     @Test
testAllCases()78     public void testAllCases() throws IOException {
79         List<ReorderAlgorithmUnitTestCase> testCases = getTestCases(
80                 "ReorderAlgorithmUnitTest/reorder_algorithm_test_cases");
81         mApplicationContext = new ActivityContextWrapper(getApplicationContext());
82         List<Integer> failingCases = new ArrayList<>();
83         for (int i = 0; i < testCases.size(); i++) {
84             try {
85                 evaluateTestCase(testCases.get(i), false);
86             } catch (AssertionError e) {
87                 e.printStackTrace();
88                 failingCases.add(i);
89             }
90         }
91         assertEquals("Some test cases failed " + Arrays.toString(failingCases.toArray()), 0,
92                 failingCases.size());
93     }
94 
95     /**
96      * This test generates random CellLayout configurations and then try to reorder it and makes
97      * sure the result is a valid board meaning it didn't remove any widget or icon.
98      */
99     @Test
generateValidTests()100     public void generateValidTests() {
101         Random generator = new Random(SEED);
102         mApplicationContext = new ActivityContextWrapper(getApplicationContext());
103         for (int i = 0; i < TOTAL_OF_CASES_GENERATED; i++) {
104             // Using a new seed so that we can replicate the same test cases.
105             int seed = generator.nextInt();
106             Log.d(TAG, "Seed = " + seed);
107             ReorderAlgorithmUnitTestCase testCase = generateRandomTestCase(
108                     new RandomBoardGenerator(new Random(seed))
109             );
110             Log.d(TAG, "testCase = " + testCase);
111             assertTrue("invalid case " + i,
112                     validateIntegrity(testCase.startBoard, testCase.endBoard, testCase));
113         }
114     }
115 
116     /**
117      * Same as above but testing the Multipage CellLayout.
118      */
119     @Test
generateValidTests_Multi()120     public void generateValidTests_Multi() {
121         Random generator = new Random(SEED);
122         mApplicationContext = new ActivityContextWrapper(getApplicationContext());
123         for (int i = 0; i < TOTAL_OF_CASES_GENERATED; i++) {
124             // Using a new seed so that we can replicate the same test cases.
125             int seed = generator.nextInt();
126             Log.d(TAG, "Seed = " + seed);
127             ReorderAlgorithmUnitTestCase testCase = generateRandomTestCase(
128                     new RandomMultiBoardGenerator(new Random(seed))
129             );
130             Log.d(TAG, "testCase = " + testCase);
131             assertTrue("invalid case " + i,
132                     validateIntegrity(testCase.startBoard, testCase.endBoard, testCase));
133         }
134     }
135 
addViewInCellLayout(CellLayout cellLayout, int cellX, int cellY, int spanX, int spanY, boolean isWidget)136     private void addViewInCellLayout(CellLayout cellLayout, int cellX, int cellY, int spanX,
137             int spanY, boolean isWidget) {
138         View cell = isWidget ? new View(mApplicationContext) : new DoubleShadowBubbleTextView(
139                 mApplicationContext);
140         cell.setLayoutParams(new CellLayoutLayoutParams(cellX, cellY, spanX, spanY));
141         cellLayout.addViewToCellLayout(cell, -1, cell.getId(),
142                 (CellLayoutLayoutParams) cell.getLayoutParams(), true);
143     }
144 
solve(CellLayoutBoard board, int x, int y, int spanX, int spanY, int minSpanX, int minSpanY, boolean isMulti)145     public ItemConfiguration solve(CellLayoutBoard board, int x, int y, int spanX,
146             int spanY, int minSpanX, int minSpanY, boolean isMulti) {
147         CellLayout cl = mCellLayoutBuilder.createCellLayout(board.getWidth(), board.getHeight(),
148                 isMulti);
149 
150         // The views have to be sorted or the result can vary
151         board.getIcons()
152                 .stream()
153                 .map(IconPoint::getCoord)
154                 .sorted(Comparator.comparing(p -> ((Point) p).x).thenComparing(p -> ((Point) p).y))
155                 .forEach(p -> addViewInCellLayout(cl, p.x, p.y, 1, 1, false));
156         board.getWidgets()
157                 .stream()
158                 .sorted(Comparator
159                         .comparing(WidgetRect::getCellX)
160                         .thenComparing(WidgetRect::getCellY)
161                 ).forEach(
162                         widget -> addViewInCellLayout(cl, widget.getCellX(), widget.getCellY(),
163                                 widget.getSpanX(), widget.getSpanY(), true)
164                 );
165 
166         int[] testCaseXYinPixels = new int[2];
167         cl.regionToCenterPoint(x, y, spanX, spanY, testCaseXYinPixels);
168         ItemConfiguration configuration = new ItemConfiguration();
169         cl.copyCurrentStateToSolution(configuration);
170         ItemConfiguration solution = cl.createReorderAlgorithm()
171                 .calculateReorder(
172                         new ReorderParameters(
173                                 testCaseXYinPixels[0],
174                                 testCaseXYinPixels[1],
175                                 spanX,
176                                 spanY,
177                                 minSpanX,
178                                 minSpanY,
179                                 null,
180                                 configuration
181                         )
182                 );
183         if (solution == null) {
184             solution = new ItemConfiguration();
185             solution.isSolution = false;
186         }
187         if (!solution.isSolution) {
188             cl.copyCurrentStateToSolution(solution);
189             if (cl instanceof MultipageCellLayout) {
190                 solution =
191                         ((MultipageCellLayout) cl).createReorderAlgorithm().removeSeamFromSolution(
192                                 solution);
193             }
194             solution.isSolution = false;
195         }
196         return solution;
197     }
198 
boardFromSolution(ItemConfiguration solution, int width, int height)199     public CellLayoutBoard boardFromSolution(ItemConfiguration solution, int width,
200             int height) {
201         // Update the views with solution value
202         solution.map.forEach((key, val) -> key.setLayoutParams(
203                 new CellLayoutLayoutParams(val.cellX, val.cellY, val.spanX, val.spanY)));
204         CellLayoutBoard board = CellLayoutTestUtils.viewsToBoard(
205                 new ArrayList<>(solution.map.keySet()), width, height);
206         if (solution.isSolution) {
207             board.addWidget(solution.cellX, solution.cellY, solution.spanX, solution.spanY,
208                     MAIN_WIDGET_TYPE);
209         }
210         return board;
211     }
212 
evaluateTestCase(ReorderAlgorithmUnitTestCase testCase, boolean isMultiCellLayout)213     public void evaluateTestCase(ReorderAlgorithmUnitTestCase testCase, boolean isMultiCellLayout) {
214         ItemConfiguration solution = solve(testCase.startBoard, testCase.x, testCase.y,
215                 testCase.spanX, testCase.spanY, testCase.minSpanX, testCase.minSpanY,
216                 isMultiCellLayout);
217         assertEquals("should be a valid solution", solution.isSolution, testCase.isValidSolution);
218         Log.d(TAG, "test case:" + testCase);
219         if (testCase.isValidSolution) {
220             CellLayoutBoard finishBoard = boardFromSolution(solution,
221                     testCase.startBoard.getWidth(), testCase.startBoard.getHeight());
222             Log.d(TAG, "finishBoard case:" + finishBoard);
223             assertTrue("End result and test case result board doesn't match ",
224                     finishBoard.compareTo(testCase.endBoard) == 0);
225         }
226     }
227 
generateRandomTestCase( RandomBoardGenerator boardGenerator)228     private ReorderAlgorithmUnitTestCase generateRandomTestCase(
229             RandomBoardGenerator boardGenerator) {
230         ReorderAlgorithmUnitTestCase testCase = new ReorderAlgorithmUnitTestCase();
231 
232         boolean isMultiCellLayout = boardGenerator instanceof RandomMultiBoardGenerator;
233 
234         int width = isMultiCellLayout
235                 ? boardGenerator.getRandom(3, MAX_BOARD_SIZE / 2) * 2
236                 : boardGenerator.getRandom(3, MAX_BOARD_SIZE);
237         int height = boardGenerator.getRandom(3, MAX_BOARD_SIZE);
238 
239         int targetWidth = boardGenerator.getRandom(1, width - 2);
240         int targetHeight = boardGenerator.getRandom(1, height - 2);
241 
242         int minTargetWidth = boardGenerator.getRandom(1, targetWidth);
243         int minTargetHeight = boardGenerator.getRandom(1, targetHeight);
244 
245         int x = boardGenerator.getRandom(0, width - targetWidth);
246         int y = boardGenerator.getRandom(0, height - targetHeight);
247 
248         CellLayoutBoard board = boardGenerator.generateBoard(width, height,
249                 targetWidth * targetHeight);
250 
251         ItemConfiguration solution = solve(board, x, y, targetWidth, targetHeight,
252                 minTargetWidth, minTargetHeight, isMultiCellLayout);
253 
254         CellLayoutBoard finishBoard = boardFromSolution(solution, board.getWidth(),
255                 board.getHeight());
256 
257         testCase.startBoard = board;
258         testCase.endBoard = finishBoard;
259         testCase.isValidSolution = solution.isSolution;
260         testCase.x = x;
261         testCase.y = y;
262         testCase.spanX = targetWidth;
263         testCase.spanY = targetHeight;
264         testCase.minSpanX = minTargetWidth;
265         testCase.minSpanY = minTargetHeight;
266         testCase.type = solution.area() == 1 ? "icon" : "widget";
267 
268         return testCase;
269     }
270 
271     /**
272      * Makes sure the final solution has valid integrity meaning that the number and sizes of
273      * widgets is the expect and there are no missing widgets.
274      */
validateIntegrity(CellLayoutBoard startBoard, CellLayoutBoard finishBoard, ReorderAlgorithmUnitTestCase testCase)275     public boolean validateIntegrity(CellLayoutBoard startBoard, CellLayoutBoard finishBoard,
276             ReorderAlgorithmUnitTestCase testCase) {
277         if (!testCase.isValidSolution) {
278             // if we couldn't place the widget then the solution should be identical to the board
279             return startBoard.compareTo(finishBoard) == 0;
280         }
281         WidgetRect addedWidget = finishBoard.getWidgetOfType(MAIN_WIDGET_TYPE);
282         finishBoard.removeItem(MAIN_WIDGET_TYPE);
283         Comparator<CellLayoutBoard> comparator = new PermutedBoardComparator();
284         if (comparator.compare(startBoard, finishBoard) != 0) {
285             return false;
286         }
287         return addedWidget.getSpanX() >= testCase.minSpanX
288                 && addedWidget.getSpanY() >= testCase.minSpanY;
289     }
290 
getTestCases(String testPath)291     private static List<ReorderAlgorithmUnitTestCase> getTestCases(String testPath)
292             throws IOException {
293         List<ReorderAlgorithmUnitTestCase> cases = new ArrayList<>();
294         Iterator<CellLayoutTestCaseReader.TestSection> iterableSection =
295                 CellLayoutTestCaseReader.readFromFile(testPath).parse().iterator();
296         while (iterableSection.hasNext()) {
297             cases.add(ReorderAlgorithmUnitTestCase.readNextCase(iterableSection));
298         }
299         return cases;
300     }
301 }
302