Adjust the widgets fitting algorithm to mitigate over packing issue

If we are fitting more than one widgets / shortcuts on the same row,
we will only allow the total width to be n - 1 cells, where n is the
grid width in cells.

Test: Run WidgetsTableUtils robolectric test.
Bug: 189103942
Change-Id: I2f23cb08fe95d68562188cc7b1852d99d7093dc0
diff --git a/robolectric_tests/src/com/android/launcher3/widget/picker/util/WidgetsTableUtilsTest.java b/robolectric_tests/src/com/android/launcher3/widget/picker/util/WidgetsTableUtilsTest.java
index e68edd3..56d7d68 100644
--- a/robolectric_tests/src/com/android/launcher3/widget/picker/util/WidgetsTableUtilsTest.java
+++ b/robolectric_tests/src/com/android/launcher3/widget/picker/util/WidgetsTableUtilsTest.java
@@ -96,12 +96,12 @@
         List<ArrayList<WidgetItem>> widgetItemInTable = WidgetsTableUtils.groupWidgetItemsIntoTable(
                 widgetItems, /* maxSpansPerRow= */ 5);
 
-        // Row 0: 1x1, 2x2, 2x3
-        // Row 1: 2x4
+        // Row 0: 1x1, 2x2
+        // Row 1: 2x3, 2x4
         // Row 2: 4x4
         assertThat(widgetItemInTable).hasSize(3);
-        assertThat(widgetItemInTable.get(0)).containsExactly(mWidget1x1, mWidget2x2, mWidget2x3);
-        assertThat(widgetItemInTable.get(1)).containsExactly(mWidget2x4);
+        assertThat(widgetItemInTable.get(0)).containsExactly(mWidget1x1, mWidget2x2);
+        assertThat(widgetItemInTable.get(1)).containsExactly(mWidget2x3, mWidget2x4);
         assertThat(widgetItemInTable.get(2)).containsExactly(mWidget4x4);
     }
 
@@ -114,12 +114,14 @@
                 widgetItems, /* maxSpansPerRow= */ 4);
 
         // Row 0: 1x1, 2x2
-        // Row 1: 2x3, 2x4
-        // Row 2: 4x4
-        assertThat(widgetItemInTable).hasSize(3);
+        // Row 1: 2x3,
+        // Row 2: 2x4,
+        // Row 3: 4x4
+        assertThat(widgetItemInTable).hasSize(4);
         assertThat(widgetItemInTable.get(0)).containsExactly(mWidget1x1, mWidget2x2);
-        assertThat(widgetItemInTable.get(1)).containsExactly(mWidget2x3, mWidget2x4);
-        assertThat(widgetItemInTable.get(2)).containsExactly(mWidget4x4);
+        assertThat(widgetItemInTable.get(1)).containsExactly(mWidget2x3);
+        assertThat(widgetItemInTable.get(2)).containsExactly(mWidget2x4);
+        assertThat(widgetItemInTable.get(3)).containsExactly(mWidget4x4);
     }
 
     @Test
@@ -131,14 +133,16 @@
                 widgetItems, /* maxSpansPerRow= */ 4);
 
         // Row 0: 1x1, 2x2
-        // Row 1: 2x3, 2x4
-        // Row 2: 4x4
-        // Row 3: shortcut3, shortcut1, shortcut2
-        assertThat(widgetItemInTable).hasSize(4);
+        // Row 1: 2x3,
+        // Row 2: 2x4,
+        // Row 3: 4x4
+        // Row 4: shortcut3, shortcut1, shortcut2
+        assertThat(widgetItemInTable).hasSize(5);
         assertThat(widgetItemInTable.get(0)).containsExactly(mWidget1x1, mWidget2x2);
-        assertThat(widgetItemInTable.get(1)).containsExactly(mWidget2x3, mWidget2x4);
-        assertThat(widgetItemInTable.get(2)).containsExactly(mWidget4x4);
-        assertThat(widgetItemInTable.get(3)).containsExactly(mShortcut3, mShortcut2, mShortcut1);
+        assertThat(widgetItemInTable.get(1)).containsExactly(mWidget2x3);
+        assertThat(widgetItemInTable.get(2)).containsExactly(mWidget2x4);
+        assertThat(widgetItemInTable.get(3)).containsExactly(mWidget4x4);
+        assertThat(widgetItemInTable.get(4)).containsExactly(mShortcut3, mShortcut2, mShortcut1);
     }
 
     private void initTestWidgets() {
diff --git a/src/com/android/launcher3/widget/util/WidgetsTableUtils.java b/src/com/android/launcher3/widget/util/WidgetsTableUtils.java
index e73d661..7294a3a 100644
--- a/src/com/android/launcher3/widget/util/WidgetsTableUtils.java
+++ b/src/com/android/launcher3/widget/util/WidgetsTableUtils.java
@@ -52,9 +52,10 @@
      * <p>Grouping:
      * 1. Widgets and shortcuts never group together in the same row.
      * 2. The ordered widgets are grouped together in the same row until their total horizontal
-     *    spans exceed the {@code maxSpansPerRow}.
+     *    spans exceed the {@code maxSpansPerRow} - 1.
      * 3. The order shortcuts are grouped together in the same row until their total horizontal
-     *    spans exceed the {@code maxSpansPerRow}.
+     *    spans exceed the {@code maxSpansPerRow} - 1.
+     * 4. If there is only one widget in a row, its width may exceed the {@code maxSpansPerRow}.
      */
     public static List<ArrayList<WidgetItem>> groupWidgetItemsIntoTable(
             List<WidgetItem> widgetItems, final int maxSpansPerRow) {
@@ -70,10 +71,15 @@
             int numOfWidgetItems = widgetItemsAtRow.size();
             int totalHorizontalSpan = widgetItemsAtRow.stream().map(item -> item.spanX)
                     .reduce(/* default= */ 0, Integer::sum);
+            int totalHorizontalSpanAfterAddingWidget = widgetItem.spanX + totalHorizontalSpan;
             if (numOfWidgetItems == 0) {
                 widgetItemsAtRow.add(widgetItem);
-            } else if (widgetItem.spanX + totalHorizontalSpan <= maxSpansPerRow
-                    && widgetItem.hasSameType(widgetItemsAtRow.get(numOfWidgetItems - 1))) {
+            } else if (
+                    // The max spans per row is reduced by 1 to ensure we don't pack too many
+                    // 1xn widgets on the same row, which may reduce the space for rendering a
+                    // widget's description.
+                    totalHorizontalSpanAfterAddingWidget <= maxSpansPerRow - 1
+                            && widgetItem.hasSameType(widgetItemsAtRow.get(numOfWidgetItems - 1))) {
                 // Group items in the same row if
                 // 1. they are with the same type, i.e. a row can only have widgets or shortcuts but
                 //    never a mix of both.