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