llvm/unittests/ADT/SimpleIListTest.cpp

   1 //===- unittests/ADT/SimpleIListTest.cpp - simple_ilist unit tests --------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/ADT/simple_ilist.h"
  10 #include "llvm/ADT/STLExtras.h"
  11 #include "gtest/gtest.h"
  12
  13 using namespace llvm;
  14
  15 namespace {
  16
  17 struct Node : ilist_node<Node> {};
  18 bool operator<(const Node &L, const Node &R) { return &L < &R; }
  19 bool makeFalse(const Node &, const Node &) { return false; }
  20
  21 struct deleteNode : std::default_delete<Node> {};
  22 void doNothing(Node *) {}
  23
  24 TEST(SimpleIListTest, DefaultConstructor) {
  25   simple_ilist<Node> L;
  26   EXPECT_EQ(L.begin(), L.end());
  27   EXPECT_TRUE(L.empty());
  28   EXPECT_EQ(0u, L.size());
  29 }
  30
  31 TEST(SimpleIListTest, pushPopFront) {
  32   simple_ilist<Node> L;
  33   Node A, B;
  34   L.push_front(B);
  35   L.push_front(A);
  36   EXPECT_EQ(&A, &L.front());
  37   EXPECT_EQ(&B, &L.back());
  38   EXPECT_FALSE(L.empty());
  39   EXPECT_EQ(2u, L.size());
  40
  41   // Pop front and check the new front.
  42   L.pop_front();
  43   EXPECT_EQ(&B, &L.front());
  44
  45   // Pop to empty.
  46   L.pop_front();
  47   EXPECT_TRUE(L.empty());
  48 }
  49
  50 TEST(SimpleIListTest, pushPopBack) {
  51   simple_ilist<Node> L;
  52   Node A, B;
  53   L.push_back(A);
  54   L.push_back(B);
  55   EXPECT_EQ(&A, &L.front());
  56   EXPECT_EQ(&B, &L.back());
  57   EXPECT_FALSE(L.empty());
  58   EXPECT_EQ(2u, L.size());
  59
  60   // Pop back and check the new front.
  61   L.pop_back();
  62   EXPECT_EQ(&A, &L.back());
  63
  64   // Pop to empty.
  65   L.pop_back();
  66   EXPECT_TRUE(L.empty());
  67 }
  68
  69 TEST(SimpleIListTest, swap) {
  70   simple_ilist<Node> L1, L2;
  71   Node A, B;
  72   L1.push_back(A);
  73   L1.push_back(B);
  74   L1.swap(L2);
  75   EXPECT_TRUE(L1.empty());
  76   EXPECT_EQ(0u, L1.size());
  77   EXPECT_EQ(&A, &L2.front());
  78   EXPECT_EQ(&B, &L2.back());
  79   EXPECT_FALSE(L2.empty());
  80   EXPECT_EQ(2u, L2.size());
  81 }
  82
  83 TEST(SimpleIListTest, insertEraseAtEnd) {
  84   simple_ilist<Node> L;
  85   Node A, B;
  86   L.insert(L.end(), A);
  87   L.insert(L.end(), B);
  88   EXPECT_EQ(&A, &L.front());
  89   EXPECT_EQ(&B, &L.back());
  90   EXPECT_FALSE(L.empty());
  91   EXPECT_EQ(2u, L.size());
  92 }
  93
  94 TEST(SimpleIListTest, insertAtBegin) {
  95   simple_ilist<Node> L;
  96   Node A, B;
  97   L.insert(L.begin(), B);
  98   L.insert(L.begin(), A);
  99   EXPECT_EQ(&A, &L.front());
 100   EXPECT_EQ(&B, &L.back());
 101   EXPECT_FALSE(L.empty());
 102   EXPECT_EQ(2u, L.size());
 103 }
 104
 105 TEST(SimpleIListTest, remove) {
 106   simple_ilist<Node> L;
 107   Node A, B, C;
 108   L.push_back(A);
 109   L.push_back(B);
 110   L.push_back(C);
 111   EXPECT_EQ(&A, &L.front());
 112   EXPECT_EQ(&B, &*++L.begin());
 113   EXPECT_EQ(&C, &L.back());
 114   EXPECT_EQ(3u, L.size());
 115
 116   L.remove(B);
 117   EXPECT_EQ(&A, &L.front());
 118   EXPECT_EQ(&C, &L.back());
 119   EXPECT_EQ(2u, L.size());
 120
 121   L.remove(A);
 122   EXPECT_EQ(&C, &L.front());
 123   EXPECT_EQ(1u, L.size());
 124
 125   L.remove(C);
 126   EXPECT_TRUE(L.empty());
 127 }
 128
 129 TEST(SimpleIListTest, removeAndDispose) {
 130   simple_ilist<Node> L;
 131   Node A, C;
 132   Node *B = new Node;
 133   L.push_back(A);
 134   L.push_back(*B);
 135   L.push_back(C);
 136   EXPECT_EQ(&A, &L.front());
 137   EXPECT_EQ(B, &*++L.begin());
 138   EXPECT_EQ(&C, &L.back());
 139   EXPECT_EQ(3u, L.size());
 140
 141   L.removeAndDispose(*B, deleteNode());
 142   EXPECT_EQ(&A, &L.front());
 143   EXPECT_EQ(&C, &L.back());
 144   EXPECT_EQ(2u, L.size());
 145 }
 146
 147 TEST(SimpleIListTest, removeAndDisposeNullDeleter) {
 148   simple_ilist<Node> L;
 149   Node A, B, C;
 150   L.push_back(A);
 151   L.push_back(B);
 152   L.push_back(C);
 153   EXPECT_EQ(&A, &L.front());
 154   EXPECT_EQ(&B, &*++L.begin());
 155   EXPECT_EQ(&C, &L.back());
 156   EXPECT_EQ(3u, L.size());
 157
 158   L.removeAndDispose(B, doNothing);
 159   EXPECT_EQ(&A, &L.front());
 160   EXPECT_EQ(&C, &L.back());
 161   EXPECT_EQ(2u, L.size());
 162 }
 163
 164 TEST(SimpleIListTest, erase) {
 165   simple_ilist<Node> L;
 166   Node A, B, C;
 167   L.push_back(A);
 168   L.push_back(B);
 169   L.push_back(C);
 170   EXPECT_EQ(&A, &L.front());
 171   EXPECT_EQ(&B, &*++L.begin());
 172   EXPECT_EQ(&C, &L.back());
 173   EXPECT_EQ(3u, L.size());
 174
 175   EXPECT_EQ(C.getIterator(), L.erase(B.getIterator()));
 176   EXPECT_EQ(&A, &L.front());
 177   EXPECT_EQ(&C, &L.back());
 178   EXPECT_EQ(2u, L.size());
 179 }
 180
 181 TEST(SimpleIListTest, reverse_iterator) {
 182   simple_ilist<Node> L;
 183   Node A, B, C;
 184   L.push_back(A);
 185   L.push_back(B);
 186   L.push_back(C);
 187
 188   auto ReverseIter = L.rbegin();
 189   EXPECT_EQ(C.getReverseIterator(), ReverseIter);
 190   ++ReverseIter;
 191   EXPECT_EQ(B.getReverseIterator(), ReverseIter);
 192   ++ReverseIter;
 193   EXPECT_EQ(A.getReverseIterator(), ReverseIter);
 194   ++ReverseIter;
 195   EXPECT_EQ(L.rend(), ReverseIter);
 196 }
 197
 198 TEST(SimpleIListTest, eraseAndDispose) {
 199   simple_ilist<Node> L;
 200   Node A, C;
 201   Node *B = new Node;
 202   L.push_back(A);
 203   L.push_back(*B);
 204   L.push_back(C);
 205   EXPECT_EQ(&A, &L.front());
 206   EXPECT_EQ(B, &*++L.begin());
 207   EXPECT_EQ(&C, &L.back());
 208   EXPECT_EQ(3u, L.size());
 209
 210   L.eraseAndDispose(B->getIterator(), deleteNode());
 211   EXPECT_EQ(&A, &L.front());
 212   EXPECT_EQ(&C, &L.back());
 213   EXPECT_EQ(2u, L.size());
 214 }
 215
 216 TEST(SimpleIListTest, eraseAndDisposeNullDeleter) {
 217   simple_ilist<Node> L;
 218   Node A, B, C;
 219   L.push_back(A);
 220   L.push_back(B);
 221   L.push_back(C);
 222   EXPECT_EQ(&A, &L.front());
 223   EXPECT_EQ(&B, &*++L.begin());
 224   EXPECT_EQ(&C, &L.back());
 225   EXPECT_EQ(3u, L.size());
 226
 227   L.eraseAndDispose(B.getIterator(), doNothing);
 228   EXPECT_EQ(&A, &L.front());
 229   EXPECT_EQ(&C, &L.back());
 230   EXPECT_EQ(2u, L.size());
 231 }
 232
 233 TEST(SimpleIListTest, eraseRange) {
 234   simple_ilist<Node> L;
 235   Node A, B, C, D, E;
 236   L.push_back(A);
 237   L.push_back(B);
 238   L.push_back(C);
 239   L.push_back(D);
 240   L.push_back(E);
 241   auto I = L.begin();
 242   EXPECT_EQ(&A, &*I++);
 243   EXPECT_EQ(&B, &*I++);
 244   EXPECT_EQ(&C, &*I++);
 245   EXPECT_EQ(&D, &*I++);
 246   EXPECT_EQ(&E, &*I++);
 247   EXPECT_EQ(L.end(), I);
 248   EXPECT_EQ(5u, L.size());
 249
 250   // Erase a range.
 251   EXPECT_EQ(E.getIterator(), L.erase(B.getIterator(), E.getIterator()));
 252   EXPECT_EQ(&A, &L.front());
 253   EXPECT_EQ(&E, &L.back());
 254   EXPECT_EQ(2u, L.size());
 255 }
 256
 257 TEST(SimpleIListTest, eraseAndDisposeRange) {
 258   simple_ilist<Node> L;
 259   Node A, *B = new Node, *C = new Node, *D = new Node, E;
 260   L.push_back(A);
 261   L.push_back(*B);
 262   L.push_back(*C);
 263   L.push_back(*D);
 264   L.push_back(E);
 265   auto I = L.begin();
 266   EXPECT_EQ(&A, &*I++);
 267   EXPECT_EQ(B, &*I++);
 268   EXPECT_EQ(C, &*I++);
 269   EXPECT_EQ(D, &*I++);
 270   EXPECT_EQ(&E, &*I++);
 271   EXPECT_EQ(L.end(), I);
 272   EXPECT_EQ(5u, L.size());
 273
 274   // Erase a range.
 275   EXPECT_EQ(E.getIterator(),
 276             L.eraseAndDispose(B->getIterator(), E.getIterator(), deleteNode()));
 277   EXPECT_EQ(&A, &L.front());
 278   EXPECT_EQ(&E, &L.back());
 279   EXPECT_EQ(2u, L.size());
 280 }
 281
 282 TEST(SimpleIListTest, eraseAndDisposeRangeNullDeleter) {
 283   simple_ilist<Node> L;
 284   Node A, B, C, D, E;
 285   L.push_back(A);
 286   L.push_back(B);
 287   L.push_back(C);
 288   L.push_back(D);
 289   L.push_back(E);
 290   auto I = L.begin();
 291   EXPECT_EQ(&A, &*I++);
 292   EXPECT_EQ(&B, &*I++);
 293   EXPECT_EQ(&C, &*I++);
 294   EXPECT_EQ(&D, &*I++);
 295   EXPECT_EQ(&E, &*I++);
 296   EXPECT_EQ(L.end(), I);
 297   EXPECT_EQ(5u, L.size());
 298
 299   // Erase a range.
 300   EXPECT_EQ(E.getIterator(),
 301             L.eraseAndDispose(B.getIterator(), E.getIterator(), doNothing));
 302   EXPECT_EQ(&A, &L.front());
 303   EXPECT_EQ(&E, &L.back());
 304   EXPECT_EQ(2u, L.size());
 305 }
 306
 307 TEST(SimpleIListTest, clear) {
 308   simple_ilist<Node> L;
 309   Node A, B;
 310   L.push_back(A);
 311   L.push_back(B);
 312   L.clear();
 313   EXPECT_TRUE(L.empty());
 314   EXPECT_EQ(0u, L.size());
 315 }
 316
 317 TEST(SimpleIListTest, clearAndDispose) {
 318   simple_ilist<Node> L;
 319   Node *A = new Node;
 320   Node *B = new Node;
 321   L.push_back(*A);
 322   L.push_back(*B);
 323   L.clearAndDispose(deleteNode());
 324   EXPECT_TRUE(L.empty());
 325   EXPECT_EQ(0u, L.size());
 326 }
 327
 328 TEST(SimpleIListTest, clearAndDisposeNullDeleter) {
 329   simple_ilist<Node> L;
 330   Node A, B;
 331   L.push_back(A);
 332   L.push_back(B);
 333   L.clearAndDispose(doNothing);
 334   EXPECT_TRUE(L.empty());
 335   EXPECT_EQ(0u, L.size());
 336 }
 337
 338 TEST(SimpleIListTest, spliceList) {
 339   simple_ilist<Node> L1, L2;
 340   Node A, B, C, D;
 341
 342   // [A, D].
 343   L1.push_back(A);
 344   L1.push_back(D);
 345
 346   // [B, C].
 347   L2.push_back(B);
 348   L2.push_back(C);
 349
 350   // Splice in L2, giving [A, B, C, D].
 351   L1.splice(--L1.end(), L2);
 352   EXPECT_TRUE(L2.empty());
 353   EXPECT_EQ(4u, L1.size());
 354   auto I = L1.begin();
 355   EXPECT_EQ(&A, &*I++);
 356   EXPECT_EQ(&B, &*I++);
 357   EXPECT_EQ(&C, &*I++);
 358   EXPECT_EQ(&D, &*I++);
 359   EXPECT_EQ(L1.end(), I);
 360 }
 361
 362 TEST(SimpleIListTest, spliceSingle) {
 363   simple_ilist<Node> L1, L2;
 364   Node A, B, C, D, E;
 365
 366   // [A, C].
 367   L1.push_back(A);
 368   L1.push_back(C);
 369
 370   // [D, B, E].
 371   L2.push_back(D);
 372   L2.push_back(B);
 373   L2.push_back(E);
 374
 375   // Splice B from L2 to L1, giving [A, B, C] and [D, E].
 376   L1.splice(--L1.end(), L2, ++L2.begin());
 377   auto I = L1.begin();
 378   EXPECT_EQ(&A, &*I++);
 379   EXPECT_EQ(&B, &*I++);
 380   EXPECT_EQ(&C, &*I++);
 381   EXPECT_EQ(L1.end(), I);
 382
 383   I = L2.begin();
 384   EXPECT_EQ(&D, &*I++);
 385   EXPECT_EQ(&E, &*I++);
 386   EXPECT_EQ(L2.end(), I);
 387 }
 388
 389 TEST(SimpleIListTest, spliceRange) {
 390   simple_ilist<Node> L1, L2;
 391   Node A, B, C, D, E, F;
 392
 393   // [A, D].
 394   L1.push_back(A);
 395   L1.push_back(D);
 396
 397   // [E, B, C, F].
 398   L2.push_back(E);
 399   L2.push_back(B);
 400   L2.push_back(C);
 401   L2.push_back(F);
 402
 403   // Splice B from L2 to L1, giving [A, B, C, D] and [E, F].
 404   L1.splice(--L1.end(), L2, ++L2.begin(), --L2.end());
 405   auto I = L1.begin();
 406   EXPECT_EQ(&A, &*I++);
 407   EXPECT_EQ(&B, &*I++);
 408   EXPECT_EQ(&C, &*I++);
 409   EXPECT_EQ(&D, &*I++);
 410   EXPECT_EQ(L1.end(), I);
 411
 412   I = L2.begin();
 413   EXPECT_EQ(&E, &*I++);
 414   EXPECT_EQ(&F, &*I++);
 415   EXPECT_EQ(L2.end(), I);
 416 }
 417
 418 TEST(SimpleIListTest, merge) {
 419   for (bool IsL1LHS : {false, true}) {
 420     simple_ilist<Node> L1, L2;
 421     Node Ns[10];
 422
 423     // Fill L1.
 424     L1.push_back(Ns[0]);
 425     L1.push_back(Ns[3]);
 426     L1.push_back(Ns[4]);
 427     L1.push_back(Ns[8]);
 428
 429     // Fill L2.
 430     L2.push_back(Ns[1]);
 431     L2.push_back(Ns[2]);
 432     L2.push_back(Ns[5]);
 433     L2.push_back(Ns[6]);
 434     L2.push_back(Ns[7]);
 435     L2.push_back(Ns[9]);
 436
 437     // Check setup.
 438     EXPECT_EQ(4u, L1.size());
 439     EXPECT_EQ(6u, L2.size());
 440     EXPECT_TRUE(llvm::is_sorted(L1));
 441     EXPECT_TRUE(llvm::is_sorted(L2));
 442
 443     // Merge.
 444     auto &LHS = IsL1LHS ? L1 : L2;
 445     auto &RHS = IsL1LHS ? L2 : L1;
 446     LHS.merge(RHS);
 447     EXPECT_TRUE(RHS.empty());
 448     EXPECT_FALSE(LHS.empty());
 449     EXPECT_TRUE(llvm::is_sorted(LHS));
 450     auto I = LHS.begin();
 451     for (Node &N : Ns)
 452       EXPECT_EQ(&N, &*I++);
 453     EXPECT_EQ(LHS.end(), I);
 454   }
 455 }
 456
 457 TEST(SimpleIListTest, mergeIsStable) {
 458   simple_ilist<Node> L1, L2;
 459   Node Ns[5];
 460
 461   auto setup = [&]() {
 462     EXPECT_TRUE(L1.empty());
 463     EXPECT_TRUE(L2.empty());
 464
 465     // Fill L1.
 466     L1.push_back(Ns[0]);
 467     L1.push_back(Ns[3]);
 468     L1.push_back(Ns[4]);
 469
 470     // Fill L2.
 471     L2.push_back(Ns[1]);
 472     L2.push_back(Ns[2]);
 473
 474     // Check setup.
 475     EXPECT_EQ(3u, L1.size());
 476     EXPECT_EQ(2u, L2.size());
 477     EXPECT_TRUE(llvm::is_sorted(L1, makeFalse));
 478     EXPECT_TRUE(llvm::is_sorted(L2, makeFalse));
 479   };
 480
 481   // Merge.  Should be stable.
 482   setup();
 483   L1.merge(L2, makeFalse);
 484   EXPECT_TRUE(L2.empty());
 485   EXPECT_FALSE(L1.empty());
 486   EXPECT_TRUE(llvm::is_sorted(L1, makeFalse));
 487   auto I = L1.begin();
 488   EXPECT_EQ(&Ns[0], &*I++);
 489   EXPECT_EQ(&Ns[3], &*I++);
 490   EXPECT_EQ(&Ns[4], &*I++);
 491   EXPECT_EQ(&Ns[1], &*I++);
 492   EXPECT_EQ(&Ns[2], &*I++);
 493   EXPECT_EQ(L1.end(), I);
 494
 495   // Merge the other way.  Should be stable.
 496   L1.clear();
 497   setup();
 498   L2.merge(L1, makeFalse);
 499   EXPECT_TRUE(L1.empty());
 500   EXPECT_FALSE(L2.empty());
 501   EXPECT_TRUE(llvm::is_sorted(L2, makeFalse));
 502   I = L2.begin();
 503   EXPECT_EQ(&Ns[1], &*I++);
 504   EXPECT_EQ(&Ns[2], &*I++);
 505   EXPECT_EQ(&Ns[0], &*I++);
 506   EXPECT_EQ(&Ns[3], &*I++);
 507   EXPECT_EQ(&Ns[4], &*I++);
 508   EXPECT_EQ(L2.end(), I);
 509 }
 510
 511 TEST(SimpleIListTest, mergeEmpty) {
 512   for (bool IsL1LHS : {false, true}) {
 513     simple_ilist<Node> L1, L2;
 514     Node Ns[4];
 515
 516     // Fill L1.
 517     L1.push_back(Ns[0]);
 518     L1.push_back(Ns[1]);
 519     L1.push_back(Ns[2]);
 520     L1.push_back(Ns[3]);
 521
 522     // Check setup.
 523     EXPECT_EQ(4u, L1.size());
 524     EXPECT_TRUE(L2.empty());
 525     EXPECT_TRUE(llvm::is_sorted(L1));
 526
 527     // Merge.
 528     auto &LHS = IsL1LHS ? L1 : L2;
 529     auto &RHS = IsL1LHS ? L2 : L1;
 530     LHS.merge(RHS);
 531     EXPECT_TRUE(RHS.empty());
 532     EXPECT_FALSE(LHS.empty());
 533     EXPECT_TRUE(llvm::is_sorted(LHS));
 534     auto I = LHS.begin();
 535     for (Node &N : Ns)
 536       EXPECT_EQ(&N, &*I++);
 537     EXPECT_EQ(LHS.end(), I);
 538   }
 539 }
 540
 541 TEST(SimpleIListTest, mergeBothEmpty) {
 542   simple_ilist<Node> L1, L2;
 543   L1.merge(L2);
 544   EXPECT_TRUE(L1.empty());
 545   EXPECT_TRUE(L2.empty());
 546 }
 547
 548 TEST(SimpleIListTest, sort) {
 549   simple_ilist<Node> L;
 550   Node Ns[10];
 551
 552   // Fill L.
 553   for (int I : {3, 4, 0, 8, 1, 2, 6, 7, 9, 5})
 554     L.push_back(Ns[I]);
 555
 556   // Check setup.
 557   EXPECT_EQ(10u, L.size());
 558   EXPECT_FALSE(llvm::is_sorted(L));
 559
 560   // Sort.
 561   L.sort();
 562   EXPECT_TRUE(llvm::is_sorted(L));
 563   auto I = L.begin();
 564   for (Node &N : Ns)
 565     EXPECT_EQ(&N, &*I++);
 566   EXPECT_EQ(L.end(), I);
 567 }
 568
 569 TEST(SimpleIListTest, sortIsStable) {
 570   simple_ilist<Node> L;
 571   Node Ns[10];
 572
 573   // Compare such that nodes are partitioned but not fully sorted.
 574   auto partition = [&](const Node &N) { return &N >= &Ns[5]; };
 575   auto compare = [&](const Node &L, const Node &R) {
 576     return partition(L) < partition(R);
 577   };
 578
 579   // Fill L.
 580   for (int I : {3, 4, 7, 8, 1, 2, 6, 0, 9, 5})
 581     L.push_back(Ns[I]);
 582
 583   // Check setup.
 584   EXPECT_EQ(10u, L.size());
 585   EXPECT_FALSE(llvm::is_sorted(L, compare));
 586
 587   // Sort.
 588   L.sort(compare);
 589   EXPECT_TRUE(llvm::is_sorted(L, compare));
 590   auto I = L.begin();
 591   for (int O : {3, 4, 1, 2, 0})
 592     EXPECT_EQ(&Ns[O], &*I++);
 593   for (int O : {7, 8, 6, 9, 5})
 594     EXPECT_EQ(&Ns[O], &*I++);
 595   EXPECT_EQ(L.end(), I);
 596 }
 597
 598 TEST(SimpleIListTest, sortEmpty) {
 599   simple_ilist<Node> L;
 600   L.sort();
 601 }
 602
 603 struct Tag1 {};
 604 struct Tag2 {};
 605
 606 struct DoubleNode : ilist_node<DoubleNode, ilist_tag<Tag1>>,
 607                     ilist_node<DoubleNode, ilist_tag<Tag2>> {
 608   typedef ilist_node<DoubleNode, ilist_tag<Tag1>> Node1Type;
 609   typedef ilist_node<DoubleNode, ilist_tag<Tag2>> Node2Type;
 610
 611   Node1Type::self_iterator getIterator1() { return Node1Type::getIterator(); }
 612   Node2Type::self_iterator getIterator2() { return Node2Type::getIterator(); }
 613   Node1Type::const_self_iterator getIterator1() const {
 614     return Node1Type::getIterator();
 615   }
 616   Node2Type::const_self_iterator getIterator2() const {
 617     return Node2Type::getIterator();
 618   }
 619 };
 620 typedef simple_ilist<DoubleNode, ilist_tag<Tag1>> TaggedList1Type;
 621 typedef simple_ilist<DoubleNode, ilist_tag<Tag2>> TaggedList2Type;
 622
 623 TEST(SimpleIListTest, TaggedLists) {
 624   TaggedList1Type L1;
 625   TaggedList2Type L2;
 626
 627   // Build the two lists, sharing a couple of nodes.
 628   DoubleNode Ns[10];
 629   int Order1[] = {0, 1, 2, 3, 4, 7, 9};
 630   int Order2[] = {2, 5, 6, 7, 8, 4, 9, 1};
 631   for (int I : Order1)
 632     L1.push_back(Ns[I]);
 633   for (int I : Order2)
 634     L2.push_back(Ns[I]);
 635
 636   // Check that each list is correct.
 637   EXPECT_EQ(sizeof(Order1) / sizeof(int), L1.size());
 638   auto I1 = L1.begin();
 639   for (int I : Order1) {
 640     EXPECT_EQ(Ns[I].getIterator1(), I1);
 641     EXPECT_EQ(&Ns[I], &*I1++);
 642   }
 643   EXPECT_EQ(L1.end(), I1);
 644
 645   EXPECT_EQ(sizeof(Order2) / sizeof(int), L2.size());
 646   auto I2 = L2.begin();
 647   for (int I : Order2) {
 648     EXPECT_EQ(Ns[I].getIterator2(), I2);
 649     EXPECT_EQ(&Ns[I], &*I2++);
 650   }
 651   EXPECT_EQ(L2.end(), I2);
 652 }
 653
 654 } // end namespace