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