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