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