1 // Licensed to the .NET Foundation under one or more agreements. 2 // The .NET Foundation licenses this file to you under the MIT license. 3 // See the LICENSE file in the project root for more information. 4 5 using System.Collections.Generic; 6 using Xunit; 7 8 namespace System.Collections.Tests 9 { 10 /// <summary> 11 /// Contains tests that ensure the correctness of the LinkedList class. 12 /// </summary> 13 public abstract partial class LinkedList_Generic_Tests<T> : ICollection_Generic_Tests<T> 14 { 15 [Fact] AddAfter_LLNode()16 public void AddAfter_LLNode() 17 { 18 LinkedList<T> linkedList = new LinkedList<T>(); 19 int arraySize = 16; 20 int seed = 8293; 21 T[] tempItems, headItems, headItemsReverse, tailItems; 22 23 headItems = new T[arraySize]; 24 tailItems = new T[arraySize]; 25 headItemsReverse = new T[arraySize]; 26 for (int i = 0; i < arraySize; i++) 27 { 28 int index = (arraySize - 1) - i; 29 T head = CreateT(seed++); 30 T tail = CreateT(seed++); 31 headItems[i] = head; 32 headItemsReverse[index] = head; 33 tailItems[i] = tail; 34 } 35 36 //[] Verify value is default(T) 37 linkedList = new LinkedList<T>(); 38 linkedList.AddFirst(headItems[0]); 39 linkedList.AddAfter(linkedList.First, default(T)); 40 InitialItems_Tests(linkedList, new T[] { headItems[0], default(T) }); 41 42 //[] Node is the Head 43 linkedList = new LinkedList<T>(); 44 linkedList.AddFirst(headItems[0]); 45 46 tempItems = new T[headItems.Length]; 47 Array.Copy(headItems, 0, tempItems, 0, headItems.Length); 48 Array.Reverse(tempItems, 1, headItems.Length - 1); 49 50 for (int i = 1; i < arraySize; ++i) 51 linkedList.AddAfter(linkedList.First, headItems[i]); 52 53 InitialItems_Tests(linkedList, tempItems); 54 55 //[] Node is the Tail 56 linkedList = new LinkedList<T>(); 57 linkedList.AddFirst(headItems[0]); 58 for (int i = 1; i < arraySize; ++i) 59 linkedList.AddAfter(linkedList.Last, headItems[i]); 60 61 InitialItems_Tests(linkedList, headItems); 62 63 //[] Node is after the Head 64 linkedList = new LinkedList<T>(); 65 linkedList.AddFirst(headItems[0]); 66 linkedList.AddLast(headItems[1]); 67 68 tempItems = new T[headItems.Length]; 69 Array.Copy(headItems, 0, tempItems, 0, headItems.Length); 70 Array.Reverse(tempItems, 2, headItems.Length - 2); 71 72 for (int i = 2; i < arraySize; ++i) 73 linkedList.AddAfter(linkedList.First.Next, headItems[i]); 74 75 InitialItems_Tests(linkedList, tempItems); 76 77 //[] Node is before the Tail 78 linkedList = new LinkedList<T>(); 79 linkedList.AddFirst(headItems[0]); 80 linkedList.AddLast(headItems[1]); 81 82 tempItems = new T[headItems.Length]; 83 Array.Copy(headItems, 2, tempItems, 1, headItems.Length - 2); 84 tempItems[0] = headItems[0]; 85 tempItems[tempItems.Length - 1] = headItems[1]; 86 87 for (int i = 2; i < arraySize; ++i) 88 linkedList.AddAfter(linkedList.Last.Previous, headItems[i]); 89 90 InitialItems_Tests(linkedList, tempItems); 91 92 //[] Node is somewhere in the middle 93 linkedList = new LinkedList<T>(); 94 linkedList.AddFirst(headItems[0]); 95 linkedList.AddLast(headItems[1]); 96 linkedList.AddLast(headItems[2]); 97 98 tempItems = new T[headItems.Length]; 99 Array.Copy(headItems, 3, tempItems, 1, headItems.Length - 3); 100 tempItems[0] = headItems[0]; 101 tempItems[tempItems.Length - 2] = headItems[1]; 102 tempItems[tempItems.Length - 1] = headItems[2]; 103 104 for (int i = 3; i < arraySize; ++i) 105 linkedList.AddAfter(linkedList.Last.Previous.Previous, headItems[i]); 106 107 InitialItems_Tests(linkedList, tempItems); 108 109 //[] Call AddAfter several times remove some of the items 110 linkedList = new LinkedList<T>(); 111 linkedList.AddFirst(headItems[0]); 112 for (int i = 1; i < arraySize; ++i) 113 linkedList.AddAfter(linkedList.Last, headItems[i]); 114 115 linkedList.Remove(headItems[2]); 116 linkedList.Remove(headItems[headItems.Length - 3]); 117 linkedList.Remove(headItems[1]); 118 linkedList.Remove(headItems[headItems.Length - 2]); 119 linkedList.RemoveFirst(); 120 linkedList.RemoveLast(); 121 //With the above remove we should have removed the first and last 3 items 122 tempItems = new T[headItems.Length - 6]; 123 Array.Copy(headItems, 3, tempItems, 0, headItems.Length - 6); 124 125 InitialItems_Tests(linkedList, tempItems); 126 127 for (int i = 0; i < arraySize; ++i) 128 linkedList.AddAfter(linkedList.Last, tailItems[i]); 129 130 T[] tempItems2 = new T[tempItems.Length + tailItems.Length]; 131 Array.Copy(tempItems, 0, tempItems2, 0, tempItems.Length); 132 Array.Copy(tailItems, 0, tempItems2, tempItems.Length, tailItems.Length); 133 134 InitialItems_Tests(linkedList, tempItems2); 135 136 //[] Call AddAfter several times remove all of the items 137 linkedList = new LinkedList<T>(); 138 linkedList.AddFirst(headItems[0]); 139 for (int i = 1; i < arraySize; ++i) 140 linkedList.AddAfter(linkedList.Last, headItems[i]); 141 142 for (int i = 0; i < arraySize; ++i) 143 linkedList.RemoveFirst(); 144 145 linkedList.AddFirst(tailItems[0]); 146 for (int i = 1; i < arraySize; ++i) 147 linkedList.AddAfter(linkedList.Last, tailItems[i]); 148 149 InitialItems_Tests(linkedList, tailItems); 150 151 //[] Call AddAfter several times then call Clear 152 linkedList = new LinkedList<T>(); 153 linkedList.AddFirst(headItems[0]); 154 for (int i = 1; i < arraySize; ++i) 155 linkedList.AddAfter(linkedList.Last, headItems[i]); 156 157 linkedList.Clear(); 158 159 linkedList.AddFirst(tailItems[0]); 160 for (int i = 1; i < arraySize; ++i) 161 linkedList.AddAfter(linkedList.Last, tailItems[i]); 162 163 InitialItems_Tests(linkedList, tailItems); 164 165 //[] Mix AddBefore and AddAfter calls 166 linkedList = new LinkedList<T>(); 167 linkedList.AddLast(headItems[0]); 168 linkedList.AddLast(tailItems[0]); 169 for (int i = 1; i < arraySize; ++i) 170 { 171 linkedList.AddBefore(linkedList.First, headItems[i]); 172 linkedList.AddAfter(linkedList.Last, tailItems[i]); 173 } 174 175 tempItems = new T[headItemsReverse.Length + tailItems.Length]; 176 Array.Copy(headItemsReverse, 0, tempItems, 0, headItemsReverse.Length); 177 Array.Copy(tailItems, 0, tempItems, headItemsReverse.Length, tailItems.Length); 178 InitialItems_Tests(linkedList, tempItems); 179 } 180 181 [Fact] AddAfter_LLNode_Negative()182 public void AddAfter_LLNode_Negative() 183 { 184 LinkedList<T> linkedList = new LinkedList<T>(); 185 LinkedList<T> tempLinkedList = new LinkedList<T>(); 186 int seed = 8293; 187 T[] items; 188 189 //[] Verify Null node 190 linkedList = new LinkedList<T>(); 191 Assert.Throws<ArgumentNullException>(() => linkedList.AddAfter(null, CreateT(seed++))); //"Err_858ahia Expected null node to throws ArgumentNullException\n" 192 193 InitialItems_Tests(linkedList, new T[0]); 194 //[] Verify Node that is a new Node 195 linkedList = new LinkedList<T>(); 196 items = new T[] { CreateT(seed++) }; 197 linkedList.AddLast(items[0]); 198 Assert.Throws<InvalidOperationException>(() => linkedList.AddAfter(new LinkedListNode<T>(CreateT(seed++)), CreateT(seed++))); //"Err_0568ajods Expected Node that is a new Node throws InvalidOperationException\n" 199 200 InitialItems_Tests(linkedList, items); 201 202 //[] Verify Node that already exists in another collection 203 linkedList = new LinkedList<T>(); 204 items = new T[] { CreateT(seed++), CreateT(seed++) }; 205 linkedList.AddLast(items[0]); 206 linkedList.AddLast(items[1]); 207 208 tempLinkedList.Clear(); 209 tempLinkedList.AddLast(CreateT(seed++)); 210 tempLinkedList.AddLast(CreateT(seed++)); 211 Assert.Throws<InvalidOperationException>(() => linkedList.AddAfter(tempLinkedList.Last, CreateT(seed++))); //"Err_98809ahied Node that already exists in another collection throws InvalidOperationException\n" 212 213 InitialItems_Tests(linkedList, items); 214 } 215 216 [Fact] AddAfter_LLNode_LLNode()217 public void AddAfter_LLNode_LLNode() 218 { 219 LinkedList<T> linkedList = new LinkedList<T>(); 220 int seed = 8293; 221 int arraySize = 16; 222 T[] tempItems, headItems, headItemsReverse, tailItems, tailItemsReverse; 223 224 headItems = new T[arraySize]; 225 tailItems = new T[arraySize]; 226 headItemsReverse = new T[arraySize]; 227 tailItemsReverse = new T[arraySize]; 228 for (int i = 0; i < arraySize; i++) 229 { 230 int index = (arraySize - 1) - i; 231 T head = CreateT(seed++); 232 T tail = CreateT(seed++); 233 headItems[i] = head; 234 headItemsReverse[index] = head; 235 tailItems[i] = tail; 236 tailItemsReverse[index] = tail; 237 } 238 239 //[] Verify value is default(T) 240 linkedList = new LinkedList<T>(); 241 linkedList.AddFirst(headItems[0]); 242 linkedList.AddAfter(linkedList.First, new LinkedListNode<T>(default(T))); 243 InitialItems_Tests(linkedList, new T[] { headItems[0], default(T) }); 244 245 //[] Node is the Head 246 linkedList = new LinkedList<T>(); 247 linkedList.AddFirst(headItems[0]); 248 249 tempItems = new T[headItems.Length]; 250 Array.Copy(headItems, 0, tempItems, 0, headItems.Length); 251 Array.Reverse(tempItems, 1, headItems.Length - 1); 252 253 for (int i = 1; i < arraySize; ++i) 254 linkedList.AddAfter(linkedList.First, new LinkedListNode<T>(headItems[i])); 255 256 InitialItems_Tests(linkedList, tempItems); 257 258 //[] Node is the Tail 259 linkedList = new LinkedList<T>(); 260 linkedList.AddFirst(headItems[0]); 261 for (int i = 1; i < arraySize; ++i) 262 linkedList.AddAfter(linkedList.Last, new LinkedListNode<T>(headItems[i])); 263 264 InitialItems_Tests(linkedList, headItems); 265 266 //[] Node is after the Head 267 linkedList = new LinkedList<T>(); 268 linkedList.AddFirst(headItems[0]); 269 linkedList.AddLast(headItems[1]); 270 tempItems = new T[headItems.Length]; 271 Array.Copy(headItems, 0, tempItems, 0, headItems.Length); 272 Array.Reverse(tempItems, 2, headItems.Length - 2); 273 274 for (int i = 2; i < arraySize; ++i) 275 linkedList.AddAfter(linkedList.First.Next, new LinkedListNode<T>(headItems[i])); 276 277 InitialItems_Tests(linkedList, tempItems); 278 279 //[] Node is before the Tail 280 linkedList = new LinkedList<T>(); 281 linkedList.AddFirst(headItems[0]); 282 linkedList.AddLast(headItems[1]); 283 284 tempItems = new T[headItems.Length]; 285 Array.Copy(headItems, 2, tempItems, 1, headItems.Length - 2); 286 tempItems[0] = headItems[0]; 287 tempItems[tempItems.Length - 1] = headItems[1]; 288 289 for (int i = 2; i < arraySize; ++i) 290 linkedList.AddAfter(linkedList.Last.Previous, new LinkedListNode<T>(headItems[i])); 291 292 InitialItems_Tests(linkedList, tempItems); 293 294 //[] Node is somewhere in the middle 295 linkedList = new LinkedList<T>(); 296 linkedList.AddFirst(headItems[0]); 297 linkedList.AddLast(headItems[1]); 298 linkedList.AddLast(headItems[2]); 299 300 tempItems = new T[headItems.Length]; 301 Array.Copy(headItems, 3, tempItems, 1, headItems.Length - 3); 302 tempItems[0] = headItems[0]; 303 tempItems[tempItems.Length - 2] = headItems[1]; 304 tempItems[tempItems.Length - 1] = headItems[2]; 305 306 for (int i = 3; i < arraySize; ++i) 307 linkedList.AddAfter(linkedList.Last.Previous.Previous, new LinkedListNode<T>(headItems[i])); 308 309 InitialItems_Tests(linkedList, tempItems); 310 311 312 //[] Call AddAfter several times remove some of the items 313 linkedList = new LinkedList<T>(); 314 linkedList.AddFirst(headItems[0]); 315 for (int i = 1; i < arraySize; ++i) 316 linkedList.AddAfter(linkedList.Last, new LinkedListNode<T>(headItems[i])); 317 318 linkedList.Remove(headItems[2]); 319 linkedList.Remove(headItems[headItems.Length - 3]); 320 linkedList.Remove(headItems[1]); 321 linkedList.Remove(headItems[headItems.Length - 2]); 322 linkedList.RemoveFirst(); 323 linkedList.RemoveLast(); 324 //With the above remove we should have removed the first and last 3 items 325 tempItems = new T[headItems.Length - 6]; 326 Array.Copy(headItems, 3, tempItems, 0, headItems.Length - 6); 327 328 InitialItems_Tests(linkedList, tempItems); 329 330 for (int i = 0; i < arraySize; ++i) 331 linkedList.AddAfter(linkedList.Last, new LinkedListNode<T>(tailItems[i])); 332 333 T[] tempItems2 = new T[tempItems.Length + tailItems.Length]; 334 Array.Copy(tempItems, 0, tempItems2, 0, tempItems.Length); 335 Array.Copy(tailItems, 0, tempItems2, tempItems.Length, tailItems.Length); 336 337 InitialItems_Tests(linkedList, tempItems2); 338 339 //[] Call AddAfter several times remove all of the items 340 linkedList = new LinkedList<T>(); 341 linkedList.AddFirst(headItems[0]); 342 for (int i = 1; i < arraySize; ++i) 343 linkedList.AddAfter(linkedList.Last, new LinkedListNode<T>(headItems[i])); 344 345 for (int i = 0; i < arraySize; ++i) 346 linkedList.RemoveFirst(); 347 348 linkedList.AddFirst(tailItems[0]); 349 for (int i = 1; i < arraySize; ++i) 350 linkedList.AddAfter(linkedList.Last, new LinkedListNode<T>(tailItems[i])); 351 352 InitialItems_Tests(linkedList, tailItems); 353 354 //[] Call AddAfter several times then call Clear 355 linkedList = new LinkedList<T>(); 356 linkedList.AddFirst(headItems[0]); 357 for (int i = 1; i < arraySize; ++i) 358 linkedList.AddAfter(linkedList.Last, new LinkedListNode<T>(headItems[i])); 359 360 linkedList.Clear(); 361 362 linkedList.AddFirst(tailItems[0]); 363 for (int i = 1; i < arraySize; ++i) 364 linkedList.AddAfter(linkedList.Last, new LinkedListNode<T>(tailItems[i])); 365 366 InitialItems_Tests(linkedList, tailItems); 367 368 //[] Mix AddBefore and AddAfter calls 369 linkedList = new LinkedList<T>(); 370 linkedList.AddLast(headItems[0]); 371 linkedList.AddLast(tailItems[0]); 372 for (int i = 1; i < arraySize; ++i) 373 { 374 if (0 == (i & 1)) 375 { 376 linkedList.AddBefore(linkedList.First, headItems[i]); 377 linkedList.AddAfter(linkedList.Last, tailItems[i]); 378 } 379 else 380 { 381 linkedList.AddBefore(linkedList.First, new LinkedListNode<T>(headItems[i])); 382 linkedList.AddAfter(linkedList.Last, new LinkedListNode<T>(tailItems[i])); 383 } 384 } 385 386 tempItems = new T[headItemsReverse.Length + tailItems.Length]; 387 Array.Copy(headItemsReverse, 0, tempItems, 0, headItemsReverse.Length); 388 Array.Copy(tailItems, 0, tempItems, headItemsReverse.Length, tailItems.Length); 389 InitialItems_Tests(linkedList, tempItems); 390 } 391 392 [Fact] AddAfter_LLNode_LLNode_Negative()393 public void AddAfter_LLNode_LLNode_Negative() 394 { 395 LinkedList<T> linkedList = new LinkedList<T>(); 396 LinkedList<T> tempLinkedList = new LinkedList<T>(); 397 int seed = 8293; 398 T[] items; 399 400 //[] Verify Null node 401 linkedList = new LinkedList<T>(); 402 Assert.Throws<ArgumentNullException>(() => linkedList.AddAfter(null, new LinkedListNode<T>(CreateT(seed++)))); //"Err_858ahia Expected null node to throws ArgumentNullException\n" 403 InitialItems_Tests(linkedList, new T[0]); 404 405 //[] Verify Node that is a new Node 406 linkedList = new LinkedList<T>(); 407 items = new T[] { CreateT(seed++) }; 408 linkedList.AddLast(items[0]); 409 Assert.Throws<InvalidOperationException>(() => linkedList.AddAfter(new LinkedListNode<T>(CreateT(seed++)), new LinkedListNode<T>(CreateT(seed++)))); //"Err_0568ajods Expected Node that is a new Node throws InvalidOperationException\n" 410 411 InitialItems_Tests(linkedList, items); 412 413 //[] Verify Node that already exists in another collection 414 linkedList = new LinkedList<T>(); 415 items = new T[] { CreateT(seed++), CreateT(seed++) }; 416 linkedList.AddLast(items[0]); 417 linkedList.AddLast(items[1]); 418 419 tempLinkedList.Clear(); 420 tempLinkedList.AddLast(CreateT(seed++)); 421 tempLinkedList.AddLast(CreateT(seed++)); 422 Assert.Throws<InvalidOperationException>(() => linkedList.AddAfter(tempLinkedList.Last, new LinkedListNode<T>(CreateT(seed++)))); //"Err_98809ahied Node that already exists in another collection throws InvalidOperationException\n" 423 424 InitialItems_Tests(linkedList, items); 425 426 // negative tests on NewNode 427 428 //[] Verify Null newNode 429 linkedList = new LinkedList<T>(); 430 items = new T[] { CreateT(seed++) }; 431 linkedList.AddLast(items[0]); 432 Assert.Throws<ArgumentNullException>(() => linkedList.AddAfter(linkedList.First, null)); //"Err_0808ajeoia Expected null newNode to throws ArgumentNullException\n" 433 434 InitialItems_Tests(linkedList, items); 435 436 //[] Verify newNode that already exists in this collection 437 linkedList = new LinkedList<T>(); 438 items = new T[] { CreateT(seed++), CreateT(seed++) }; 439 linkedList.AddLast(items[0]); 440 linkedList.AddLast(items[1]); 441 Assert.Throws<InvalidOperationException>(() => linkedList.AddAfter(linkedList.First, linkedList.Last)); //"Err_58808adjioe Verify newNode that already exists in this collection throws InvalidOperationException\n" 442 443 InitialItems_Tests(linkedList, items); 444 445 //[] Verify newNode that already exists in another collection 446 linkedList = new LinkedList<T>(); 447 items = new T[] { CreateT(seed++), CreateT(seed++) }; 448 linkedList.AddLast(items[0]); 449 linkedList.AddLast(items[1]); 450 451 tempLinkedList.Clear(); 452 tempLinkedList.AddLast(CreateT(seed++)); 453 tempLinkedList.AddLast(CreateT(seed++)); 454 Assert.Throws<InvalidOperationException>(() => linkedList.AddAfter(linkedList.First, tempLinkedList.Last)); //"Err_54808ajied newNode that already exists in another collection throws InvalidOperationException\n" 455 456 InitialItems_Tests(linkedList, items); 457 } 458 } 459 }