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