Solved

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

Posted on 2008-10-12
7
3,190 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
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 

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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Java asynchronous logging 4 50
get weblogic logged in user in java 2 58
Need to track down Infection in a Server 2008 domain user profile 7 48
servlet doXXX methods 3 37
The greatest common divisor (gcd) of two positive integers is their largest common divisor. Let's consider two numbers 12 and 20. The divisors of 12 are 1, 2, 3, 4, 6, 12 The divisors of 20 are 1, 2, 4, 5, 10 20 The highest number among the c…
Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approac…
Viewers learn about the “for” loop and how it works in Java. By comparing it to the while loop learned before, viewers can make the transition easily. You will learn about the formatting of the for loop as we write a program that prints even numbers…
This video teaches viewers about errors in exception handling.

920 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

12 Experts available now in Live!

Get 1:1 Help Now