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