A Queue of Cards Understand the Problem You are going to parallel the developmen
ID: 3843068 • Letter: A
Question
A Queue of Cards
Understand the Problem
You are going to parallel the development done in a past lesson on inheritance where we constructed some base classes, StackNode and Stack, and derived FloatNode and FloatStack from them. You can work best by referring to those modules all through the development of your program. These are the differences between what we did in the lesson and what you will do for your assignment.
Instead of a Stack data structure, you will create a Queue data structure. A Stack is last-in-first-out (LIFO). A Queue is first-in-first-out (FIFO). We'll use add() and remove(), instead of push() and pop(), as the names of our primary accessors.
Instead of deriving a FloatNode from the basic Node class, you will derive a CardNode from our Node. CardNode will use the given Card class(Look at the bottom)
Instead of signaling a pop() error by returning a special value (STACK_EMPTY = Float.MIN_VALUE), we will be more sophisticated and throw our own home-made QueueEmptyException in our remove() method. The client will catch it.
We will replace all instances of show() with the more professional toString(), and let only the client send results to the display.
Picturing Queues
The head member of Queue will, be the first or oldest Node in the queue, and it is the will be the least recent one added. The tail will always point to the most recent one added to the end of the Queue. Say we have added Nodes N1, N2, N3 and N4, in that order. The Nodes would be linked (in your Queue) as follows:
The links of the next pointers look like the StackNode organization, with head and tail sharing the role of our old top:
head N1 N2 N3 N4 null
The tail pointer, not shown above, points to N4
head N1 N2 N3 N4 tail
If we instantiated a new Node N5, and added it onto the Queue q, it would go in at the tail, Here is the Queue, q, after a q.Add(N5);
A couple links have to be changed to result in:
head N1 N2 N3 N4 N5 null
Note: the tail has to be adjusted:
head N1 N2 N3 N4 N5 tail
If we then removed an item from the Queue, using q.Remove(), the picture would be:
The links now convey the following:
head N2 N3 N4 N5 null
Note, the tail may not have to be adjusted (but in one case, not shown, it will):
head N2 N3 N4 N5 tail
Of course, when you do this, you will only be changing a couple pointers in each operation (either near the tail or near the head). Most of the nodes don't need to be touched in add() and remove().
Phase 1: Base Classes Node and Queue
Base Class Node
You can use the same class for a base class that was used in the modules. However, I want you to give this class a different name. Call it Node (not QueueNode or StackNode, just Node). Also, take heed to replace show() methods with toString() methods.
Base Class Queue
Next, do almost the same thing as we did with the Stack class, except make sure that this class works like a Queue, not a Stack. That means
We add items to the Queue using add() not push(). push() does not appear in our Queue class.
We retrieve items from the Queue using remove() not pop(). pop() does not appear in our Queue class.
remove() removes and returns the oldest item in the Queue. This is different from pop() which removed and returned the youngest item in the Queue.
remove() throws a QueueEmptyException exception if the queue is empty. You will define this exception.
Provide a toString() method produces a String of all the items in the Queue from oldest to youngest.
Instead of one Node pointer member, top, you'll need two Node pointer members, and neither should be called top (since top is not meaningful in a Queue). Examples are head/tail, front/back, oldest/youngest, etc. Select two names and use them accordingly.
Phase 2: Intermediate Step - Check Your Base Classes
Once you have written these two classes, write a simple test main() just like I did in the modules - show a run that displays some (generic node)s. Test the Queue's toString() method and also build a simple loop in your main() to remove and display nodes as they are removed. Compare the output of these two techniques -- they should be similar. You will not hand this in. It is just for your use in developing the full program. Test your QueueEmptyException.
add() and remove() will be slightly more complicated than push() and pop() because you have two pointers, front and back (or head and tail, or whatever you call them) to manage. This may take some time and debugging. Test it carefully. Even after you get it to work, you may find that it still needs debugging later, since your "(generic node)" screen results won't tell you if things are coming off in the correct order. You won't know that until you have real data in your Nodes. That's the next part.
Phase 3: Derived Classes CardNode and CardQueue
Deriving from Node
Now comes the fun. Derive a class from Node, CardNode. This will contain one additional member, just like the FloatNode did. However, instead of that additional member being a float it will be a Card. For this, you'll need to include the Card class of the first or second week.
Override the toString() method of the generic Node class to return the specific type of data. The important thing here is to not do any work - you let your Card class stringize itself through its, already defined, toString() method.
Deriving from Queue
Derive CardQueue from Queue, and, just like we did in the modules, write methods that let you add actual Cards onto each of the Queue.
In your client, add() a bunch of cards, toString() the queue to the screen to see that this is working, then in a loop, remove() items displaying them as you do. Go "too far" so that you attempt to remove() from an empty queue and see that you are catching the exception.
Do not use collections or generics for this assignment. You are being asked to create your own data structures exactly as I did in the lesson.
class Card {
// type and constants
public enum Suit {
clubs, diamonds, hearts, spades
}
static char DEFAULT_VAL = 'A';
static Suit DEFAULT_SUIT = Suit.spades;
// private data
private char value;
private Suit suit;
private boolean errorFlag;
// 4 overloaded constructors
public Card(char value, Suit suit) { // because mutator sets errorFlag, we
// don't have to test
set(value, suit);
}
public Card(char value) {
this(value, DEFAULT_SUIT);
}
public Card() {
this(DEFAULT_VAL, DEFAULT_SUIT);
}
// copy constructor
public Card(Card card) {
this(card.value, card.suit);
}
// mutators
public boolean set(char value, Suit suit) {
char upVal; // for upcasing char
// convert to uppercase to simplify
upVal = Character.toUpperCase(value);
if (!isValid(upVal, suit)) {
errorFlag = true;
return false;
}
// else implied
errorFlag = false;
this.value = upVal;
this.suit = suit;
return true;
}
// accessors
public char getVal() {
return value;
}
public Suit getSuit() {
return suit;
}
public boolean getErrorFlag() {
return errorFlag;
}
// stringizer
public String toString() {
String retVal;
if (errorFlag)
return "** illegal **";
// else implied
retVal = String.valueOf(value);
retVal += " of ";
retVal += String.valueOf(suit);
return retVal;
}
// helper
private static boolean isValid(char value, Suit suit) {
// don't need to test suit (enum), but leave in for clarity
char upVal; // string to hold the 1-char value
String legalVals = "23456789TJQKA";
// convert to uppercase to simplify (need #include <cctype>)
upVal = Character.toUpperCase(value);
// check for validity
if (legalVals.indexOf(upVal) >= 0)
return true;
else
return false;
}
public boolean equals(Card card) {
if (this.value != card.value)
return false;
if (this.suit != card.suit)
return false;
if (this.errorFlag != card.errorFlag)
return false;
return true;
}
}
Explanation / Answer
/* OptionA.java */
import java.lang.Exception;
/* OptionA class */
public class OptionA
{
/* main */
public static void main(String[] args)
{
/* creating lines */
lineCreation(80, "*");
/* creating cards */
System.out.println("Create Cards");
/* Ten */
MyCard c0 = new MyCard('T', MyCard.mySuit.spade);
/* Jack */
MyCard c1 = new MyCard('J', MyCard.mySuit.club);
/* Queen */
MyCard c2 = new MyCard('Q', MyCard.mySuit.diamond);
/* King */
MyCard c3 = new MyCard('K', MyCard.mySuit.heart);
/* Joker */
MyCard c4 = new MyCard('A', MyCard.mySuit.spade);
lineCreation(80, "*");
System.out.println("Adding Cards 2 myCardQueue");
myCardQueue cqObj = new myCardQueue();
cqObj.addCard(c0);
cqObj.addCard(c1);
cqObj.addCard(c2);
cqObj.addCard(c3);
cqObj.addCard(c4);
lineCreation(80, "*");
System.out.println("Display the complete queue:");
/* Displays the complete queue */
System.out.println(cqObj.toString());
lineCreation(80, "*");
System.out.println("Deleting cards 1 by 1, while displaying the "
+ "returned card. Deleting cards for 10 times:");
/* deleting the cards */
for (int inc = 0; inc < 10; inc++)
{
try
{
System.out.println(cqObj.removeCard());
}
catch (ExceptionQueueEmpty e)
/* catching error */
{
System.out.println("[Catched an exception]");
}
}
lineCreation(80, "*");
System.out.println("Program ends now!");
lineCreation(80, "*");
}
/* method lineCreation */
private static void lineCreation(int len, String type)
{
for (int inc = 0; inc < len; inc += 1)
{
System.out.print(type);
}
}
}
/* myNode class*/
class myNode
{
/* member variable*/
protected myNode next;
/* constructor */
public myNode()
{
next = null;
}
/* return string */
public String toString()
{
return "[Node] ";
}
}
/* myQueue class */
class myQueue
{
/* pointer to the first node */
private myNode head;
private myNode tail;
/* constructor */
myQueue()
{
head = null;
tail = null;
}
/* method addNode */
public boolean addNode(myNode mynewNode)
{
if (mynewNode == null)
return false;
if (head == null)
{
head = mynewNode;
tail = mynewNode;
}
tail.next = mynewNode;
tail = mynewNode;
return true;
}
/* method removeNode */
public myNode removeNode() throws ExceptionQueueEmpty
{
/* creating a temp node */
myNode mytempNode;
mytempNode = head;
if (head != null)
{
head = head.next;
mytempNode.next = null;
}
else
{
/* throwing an exception if queue node is null */
throw new ExceptionQueueEmpty();
}
/* returns previous headnode */
return mytempNode;
}
/* toString method */
public String toString()
{
myNode mynodes;
StringBuilder sbObj = new StringBuilder();
for (mynodes = head; mynodes != null; mynodes = mynodes.next)
{
sbObj.append(mynodes.toString());
}
return sbObj.toString();
}
}
/* ExceptionQueueEmpty class */
class ExceptionQueueEmpty extends Exception
{
ExceptionQueueEmpty()
{
super("Queue Empty");
}
}
/* myCardNode class */
class myCardNode extends myNode
{
/* variables */
private MyCard mycard;
/* constructor */
myCardNode(char myValue, MyCard.mySuit mysuit)
{
super();
mycard = new MyCard(myValue, mysuit);
}
/* Accessors */
public MyCard getmyCard()
{
return mycard;
}
/* method toString */
public String toString()
{
return mycard.toString() + " ";
}
}
/* myCardQueue class an extension of myQueue class*/
class myCardQueue extends myQueue
{
myCardQueue()
{
super();
}
/* method addCard */
public void addCard(char myValue, MyCard.mySuit mysuit)
{
myCardNode cNode = new myCardNode(myValue, mysuit);
super.addNode(cNode);
}
/* method addCard */
public void addCard(MyCard mycard)
{
this.addCard(mycard.getmyVal(), mycard.getmySuit());
}
/* method removeCard */
public MyCard removeCard() throws ExceptionQueueEmpty
{
myCardNode cNode = (myCardNode) removeNode();
return cNode.getmyCard();
}
}
/* class MyCard */
class MyCard
{
public enum myState
{
removed, alive
}
public enum mySuit
{
club, diamond, heart, spade
}
/* for sorting */
public static char[] valueRank =
{ '2', '3', '4', '5', '6', '7', '8', '9', 'T', 'J', 'Q', 'K', 'A', 'Z' };
static mySuit[] suitRanks =
{ mySuit.club, mySuit.diamond, mySuit.heart, mySuit.spade };
static int numOrder = 13;
/* private variables */
private char myValue;
private mySuit mysuit;
myState mystate;
boolean errFlag;
/* overloaded constructors */
public MyCard(char myValue, mySuit mysuit)
{
set(myValue, mysuit);
}
public MyCard(char myValue)
{
this(myValue, mySuit.spade);
}
public MyCard()
{
this('E', mySuit.spade);
}
/* copy constructor */
public MyCard(MyCard mycard)
{
this(mycard.myValue, mycard.mysuit);
}
/* mutator */
public boolean set(char myValue, mySuit mysuit)
{
char up;
this.mysuit = mysuit;
up = Character.toUpperCase(myValue);
if (up == 'A' || up == 'K' || up == 'Q' || up == 'J'
|| up == 'T' || up == 'Z' || (up >= '2' && up <= '9'))
{
errFlag = false;
mystate = myState.alive;
this.myValue = up;
}
else
{
errFlag = true;
return false;
}
return !errFlag;
}
public void setState(myState mystate)
{
this.mystate = mystate;
}
/* accessors */
public char getmyVal()
{
return myValue;
}
public mySuit getmySuit()
{
return mysuit;
}
public myState getmyState()
{
return mystate;
}
public boolean getErrFlag()
{
return errFlag;
}
public String toString()
{
String rVal;
if (errFlag)
return "Not legal";
if (mystate == myState.removed)
return "( removed )";
if (myValue != 'Z')
{
rVal = String.valueOf(myValue);
rVal += " of ";
rVal += String.valueOf(mysuit);
}
else
{
rVal = "joker";
if (mysuit == mySuit.club)
rVal += " 1";
else if (mysuit == mySuit.diamond)
rVal += " 2";
else if (mysuit == mySuit.heart)
rVal += " 3";
else if (mysuit == mySuit.spade)
rVal += " 4";
}
return rVal;
}
public boolean equals(MyCard mycard)
{
if (this.myValue != mycard.myValue)
return false;
if (this.mysuit != mycard.mysuit)
return false;
if (this.errFlag != mycard.errFlag)
return false;
if (this.mystate != mycard.mystate)
return false;
return true;
}
public int compareTo(MyCard others)
{
if (this.myValue == others.myValue)
return (getSuitRanks(this.mysuit) - getSuitRanks(others.mysuit));
return (getValueRanks(this.myValue) - getValueRanks(others.myValue));
}
public static void setRankOrder(char[] valueOrder, mySuit[] suitOrder,
int numOrder)
{
int inc;
if (numOrder < 0 || numOrder > 13)
return;
MyCard.numOrder = numOrder;
for (inc = 0; inc < numOrder; inc++)
MyCard.valueRank[inc] = valueOrder[inc];
for (inc = 0; inc < 4; inc++)
MyCard.suitRanks[inc] = suitOrder[inc];
}
public static int getSuitRanks(mySuit st)
{
int inc;
for (inc = 0; inc < 4; inc++)
if (suitRanks[inc] == st)
return inc;
return 0;
}
public static int getValueRanks(char val)
{
int inc;
for (inc = 0; inc < numOrder; inc++)
if (valueRank[inc] == val)
return inc;
return 0;
}
public static void arrSort(MyCard[] array, int arraySiz)
{
for (int inc = 0; inc < arraySiz; inc++)
if (!floatLargeToTop(array, arraySiz - 1 - inc))
return;
}
private static boolean floatLargeToTop(MyCard[] array, int top)
{
boolean change = false;
MyCard tmp;
for (int inc = 0; inc < top; inc++)
if (array[inc].compareTo(array[inc + 1]) > 0)
{
tmp = array[inc];
array[inc] = array[inc + 1];
array[inc + 1] = tmp;
change = true;
};
return change;
}
}