Shuffle
A.First Edition
This is my first edition of assignment of shuffle which is quite different from what I write by myself before
which is a dealing program.
The problem is to use the methods specified in the base abstract class List which implemented in two derived class
---AList, LList. They are array-based and linklist-based implementation class.
กก
//program features: //1. The header file given by book has one problem, that is, the AList.h and LList.h // both has a "DefaultListSize" as default parameter for constructor which is not // defined in their abastract base class----List. So, I arbitrarily add // const int DefaultListSize = 52 in List.h. //2. In order for a better representation, I defined a helper class "Card" which stores // the suit and value information of a card. Since the List "print" function will use // "cout<<element" to printout element. This Card class has implement a friend function // to overload operator <<. And because I use pointer "Card*" instead of object "Card" // as element in AList and LList, I have to overload "ostream& operator<<(ostream&, Card*)". //3. Shuffle is the major class to handle shuffling. Its private data includes both AList and // LList lists. Basically I need to four lists to do shuffling: // a) a source list, which stores the original data to be shuffled. // b) a target list, which stores the result data. // c) one left and one right list to store the left and right half of source list. // Since AList and LList are all inherited from List, I can use base class pointer to // do the same job. So I also need four pointer of List: // a) a pointer pointing to source list---pSource; // b) a pointer pointing to target list---pTarget; // c) two pointer pointing to left and right list---pLeft, pRight; //4. Within the Shuffle there is a Card array cards[52] which stores all 52 cards. The List // don't have to store the Card object itself, instead store its pointer Card*. So my AList // and LList is of type of AList<Card*> and LList<Card*>. Suppose this element Card is a // complicated class with many data inside, its pointer will be much lighter to store. //5. In the main function, I simply pass a flag to indicate whether I need to use array-based // List or LinkList-based List implementation to function "shuffling(ListType theType);". // All other code don't have to modify and it will output almost same with different List // implementation to indicate that my program is implementation independent! So, the input // of program is as simple as changing a single parameter in main function and call the // function "shuffling" again which will automatically initialize and doShuffle. //6. function "shuffling" will call function "doShuffle" several times before it initialize // all parameters and divide the original source list into "left" and "right" by copying. //7. function "doShuffle" is using base class pointer, so it is totally List-implementation- // independent which means the code is uniform disregarding the type of List. /////////////////////////////////////////////////////////////////////////////////////////////
C.Further improvement
กก
//List.h The base abstract class
#ifndef LIST_H #define LIST_H // List abstract class const int DefaultListSize=52; template <class Elem> class List { public: // Reinitialize the list. The client is responsible for // reclaiming the storage used by the list elements. virtual void clear() = 0; // Insert an element at the front of the right partition. // Return true if successful, false if the list is full. virtual bool insert(const Elem&) = 0; // Append an element at the end of the right partition. // Return true if successful, false if the list is full. virtual bool append(const Elem&) = 0; // Remove the first element of right partition. Return // true if successful, false if right partition is empty. // The element removed is returned in the parameter. virtual bool remove(Elem&) = 0; // Place fence at list start, making left partition empty virtual void setStart() = 0; // Place fence at list end, making right partition empty virtual void setEnd() = 0; // Move fence one step left; no change if already at start virtual void prev() = 0; // Move fence one step right; no change if already at end virtual void next() = 0; // Return length of left partition virtual int leftLength() const = 0; // Return length of right partition virtual int rightLength() const = 0; // If pos or more elements are in the list, set the size // of left partition to pos and return true. Otherwise, // do nothing and return false. virtual bool setPos(int pos) = 0; // Return in first parameter the first element of the // right partition. Return true if successful, false // if the right partition is empty. virtual bool getValue(Elem&) const = 0; // Print the contents of the list virtual void print() const = 0; }; #endif
กก
//AList.h The array-based derived class
#ifndef ALIST_H #define ALIST_H // This is the file to include in your code if you want access to the // complete AList template class // First, get the declaration for the base list class #include "list.h" template <class Elem> // Array-based list implementation class AList : public List<Elem> { private: int maxSize; // Maximum size of list int listSize; // Actual number of elements in list int fence; // Position of fence Elem* listArray; // Array holding list elements public: AList(int size=DefaultListSize) { // Constructor maxSize = size; listSize = fence = 0; listArray = new Elem[maxSize]; } ~AList() { delete [] listArray; } // Destructor void clear() { delete [] listArray; listSize = fence = 0; listArray = new Elem[maxSize]; } bool insert(const Elem&); bool append(const Elem&); bool remove(Elem&); void setStart() { fence = 0; } void setEnd() { fence = listSize; } void prev() { if (fence != 0) fence--; } void next() { if (fence <= listSize) fence++; } int leftLength() const { return fence; } int rightLength() const { return listSize - fence; } bool setPos(int pos) { if ((pos >= 0) && (pos <= listSize)) fence = pos; return (pos >= 0) && (pos <= listSize); } bool getValue(Elem& it) const { if (rightLength() == 0) return false; else { it = listArray[fence]; return true; } } void print() const { int temp = 0; cout << "< "; while (temp < fence) cout << listArray[temp++] << " "; cout << "| "; while (temp<listSize) cout << listArray[temp++] << " "; cout << ">\n"; } }; template <class Elem> // Insert at front of right partition bool AList<Elem>::insert(const Elem& item) { if (listSize == maxSize) return false; // List is full for(int i=listSize; i>fence; i--) // Shift Elems up listArray[i] = listArray[i-1]; // to make room listArray[fence] = item; listSize++; // Increment list size return true; } template <class Elem> // Append Elem to end of the list bool AList<Elem>::append(const Elem& item) { if (listSize == maxSize) return false; listArray[listSize++] = item; return true; } // Remove and return first Elem in right partition template <class Elem> bool AList<Elem>::remove(Elem& it) { if (rightLength() == 0) return false; // Nothing in right it = listArray[fence]; // Copy removed Elem for(int i=fence; i<listSize-1; i++) // Shift them down listArray[i] = listArray[i+1]; listSize--; // Decrement size return true; } #endif
//Link.h A helper class for linklist
#ifndef LINK_H #define LINK_H // Singly-linked list node template <class Elem> class Link { public: Elem element; // Value for this node Link *next; // Pointer to next node in list Link(const Elem& elemval, Link* nextval =NULL) { element = elemval; next = nextval; } Link(Link* nextval =NULL) { next = nextval; } }; #endif
//LList.h Linklist-based derived class
#ifndef LLIST_H #define LLIST_H // This is the file to include in your code if you want access to the // complete LList template class // First, get the declaration for the base list class #include "list.h" // Linked list implementation template <class Elem> class LList: public List<Elem> { private: Link<Elem>* head; // Pointer to list header Link<Elem>* tail; // Pointer to last Elem in list Link<Elem>* fence; // Last element on left side int leftcnt; // Size of left partition int rightcnt; // Size of right partition void init() { // Intialization routine fence = tail = head = new Link<Elem>; leftcnt = rightcnt = 0; } void removeall() { // Return link nodes to free store while(head != NULL) { fence = head; head = head->next; delete fence; } } public: LList(int size=DefaultListSize) { init(); } ~LList() { removeall(); } // Destructor void clear() { removeall(); init(); } bool insert(const Elem&); bool append(const Elem&); bool remove(Elem&); void setStart() { fence = head; rightcnt += leftcnt; leftcnt = 0; } void setEnd() { fence = tail; leftcnt += rightcnt; rightcnt = 0; } void prev(); void next() { if (fence != tail) // Don't move fence if right empty { fence = fence->next; rightcnt--; leftcnt++; } } int leftLength() const { return leftcnt; } int rightLength() const { return rightcnt; } bool setPos(int pos); bool getValue(Elem& it) const { if(rightLength() == 0) return false; it = fence->next->element; return true; } void print() const; }; template <class Elem> // Insert at front of right partition bool LList<Elem>::insert(const Elem& item) { fence->next = new Link<Elem>(item, fence->next); if (tail == fence) tail = fence->next; // New tail rightcnt++; return true; } template <class Elem> // Append Elem to end of the list bool LList<Elem>::append(const Elem& item) { tail = tail->next = new Link<Elem>(item, NULL); rightcnt++; return true; } // Remove and return first Elem in right partition template <class Elem> bool LList<Elem>::remove(Elem& it) { if (fence->next == NULL) return false; // Empty right it = fence->next->element; // Remember value Link<Elem>* ltemp = fence->next; // Remember link node fence->next = ltemp->next; // Remove from list if (tail == ltemp) tail = fence; // Reset tail delete ltemp; // Reclaim space rightcnt--; return true; } // Move fence one step left; no change if left is empty template <class Elem> void LList<Elem>::prev() { Link<Elem>* temp = head; if (fence == head) return; // No previous Elem while (temp->next!=fence) temp=temp->next; fence = temp; leftcnt--; rightcnt++; } // Set the size of left partition to pos template <class Elem> bool LList<Elem>::setPos(int pos) { if ((pos < 0) || (pos > rightcnt+leftcnt)) return false; fence = head; for(int i=0; i<pos; i++) fence = fence->next; return true; } template <class Elem> void LList<Elem>::print() const { Link<Elem>* temp = head; cout << "< "; while (temp != fence) { cout << temp->next->element << " "; temp = temp->next; } cout << "| "; while (temp->next != NULL) { cout << temp->next->element << " "; temp = temp->next; } cout << ">\n"; } #endif
//Shuffle.cpp The implementation of shuffle class and driver program
////////////////////////////////////////////////////// //program Name: Shuffle for assignment 2 of comp352 // //file name: Shuffle.cpp // //author: Qingzhe Huang // //ID: 5037735 // //date: Oct. 5, 2003 // ////////////////////////////////////////////////////// ////////////////////////////////////////////////////////////////////////////////////////////// //program features: //1. The header file given by book has one problem, that is, the AList.h and LList.h // both has a "DefaultListSize" as default parameter for constructor which is not // defined in their abastract base class----List. So, I arbitrarily add // const int DefaultListSize = 52 in List.h. //2. In order for a better representation, I defined a helper class "Card" which stores // the suit and value information of a card. Since the List "print" function will use // "cout<<element" to printout element. This Card class has implement a friend function // to overload operator <<. And because I use pointer "Card*" instead of object "Card" // as element in AList and LList, I have to overload "ostream& operator<<(ostream&, Card*)". //3. Shuffle is the major class to handle shuffling. Its private data includes both AList and // LList lists. Basically I need to four lists to do shuffling: // a) a source list, which stores the original data to be shuffled. // b) a target list, which stores the result data. // c) one left and one right list to store the left and right half of source list. // Since AList and LList are all inherited from List, I can use base class pointer to // do the same job. So I also need four pointer of List: // a) a pointer pointing to source list---pSource; // b) a pointer pointing to target list---pTarget; // c) two pointer pointing to left and right list---pLeft, pRight; //4. Within the Shuffle there is a Card array cards[52] which stores all 52 cards. The List // don't have to store the Card object itself, instead store its pointer Card*. So my AList // and LList is of type of AList<Card*> and LList<Card*>. Suppose this element Card is a // complicated class with many data inside, its pointer will be much lighter to store. //5. In the main function, I simply pass a flag to indicate whether I need to use array-based // List or LinkList-based List implementation to function "shuffling(ListType theType);". // All other code don't have to modify and it will output almost same with different List // implementation to indicate that my program is implementation independent! So, the input // of program is as simple as changing a single parameter in main function and call the // function "shuffling" again which will automatically initialize and doShuffle. //6. function "shuffling" will call function "doShuffle" several times before it initialize // all parameters and divide the original source list into "left" and "right" by copying. //7. function "doShuffle" is using base class pointer, so it is totally List-implementation- // independent which means the code is uniform disregarding the type of List. ///////////////////////////////////////////////////////////////////////////////////////////// #include <iostream> #include "LIST.H" #include "ALIST.H" #include "LINK.H" #include "LLIST.H" using namespace std; char* suitStr[4] = { "Spade", "Heart", "Diamond", "Club"}; enum SuitName {Spade, Heart, Diamond, Club}; enum ListType {ArrayList, LinkList}; enum Position {Left, Right}; //a helper class to denote the card value and suit class Card { //Card overload "<<" operator, // otherwise List member function "print" won't work! //PLS note the second parameter is pointer of Card: "Card*" friend ostream& operator<<(ostream& out, Card* card) { switch (card->value) { case 14: out<<"Ace"; break; case 13: out<<"King"; break; case 12: out<<"Queen"; break; case 11: out<<"Jack"; break; default: out<<card->value; break; } out<<" "<<suitStr[card->suit]; return out; } private: int suit; int value; public: void setSuit(int theSuit) { suit = theSuit;} void setValue(int theValue) { value = theValue;} }; class Shuffle { private: //this is the real card array and its pointers will be //given to our List class Card cards[4][13]; //these two generic base class pointer will do the same job //disregarding the implementation of array or linklist based. List<Card*>* pSource; List<Card*>* pTarget; //these two pointer represents the left-half and right-half List<Card*>* pLeft; List<Card*>* pRight; //array-based list //these are the left-half, right-half list AList<Card*> aLeft; AList<Card*> aRight; //these are the source and target list(array) AList<Card*> aSource; AList<Card*> aTarget; //link-list based list //these are the left-half, right-half list LList<Card*> lLeft; LList<Card*> lRight; //these are the source and target list(Linklist) LList<Card*> lSource; LList<Card*> lTarget; //param "pos" indicate whether remove from left or right, //return true if can remove, otherwise false bool getCard(Position pos); int getRand(); void doShuffle(bool toShow=false); void initialize(ListType theType); void setParam(ListType theType); void divideList(); public: void shuffling(ListType theType=ArrayList); }; int main() { Shuffle S; cout<<"First use array-based List to shuffle:\n"; S.shuffling(); cout<<"\n\n\nSecond use linklist-based List to shuffle:\n\n"; S.shuffling(LinkList); cout<<endl; return 0; } //param "pos" indicate whether remove from left or right, //return true if can remove, otherwise false bool Shuffle::getCard(Position pos) { Card* card;//a pointer int number = getRand(); List<Card*>* temp = pos==Left?pLeft:pRight; for (int i=0; i<number; i++) { //remove one from left or right and //insert into target if (temp->remove(card)) { pTarget->insert(card); } else { return false; } } return true; } //divide source list into two halves and copy //them into "left" and "right" void Shuffle::divideList() { Card* card; pSource->setPos(26); pLeft->setStart(); pRight->setStart(); while (pSource->remove(card)) { //remove is from beginning, so we need append pRight->append(card); } pSource->setStart(); while (pSource->remove(card)) { //append is efficient than insert generally pLeft->append(card); } } //this set up the pointers by param of ListType which //indicate whether it is array or linklist void Shuffle::setParam(ListType theType) { switch (theType) { case ArrayList: pLeft = &aLeft; pRight = &aRight; pSource = &aSource; pTarget = &aTarget; break; case LinkList: pLeft = &lLeft; pRight = &lRight; pSource = &lSource; pTarget = &lTarget; break; } } //this function do the shuffle job, it first initialize //source according parameter "ListType"; Then shuffle 5 times //in first time, call "doShuffle" with param of "true" to ask //"doShuffle" to print intermidiate result. void Shuffle::shuffling(ListType theType) { List<Card*>* temp; initialize(theType); for (int i=0; i<5; i++) { cout<<"\nbefore no."<<i+1<<" times shuffle:\n"; pSource->print(); if (i==0) { doShuffle(true); } else { doShuffle(false); } cout<<"\nafter no."<<i+1<<" times shuffle:\n"; pTarget->print(); //swap the two pointer so that shuffle again. temp = pSource; pSource= pTarget; pTarget = temp; } } //a utility method to get random number of 0-5 int Shuffle::getRand() { return rand()%6; } //first divide source into two halves, copy them to pLeft and pRight //alternatively remove random number of cards from two halves until both //halves are empty void Shuffle::doShuffle(bool toShow) { bool leftEmpty=false, rightEmpty=false; int counter=0; divideList(); if (toShow) { cout<<"\nbefore getCard, left half is:\n"; pLeft->print(); cout<<"\nbefore getCard, right half is:\n"; pRight->print(); cout<<"\nbefore getCard, result is:\n"; pTarget->print(); } while ((!leftEmpty)||(!rightEmpty)) { if (!getCard(Left)) { leftEmpty= true; } if (!getCard(Right)) { rightEmpty = true; } counter++; if (toShow) { cout<<"\nafter "<<counter<<" times getCard, left half is:\n"; pLeft->print(); cout<<"\nafter "<<counter<<" times getCard, right half is:\n"; pRight->print(); cout<<"\nafter "<<counter<<" times getCard, result is:\n"; pTarget->print(); } } } //initialize cards array and copy the standard card pointers into source. void Shuffle::initialize(ListType theType) { setParam(theType); for (int theSuit =0; theSuit<4; theSuit++) { for (int theValue=0; theValue<13; theValue++) { cards[theSuit][theValue].setSuit(theSuit); //the value of a card is starting from 14 till 2 cards[theSuit][theValue].setValue(14-theValue); //as the element is Card*, we add pointers //and here the pSource is actually a base class pointer //disregarding it is array-based-list or link-list-based-list! pSource->append(&cards[theSuit][theValue]); } } }
กก
The result is like following:
I omitted all intermediate result as it is too many, if you really like to check, click here.
......
after no.1 times shuffle:
< | 2 Club 3 Club 4 Club 5 Club 6 Club 7 Club 8 Club 9 Club 10 Club Jack Club
Queen Club 2 Heart King Club Ace Club 2 Diamond 3 Diamond 3 Heart 4 Heart 5
Heart 4 Diamond 5 Diamond 6 Diamond 7 Diamond 8 Diamond 6 Heart 7 Heart 8 Heart
9 Heart 10 Heart Jack Heart Queen Heart King Heart Ace Heart 2 Spade 3 Spade 4
Spade 5 Spade 6 Spade 7 Spade 8 Spade 9 Spade 9 Diamond 10 Diamond Jack Diamond
10 Spade Jack Spade Queen Spade King Spade Ace Spade Queen Diamond King Diamond
Ace Diamond >
before no.2 times shuffle:
< | 2 Club 3 Club 4 Club 5 Club 6 Club 7 Club 8 Club 9 Club 10 Club Jack Club
Queen Club 2 Heart King Club Ace Club 2 Diamond 3 Diamond 3 Heart 4 Heart 5
Heart 4 Diamond 5 Diamond 6 Diamond 7 Diamond 8 Diamond 6 Heart 7 Heart 8 Heart
9 Heart 10 Heart Jack Heart Queen Heart King Heart Ace Heart 2 Spade 3 Spade 4
Spade 5 Spade 6 Spade 7 Spade 8 Spade 9 Spade 9 Diamond 10 Diamond Jack Diamond
10 Spade Jack Spade Queen Spade King Spade Ace Spade Queen Diamond King Diamond
Ace Diamond >
after no.2 times shuffle:
< | 7 Heart 6 Heart 8 Diamond 7 Diamond 6 Diamond 5 Diamond 4 Diamond 5 Heart
Ace Diamond 4 Heart King Diamond Queen Diamond Ace Spade King Spade Queen Spade
3 Heart 3 Diamond 2 Diamond Ace Club King Club Jack Spade 10 Spade Jack Diamond
2 Heart Queen Club Jack Club 10 Diamond 9 Diamond 9 Spade 8 Spade 7 Spade 10
Club 6 Spade 5 Spade 4 Spade 9 Club 3 Spade 2 Spade Ace Heart King Heart Queen
Heart 8 Club 7 Club 6 Club Jack Heart 10 Heart 9 Heart 8 Heart 5 Club 4 Club 3
Club 2 Club >
before no.3 times shuffle:
< | 7 Heart 6 Heart 8 Diamond 7 Diamond 6 Diamond 5 Diamond 4 Diamond 5 Heart
Ace Diamond 4 Heart King Diamond Queen Diamond Ace Spade King Spade Queen Spade
3 Heart 3 Diamond 2 Diamond Ace Club King Club Jack Spade 10 Spade Jack Diamond
2 Heart Queen Club Jack Club 10 Diamond 9 Diamond 9 Spade 8 Spade 7 Spade 10
Club 6 Spade 5 Spade 4 Spade 9 Club 3 Spade 2 Spade Ace Heart King Heart Queen
Heart 8 Club 7 Club 6 Club Jack Heart 10 Heart 9 Heart 8 Heart 5 Club 4 Club 3
Club 2 Club >
after no.3 times shuffle:
< | Jack Club Queen Club 2 Heart Jack Diamond 10 Spade Jack Spade King Club
Ace Club 2 Diamond 3 Diamond 3 Heart Queen Spade King Spade Ace Spade Queen
Diamond King Diamond 2 Club 4 Heart 3 Club 4 Club 5 Club Ace Diamond 5 Heart 8
Heart 9 Heart 10 Heart Jack Heart 6 Club 7 Club 8 Club Queen Heart King Heart
Ace Heart 4 Diamond 5 Diamond 6 Diamond 7 Diamond 2 Spade 3 Spade 9 Club 4 Spade
5 Spade 6 Spade 10 Club 7 Spade 8 Spade 9 Spade 9 Diamond 10 Diamond 8 Diamond 6
Heart 7 Heart >
before no.4 times shuffle:
< | Jack Club Queen Club 2 Heart Jack Diamond 10 Spade Jack Spade King Club
Ace Club 2 Diamond 3 Diamond 3 Heart Queen Spade King Spade Ace Spade Queen
Diamond King Diamond 2 Club 4 Heart 3 Club 4 Club 5 Club Ace Diamond 5 Heart 8
Heart 9 Heart 10 Heart Jack Heart 6 Club 7 Club 8 Club Queen Heart King Heart
Ace Heart 4 Diamond 5 Diamond 6 Diamond 7 Diamond 2 Spade 3 Spade 9 Club 4 Spade
5 Spade 6 Spade 10 Club 7 Spade 8 Spade 9 Spade 9 Diamond 10 Diamond 8 Diamond 6
Heart 7 Heart >
after no.4 times shuffle:
< | 10 Heart 9 Heart 8 Heart 5 Heart Ace Diamond 5 Club 7 Heart 6 Heart 4
Club 3 Club 8 Diamond 10 Diamond 9 Diamond 4 Heart 2 Club King Diamond Queen
Diamond 9 Spade 8 Spade Ace Spade 7 Spade 10 Club 6 Spade 5 Spade 4 Spade King
Spade Queen Spade 9 Club 3 Spade 2 Spade 3 Heart 3 Diamond 2 Diamond Ace Club
King Club 7 Diamond 6 Diamond Jack Spade 10 Spade Jack Diamond 2 Heart Queen
Club 5 Diamond 4 Diamond Ace Heart King Heart Jack Club Queen Heart 8 Club 7
Club 6 Club Jack Heart >
before no.5 times shuffle:
< | 10 Heart 9 Heart 8 Heart 5 Heart Ace Diamond 5 Club 7 Heart 6 Heart 4
Club 3 Club 8 Diamond 10 Diamond 9 Diamond 4 Heart 2 Club King Diamond Queen
Diamond 9 Spade 8 Spade Ace Spade 7 Spade 10 Club 6 Spade 5 Spade 4 Spade King
Spade Queen Spade 9 Club 3 Spade 2 Spade 3 Heart 3 Diamond 2 Diamond Ace Club
King Club 7 Diamond 6 Diamond Jack Spade 10 Spade Jack Diamond 2 Heart Queen
Club 5 Diamond 4 Diamond Ace Heart King Heart Jack Club Queen Heart 8 Club 7
Club 6 Club Jack Heart >
after no.5 times shuffle:
< | King Spade 4 Spade 5 Spade 6 Spade 10 Club Jack Heart 6 Club 7 Club 8
Club 7 Spade Ace Spade Queen Heart Jack Club King Heart Ace Heart 8 Spade 9
Spade Queen Diamond King Diamond 4 Diamond 2 Club 5 Diamond Queen Club 4 Heart 9
Diamond 10 Diamond 8 Diamond 3 Club 2 Heart Jack Diamond 10 Spade Jack Spade 6
Diamond 4 Club 6 Heart 7 Diamond King Club 7 Heart 5 Club Ace Club 2 Diamond 3
Diamond 3 Heart 2 Spade Ace Diamond 5 Heart 8 Heart 9 Heart 3 Spade 9 Club Queen
Spade 10 Heart >