am 3bcfbdd9: am 8120652b: Order GhostViews so that they display in their ghosted view\'s order.

* commit '3bcfbdd9024785af3bbf8a0f6c513b36ea1b7ae9':
  Order GhostViews so that they display in their ghosted view's order.

2 files changed, 191 insertions, 8 deletions

diff --git a/core/java/android/view/GhostView.java b/core/java/android/view/GhostView.java
index e4500eb81cd5..50c927a131a7 100644
--- a/core/java/android/view/GhostView.java
+++ b/core/java/android/view/GhostView.java
@@ -19,6 +19,8 @@ import android.graphics.Canvas;
 import android.graphics.Matrix;
 import android.widget.FrameLayout;
 
+import java.util.ArrayList;
+
 /**
  * This view draws another View in an Overlay without changing the parent. It will not be drawn
  * by its parent because its visibility is set to INVISIBLE, but will be drawn
@@ -30,6 +32,7 @@ import android.widget.FrameLayout;
 public class GhostView extends View {
     private final View mView;
     private int mReferences;
+    private boolean mBeingMoved;
 
     private GhostView(View view) {
         super(view.getContext());
@@ -75,12 +78,14 @@ public class GhostView extends View {
     @Override
     protected void onDetachedFromWindow() {
         super.onDetachedFromWindow();
-        setGhostedVisibility(View.VISIBLE);
-        mView.mGhostView = null;
-        final ViewGroup parent = (ViewGroup) mView.getParent();
-        if (parent != null) {
-            parent.mRecreateDisplayList = true;
-            parent.getDisplayList();
+        if (!mBeingMoved) {
+            setGhostedVisibility(View.VISIBLE);
+            mView.mGhostView = null;
+            final ViewGroup parent = (ViewGroup) mView.getParent();
+            if (parent != null) {
+                parent.mRecreateDisplayList = true;
+                parent.getDisplayList();
+            }
         }
     }
 
@@ -121,7 +126,9 @@ public class GhostView extends View {
             copySize(viewGroup, parent);
             copySize(viewGroup, ghostView);
             parent.addView(ghostView);
-            overlay.add(parent);
+            ArrayList<View> tempViews = new ArrayList<View>();
+            int firstGhost = moveGhostViewsToTop(overlay.mOverlayViewGroup, tempViews);
+            insertIntoOverlay(overlay.mOverlayViewGroup, parent, ghostView, tempViews, firstGhost);
             ghostView.mReferences = previousRefCount;
         } else if (matrix != null) {
             ghostView.setMatrix(matrix);
@@ -156,4 +163,180 @@ public class GhostView extends View {
         to.setRight(from.getWidth());
         to.setBottom(from.getHeight());
     }
+
+    /**
+     * Move the GhostViews to the end so that they are on top of other views and it is easier
+     * to do binary search for the correct location for the GhostViews in insertIntoOverlay.
+     *
+     * @return The index of the first GhostView or -1 if no GhostView is in the ViewGroup
+     */
+    private static int moveGhostViewsToTop(ViewGroup viewGroup, ArrayList<View> tempViews) {
+        final int numChildren = viewGroup.getChildCount();
+        if (numChildren == 0) {
+            return -1;
+        } else if (isGhostWrapper(viewGroup.getChildAt(numChildren - 1))) {
+            // GhostViews are already at the end
+            int firstGhost = numChildren - 1;
+            for (int i = numChildren - 2; i >= 0; i--) {
+                if (!isGhostWrapper(viewGroup.getChildAt(i))) {
+                    break;
+                }
+                firstGhost = i;
+            }
+            return firstGhost;
+        }
+
+        // Remove all GhostViews from the middle
+        for (int i = numChildren - 2; i >= 0; i--) {
+            View child = viewGroup.getChildAt(i);
+            if (isGhostWrapper(child)) {
+                tempViews.add(child);
+                GhostView ghostView = (GhostView)((ViewGroup)child).getChildAt(0);
+                ghostView.mBeingMoved = true;
+                viewGroup.removeViewAt(i);
+                ghostView.mBeingMoved = false;
+            }
+        }
+
+        final int firstGhost;
+        if (tempViews.isEmpty()) {
+            firstGhost = -1;
+        } else {
+            firstGhost = viewGroup.getChildCount();
+            // Add the GhostViews to the end
+            for (int i = tempViews.size() - 1; i >= 0; i--) {
+                viewGroup.addView(tempViews.get(i));
+            }
+            tempViews.clear();
+        }
+        return firstGhost;
+    }
+
+    /**
+     * Inserts a GhostView into the overlay's ViewGroup in the order in which they
+     * should be displayed by the UI.
+     */
+    private static void insertIntoOverlay(ViewGroup viewGroup, ViewGroup wrapper,
+            GhostView ghostView, ArrayList<View> tempParents, int firstGhost) {
+        if (firstGhost == -1) {
+            viewGroup.addView(wrapper);
+        } else {
+            ArrayList<View> viewParents = new ArrayList<View>();
+            getParents(ghostView.mView, viewParents);
+
+            int index = getInsertIndex(viewGroup, viewParents, tempParents, firstGhost);
+            if (index < 0 || index >= viewGroup.getChildCount()) {
+                viewGroup.addView(wrapper);
+            } else {
+                viewGroup.addView(wrapper, index);
+            }
+        }
+    }
+
+    /**
+     * Find the index into the overlay to insert the GhostView based on the order that the
+     * views should be drawn. This keeps GhostViews layered in the same order
+     * that they are ordered in the UI.
+     */
+    private static int getInsertIndex(ViewGroup overlayViewGroup, ArrayList<View> viewParents,
+            ArrayList<View> tempParents, int firstGhost) {
+        int low = firstGhost;
+        int high = overlayViewGroup.getChildCount() - 1;
+
+        while (low <= high) {
+            int mid = (low + high) / 2;
+            ViewGroup wrapper = (ViewGroup) overlayViewGroup.getChildAt(mid);
+            GhostView midView = (GhostView) wrapper.getChildAt(0);
+            getParents(midView.mView, tempParents);
+            if (isOnTop(viewParents, tempParents)) {
+                low = mid + 1;
+            } else {
+                high = mid - 1;
+            }
+            tempParents.clear();
+        }
+
+        return low;
+    }
+
+    /**
+     * Returns true if view is a GhostView's FrameLayout wrapper.
+     */
+    private static boolean isGhostWrapper(View view) {
+        if (view instanceof FrameLayout) {
+            FrameLayout frameLayout = (FrameLayout) view;
+            if (frameLayout.getChildCount() == 1) {
+                View child = frameLayout.getChildAt(0);
+                return child instanceof GhostView;
+            }
+        }
+        return false;
+    }
+
+    /**
+     * Returns true if viewParents is from a View that is on top of the comparedWith's view.
+     * The ArrayLists contain the ancestors of views in order from top most grandparent, to
+     * the view itself, in order. The goal is to find the first matching parent and then
+     * compare the draw order of the siblings.
+     */
+    private static boolean isOnTop(ArrayList<View> viewParents, ArrayList<View> comparedWith) {
+        if (viewParents.isEmpty() || comparedWith.isEmpty() ||
+                viewParents.get(0) != comparedWith.get(0)) {
+            // Not the same decorView -- arbitrary ordering
+            return true;
+        }
+        int depth = Math.min(viewParents.size(), comparedWith.size());
+        for (int i = 1; i < depth; i++) {
+            View viewParent = viewParents.get(i);
+            View comparedWithParent = comparedWith.get(i);
+
+            if (viewParent != comparedWithParent) {
+                // i - 1 is the same parent, but these are different children.
+                return isOnTop(viewParent, comparedWithParent);
+            }
+        }
+
+        // one of these is the parent of the other
+        boolean isComparedWithTheParent = (comparedWith.size() == depth);
+        return isComparedWithTheParent;
+    }
+
+    /**
+     * Adds all the parents, grandparents, etc. of view to parents.
+     */
+    private static void getParents(View view, ArrayList<View> parents) {
+        ViewParent parent = view.getParent();
+        if (parent != null && parent instanceof ViewGroup) {
+            getParents((View) parent, parents);
+        }
+        parents.add(view);
+    }
+
+    /**
+     * Returns true if view would be drawn on top of comparedWith or false otherwise.
+     * view and comparedWith are siblings with the same parent. This uses the logic
+     * that dispatchDraw uses to determine which View should be drawn first.
+     */
+    private static boolean isOnTop(View view, View comparedWith) {
+        ViewGroup parent = (ViewGroup) view.getParent();
+
+        final int childrenCount = parent.getChildCount();
+        final ArrayList<View> preorderedList = parent.buildOrderedChildList();
+        final boolean customOrder = preorderedList == null
+                && parent.isChildrenDrawingOrderEnabled();
+        for (int i = 0; i < childrenCount; i++) {
+            int childIndex = customOrder ? parent.getChildDrawingOrder(childrenCount, i) : i;
+            final View child = (preorderedList == null)
+                    ? parent.getChildAt(childIndex) : preorderedList.get(childIndex);
+            if (child == view) {
+                return false;
+            } else if (child == comparedWith) {
+                return true;
+            }
+        }
+
+        // Shouldn't get here. Neither of the children is in the parent.
+        // Just return an arbitrary one.
+        return true;
+    }
 }
diff --git a/core/java/android/view/ViewGroup.java b/core/java/android/view/ViewGroup.java
index 6d3b419b1253..b586caab0780 100644
--- a/core/java/android/view/ViewGroup.java
+++ b/core/java/android/view/ViewGroup.java
@@ -3298,7 +3298,7 @@ public abstract class ViewGroup extends View implements ViewParent, ViewManager
      * Uses a stable, insertion sort which is commonly O(n) for ViewGroups with very few elevated
      * children.
      */
-    private ArrayList<View> buildOrderedChildList() {
+    ArrayList<View> buildOrderedChildList() {
         final int count = mChildrenCount;
         if (count <= 1 || !hasChildWithZ()) return null;