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