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