1/*
2 * Copyright (C) 2014 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package android.support.v7.widget;
18
19import junit.framework.TestCase;
20
21import java.util.ArrayList;
22import java.util.HashSet;
23import java.util.List;
24import java.util.Random;
25import java.util.Set;
26
27import android.support.v7.widget.AdapterHelper.UpdateOp;
28import android.util.Log;
29
30import static android.support.v7.widget.AdapterHelper.UpdateOp.ADD;
31import static android.support.v7.widget.AdapterHelper.UpdateOp.MOVE;
32import static android.support.v7.widget.AdapterHelper.UpdateOp.REMOVE;
33import static android.support.v7.widget.AdapterHelper.UpdateOp.UPDATE;
34
35public class OpReorderTest extends TestCase {
36
37    private static final String TAG = "OpReorderTest";
38
39    List<UpdateOp> mUpdateOps = new ArrayList<UpdateOp>();
40    List<Item> mAddedItems = new ArrayList<Item>();
41    List<Item> mRemovedItems = new ArrayList<Item>();
42    Set<UpdateOp> mRecycledOps = new HashSet<UpdateOp>();
43    static Random random = new Random(System.nanoTime());
44
45    OpReorderer mOpReorderer = new OpReorderer(new OpReorderer.Callback() {
46        @Override
47        public UpdateOp obtainUpdateOp(int cmd, int startPosition, int itemCount) {
48            return new UpdateOp(cmd, startPosition, itemCount);
49        }
50
51        @Override
52        public void recycleUpdateOp(UpdateOp op) {
53            mRecycledOps.add(op);
54        }
55    });
56
57    int itemCount = 10;
58    int updatedItemCount = 0;
59
60    public void setup(int count) {
61        itemCount = count;
62        updatedItemCount = itemCount;
63    }
64
65    @Override
66    protected void setUp() throws Exception {
67        super.setUp();
68        cleanState();
69    }
70
71    void cleanState() {
72        mUpdateOps = new ArrayList<UpdateOp>();
73        mAddedItems = new ArrayList<Item>();
74        mRemovedItems = new ArrayList<Item>();
75        mRecycledOps = new HashSet<UpdateOp>();
76        Item.idCounter = 0;
77    }
78
79    public void testMoveRemoved() throws Exception {
80        setup(10);
81        mv(3, 8);
82        rm(7, 3);
83        process();
84    }
85
86    public void testMoveRemove() throws Exception {
87        setup(10);
88        mv(3, 8);
89        rm(3, 5);
90        process();
91    }
92
93    public void test1() {
94        setup(10);
95        mv(3, 5);
96        rm(3, 4);
97        process();
98    }
99
100    public void test2() {
101        setup(5);
102        mv(1, 3);
103        rm(1, 1);
104        process();
105    }
106
107    public void test3() {
108        setup(5);
109        mv(0, 4);
110        rm(2, 1);
111        process();
112    }
113
114    public void test4() {
115        setup(5);
116        mv(3, 0);
117        rm(3, 1);
118        process();
119    }
120
121    public void test5() {
122        setup(10);
123        mv(8, 1);
124        rm(6, 3);
125        process();
126    }
127
128    public void test6() {
129        setup(5);
130        mv(1, 3);
131        rm(0, 3);
132        process();
133    }
134
135    public void test7() {
136        setup(5);
137        mv(3, 4);
138        rm(3, 1);
139        process();
140    }
141
142    public void test8() {
143        setup(5);
144        mv(4, 3);
145        rm(3, 1);
146        process();
147    }
148
149    public void test9() {
150        setup(5);
151        mv(2, 0);
152        rm(2, 2);
153        process();
154    }
155
156    public void testRandom() throws Exception {
157        for (int i = 0; i < 150; i++) {
158            try {
159                cleanState();
160                setup(50);
161                for (int j = 0; j < 50; j++) {
162                    randOp(nextInt(random, nextInt(random, 4)));
163                }
164                Log.d(TAG, "running random test " + i);
165                process();
166            } catch (Throwable t) {
167                throw new Exception(t.getMessage() + "\n" + opsToString(mUpdateOps));
168            }
169        }
170    }
171
172    public void testRandomMoveRemove() throws Exception {
173        for (int i = 0; i < 1000; i++) {
174            try {
175                cleanState();
176                setup(5);
177                orderedRandom(MOVE, REMOVE);
178                process();
179            } catch (Throwable t) {
180                throw new Exception(t.getMessage() + "\n" + opsToString(mUpdateOps));
181            }
182        }
183    }
184
185    public void testRandomMoveAdd() throws Exception {
186        for (int i = 0; i < 1000; i++) {
187            try {
188                cleanState();
189                setup(5);
190                orderedRandom(MOVE, ADD);
191                process();
192            } catch (Throwable t) {
193                throw new Exception(t.getMessage() + "\n" + opsToString(mUpdateOps));
194            }
195        }
196    }
197
198    public void testRandomMoveUpdate() throws Exception {
199        for (int i = 0; i < 1000; i++) {
200            try {
201                cleanState();
202                setup(5);
203                orderedRandom(MOVE, UPDATE);
204                process();
205            } catch (Throwable t) {
206                throw new Exception(t.getMessage() + "\n" + opsToString(mUpdateOps));
207            }
208        }
209    }
210
211    private String opsToString(List<UpdateOp> updateOps) {
212        StringBuilder sb = new StringBuilder();
213        for (UpdateOp op : updateOps) {
214            sb.append("\n").append(op.toString());
215        }
216        return sb.append("\n").toString();
217    }
218
219    public void orderedRandom(int... ops) {
220        for (int op : ops) {
221            randOp(op);
222        }
223    }
224
225    void randOp(int cmd) {
226        switch (cmd) {
227            case REMOVE:
228                if (updatedItemCount > 1) {
229                    int s = nextInt(random, updatedItemCount - 1);
230                    int len = Math.max(1, nextInt(random, updatedItemCount - s));
231                    rm(s, len);
232                }
233                break;
234            case ADD:
235                int s = updatedItemCount == 0 ? 0 : nextInt(random, updatedItemCount);
236                add(s, nextInt(random, 50));
237                break;
238            case MOVE:
239                if (updatedItemCount >= 2) {
240                    int from = nextInt(random, updatedItemCount);
241                    int to;
242                    do {
243                        to = nextInt(random, updatedItemCount);
244                    } while (to == from);
245                    mv(from, to);
246                }
247                break;
248            case UPDATE:
249                if (updatedItemCount > 1) {
250                    s = nextInt(random, updatedItemCount - 1);
251                    int len = Math.max(1, nextInt(random, updatedItemCount - s));
252                    up(s, len);
253                }
254                break;
255        }
256    }
257
258    int nextInt(Random random, int n) {
259        if (n == 0) {
260            return 0;
261        }
262        return random.nextInt(n);
263    }
264
265    UpdateOp rm(int start, int count) {
266        updatedItemCount -= count;
267        return record(new UpdateOp(REMOVE, start, count));
268    }
269
270    UpdateOp mv(int from, int to) {
271        return record(new UpdateOp(MOVE, from, to));
272    }
273
274    UpdateOp add(int start, int count) {
275        updatedItemCount += count;
276        return record(new UpdateOp(ADD, start, count));
277    }
278
279    UpdateOp up(int start, int count) {
280        return record(new UpdateOp(UPDATE, start, count));
281    }
282
283    UpdateOp record(UpdateOp op) {
284        mUpdateOps.add(op);
285        return op;
286    }
287
288    void process() {
289        List<Item> items = new ArrayList<Item>(itemCount);
290        for (int i = 0; i < itemCount; i++) {
291            items.add(Item.create());
292        }
293        List<Item> clones = new ArrayList<Item>(itemCount);
294        for (int i = 0; i < itemCount; i++) {
295            clones.add(Item.clone(items.get(i)));
296        }
297        List<UpdateOp> rewritten = rewriteOps(mUpdateOps);
298
299        assertAllMovesAtTheEnd(rewritten);
300
301        apply(items, mUpdateOps);
302        List<Item> originalAdded = mAddedItems;
303        List<Item> originalRemoved = mRemovedItems;
304        if (originalAdded.size() > 0) {
305            Item.idCounter = originalAdded.get(0).id;
306        }
307        mAddedItems = new ArrayList<Item>();
308        mRemovedItems = new ArrayList<Item>();
309        apply(clones, rewritten);
310
311        // now check equality
312        assertListsIdentical(items, clones);
313        assertHasTheSameItems(originalAdded, mAddedItems);
314        assertHasTheSameItems(originalRemoved, mRemovedItems);
315
316        assertRecycledOpsAreNotReused(items);
317        assertRecycledOpsAreNotReused(clones);
318    }
319
320    private void assertRecycledOpsAreNotReused(List<Item> items) {
321        for (Item item : items) {
322            assertFalse(mRecycledOps.contains(item));
323        }
324    }
325
326    private void assertAllMovesAtTheEnd(List<UpdateOp> ops) {
327        boolean foundMove = false;
328        for (UpdateOp op : ops) {
329            if (op.cmd == MOVE) {
330                foundMove = true;
331            } else {
332                assertFalse(foundMove);
333            }
334        }
335    }
336
337    private void assertHasTheSameItems(List<Item> items,
338            List<Item> clones) {
339        String log = "has the same items\n" + toString(items) + "--\n" + toString(clones);
340        assertEquals(log, items.size(), clones.size());
341        for (Item item : items) {
342            for (Item clone : clones) {
343                if (item.id == clone.id && item.version == clone.version) {
344                    clones.remove(clone);
345                    break;
346                }
347            }
348        }
349        assertEquals(log, 0, clones.size());
350    }
351
352    private void assertListsIdentical(List<Item> items, List<Item> clones) {
353        String log = "is identical\n" + toString(items) + "--\n" + toString(clones);
354        assertEquals(items.size(), clones.size());
355        for (int i = 0; i < items.size(); i++) {
356            Item.assertIdentical(log, items.get(i), clones.get(i));
357        }
358    }
359
360    private void apply(List<Item> items, List<UpdateOp> updateOps) {
361        for (UpdateOp op : updateOps) {
362            switch (op.cmd) {
363                case UpdateOp.ADD:
364                    for (int i = 0; i < op.itemCount; i++) {
365                        final Item newItem = Item.create();
366                        mAddedItems.add(newItem);
367                        items.add(op.positionStart + i, newItem);
368                    }
369                    break;
370                case UpdateOp.REMOVE:
371                    for (int i = 0; i < op.itemCount; i++) {
372                        mRemovedItems.add(items.remove(op.positionStart));
373                    }
374                    break;
375                case UpdateOp.MOVE:
376                    items.add(op.itemCount, items.remove(op.positionStart));
377                    break;
378                case UpdateOp.UPDATE:
379                    for (int i = 0; i < op.itemCount; i++) {
380                        final int index = op.positionStart + i;
381                        items.get(index).version = items.get(index).version + 1;
382                    }
383                    break;
384            }
385        }
386    }
387
388    private List<UpdateOp> rewriteOps(List<UpdateOp> updateOps) {
389        List<UpdateOp> copy = new ArrayList<UpdateOp>();
390        for (UpdateOp op : updateOps) {
391            copy.add(new UpdateOp(op.cmd, op.positionStart, op.itemCount));
392        }
393        mOpReorderer.reorderOps(copy);
394        return copy;
395    }
396
397    public void testSwapMoveRemove_1() {
398        mv(10, 15);
399        rm(2, 3);
400        swapMoveRemove(mUpdateOps, 0);
401        assertEquals(2, mUpdateOps.size());
402        assertEquals(mv(7, 12), mUpdateOps.get(1));
403        assertEquals(rm(2, 3), mUpdateOps.get(0));
404    }
405
406    public void testSwapMoveRemove_2() {
407        mv(3, 8);
408        rm(4, 2);
409        swapMoveRemove(mUpdateOps, 0);
410        assertEquals(2, mUpdateOps.size());
411        assertEquals(rm(5, 2), mUpdateOps.get(0));
412        assertEquals(mv(3, 6), mUpdateOps.get(1));
413    }
414
415    public void testSwapMoveRemove_3() {
416        mv(3, 8);
417        rm(3, 2);
418        swapMoveRemove(mUpdateOps, 0);
419        assertEquals(2, mUpdateOps.size());
420        assertEquals(rm(4, 2), mUpdateOps.get(0));
421        assertEquals(mv(3, 6), mUpdateOps.get(1));
422    }
423
424    public void testSwapMoveRemove_4() {
425        mv(3, 8);
426        rm(2, 3);
427        swapMoveRemove(mUpdateOps, 0);
428        assertEquals(3, mUpdateOps.size());
429        assertEquals(rm(4, 2), mUpdateOps.get(0));
430        assertEquals(rm(2, 1), mUpdateOps.get(1));
431        assertEquals(mv(2, 5), mUpdateOps.get(2));
432    }
433
434    public void testSwapMoveRemove_5() {
435        mv(3, 0);
436        rm(2, 3);
437        swapMoveRemove(mUpdateOps, 0);
438        assertEquals(3, mUpdateOps.size());
439        assertEquals(rm(4, 1), mUpdateOps.get(0));
440        assertEquals(rm(1, 2), mUpdateOps.get(1));
441        assertEquals(mv(1, 0), mUpdateOps.get(2));
442    }
443
444    public void testSwapMoveRemove_6() {
445        mv(3, 10);
446        rm(2, 3);
447        swapMoveRemove(mUpdateOps, 0);
448        assertEquals(3, mUpdateOps.size());
449        assertEquals(rm(4, 2), mUpdateOps.get(0));
450        assertEquals(rm(2, 1), mUpdateOps.get(1));
451    }
452
453    public void testSwapMoveRemove_7() {
454        mv(3, 2);
455        rm(6, 2);
456        swapMoveRemove(mUpdateOps, 0);
457        assertEquals(2, mUpdateOps.size());
458        assertEquals(rm(6, 2), mUpdateOps.get(0));
459        assertEquals(mv(3, 2), mUpdateOps.get(1));
460    }
461
462    public void testSwapMoveRemove_8() {
463        mv(3, 4);
464        rm(3, 1);
465        swapMoveRemove(mUpdateOps, 0);
466        assertEquals(1, mUpdateOps.size());
467        assertEquals(rm(4, 1), mUpdateOps.get(0));
468    }
469
470    public void testSwapMoveRemove_9() {
471        mv(3, 4);
472        rm(4, 1);
473        swapMoveRemove(mUpdateOps, 0);
474        assertEquals(1, mUpdateOps.size());
475        assertEquals(rm(3, 1), mUpdateOps.get(0));
476    }
477
478    public void testSwapMoveRemove_10() {
479        mv(1, 3);
480        rm(0, 3);
481        swapMoveRemove(mUpdateOps, 0);
482        assertEquals(2, mUpdateOps.size());
483        assertEquals(rm(2, 2), mUpdateOps.get(0));
484        assertEquals(rm(0, 1), mUpdateOps.get(1));
485    }
486
487    public void testSwapMoveRemove_11() {
488        mv(3, 8);
489        rm(7, 3);
490        swapMoveRemove(mUpdateOps, 0);
491        assertEquals(2, mUpdateOps.size());
492        assertEquals(rm(3, 1), mUpdateOps.get(0));
493        assertEquals(rm(7, 2), mUpdateOps.get(1));
494    }
495
496    public void testSwapMoveRemove_12() {
497        mv(1, 3);
498        rm(2, 1);
499        swapMoveRemove(mUpdateOps, 0);
500        assertEquals(2, mUpdateOps.size());
501        assertEquals(rm(3, 1), mUpdateOps.get(0));
502        assertEquals(mv(1, 2), mUpdateOps.get(1));
503    }
504
505    public void testSwapMoveRemove_13() {
506        mv(1, 3);
507        rm(1, 2);
508        swapMoveRemove(mUpdateOps, 0);
509        assertEquals(1, mUpdateOps.size());
510        assertEquals(rm(2, 2), mUpdateOps.get(1));
511    }
512
513    public void testSwapMoveRemove_14() {
514        mv(4, 2);
515        rm(3, 1);
516        swapMoveRemove(mUpdateOps, 0);
517        assertEquals(2, mUpdateOps.size());
518        assertEquals(rm(2, 1), mUpdateOps.get(0));
519        assertEquals(mv(2, 3), mUpdateOps.get(1));
520    }
521
522    public void testSwapMoveRemove_15() {
523        mv(4, 2);
524        rm(3, 2);
525        swapMoveRemove(mUpdateOps, 0);
526        assertEquals(1, mUpdateOps.size());
527        assertEquals(rm(2, 2), mUpdateOps.get(0));
528    }
529
530    public void testSwapMoveRemove_16() {
531        mv(2, 3);
532        rm(1, 2);
533        swapMoveRemove(mUpdateOps, 0);
534        assertEquals(2, mUpdateOps.size());
535        assertEquals(rm(3, 1), mUpdateOps.get(0));
536        assertEquals(rm(1, 1), mUpdateOps.get(1));
537    }
538
539    public void testSwapMoveUpdate_0() {
540        mv(1, 3);
541        up(1, 2);
542        swapMoveUpdate(mUpdateOps, 0);
543        assertEquals(2, mUpdateOps.size());
544        assertEquals(up(2, 2), mUpdateOps.get(0));
545        assertEquals(mv(1, 3), mUpdateOps.get(1));
546    }
547
548    public void testSwapMoveUpdate_1() {
549        mv(0, 2);
550        up(0, 4);
551        swapMoveUpdate(mUpdateOps, 0);
552        assertEquals(3, mUpdateOps.size());
553        assertEquals(up(0, 1), mUpdateOps.get(0));
554        assertEquals(up(1, 3), mUpdateOps.get(1));
555        assertEquals(mv(0, 2), mUpdateOps.get(2));
556    }
557
558    public void testSwapMoveUpdate_2() {
559        mv(2, 0);
560        up(1, 3);
561        swapMoveUpdate(mUpdateOps, 0);
562        assertEquals(3, mUpdateOps.size());
563        assertEquals(up(3, 1), mUpdateOps.get(0));
564        assertEquals(up(0, 2), mUpdateOps.get(1));
565        assertEquals(mv(2, 0), mUpdateOps.get(2));
566    }
567
568    private void swapMoveUpdate(List<UpdateOp> list, int move) {
569        mOpReorderer.swapMoveUpdate(list, move, list.get(move), move + 1, list.get(move + 1));
570    }
571
572    private void swapMoveRemove(List<UpdateOp> list, int move) {
573        mOpReorderer.swapMoveRemove(list, move, list.get(move), move + 1, list.get(move + 1));
574    }
575
576    private String toString(List<Item> items) {
577        StringBuilder sb = new StringBuilder();
578        for (Item item : items) {
579            sb.append(item.toString()).append("\n");
580        }
581        return sb.toString();
582    }
583
584    static class Item {
585
586        static int idCounter = 0;
587        int id;
588        int version;
589
590        Item(int id, int version) {
591            this.id = id;
592            this.version = version;
593        }
594
595        static Item create() {
596            return new Item(idCounter++, 1);
597        }
598
599        static Item clone(Item other) {
600            return new Item(other.id, other.version);
601        }
602
603        public static void assertIdentical(String logPrefix, Item item1, Item item2) {
604            assertEquals(logPrefix + "\n" + item1 + " vs " + item2, item1.id, item2.id);
605            assertEquals(logPrefix + "\n" + item1 + " vs " + item2, item1.version, item2.version);
606        }
607
608        @Override
609        public String toString() {
610            return "Item{" +
611                    "id=" + id +
612                    ", version=" + version +
613                    '}';
614        }
615    }
616}
617