1 /* 2 * Copyright (C) 2011 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 17 package android.widget; 18 19 import android.content.Context; 20 import android.content.res.TypedArray; 21 import android.graphics.Canvas; 22 import android.graphics.Color; 23 import android.graphics.Paint; 24 import android.util.AttributeSet; 25 import android.util.Log; 26 import android.util.Pair; 27 import android.view.Gravity; 28 import android.view.View; 29 import android.view.ViewGroup; 30 import com.android.internal.R; 31 32 import java.lang.reflect.Array; 33 import java.util.ArrayList; 34 import java.util.Arrays; 35 import java.util.HashMap; 36 import java.util.List; 37 import java.util.Map; 38 39 import static android.view.Gravity.*; 40 import static android.view.View.MeasureSpec.EXACTLY; 41 import static android.view.View.MeasureSpec.makeMeasureSpec; 42 import static java.lang.Math.max; 43 import static java.lang.Math.min; 44 45 /** 46 * A layout that places its children in a rectangular <em>grid</em>. 47 * <p> 48 * The grid is composed of a set of infinitely thin lines that separate the 49 * viewing area into <em>cells</em>. Throughout the API, grid lines are referenced 50 * by grid <em>indices</em>. A grid with {@code N} columns 51 * has {@code N + 1} grid indices that run from {@code 0} 52 * through {@code N} inclusive. Regardless of how GridLayout is 53 * configured, grid index {@code 0} is fixed to the leading edge of the 54 * container and grid index {@code N} is fixed to its trailing edge 55 * (after padding is taken into account). 56 * 57 * <h4>Row and Column Specs</h4> 58 * 59 * Children occupy one or more contiguous cells, as defined 60 * by their {@link GridLayout.LayoutParams#rowSpec rowSpec} and 61 * {@link GridLayout.LayoutParams#columnSpec columnSpec} layout parameters. 62 * Each spec defines the set of rows or columns that are to be 63 * occupied; and how children should be aligned within the resulting group of cells. 64 * Although cells do not normally overlap in a GridLayout, GridLayout does 65 * not prevent children being defined to occupy the same cell or group of cells. 66 * In this case however, there is no guarantee that children will not themselves 67 * overlap after the layout operation completes. 68 * 69 * <h4>Default Cell Assignment</h4> 70 * 71 * If a child does not specify the row and column indices of the cell it 72 * wishes to occupy, GridLayout assigns cell locations automatically using its: 73 * {@link GridLayout#setOrientation(int) orientation}, 74 * {@link GridLayout#setRowCount(int) rowCount} and 75 * {@link GridLayout#setColumnCount(int) columnCount} properties. 76 * 77 * <h4>Space</h4> 78 * 79 * Space between children may be specified either by using instances of the 80 * dedicated {@link Space} view or by setting the 81 * 82 * {@link ViewGroup.MarginLayoutParams#leftMargin leftMargin}, 83 * {@link ViewGroup.MarginLayoutParams#topMargin topMargin}, 84 * {@link ViewGroup.MarginLayoutParams#rightMargin rightMargin} and 85 * {@link ViewGroup.MarginLayoutParams#bottomMargin bottomMargin} 86 * 87 * layout parameters. When the 88 * {@link GridLayout#setUseDefaultMargins(boolean) useDefaultMargins} 89 * property is set, default margins around children are automatically 90 * allocated based on the prevailing UI style guide for the platform. 91 * Each of the margins so defined may be independently overridden by an assignment 92 * to the appropriate layout parameter. 93 * Default values will generally produce a reasonable spacing between components 94 * but values may change between different releases of the platform. 95 * 96 * <h4>Excess Space Distribution</h4> 97 * 98 * GridLayout's distribution of excess space is based on <em>priority</em> 99 * rather than <em>weight</em>. 100 * <p> 101 * A child's ability to stretch is inferred from the alignment properties of 102 * its row and column groups (which are typically set by setting the 103 * {@link LayoutParams#setGravity(int) gravity} property of the child's layout parameters). 104 * If alignment was defined along a given axis then the component 105 * is taken as <em>flexible</em> in that direction. If no alignment was set, 106 * the component is instead assumed to be <em>inflexible</em>. 107 * <p> 108 * Multiple components in the same row or column group are 109 * considered to act in <em>parallel</em>. Such a 110 * group is flexible only if <em>all</em> of the components 111 * within it are flexible. Row and column groups that sit either side of a common boundary 112 * are instead considered to act in <em>series</em>. The composite group made of these two 113 * elements is flexible if <em>one</em> of its elements is flexible. 114 * <p> 115 * To make a column stretch, make sure all of the components inside it define a 116 * gravity. To prevent a column from stretching, ensure that one of the components 117 * in the column does not define a gravity. 118 * <p> 119 * When the principle of flexibility does not provide complete disambiguation, 120 * GridLayout's algorithms favour rows and columns that are closer to its <em>right</em> 121 * and <em>bottom</em> edges. 122 * 123 * <h5>Limitations</h5> 124 * 125 * GridLayout does not provide support for the principle of <em>weight</em>, as defined in 126 * {@link LinearLayout.LayoutParams#weight}. In general, it is not therefore possible 127 * to configure a GridLayout to distribute excess space in non-trivial proportions between 128 * multiple rows or columns. 129 * <p> 130 * Some common use-cases may nevertheless be accommodated as follows. 131 * To place equal amounts of space around a component in a cell group; 132 * use {@link #CENTER} alignment (or {@link LayoutParams#setGravity(int) gravity}). 133 * For complete control over excess space distribution in a row or column; 134 * use a {@link LinearLayout} subview to hold the components in the associated cell group. 135 * When using either of these techniques, bear in mind that cell groups may be defined to overlap. 136 * <p> 137 * See {@link GridLayout.LayoutParams} for a full description of the 138 * layout parameters used by GridLayout. 139 * 140 * @attr ref android.R.styleable#GridLayout_orientation 141 * @attr ref android.R.styleable#GridLayout_rowCount 142 * @attr ref android.R.styleable#GridLayout_columnCount 143 * @attr ref android.R.styleable#GridLayout_useDefaultMargins 144 * @attr ref android.R.styleable#GridLayout_rowOrderPreserved 145 * @attr ref android.R.styleable#GridLayout_columnOrderPreserved 146 */ 147 public class GridLayout extends ViewGroup { 148 149 // Public constants 150 151 /** 152 * The horizontal orientation. 153 */ 154 public static final int HORIZONTAL = LinearLayout.HORIZONTAL; 155 156 /** 157 * The vertical orientation. 158 */ 159 public static final int VERTICAL = LinearLayout.VERTICAL; 160 161 /** 162 * The constant used to indicate that a value is undefined. 163 * Fields can use this value to indicate that their values 164 * have not yet been set. Similarly, methods can return this value 165 * to indicate that there is no suitable value that the implementation 166 * can return. 167 * The value used for the constant (currently {@link Integer#MIN_VALUE}) is 168 * intended to avoid confusion between valid values whose sign may not be known. 169 */ 170 public static final int UNDEFINED = Integer.MIN_VALUE; 171 172 /** 173 * This constant is an {@link #setAlignmentMode(int) alignmentMode}. 174 * When the {@code alignmentMode} is set to {@link #ALIGN_BOUNDS}, alignment 175 * is made between the edges of each component's raw 176 * view boundary: i.e. the area delimited by the component's: 177 * {@link android.view.View#getTop() top}, 178 * {@link android.view.View#getLeft() left}, 179 * {@link android.view.View#getBottom() bottom} and 180 * {@link android.view.View#getRight() right} properties. 181 * <p> 182 * For example, when {@code GridLayout} is in {@link #ALIGN_BOUNDS} mode, 183 * children that belong to a row group that uses {@link #TOP} alignment will 184 * all return the same value when their {@link android.view.View#getTop()} 185 * method is called. 186 * 187 * @see #setAlignmentMode(int) 188 */ 189 public static final int ALIGN_BOUNDS = 0; 190 191 /** 192 * This constant is an {@link #setAlignmentMode(int) alignmentMode}. 193 * When the {@code alignmentMode} is set to {@link #ALIGN_MARGINS}, 194 * the bounds of each view are extended outwards, according 195 * to their margins, before the edges of the resulting rectangle are aligned. 196 * <p> 197 * For example, when {@code GridLayout} is in {@link #ALIGN_MARGINS} mode, 198 * the quantity {@code top - layoutParams.topMargin} is the same for all children that 199 * belong to a row group that uses {@link #TOP} alignment. 200 * 201 * @see #setAlignmentMode(int) 202 */ 203 public static final int ALIGN_MARGINS = 1; 204 205 // Misc constants 206 207 static final String TAG = GridLayout.class.getName(); 208 static final boolean DEBUG = false; 209 static final int PRF = 1; 210 static final int MAX_SIZE = 100000; 211 static final int DEFAULT_CONTAINER_MARGIN = 0; 212 213 // Defaults 214 215 private static final int DEFAULT_ORIENTATION = HORIZONTAL; 216 private static final int DEFAULT_COUNT = UNDEFINED; 217 private static final boolean DEFAULT_USE_DEFAULT_MARGINS = false; 218 private static final boolean DEFAULT_ORDER_PRESERVED = true; 219 private static final int DEFAULT_ALIGNMENT_MODE = ALIGN_MARGINS; 220 221 // TypedArray indices 222 223 private static final int ORIENTATION = R.styleable.GridLayout_orientation; 224 private static final int ROW_COUNT = R.styleable.GridLayout_rowCount; 225 private static final int COLUMN_COUNT = R.styleable.GridLayout_columnCount; 226 private static final int USE_DEFAULT_MARGINS = R.styleable.GridLayout_useDefaultMargins; 227 private static final int ALIGNMENT_MODE = R.styleable.GridLayout_alignmentMode; 228 private static final int ROW_ORDER_PRESERVED = R.styleable.GridLayout_rowOrderPreserved; 229 private static final int COLUMN_ORDER_PRESERVED = R.styleable.GridLayout_columnOrderPreserved; 230 231 // Instance variables 232 233 final Axis horizontalAxis = new Axis(true); 234 final Axis verticalAxis = new Axis(false); 235 boolean layoutParamsValid = false; 236 int orientation = DEFAULT_ORIENTATION; 237 boolean useDefaultMargins = DEFAULT_USE_DEFAULT_MARGINS; 238 int alignmentMode = DEFAULT_ALIGNMENT_MODE; 239 int defaultGap; 240 241 // Constructors 242 243 /** 244 * {@inheritDoc} 245 */ 246 public GridLayout(Context context, AttributeSet attrs, int defStyle) { 247 super(context, attrs, defStyle); 248 if (DEBUG) { 249 setWillNotDraw(false); 250 } 251 defaultGap = context.getResources().getDimensionPixelOffset(R.dimen.default_gap); 252 TypedArray a = context.obtainStyledAttributes(attrs, R.styleable.GridLayout); 253 try { 254 setRowCount(a.getInt(ROW_COUNT, DEFAULT_COUNT)); 255 setColumnCount(a.getInt(COLUMN_COUNT, DEFAULT_COUNT)); 256 setOrientation(a.getInt(ORIENTATION, DEFAULT_ORIENTATION)); 257 setUseDefaultMargins(a.getBoolean(USE_DEFAULT_MARGINS, DEFAULT_USE_DEFAULT_MARGINS)); 258 setAlignmentMode(a.getInt(ALIGNMENT_MODE, DEFAULT_ALIGNMENT_MODE)); 259 setRowOrderPreserved(a.getBoolean(ROW_ORDER_PRESERVED, DEFAULT_ORDER_PRESERVED)); 260 setColumnOrderPreserved(a.getBoolean(COLUMN_ORDER_PRESERVED, DEFAULT_ORDER_PRESERVED)); 261 } finally { 262 a.recycle(); 263 } 264 } 265 266 /** 267 * {@inheritDoc} 268 */ 269 public GridLayout(Context context, AttributeSet attrs) { 270 this(context, attrs, 0); 271 } 272 273 /** 274 * {@inheritDoc} 275 */ 276 public GridLayout(Context context) { 277 //noinspection NullableProblems 278 this(context, null); 279 } 280 281 // Implementation 282 283 /** 284 * Returns the current orientation. 285 * 286 * @return either {@link #HORIZONTAL} or {@link #VERTICAL} 287 * 288 * @see #setOrientation(int) 289 * 290 * @attr ref android.R.styleable#GridLayout_orientation 291 */ 292 public int getOrientation() { 293 return orientation; 294 } 295 296 /** 297 * Orientation is used only to generate default row/column indices when 298 * they are not specified by a component's layout parameters. 299 * <p> 300 * The default value of this property is {@link #HORIZONTAL}. 301 * 302 * @param orientation either {@link #HORIZONTAL} or {@link #VERTICAL} 303 * 304 * @see #getOrientation() 305 * 306 * @attr ref android.R.styleable#GridLayout_orientation 307 */ 308 public void setOrientation(int orientation) { 309 if (this.orientation != orientation) { 310 this.orientation = orientation; 311 invalidateStructure(); 312 requestLayout(); 313 } 314 } 315 316 /** 317 * Returns the current number of rows. This is either the last value that was set 318 * with {@link #setRowCount(int)} or, if no such value was set, the maximum 319 * value of each the upper bounds defined in {@link LayoutParams#rowSpec}. 320 * 321 * @return the current number of rows 322 * 323 * @see #setRowCount(int) 324 * @see LayoutParams#rowSpec 325 * 326 * @attr ref android.R.styleable#GridLayout_rowCount 327 */ 328 public int getRowCount() { 329 return verticalAxis.getCount(); 330 } 331 332 /** 333 * RowCount is used only to generate default row/column indices when 334 * they are not specified by a component's layout parameters. 335 * 336 * @param rowCount the number of rows 337 * 338 * @see #getRowCount() 339 * @see LayoutParams#rowSpec 340 * 341 * @attr ref android.R.styleable#GridLayout_rowCount 342 */ 343 public void setRowCount(int rowCount) { 344 verticalAxis.setCount(rowCount); 345 invalidateStructure(); 346 requestLayout(); 347 } 348 349 /** 350 * Returns the current number of columns. This is either the last value that was set 351 * with {@link #setColumnCount(int)} or, if no such value was set, the maximum 352 * value of each the upper bounds defined in {@link LayoutParams#columnSpec}. 353 * 354 * @return the current number of columns 355 * 356 * @see #setColumnCount(int) 357 * @see LayoutParams#columnSpec 358 * 359 * @attr ref android.R.styleable#GridLayout_columnCount 360 */ 361 public int getColumnCount() { 362 return horizontalAxis.getCount(); 363 } 364 365 /** 366 * ColumnCount is used only to generate default column/column indices when 367 * they are not specified by a component's layout parameters. 368 * 369 * @param columnCount the number of columns. 370 * 371 * @see #getColumnCount() 372 * @see LayoutParams#columnSpec 373 * 374 * @attr ref android.R.styleable#GridLayout_columnCount 375 */ 376 public void setColumnCount(int columnCount) { 377 horizontalAxis.setCount(columnCount); 378 invalidateStructure(); 379 requestLayout(); 380 } 381 382 /** 383 * Returns whether or not this GridLayout will allocate default margins when no 384 * corresponding layout parameters are defined. 385 * 386 * @return {@code true} if default margins should be allocated 387 * 388 * @see #setUseDefaultMargins(boolean) 389 * 390 * @attr ref android.R.styleable#GridLayout_useDefaultMargins 391 */ 392 public boolean getUseDefaultMargins() { 393 return useDefaultMargins; 394 } 395 396 /** 397 * When {@code true}, GridLayout allocates default margins around children 398 * based on the child's visual characteristics. Each of the 399 * margins so defined may be independently overridden by an assignment 400 * to the appropriate layout parameter. 401 * <p> 402 * When {@code false}, the default value of all margins is zero. 403 * <p> 404 * When setting to {@code true}, consider setting the value of the 405 * {@link #setAlignmentMode(int) alignmentMode} 406 * property to {@link #ALIGN_BOUNDS}. 407 * <p> 408 * The default value of this property is {@code false}. 409 * 410 * @param useDefaultMargins use {@code true} to make GridLayout allocate default margins 411 * 412 * @see #getUseDefaultMargins() 413 * @see #setAlignmentMode(int) 414 * 415 * @see MarginLayoutParams#leftMargin 416 * @see MarginLayoutParams#topMargin 417 * @see MarginLayoutParams#rightMargin 418 * @see MarginLayoutParams#bottomMargin 419 * 420 * @attr ref android.R.styleable#GridLayout_useDefaultMargins 421 */ 422 public void setUseDefaultMargins(boolean useDefaultMargins) { 423 this.useDefaultMargins = useDefaultMargins; 424 requestLayout(); 425 } 426 427 /** 428 * Returns the alignment mode. 429 * 430 * @return the alignment mode; either {@link #ALIGN_BOUNDS} or {@link #ALIGN_MARGINS} 431 * 432 * @see #ALIGN_BOUNDS 433 * @see #ALIGN_MARGINS 434 * 435 * @see #setAlignmentMode(int) 436 * 437 * @attr ref android.R.styleable#GridLayout_alignmentMode 438 */ 439 public int getAlignmentMode() { 440 return alignmentMode; 441 } 442 443 /** 444 * Sets the alignment mode to be used for all of the alignments between the 445 * children of this container. 446 * <p> 447 * The default value of this property is {@link #ALIGN_MARGINS}. 448 * 449 * @param alignmentMode either {@link #ALIGN_BOUNDS} or {@link #ALIGN_MARGINS} 450 * 451 * @see #ALIGN_BOUNDS 452 * @see #ALIGN_MARGINS 453 * 454 * @see #getAlignmentMode() 455 * 456 * @attr ref android.R.styleable#GridLayout_alignmentMode 457 */ 458 public void setAlignmentMode(int alignmentMode) { 459 this.alignmentMode = alignmentMode; 460 requestLayout(); 461 } 462 463 /** 464 * Returns whether or not row boundaries are ordered by their grid indices. 465 * 466 * @return {@code true} if row boundaries must appear in the order of their indices, 467 * {@code false} otherwise 468 * 469 * @see #setRowOrderPreserved(boolean) 470 * 471 * @attr ref android.R.styleable#GridLayout_rowOrderPreserved 472 */ 473 public boolean isRowOrderPreserved() { 474 return verticalAxis.isOrderPreserved(); 475 } 476 477 /** 478 * When this property is {@code true}, GridLayout is forced to place the row boundaries 479 * so that their associated grid indices are in ascending order in the view. 480 * <p> 481 * When this property is {@code false} GridLayout is at liberty to place the vertical row 482 * boundaries in whatever order best fits the given constraints. 483 * <p> 484 * The default value of this property is {@code true}. 485 486 * @param rowOrderPreserved {@code true} to force GridLayout to respect the order 487 * of row boundaries 488 * 489 * @see #isRowOrderPreserved() 490 * 491 * @attr ref android.R.styleable#GridLayout_rowOrderPreserved 492 */ 493 public void setRowOrderPreserved(boolean rowOrderPreserved) { 494 verticalAxis.setOrderPreserved(rowOrderPreserved); 495 invalidateStructure(); 496 requestLayout(); 497 } 498 499 /** 500 * Returns whether or not column boundaries are ordered by their grid indices. 501 * 502 * @return {@code true} if column boundaries must appear in the order of their indices, 503 * {@code false} otherwise 504 * 505 * @see #setColumnOrderPreserved(boolean) 506 * 507 * @attr ref android.R.styleable#GridLayout_columnOrderPreserved 508 */ 509 public boolean isColumnOrderPreserved() { 510 return horizontalAxis.isOrderPreserved(); 511 } 512 513 /** 514 * When this property is {@code true}, GridLayout is forced to place the column boundaries 515 * so that their associated grid indices are in ascending order in the view. 516 * <p> 517 * When this property is {@code false} GridLayout is at liberty to place the horizontal column 518 * boundaries in whatever order best fits the given constraints. 519 * <p> 520 * The default value of this property is {@code true}. 521 * 522 * @param columnOrderPreserved use {@code true} to force GridLayout to respect the order 523 * of column boundaries. 524 * 525 * @see #isColumnOrderPreserved() 526 * 527 * @attr ref android.R.styleable#GridLayout_columnOrderPreserved 528 */ 529 public void setColumnOrderPreserved(boolean columnOrderPreserved) { 530 horizontalAxis.setOrderPreserved(columnOrderPreserved); 531 invalidateStructure(); 532 requestLayout(); 533 } 534 535 // Static utility methods 536 537 static int max2(int[] a, int valueIfEmpty) { 538 int result = valueIfEmpty; 539 for (int i = 0, N = a.length; i < N; i++) { 540 result = Math.max(result, a[i]); 541 } 542 return result; 543 } 544 545 @SuppressWarnings("unchecked") 546 static <T> T[] append(T[] a, T[] b) { 547 T[] result = (T[]) Array.newInstance(a.getClass().getComponentType(), a.length + b.length); 548 System.arraycopy(a, 0, result, 0, a.length); 549 System.arraycopy(b, 0, result, a.length, b.length); 550 return result; 551 } 552 553 static Alignment getAlignment(int gravity, boolean horizontal) { 554 int mask = horizontal ? HORIZONTAL_GRAVITY_MASK : VERTICAL_GRAVITY_MASK; 555 int shift = horizontal ? AXIS_X_SHIFT : AXIS_Y_SHIFT; 556 int flags = (gravity & mask) >> shift; 557 switch (flags) { 558 case (AXIS_SPECIFIED | AXIS_PULL_BEFORE): 559 return LEADING; 560 case (AXIS_SPECIFIED | AXIS_PULL_AFTER): 561 return TRAILING; 562 case (AXIS_SPECIFIED | AXIS_PULL_BEFORE | AXIS_PULL_AFTER): 563 return FILL; 564 case AXIS_SPECIFIED: 565 return CENTER; 566 default: 567 return UNDEFINED_ALIGNMENT; 568 } 569 } 570 571 /** @noinspection UnusedParameters*/ 572 private int getDefaultMargin(View c, boolean horizontal, boolean leading) { 573 if (c.getClass() == Space.class) { 574 return 0; 575 } 576 return defaultGap / 2; 577 } 578 579 private int getDefaultMargin(View c, boolean isAtEdge, boolean horizontal, boolean leading) { 580 return isAtEdge ? DEFAULT_CONTAINER_MARGIN : getDefaultMargin(c, horizontal, leading); 581 } 582 583 private int getDefaultMarginValue(View c, LayoutParams p, boolean horizontal, boolean leading) { 584 if (!useDefaultMargins) { 585 return 0; 586 } 587 Spec spec = horizontal ? p.columnSpec : p.rowSpec; 588 Axis axis = horizontal ? horizontalAxis : verticalAxis; 589 Interval span = spec.span; 590 boolean isAtEdge = leading ? (span.min == 0) : (span.max == axis.getCount()); 591 592 return getDefaultMargin(c, isAtEdge, horizontal, leading); 593 } 594 595 int getMargin1(View view, boolean horizontal, boolean leading) { 596 LayoutParams lp = getLayoutParams(view); 597 int margin = horizontal ? 598 (leading ? lp.leftMargin : lp.rightMargin) : 599 (leading ? lp.topMargin : lp.bottomMargin); 600 return margin == UNDEFINED ? getDefaultMarginValue(view, lp, horizontal, leading) : margin; 601 } 602 603 private int getMargin(View view, boolean horizontal, boolean leading) { 604 if (alignmentMode == ALIGN_MARGINS) { 605 return getMargin1(view, horizontal, leading); 606 } else { 607 Axis axis = horizontal ? horizontalAxis : verticalAxis; 608 int[] margins = leading ? axis.getLeadingMargins() : axis.getTrailingMargins(); 609 LayoutParams lp = getLayoutParams(view); 610 Spec spec = horizontal ? lp.columnSpec : lp.rowSpec; 611 int index = leading ? spec.span.min : spec.span.max; 612 return margins[index]; 613 } 614 } 615 616 private int getTotalMargin(View child, boolean horizontal) { 617 return getMargin(child, horizontal, true) + getMargin(child, horizontal, false); 618 } 619 620 private static boolean fits(int[] a, int value, int start, int end) { 621 if (end > a.length) { 622 return false; 623 } 624 for (int i = start; i < end; i++) { 625 if (a[i] > value) { 626 return false; 627 } 628 } 629 return true; 630 } 631 632 private static void procrusteanFill(int[] a, int start, int end, int value) { 633 int length = a.length; 634 Arrays.fill(a, Math.min(start, length), Math.min(end, length), value); 635 } 636 637 private static void setCellGroup(LayoutParams lp, int row, int rowSpan, int col, int colSpan) { 638 lp.setRowSpecSpan(new Interval(row, row + rowSpan)); 639 lp.setColumnSpecSpan(new Interval(col, col + colSpan)); 640 } 641 642 // Logic to avert infinite loops by ensuring that the cells can be placed somewhere. 643 private static int clip(Interval minorRange, boolean minorWasDefined, int count) { 644 int size = minorRange.size(); 645 if (count == 0) { 646 return size; 647 } 648 int min = minorWasDefined ? min(minorRange.min, count) : 0; 649 return min(size, count - min); 650 } 651 652 // install default indices for cells that don't define them 653 private void validateLayoutParams() { 654 final boolean horizontal = (orientation == HORIZONTAL); 655 final Axis axis = horizontal ? horizontalAxis : verticalAxis; 656 final int count = (axis.definedCount != UNDEFINED) ? axis.definedCount : 0; 657 658 int major = 0; 659 int minor = 0; 660 int[] maxSizes = new int[count]; 661 662 for (int i = 0, N = getChildCount(); i < N; i++) { 663 LayoutParams lp = getLayoutParams1(getChildAt(i)); 664 665 final Spec majorSpec = horizontal ? lp.rowSpec : lp.columnSpec; 666 final Interval majorRange = majorSpec.span; 667 final boolean majorWasDefined = majorSpec.startDefined; 668 final int majorSpan = majorRange.size(); 669 if (majorWasDefined) { 670 major = majorRange.min; 671 } 672 673 final Spec minorSpec = horizontal ? lp.columnSpec : lp.rowSpec; 674 final Interval minorRange = minorSpec.span; 675 final boolean minorWasDefined = minorSpec.startDefined; 676 final int minorSpan = clip(minorRange, minorWasDefined, count); 677 if (minorWasDefined) { 678 minor = minorRange.min; 679 } 680 681 if (count != 0) { 682 // Find suitable row/col values when at least one is undefined. 683 if (!majorWasDefined || !minorWasDefined) { 684 while (!fits(maxSizes, major, minor, minor + minorSpan)) { 685 if (minorWasDefined) { 686 major++; 687 } else { 688 if (minor + minorSpan <= count) { 689 minor++; 690 } else { 691 minor = 0; 692 major++; 693 } 694 } 695 } 696 } 697 procrusteanFill(maxSizes, minor, minor + minorSpan, major + majorSpan); 698 } 699 700 if (horizontal) { 701 setCellGroup(lp, major, majorSpan, minor, minorSpan); 702 } else { 703 setCellGroup(lp, minor, minorSpan, major, majorSpan); 704 } 705 706 minor = minor + minorSpan; 707 } 708 invalidateStructure(); 709 } 710 711 private void invalidateStructure() { 712 layoutParamsValid = false; 713 horizontalAxis.invalidateStructure(); 714 verticalAxis.invalidateStructure(); 715 // This can end up being done twice. Better twice than not at all. 716 invalidateValues(); 717 } 718 719 private void invalidateValues() { 720 // Need null check because requestLayout() is called in View's initializer, 721 // before we are set up. 722 if (horizontalAxis != null && verticalAxis != null) { 723 horizontalAxis.invalidateValues(); 724 verticalAxis.invalidateValues(); 725 } 726 } 727 728 private LayoutParams getLayoutParams1(View c) { 729 return (LayoutParams) c.getLayoutParams(); 730 } 731 732 final LayoutParams getLayoutParams(View c) { 733 if (!layoutParamsValid) { 734 validateLayoutParams(); 735 layoutParamsValid = true; 736 } 737 return getLayoutParams1(c); 738 } 739 740 @Override 741 protected LayoutParams generateDefaultLayoutParams() { 742 return new LayoutParams(); 743 } 744 745 @Override 746 public LayoutParams generateLayoutParams(AttributeSet attrs) { 747 return new LayoutParams(getContext(), attrs); 748 } 749 750 @Override 751 protected LayoutParams generateLayoutParams(ViewGroup.LayoutParams p) { 752 return new LayoutParams(p); 753 } 754 755 // Draw grid 756 757 private void drawLine(Canvas graphics, int x1, int y1, int x2, int y2, Paint paint) { 758 int dx = getPaddingLeft(); 759 int dy = getPaddingTop(); 760 graphics.drawLine(dx + x1, dy + y1, dx + x2, dy + y2, paint); 761 } 762 763 private static void drawRect(Canvas canvas, int x1, int y1, int x2, int y2, Paint paint) { 764 canvas.drawRect(x1, y1, x2 - 1, y2 - 1, paint); 765 } 766 767 @Override 768 protected void onDraw(Canvas canvas) { 769 super.onDraw(canvas); 770 771 if (DEBUG) { 772 int height = getHeight() - getPaddingTop() - getPaddingBottom(); 773 int width = getWidth() - getPaddingLeft() - getPaddingRight(); 774 775 Paint paint = new Paint(); 776 paint.setStyle(Paint.Style.STROKE); 777 paint.setColor(Color.argb(50, 255, 255, 255)); 778 779 int[] xs = horizontalAxis.locations; 780 if (xs != null) { 781 for (int i = 0, length = xs.length; i < length; i++) { 782 int x = xs[i]; 783 drawLine(canvas, x, 0, x, height - 1, paint); 784 } 785 } 786 787 int[] ys = verticalAxis.locations; 788 if (ys != null) { 789 for (int i = 0, length = ys.length; i < length; i++) { 790 int y = ys[i]; 791 drawLine(canvas, 0, y, width - 1, y, paint); 792 } 793 } 794 795 // Draw bounds 796 paint.setColor(Color.BLUE); 797 for (int i = 0; i < getChildCount(); i++) { 798 View c = getChildAt(i); 799 drawRect(canvas, c.getLeft(), c.getTop(), c.getRight(), c.getBottom(), paint); 800 } 801 802 // Draw margins 803 paint.setColor(Color.MAGENTA); 804 for (int i = 0; i < getChildCount(); i++) { 805 View c = getChildAt(i); 806 drawRect(canvas, 807 c.getLeft() - getMargin1(c, true, true), 808 c.getTop() - getMargin1(c, false, true), 809 c.getRight() + getMargin1(c, true, false), 810 c.getBottom() + getMargin1(c, false, false), paint); 811 } 812 } 813 } 814 815 // Add/remove 816 817 /** 818 * @hide 819 */ 820 @Override 821 protected void onViewAdded(View child) { 822 super.onViewAdded(child); 823 invalidateStructure(); 824 } 825 826 /** 827 * @hide 828 */ 829 @Override 830 protected void onViewRemoved(View child) { 831 super.onViewRemoved(child); 832 invalidateStructure(); 833 } 834 835 /** 836 * We need to call invalidateStructure() when a child's GONE flag changes state. 837 * This implementation is a catch-all, invalidating on any change in the visibility flags. 838 * 839 * @hide 840 */ 841 @Override 842 protected void onChildVisibilityChanged(View child, int visibility) { 843 super.onChildVisibilityChanged(child, visibility); 844 invalidateStructure(); 845 } 846 847 // Measurement 848 849 final boolean isGone(View c) { 850 return c.getVisibility() == View.GONE; 851 } 852 853 private void measureChildWithMargins2(View child, int parentWidthSpec, int parentHeightSpec, 854 int childWidth, int childHeight) { 855 int childWidthSpec = getChildMeasureSpec(parentWidthSpec, 856 mPaddingLeft + mPaddingRight + getTotalMargin(child, true), childWidth); 857 int childHeightSpec = getChildMeasureSpec(parentHeightSpec, 858 mPaddingTop + mPaddingBottom + getTotalMargin(child, false), childHeight); 859 child.measure(childWidthSpec, childHeightSpec); 860 } 861 862 private void measureChildrenWithMargins(int widthSpec, int heightSpec, boolean firstPass) { 863 for (int i = 0, N = getChildCount(); i < N; i++) { 864 View c = getChildAt(i); 865 if (isGone(c)) continue; 866 LayoutParams lp = getLayoutParams(c); 867 if (firstPass) { 868 measureChildWithMargins2(c, widthSpec, heightSpec, lp.width, lp.height); 869 } else { 870 boolean horizontal = (orientation == HORIZONTAL); 871 Spec spec = horizontal ? lp.columnSpec : lp.rowSpec; 872 if (spec.alignment == FILL) { 873 Interval span = spec.span; 874 Axis axis = horizontal ? horizontalAxis : verticalAxis; 875 int[] locations = axis.getLocations(); 876 int cellSize = locations[span.max] - locations[span.min]; 877 int viewSize = cellSize - getTotalMargin(c, horizontal); 878 if (horizontal) { 879 measureChildWithMargins2(c, widthSpec, heightSpec, viewSize, lp.height); 880 } else { 881 measureChildWithMargins2(c, widthSpec, heightSpec, lp.width, viewSize); 882 } 883 } 884 } 885 } 886 } 887 888 @Override 889 protected void onMeasure(int widthSpec, int heightSpec) { 890 /** If we have been called by {@link View#measure(int, int)}, one of width or height 891 * is likely to have changed. We must invalidate if so. */ 892 invalidateValues(); 893 894 measureChildrenWithMargins(widthSpec, heightSpec, true); 895 896 int width, height; 897 898 // Use the orientation property to decide which axis should be laid out first. 899 if (orientation == HORIZONTAL) { 900 width = horizontalAxis.getMeasure(widthSpec); 901 measureChildrenWithMargins(widthSpec, heightSpec, false); 902 height = verticalAxis.getMeasure(heightSpec); 903 } else { 904 height = verticalAxis.getMeasure(heightSpec); 905 measureChildrenWithMargins(widthSpec, heightSpec, false); 906 width = horizontalAxis.getMeasure(widthSpec); 907 } 908 909 int hPadding = getPaddingLeft() + getPaddingRight(); 910 int vPadding = getPaddingTop() + getPaddingBottom(); 911 912 int measuredWidth = Math.max(hPadding + width, getSuggestedMinimumWidth()); 913 int measuredHeight = Math.max(vPadding + height, getSuggestedMinimumHeight()); 914 915 setMeasuredDimension( 916 resolveSizeAndState(measuredWidth, widthSpec, 0), 917 resolveSizeAndState(measuredHeight, heightSpec, 0)); 918 } 919 920 private int protect(int alignment) { 921 return (alignment == UNDEFINED) ? 0 : alignment; 922 } 923 924 private int getMeasurement(View c, boolean horizontal) { 925 return horizontal ? c.getMeasuredWidth() : c.getMeasuredHeight(); 926 } 927 928 final int getMeasurementIncludingMargin(View c, boolean horizontal) { 929 if (isGone(c)) { 930 return 0; 931 } 932 return getMeasurement(c, horizontal) + getTotalMargin(c, horizontal); 933 } 934 935 @Override 936 public void requestLayout() { 937 super.requestLayout(); 938 invalidateValues(); 939 } 940 941 final Alignment getAlignment(Alignment alignment, boolean horizontal) { 942 return (alignment != UNDEFINED_ALIGNMENT) ? alignment : 943 (horizontal ? LEFT : BASELINE); 944 } 945 946 // Layout container 947 948 /** 949 * {@inheritDoc} 950 */ 951 /* 952 The layout operation is implemented by delegating the heavy lifting to the 953 to the mHorizontalAxis and mVerticalAxis instances of the internal Axis class. 954 Together they compute the locations of the vertical and horizontal lines of 955 the grid (respectively!). 956 957 This method is then left with the simpler task of applying margins, gravity 958 and sizing to each child view and then placing it in its cell. 959 */ 960 @Override 961 protected void onLayout(boolean changed, int left, int top, int right, int bottom) { 962 int targetWidth = right - left; 963 int targetHeight = bottom - top; 964 965 int paddingLeft = getPaddingLeft(); 966 int paddingTop = getPaddingTop(); 967 int paddingRight = getPaddingRight(); 968 int paddingBottom = getPaddingBottom(); 969 970 horizontalAxis.layout(targetWidth - paddingLeft - paddingRight); 971 verticalAxis.layout(targetHeight - paddingTop - paddingBottom); 972 973 int[] hLocations = horizontalAxis.getLocations(); 974 int[] vLocations = verticalAxis.getLocations(); 975 976 for (int i = 0, N = getChildCount(); i < N; i++) { 977 View c = getChildAt(i); 978 if (isGone(c)) continue; 979 LayoutParams lp = getLayoutParams(c); 980 Spec columnSpec = lp.columnSpec; 981 Spec rowSpec = lp.rowSpec; 982 983 Interval colSpan = columnSpec.span; 984 Interval rowSpan = rowSpec.span; 985 986 int x1 = hLocations[colSpan.min]; 987 int y1 = vLocations[rowSpan.min]; 988 989 int x2 = hLocations[colSpan.max]; 990 int y2 = vLocations[rowSpan.max]; 991 992 int cellWidth = x2 - x1; 993 int cellHeight = y2 - y1; 994 995 int pWidth = getMeasurement(c, true); 996 int pHeight = getMeasurement(c, false); 997 998 Alignment hAlign = getAlignment(columnSpec.alignment, true); 999 Alignment vAlign = getAlignment(rowSpec.alignment, false); 1000 1001 int dx, dy; 1002 1003 Bounds colBounds = horizontalAxis.getGroupBounds().getValue(i); 1004 Bounds rowBounds = verticalAxis.getGroupBounds().getValue(i); 1005 1006 // Gravity offsets: the location of the alignment group relative to its cell group. 1007 //noinspection NullableProblems 1008 int c2ax = protect(hAlign.getAlignmentValue(null, cellWidth - colBounds.size(true))); 1009 //noinspection NullableProblems 1010 int c2ay = protect(vAlign.getAlignmentValue(null, cellHeight - rowBounds.size(true))); 1011 1012 int leftMargin = getMargin(c, true, true); 1013 int topMargin = getMargin(c, false, true); 1014 int rightMargin = getMargin(c, true, false); 1015 int bottomMargin = getMargin(c, false, false); 1016 1017 // Same calculation as getMeasurementIncludingMargin() 1018 int mWidth = leftMargin + pWidth + rightMargin; 1019 int mHeight = topMargin + pHeight + bottomMargin; 1020 1021 // Alignment offsets: the location of the view relative to its alignment group. 1022 int a2vx = colBounds.getOffset(c, hAlign, mWidth); 1023 int a2vy = rowBounds.getOffset(c, vAlign, mHeight); 1024 1025 dx = c2ax + a2vx + leftMargin; 1026 dy = c2ay + a2vy + topMargin; 1027 1028 cellWidth -= leftMargin + rightMargin; 1029 cellHeight -= topMargin + bottomMargin; 1030 1031 int type = PRF; 1032 int width = hAlign.getSizeInCell(c, pWidth, cellWidth, type); 1033 int height = vAlign.getSizeInCell(c, pHeight, cellHeight, type); 1034 1035 int cx = paddingLeft + x1 + dx; 1036 int cy = paddingTop + y1 + dy; 1037 if (width != c.getMeasuredWidth() || height != c.getMeasuredHeight()) { 1038 c.measure(makeMeasureSpec(width, EXACTLY), makeMeasureSpec(height, EXACTLY)); 1039 } 1040 c.layout(cx, cy, cx + width, cy + height); 1041 } 1042 } 1043 1044 // Inner classes 1045 1046 /* 1047 This internal class houses the algorithm for computing the locations of grid lines; 1048 along either the horizontal or vertical axis. A GridLayout uses two instances of this class - 1049 distinguished by the "horizontal" flag which is true for the horizontal axis and false 1050 for the vertical one. 1051 */ 1052 final class Axis { 1053 private static final int NEW = 0; 1054 private static final int PENDING = 1; 1055 private static final int COMPLETE = 2; 1056 1057 public final boolean horizontal; 1058 1059 public int definedCount = UNDEFINED; 1060 private int maxIndex = UNDEFINED; 1061 1062 PackedMap<Spec, Bounds> groupBounds; 1063 public boolean groupBoundsValid = false; 1064 1065 PackedMap<Interval, MutableInt> forwardLinks; 1066 public boolean forwardLinksValid = false; 1067 1068 PackedMap<Interval, MutableInt> backwardLinks; 1069 public boolean backwardLinksValid = false; 1070 1071 public int[] leadingMargins; 1072 public boolean leadingMarginsValid = false; 1073 1074 public int[] trailingMargins; 1075 public boolean trailingMarginsValid = false; 1076 1077 public Arc[] arcs; 1078 public boolean arcsValid = false; 1079 1080 public int[] locations; 1081 public boolean locationsValid = false; 1082 1083 boolean orderPreserved = DEFAULT_ORDER_PRESERVED; 1084 1085 private MutableInt parentMin = new MutableInt(0); 1086 private MutableInt parentMax = new MutableInt(-MAX_SIZE); 1087 1088 private Axis(boolean horizontal) { 1089 this.horizontal = horizontal; 1090 } 1091 1092 private int calculateMaxIndex() { 1093 // the number Integer.MIN_VALUE + 1 comes up in undefined cells 1094 int result = -1; 1095 for (int i = 0, N = getChildCount(); i < N; i++) { 1096 View c = getChildAt(i); 1097 LayoutParams params = getLayoutParams(c); 1098 Spec spec = horizontal ? params.columnSpec : params.rowSpec; 1099 Interval span = spec.span; 1100 result = max(result, span.min); 1101 result = max(result, span.max); 1102 } 1103 return result == -1 ? UNDEFINED : result; 1104 } 1105 1106 private int getMaxIndex() { 1107 if (maxIndex == UNDEFINED) { 1108 maxIndex = max(0, calculateMaxIndex()); // use zero when there are no children 1109 } 1110 return maxIndex; 1111 } 1112 1113 public int getCount() { 1114 return max(definedCount, getMaxIndex()); 1115 } 1116 1117 public void setCount(int count) { 1118 this.definedCount = count; 1119 } 1120 1121 public boolean isOrderPreserved() { 1122 return orderPreserved; 1123 } 1124 1125 public void setOrderPreserved(boolean orderPreserved) { 1126 this.orderPreserved = orderPreserved; 1127 invalidateStructure(); 1128 } 1129 1130 private PackedMap<Spec, Bounds> createGroupBounds() { 1131 Assoc<Spec, Bounds> assoc = Assoc.of(Spec.class, Bounds.class); 1132 for (int i = 0, N = getChildCount(); i < N; i++) { 1133 View c = getChildAt(i); 1134 LayoutParams lp = getLayoutParams(c); 1135 Spec spec = horizontal ? lp.columnSpec : lp.rowSpec; 1136 Bounds bounds = getAlignment(spec.alignment, horizontal).getBounds(); 1137 assoc.put(spec, bounds); 1138 } 1139 return assoc.pack(); 1140 } 1141 1142 private void computeGroupBounds() { 1143 Bounds[] values = groupBounds.values; 1144 for (int i = 0; i < values.length; i++) { 1145 values[i].reset(); 1146 } 1147 for (int i = 0, N = getChildCount(); i < N; i++) { 1148 View c = getChildAt(i); 1149 LayoutParams lp = getLayoutParams(c); 1150 Spec spec = horizontal ? lp.columnSpec : lp.rowSpec; 1151 groupBounds.getValue(i).include(c, spec, GridLayout.this, this); 1152 } 1153 } 1154 1155 public PackedMap<Spec, Bounds> getGroupBounds() { 1156 if (groupBounds == null) { 1157 groupBounds = createGroupBounds(); 1158 } 1159 if (!groupBoundsValid) { 1160 computeGroupBounds(); 1161 groupBoundsValid = true; 1162 } 1163 return groupBounds; 1164 } 1165 1166 // Add values computed by alignment - taking the max of all alignments in each span 1167 private PackedMap<Interval, MutableInt> createLinks(boolean min) { 1168 Assoc<Interval, MutableInt> result = Assoc.of(Interval.class, MutableInt.class); 1169 Spec[] keys = getGroupBounds().keys; 1170 for (int i = 0, N = keys.length; i < N; i++) { 1171 Interval span = min ? keys[i].span : keys[i].span.inverse(); 1172 result.put(span, new MutableInt()); 1173 } 1174 return result.pack(); 1175 } 1176 1177 private void computeLinks(PackedMap<Interval, MutableInt> links, boolean min) { 1178 MutableInt[] spans = links.values; 1179 for (int i = 0; i < spans.length; i++) { 1180 spans[i].reset(); 1181 } 1182 1183 // Use getter to trigger a re-evaluation 1184 Bounds[] bounds = getGroupBounds().values; 1185 for (int i = 0; i < bounds.length; i++) { 1186 int size = bounds[i].size(min); 1187 MutableInt valueHolder = links.getValue(i); 1188 // this effectively takes the max() of the minima and the min() of the maxima 1189 valueHolder.value = max(valueHolder.value, min ? size : -size); 1190 } 1191 } 1192 1193 private PackedMap<Interval, MutableInt> getForwardLinks() { 1194 if (forwardLinks == null) { 1195 forwardLinks = createLinks(true); 1196 } 1197 if (!forwardLinksValid) { 1198 computeLinks(forwardLinks, true); 1199 forwardLinksValid = true; 1200 } 1201 return forwardLinks; 1202 } 1203 1204 private PackedMap<Interval, MutableInt> getBackwardLinks() { 1205 if (backwardLinks == null) { 1206 backwardLinks = createLinks(false); 1207 } 1208 if (!backwardLinksValid) { 1209 computeLinks(backwardLinks, false); 1210 backwardLinksValid = true; 1211 } 1212 return backwardLinks; 1213 } 1214 1215 private void include(List<Arc> arcs, Interval key, MutableInt size, 1216 boolean ignoreIfAlreadyPresent) { 1217 /* 1218 Remove self referential links. 1219 These appear: 1220 . as parental constraints when GridLayout has no children 1221 . when components have been marked as GONE 1222 */ 1223 if (key.size() == 0) { 1224 return; 1225 } 1226 // this bit below should really be computed outside here - 1227 // its just to stop default (row/col > 0) constraints obliterating valid entries 1228 if (ignoreIfAlreadyPresent) { 1229 for (Arc arc : arcs) { 1230 Interval span = arc.span; 1231 if (span.equals(key)) { 1232 return; 1233 } 1234 } 1235 } 1236 arcs.add(new Arc(key, size)); 1237 } 1238 1239 private void include(List<Arc> arcs, Interval key, MutableInt size) { 1240 include(arcs, key, size, true); 1241 } 1242 1243 // Group arcs by their first vertex, returning an array of arrays. 1244 // This is linear in the number of arcs. 1245 Arc[][] groupArcsByFirstVertex(Arc[] arcs) { 1246 int N = getCount() + 1; // the number of vertices 1247 Arc[][] result = new Arc[N][]; 1248 int[] sizes = new int[N]; 1249 for (Arc arc : arcs) { 1250 sizes[arc.span.min]++; 1251 } 1252 for (int i = 0; i < sizes.length; i++) { 1253 result[i] = new Arc[sizes[i]]; 1254 } 1255 // reuse the sizes array to hold the current last elements as we insert each arc 1256 Arrays.fill(sizes, 0); 1257 for (Arc arc : arcs) { 1258 int i = arc.span.min; 1259 result[i][sizes[i]++] = arc; 1260 } 1261 1262 return result; 1263 } 1264 1265 private Arc[] topologicalSort(final Arc[] arcs) { 1266 return new Object() { 1267 Arc[] result = new Arc[arcs.length]; 1268 int cursor = result.length - 1; 1269 Arc[][] arcsByVertex = groupArcsByFirstVertex(arcs); 1270 int[] visited = new int[getCount() + 1]; 1271 1272 void walk(int loc) { 1273 switch (visited[loc]) { 1274 case NEW: { 1275 visited[loc] = PENDING; 1276 for (Arc arc : arcsByVertex[loc]) { 1277 walk(arc.span.max); 1278 result[cursor--] = arc; 1279 } 1280 visited[loc] = COMPLETE; 1281 break; 1282 } 1283 case PENDING: { 1284 assert false; 1285 break; 1286 } 1287 case COMPLETE: { 1288 break; 1289 } 1290 } 1291 } 1292 1293 Arc[] sort() { 1294 for (int loc = 0, N = arcsByVertex.length; loc < N; loc++) { 1295 walk(loc); 1296 } 1297 assert cursor == -1; 1298 return result; 1299 } 1300 }.sort(); 1301 } 1302 1303 private Arc[] topologicalSort(List<Arc> arcs) { 1304 return topologicalSort(arcs.toArray(new Arc[arcs.size()])); 1305 } 1306 1307 private void addComponentSizes(List<Arc> result, PackedMap<Interval, MutableInt> links) { 1308 for (int i = 0; i < links.keys.length; i++) { 1309 Interval key = links.keys[i]; 1310 include(result, key, links.values[i], false); 1311 } 1312 } 1313 1314 private Arc[] createArcs() { 1315 List<Arc> mins = new ArrayList<Arc>(); 1316 List<Arc> maxs = new ArrayList<Arc>(); 1317 1318 // Add the minimum values from the components. 1319 addComponentSizes(mins, getForwardLinks()); 1320 // Add the maximum values from the components. 1321 addComponentSizes(maxs, getBackwardLinks()); 1322 1323 // Add ordering constraints to prevent row/col sizes from going negative 1324 if (orderPreserved) { 1325 // Add a constraint for every row/col 1326 for (int i = 0; i < getCount(); i++) { 1327 include(mins, new Interval(i, i + 1), new MutableInt(0)); 1328 } 1329 } 1330 1331 // Add the container constraints. Use the version of include that allows 1332 // duplicate entries in case a child spans the entire grid. 1333 int N = getCount(); 1334 include(mins, new Interval(0, N), parentMin, false); 1335 include(maxs, new Interval(N, 0), parentMax, false); 1336 1337 // Sort 1338 Arc[] sMins = topologicalSort(mins); 1339 Arc[] sMaxs = topologicalSort(maxs); 1340 1341 return append(sMins, sMaxs); 1342 } 1343 1344 private void computeArcs() { 1345 // getting the links validates the values that are shared by the arc list 1346 getForwardLinks(); 1347 getBackwardLinks(); 1348 } 1349 1350 public Arc[] getArcs() { 1351 if (arcs == null) { 1352 arcs = createArcs(); 1353 } 1354 if (!arcsValid) { 1355 computeArcs(); 1356 arcsValid = true; 1357 } 1358 return arcs; 1359 } 1360 1361 private boolean relax(int[] locations, Arc entry) { 1362 if (!entry.valid) { 1363 return false; 1364 } 1365 Interval span = entry.span; 1366 int u = span.min; 1367 int v = span.max; 1368 int value = entry.value.value; 1369 int candidate = locations[u] + value; 1370 if (candidate > locations[v]) { 1371 locations[v] = candidate; 1372 return true; 1373 } 1374 return false; 1375 } 1376 1377 private void init(int[] locations) { 1378 Arrays.fill(locations, 0); 1379 } 1380 1381 private String arcsToString(List<Arc> arcs) { 1382 String var = horizontal ? "x" : "y"; 1383 StringBuilder result = new StringBuilder(); 1384 boolean first = true; 1385 for (Arc arc : arcs) { 1386 if (first) { 1387 first = false; 1388 } else { 1389 result = result.append(", "); 1390 } 1391 int src = arc.span.min; 1392 int dst = arc.span.max; 1393 int value = arc.value.value; 1394 result.append((src < dst) ? 1395 var + dst + " - " + var + src + " > " + value : 1396 var + src + " - " + var + dst + " < " + -value); 1397 1398 } 1399 return result.toString(); 1400 } 1401 1402 private void logError(String axisName, Arc[] arcs, boolean[] culprits0) { 1403 List<Arc> culprits = new ArrayList<Arc>(); 1404 List<Arc> removed = new ArrayList<Arc>(); 1405 for (int c = 0; c < arcs.length; c++) { 1406 Arc arc = arcs[c]; 1407 if (culprits0[c]) { 1408 culprits.add(arc); 1409 } 1410 if (!arc.valid) { 1411 removed.add(arc); 1412 } 1413 } 1414 Log.d(TAG, axisName + " constraints: " + arcsToString(culprits) + " are inconsistent; " 1415 + "permanently removing: " + arcsToString(removed) + ". "); 1416 } 1417 1418 /* 1419 Bellman-Ford variant - modified to reduce typical running time from O(N^2) to O(N) 1420 1421 GridLayout converts its requirements into a system of linear constraints of the 1422 form: 1423 1424 x[i] - x[j] < a[k] 1425 1426 Where the x[i] are variables and the a[k] are constants. 1427 1428 For example, if the variables were instead labeled x, y, z we might have: 1429 1430 x - y < 17 1431 y - z < 23 1432 z - x < 42 1433 1434 This is a special case of the Linear Programming problem that is, in turn, 1435 equivalent to the single-source shortest paths problem on a digraph, for 1436 which the O(n^2) Bellman-Ford algorithm the most commonly used general solution. 1437 1438 Other algorithms are faster in the case where no arcs have negative weights 1439 but allowing negative weights turns out to be the same as accommodating maximum 1440 size requirements as well as minimum ones. 1441 1442 Bellman-Ford works by iteratively 'relaxing' constraints over all nodes (an O(N) 1443 process) and performing this step N times. Proof of correctness hinges on the 1444 fact that there can be no negative weight chains of length > N - unless a 1445 'negative weight loop' exists. The algorithm catches this case in a final 1446 checking phase that reports failure. 1447 1448 By topologically sorting the nodes and checking this condition at each step 1449 typical layout problems complete after the first iteration and the algorithm 1450 completes in O(N) steps with very low constants. 1451 */ 1452 private void solve(Arc[] arcs, int[] locations) { 1453 String axisName = horizontal ? "horizontal" : "vertical"; 1454 int N = getCount() + 1; // The number of vertices is the number of columns/rows + 1. 1455 boolean[] originalCulprits = null; 1456 1457 for (int p = 0; p < arcs.length; p++) { 1458 init(locations); 1459 1460 // We take one extra pass over traditional Bellman-Ford (and omit their final step) 1461 for (int i = 0; i < N; i++) { 1462 boolean changed = false; 1463 for (int j = 0, length = arcs.length; j < length; j++) { 1464 changed |= relax(locations, arcs[j]); 1465 } 1466 if (!changed) { 1467 if (originalCulprits != null) { 1468 logError(axisName, arcs, originalCulprits); 1469 } 1470 return; 1471 } 1472 } 1473 1474 boolean[] culprits = new boolean[arcs.length]; 1475 for (int i = 0; i < N; i++) { 1476 for (int j = 0, length = arcs.length; j < length; j++) { 1477 culprits[j] |= relax(locations, arcs[j]); 1478 } 1479 } 1480 1481 if (p == 0) { 1482 originalCulprits = culprits; 1483 } 1484 1485 for (int i = 0; i < arcs.length; i++) { 1486 if (culprits[i]) { 1487 Arc arc = arcs[i]; 1488 // Only remove max values, min values alone cannot be inconsistent 1489 if (arc.span.min < arc.span.max) { 1490 continue; 1491 } 1492 arc.valid = false; 1493 break; 1494 } 1495 } 1496 } 1497 } 1498 1499 private void computeMargins(boolean leading) { 1500 int[] margins = leading ? leadingMargins : trailingMargins; 1501 for (int i = 0, N = getChildCount(); i < N; i++) { 1502 View c = getChildAt(i); 1503 if (isGone(c)) continue; 1504 LayoutParams lp = getLayoutParams(c); 1505 Spec spec = horizontal ? lp.columnSpec : lp.rowSpec; 1506 Interval span = spec.span; 1507 int index = leading ? span.min : span.max; 1508 margins[index] = max(margins[index], getMargin1(c, horizontal, leading)); 1509 } 1510 } 1511 1512 // External entry points 1513 1514 public int[] getLeadingMargins() { 1515 if (leadingMargins == null) { 1516 leadingMargins = new int[getCount() + 1]; 1517 } 1518 if (!leadingMarginsValid) { 1519 computeMargins(true); 1520 leadingMarginsValid = true; 1521 } 1522 return leadingMargins; 1523 } 1524 1525 public int[] getTrailingMargins() { 1526 if (trailingMargins == null) { 1527 trailingMargins = new int[getCount() + 1]; 1528 } 1529 if (!trailingMarginsValid) { 1530 computeMargins(false); 1531 trailingMarginsValid = true; 1532 } 1533 return trailingMargins; 1534 } 1535 1536 private void computeLocations(int[] a) { 1537 solve(getArcs(), a); 1538 if (!orderPreserved) { 1539 // Solve returns the smallest solution to the constraint system for which all 1540 // values are positive. One value is therefore zero - though if the row/col 1541 // order is not preserved this may not be the first vertex. For consistency, 1542 // translate all the values so that they measure the distance from a[0]; the 1543 // leading edge of the parent. After this transformation some values may be 1544 // negative. 1545 int a0 = a[0]; 1546 for (int i = 0, N = a.length; i < N; i++) { 1547 a[i] = a[i] - a0; 1548 } 1549 } 1550 } 1551 1552 public int[] getLocations() { 1553 if (locations == null) { 1554 int N = getCount() + 1; 1555 locations = new int[N]; 1556 } 1557 if (!locationsValid) { 1558 computeLocations(locations); 1559 locationsValid = true; 1560 } 1561 return locations; 1562 } 1563 1564 private int size(int[] locations) { 1565 // The parental edges are attached to vertices 0 and N - even when order is not 1566 // being preserved and other vertices fall outside this range. Measure the distance 1567 // between vertices 0 and N, assuming that locations[0] = 0. 1568 return locations[getCount()]; 1569 } 1570 1571 private void setParentConstraints(int min, int max) { 1572 parentMin.value = min; 1573 parentMax.value = -max; 1574 locationsValid = false; 1575 } 1576 1577 private int getMeasure(int min, int max) { 1578 setParentConstraints(min, max); 1579 return size(getLocations()); 1580 } 1581 1582 public int getMeasure(int measureSpec) { 1583 int mode = MeasureSpec.getMode(measureSpec); 1584 int size = MeasureSpec.getSize(measureSpec); 1585 switch (mode) { 1586 case MeasureSpec.UNSPECIFIED: { 1587 return getMeasure(0, MAX_SIZE); 1588 } 1589 case MeasureSpec.EXACTLY: { 1590 return getMeasure(size, size); 1591 } 1592 case MeasureSpec.AT_MOST: { 1593 return getMeasure(0, size); 1594 } 1595 default: { 1596 assert false; 1597 return 0; 1598 } 1599 } 1600 } 1601 1602 public void layout(int size) { 1603 setParentConstraints(size, size); 1604 getLocations(); 1605 } 1606 1607 public void invalidateStructure() { 1608 maxIndex = UNDEFINED; 1609 1610 groupBounds = null; 1611 forwardLinks = null; 1612 backwardLinks = null; 1613 1614 leadingMargins = null; 1615 trailingMargins = null; 1616 arcs = null; 1617 1618 locations = null; 1619 1620 invalidateValues(); 1621 } 1622 1623 public void invalidateValues() { 1624 groupBoundsValid = false; 1625 forwardLinksValid = false; 1626 backwardLinksValid = false; 1627 1628 leadingMarginsValid = false; 1629 trailingMarginsValid = false; 1630 arcsValid = false; 1631 1632 locationsValid = false; 1633 } 1634 } 1635 1636 /** 1637 * Layout information associated with each of the children of a GridLayout. 1638 * <p> 1639 * GridLayout supports both row and column spanning and arbitrary forms of alignment within 1640 * each cell group. The fundamental parameters associated with each cell group are 1641 * gathered into their vertical and horizontal components and stored 1642 * in the {@link #rowSpec} and {@link #columnSpec} layout parameters. 1643 * {@link android.widget.GridLayout.Spec Specs} are immutable structures 1644 * and may be shared between the layout parameters of different children. 1645 * <p> 1646 * The row and column specs contain the leading and trailing indices along each axis 1647 * and together specify the four grid indices that delimit the cells of this cell group. 1648 * <p> 1649 * The alignment properties of the row and column specs together specify 1650 * both aspects of alignment within the cell group. It is also possible to specify a child's 1651 * alignment within its cell group by using the {@link GridLayout.LayoutParams#setGravity(int)} 1652 * method. 1653 * 1654 * <h4>WRAP_CONTENT and MATCH_PARENT</h4> 1655 * 1656 * Because the default values of the {@link #width} and {@link #height} 1657 * properties are both {@link #WRAP_CONTENT}, this value never needs to be explicitly 1658 * declared in the layout parameters of GridLayout's children. In addition, 1659 * GridLayout does not distinguish the special size value {@link #MATCH_PARENT} from 1660 * {@link #WRAP_CONTENT}. A component's ability to expand to the size of the parent is 1661 * instead controlled by the principle of <em>flexibility</em>, 1662 * as discussed in {@link GridLayout}. 1663 * 1664 * <h4>Summary</h4> 1665 * 1666 * You should not need to use either of the special size values: 1667 * {@code WRAP_CONTENT} or {@code MATCH_PARENT} when configuring the children of 1668 * a GridLayout. 1669 * 1670 * <h4>Default values</h4> 1671 * 1672 * <ul> 1673 * <li>{@link #width} = {@link #WRAP_CONTENT}</li> 1674 * <li>{@link #height} = {@link #WRAP_CONTENT}</li> 1675 * <li>{@link #topMargin} = 0 when 1676 * {@link GridLayout#setUseDefaultMargins(boolean) useDefaultMargins} is 1677 * {@code false}; otherwise {@link #UNDEFINED}, to 1678 * indicate that a default value should be computed on demand. </li> 1679 * <li>{@link #leftMargin} = 0 when 1680 * {@link GridLayout#setUseDefaultMargins(boolean) useDefaultMargins} is 1681 * {@code false}; otherwise {@link #UNDEFINED}, to 1682 * indicate that a default value should be computed on demand. </li> 1683 * <li>{@link #bottomMargin} = 0 when 1684 * {@link GridLayout#setUseDefaultMargins(boolean) useDefaultMargins} is 1685 * {@code false}; otherwise {@link #UNDEFINED}, to 1686 * indicate that a default value should be computed on demand. </li> 1687 * <li>{@link #rightMargin} = 0 when 1688 * {@link GridLayout#setUseDefaultMargins(boolean) useDefaultMargins} is 1689 * {@code false}; otherwise {@link #UNDEFINED}, to 1690 * indicate that a default value should be computed on demand. </li> 1691 * <li>{@link #rowSpec}<code>.row</code> = {@link #UNDEFINED} </li> 1692 * <li>{@link #rowSpec}<code>.rowSpan</code> = 1 </li> 1693 * <li>{@link #rowSpec}<code>.alignment</code> = {@link #BASELINE} </li> 1694 * <li>{@link #columnSpec}<code>.column</code> = {@link #UNDEFINED} </li> 1695 * <li>{@link #columnSpec}<code>.columnSpan</code> = 1 </li> 1696 * <li>{@link #columnSpec}<code>.alignment</code> = {@link #LEFT} </li> 1697 * </ul> 1698 * 1699 * See {@link GridLayout} for a more complete description of the conventions 1700 * used by GridLayout in the interpretation of the properties of this class. 1701 * 1702 * @attr ref android.R.styleable#GridLayout_Layout_layout_row 1703 * @attr ref android.R.styleable#GridLayout_Layout_layout_rowSpan 1704 * @attr ref android.R.styleable#GridLayout_Layout_layout_column 1705 * @attr ref android.R.styleable#GridLayout_Layout_layout_columnSpan 1706 * @attr ref android.R.styleable#GridLayout_Layout_layout_gravity 1707 */ 1708 public static class LayoutParams extends MarginLayoutParams { 1709 1710 // Default values 1711 1712 private static final int DEFAULT_WIDTH = WRAP_CONTENT; 1713 private static final int DEFAULT_HEIGHT = WRAP_CONTENT; 1714 private static final int DEFAULT_MARGIN = UNDEFINED; 1715 private static final int DEFAULT_ROW = UNDEFINED; 1716 private static final int DEFAULT_COLUMN = UNDEFINED; 1717 private static final Interval DEFAULT_SPAN = new Interval(UNDEFINED, UNDEFINED + 1); 1718 private static final int DEFAULT_SPAN_SIZE = DEFAULT_SPAN.size(); 1719 1720 // TypedArray indices 1721 1722 private static final int MARGIN = R.styleable.ViewGroup_MarginLayout_layout_margin; 1723 private static final int LEFT_MARGIN = R.styleable.ViewGroup_MarginLayout_layout_marginLeft; 1724 private static final int TOP_MARGIN = R.styleable.ViewGroup_MarginLayout_layout_marginTop; 1725 private static final int RIGHT_MARGIN = 1726 R.styleable.ViewGroup_MarginLayout_layout_marginRight; 1727 private static final int BOTTOM_MARGIN = 1728 R.styleable.ViewGroup_MarginLayout_layout_marginBottom; 1729 1730 private static final int COLUMN = R.styleable.GridLayout_Layout_layout_column; 1731 private static final int COLUMN_SPAN = R.styleable.GridLayout_Layout_layout_columnSpan; 1732 1733 private static final int ROW = R.styleable.GridLayout_Layout_layout_row; 1734 private static final int ROW_SPAN = R.styleable.GridLayout_Layout_layout_rowSpan; 1735 1736 private static final int GRAVITY = R.styleable.GridLayout_Layout_layout_gravity; 1737 1738 // Instance variables 1739 1740 /** 1741 * The spec that defines the vertical characteristics of the cell group 1742 * described by these layout parameters. 1743 */ 1744 public Spec rowSpec = Spec.UNDEFINED; 1745 1746 /** 1747 * The spec that defines the horizontal characteristics of the cell group 1748 * described by these layout parameters. 1749 */ 1750 public Spec columnSpec = Spec.UNDEFINED; 1751 1752 // Constructors 1753 1754 private LayoutParams( 1755 int width, int height, 1756 int left, int top, int right, int bottom, 1757 Spec rowSpec, Spec columnSpec) { 1758 super(width, height); 1759 setMargins(left, top, right, bottom); 1760 this.rowSpec = rowSpec; 1761 this.columnSpec = columnSpec; 1762 } 1763 1764 /** 1765 * Constructs a new LayoutParams instance for this <code>rowSpec</code> 1766 * and <code>columnSpec</code>. All other fields are initialized with 1767 * default values as defined in {@link LayoutParams}. 1768 * 1769 * @param rowSpec the rowSpec 1770 * @param columnSpec the columnSpec 1771 */ 1772 public LayoutParams(Spec rowSpec, Spec columnSpec) { 1773 this(DEFAULT_WIDTH, DEFAULT_HEIGHT, 1774 DEFAULT_MARGIN, DEFAULT_MARGIN, DEFAULT_MARGIN, DEFAULT_MARGIN, 1775 rowSpec, columnSpec); 1776 } 1777 1778 /** 1779 * Constructs a new LayoutParams with default values as defined in {@link LayoutParams}. 1780 */ 1781 public LayoutParams() { 1782 this(Spec.UNDEFINED, Spec.UNDEFINED); 1783 } 1784 1785 // Copying constructors 1786 1787 /** 1788 * {@inheritDoc} 1789 */ 1790 public LayoutParams(ViewGroup.LayoutParams params) { 1791 super(params); 1792 } 1793 1794 /** 1795 * {@inheritDoc} 1796 */ 1797 public LayoutParams(MarginLayoutParams params) { 1798 super(params); 1799 } 1800 1801 /** 1802 * {@inheritDoc} 1803 */ 1804 public LayoutParams(LayoutParams that) { 1805 super(that); 1806 this.rowSpec = that.rowSpec; 1807 this.columnSpec = that.columnSpec; 1808 } 1809 1810 // AttributeSet constructors 1811 1812 /** 1813 * {@inheritDoc} 1814 * 1815 * Values not defined in the attribute set take the default values 1816 * defined in {@link LayoutParams}. 1817 */ 1818 public LayoutParams(Context context, AttributeSet attrs) { 1819 super(context, attrs); 1820 reInitSuper(context, attrs); 1821 init(context, attrs); 1822 } 1823 1824 // Implementation 1825 1826 // Reinitialise the margins using a different default policy than MarginLayoutParams. 1827 // Here we use the value UNDEFINED (as distinct from zero) to represent the undefined state 1828 // so that a layout manager default can be accessed post set up. We need this as, at the 1829 // point of installation, we do not know how many rows/cols there are and therefore 1830 // which elements are positioned next to the container's trailing edges. We need to 1831 // know this as margins around the container's boundary should have different 1832 // defaults to those between peers. 1833 1834 // This method could be parametrized and moved into MarginLayout. 1835 private void reInitSuper(Context context, AttributeSet attrs) { 1836 TypedArray a = 1837 context.obtainStyledAttributes(attrs, R.styleable.ViewGroup_MarginLayout); 1838 try { 1839 int margin = a.getDimensionPixelSize(MARGIN, DEFAULT_MARGIN); 1840 1841 this.leftMargin = a.getDimensionPixelSize(LEFT_MARGIN, margin); 1842 this.topMargin = a.getDimensionPixelSize(TOP_MARGIN, margin); 1843 this.rightMargin = a.getDimensionPixelSize(RIGHT_MARGIN, margin); 1844 this.bottomMargin = a.getDimensionPixelSize(BOTTOM_MARGIN, margin); 1845 } finally { 1846 a.recycle(); 1847 } 1848 } 1849 1850 private void init(Context context, AttributeSet attrs) { 1851 TypedArray a = context.obtainStyledAttributes(attrs, R.styleable.GridLayout_Layout); 1852 try { 1853 int gravity = a.getInt(GRAVITY, Gravity.NO_GRAVITY); 1854 1855 int column = a.getInt(COLUMN, DEFAULT_COLUMN); 1856 int colSpan = a.getInt(COLUMN_SPAN, DEFAULT_SPAN_SIZE); 1857 this.columnSpec = spec(column, colSpan, getAlignment(gravity, true)); 1858 1859 int row = a.getInt(ROW, DEFAULT_ROW); 1860 int rowSpan = a.getInt(ROW_SPAN, DEFAULT_SPAN_SIZE); 1861 this.rowSpec = spec(row, rowSpan, getAlignment(gravity, false)); 1862 } finally { 1863 a.recycle(); 1864 } 1865 } 1866 1867 /** 1868 * Describes how the child views are positioned. Default is {@code LEFT | BASELINE}. 1869 * See {@link android.view.Gravity}. 1870 * 1871 * @param gravity the new gravity value 1872 * 1873 * @attr ref android.R.styleable#GridLayout_Layout_layout_gravity 1874 */ 1875 public void setGravity(int gravity) { 1876 rowSpec = rowSpec.copyWriteAlignment(getAlignment(gravity, false)); 1877 columnSpec = columnSpec.copyWriteAlignment(getAlignment(gravity, true)); 1878 } 1879 1880 @Override 1881 protected void setBaseAttributes(TypedArray attributes, int widthAttr, int heightAttr) { 1882 this.width = attributes.getLayoutDimension(widthAttr, DEFAULT_WIDTH); 1883 this.height = attributes.getLayoutDimension(heightAttr, DEFAULT_HEIGHT); 1884 } 1885 1886 final void setRowSpecSpan(Interval span) { 1887 rowSpec = rowSpec.copyWriteSpan(span); 1888 } 1889 1890 final void setColumnSpecSpan(Interval span) { 1891 columnSpec = columnSpec.copyWriteSpan(span); 1892 } 1893 } 1894 1895 /* 1896 In place of a HashMap from span to Int, use an array of key/value pairs - stored in Arcs. 1897 Add the mutables completesCycle flag to avoid creating another hash table for detecting cycles. 1898 */ 1899 final static class Arc { 1900 public final Interval span; 1901 public final MutableInt value; 1902 public boolean valid = true; 1903 1904 public Arc(Interval span, MutableInt value) { 1905 this.span = span; 1906 this.value = value; 1907 } 1908 1909 @Override 1910 public String toString() { 1911 return span + " " + (!valid ? "+>" : "->") + " " + value; 1912 } 1913 } 1914 1915 // A mutable Integer - used to avoid heap allocation during the layout operation 1916 1917 final static class MutableInt { 1918 public int value; 1919 1920 public MutableInt() { 1921 reset(); 1922 } 1923 1924 public MutableInt(int value) { 1925 this.value = value; 1926 } 1927 1928 public void reset() { 1929 value = Integer.MIN_VALUE; 1930 } 1931 1932 @Override 1933 public String toString() { 1934 return Integer.toString(value); 1935 } 1936 } 1937 1938 final static class Assoc<K, V> extends ArrayList<Pair<K, V>> { 1939 private final Class<K> keyType; 1940 private final Class<V> valueType; 1941 1942 private Assoc(Class<K> keyType, Class<V> valueType) { 1943 this.keyType = keyType; 1944 this.valueType = valueType; 1945 } 1946 1947 public static <K, V> Assoc<K, V> of(Class<K> keyType, Class<V> valueType) { 1948 return new Assoc<K, V>(keyType, valueType); 1949 } 1950 1951 public void put(K key, V value) { 1952 add(Pair.create(key, value)); 1953 } 1954 1955 @SuppressWarnings(value = "unchecked") 1956 public PackedMap<K, V> pack() { 1957 int N = size(); 1958 K[] keys = (K[]) Array.newInstance(keyType, N); 1959 V[] values = (V[]) Array.newInstance(valueType, N); 1960 for (int i = 0; i < N; i++) { 1961 keys[i] = get(i).first; 1962 values[i] = get(i).second; 1963 } 1964 return new PackedMap<K, V>(keys, values); 1965 } 1966 } 1967 1968 /* 1969 This data structure is used in place of a Map where we have an index that refers to the order 1970 in which each key/value pairs were added to the map. In this case we store keys and values 1971 in arrays of a length that is equal to the number of unique keys. We also maintain an 1972 array of indexes from insertion order to the compacted arrays of keys and values. 1973 1974 Note that behavior differs from that of a LinkedHashMap in that repeated entries 1975 *do* get added multiples times. So the length of index is equals to the number of 1976 items added. 1977 1978 This is useful in the GridLayout class where we can rely on the order of children not 1979 changing during layout - to use integer-based lookup for our internal structures 1980 rather than using (and storing) an implementation of Map<Key, ?>. 1981 */ 1982 @SuppressWarnings(value = "unchecked") 1983 final static class PackedMap<K, V> { 1984 public final int[] index; 1985 public final K[] keys; 1986 public final V[] values; 1987 1988 private PackedMap(K[] keys, V[] values) { 1989 this.index = createIndex(keys); 1990 1991 this.keys = compact(keys, index); 1992 this.values = compact(values, index); 1993 } 1994 1995 public V getValue(int i) { 1996 return values[index[i]]; 1997 } 1998 1999 private static <K> int[] createIndex(K[] keys) { 2000 int size = keys.length; 2001 int[] result = new int[size]; 2002 2003 Map<K, Integer> keyToIndex = new HashMap<K, Integer>(); 2004 for (int i = 0; i < size; i++) { 2005 K key = keys[i]; 2006 Integer index = keyToIndex.get(key); 2007 if (index == null) { 2008 index = keyToIndex.size(); 2009 keyToIndex.put(key, index); 2010 } 2011 result[i] = index; 2012 } 2013 return result; 2014 } 2015 2016 /* 2017 Create a compact array of keys or values using the supplied index. 2018 */ 2019 private static <K> K[] compact(K[] a, int[] index) { 2020 int size = a.length; 2021 Class<?> componentType = a.getClass().getComponentType(); 2022 K[] result = (K[]) Array.newInstance(componentType, max2(index, -1) + 1); 2023 2024 // this overwrite duplicates, retaining the last equivalent entry 2025 for (int i = 0; i < size; i++) { 2026 result[index[i]] = a[i]; 2027 } 2028 return result; 2029 } 2030 } 2031 2032 /* 2033 For each group (with a given alignment) we need to store the amount of space required 2034 before the alignment point and the amount of space required after it. One side of this 2035 calculation is always 0 for LEADING and TRAILING alignments but we don't make use of this. 2036 For CENTER and BASELINE alignments both sides are needed and in the BASELINE case no 2037 simple optimisations are possible. 2038 2039 The general algorithm therefore is to create a Map (actually a PackedMap) from 2040 group to Bounds and to loop through all Views in the group taking the maximum 2041 of the values for each View. 2042 */ 2043 static class Bounds { 2044 public int before; 2045 public int after; 2046 public int flexibility; // we're flexible iff all included specs are flexible 2047 2048 private Bounds() { 2049 reset(); 2050 } 2051 2052 protected void reset() { 2053 before = Integer.MIN_VALUE; 2054 after = Integer.MIN_VALUE; 2055 flexibility = CAN_STRETCH; // from the above, we're flexible when empty 2056 } 2057 2058 protected void include(int before, int after) { 2059 this.before = max(this.before, before); 2060 this.after = max(this.after, after); 2061 } 2062 2063 protected int size(boolean min) { 2064 if (!min) { 2065 if (canStretch(flexibility)) { 2066 return MAX_SIZE; 2067 } 2068 } 2069 return before + after; 2070 } 2071 2072 protected int getOffset(View c, Alignment alignment, int size) { 2073 return before - alignment.getAlignmentValue(c, size); 2074 } 2075 2076 protected final void include(View c, Spec spec, GridLayout gridLayout, Axis axis) { 2077 this.flexibility &= spec.getFlexibility(); 2078 int size = gridLayout.getMeasurementIncludingMargin(c, axis.horizontal); 2079 Alignment alignment = gridLayout.getAlignment(spec.alignment, axis.horizontal); 2080 // todo test this works correctly when the returned value is UNDEFINED 2081 int before = alignment.getAlignmentValue(c, size); 2082 include(before, size - before); 2083 } 2084 2085 @Override 2086 public String toString() { 2087 return "Bounds{" + 2088 "before=" + before + 2089 ", after=" + after + 2090 '}'; 2091 } 2092 } 2093 2094 /** 2095 * An Interval represents a contiguous range of values that lie between 2096 * the interval's {@link #min} and {@link #max} values. 2097 * <p> 2098 * Intervals are immutable so may be passed as values and used as keys in hash tables. 2099 * It is not necessary to have multiple instances of Intervals which have the same 2100 * {@link #min} and {@link #max} values. 2101 * <p> 2102 * Intervals are often written as {@code [min, max]} and represent the set of values 2103 * {@code x} such that {@code min <= x < max}. 2104 */ 2105 final static class Interval { 2106 /** 2107 * The minimum value. 2108 */ 2109 public final int min; 2110 2111 /** 2112 * The maximum value. 2113 */ 2114 public final int max; 2115 2116 /** 2117 * Construct a new Interval, {@code interval}, where: 2118 * <ul> 2119 * <li> {@code interval.min = min} </li> 2120 * <li> {@code interval.max = max} </li> 2121 * </ul> 2122 * 2123 * @param min the minimum value. 2124 * @param max the maximum value. 2125 */ 2126 public Interval(int min, int max) { 2127 this.min = min; 2128 this.max = max; 2129 } 2130 2131 int size() { 2132 return max - min; 2133 } 2134 2135 Interval inverse() { 2136 return new Interval(max, min); 2137 } 2138 2139 /** 2140 * Returns {@code true} if the {@link #getClass class}, 2141 * {@link #min} and {@link #max} properties of this Interval and the 2142 * supplied parameter are pairwise equal; {@code false} otherwise. 2143 * 2144 * @param that the object to compare this interval with 2145 * 2146 * @return {@code true} if the specified object is equal to this 2147 * {@code Interval}, {@code false} otherwise. 2148 */ 2149 @Override 2150 public boolean equals(Object that) { 2151 if (this == that) { 2152 return true; 2153 } 2154 if (that == null || getClass() != that.getClass()) { 2155 return false; 2156 } 2157 2158 Interval interval = (Interval) that; 2159 2160 if (max != interval.max) { 2161 return false; 2162 } 2163 //noinspection RedundantIfStatement 2164 if (min != interval.min) { 2165 return false; 2166 } 2167 2168 return true; 2169 } 2170 2171 @Override 2172 public int hashCode() { 2173 int result = min; 2174 result = 31 * result + max; 2175 return result; 2176 } 2177 2178 @Override 2179 public String toString() { 2180 return "[" + min + ", " + max + "]"; 2181 } 2182 } 2183 2184 /** 2185 * A Spec defines the horizontal or vertical characteristics of a group of 2186 * cells. Each spec. defines the <em>grid indices</em> and <em>alignment</em> 2187 * along the appropriate axis. 2188 * <p> 2189 * The <em>grid indices</em> are the leading and trailing edges of this cell group. 2190 * See {@link GridLayout} for a description of the conventions used by GridLayout 2191 * for grid indices. 2192 * <p> 2193 * The <em>alignment</em> property specifies how cells should be aligned in this group. 2194 * For row groups, this specifies the vertical alignment. 2195 * For column groups, this specifies the horizontal alignment. 2196 * <p> 2197 * Use the following static methods to create specs: 2198 * <ul> 2199 * <li>{@link #spec(int)}</li> 2200 * <li>{@link #spec(int, int)}</li> 2201 * <li>{@link #spec(int, Alignment)}</li> 2202 * <li>{@link #spec(int, int, Alignment)}</li> 2203 * </ul> 2204 * 2205 */ 2206 public static class Spec { 2207 static final Spec UNDEFINED = spec(GridLayout.UNDEFINED); 2208 2209 final boolean startDefined; 2210 final Interval span; 2211 final Alignment alignment; 2212 2213 private Spec(boolean startDefined, Interval span, Alignment alignment) { 2214 this.startDefined = startDefined; 2215 this.span = span; 2216 this.alignment = alignment; 2217 } 2218 2219 private Spec(boolean startDefined, int start, int size, Alignment alignment) { 2220 this(startDefined, new Interval(start, start + size), alignment); 2221 } 2222 2223 final Spec copyWriteSpan(Interval span) { 2224 return new Spec(startDefined, span, alignment); 2225 } 2226 2227 final Spec copyWriteAlignment(Alignment alignment) { 2228 return new Spec(startDefined, span, alignment); 2229 } 2230 2231 final int getFlexibility() { 2232 return (alignment == UNDEFINED_ALIGNMENT) ? INFLEXIBLE : CAN_STRETCH; 2233 } 2234 2235 /** 2236 * Returns {@code true} if the {@code class}, {@code alignment} and {@code span} 2237 * properties of this Spec and the supplied parameter are pairwise equal, 2238 * {@code false} otherwise. 2239 * 2240 * @param that the object to compare this spec with 2241 * 2242 * @return {@code true} if the specified object is equal to this 2243 * {@code Spec}; {@code false} otherwise 2244 */ 2245 @Override 2246 public boolean equals(Object that) { 2247 if (this == that) { 2248 return true; 2249 } 2250 if (that == null || getClass() != that.getClass()) { 2251 return false; 2252 } 2253 2254 Spec spec = (Spec) that; 2255 2256 if (!alignment.equals(spec.alignment)) { 2257 return false; 2258 } 2259 //noinspection RedundantIfStatement 2260 if (!span.equals(spec.span)) { 2261 return false; 2262 } 2263 2264 return true; 2265 } 2266 2267 @Override 2268 public int hashCode() { 2269 int result = span.hashCode(); 2270 result = 31 * result + alignment.hashCode(); 2271 return result; 2272 } 2273 } 2274 2275 /** 2276 * Return a Spec, {@code spec}, where: 2277 * <ul> 2278 * <li> {@code spec.span = [start, start + size]} </li> 2279 * <li> {@code spec.alignment = alignment} </li> 2280 * </ul> 2281 * 2282 * @param start the start 2283 * @param size the size 2284 * @param alignment the alignment 2285 */ 2286 public static Spec spec(int start, int size, Alignment alignment) { 2287 return new Spec(start != UNDEFINED, start, size, alignment); 2288 } 2289 2290 /** 2291 * Return a Spec, {@code spec}, where: 2292 * <ul> 2293 * <li> {@code spec.span = [start, start + 1]} </li> 2294 * <li> {@code spec.alignment = alignment} </li> 2295 * </ul> 2296 * 2297 * @param start the start index 2298 * @param alignment the alignment 2299 */ 2300 public static Spec spec(int start, Alignment alignment) { 2301 return spec(start, 1, alignment); 2302 } 2303 2304 /** 2305 * Return a Spec, {@code spec}, where: 2306 * <ul> 2307 * <li> {@code spec.span = [start, start + size]} </li> 2308 * </ul> 2309 * 2310 * @param start the start 2311 * @param size the size 2312 */ 2313 public static Spec spec(int start, int size) { 2314 return spec(start, size, UNDEFINED_ALIGNMENT); 2315 } 2316 2317 /** 2318 * Return a Spec, {@code spec}, where: 2319 * <ul> 2320 * <li> {@code spec.span = [start, start + 1]} </li> 2321 * </ul> 2322 * 2323 * @param start the start index 2324 */ 2325 public static Spec spec(int start) { 2326 return spec(start, 1); 2327 } 2328 2329 /** 2330 * Alignments specify where a view should be placed within a cell group and 2331 * what size it should be. 2332 * <p> 2333 * The {@link LayoutParams} class contains a {@link LayoutParams#rowSpec rowSpec} 2334 * and a {@link LayoutParams#columnSpec columnSpec} each of which contains an 2335 * {@code alignment}. Overall placement of the view in the cell 2336 * group is specified by the two alignments which act along each axis independently. 2337 * <p> 2338 * The GridLayout class defines the most common alignments used in general layout: 2339 * {@link #TOP}, {@link #LEFT}, {@link #BOTTOM}, {@link #RIGHT}, {@link #CENTER}, {@link 2340 * #BASELINE} and {@link #FILL}. 2341 */ 2342 /* 2343 * An Alignment implementation must define {@link #getAlignmentValue(View, int, int)}, 2344 * to return the appropriate value for the type of alignment being defined. 2345 * The enclosing algorithms position the children 2346 * so that the locations defined by the alignment values 2347 * are the same for all of the views in a group. 2348 * <p> 2349 */ 2350 public static abstract class Alignment { 2351 Alignment() { 2352 } 2353 2354 /** 2355 * Returns an alignment value. In the case of vertical alignments the value 2356 * returned should indicate the distance from the top of the view to the 2357 * alignment location. 2358 * For horizontal alignments measurement is made from the left edge of the component. 2359 * 2360 * @param view the view to which this alignment should be applied 2361 * @param viewSize the measured size of the view 2362 * @return the alignment value 2363 */ 2364 abstract int getAlignmentValue(View view, int viewSize); 2365 2366 /** 2367 * Returns the size of the view specified by this alignment. 2368 * In the case of vertical alignments this method should return a height; for 2369 * horizontal alignments this method should return the width. 2370 * <p> 2371 * The default implementation returns {@code viewSize}. 2372 * 2373 * @param view the view to which this alignment should be applied 2374 * @param viewSize the measured size of the view 2375 * @param cellSize the size of the cell into which this view will be placed 2376 * @param measurementType This parameter is currently unused as GridLayout only supports 2377 * one type of measurement: {@link View#measure(int, int)}. 2378 * 2379 * @return the aligned size 2380 */ 2381 int getSizeInCell(View view, int viewSize, int cellSize, int measurementType) { 2382 return viewSize; 2383 } 2384 2385 Bounds getBounds() { 2386 return new Bounds(); 2387 } 2388 } 2389 2390 static final Alignment UNDEFINED_ALIGNMENT = new Alignment() { 2391 public int getAlignmentValue(View view, int viewSize) { 2392 return UNDEFINED; 2393 } 2394 }; 2395 2396 private static final Alignment LEADING = new Alignment() { 2397 public int getAlignmentValue(View view, int viewSize) { 2398 return 0; 2399 } 2400 }; 2401 2402 private static final Alignment TRAILING = new Alignment() { 2403 public int getAlignmentValue(View view, int viewSize) { 2404 return viewSize; 2405 } 2406 }; 2407 2408 /** 2409 * Indicates that a view should be aligned with the <em>top</em> 2410 * edges of the other views in its cell group. 2411 */ 2412 public static final Alignment TOP = LEADING; 2413 2414 /** 2415 * Indicates that a view should be aligned with the <em>bottom</em> 2416 * edges of the other views in its cell group. 2417 */ 2418 public static final Alignment BOTTOM = TRAILING; 2419 2420 /** 2421 * Indicates that a view should be aligned with the <em>right</em> 2422 * edges of the other views in its cell group. 2423 */ 2424 public static final Alignment RIGHT = TRAILING; 2425 2426 /** 2427 * Indicates that a view should be aligned with the <em>left</em> 2428 * edges of the other views in its cell group. 2429 */ 2430 public static final Alignment LEFT = LEADING; 2431 2432 /** 2433 * Indicates that a view should be <em>centered</em> with the other views in its cell group. 2434 * This constant may be used in both {@link LayoutParams#rowSpec rowSpecs} and {@link 2435 * LayoutParams#columnSpec columnSpecs}. 2436 */ 2437 public static final Alignment CENTER = new Alignment() { 2438 public int getAlignmentValue(View view, int viewSize) { 2439 return viewSize >> 1; 2440 } 2441 }; 2442 2443 /** 2444 * Indicates that a view should be aligned with the <em>baselines</em> 2445 * of the other views in its cell group. 2446 * This constant may only be used as an alignment in {@link LayoutParams#rowSpec rowSpecs}. 2447 * 2448 * @see View#getBaseline() 2449 */ 2450 public static final Alignment BASELINE = new Alignment() { 2451 public int getAlignmentValue(View view, int viewSize) { 2452 if (view == null) { 2453 return UNDEFINED; 2454 } 2455 int baseline = view.getBaseline(); 2456 return (baseline == -1) ? UNDEFINED : baseline; 2457 } 2458 2459 @Override 2460 public Bounds getBounds() { 2461 return new Bounds() { 2462 /* 2463 In a baseline aligned row in which some components define a baseline 2464 and some don't, we need a third variable to properly account for all 2465 the sizes. This tracks the maximum size of all the components - 2466 including those that don't define a baseline. 2467 */ 2468 private int size; 2469 2470 @Override 2471 protected void reset() { 2472 super.reset(); 2473 size = Integer.MIN_VALUE; 2474 } 2475 2476 @Override 2477 protected void include(int before, int after) { 2478 super.include(before, after); 2479 size = max(size, before + after); 2480 } 2481 2482 @Override 2483 protected int size(boolean min) { 2484 return max(super.size(min), size); 2485 } 2486 2487 @Override 2488 protected int getOffset(View c, Alignment alignment, int size) { 2489 return max(0, super.getOffset(c, alignment, size)); 2490 } 2491 }; 2492 } 2493 }; 2494 2495 /** 2496 * Indicates that a view should expanded to fit the boundaries of its cell group. 2497 * This constant may be used in both {@link LayoutParams#rowSpec rowSpecs} and 2498 * {@link LayoutParams#columnSpec columnSpecs}. 2499 */ 2500 public static final Alignment FILL = new Alignment() { 2501 public int getAlignmentValue(View view, int viewSize) { 2502 return UNDEFINED; 2503 } 2504 2505 @Override 2506 public int getSizeInCell(View view, int viewSize, int cellSize, int measurementType) { 2507 return cellSize; 2508 } 2509 }; 2510 2511 static boolean canStretch(int flexibility) { 2512 return (flexibility & CAN_STRETCH) != 0; 2513 } 2514 2515 private static final int INFLEXIBLE = 0; 2516 2517 private static final int CAN_STRETCH = 2; 2518 } 2519