PriorityLinkedListTest.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements. See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License. You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.activemq.artemis.core.list;

import java.util.HashSet;
import java.util.Iterator;
import java.util.Objects;

import io.netty.util.collection.LongObjectHashMap;
import org.apache.activemq.artemis.utils.collections.NodeStore;
import org.apache.activemq.artemis.utils.collections.LinkedListImpl;
import org.apache.activemq.artemis.utils.collections.LinkedListIterator;
import org.apache.activemq.artemis.utils.collections.PriorityLinkedListImpl;
import org.junit.Assert;
import org.junit.Before;
import org.junit.Test;

public final class PriorityLinkedListTest extends Assert {

   protected Wibble a;

   protected Wibble b;

   protected Wibble c;

   protected Wibble d;

   protected Wibble e;

   protected Wibble f;

   protected Wibble g;

   protected Wibble h;

   protected Wibble i;

   protected Wibble j;

   protected Wibble k;

   protected Wibble l;

   protected Wibble m;

   protected Wibble n;

   protected Wibble o;

   protected Wibble p;

   protected Wibble q;

   protected Wibble r;

   protected Wibble s;

   protected Wibble t;

   protected Wibble u;

   protected Wibble v;

   protected Wibble w;

   protected Wibble x;

   protected Wibble y;

   protected Wibble z;

   private PriorityLinkedListImpl<Wibble> list;

   protected PriorityLinkedListImpl<Wibble> getList() {
      return new PriorityLinkedListImpl<>(10);
   }

   @Before
   public void setUp() throws Exception {

      list = getList();

      a = new Wibble("a", 1);
      b = new Wibble("b", 2);
      c = new Wibble("c", 3);
      d = new Wibble("d", 4);
      e = new Wibble("e", 5);
      f = new Wibble("f", 6);
      g = new Wibble("g", 7);
      h = new Wibble("h", 8);
      i = new Wibble("i", 9);
      j = new Wibble("j", 10);
      k = new Wibble("k", 11);
      l = new Wibble("l", 12);
      m = new Wibble("m", 13);
      n = new Wibble("n", 14);
      o = new Wibble("o", 15);
      p = new Wibble("p", 16);
      q = new Wibble("q", 17);
      r = new Wibble("r", 18);
      s = new Wibble("s", 19);
      t = new Wibble("t", 20);
      u = new Wibble("u", 21);
      v = new Wibble("v", 22);
      w = new Wibble("w", 23);
      x = new Wibble("x", 24);
      y = new Wibble("y", 25);
      z = new Wibble("z", 26);
   }

   @Test
   public void testEmpty() throws Exception {
      Assert.assertTrue(list.isEmpty());

      list.addHead(a, 0);

      Assert.assertFalse(list.isEmpty());

      Wibble w1 = list.poll();
      Assert.assertEquals(a, w1);
      Assert.assertTrue(list.isEmpty());

      assertEquals(0, list.size());
   }

   @Test
   public void testaddHead() throws Exception {
      list.addHead(a, 0);
      list.addHead(b, 0);
      list.addHead(c, 0);
      list.addHead(d, 0);
      list.addHead(e, 0);

      assertEquals(5, list.size());

      Assert.assertEquals(e, list.poll());
      Assert.assertEquals(d, list.poll());
      Assert.assertEquals(c, list.poll());
      Assert.assertEquals(b, list.poll());
      Assert.assertEquals(a, list.poll());
      Assert.assertNull(list.poll());

      assertEquals(0, list.size());
   }

   @Test
   public void testaddTail() throws Exception {
      list.addTail(a, 0);
      list.addTail(b, 0);
      list.addTail(c, 0);
      list.addTail(d, 0);
      list.addTail(e, 0);
      assertEquals(5, list.size());

      Assert.assertEquals(a, list.poll());
      Assert.assertEquals(b, list.poll());
      Assert.assertEquals(c, list.poll());
      Assert.assertEquals(d, list.poll());
      Assert.assertEquals(e, list.poll());
      Assert.assertNull(list.poll());

      assertEquals(0, list.size());

   }

   @Test
   public void testAddLastAndFirst() throws Exception {
      list.addTail(a, 0);
      list.addTail(b, 0);
      list.addTail(c, 0);
      list.addTail(d, 0);
      list.addTail(e, 0);
      list.addTail(f, 0);
      list.addTail(g, 0);
      list.addTail(h, 0);
      list.addTail(i, 0);
      list.addTail(j, 0);

      list.addHead(k, 0);
      list.addHead(l, 0);
      list.addHead(m, 0);
      list.addHead(n, 0);
      list.addHead(o, 0);
      list.addHead(p, 0);
      list.addHead(q, 0);
      list.addHead(r, 0);
      list.addHead(s, 0);
      list.addHead(t, 0);

      assertEquals(t, list.poll());
      assertEquals(s, list.poll());
      assertEquals(r, list.poll());
      assertEquals(q, list.poll());
      assertEquals(p, list.poll());
      assertEquals(o, list.poll());
      assertEquals(n, list.poll());
      assertEquals(m, list.poll());
      assertEquals(l, list.poll());
      assertEquals(k, list.poll());

      assertEquals(a, list.poll());
      assertEquals(b, list.poll());
      assertEquals(c, list.poll());
      assertEquals(d, list.poll());
      assertEquals(e, list.poll());
      assertEquals(f, list.poll());
      assertEquals(g, list.poll());
      assertEquals(h, list.poll());
      assertEquals(i, list.poll());
      assertEquals(j, list.poll());
   }

   @Test
   public void testAddLastAndFirstWithIterator() throws Exception {
      list.addTail(a, 0);
      list.addTail(b, 0);
      list.addTail(c, 0);
      list.addTail(d, 0);
      list.addTail(e, 0);
      list.addTail(f, 0);
      list.addTail(g, 0);
      list.addTail(h, 0);
      list.addTail(i, 0);
      list.addTail(j, 0);

      list.addHead(k, 0);
      list.addHead(l, 0);
      list.addHead(m, 0);
      list.addHead(n, 0);
      list.addHead(o, 0);
      list.addHead(p, 0);
      list.addHead(q, 0);
      list.addHead(r, 0);
      list.addHead(s, 0);
      list.addHead(t, 0);

      LinkedListIterator<Wibble> iter = list.iterator();

      assertTrue(iter.hasNext());
      assertEquals(t, iter.next());
      assertTrue(iter.hasNext());
      assertEquals(s, iter.next());
      assertTrue(iter.hasNext());
      assertEquals(r, iter.next());
      assertTrue(iter.hasNext());
      assertEquals(q, iter.next());
      assertTrue(iter.hasNext());
      assertEquals(p, iter.next());
      assertTrue(iter.hasNext());
      assertEquals(o, iter.next());
      assertTrue(iter.hasNext());
      assertEquals(n, iter.next());
      assertTrue(iter.hasNext());
      assertEquals(m, iter.next());
      assertTrue(iter.hasNext());
      assertEquals(l, iter.next());
      assertTrue(iter.hasNext());
      assertEquals(k, iter.next());

      assertTrue(iter.hasNext());
      assertEquals(a, iter.next());
      assertTrue(iter.hasNext());
      assertEquals(b, iter.next());
      assertTrue(iter.hasNext());
      assertEquals(c, iter.next());
      assertTrue(iter.hasNext());
      assertEquals(d, iter.next());
      assertTrue(iter.hasNext());
      assertEquals(e, iter.next());
      assertTrue(iter.hasNext());
      assertEquals(f, iter.next());
      assertTrue(iter.hasNext());
      assertEquals(g, iter.next());
      assertTrue(iter.hasNext());
      assertEquals(h, iter.next());
      assertTrue(iter.hasNext());
      assertEquals(i, iter.next());
      assertTrue(iter.hasNext());
      assertEquals(j, iter.next());
   }

   @Test
   public void testPoll() throws Exception {
      list.addTail(a, 0);
      list.addTail(b, 1);
      list.addTail(c, 2);
      list.addTail(d, 3);
      list.addTail(e, 4);
      list.addTail(f, 5);
      list.addTail(g, 6);
      list.addTail(h, 7);
      list.addTail(i, 8);
      list.addTail(j, 9);

      Assert.assertEquals(j, list.poll());
      Assert.assertEquals(i, list.poll());
      Assert.assertEquals(h, list.poll());
      Assert.assertEquals(g, list.poll());
      Assert.assertEquals(f, list.poll());
      Assert.assertEquals(e, list.poll());
      Assert.assertEquals(d, list.poll());
      Assert.assertEquals(c, list.poll());
      Assert.assertEquals(b, list.poll());
      Assert.assertEquals(a, list.poll());

      Assert.assertNull(list.poll());

      list.addTail(a, 9);
      list.addTail(b, 8);
      list.addTail(c, 7);
      list.addTail(d, 6);
      list.addTail(e, 5);
      list.addTail(f, 4);
      list.addTail(g, 3);
      list.addTail(h, 2);
      list.addTail(i, 1);
      list.addTail(j, 0);

      Assert.assertEquals(a, list.poll());
      Assert.assertEquals(b, list.poll());
      Assert.assertEquals(c, list.poll());
      Assert.assertEquals(d, list.poll());
      Assert.assertEquals(e, list.poll());
      Assert.assertEquals(f, list.poll());
      Assert.assertEquals(g, list.poll());
      Assert.assertEquals(h, list.poll());
      Assert.assertEquals(i, list.poll());
      Assert.assertEquals(j, list.poll());

      Assert.assertNull(list.poll());

      list.addTail(a, 9);
      list.addTail(b, 0);
      list.addTail(c, 8);
      list.addTail(d, 1);
      list.addTail(e, 7);
      list.addTail(f, 2);
      list.addTail(g, 6);
      list.addTail(h, 3);
      list.addTail(i, 5);
      list.addTail(j, 4);

      Assert.assertEquals(a, list.poll());
      Assert.assertEquals(c, list.poll());
      Assert.assertEquals(e, list.poll());
      Assert.assertEquals(g, list.poll());
      Assert.assertEquals(i, list.poll());
      Assert.assertEquals(j, list.poll());
      Assert.assertEquals(h, list.poll());
      Assert.assertEquals(f, list.poll());
      Assert.assertEquals(d, list.poll());
      Assert.assertEquals(b, list.poll());

      Assert.assertNull(list.poll());

      list.addTail(a, 0);
      list.addTail(b, 3);
      list.addTail(c, 3);
      list.addTail(d, 3);
      list.addTail(e, 6);
      list.addTail(f, 6);
      list.addTail(g, 6);
      list.addTail(h, 9);
      list.addTail(i, 9);
      list.addTail(j, 9);

      Assert.assertEquals(h, list.poll());
      Assert.assertEquals(i, list.poll());
      Assert.assertEquals(j, list.poll());
      Assert.assertEquals(e, list.poll());
      Assert.assertEquals(f, list.poll());
      Assert.assertEquals(g, list.poll());
      Assert.assertEquals(b, list.poll());
      Assert.assertEquals(c, list.poll());
      Assert.assertEquals(d, list.poll());
      Assert.assertEquals(a, list.poll());

      Assert.assertNull(list.poll());

      list.addTail(a, 5);
      list.addTail(b, 5);
      list.addTail(c, 5);
      list.addTail(d, 5);
      list.addTail(e, 5);
      list.addTail(f, 5);
      list.addTail(g, 5);
      list.addTail(h, 5);
      list.addTail(i, 5);
      list.addTail(j, 5);

      Assert.assertEquals(a, list.poll());
      Assert.assertEquals(b, list.poll());
      Assert.assertEquals(c, list.poll());
      Assert.assertEquals(d, list.poll());
      Assert.assertEquals(e, list.poll());
      Assert.assertEquals(f, list.poll());
      Assert.assertEquals(g, list.poll());
      Assert.assertEquals(h, list.poll());
      Assert.assertEquals(i, list.poll());
      Assert.assertEquals(j, list.poll());

      Assert.assertNull(list.poll());

      list.addTail(j, 5);
      list.addTail(i, 5);
      list.addTail(h, 5);
      list.addTail(g, 5);
      list.addTail(f, 5);
      list.addTail(e, 5);
      list.addTail(d, 5);
      list.addTail(c, 5);
      list.addTail(b, 5);
      list.addTail(a, 5);

      Assert.assertEquals(j, list.poll());
      Assert.assertEquals(i, list.poll());
      Assert.assertEquals(h, list.poll());
      Assert.assertEquals(g, list.poll());
      Assert.assertEquals(f, list.poll());
      Assert.assertEquals(e, list.poll());
      Assert.assertEquals(d, list.poll());
      Assert.assertEquals(c, list.poll());
      Assert.assertEquals(b, list.poll());
      Assert.assertEquals(a, list.poll());

      Assert.assertNull(list.poll());

      assertEquals(0, list.size());

   }

   @Test
   public void testIterator() {
      list.addTail(a, 9);
      list.addTail(b, 9);
      list.addTail(c, 8);
      list.addTail(d, 8);
      list.addTail(e, 7);
      list.addTail(f, 7);
      list.addTail(g, 7);
      list.addTail(h, 6);
      list.addTail(i, 6);
      list.addTail(j, 6);
      list.addTail(k, 5);
      list.addTail(l, 5);
      list.addTail(m, 4);
      list.addTail(n, 4);
      list.addTail(o, 4);
      list.addTail(p, 3);
      list.addTail(q, 3);
      list.addTail(r, 3);
      list.addTail(s, 2);
      list.addTail(t, 2);
      list.addTail(u, 2);
      list.addTail(v, 1);
      list.addTail(w, 1);
      list.addTail(x, 1);
      list.addTail(y, 0);
      list.addTail(z, 0);

      LinkedListIterator<Wibble> iter = list.iterator();

      int count = 0;
      Wibble w1;
      while (iter.hasNext()) {
         w1 = iter.next();
         count++;
      }
      Assert.assertEquals(26, count);
      Assert.assertEquals(26, list.size());

      iter = list.iterator();

      assertTrue(iter.hasNext());
      w1 = iter.next();
      assertTrue(iter.hasNext());
      Assert.assertEquals("a", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      assertTrue(iter.hasNext());
      Assert.assertEquals("b", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("c", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("d", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("e", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("f", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("g", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("h", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("i", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("j", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("k", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("l", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("m", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("n", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("o", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("p", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("q", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("r", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("s", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("t", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("u", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("v", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("w", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("x", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("y", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("z", w1.s1);
      assertFalse(iter.hasNext());

      iter = list.iterator();
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("a", w1.s1);

      iter.remove();

      Assert.assertEquals(25, list.size());

      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("b", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("c", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("d", w1.s1);

      iter.remove();

      Assert.assertEquals(24, list.size());

      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("c", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("e", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("f", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("g", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("h", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("i", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("j", w1.s1);

      iter.remove();

      Assert.assertEquals(23, list.size());

      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("i", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("k", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("l", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("m", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("n", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("o", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("p", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("q", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("r", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("s", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("t", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("u", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("v", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("w", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("x", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("y", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("z", w1.s1);
      iter.remove();

      iter = list.iterator();
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("b", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("c", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("e", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("f", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("g", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("h", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("i", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("k", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("l", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("m", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("n", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("o", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("p", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("q", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("r", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("s", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("t", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("u", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("v", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("w", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("x", w1.s1);
      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("y", w1.s1);

      assertFalse(iter.hasNext());
      assertFalse(iter.hasNext());

      // Test the elements added after iter created are seen

      list.addTail(a, 4);
      list.addTail(b, 4);

      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("a", w1.s1);

      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("b", w1.s1);

      assertFalse(iter.hasNext());

      list.addTail(c, 4);
      list.addTail(d, 4);

      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("c", w1.s1);

      assertTrue(iter.hasNext());
      w1 = iter.next();
      Assert.assertEquals("d", w1.s1);

      assertFalse(iter.hasNext());

   }

   @Test
   public void testIteratorPicksUpHigherPriorities() {
      list.addTail(a, 4);
      list.addTail(b, 4);
      list.addTail(c, 4);

      LinkedListIterator<Wibble> iter = list.iterator();

      assertTrue(iter.hasNext());
      assertEquals(a, iter.next());

      assertTrue(iter.hasNext());
      assertEquals(b, iter.next());

      list.addTail(d, 5);
      list.addTail(e, 5);

      assertTrue(iter.hasNext());
      assertEquals(d, iter.next());

      assertTrue(iter.hasNext());
      assertEquals(e, iter.next());

      assertTrue(iter.hasNext());
      assertEquals(c, iter.next());

      list.addTail(f, 1);
      list.addTail(g, 9);

      assertTrue(iter.hasNext());
      assertEquals(g, iter.next());

      assertTrue(iter.hasNext());
      assertEquals(f, iter.next());
   }

   @Test
   public void testClear() {
      list.addTail(a, 0);
      list.addTail(b, 3);
      list.addTail(c, 3);
      list.addTail(d, 3);
      list.addTail(e, 6);
      list.addTail(f, 6);
      list.addTail(g, 6);
      list.addTail(h, 9);
      list.addTail(i, 9);
      list.addTail(j, 9);

      list.clear();

      Assert.assertNull(list.poll());
   }

   @Test
   public void testMixupIterator() {
      list.addTail(c, 5);
      list.addTail(a, 4);
      list.addTail(b, 4);

      LinkedListIterator<Wibble> iter = list.iterator();

      assertTrue(iter.hasNext());
      assertEquals(c, iter.next());
      assertTrue(iter.hasNext());
      assertEquals(a, iter.next());
      assertTrue(iter.hasNext());
      assertEquals(b, iter.next());
      list.addTail(d, 5);
      assertTrue(iter.hasNext());
      assertEquals(d, iter.next());
   }

   @Test
   public void testMixupIterator2() {
      list.addTail(c, 5);

      list.addTail(k, 0);

      list.addTail(a, 2);
      list.addTail(b, 2);

      LinkedListIterator<Wibble> iter = list.iterator();

      assertTrue(iter.hasNext());
      assertEquals(c, iter.next());
      iter.remove();

      assertTrue(iter.hasNext());
      assertEquals(a, iter.next());
      iter.remove();

      assertTrue(iter.hasNext());
      assertEquals(b, iter.next());
      iter.remove();

      assertTrue(iter.hasNext());
      assertEquals(k, iter.next());
      iter.remove();

      list.addTail(d, 2);

      assertTrue(iter.hasNext());
      assertEquals(d, iter.next());
      iter.remove();
   }


   @Test
   public void testPeek() {
      assertNull(list.peek());

      list.addTail(c, 5);
      assertEquals(c, list.peek());

      list.addTail(k, 0);
      assertEquals(k, list.peek());

      list.addHead(a, 0);
      assertEquals(a, list.peek());
   }


   @Test
   public void testRemoveWithID() {

      for (int i = 1; i <= 3000; i++) {
         list.addHead(new Wibble("" + i, i), i % 10);
      }

      class WibbleNodeStore implements NodeStore<Wibble> {
         LongObjectHashMap<LinkedListImpl.Node<Wibble>> list = new LongObjectHashMap<>();

         @Override
         public void storeNode(Wibble element, LinkedListImpl.Node<Wibble> node) {
            list.put(element.id, node);
         }

         @Override
         public LinkedListImpl.Node<Wibble> getNode(String listID, long id) {
            return list.get(id);
         }

         @Override
         public void removeNode(Wibble element, LinkedListImpl.Node<Wibble> node) {
            list.remove(element.id);
         }

         @Override
         public void clear() {
            list.clear();
         }

         @Override
         public int size() {
            return list.size();
         }
      }

      list.setNodeStore(new WibbleNodeStore());

      // remove every 3rd
      for (int i = 3; i <= 3000; i += 3) {
         Assert.assertEquals(new Wibble("" + i, i), list.removeWithID("", i));
      }

      Assert.assertEquals(2000, list.size());

      Iterator<Wibble> iterator = list.iterator();

      HashSet<String> values = new HashSet<>();
      while (iterator.hasNext()) {
         values.add(iterator.next().s1);
      }

      Assert.assertEquals(2000, values.size());


      for (int i = 1; i <= 3000; i += 3) {
         if (i % 3 == 0) {
            Assert.assertFalse(values.contains("" + i));
         } else {
            Assert.assertTrue(values.contains("" + i));
         }
      }


   }

   static class Wibble {

      String s1;
      long id;

      Wibble(final String s, long id) {
         this.s1 = s;
         this.id = id;
      }

      @Override
      public String toString() {
         return s1;
      }

      @Override
      public boolean equals(Object o) {
         if (this == o)
            return true;
         if (o == null || getClass() != o.getClass())
            return false;
         Wibble wibble = (Wibble) o;
         return Objects.equals(s1, wibble.s1);
      }

      @Override
      public int hashCode() {
         return Objects.hash(s1);
      }
   }

}