frameworks/base/core/java/android/widget/RelativeLayout.java

   1 /*
   2  * Copyright (C) 2006 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
  17 package android.widget;
  18
  19 import com.android.internal.R;
  20
  21 import android.content.Context;
  22 import android.content.res.TypedArray;
  23 import android.content.res.Resources;
  24 import android.graphics.Rect;
  25 import android.util.AttributeSet;
  26 import android.util.SparseArray;
  27 import android.util.Poolable;
  28 import android.util.Pool;
  29 import android.util.Pools;
  30 import android.util.PoolableManager;
  31 import static android.util.Log.d;
  32 import android.view.Gravity;
  33 import android.view.View;
  34 import android.view.ViewDebug;
  35 import android.view.ViewGroup;
  36 import android.view.accessibility.AccessibilityEvent;
  37 import android.widget.RemoteViews.RemoteView;
  38
  39 import java.util.Comparator;
  40 import java.util.SortedSet;
  41 import java.util.TreeSet;
  42 import java.util.LinkedList;
  43 import java.util.HashSet;
  44 import java.util.ArrayList;
  45
  46 /**
  47  * A Layout where the positions of the children can be described in relation to each other or to the
  48  * parent.
  49  *
  50  * <p>
  51  * Note that you cannot have a circular dependency between the size of the RelativeLayout and the
  52  * position of its children. For example, you cannot have a RelativeLayout whose height is set to
  53  * {@link android.view.ViewGroup.LayoutParams#WRAP_CONTENT WRAP_CONTENT} and a child set to
  54  * {@link #ALIGN_PARENT_BOTTOM}.
  55  * </p>
  56  *
  57  * <p>See the <a href="{@docRoot}resources/tutorials/views/hello-relativelayout.html">Relative
  58  * Layout tutorial</a>.</p>
  59  *
  60  * <p>
  61  * Also see {@link android.widget.RelativeLayout.LayoutParams RelativeLayout.LayoutParams} for
  62  * layout attributes
  63  * </p>
  64  *
  65  * @attr ref android.R.styleable#RelativeLayout_gravity
  66  * @attr ref android.R.styleable#RelativeLayout_ignoreGravity
  67  */
  68 @RemoteView
  69 public class RelativeLayout extends ViewGroup {
  70     private static final String LOG_TAG = "RelativeLayout";
  71
  72     private static final boolean DEBUG_GRAPH = false;
  73
  74     public static final int TRUE = -1;
  75
  76     /**
  77      * Rule that aligns a child's right edge with another child's left edge.
  78      */
  79     public static final int LEFT_OF                  = 0;
  80     /**
  81      * Rule that aligns a child's left edge with another child's right edge.
  82      */
  83     public static final int RIGHT_OF                 = 1;
  84     /**
  85      * Rule that aligns a child's bottom edge with another child's top edge.
  86      */
  87     public static final int ABOVE                    = 2;
  88     /**
  89      * Rule that aligns a child's top edge with another child's bottom edge.
  90      */
  91     public static final int BELOW                    = 3;
  92
  93     /**
  94      * Rule that aligns a child's baseline with another child's baseline.
  95      */
  96     public static final int ALIGN_BASELINE           = 4;
  97     /**
  98      * Rule that aligns a child's left edge with another child's left edge.
  99      */
 100     public static final int ALIGN_LEFT               = 5;
 101     /**
 102      * Rule that aligns a child's top edge with another child's top edge.
 103      */
 104     public static final int ALIGN_TOP                = 6;
 105     /**
 106      * Rule that aligns a child's right edge with another child's right edge.
 107      */
 108     public static final int ALIGN_RIGHT              = 7;
 109     /**
 110      * Rule that aligns a child's bottom edge with another child's bottom edge.
 111      */
 112     public static final int ALIGN_BOTTOM             = 8;
 113
 114     /**
 115      * Rule that aligns the child's left edge with its RelativeLayout
 116      * parent's left edge.
 117      */
 118     public static final int ALIGN_PARENT_LEFT        = 9;
 119     /**
 120      * Rule that aligns the child's top edge with its RelativeLayout
 121      * parent's top edge.
 122      */
 123     public static final int ALIGN_PARENT_TOP         = 10;
 124     /**
 125      * Rule that aligns the child's right edge with its RelativeLayout
 126      * parent's right edge.
 127      */
 128     public static final int ALIGN_PARENT_RIGHT       = 11;
 129     /**
 130      * Rule that aligns the child's bottom edge with its RelativeLayout
 131      * parent's bottom edge.
 132      */
 133     public static final int ALIGN_PARENT_BOTTOM      = 12;
 134
 135     /**
 136      * Rule that centers the child with respect to the bounds of its
 137      * RelativeLayout parent.
 138      */
 139     public static final int CENTER_IN_PARENT         = 13;
 140     /**
 141      * Rule that centers the child horizontally with respect to the
 142      * bounds of its RelativeLayout parent.
 143      */
 144     public static final int CENTER_HORIZONTAL        = 14;
 145     /**
 146      * Rule that centers the child vertically with respect to the
 147      * bounds of its RelativeLayout parent.
 148      */
 149     public static final int CENTER_VERTICAL          = 15;
 150
 151     private static final int VERB_COUNT              = 16;
 152
 153     private View mBaselineView = null;
 154     private boolean mHasBaselineAlignedChild;
 155
 156     private int mGravity = Gravity.LEFT | Gravity.TOP;
 157     private final Rect mContentBounds = new Rect();
 158     private final Rect mSelfBounds = new Rect();
 159     private int mIgnoreGravity;
 160
 161     private SortedSet<View> mTopToBottomLeftToRightSet = null;
 162
 163     private boolean mDirtyHierarchy;
 164     private View[] mSortedHorizontalChildren = new View[0];
 165     private View[] mSortedVerticalChildren = new View[0];
 166     private final DependencyGraph mGraph = new DependencyGraph();
 167
 168     public RelativeLayout(Context context) {
 169         super(context);
 170     }
 171
 172     public RelativeLayout(Context context, AttributeSet attrs) {
 173         super(context, attrs);
 174         initFromAttributes(context, attrs);
 175     }
 176
 177     public RelativeLayout(Context context, AttributeSet attrs, int defStyle) {
 178         super(context, attrs, defStyle);
 179         initFromAttributes(context, attrs);
 180     }
 181
 182     private void initFromAttributes(Context context, AttributeSet attrs) {
 183         TypedArray a = context.obtainStyledAttributes(attrs, R.styleable.RelativeLayout);
 184         mIgnoreGravity = a.getResourceId(R.styleable.RelativeLayout_ignoreGravity, View.NO_ID);
 185         mGravity = a.getInt(R.styleable.RelativeLayout_gravity, mGravity);
 186         a.recycle();
 187     }
 188
 189     /**
 190      * Defines which View is ignored when the gravity is applied. This setting has no
 191      * effect if the gravity is <code>Gravity.LEFT | Gravity.TOP</code>.
 192      *
 193      * @param viewId The id of the View to be ignored by gravity, or 0 if no View
 194      *        should be ignored.
 195      *
 196      * @see #setGravity(int)
 197      *
 198      * @attr ref android.R.styleable#RelativeLayout_ignoreGravity
 199      */
 200     @android.view.RemotableViewMethod
 201     public void setIgnoreGravity(int viewId) {
 202         mIgnoreGravity = viewId;
 203     }
 204
 205     /**
 206      * Describes how the child views are positioned. Defaults to
 207      * <code>Gravity.LEFT | Gravity.TOP</code>.
 208      *
 209      * @param gravity See {@link android.view.Gravity}
 210      *
 211      * @see #setHorizontalGravity(int)
 212      * @see #setVerticalGravity(int)
 213      *
 214      * @attr ref android.R.styleable#RelativeLayout_gravity
 215      */
 216     @android.view.RemotableViewMethod
 217     public void setGravity(int gravity) {
 218         if (mGravity != gravity) {
 219             if ((gravity & Gravity.HORIZONTAL_GRAVITY_MASK) == 0) {
 220                 gravity |= Gravity.LEFT;
 221             }
 222
 223             if ((gravity & Gravity.VERTICAL_GRAVITY_MASK) == 0) {
 224                 gravity |= Gravity.TOP;
 225             }
 226
 227             mGravity = gravity;
 228             requestLayout();
 229         }
 230     }
 231
 232     @android.view.RemotableViewMethod
 233     public void setHorizontalGravity(int horizontalGravity) {
 234         final int gravity = horizontalGravity & Gravity.HORIZONTAL_GRAVITY_MASK;
 235         if ((mGravity & Gravity.HORIZONTAL_GRAVITY_MASK) != gravity) {
 236             mGravity = (mGravity & ~Gravity.HORIZONTAL_GRAVITY_MASK) | gravity;
 237             requestLayout();
 238         }
 239     }
 240
 241     @android.view.RemotableViewMethod
 242     public void setVerticalGravity(int verticalGravity) {
 243         final int gravity = verticalGravity & Gravity.VERTICAL_GRAVITY_MASK;
 244         if ((mGravity & Gravity.VERTICAL_GRAVITY_MASK) != gravity) {
 245             mGravity = (mGravity & ~Gravity.VERTICAL_GRAVITY_MASK) | gravity;
 246             requestLayout();
 247         }
 248     }
 249
 250     @Override
 251     public int getBaseline() {
 252         return mBaselineView != null ? mBaselineView.getBaseline() : super.getBaseline();
 253     }
 254
 255     @Override
 256     public void requestLayout() {
 257         super.requestLayout();
 258         mDirtyHierarchy = true;
 259     }
 260
 261     private void sortChildren() {
 262         int count = getChildCount();
 263         if (mSortedVerticalChildren.length != count) mSortedVerticalChildren = new View[count];
 264         if (mSortedHorizontalChildren.length != count) mSortedHorizontalChildren = new View[count];
 265
 266         final DependencyGraph graph = mGraph;
 267         graph.clear();
 268
 269         for (int i = 0; i < count; i++) {
 270             final View child = getChildAt(i);
 271             graph.add(child);
 272         }
 273
 274         if (DEBUG_GRAPH) {
 275             d(LOG_TAG, "=== Sorted vertical children");
 276             graph.log(getResources(), ABOVE, BELOW, ALIGN_BASELINE, ALIGN_TOP, ALIGN_BOTTOM);
 277             d(LOG_TAG, "=== Sorted horizontal children");
 278             graph.log(getResources(), LEFT_OF, RIGHT_OF, ALIGN_LEFT, ALIGN_RIGHT);
 279         }
 280
 281         graph.getSortedViews(mSortedVerticalChildren, ABOVE, BELOW, ALIGN_BASELINE,
 282                 ALIGN_TOP, ALIGN_BOTTOM);
 283         graph.getSortedViews(mSortedHorizontalChildren, LEFT_OF, RIGHT_OF, ALIGN_LEFT, ALIGN_RIGHT);
 284
 285         if (DEBUG_GRAPH) {
 286             d(LOG_TAG, "=== Ordered list of vertical children");
 287             for (View view : mSortedVerticalChildren) {
 288                 DependencyGraph.printViewId(getResources(), view);
 289             }
 290             d(LOG_TAG, "=== Ordered list of horizontal children");
 291             for (View view : mSortedHorizontalChildren) {
 292                 DependencyGraph.printViewId(getResources(), view);
 293             }
 294         }
 295     }
 296
 297     // TODO: we need to find another way to implement RelativeLayout
 298     // This implementation cannot handle every case
 299     @Override
 300     protected void onMeasure(int widthMeasureSpec, int heightMeasureSpec) {
 301         if (mDirtyHierarchy) {
 302             mDirtyHierarchy = false;
 303             sortChildren();
 304         }
 305
 306         int myWidth = -1;
 307         int myHeight = -1;
 308
 309         int width = 0;
 310         int height = 0;
 311
 312         int widthMode = MeasureSpec.getMode(widthMeasureSpec);
 313         int heightMode = MeasureSpec.getMode(heightMeasureSpec);
 314         int widthSize = MeasureSpec.getSize(widthMeasureSpec);
 315         int heightSize = MeasureSpec.getSize(heightMeasureSpec);
 316
 317         // Record our dimensions if they are known;
 318         if (widthMode != MeasureSpec.UNSPECIFIED) {
 319             myWidth = widthSize;
 320         }
 321
 322         if (heightMode != MeasureSpec.UNSPECIFIED) {
 323             myHeight = heightSize;
 324         }
 325
 326         if (widthMode == MeasureSpec.EXACTLY) {
 327             width = myWidth;
 328         }
 329
 330         if (heightMode == MeasureSpec.EXACTLY) {
 331             height = myHeight;
 332         }
 333
 334         mHasBaselineAlignedChild = false;
 335
 336         View ignore = null;
 337         int gravity = mGravity & Gravity.HORIZONTAL_GRAVITY_MASK;
 338         final boolean horizontalGravity = gravity != Gravity.LEFT && gravity != 0;
 339         gravity = mGravity & Gravity.VERTICAL_GRAVITY_MASK;
 340         final boolean verticalGravity = gravity != Gravity.TOP && gravity != 0;
 341
 342         int left = Integer.MAX_VALUE;
 343         int top = Integer.MAX_VALUE;
 344         int right = Integer.MIN_VALUE;
 345         int bottom = Integer.MIN_VALUE;
 346
 347         boolean offsetHorizontalAxis = false;
 348         boolean offsetVerticalAxis = false;
 349
 350         if ((horizontalGravity || verticalGravity) && mIgnoreGravity != View.NO_ID) {
 351             ignore = findViewById(mIgnoreGravity);
 352         }
 353
 354         final boolean isWrapContentWidth = widthMode != MeasureSpec.EXACTLY;
 355         final boolean isWrapContentHeight = heightMode != MeasureSpec.EXACTLY;
 356
 357         View[] views = mSortedHorizontalChildren;
 358         int count = views.length;
 359         for (int i = 0; i < count; i++) {
 360             View child = views[i];
 361             if (child.getVisibility() != GONE) {
 362                 LayoutParams params = (LayoutParams) child.getLayoutParams();
 363
 364                 applyHorizontalSizeRules(params, myWidth);
 365                 measureChildHorizontal(child, params, myWidth, myHeight);
 366                 if (positionChildHorizontal(child, params, myWidth, isWrapContentWidth)) {
 367                     offsetHorizontalAxis = true;
 368                 }
 369             }
 370         }
 371
 372         views = mSortedVerticalChildren;
 373         count = views.length;
 374
 375         for (int i = 0; i < count; i++) {
 376             View child = views[i];
 377             if (child.getVisibility() != GONE) {
 378                 LayoutParams params = (LayoutParams) child.getLayoutParams();
 379
 380                 applyVerticalSizeRules(params, myHeight);
 381                 measureChild(child, params, myWidth, myHeight);
 382                 if (positionChildVertical(child, params, myHeight, isWrapContentHeight)) {
 383                     offsetVerticalAxis = true;
 384                 }
 385
 386                 if (isWrapContentWidth) {
 387                     width = Math.max(width, params.mRight);
 388                 }
 389
 390                 if (isWrapContentHeight) {
 391                     height = Math.max(height, params.mBottom);
 392                 }
 393
 394                 if (child != ignore || verticalGravity) {
 395                     left = Math.min(left, params.mLeft - params.leftMargin);
 396                     top = Math.min(top, params.mTop - params.topMargin);
 397                 }
 398
 399                 if (child != ignore || horizontalGravity) {
 400                     right = Math.max(right, params.mRight + params.rightMargin);
 401                     bottom = Math.max(bottom, params.mBottom + params.bottomMargin);
 402                 }
 403             }
 404         }
 405
 406         if (mHasBaselineAlignedChild) {
 407             for (int i = 0; i < count; i++) {
 408                 View child = getChildAt(i);
 409                 if (child.getVisibility() != GONE) {
 410                     LayoutParams params = (LayoutParams) child.getLayoutParams();
 411                     alignBaseline(child, params);
 412
 413                     if (child != ignore || verticalGravity) {
 414                         left = Math.min(left, params.mLeft - params.leftMargin);
 415                         top = Math.min(top, params.mTop - params.topMargin);
 416                     }
 417
 418                     if (child != ignore || horizontalGravity) {
 419                         right = Math.max(right, params.mRight + params.rightMargin);
 420                         bottom = Math.max(bottom, params.mBottom + params.bottomMargin);
 421                     }
 422                 }
 423             }
 424         }
 425
 426         if (isWrapContentWidth) {
 427             // Width already has left padding in it since it was calculated by looking at
 428             // the right of each child view
 429             width += mPaddingRight;
 430
 431             if (mLayoutParams.width >= 0) {
 432                 width = Math.max(width, mLayoutParams.width);
 433             }
 434
 435             width = Math.max(width, getSuggestedMinimumWidth());
 436             width = resolveSize(width, widthMeasureSpec);
 437
 438             if (offsetHorizontalAxis) {
 439                 for (int i = 0; i < count; i++) {
 440                     View child = getChildAt(i);
 441                     if (child.getVisibility() != GONE) {
 442                         LayoutParams params = (LayoutParams) child.getLayoutParams();
 443                         final int[] rules = params.getRules();
 444                         if (rules[CENTER_IN_PARENT] != 0 || rules[CENTER_HORIZONTAL] != 0) {
 445                             centerHorizontal(child, params, width);
 446                         } else if (rules[ALIGN_PARENT_RIGHT] != 0) {
 447                             final int childWidth = child.getMeasuredWidth();
 448                             params.mLeft = width - mPaddingRight - childWidth;
 449                             params.mRight = params.mLeft + childWidth;
 450                         }
 451                     }
 452                 }
 453             }
 454         }
 455
 456         if (isWrapContentHeight) {
 457             // Height already has top padding in it since it was calculated by looking at
 458             // the bottom of each child view
 459             height += mPaddingBottom;
 460
 461             if (mLayoutParams.height >= 0) {
 462                 height = Math.max(height, mLayoutParams.height);
 463             }
 464
 465             height = Math.max(height, getSuggestedMinimumHeight());
 466             height = resolveSize(height, heightMeasureSpec);
 467
 468             if (offsetVerticalAxis) {
 469                 for (int i = 0; i < count; i++) {
 470                     View child = getChildAt(i);
 471                     if (child.getVisibility() != GONE) {
 472                         LayoutParams params = (LayoutParams) child.getLayoutParams();
 473                         final int[] rules = params.getRules();
 474                         if (rules[CENTER_IN_PARENT] != 0 || rules[CENTER_VERTICAL] != 0) {
 475                             centerVertical(child, params, height);
 476                         } else if (rules[ALIGN_PARENT_BOTTOM] != 0) {
 477                             final int childHeight = child.getMeasuredHeight();
 478                             params.mTop = height - mPaddingBottom - childHeight;
 479                             params.mBottom = params.mTop + childHeight;
 480                         }
 481                     }
 482                 }
 483             }
 484         }
 485
 486         if (horizontalGravity || verticalGravity) {
 487             final Rect selfBounds = mSelfBounds;
 488             selfBounds.set(mPaddingLeft, mPaddingTop, width - mPaddingRight,
 489                     height - mPaddingBottom);
 490
 491             final Rect contentBounds = mContentBounds;
 492             Gravity.apply(mGravity, right - left, bottom - top, selfBounds, contentBounds);
 493
 494             final int horizontalOffset = contentBounds.left - left;
 495             final int verticalOffset = contentBounds.top - top;
 496             if (horizontalOffset != 0 || verticalOffset != 0) {
 497                 for (int i = 0; i < count; i++) {
 498                     View child = getChildAt(i);
 499                     if (child.getVisibility() != GONE && child != ignore) {
 500                         LayoutParams params = (LayoutParams) child.getLayoutParams();
 501                         if (horizontalGravity) {
 502                             params.mLeft += horizontalOffset;
 503                             params.mRight += horizontalOffset;
 504                         }
 505                         if (verticalGravity) {
 506                             params.mTop += verticalOffset;
 507                             params.mBottom += verticalOffset;
 508                         }
 509                     }
 510                 }
 511             }
 512         }
 513
 514         setMeasuredDimension(width, height);
 515     }
 516
 517     private void alignBaseline(View child, LayoutParams params) {
 518         int[] rules = params.getRules();
 519         int anchorBaseline = getRelatedViewBaseline(rules, ALIGN_BASELINE);
 520
 521         if (anchorBaseline != -1) {
 522             LayoutParams anchorParams = getRelatedViewParams(rules, ALIGN_BASELINE);
 523             if (anchorParams != null) {
 524                 int offset = anchorParams.mTop + anchorBaseline;
 525                 int baseline = child.getBaseline();
 526                 if (baseline != -1) {
 527                     offset -= baseline;
 528                 }
 529                 int height = params.mBottom - params.mTop;
 530                 params.mTop = offset;
 531                 params.mBottom = params.mTop + height;
 532             }
 533         }
 534
 535         if (mBaselineView == null) {
 536             mBaselineView = child;
 537         } else {
 538             LayoutParams lp = (LayoutParams) mBaselineView.getLayoutParams();
 539             if (params.mTop < lp.mTop || (params.mTop == lp.mTop && params.mLeft < lp.mLeft)) {
 540                 mBaselineView = child;
 541             }
 542         }
 543     }
 544
 545     /**
 546      * Measure a child. The child should have left, top, right and bottom information
 547      * stored in its LayoutParams. If any of these values is -1 it means that the view
 548      * can extend up to the corresponding edge.
 549      *
 550      * @param child Child to measure
 551      * @param params LayoutParams associated with child
 552      * @param myWidth Width of the the RelativeLayout
 553      * @param myHeight Height of the RelativeLayout
 554      */
 555     private void measureChild(View child, LayoutParams params, int myWidth, int myHeight) {
 556         int childWidthMeasureSpec = getChildMeasureSpec(params.mLeft,
 557                 params.mRight, params.width,
 558                 params.leftMargin, params.rightMargin,
 559                 mPaddingLeft, mPaddingRight,
 560                 myWidth);
 561         int childHeightMeasureSpec = getChildMeasureSpec(params.mTop,
 562                 params.mBottom, params.height,
 563                 params.topMargin, params.bottomMargin,
 564                 mPaddingTop, mPaddingBottom,
 565                 myHeight);
 566         child.measure(childWidthMeasureSpec, childHeightMeasureSpec);
 567     }
 568
 569     private void measureChildHorizontal(View child, LayoutParams params, int myWidth, int myHeight) {
 570         int childWidthMeasureSpec = getChildMeasureSpec(params.mLeft,
 571                 params.mRight, params.width,
 572                 params.leftMargin, params.rightMargin,
 573                 mPaddingLeft, mPaddingRight,
 574                 myWidth);
 575         int childHeightMeasureSpec;
 576         if (params.width == LayoutParams.MATCH_PARENT) {
 577             childHeightMeasureSpec = MeasureSpec.makeMeasureSpec(myHeight, MeasureSpec.EXACTLY);
 578         } else {
 579             childHeightMeasureSpec = MeasureSpec.makeMeasureSpec(myHeight, MeasureSpec.AT_MOST);
 580         }
 581         child.measure(childWidthMeasureSpec, childHeightMeasureSpec);
 582     }
 583
 584     /**
 585      * Get a measure spec that accounts for all of the constraints on this view.
 586      * This includes size contstraints imposed by the RelativeLayout as well as
 587      * the View's desired dimension.
 588      *
 589      * @param childStart The left or top field of the child's layout params
 590      * @param childEnd The right or bottom field of the child's layout params
 591      * @param childSize The child's desired size (the width or height field of
 592      *        the child's layout params)
 593      * @param startMargin The left or top margin
 594      * @param endMargin The right or bottom margin
 595      * @param startPadding mPaddingLeft or mPaddingTop
 596      * @param endPadding mPaddingRight or mPaddingBottom
 597      * @param mySize The width or height of this view (the RelativeLayout)
 598      * @return MeasureSpec for the child
 599      */
 600     private int getChildMeasureSpec(int childStart, int childEnd,
 601             int childSize, int startMargin, int endMargin, int startPadding,
 602             int endPadding, int mySize) {
 603         int childSpecMode = 0;
 604         int childSpecSize = 0;
 605
 606         // Figure out start and end bounds.
 607         int tempStart = childStart;
 608         int tempEnd = childEnd;
 609
 610         // If the view did not express a layout constraint for an edge, use
 611         // view's margins and our padding
 612         if (tempStart < 0) {
 613             tempStart = startPadding + startMargin;
 614         }
 615         if (tempEnd < 0) {
 616             tempEnd = mySize - endPadding - endMargin;
 617         }
 618
 619         // Figure out maximum size available to this view
 620         int maxAvailable = tempEnd - tempStart;
 621
 622         if (childStart >= 0 && childEnd >= 0) {
 623             // Constraints fixed both edges, so child must be an exact size
 624             childSpecMode = MeasureSpec.EXACTLY;
 625             childSpecSize = maxAvailable;
 626         } else {
 627             if (childSize >= 0) {
 628                 // Child wanted an exact size. Give as much as possible
 629                 childSpecMode = MeasureSpec.EXACTLY;
 630
 631                 if (maxAvailable >= 0) {
 632                     // We have a maxmum size in this dimension.
 633                     childSpecSize = Math.min(maxAvailable, childSize);
 634                 } else {
 635                     // We can grow in this dimension.
 636                     childSpecSize = childSize;
 637                 }
 638             } else if (childSize == LayoutParams.MATCH_PARENT) {
 639                 // Child wanted to be as big as possible. Give all availble
 640                 // space
 641                 childSpecMode = MeasureSpec.EXACTLY;
 642                 childSpecSize = maxAvailable;
 643             } else if (childSize == LayoutParams.WRAP_CONTENT) {
 644                 // Child wants to wrap content. Use AT_MOST
 645                 // to communicate available space if we know
 646                 // our max size
 647                 if (maxAvailable >= 0) {
 648                     // We have a maxmum size in this dimension.
 649                     childSpecMode = MeasureSpec.AT_MOST;
 650                     childSpecSize = maxAvailable;
 651                 } else {
 652                     // We can grow in this dimension. Child can be as big as it
 653                     // wants
 654                     childSpecMode = MeasureSpec.UNSPECIFIED;
 655                     childSpecSize = 0;
 656                 }
 657             }
 658         }
 659
 660         return MeasureSpec.makeMeasureSpec(childSpecSize, childSpecMode);
 661     }
 662
 663     private boolean positionChildHorizontal(View child, LayoutParams params, int myWidth,
 664             boolean wrapContent) {
 665
 666         int[] rules = params.getRules();
 667
 668         if (params.mLeft < 0 && params.mRight >= 0) {
 669             // Right is fixed, but left varies
 670             params.mLeft = params.mRight - child.getMeasuredWidth();
 671         } else if (params.mLeft >= 0 && params.mRight < 0) {
 672             // Left is fixed, but right varies
 673             params.mRight = params.mLeft + child.getMeasuredWidth();
 674         } else if (params.mLeft < 0 && params.mRight < 0) {
 675             // Both left and right vary
 676             if (rules[CENTER_IN_PARENT] != 0 || rules[CENTER_HORIZONTAL] != 0) {
 677                 if (!wrapContent) {
 678                     centerHorizontal(child, params, myWidth);
 679                 } else {
 680                     params.mLeft = mPaddingLeft + params.leftMargin;
 681                     params.mRight = params.mLeft + child.getMeasuredWidth();
 682                 }
 683                 return true;
 684             } else {
 685                 params.mLeft = mPaddingLeft + params.leftMargin;
 686                 params.mRight = params.mLeft + child.getMeasuredWidth();
 687             }
 688         }
 689         return rules[ALIGN_PARENT_RIGHT] != 0;
 690     }
 691
 692     private boolean positionChildVertical(View child, LayoutParams params, int myHeight,
 693             boolean wrapContent) {
 694
 695         int[] rules = params.getRules();
 696
 697         if (params.mTop < 0 && params.mBottom >= 0) {
 698             // Bottom is fixed, but top varies
 699             params.mTop = params.mBottom - child.getMeasuredHeight();
 700         } else if (params.mTop >= 0 && params.mBottom < 0) {
 701             // Top is fixed, but bottom varies
 702             params.mBottom = params.mTop + child.getMeasuredHeight();
 703         } else if (params.mTop < 0 && params.mBottom < 0) {
 704             // Both top and bottom vary
 705             if (rules[CENTER_IN_PARENT] != 0 || rules[CENTER_VERTICAL] != 0) {
 706                 if (!wrapContent) {
 707                     centerVertical(child, params, myHeight);
 708                 } else {
 709                     params.mTop = mPaddingTop + params.topMargin;
 710                     params.mBottom = params.mTop + child.getMeasuredHeight();
 711                 }
 712                 return true;
 713             } else {
 714                 params.mTop = mPaddingTop + params.topMargin;
 715                 params.mBottom = params.mTop + child.getMeasuredHeight();
 716             }
 717         }
 718         return rules[ALIGN_PARENT_BOTTOM] != 0;
 719     }
 720
 721     private void applyHorizontalSizeRules(LayoutParams childParams, int myWidth) {
 722         int[] rules = childParams.getRules();
 723         RelativeLayout.LayoutParams anchorParams;
 724
 725         // -1 indicated a "soft requirement" in that direction. For example:
 726         // left=10, right=-1 means the view must start at 10, but can go as far as it wants to the right
 727         // left =-1, right=10 means the view must end at 10, but can go as far as it wants to the left
 728         // left=10, right=20 means the left and right ends are both fixed
 729         childParams.mLeft = -1;
 730         childParams.mRight = -1;
 731
 732         anchorParams = getRelatedViewParams(rules, LEFT_OF);
 733         if (anchorParams != null) {
 734             childParams.mRight = anchorParams.mLeft - (anchorParams.leftMargin +
 735                     childParams.rightMargin);
 736         } else if (childParams.alignWithParent && rules[LEFT_OF] != 0) {
 737             if (myWidth >= 0) {
 738                 childParams.mRight = myWidth - mPaddingRight - childParams.rightMargin;
 739             } else {
 740                 // FIXME uh oh...
 741             }
 742         }
 743
 744         anchorParams = getRelatedViewParams(rules, RIGHT_OF);
 745         if (anchorParams != null) {
 746             childParams.mLeft = anchorParams.mRight + (anchorParams.rightMargin +
 747                     childParams.leftMargin);
 748         } else if (childParams.alignWithParent && rules[RIGHT_OF] != 0) {
 749             childParams.mLeft = mPaddingLeft + childParams.leftMargin;
 750         }
 751
 752         anchorParams = getRelatedViewParams(rules, ALIGN_LEFT);
 753         if (anchorParams != null) {
 754             childParams.mLeft = anchorParams.mLeft + childParams.leftMargin;
 755         } else if (childParams.alignWithParent && rules[ALIGN_LEFT] != 0) {
 756             childParams.mLeft = mPaddingLeft + childParams.leftMargin;
 757         }
 758
 759         anchorParams = getRelatedViewParams(rules, ALIGN_RIGHT);
 760         if (anchorParams != null) {
 761             childParams.mRight = anchorParams.mRight - childParams.rightMargin;
 762         } else if (childParams.alignWithParent && rules[ALIGN_RIGHT] != 0) {
 763             if (myWidth >= 0) {
 764                 childParams.mRight = myWidth - mPaddingRight - childParams.rightMargin;
 765             } else {
 766                 // FIXME uh oh...
 767             }
 768         }
 769
 770         if (0 != rules[ALIGN_PARENT_LEFT]) {
 771             childParams.mLeft = mPaddingLeft + childParams.leftMargin;
 772         }
 773
 774         if (0 != rules[ALIGN_PARENT_RIGHT]) {
 775             if (myWidth >= 0) {
 776                 childParams.mRight = myWidth - mPaddingRight - childParams.rightMargin;
 777             } else {
 778                 // FIXME uh oh...
 779             }
 780         }
 781     }
 782
 783     private void applyVerticalSizeRules(LayoutParams childParams, int myHeight) {
 784         int[] rules = childParams.getRules();
 785         RelativeLayout.LayoutParams anchorParams;
 786
 787         childParams.mTop = -1;
 788         childParams.mBottom = -1;
 789
 790         anchorParams = getRelatedViewParams(rules, ABOVE);
 791         if (anchorParams != null) {
 792             childParams.mBottom = anchorParams.mTop - (anchorParams.topMargin +
 793                     childParams.bottomMargin);
 794         } else if (childParams.alignWithParent && rules[ABOVE] != 0) {
 795             if (myHeight >= 0) {
 796                 childParams.mBottom = myHeight - mPaddingBottom - childParams.bottomMargin;
 797             } else {
 798                 // FIXME uh oh...
 799             }
 800         }
 801
 802         anchorParams = getRelatedViewParams(rules, BELOW);
 803         if (anchorParams != null) {
 804             childParams.mTop = anchorParams.mBottom + (anchorParams.bottomMargin +
 805                     childParams.topMargin);
 806         } else if (childParams.alignWithParent && rules[BELOW] != 0) {
 807             childParams.mTop = mPaddingTop + childParams.topMargin;
 808         }
 809
 810         anchorParams = getRelatedViewParams(rules, ALIGN_TOP);
 811         if (anchorParams != null) {
 812             childParams.mTop = anchorParams.mTop + childParams.topMargin;
 813         } else if (childParams.alignWithParent && rules[ALIGN_TOP] != 0) {
 814             childParams.mTop = mPaddingTop + childParams.topMargin;
 815         }
 816
 817         anchorParams = getRelatedViewParams(rules, ALIGN_BOTTOM);
 818         if (anchorParams != null) {
 819             childParams.mBottom = anchorParams.mBottom - childParams.bottomMargin;
 820         } else if (childParams.alignWithParent && rules[ALIGN_BOTTOM] != 0) {
 821             if (myHeight >= 0) {
 822                 childParams.mBottom = myHeight - mPaddingBottom - childParams.bottomMargin;
 823             } else {
 824                 // FIXME uh oh...
 825             }
 826         }
 827
 828         if (0 != rules[ALIGN_PARENT_TOP]) {
 829             childParams.mTop = mPaddingTop + childParams.topMargin;
 830         }
 831
 832         if (0 != rules[ALIGN_PARENT_BOTTOM]) {
 833             if (myHeight >= 0) {
 834                 childParams.mBottom = myHeight - mPaddingBottom - childParams.bottomMargin;
 835             } else {
 836                 // FIXME uh oh...
 837             }
 838         }
 839
 840         if (rules[ALIGN_BASELINE] != 0) {
 841             mHasBaselineAlignedChild = true;
 842         }
 843     }
 844
 845     private View getRelatedView(int[] rules, int relation) {
 846         int id = rules[relation];
 847         if (id != 0) {
 848             DependencyGraph.Node node = mGraph.mKeyNodes.get(id);
 849             if (node == null) return null;
 850             View v = node.view;
 851
 852             // Find the first non-GONE view up the chain
 853             while (v.getVisibility() == View.GONE) {
 854                 rules = ((LayoutParams) v.getLayoutParams()).getRules();
 855                 node = mGraph.mKeyNodes.get((rules[relation]));
 856                 if (node == null) return null;
 857                 v = node.view;
 858             }
 859
 860             return v;
 861         }
 862
 863         return null;
 864     }
 865
 866     private LayoutParams getRelatedViewParams(int[] rules, int relation) {
 867         View v = getRelatedView(rules, relation);
 868         if (v != null) {
 869             ViewGroup.LayoutParams params = v.getLayoutParams();
 870             if (params instanceof LayoutParams) {
 871                 return (LayoutParams) v.getLayoutParams();
 872             }
 873         }
 874         return null;
 875     }
 876
 877     private int getRelatedViewBaseline(int[] rules, int relation) {
 878         View v = getRelatedView(rules, relation);
 879         if (v != null) {
 880             return v.getBaseline();
 881         }
 882         return -1;
 883     }
 884
 885     private void centerHorizontal(View child, LayoutParams params, int myWidth) {
 886         int childWidth = child.getMeasuredWidth();
 887         int left = (myWidth - childWidth) / 2;
 888
 889         params.mLeft = left;
 890         params.mRight = left + childWidth;
 891     }
 892
 893     private void centerVertical(View child, LayoutParams params, int myHeight) {
 894         int childHeight = child.getMeasuredHeight();
 895         int top = (myHeight - childHeight) / 2;
 896
 897         params.mTop = top;
 898         params.mBottom = top + childHeight;
 899     }
 900
 901     @Override
 902     protected void onLayout(boolean changed, int l, int t, int r, int b) {
 903         //  The layout has actually already been performed and the positions
 904         //  cached.  Apply the cached values to the children.
 905         int count = getChildCount();
 906
 907         for (int i = 0; i < count; i++) {
 908             View child = getChildAt(i);
 909             if (child.getVisibility() != GONE) {
 910                 RelativeLayout.LayoutParams st =
 911                         (RelativeLayout.LayoutParams) child.getLayoutParams();
 912                 child.layout(st.mLeft, st.mTop, st.mRight, st.mBottom);
 913
 914             }
 915         }
 916     }
 917
 918     @Override
 919     public LayoutParams generateLayoutParams(AttributeSet attrs) {
 920         return new RelativeLayout.LayoutParams(getContext(), attrs);
 921     }
 922
 923     /**
 924      * Returns a set of layout parameters with a width of
 925      * {@link android.view.ViewGroup.LayoutParams#WRAP_CONTENT},
 926      * a height of {@link android.view.ViewGroup.LayoutParams#WRAP_CONTENT} and no spanning.
 927      */
 928     @Override
 929     protected ViewGroup.LayoutParams generateDefaultLayoutParams() {
 930         return new LayoutParams(LayoutParams.WRAP_CONTENT, LayoutParams.WRAP_CONTENT);
 931     }
 932
 933     // Override to allow type-checking of LayoutParams.
 934     @Override
 935     protected boolean checkLayoutParams(ViewGroup.LayoutParams p) {
 936         return p instanceof RelativeLayout.LayoutParams;
 937     }
 938
 939     @Override
 940     protected ViewGroup.LayoutParams generateLayoutParams(ViewGroup.LayoutParams p) {
 941         return new LayoutParams(p);
 942     }
 943
 944     @Override
 945     public boolean dispatchPopulateAccessibilityEvent(AccessibilityEvent event) {
 946         if (mTopToBottomLeftToRightSet == null) {
 947             mTopToBottomLeftToRightSet = new TreeSet<View>(new TopToBottomLeftToRightComparator());
 948         }
 949
 950         // sort children top-to-bottom and left-to-right
 951         for (int i = 0, count = getChildCount(); i < count; i++) {
 952             mTopToBottomLeftToRightSet.add(getChildAt(i));
 953         }
 954
 955         for (View view : mTopToBottomLeftToRightSet) {
 956             if (view.dispatchPopulateAccessibilityEvent(event)) {
 957                 mTopToBottomLeftToRightSet.clear();
 958                 return true;
 959             }
 960         }
 961
 962         mTopToBottomLeftToRightSet.clear();
 963         return false;
 964     }
 965
 966     /**
 967      * Compares two views in left-to-right and top-to-bottom fashion.
 968      */
 969      private class TopToBottomLeftToRightComparator implements Comparator<View> {
 970         public int compare(View first, View second) {
 971             // top - bottom
 972             int topDifference = first.getTop() - second.getTop();
 973             if (topDifference != 0) {
 974                 return topDifference;
 975             }
 976             // left - right
 977             int leftDifference = first.getLeft() - second.getLeft();
 978             if (leftDifference != 0) {
 979                 return leftDifference;
 980             }
 981             // break tie by height
 982             int heightDiference = first.getHeight() - second.getHeight();
 983             if (heightDiference != 0) {
 984                 return heightDiference;
 985             }
 986             // break tie by width
 987             int widthDiference = first.getWidth() - second.getWidth();
 988             if (widthDiference != 0) {
 989                 return widthDiference;
 990             }
 991             return 0;
 992         }
 993     }
 994
 995     /**
 996      * Per-child layout information associated with RelativeLayout.
 997      *
 998      * @attr ref android.R.styleable#RelativeLayout_Layout_layout_alignWithParentIfMissing
 999      * @attr ref android.R.styleable#RelativeLayout_Layout_layout_toLeftOf
1000      * @attr ref android.R.styleable#RelativeLayout_Layout_layout_toRightOf
1001      * @attr ref android.R.styleable#RelativeLayout_Layout_layout_above
1002      * @attr ref android.R.styleable#RelativeLayout_Layout_layout_below
1003      * @attr ref android.R.styleable#RelativeLayout_Layout_layout_alignBaseline
1004      * @attr ref android.R.styleable#RelativeLayout_Layout_layout_alignLeft
1005      * @attr ref android.R.styleable#RelativeLayout_Layout_layout_alignTop
1006      * @attr ref android.R.styleable#RelativeLayout_Layout_layout_alignRight
1007      * @attr ref android.R.styleable#RelativeLayout_Layout_layout_alignBottom
1008      * @attr ref android.R.styleable#RelativeLayout_Layout_layout_alignParentLeft
1009      * @attr ref android.R.styleable#RelativeLayout_Layout_layout_alignParentTop
1010      * @attr ref android.R.styleable#RelativeLayout_Layout_layout_alignParentRight
1011      * @attr ref android.R.styleable#RelativeLayout_Layout_layout_alignParentBottom
1012      * @attr ref android.R.styleable#RelativeLayout_Layout_layout_centerInParent
1013      * @attr ref android.R.styleable#RelativeLayout_Layout_layout_centerHorizontal
1014      * @attr ref android.R.styleable#RelativeLayout_Layout_layout_centerVertical
1015      */
1016     public static class LayoutParams extends ViewGroup.MarginLayoutParams {
1017         @ViewDebug.ExportedProperty(category = "layout", resolveId = true, indexMapping = {
1018             @ViewDebug.IntToString(from = ABOVE,               to = "above"),
1019             @ViewDebug.IntToString(from = ALIGN_BASELINE,      to = "alignBaseline"),
1020             @ViewDebug.IntToString(from = ALIGN_BOTTOM,        to = "alignBottom"),
1021             @ViewDebug.IntToString(from = ALIGN_LEFT,          to = "alignLeft"),
1022             @ViewDebug.IntToString(from = ALIGN_PARENT_BOTTOM, to = "alignParentBottom"),
1023             @ViewDebug.IntToString(from = ALIGN_PARENT_LEFT,   to = "alignParentLeft"),
1024             @ViewDebug.IntToString(from = ALIGN_PARENT_RIGHT,  to = "alignParentRight"),
1025             @ViewDebug.IntToString(from = ALIGN_PARENT_TOP,    to = "alignParentTop"),
1026             @ViewDebug.IntToString(from = ALIGN_RIGHT,         to = "alignRight"),
1027             @ViewDebug.IntToString(from = ALIGN_TOP,           to = "alignTop"),
1028             @ViewDebug.IntToString(from = BELOW,               to = "below"),
1029             @ViewDebug.IntToString(from = CENTER_HORIZONTAL,   to = "centerHorizontal"),
1030             @ViewDebug.IntToString(from = CENTER_IN_PARENT,    to = "center"),
1031             @ViewDebug.IntToString(from = CENTER_VERTICAL,     to = "centerVertical"),
1032             @ViewDebug.IntToString(from = LEFT_OF,             to = "leftOf"),
1033             @ViewDebug.IntToString(from = RIGHT_OF,            to = "rightOf")
1034         }, mapping = {
1035             @ViewDebug.IntToString(from = TRUE, to = "true"),
1036             @ViewDebug.IntToString(from = 0,    to = "false/NO_ID")
1037         })
1038         private int[] mRules = new int[VERB_COUNT];
1039
1040         private int mLeft, mTop, mRight, mBottom;
1041
1042         /**
1043          * When true, uses the parent as the anchor if the anchor doesn't exist or if
1044          * the anchor's visibility is GONE.
1045          */
1046         @ViewDebug.ExportedProperty(category = "layout")
1047         public boolean alignWithParent;
1048
1049         public LayoutParams(Context c, AttributeSet attrs) {
1050             super(c, attrs);
1051
1052             TypedArray a = c.obtainStyledAttributes(attrs,
1053                     com.android.internal.R.styleable.RelativeLayout_Layout);
1054
1055             final int[] rules = mRules;
1056
1057             final int N = a.getIndexCount();
1058             for (int i = 0; i < N; i++) {
1059                 int attr = a.getIndex(i);
1060                 switch (attr) {
1061                     case com.android.internal.R.styleable.RelativeLayout_Layout_layout_alignWithParentIfMissing:
1062                         alignWithParent = a.getBoolean(attr, false);
1063                         break;
1064                     case com.android.internal.R.styleable.RelativeLayout_Layout_layout_toLeftOf:
1065                         rules[LEFT_OF] = a.getResourceId(attr, 0);
1066                         break;
1067                     case com.android.internal.R.styleable.RelativeLayout_Layout_layout_toRightOf:
1068                         rules[RIGHT_OF] = a.getResourceId(attr, 0);
1069                         break;
1070                     case com.android.internal.R.styleable.RelativeLayout_Layout_layout_above:
1071                         rules[ABOVE] = a.getResourceId(attr, 0);
1072                         break;
1073                     case com.android.internal.R.styleable.RelativeLayout_Layout_layout_below:
1074                         rules[BELOW] = a.getResourceId(attr, 0);
1075                         break;
1076                     case com.android.internal.R.styleable.RelativeLayout_Layout_layout_alignBaseline:
1077                         rules[ALIGN_BASELINE] = a.getResourceId(attr, 0);
1078                         break;
1079                     case com.android.internal.R.styleable.RelativeLayout_Layout_layout_alignLeft:
1080                         rules[ALIGN_LEFT] = a.getResourceId(attr, 0);
1081                         break;
1082                     case com.android.internal.R.styleable.RelativeLayout_Layout_layout_alignTop:
1083                         rules[ALIGN_TOP] = a.getResourceId(attr, 0);
1084                         break;
1085                     case com.android.internal.R.styleable.RelativeLayout_Layout_layout_alignRight:
1086                         rules[ALIGN_RIGHT] = a.getResourceId(attr, 0);
1087                         break;
1088                     case com.android.internal.R.styleable.RelativeLayout_Layout_layout_alignBottom:
1089                         rules[ALIGN_BOTTOM] = a.getResourceId(attr, 0);
1090                         break;
1091                     case com.android.internal.R.styleable.RelativeLayout_Layout_layout_alignParentLeft:
1092                         rules[ALIGN_PARENT_LEFT] = a.getBoolean(attr, false) ? TRUE : 0;
1093                         break;
1094                     case com.android.internal.R.styleable.RelativeLayout_Layout_layout_alignParentTop:
1095                         rules[ALIGN_PARENT_TOP] = a.getBoolean(attr, false) ? TRUE : 0;
1096                         break;
1097                     case com.android.internal.R.styleable.RelativeLayout_Layout_layout_alignParentRight:
1098                         rules[ALIGN_PARENT_RIGHT] = a.getBoolean(attr, false) ? TRUE : 0;
1099                         break;
1100                     case com.android.internal.R.styleable.RelativeLayout_Layout_layout_alignParentBottom:
1101                         rules[ALIGN_PARENT_BOTTOM] = a.getBoolean(attr, false) ? TRUE : 0;
1102                         break;
1103                     case com.android.internal.R.styleable.RelativeLayout_Layout_layout_centerInParent:
1104                         rules[CENTER_IN_PARENT] = a.getBoolean(attr, false) ? TRUE : 0;
1105                         break;
1106                     case com.android.internal.R.styleable.RelativeLayout_Layout_layout_centerHorizontal:
1107                         rules[CENTER_HORIZONTAL] = a.getBoolean(attr, false) ? TRUE : 0;
1108                         break;
1109                     case com.android.internal.R.styleable.RelativeLayout_Layout_layout_centerVertical:
1110                         rules[CENTER_VERTICAL] = a.getBoolean(attr, false) ? TRUE : 0;
1111                        break;
1112                 }
1113             }
1114
1115             a.recycle();
1116         }
1117
1118         public LayoutParams(int w, int h) {
1119             super(w, h);
1120         }
1121
1122         /**
1123          * {@inheritDoc}
1124          */
1125         public LayoutParams(ViewGroup.LayoutParams source) {
1126             super(source);
1127         }
1128
1129         /**
1130          * {@inheritDoc}
1131          */
1132         public LayoutParams(ViewGroup.MarginLayoutParams source) {
1133             super(source);
1134         }
1135
1136         @Override
1137         public String debug(String output) {
1138             return output + "ViewGroup.LayoutParams={ width=" + sizeToString(width) +
1139                     ", height=" + sizeToString(height) + " }";
1140         }
1141
1142         /**
1143          * Adds a layout rule to be interpreted by the RelativeLayout. This
1144          * method should only be used for constraints that don't refer to another sibling
1145          * (e.g., CENTER_IN_PARENT) or take a boolean value ({@link RelativeLayout#TRUE}
1146          * for true or - for false). To specify a verb that takes a subject, use
1147          * {@link #addRule(int, int)} instead.
1148          *
1149          * @param verb One of the verbs defined by
1150          *        {@link android.widget.RelativeLayout RelativeLayout}, such as
1151          *        ALIGN_WITH_PARENT_LEFT.
1152          * @see #addRule(int, int)
1153          */
1154         public void addRule(int verb) {
1155             mRules[verb] = TRUE;
1156         }
1157
1158         /**
1159          * Adds a layout rule to be interpreted by the RelativeLayout. Use this for
1160          * verbs that take a target, such as a sibling (ALIGN_RIGHT) or a boolean
1161          * value (VISIBLE).
1162          *
1163          * @param verb One of the verbs defined by
1164          *        {@link android.widget.RelativeLayout RelativeLayout}, such as
1165          *         ALIGN_WITH_PARENT_LEFT.
1166          * @param anchor The id of another view to use as an anchor,
1167          *        or a boolean value(represented as {@link RelativeLayout#TRUE})
1168          *        for true or 0 for false).  For verbs that don't refer to another sibling
1169          *        (for example, ALIGN_WITH_PARENT_BOTTOM) just use -1.
1170          * @see #addRule(int)
1171          */
1172         public void addRule(int verb, int anchor) {
1173             mRules[verb] = anchor;
1174         }
1175
1176         /**
1177          * Retrieves a complete list of all supported rules, where the index is the rule
1178          * verb, and the element value is the value specified, or "false" if it was never
1179          * set.
1180          *
1181          * @return the supported rules
1182          * @see #addRule(int, int)
1183          */
1184         public int[] getRules() {
1185             return mRules;
1186         }
1187     }
1188
1189     private static class DependencyGraph {
1190         /**
1191          * List of all views in the graph.
1192          */
1193         private ArrayList<Node> mNodes = new ArrayList<Node>();
1194
1195         /**
1196          * List of nodes in the graph. Each node is identified by its
1197          * view id (see View#getId()).
1198          */
1199         private SparseArray<Node> mKeyNodes = new SparseArray<Node>();
1200
1201         /**
1202          * Temporary data structure used to build the list of roots
1203          * for this graph.
1204          */
1205         private LinkedList<Node> mRoots = new LinkedList<Node>();
1206
1207         /**
1208          * Clears the graph.
1209          */
1210         void clear() {
1211             final ArrayList<Node> nodes = mNodes;
1212             final int count = nodes.size();
1213
1214             for (int i = 0; i < count; i++) {
1215                 nodes.get(i).release();
1216             }
1217             nodes.clear();
1218
1219             mKeyNodes.clear();
1220             mRoots.clear();
1221         }
1222
1223         /**
1224          * Adds a view to the graph.
1225          *
1226          * @param view The view to be added as a node to the graph.
1227          */
1228         void add(View view) {
1229             final int id = view.getId();
1230             final Node node = Node.acquire(view);
1231
1232             if (id != View.NO_ID) {
1233                 mKeyNodes.put(id, node);
1234             }
1235
1236             mNodes.add(node);
1237         }
1238
1239         /**
1240          * Builds a sorted list of views. The sorting order depends on the dependencies
1241          * between the view. For instance, if view C needs view A to be processed first
1242          * and view A needs view B to be processed first, the dependency graph
1243          * is: B -> A -> C. The sorted array will contain views B, A and C in this order.
1244          *
1245          * @param sorted The sorted list of views. The length of this array must
1246          *        be equal to getChildCount().
1247          * @param rules The list of rules to take into account.
1248          */
1249         void getSortedViews(View[] sorted, int... rules) {
1250             final LinkedList<Node> roots = findRoots(rules);
1251             int index = 0;
1252
1253             while (roots.size() > 0) {
1254                 final Node node = roots.removeFirst();
1255                 final View view = node.view;
1256                 final int key = view.getId();
1257
1258                 sorted[index++] = view;
1259
1260                 final HashSet<Node> dependents = node.dependents;
1261                 for (Node dependent : dependents) {
1262                     final SparseArray<Node> dependencies = dependent.dependencies;
1263
1264                     dependencies.remove(key);
1265                     if (dependencies.size() == 0) {
1266                         roots.add(dependent);
1267                     }
1268                 }
1269             }
1270
1271             if (index < sorted.length) {
1272                 throw new IllegalStateException("Circular dependencies cannot exist"
1273                         + " in RelativeLayout");
1274             }
1275         }
1276
1277         /**
1278          * Finds the roots of the graph. A root is a node with no dependency and
1279          * with [0..n] dependents.
1280          *
1281          * @param rulesFilter The list of rules to consider when building the
1282          *        dependencies
1283          *
1284          * @return A list of node, each being a root of the graph
1285          */
1286         private LinkedList<Node> findRoots(int[] rulesFilter) {
1287             final SparseArray<Node> keyNodes = mKeyNodes;
1288             final ArrayList<Node> nodes = mNodes;
1289             final int count = nodes.size();
1290
1291             // Find roots can be invoked several times, so make sure to clear
1292             // all dependents and dependencies before running the algorithm
1293             for (int i = 0; i < count; i++) {
1294                 final Node node = nodes.get(i);
1295                 node.dependents.clear();
1296                 node.dependencies.clear();
1297             }
1298
1299             // Builds up the dependents and dependencies for each node of the graph
1300             for (int i = 0; i < count; i++) {
1301                 final Node node = nodes.get(i);
1302
1303                 final LayoutParams layoutParams = (LayoutParams) node.view.getLayoutParams();
1304                 final int[] rules = layoutParams.mRules;
1305                 final int rulesCount = rulesFilter.length;
1306
1307                 // Look only the the rules passed in parameter, this way we build only the
1308                 // dependencies for a specific set of rules
1309                 for (int j = 0; j < rulesCount; j++) {
1310                     final int rule = rules[rulesFilter[j]];
1311                     if (rule > 0) {
1312                         // The node this node depends on
1313                         final Node dependency = keyNodes.get(rule);
1314                         // Skip unknowns and self dependencies
1315                         if (dependency == null || dependency == node) {
1316                             continue;
1317                         }
1318                         // Add the current node as a dependent
1319                         dependency.dependents.add(node);
1320                         // Add a dependency to the current node
1321                         node.dependencies.put(rule, dependency);
1322                     }
1323                 }
1324             }
1325
1326             final LinkedList<Node> roots = mRoots;
1327             roots.clear();
1328
1329             // Finds all the roots in the graph: all nodes with no dependencies
1330             for (int i = 0; i < count; i++) {
1331                 final Node node = nodes.get(i);
1332                 if (node.dependencies.size() == 0) roots.add(node);
1333             }
1334
1335             return roots;
1336         }
1337
1338         /**
1339          * Prints the dependency graph for the specified rules.
1340          *
1341          * @param resources The context's resources to print the ids.
1342          * @param rules The list of rules to take into account.
1343          */
1344         void log(Resources resources, int... rules) {
1345             final LinkedList<Node> roots = findRoots(rules);
1346             for (Node node : roots) {
1347                 printNode(resources, node);
1348             }
1349         }
1350
1351         static void printViewId(Resources resources, View view) {
1352             if (view.getId() != View.NO_ID) {
1353                 d(LOG_TAG, resources.getResourceEntryName(view.getId()));
1354             } else {
1355                 d(LOG_TAG, "NO_ID");
1356             }
1357         }
1358
1359         private static void appendViewId(Resources resources, Node node, StringBuilder buffer) {
1360             if (node.view.getId() != View.NO_ID) {
1361                 buffer.append(resources.getResourceEntryName(node.view.getId()));
1362             } else {
1363                 buffer.append("NO_ID");
1364             }
1365         }
1366
1367         private static void printNode(Resources resources, Node node) {
1368             if (node.dependents.size() == 0) {
1369                 printViewId(resources, node.view);
1370             } else {
1371                 for (Node dependent : node.dependents) {
1372                     StringBuilder buffer = new StringBuilder();
1373                     appendViewId(resources, node, buffer);
1374                     printdependents(resources, dependent, buffer);
1375                 }
1376             }
1377         }
1378
1379         private static void printdependents(Resources resources, Node node, StringBuilder buffer) {
1380             buffer.append(" -> ");
1381             appendViewId(resources, node, buffer);
1382
1383             if (node.dependents.size() == 0) {
1384                 d(LOG_TAG, buffer.toString());
1385             } else {
1386                 for (Node dependent : node.dependents) {
1387                     StringBuilder subBuffer = new StringBuilder(buffer);
1388                     printdependents(resources, dependent, subBuffer);
1389                 }
1390             }
1391         }
1392
1393         /**
1394          * A node in the dependency graph. A node is a view, its list of dependencies
1395          * and its list of dependents.
1396          *
1397          * A node with no dependent is considered a root of the graph.
1398          */
1399         static class Node implements Poolable<Node> {
1400             /**
1401              * The view representing this node in the layout.
1402              */
1403             View view;
1404
1405             /**
1406              * The list of dependents for this node; a dependent is a node
1407              * that needs this node to be processed first.
1408              */
1409             final HashSet<Node> dependents = new HashSet<Node>();
1410
1411             /**
1412              * The list of dependencies for this node.
1413              */
1414             final SparseArray<Node> dependencies = new SparseArray<Node>();
1415
1416             /*
1417              * START POOL IMPLEMENTATION
1418              */
1419             // The pool is static, so all nodes instances are shared across
1420             // activities, that's why we give it a rather high limit
1421             private static final int POOL_LIMIT = 100;
1422             private static final Pool<Node> sPool = Pools.synchronizedPool(
1423                     Pools.finitePool(new PoolableManager<Node>() {
1424                         public Node newInstance() {
1425                             return new Node();
1426                         }
1427
1428                         public void onAcquired(Node element) {
1429                         }
1430
1431                         public void onReleased(Node element) {
1432                         }
1433                     }, POOL_LIMIT)
1434             );
1435
1436             private Node mNext;
1437
1438             public void setNextPoolable(Node element) {
1439                 mNext = element;
1440             }
1441
1442             public Node getNextPoolable() {
1443                 return mNext;
1444             }
1445
1446             static Node acquire(View view) {
1447                 final Node node = sPool.acquire();
1448                 node.view = view;
1449
1450                 return node;
1451             }
1452
1453             void release() {
1454                 view = null;
1455                 dependents.clear();
1456                 dependencies.clear();
1457
1458                 sPool.release(this);
1459             }
1460             /*
1461              * END POOL IMPLEMENTATION
1462              */
1463         }
1464     }
1465 }