Solved

Testing Circular Array Queue Implementation -- Creating a Driver Class to Test Circular Properties

Posted on 2008-10-12
7
3,178 Views
Last Modified: 2013-11-23
I'm in the process of implementing a circular queue that uses a generic array. To my knowledge, my implementation, while not the cleanest, correctly implements the circular function of the array queue.

 I've been able to successfully test that the size gets incremented when necessary and that the basic enqueue and dequeue function work; however, I can't seem to code up a Driver Class to test the circular properties of the ArrayQueue (mainly, if there is space at the front of the array, the enqueue method should add elements to the front position).

I've attached my code below, and any input on how to test the circular properties and/or if my Circular ArrayQueue implementation is actually correct would be great.
import java.util.*;
 

// Circular Array Queue Implementation Class

public class ArrayQueue<AnyType>{

	

	//Declare Fields

	public AnyType [] theQueue;

	private int theSize;

	private int front;

	private int back;

	

	//Array Queue Constructor

	public ArrayQueue (){

		theQueue = (AnyType[]) new Object [10];

		front = 0;

		back = -1;

		theSize = 0;		

	}

	

	// Enqueue method

	public void enqueue(AnyType obj)

	{

		

		// Conditional to increment size of queue 

		if (back==theQueue.length-1 && theSize==theQueue.length)

		{

			this.incrementArray();

			theSize ++;

			back++;

			theQueue[back] = obj;

		}

		

		// Conditional to find extra space at front of queue

		else if (back==theQueue.length-1 && theSize<theQueue.length)

		{

			back = 0;

			theSize ++;

			theQueue[back] = obj;

		}

		// Basic case

		else

		{

			theSize++;

			back++;

			theQueue[back] = obj;

		}

	}

	

	// Returns ture or false based on empty size

	public boolean isEmpty()

	{

		return (theSize==0);

	}

	

	// Dequeue Method

	public AnyType dequeue()

	{

		// Check size

		if (isEmpty())

			throw new NoSuchElementException("Empty Queue");

		theSize--;

		AnyType returnElement = theQueue[front];

		

		// Set front to initial value if space found

		if (front==theQueue.length)

		{

			front = 0;

			return returnElement;

		}

		front++;

		return returnElement;

	}

	

	// Internal method to increment the size of the queue

	private void incrementArray()

	{

		int newLength = theQueue.length*2;

		AnyType [] theNewQueue = (AnyType[]) new Object [newLength];

		

		// Copy values over

		for (int i=0; i<=back; i++)

		{

			theNewQueue[i] = theQueue[i];

		}

		

		theQueue = theNewQueue;

		

	}

	

	// Testing purposes to return length

	public int test ()

	{

		return theQueue.length;

	}

	

	// Driver class

	public static void main(String[] args) {

		

		// Create new queue

		ArrayQueue<Integer> array = new ArrayQueue<Integer>();

		

		// Test increment size

		for (int i=0; i < 25; i++)

		{

			// Test enqueue method

			array.enqueue(i);

			System.out.print(i+" ");

		}

		System.out.println();

		

		// Test dequeue method

		array.dequeue();

		System.out.println(array.dequeue());

		

		// Print out length of queue to check if increment method is correct

		System.out.println(array.test());
 

	}

}

Open in new window

0
Comment
Question by:paid_tech
  • 4
  • 3
7 Comments
 
LVL 2

Expert Comment

by:themuppeteer
ID: 22700439
Hi there,
I don't want to spoil the fun (if you are exercising for school or so,please say so), but I just wanted to ask if you are fully aware of the fact that there is such in thing in java called the Queue interface with implementations LinkedList and PriorityQueue ? They work fine and you don't have to test them anymore ;)

br,
mark


http://users.telenet.be/free_quiz
0
 

Author Comment

by:paid_tech
ID: 22701388
hi Mark,

I was aware of that, and unfortunately this is an assignment for school, so I will not be able to use that. The implementation must strictly use an array. Any ideas on how to test to see if it works circularly (or if it works at all for that matter)?
0
 
LVL 2

Accepted Solution

by:
themuppeteer earned 500 total points
ID: 22704017
ok, I see.
I read http://cis.stvincent.edu/html/tutorials/swd/queues/queues.html to be better able to help you.

You are missing something in your current implementation. Major bug :) The incrementArray method is wrong.
Say my array is 5 long, I add 5 numbers and pop 1 off. Front will be 1 then (moving up a bit from 0->1) and back will be 4 (at the end) and length will be 4. If we add a number now, that number will be on index 0 in our array and back will point to this. Great. But what if we add more numbers now ? The increment array will make me a bigger array but then what ? Check that code.
 What you have to do in incremenArray is do a clean copy to the new array, so
if first< back copy from first to back in the new array starting at 0
if first > back copy from first to (end of origQueue) to the new queue and then from 0 to back after that in your new queue.
in both cases, also make first=0 and back= size-1

Right now your not doing that.

But how to test it.
First of all I would use JUnit for that. Testing with System.out is not testing.It is really easy and you'll need it on the job anyway so it is not wasted time (in eclipse new->junit test case)
Then you need to:

*Test if you add objects the length increments.
*Test if you add X objects you can pop them off again and they are the same (create a queue of 5, create a test array of 20, add random numbers in the test array but you should hard code them, a test should always run the same. Then enqueue the test array to the queue and dequeue them again while checking against the test array). The poped of objects should == those in the test array.
* Test if your queue is valid. It is valid when
in pseudo code here is what should be:

first<back{
 first+number of items in queue = back
}

if first ==back you have a problem

if first>back
{
    (array size - first) + back = number of items in queue
}

hope this helps.

grtz
mark

0
Threat Intelligence Starter Resources

Integrating threat intelligence can be challenging, and not all companies are ready. These resources can help you build awareness and prepare for defense.

 

Author Comment

by:paid_tech
ID: 22705705
thanks for your input mark--i've started to reconstruct my code based on your advice.

however, I don't really understand how to set up a JUnit Test case and actually test the queue. could you please elaborate on how to set that up?
0
 
LVL 2

Expert Comment

by:themuppeteer
ID: 22709070
first of all, I would strongly suggest to use eclipse ide for development (its free and great http://update.eclipse.org/downloads/drops/R-3.4-200806172000/index.php)

what you need:
1) you need a class to test :)
2) you need to download junit (http://www.brothersoft.com/d.php?soft_id=69027&url=http%3A%2F%2Ffiles.brothersoft.com%2Fdevelopment%2Fmisc_software_development%2Fjunit4.5.zip)
3) you need to create a new class that will test the other one
4) compile with junit jar on classpath and run the test the same way

Basically what you do in a test is create an instance of the object you want to test (e.g. a calculator), put in some data (add 5 and 3) and call junit test methods like assertEquals(expected, result); (so assertEquals(calculator.add(5,3),8) ) to check your object. If for some reason the calculator malfunctions, you'll notice.
Then everytime you (or the testing departement) find a bug in your code, you first create a new test case that reproduces the bug (and fails for that reason) and then you fix the code and the test should succeed too.

but you there is plenty of info available on the net to do this.  look at:
http://www.comscigate.com/junit/learn_JUnit.htm
http://www.cavdar.net/2008/07/21/junit-4-in-60-seconds/

you'll have to play a bit with in it but it shouldn't take you too long to get something working.

good luck
mark
0
 

Author Closing Comment

by:paid_tech
ID: 31505523
Mark, you were very helpful. It took me a while, but based on your input I was able to fix the bugs in my problem. I still haven't figured out how to use JUnit, but I figure I can do that on my own time. I do use Eclipse as my IDE, so I will keep looking into it.

Thanks again!
0
 
LVL 2

Expert Comment

by:themuppeteer
ID: 22743219
Glad it was helpful :)


I've created a small and simple JUNIT tutorial to get you started. You can find it here:

http://users.telenet.be/free_quiz/scjp/junit_tutorial.htm


I hope it gets you started!



grtz
mark
0

Featured Post

IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

Join & Write a Comment

This was posted to the Netbeans forum a Feb, 2010 and I also sent it to Verisign. Who didn't help much in my struggles to get my application signed. ------------------------- Start The idea here is to target your cell phones with the correct…
Java Flight Recorder and Java Mission Control together create a complete tool chain to continuously collect low level and detailed runtime information enabling after-the-fact incident analysis. Java Flight Recorder is a profiling and event collectio…
Viewers learn about the “while” loop and how to utilize it correctly in Java. Additionally, viewers begin exploring how to include conditional statements within a while loop and avoid an endless loop. Define While Loop: Basic Example: Explanatio…
This video teaches viewers about errors in exception handling.

747 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now