1/*
2 * Copyright (C) 2017 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.android.internal.widget;
18
19import static com.android.internal.widget.AdapterHelper.UpdateOp.ADD;
20import static com.android.internal.widget.AdapterHelper.UpdateOp.MOVE;
21import static com.android.internal.widget.AdapterHelper.UpdateOp.REMOVE;
22import static com.android.internal.widget.AdapterHelper.UpdateOp.UPDATE;
23
24import com.android.internal.widget.AdapterHelper.UpdateOp;
25
26import java.util.List;
27
28class OpReorderer {
29
30    final Callback mCallback;
31
32    OpReorderer(Callback callback) {
33        mCallback = callback;
34    }
35
36    void reorderOps(List<UpdateOp> ops) {
37        // since move operations breaks continuity, their effects on ADD/RM are hard to handle.
38        // we push them to the end of the list so that they can be handled easily.
39        int badMove;
40        while ((badMove = getLastMoveOutOfOrder(ops)) != -1) {
41            swapMoveOp(ops, badMove, badMove + 1);
42        }
43    }
44
45    private void swapMoveOp(List<UpdateOp> list, int badMove, int next) {
46        final UpdateOp moveOp = list.get(badMove);
47        final UpdateOp nextOp = list.get(next);
48        switch (nextOp.cmd) {
49            case REMOVE:
50                swapMoveRemove(list, badMove, moveOp, next, nextOp);
51                break;
52            case ADD:
53                swapMoveAdd(list, badMove, moveOp, next, nextOp);
54                break;
55            case UPDATE:
56                swapMoveUpdate(list, badMove, moveOp, next, nextOp);
57                break;
58        }
59    }
60
61    void swapMoveRemove(List<UpdateOp> list, int movePos, UpdateOp moveOp,
62            int removePos, UpdateOp removeOp) {
63        UpdateOp extraRm = null;
64        // check if move is nulled out by remove
65        boolean revertedMove = false;
66        final boolean moveIsBackwards;
67
68        if (moveOp.positionStart < moveOp.itemCount) {
69            moveIsBackwards = false;
70            if (removeOp.positionStart == moveOp.positionStart
71                    && removeOp.itemCount == moveOp.itemCount - moveOp.positionStart) {
72                revertedMove = true;
73            }
74        } else {
75            moveIsBackwards = true;
76            if (removeOp.positionStart == moveOp.itemCount + 1
77                    && removeOp.itemCount == moveOp.positionStart - moveOp.itemCount) {
78                revertedMove = true;
79            }
80        }
81
82        // going in reverse, first revert the effect of add
83        if (moveOp.itemCount < removeOp.positionStart) {
84            removeOp.positionStart--;
85        } else if (moveOp.itemCount < removeOp.positionStart + removeOp.itemCount) {
86            // move is removed.
87            removeOp.itemCount--;
88            moveOp.cmd = REMOVE;
89            moveOp.itemCount = 1;
90            if (removeOp.itemCount == 0) {
91                list.remove(removePos);
92                mCallback.recycleUpdateOp(removeOp);
93            }
94            // no need to swap, it is already a remove
95            return;
96        }
97
98        // now affect of add is consumed. now apply effect of first remove
99        if (moveOp.positionStart <= removeOp.positionStart) {
100            removeOp.positionStart++;
101        } else if (moveOp.positionStart < removeOp.positionStart + removeOp.itemCount) {
102            final int remaining = removeOp.positionStart + removeOp.itemCount
103                    - moveOp.positionStart;
104            extraRm = mCallback.obtainUpdateOp(REMOVE, moveOp.positionStart + 1, remaining, null);
105            removeOp.itemCount = moveOp.positionStart - removeOp.positionStart;
106        }
107
108        // if effects of move is reverted by remove, we are done.
109        if (revertedMove) {
110            list.set(movePos, removeOp);
111            list.remove(removePos);
112            mCallback.recycleUpdateOp(moveOp);
113            return;
114        }
115
116        // now find out the new locations for move actions
117        if (moveIsBackwards) {
118            if (extraRm != null) {
119                if (moveOp.positionStart > extraRm.positionStart) {
120                    moveOp.positionStart -= extraRm.itemCount;
121                }
122                if (moveOp.itemCount > extraRm.positionStart) {
123                    moveOp.itemCount -= extraRm.itemCount;
124                }
125            }
126            if (moveOp.positionStart > removeOp.positionStart) {
127                moveOp.positionStart -= removeOp.itemCount;
128            }
129            if (moveOp.itemCount > removeOp.positionStart) {
130                moveOp.itemCount -= removeOp.itemCount;
131            }
132        } else {
133            if (extraRm != null) {
134                if (moveOp.positionStart >= extraRm.positionStart) {
135                    moveOp.positionStart -= extraRm.itemCount;
136                }
137                if (moveOp.itemCount >= extraRm.positionStart) {
138                    moveOp.itemCount -= extraRm.itemCount;
139                }
140            }
141            if (moveOp.positionStart >= removeOp.positionStart) {
142                moveOp.positionStart -= removeOp.itemCount;
143            }
144            if (moveOp.itemCount >= removeOp.positionStart) {
145                moveOp.itemCount -= removeOp.itemCount;
146            }
147        }
148
149        list.set(movePos, removeOp);
150        if (moveOp.positionStart != moveOp.itemCount) {
151            list.set(removePos, moveOp);
152        } else {
153            list.remove(removePos);
154        }
155        if (extraRm != null) {
156            list.add(movePos, extraRm);
157        }
158    }
159
160    private void swapMoveAdd(List<UpdateOp> list, int move, UpdateOp moveOp, int add,
161            UpdateOp addOp) {
162        int offset = 0;
163        // going in reverse, first revert the effect of add
164        if (moveOp.itemCount < addOp.positionStart) {
165            offset--;
166        }
167        if (moveOp.positionStart < addOp.positionStart) {
168            offset++;
169        }
170        if (addOp.positionStart <= moveOp.positionStart) {
171            moveOp.positionStart += addOp.itemCount;
172        }
173        if (addOp.positionStart <= moveOp.itemCount) {
174            moveOp.itemCount += addOp.itemCount;
175        }
176        addOp.positionStart += offset;
177        list.set(move, addOp);
178        list.set(add, moveOp);
179    }
180
181    void swapMoveUpdate(List<UpdateOp> list, int move, UpdateOp moveOp, int update,
182            UpdateOp updateOp) {
183        UpdateOp extraUp1 = null;
184        UpdateOp extraUp2 = null;
185        // going in reverse, first revert the effect of add
186        if (moveOp.itemCount < updateOp.positionStart) {
187            updateOp.positionStart--;
188        } else if (moveOp.itemCount < updateOp.positionStart + updateOp.itemCount) {
189            // moved item is updated. add an update for it
190            updateOp.itemCount--;
191            extraUp1 = mCallback.obtainUpdateOp(UPDATE, moveOp.positionStart, 1, updateOp.payload);
192        }
193        // now affect of add is consumed. now apply effect of first remove
194        if (moveOp.positionStart <= updateOp.positionStart) {
195            updateOp.positionStart++;
196        } else if (moveOp.positionStart < updateOp.positionStart + updateOp.itemCount) {
197            final int remaining = updateOp.positionStart + updateOp.itemCount
198                    - moveOp.positionStart;
199            extraUp2 = mCallback.obtainUpdateOp(UPDATE, moveOp.positionStart + 1, remaining,
200                    updateOp.payload);
201            updateOp.itemCount -= remaining;
202        }
203        list.set(update, moveOp);
204        if (updateOp.itemCount > 0) {
205            list.set(move, updateOp);
206        } else {
207            list.remove(move);
208            mCallback.recycleUpdateOp(updateOp);
209        }
210        if (extraUp1 != null) {
211            list.add(move, extraUp1);
212        }
213        if (extraUp2 != null) {
214            list.add(move, extraUp2);
215        }
216    }
217
218    private int getLastMoveOutOfOrder(List<UpdateOp> list) {
219        boolean foundNonMove = false;
220        for (int i = list.size() - 1; i >= 0; i--) {
221            final UpdateOp op1 = list.get(i);
222            if (op1.cmd == MOVE) {
223                if (foundNonMove) {
224                    return i;
225                }
226            } else {
227                foundNonMove = true;
228            }
229        }
230        return -1;
231    }
232
233    interface Callback {
234
235        UpdateOp obtainUpdateOp(int cmd, int startPosition, int itemCount, Object payload);
236
237        void recycleUpdateOp(UpdateOp op);
238    }
239}
240