Back to Repositories

Testing LongQueue Data Structure Operations in LibGDX

This test suite provides comprehensive validation of the LongQueue data structure implementation in LibGDX, covering queue operations, resizing behavior, and data integrity. The tests verify both FIFO and LIFO operations along with edge cases and queue manipulation methods.

Test Coverage Overview

The test suite provides extensive coverage of LongQueue functionality including:

Basic queue operations (addFirst, addLast, removeFirst, removeLast)
Dynamic resizing capabilities
Index-based access and manipulation
Queue state validation
Edge cases handling for empty and full queues

Implementation Analysis

The testing approach employs JUnit to validate the LongQueue implementation through systematic test cases. Each test method focuses on specific queue operations, using assertion-based verification to ensure correct behavior. The test structure follows a clear pattern of setup, operation, and verification phases.

Key testing patterns include iterative testing with size validation, boundary testing, and state verification after operations.

Technical Details

Testing infrastructure includes:

JUnit 4 framework for test execution
Custom assertion utilities for queue validation
Systematic test organization with @Test annotations
Helper methods for queue state verification
Clear test isolation with new queue instances per test

Best Practices Demonstrated

The test suite exemplifies strong testing practices including:

Comprehensive edge case coverage
Isolated test cases with clear purpose
Consistent state validation
Helper methods for common assertions
Clear test naming conventions
Thorough documentation of test scenarios

libgdx/libgdx

gdx/test/com/badlogic/gdx/utils/LongQueueTest.java

            

package com.badlogic.gdx.utils;

import static org.junit.Assert.*;

import org.junit.Assert;
import org.junit.Test;

public class LongQueueTest {
	@Test
	public void addFirstAndLastTest () {
		LongQueue queue = new LongQueue();
		queue.addFirst(1);
		queue.addLast(2);
		queue.addFirst(3);
		queue.addLast(4);

		assertEquals(0, queue.indexOf(3));
		assertEquals(1, queue.indexOf(1));
		assertEquals(2, queue.indexOf(2));
		assertEquals(3, queue.indexOf(4));
	}

	@Test
	public void removeLastTest () {
		LongQueue queue = new LongQueue();
		queue.addLast(1);
		queue.addLast(2);
		queue.addLast(3);
		queue.addLast(4);

		assertEquals(4, queue.size);
		assertEquals(3, queue.indexOf(4));
		assertEquals(4, queue.removeLast());

		assertEquals(3, queue.size);
		assertEquals(2, queue.indexOf(3));
		assertEquals(3, queue.removeLast());

		assertEquals(2, queue.size);
		assertEquals(1, queue.indexOf(2));
		assertEquals(2, queue.removeLast());

		assertEquals(1, queue.size);
		assertEquals(0, queue.indexOf(1));
		assertEquals(1, queue.removeLast());

		assertEquals(0, queue.size);
	}

	@Test
	public void removeFirstTest () {
		LongQueue queue = new LongQueue();
		queue.addLast(1);
		queue.addLast(2);
		queue.addLast(3);
		queue.addLast(4);

		assertEquals(4, queue.size);
		assertEquals(0, queue.indexOf(1));
		assertEquals(1, queue.removeFirst());

		assertEquals(3, queue.size);
		assertEquals(0, queue.indexOf(2));
		assertEquals(2, queue.removeFirst());

		assertEquals(2, queue.size);
		assertEquals(0, queue.indexOf(3));
		assertEquals(3, queue.removeFirst());

		assertEquals(1, queue.size);
		assertEquals(0, queue.indexOf(4));
		assertEquals(4, queue.removeFirst());

		assertEquals(0, queue.size);
	}

	@Test
	public void resizableQueueTest () {
		final LongQueue q = new LongQueue(8);

		assertTrue("New queue is not empty!", q.size == 0);

		for (int i = 0; i < 100; i++) {

			for (int j = 0; j < i; j++) {
				try {
					q.addLast(j);
				} catch (IllegalStateException e) {
					fail("Failed to add element " + j + " (" + i + ")");
				}
				final long peeked = q.last();
				assertTrue("peekLast shows " + peeked + ", should be " + j + " (" + i + ")", peeked == j);
				final int size = q.size;
				assertTrue("Size should be " + (j + 1) + " but is " + size + " (" + i + ")", size == j + 1);
			}

			if (i != 0) {
				final long peek = q.first();
				assertTrue("First thing is not zero but " + peek + " (" + i + ")", peek == 0);
			}

			for (int j = 0; j < i; j++) {
				final long pop = q.removeFirst();
				assertTrue("Popped should be " + j + " but is " + pop + " (" + i + ")", pop == j);

				final int size = q.size;
				assertTrue("Size should be " + (i - 1 - j) + " but is " + size + " (" + i + ")", size == i - 1 - j);
			}

			assertTrue("Not empty after cycle " + i, q.size == 0);
		}

		for (int i = 0; i < 56; i++) {
			q.addLast(42);
		}
		q.clear();
		assertTrue("Clear did not clear properly", q.size == 0);
	}

	/** Same as resizableQueueTest, but in reverse */
	@Test
	public void resizableDequeTest () {
		final LongQueue q = new LongQueue(8);

		assertTrue("New deque is not empty!", q.size == 0);

		for (int i = 0; i < 100; i++) {

			for (int j = 0; j < i; j++) {
				try {
					q.addFirst(j);
				} catch (IllegalStateException e) {
					fail("Failed to add element " + j + " (" + i + ")");
				}
				final long peeked = q.first();
				assertTrue("peek shows " + peeked + ", should be " + j + " (" + i + ")", peeked == j);
				final int size = q.size;
				assertTrue("Size should be " + (j + 1) + " but is " + size + " (" + i + ")", size == j + 1);
			}

			if (i != 0) {
				final long peek = q.last();
				assertTrue("Last thing is not zero but " + peek + " (" + i + ")", peek == 0);
			}

			for (int j = 0; j < i; j++) {
				final long pop = q.removeLast();
				assertTrue("Popped should be " + j + " but is " + pop + " (" + i + ")", pop == j);

				final int size = q.size;
				assertTrue("Size should be " + (i - 1 - j) + " but is " + size + " (" + i + ")", size == i - 1 - j);
			}

			assertTrue("Not empty after cycle " + i, q.size == 0);
		}

		for (int i = 0; i < 56; i++) {
			q.addFirst(42);
		}
		q.clear();
		assertTrue("Clear did not clear properly", q.size == 0);
	}

	@Test
	public void getTest () {
		final LongQueue q = new LongQueue(7);
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < 4; j++) {
				q.addLast(j);
			}
			assertEquals("get(0) is not equal to peek (" + i + ")", q.get(0), q.first());
			assertEquals("get(size-1) is not equal to peekLast (" + i + ")", q.get(q.size - 1), q.last());
			for (int j = 0; j < 4; j++) {
				assertTrue(q.get(j) == j);
			}
			for (int j = 0; j < 4 - 1; j++) {
				q.removeFirst();
				assertEquals("get(0) is not equal to peek (" + i + ")", q.get(0), q.first());
			}
			q.removeFirst();
			assert q.size == 0; // Failing this means broken test
			try {
				q.get(0);
				fail("get() on empty queue did not throw");
			} catch (IndexOutOfBoundsException ignore) {
				// Expected
			}
		}
	}

	@Test
	public void removeTest () {
		final LongQueue q = new LongQueue();

		// Test head < tail.
		for (int j = 0; j <= 6; j++)
			q.addLast(j);
		assertValues(q, 0, 1, 2, 3, 4, 5, 6);
		q.removeIndex(0);
		assertValues(q, 1, 2, 3, 4, 5, 6);
		q.removeIndex(1);
		assertValues(q, 1, 3, 4, 5, 6);
		q.removeIndex(4);
		assertValues(q, 1, 3, 4, 5);
		q.removeIndex(2);
		assertValues(q, 1, 3, 5);

		// Test head >= tail and index >= head.
		q.clear();
		for (int j = 2; j >= 0; j--)
			q.addFirst(j);
		for (int j = 3; j <= 6; j++)
			q.addLast(j);
		assertValues(q, 0, 1, 2, 3, 4, 5, 6);
		q.removeIndex(1);
		assertValues(q, 0, 2, 3, 4, 5, 6);
		q.removeIndex(0);
		assertValues(q, 2, 3, 4, 5, 6);

		// Test head >= tail and index < tail.
		q.clear();
		for (int j = 2; j >= 0; j--)
			q.addFirst(j);
		for (int j = 3; j <= 6; j++)
			q.addLast(j);
		assertValues(q, 0, 1, 2, 3, 4, 5, 6);
		q.removeIndex(5);
		assertValues(q, 0, 1, 2, 3, 4, 6);
		q.removeIndex(5);
		assertValues(q, 0, 1, 2, 3, 4);
	}

	@Test
	public void indexOfTest () {
		final LongQueue q = new LongQueue();

		// Test head < tail.
		for (int j = 0; j <= 6; j++)
			q.addLast(j);
		for (int j = 0; j <= 6; j++)
			assertEquals(q.indexOf(j), j);

		// Test head >= tail.
		q.clear();
		for (int j = 2; j >= 0; j--)
			q.addFirst(j);
		for (int j = 3; j <= 6; j++)
			q.addLast(j);
		for (int j = 0; j <= 6; j++)
			assertEquals(q.indexOf(j), j);
	}

	@Test
	public void toStringTest () {
		LongQueue q = new LongQueue(1);
		assertTrue(q.toString().equals("[]"));
		q.addLast(4);
		assertTrue(q.toString().equals("[4]"));
		q.addLast(5);
		q.addLast(6);
		q.addLast(7);
		assertTrue(q.toString().equals("[4, 5, 6, 7]"));
	}

	@Test
	public void hashEqualsTest () {
		LongQueue q1 = new LongQueue();
		LongQueue q2 = new LongQueue();

		assertEqualsAndHash(q1, q2);
		q1.addFirst(1);
		assertNotEquals(q1, q2);
		q2.addFirst(1);
		assertEqualsAndHash(q1, q2);

		q1.clear();
		q1.addLast(1);
		q1.addLast(2);
		q2.addLast(2);
		assertEqualsAndHash(q1, q2);

		for (int i = 0; i < 100; i++) {
			q1.addLast(i);
			q1.addLast(i);
			q1.removeFirst();

			assertNotEquals(q1, q2);

			q2.addLast(i);
			q2.addLast(i);
			q2.removeFirst();

			assertEqualsAndHash(q1, q2);
		}
	}

	private void assertEqualsAndHash (LongQueue q1, LongQueue q2) {
		assertEquals(q1, q2);
		assertEquals("Hash codes are not equal", q1.hashCode(), q2.hashCode());
	}

	private void assertValues (LongQueue q, long... values) {
		for (int i = 0, n = values.length; i < n; i++) {
			Assert.assertEquals(values[i], q.get(i));
		}
	}
}