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