Merge "Fix Snackbar theme on sw600dp" into nyc-support-24.1-dev
diff --git a/api/current.txt b/api/current.txt
index 36b2296..a1cbcb3 100644
--- a/api/current.txt
+++ b/api/current.txt
@@ -444,6 +444,7 @@
     method public void dispatchDependentViewsChanged(android.view.View);
     method public boolean doViewsOverlap(android.view.View, android.view.View);
     method public java.util.List<android.view.View> getDependencies(android.view.View);
+    method public java.util.List<android.view.View> getDependents(android.view.View);
     method public android.graphics.drawable.Drawable getStatusBarBackground();
     method public boolean isPointInChildBounds(android.view.View, int, int);
     method public void onAttachedToWindow();
diff --git a/design/build.gradle b/design/build.gradle
index b949d61..ccbffb2 100644
--- a/design/build.gradle
+++ b/design/build.gradle
@@ -40,6 +40,8 @@
         androidTest.java.srcDir 'tests/src'
         androidTest.res.srcDir 'tests/res'
         androidTest.manifest.srcFile 'tests/AndroidManifest.xml'
+
+        test.java.srcDir 'jvm-tests/src'
     }
 
     compileOptions {
diff --git a/design/jvm-tests/NO_DOCS b/design/jvm-tests/NO_DOCS
new file mode 100644
index 0000000..092a39c
--- /dev/null
+++ b/design/jvm-tests/NO_DOCS
@@ -0,0 +1,17 @@
+# Copyright (C) 2016 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#      http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+Having this file, named NO_DOCS, in a directory will prevent
+Android javadocs from being generated for java files under
+the directory. This is especially useful for test projects.
diff --git a/design/jvm-tests/src/android/support/design/widget/DirectedAcyclicGraphTest.java b/design/jvm-tests/src/android/support/design/widget/DirectedAcyclicGraphTest.java
new file mode 100644
index 0000000..58501be
--- /dev/null
+++ b/design/jvm-tests/src/android/support/design/widget/DirectedAcyclicGraphTest.java
@@ -0,0 +1,209 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package android.support.design.widget;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertNotNull;
+import static org.junit.Assert.assertTrue;
+
+import android.support.annotation.NonNull;
+import android.test.suitebuilder.annotation.SmallTest;
+
+import org.junit.Before;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.JUnit4;
+
+import java.util.List;
+
+@RunWith(JUnit4.class)
+@SmallTest
+public class DirectedAcyclicGraphTest {
+
+    private DirectedAcyclicGraph<TestNode> mGraph;
+
+    @Before
+    public void setup() {
+        mGraph = new DirectedAcyclicGraph<>();
+    }
+
+    @Test
+    public void test_addNode() {
+        final TestNode node = new TestNode("node");
+        mGraph.addNode(node);
+        assertEquals(1, mGraph.size());
+        assertTrue(mGraph.contains(node));
+    }
+
+    @Test
+    public void test_addNodeAgain() {
+        final TestNode node = new TestNode("node");
+        mGraph.addNode(node);
+        mGraph.addNode(node);
+
+        assertEquals(1, mGraph.size());
+        assertTrue(mGraph.contains(node));
+    }
+
+    @Test
+    public void test_addEdge() {
+        final TestNode node = new TestNode("node");
+        final TestNode edge = new TestNode("edge");
+
+        mGraph.addNode(node);
+        mGraph.addNode(edge);
+        mGraph.addEdge(node, edge);
+    }
+
+    @Test(expected = IllegalArgumentException.class)
+    public void test_addEdgeWithNotAddedEdgeNode() {
+        final TestNode node = new TestNode("node");
+        final TestNode edge = new TestNode("edge");
+
+        // Add the node, but not the edge node
+        mGraph.addNode(node);
+
+        // Now add the link
+        mGraph.addEdge(node, edge);
+    }
+
+    @Test
+    public void test_getIncomingEdges() {
+        final TestNode node = new TestNode("node");
+        final TestNode edge = new TestNode("edge");
+        mGraph.addNode(node);
+        mGraph.addNode(edge);
+        mGraph.addEdge(node, edge);
+
+        final List<TestNode> incomingEdges = mGraph.getIncomingEdges(node);
+        assertNotNull(incomingEdges);
+        assertEquals(1, incomingEdges.size());
+        assertEquals(edge, incomingEdges.get(0));
+    }
+
+    @Test
+    public void test_getOutgoingEdges() {
+        final TestNode node = new TestNode("node");
+        final TestNode edge = new TestNode("edge");
+        mGraph.addNode(node);
+        mGraph.addNode(edge);
+        mGraph.addEdge(node, edge);
+
+        // Now assert the getOutgoingEdges returns a list which has one element (node)
+        final List<TestNode> outgoingEdges = mGraph.getOutgoingEdges(edge);
+        assertNotNull(outgoingEdges);
+        assertEquals(1, outgoingEdges.size());
+        assertTrue(outgoingEdges.contains(node));
+    }
+
+    @Test
+    public void test_getOutgoingEdgesMultiple() {
+        final TestNode node1 = new TestNode("1");
+        final TestNode node2 = new TestNode("2");
+        final TestNode edge = new TestNode("edge");
+        mGraph.addNode(node1);
+        mGraph.addNode(node2);
+        mGraph.addNode(edge);
+
+        mGraph.addEdge(node1, edge);
+        mGraph.addEdge(node2, edge);
+
+        // Now assert the getOutgoingEdges returns a list which has 2 elements (node1 & node2)
+        final List<TestNode> outgoingEdges = mGraph.getOutgoingEdges(edge);
+        assertNotNull(outgoingEdges);
+        assertEquals(2, outgoingEdges.size());
+        assertTrue(outgoingEdges.contains(node1));
+        assertTrue(outgoingEdges.contains(node2));
+    }
+
+    @Test
+    public void test_hasOutgoingEdges() {
+        final TestNode node = new TestNode("node");
+        final TestNode edge = new TestNode("edge");
+        mGraph.addNode(node);
+        mGraph.addNode(edge);
+
+        // There is no edge currently and assert that fact
+        assertFalse(mGraph.hasOutgoingEdges(edge));
+        // Now add the edge
+        mGraph.addEdge(node, edge);
+        // and assert that the methods returns true;
+        assertTrue(mGraph.hasOutgoingEdges(edge));
+    }
+
+    @Test
+    public void test_clear() {
+        final TestNode node1 = new TestNode("1");
+        final TestNode node2 = new TestNode("2");
+        final TestNode edge = new TestNode("edge");
+        mGraph.addNode(node1);
+        mGraph.addNode(node2);
+        mGraph.addNode(edge);
+
+        // Now clear the graph
+        mGraph.clear();
+
+        // Now assert the graph is empty and that contains returns false
+        assertEquals(0, mGraph.size());
+        assertFalse(mGraph.contains(node1));
+        assertFalse(mGraph.contains(node2));
+        assertFalse(mGraph.contains(edge));
+    }
+
+    @Test
+    public void test_getSortedList() {
+        final TestNode node1 = new TestNode("A");
+        final TestNode node2 = new TestNode("B");
+        final TestNode node3 = new TestNode("C");
+        final TestNode node4 = new TestNode("D");
+
+        // Now we'll add the nodes
+        mGraph.addNode(node1);
+        mGraph.addNode(node2);
+        mGraph.addNode(node3);
+        mGraph.addNode(node4);
+
+        // Now we'll add edges so that 4 <- 2, 2 <- 3, 3 <- 1  (where <- denotes a dependency)
+        mGraph.addEdge(node4, node2);
+        mGraph.addEdge(node2, node3);
+        mGraph.addEdge(node3, node1);
+
+        final List<TestNode> sorted = mGraph.getSortedList();
+        // Assert that it is the correct size
+        assertEquals(4, sorted.size());
+        // Assert that all of the nodes are present and in their sorted order
+        assertEquals(node1, sorted.get(0));
+        assertEquals(node3, sorted.get(1));
+        assertEquals(node2, sorted.get(2));
+        assertEquals(node4, sorted.get(3));
+    }
+
+    private static class TestNode {
+        private final String mLabel;
+
+        TestNode(@NonNull String label) {
+            mLabel = label;
+        }
+
+        @Override
+        public String toString() {
+            return "TestNode: " + mLabel;
+        }
+    }
+
+}
diff --git a/design/src/android/support/design/internal/BottomNavigationMenuView.java b/design/src/android/support/design/internal/BottomNavigationMenuView.java
index 51750ac..0c44ed9 100644
--- a/design/src/android/support/design/internal/BottomNavigationMenuView.java
+++ b/design/src/android/support/design/internal/BottomNavigationMenuView.java
@@ -57,11 +57,7 @@
     }
 
     public BottomNavigationMenuView(Context context, AttributeSet attrs) {
-        this(context, attrs, 0);
-    }
-
-    public BottomNavigationMenuView(Context context, AttributeSet attrs, int defStyleAttr) {
-        super(context, attrs, defStyleAttr);
+        super(context, attrs);
         setGravity(Gravity.CENTER);
         setOrientation(HORIZONTAL);
 
diff --git a/design/src/android/support/design/widget/BottomNavigationView.java b/design/src/android/support/design/widget/BottomNavigationView.java
index c271757..0f04ce3 100644
--- a/design/src/android/support/design/widget/BottomNavigationView.java
+++ b/design/src/android/support/design/widget/BottomNavigationView.java
@@ -40,15 +40,23 @@
 import android.widget.LinearLayout;
 
 /**
- * Represents a standard bottom navigation bar for application. It is an implementation of material
- * design bottom navigation. See https://material.google.com/components/bottom-navigation.html
+ * <p>
+ * Represents a standard bottom navigation bar for application. It is an implementation of
+ * <a href="https://material.google.com/components/bottom-navigation.html">material design bottom
+ * navigation</a>.
+ * </p>
  *
+ * <p>
  * Bottom navigation bars make it easy for users to explore and switch between top-level views in
  * a single tap. It should be used when application has three to five top-level destinations.
+ * </p>
  *
+ * <p>
  * The bar contents can be populated by specifying a menu resource file. Each menu item title, icon
  * and enabled state will be used for displaying bottom navigation bar items.
+ * </p>
  *
+ * <pre>
  * &lt;android.support.design.widget.BottomNavigationView
  *     xmlns:android="http://schemas.android.com/apk/res/android"
  *     xmlns:app="http://schemas.android.com/apk/res-auto"
@@ -57,6 +65,7 @@
  *     android:layout_height="match_parent"
  *     android:layout_gravity="start"
  *     app:menu="@menu/my_navigation_items" /&gt;
+ * </pre>
  */
 public class BottomNavigationView extends FrameLayout {
 
diff --git a/design/src/android/support/design/widget/CoordinatorLayout.java b/design/src/android/support/design/widget/CoordinatorLayout.java
index 9420920..258e47d 100644
--- a/design/src/android/support/design/widget/CoordinatorLayout.java
+++ b/design/src/android/support/design/widget/CoordinatorLayout.java
@@ -35,6 +35,7 @@
 import android.support.annotation.IntDef;
 import android.support.annotation.NonNull;
 import android.support.annotation.Nullable;
+import android.support.annotation.VisibleForTesting;
 import android.support.design.R;
 import android.support.v4.content.ContextCompat;
 import android.support.v4.graphics.drawable.DrawableCompat;
@@ -128,22 +129,6 @@
     static final ThreadLocal<Map<String, Constructor<Behavior>>> sConstructors =
             new ThreadLocal<>();
 
-    final Comparator<View> mLayoutDependencyComparator = new Comparator<View>() {
-        @Override
-        public int compare(View lhs, View rhs) {
-            if (lhs == rhs) {
-                return 0;
-            } else if (((LayoutParams) lhs.getLayoutParams()).dependsOn(
-                    CoordinatorLayout.this, lhs, rhs)) {
-                return 1;
-            } else if (((LayoutParams) rhs.getLayoutParams()).dependsOn(
-                    CoordinatorLayout.this, rhs, lhs)) {
-                return -1;
-            } else {
-                return 0;
-            }
-        }
-    };
 
     private static final int EVENT_PRE_DRAW = 0;
     private static final int EVENT_NESTED_SCROLL = 1;
@@ -156,7 +141,9 @@
 
     static final Comparator<View> TOP_SORTED_CHILDREN_COMPARATOR;
 
-    private final List<View> mDependencySortedChildren = new ArrayList<View>();
+    private final List<View> mDependencySortedChildren = new ArrayList<>();
+    private final DirectedAcyclicGraph<View> mChildDag = new DirectedAcyclicGraph<>();
+
     private final List<View> mTempList1 = new ArrayList<>();
     private final List<View> mTempDependenciesList = new ArrayList<>();
     private final Rect mTempRect1 = new Rect();
@@ -635,19 +622,47 @@
         return result;
     }
 
-    private void prepareChildren() {
-        mDependencySortedChildren.clear();
-        for (int i = 0, count = getChildCount(); i < count; i++) {
-            final View child = getChildAt(i);
-
-            final LayoutParams lp = getResolvedLayoutParams(child);
-            lp.findAnchorView(this, child);
-
-            mDependencySortedChildren.add(child);
+    private void prepareChildren(final boolean forceRefresh) {
+        if (!forceRefresh && mChildDag.size() == getChildCount()
+                && mChildDag.size() == mDependencySortedChildren.size()) {
+            // If we're not being forced and everything looks good, lets skip the call
+            return;
         }
-        // We need to use a selection sort here to make sure that every item is compared
-        // against each other
-        selectionSort(mDependencySortedChildren, mLayoutDependencyComparator);
+
+        mDependencySortedChildren.clear();
+        mChildDag.clear();
+
+        for (int i = 0, count = getChildCount(); i < count; i++) {
+            final View view = getChildAt(i);
+
+            final LayoutParams lp = getResolvedLayoutParams(view);
+            lp.findAnchorView(this, view);
+
+            mChildDag.addNode(view);
+
+            // Now iterate again over the other children, adding any dependencies to the graph
+            for (int j = 0; j < count; j++) {
+                if (j == i) {
+                    continue;
+                }
+                final View other = getChildAt(j);
+                final LayoutParams otherLp = getResolvedLayoutParams(other);
+                if (otherLp.dependsOn(this, other, view)) {
+                    if (!mChildDag.contains(other)) {
+                        // Make sure that the other node is added
+                        mChildDag.addNode(other);
+                    }
+                    // Now add the dependency to the graph
+                    mChildDag.addEdge(view, other);
+                }
+            }
+        }
+
+        // Finally add the sorted graph list to our list
+        mDependencySortedChildren.addAll(mChildDag.getSortedList());
+        // We also need to reverse the result since we want the start of the list to contain
+        // Views which have no dependencies, then dependent views after that
+        Collections.reverse(mDependencySortedChildren);
     }
 
     /**
@@ -692,7 +707,7 @@
 
     @Override
     protected void onMeasure(int widthMeasureSpec, int heightMeasureSpec) {
-        prepareChildren();
+        prepareChildren(true);
         ensurePreDrawListener();
 
         final int paddingLeft = getPaddingLeft();
@@ -1363,20 +1378,16 @@
      * @param view the View to find dependents of to dispatch the call.
      */
     public void dispatchDependentViewsChanged(View view) {
-        final int childCount = mDependencySortedChildren.size();
-        boolean viewSeen = false;
-        for (int i = 0; i < childCount; i++) {
-            final View child = mDependencySortedChildren.get(i);
-            if (child == view) {
-                // We've seen our view, which means that any Views after this could be dependent
-                viewSeen = true;
-                continue;
-            }
-            if (viewSeen) {
+        prepareChildren(false);
+
+        final List<View> dependents = mChildDag.getIncomingEdges(view);
+        if (dependents != null && !dependents.isEmpty()) {
+            for (int i = 0; i < dependents.size(); i++) {
+                final View child = (View) dependents.get(i);
                 CoordinatorLayout.LayoutParams lp = (CoordinatorLayout.LayoutParams)
                         child.getLayoutParams();
                 CoordinatorLayout.Behavior b = lp.getBehavior();
-                if (b != null && lp.dependsOn(this, child, view)) {
+                if (b != null) {
                     b.onDependentViewChanged(this, child, view);
                 }
             }
@@ -1384,32 +1395,47 @@
     }
 
     /**
-     * Returns the list of views which the provided view depends on. Do not store this list as it's
+     * Returns the list of views which the provided view depends on. Do not store this list as its
      * contents may not be valid beyond the caller.
      *
      * @param child the view to find dependencies for.
      *
      * @return the list of views which {@code child} depends on.
      */
-    public List<View> getDependencies(View child) {
-        // TODO The result of this is probably a good candidate for caching
+    public List<View> getDependencies(@NonNull View child) {
+        prepareChildren(false);
 
-        final LayoutParams lp = (LayoutParams) child.getLayoutParams();
-        final List<View> list = mTempDependenciesList;
-        list.clear();
-
-        final int childCount = getChildCount();
-        for (int i = 0; i < childCount; i++) {
-            final View other = getChildAt(i);
-            if (other == child) {
-                continue;
-            }
-            if (lp.dependsOn(this, child, other)) {
-                list.add(other);
-            }
+        final List<View> dependencies = mChildDag.getOutgoingEdges(child);
+        mTempDependenciesList.clear();
+        if (dependencies != null) {
+            mTempDependenciesList.addAll(dependencies);
         }
+        return mTempDependenciesList;
+    }
 
-        return list;
+    /**
+     * Returns the list of views which depend on the provided view. Do not store this list as its
+     * contents may not be valid beyond the caller.
+     *
+     * @param child the view to find dependents of.
+     *
+     * @return the list of views which depend on {@code child}.
+     */
+    public List<View> getDependents(@NonNull View child) {
+        prepareChildren(false);
+
+        final List<View> edges = mChildDag.getIncomingEdges(child);
+        mTempDependenciesList.clear();
+        if (edges != null) {
+            mTempDependenciesList.addAll(edges);
+        }
+        return mTempDependenciesList;
+    }
+
+    @VisibleForTesting
+    final List<View> getDependencySortedChildren() {
+        prepareChildren(true);
+        return Collections.unmodifiableList(mDependencySortedChildren);
     }
 
     /**
@@ -1439,22 +1465,8 @@
      * Check if the given child has any layout dependencies on other child views.
      */
     boolean hasDependencies(View child) {
-        final LayoutParams lp = (LayoutParams) child.getLayoutParams();
-        if (lp.mAnchorView != null) {
-            return true;
-        }
-
-        final int childCount = getChildCount();
-        for (int i = 0; i < childCount; i++) {
-            final View other = getChildAt(i);
-            if (other == child) {
-                continue;
-            }
-            if (lp.dependsOn(this, child, other)) {
-                return true;
-            }
-        }
-        return false;
+        prepareChildren(false);
+        return mChildDag.hasOutgoingEdges(child);
     }
 
     /**
@@ -2827,7 +2839,7 @@
 
         @Override
         public void onChildViewRemoved(View parent, View child) {
-            prepareChildren();
+            prepareChildren(true);
             onChildViewsChanged(EVENT_VIEW_REMOVED);
 
             if (mOnHierarchyChangeListener != null) {
@@ -2981,37 +2993,4 @@
             }
         });
     }
-
-    private static void selectionSort(final List<View> list, final Comparator<View> comparator) {
-        if (list == null || list.size() < 2) {
-            return;
-        }
-
-        final View[] array = new View[list.size()];
-        list.toArray(array);
-        final int count = array.length;
-
-        for (int i = 0; i < count; i++) {
-            int min = i;
-
-            for (int j = i + 1; j < count; j++) {
-                if (comparator.compare(array[j], array[min]) < 0) {
-                    min = j;
-                }
-            }
-
-            if (i != min) {
-                // We have a different min so swap the items
-                final View minItem = array[min];
-                array[min] = array[i];
-                array[i] = minItem;
-            }
-        }
-
-        // Finally add the array back into the collection
-        list.clear();
-        for (int i = 0; i < count; i++) {
-            list.add(array[i]);
-        }
-    }
 }
diff --git a/design/src/android/support/design/widget/DirectedAcyclicGraph.java b/design/src/android/support/design/widget/DirectedAcyclicGraph.java
new file mode 100644
index 0000000..189daf4
--- /dev/null
+++ b/design/src/android/support/design/widget/DirectedAcyclicGraph.java
@@ -0,0 +1,201 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package android.support.design.widget;
+
+import android.support.annotation.NonNull;
+import android.support.annotation.Nullable;
+import android.support.v4.util.Pools;
+import android.support.v4.util.SimpleArrayMap;
+
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.List;
+
+/**
+ * A class which represents a simple directed acyclic graph.
+ */
+final class DirectedAcyclicGraph<T> {
+    private final Pools.Pool<ArrayList<T>> mListPool = new Pools.SimplePool<>(10);
+    private final SimpleArrayMap<T, ArrayList<T>> mGraph = new SimpleArrayMap<>();
+
+    private final ArrayList<T> mSortResult = new ArrayList<>();
+    private final HashSet<T> mSortTmpMarked = new HashSet<>();
+
+    /**
+     * Add a node to the graph.
+     *
+     * <p>If the node already exists in the graph then this method is a no-op.</p>
+     *
+     * @param node the node to add
+     */
+    void addNode(@NonNull T node) {
+        if (!mGraph.containsKey(node)) {
+            mGraph.put(node, null);
+        }
+    }
+
+    /**
+     * Returns true if the node is already present in the graph, false otherwise.
+     */
+    boolean contains(@NonNull T node) {
+        return mGraph.containsKey(node);
+    }
+
+    /**
+     * Add an edge to the graph.
+     *
+     * <p>Both the given nodes should already have been added to the graph through
+     * {@link #addNode(Object)}.</p>
+     *
+     * @param node the parent node
+     * @param incomingEdge the node which has is an incoming edge to {@code node}
+     */
+    void addEdge(@NonNull T node, @NonNull T incomingEdge) {
+        if (!mGraph.containsKey(node) || !mGraph.containsKey(incomingEdge)) {
+            throw new IllegalArgumentException("All nodes must be present in the graph before"
+                    + " being added as an edge");
+        }
+
+        ArrayList<T> edges = mGraph.get(node);
+        if (edges == null) {
+            // If edges is null, we should try and get one from the pool and add it to the graph
+            edges = getEmptyList();
+            mGraph.put(node, edges);
+        }
+        // Finally add the edge to the list
+        edges.add(incomingEdge);
+    }
+
+    /**
+     * Get any incoming edges from the given node.
+     *
+     * @return a list containing any incoming edges, or null if there are none.
+     */
+    @Nullable
+    List getIncomingEdges(@NonNull T node) {
+        return mGraph.get(node);
+    }
+
+    /**
+     * Get any outgoing edges for the given node (i.e. nodes which have an incoming edge
+     * from the given node).
+     *
+     * @return a list containing any outgoing edges, or null if there are none.
+     */
+    @Nullable
+    List getOutgoingEdges(@NonNull T node) {
+        ArrayList<T> result = null;
+        for (int i = 0, size = mGraph.size(); i < size; i++) {
+            ArrayList<T> edges = mGraph.valueAt(i);
+            if (edges != null && edges.contains(node)) {
+                if (result == null) {
+                    result = new ArrayList<>();
+                }
+                result.add(mGraph.keyAt(i));
+            }
+        }
+        return result;
+    }
+
+    boolean hasOutgoingEdges(@NonNull T node) {
+        for (int i = 0, size = mGraph.size(); i < size; i++) {
+            ArrayList<T> edges = mGraph.valueAt(i);
+            if (edges != null && edges.contains(node)) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    /**
+     * Clears the internal graph, and releases resources to pools.
+     */
+    void clear() {
+        for (int i = 0, size = mGraph.size(); i < size; i++) {
+            ArrayList<T> edges = mGraph.valueAt(i);
+            if (edges != null) {
+                poolList(edges);
+            }
+        }
+        mGraph.clear();
+    }
+
+    /**
+     * Returns a topologically sorted list of the nodes in this graph. This uses the DFS algorithm
+     * as described by Cormen et al. (2001). If this graph contains cyclic dependencies then this
+     * method will throw a {@link RuntimeException}.
+     *
+     * <p>The resulting list will be ordered such that index 0 will contain the node at the bottom
+     * of the graph. The node at the end of the list will have no dependencies on other nodes.</p>
+     */
+    @NonNull
+    ArrayList<T> getSortedList() {
+        mSortResult.clear();
+        mSortTmpMarked.clear();
+
+        // Start a DFS from each node in the graph
+        for (int i = 0, size = mGraph.size(); i < size; i++) {
+            dfs(mGraph.keyAt(i), mSortResult, mSortTmpMarked);
+        }
+
+        return mSortResult;
+    }
+
+    private void dfs(final T node, final ArrayList<T> result, final HashSet<T> tmpMarked) {
+        if (result.contains(node)) {
+            // We've already seen and added the node to the result list, skip...
+            return;
+        }
+        if (tmpMarked.contains(node)) {
+            throw new RuntimeException("This graph contains cyclic dependencies");
+        }
+        // Temporarily mark the node
+        tmpMarked.add(node);
+        // Recursively dfs all of the node's edges
+        final ArrayList<T> edges = mGraph.get(node);
+        if (edges != null) {
+            for (int i = 0, size = edges.size(); i < size; i++) {
+                dfs(edges.get(i), result, tmpMarked);
+            }
+        }
+        // Unmark the node from the temporary list
+        tmpMarked.remove(node);
+        // Finally add it to the result list
+        result.add(node);
+    }
+
+    /**
+     * Returns the size of the graph
+     */
+    int size() {
+        return mGraph.size();
+    }
+
+    @NonNull
+    private ArrayList<T> getEmptyList() {
+        ArrayList<T> list = mListPool.acquire();
+        if (list == null) {
+            list = new ArrayList<>();
+        }
+        return list;
+    }
+
+    private void poolList(@NonNull ArrayList<T> list) {
+        list.clear();
+        mListPool.release(list);
+    }
+}
\ No newline at end of file
diff --git a/design/tests/src/android/support/design/widget/CoordinatorLayoutSortTest.java b/design/tests/src/android/support/design/widget/CoordinatorLayoutSortTest.java
new file mode 100644
index 0000000..9258374
--- /dev/null
+++ b/design/tests/src/android/support/design/widget/CoordinatorLayoutSortTest.java
@@ -0,0 +1,144 @@
+/*
+ * Copyright (C) 2016 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package android.support.design.widget;
+
+import static org.junit.Assert.assertEquals;
+
+import android.app.Instrumentation;
+import android.support.test.InstrumentationRegistry;
+import android.test.suitebuilder.annotation.MediumTest;
+import android.view.View;
+
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.List;
+
+@RunWith(Parameterized.class)
+@MediumTest
+public class CoordinatorLayoutSortTest
+        extends BaseInstrumentationTestCase<CoordinatorLayoutActivity> {
+
+    private static final int NUMBER_VIEWS_DEPENDENCY_SORT = 4;
+
+    /**
+     * All 27 permutations of a quad-tuple containing unique values in the range 0-3
+     */
+    @Parameterized.Parameters
+    public static Collection<Object[]> data() {
+        return Arrays.asList(new Object[][] {
+                {0, 1, 2, 3}, {0, 1, 3, 2}, {0, 2, 1, 3}, {0, 2, 3, 1}, {0, 3, 1, 2}, {0, 3, 2, 1},
+                {1, 0, 2, 3}, {1, 0, 3, 2}, {1, 2, 0, 3}, {1, 2, 3, 0}, {1, 3, 0, 2}, {1, 3, 2, 0},
+                {2, 0, 1, 3}, {2, 0, 3, 1}, {2, 1, 0, 3}, {2, 1, 3, 0}, {2, 3, 0, 1}, {2, 3, 1, 0},
+                {3, 0, 1, 2}, {3, 0, 2, 1}, {3, 1, 0, 2}, {3, 1, 2, 0}, {3, 2, 0, 1}, {3, 2, 1, 0}
+        });
+    }
+
+    private int mFirstAddIndex;
+    private int mSecondAddIndex;
+    private int mThirdAddIndex;
+    private int mFourthAddIndex;
+
+    public CoordinatorLayoutSortTest(int firstIndex, int secondIndex, int thirdIndex,
+            int fourthIndex) {
+        super(CoordinatorLayoutActivity.class);
+        mFirstAddIndex = firstIndex;
+        mSecondAddIndex = secondIndex;
+        mThirdAddIndex = thirdIndex;
+        mFourthAddIndex = fourthIndex;
+    }
+
+    @Test
+    public void testDependencySortingOrder() {
+        final CoordinatorLayout col = mActivityTestRule.getActivity().mCoordinatorLayout;
+
+        // Let's create some views where each view depends on the previous view.
+        // i.e C depends on B, B depends on A, A doesn't depend on anything.
+        final List<View> views = new ArrayList<>();
+        for (int i = 0; i < NUMBER_VIEWS_DEPENDENCY_SORT; i++) {
+            // 65 == A in ASCII
+            final String label = Character.toString((char) (65 + i));
+            final View view = new View(col.getContext()) {
+                @Override
+                public String toString() {
+                    return label;
+                }
+            };
+
+            // Create a Behavior which depends on the previously added view
+            View dependency = i > 0 ? views.get(i - 1) : null;
+            CoordinatorLayout.Behavior<View> behavior = createBehaviorWhichDependsOn(dependency);
+
+            // And set its LayoutParams to use the Behavior
+            CoordinatorLayout.LayoutParams lp = col.generateDefaultLayoutParams();
+            lp.setBehavior(behavior);
+            view.setLayoutParams(lp);
+
+            views.add(view);
+        }
+
+        // Now the add the views in the given order and assert that they still end up in
+        // the expected order A, B, C, D
+        final List<View> testOrder = new ArrayList<>();
+        testOrder.add(views.get(mFirstAddIndex));
+        testOrder.add(views.get(mSecondAddIndex));
+        testOrder.add(views.get(mThirdAddIndex));
+        testOrder.add(views.get(mFourthAddIndex));
+        addViewsAndAssertOrdering(col, views, testOrder);
+    }
+
+    private static void addViewsAndAssertOrdering(final CoordinatorLayout col,
+            final List<View> expectedOrder, final List<View> addOrder) {
+        final Instrumentation instrumentation = InstrumentationRegistry.getInstrumentation();
+
+        // Add the Views in the given order
+        instrumentation.runOnMainSync(new Runnable() {
+            @Override
+            public void run() {
+                for (int i = 0; i < addOrder.size(); i++) {
+                    col.addView(addOrder.get(i));
+                }
+            }
+        });
+        instrumentation.waitForIdleSync();
+
+        // Now assert that the dependency sorted order is correct
+        assertEquals(expectedOrder, col.getDependencySortedChildren());
+
+        // Finally remove all of the views
+        instrumentation.runOnMainSync(new Runnable() {
+            @Override
+            public void run() {
+                col.removeAllViews();
+            }
+        });
+    }
+
+    private static CoordinatorLayout.Behavior<View> createBehaviorWhichDependsOn(final View view) {
+        return new CoordinatorLayout.Behavior<View>() {
+            @Override
+            public boolean layoutDependsOn(CoordinatorLayout parent, View child, View dependency) {
+                return view != null && dependency == view;
+            }
+        };
+    }
+
+}
diff --git a/v7/mediarouter/res/layout/mr_controller_volume_item.xml b/v7/mediarouter/res/layout/mr_controller_volume_item.xml
index 3e7b39b..985646d 100644
--- a/v7/mediarouter/res/layout/mr_controller_volume_item.xml
+++ b/v7/mediarouter/res/layout/mr_controller_volume_item.xml
@@ -45,7 +45,8 @@
                 android:layout_width="fill_parent"
                 android:layout_height="40dp"
                 android:minHeight="40dp"
-                android:maxHeight="40dp" />
+                android:maxHeight="40dp"
+                android:contentDescription="@string/mr_controller_volume_slider" />
         </LinearLayout>
     </LinearLayout>
 </LinearLayout>
diff --git a/v7/mediarouter/res/layout/mr_volume_control.xml b/v7/mediarouter/res/layout/mr_volume_control.xml
index 4fd51fb..ee923ec 100644
--- a/v7/mediarouter/res/layout/mr_volume_control.xml
+++ b/v7/mediarouter/res/layout/mr_volume_control.xml
@@ -38,7 +38,8 @@
             android:minHeight="48dp"
             android:maxHeight="48dp"
             android:layout_weight="1"
-            android:clickable="true" />
+            android:clickable="true"
+            android:contentDescription="@string/mr_controller_volume_slider" />
     <android.support.v7.app.MediaRouteExpandCollapseButton
             android:id="@+id/mr_group_expand_collapse"
             android:layout_width="48dp"
diff --git a/v7/mediarouter/res/values/strings.xml b/v7/mediarouter/res/values/strings.xml
index b6a949a..bff7176 100644
--- a/v7/mediarouter/res/values/strings.xml
+++ b/v7/mediarouter/res/values/strings.xml
@@ -21,10 +21,22 @@
     <!-- Name for the user route category created when publishing routes to the system in Jellybean and above. [CHAR LIMIT=30] -->
     <string name="mr_user_route_category_name">Devices</string>
 
-    <!-- Content description of a MediaRouteButton for accessibility support.
+    <!-- String to be shown as a tooltip of MediaRouteButton
         Cast is the standard android verb for sending content to a remote device. [CHAR LIMIT=50] -->
     <string name="mr_button_content_description">Cast button</string>
 
+    <!-- Content description of a MediaRouteButton for accessibility support when no remote device is connected.
+        Cast is the standard android verb for sending content to a remote device. [CHAR LIMIT=NONE] -->
+    <string name="mr_cast_button_disconnected">Cast button. Disconnected</string>
+
+    <!-- Content description of a MediaRouteButton for accessibility support while connecting to a remote device.
+        Cast is the standard android verb for sending content to a remote device. [CHAR LIMIT=NONE] -->
+    <string name="mr_cast_button_connecting">Cast button. Connecting</string>
+
+    <!-- Content description of a MediaRouteButton for accessibility support when a remote device is connected.
+        Cast is the standard android verb for sending content to a remote device. [CHAR LIMIT=NONE] -->
+    <string name="mr_cast_button_connected">Cast button. Connected</string>
+
     <!-- Title of the media route chooser dialog. [CHAR LIMIT=30] -->
     <string name="mr_chooser_title">Cast to</string>
 
@@ -55,6 +67,9 @@
     <!-- Content description for accessibility (not shown on the screen): album art button. Clicking on the album art takes user to a predefined activity per media app. [CHAR LIMIT=50] -->
     <string name="mr_controller_album_art">Album art</string>
 
+    <!-- Content description for accessibility (not shown on the screen): volume slider. [CHAR LIMIT=NONE] -->
+    <string name="mr_controller_volume_slider">Volume slider</string>
+
     <!-- Placeholder text to show when no media have been selected for playback. [CHAR LIMIT=50] -->
     <string name="mr_controller_no_media_selected">No media selected</string>
 
diff --git a/v7/mediarouter/res/values/styles.xml b/v7/mediarouter/res/values/styles.xml
index 0edee9b..ea53cf3 100644
--- a/v7/mediarouter/res/values/styles.xml
+++ b/v7/mediarouter/res/values/styles.xml
@@ -17,13 +17,11 @@
 <resources>
     <style name="Widget.MediaRouter.MediaRouteButton"
             parent="Widget.AppCompat.ActionButton">
-        <item name="android:contentDescription">@string/mr_button_content_description</item>
         <item name="externalRouteEnabledDrawable">@drawable/mr_button_dark</item>
     </style>
 
     <style name="Widget.MediaRouter.Light.MediaRouteButton"
             parent="Widget.AppCompat.Light.ActionButton">
-        <item name="android:contentDescription">@string/mr_button_content_description</item>
         <item name="externalRouteEnabledDrawable">@drawable/mr_button_light</item>
     </style>
 
diff --git a/v7/mediarouter/src/android/support/v7/app/MediaRouteButton.java b/v7/mediarouter/src/android/support/v7/app/MediaRouteButton.java
index da5c194..c45121e 100644
--- a/v7/mediarouter/src/android/support/v7/app/MediaRouteButton.java
+++ b/v7/mediarouter/src/android/support/v7/app/MediaRouteButton.java
@@ -137,6 +137,7 @@
                 R.styleable.MediaRouteButton_android_minHeight, 0);
         a.recycle();
 
+        updateContentDescription();
         setClickable(true);
         setLongClickable(true);
     }
@@ -300,12 +301,6 @@
             return false;
         }
 
-        final CharSequence contentDesc = getContentDescription();
-        if (TextUtils.isEmpty(contentDesc)) {
-            // Don't show the cheat sheet if we have no description
-            return false;
-        }
-
         final int[] screenPos = new int[2];
         final Rect displayFrame = new Rect();
         getLocationOnScreen(screenPos);
@@ -317,7 +312,8 @@
         final int midy = screenPos[1] + height / 2;
         final int screenWidth = context.getResources().getDisplayMetrics().widthPixels;
 
-        Toast cheatSheet = Toast.makeText(context, contentDesc, Toast.LENGTH_SHORT);
+        Toast cheatSheet = Toast.makeText(context, R.string.mr_button_content_description,
+                Toast.LENGTH_SHORT);
         if (midy < displayFrame.height()) {
             // Show along the top; follow action buttons
             cheatSheet.setGravity(Gravity.TOP | GravityCompat.END,
@@ -507,6 +503,7 @@
             }
 
             if (needsRefresh) {
+                updateContentDescription();
                 refreshDrawableState();
                 if (mRemoteIndicator.getCurrent() instanceof AnimationDrawable) {
                     AnimationDrawable curDrawable =
@@ -519,6 +516,18 @@
         }
     }
 
+    private void updateContentDescription() {
+        int resId;
+        if (mIsConnecting) {
+            resId = R.string.mr_cast_button_connecting;
+        } else if (mRemoteActive) {
+            resId = R.string.mr_cast_button_connected;
+        } else {
+            resId = R.string.mr_cast_button_disconnected;
+        }
+        setContentDescription(getContext().getString(resId));
+    }
+
     private final class MediaRouterCallback extends MediaRouter.Callback {
         @Override
         public void onRouteAdded(MediaRouter router, MediaRouter.RouteInfo info) {