Symple Shuffle
A.First Edition
This is my second 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.
This is a simplified version of my original assignment.
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
#include "List.h" #include "link.h" #include "Alist.h" #include "LList.h" #include <iostream> using namespace std; enum ListType {ArrayList, LinkList}; char* suitString[4] = {"spade", "heart", "diamond", "club"}; AList<char*> aSource; AList<char*> aLeft; AList<char*> aRight; LList<char*> lSource; LList<char*> lLeft; LList<char*> lRight; void initialize(ListType listType= ArrayList); void splitDeck(ListType listType=ArrayList); void shuffling(ListType listType=ArrayList, bool toShow=false); void shuffle(); int main() { shuffle(); return 0; } void shuffle() { initialize(); cout<<"This is for arrayList\n"; for (int i=0; i<6; i++) { cout<<"\nbefore no."<<i+1<<"times shuffle:"; aSource.print(); if (i==0) { shuffling(ArrayList, true); } else { shuffling(ArrayList, false); } } cout<<"\nafter all shuffling\n"; aSource.print(); cout<<"\nThis is for linkList\n"; initialize(LinkList); for (i=0; i<6; i++) { cout<<"\nbefore no."<<i+1<<"times shuffle:"; lSource.print(); if (i==0) { shuffling(LinkList, true); } else { shuffling(LinkList, false); } } cout<<"\nafter all shuffling\n"; lSource.print(); } void shuffling(ListType listType, bool toShow) { int number; bool leftEmpty=false, rightEmpty =false; List<char*>* ptr; List<char*>* pLeft; List<char*>* pRight; char* str; if (listType==ArrayList) { ptr = &aSource; pLeft = &aLeft; pRight = &aRight; } else { ptr = &lSource; pLeft = &lLeft; pRight = &lRight; } splitDeck(listType); while (!leftEmpty||!rightEmpty) { if (toShow) { cout<<"\nresult before shuffle:"; ptr->print(); cout<<endl; cout<<"\nleft before shuffle:"; pLeft->print(); cout<<endl; } number = rand()%6; for (int i=0; i<number; i++) { if (pLeft->remove(str)) { ptr->append(str); } else { leftEmpty = true; break; } } number = rand()%6; if (toShow) { cout<<"\nright before shuffle:"; pRight->print(); cout<<endl; } for (i=0; i<number; i++) { if (pRight->remove(str)) { ptr->append(str); } else { rightEmpty = true; break; } } } } void fillSuit(int suit, char* str, ListType listType) { char buffer[20]; char* ptr; strcpy(buffer, str); strcat(buffer, suitString[suit]); ptr = new char[strlen(buffer)+1]; if (listType==ArrayList) { aSource.append(strcpy(ptr, buffer)); } else { lSource.append(strcpy(ptr, buffer)); } } void splitDeck(ListType listType) { List<char*>* ptr; List<char*>* pLeft; List<char*>* pRight; char* str; if (listType==ArrayList) { ptr = &aSource; pLeft = &aLeft; pRight = &aRight; } else { ptr = &lSource; pLeft = &lLeft; pRight = &lRight; } ptr->setStart(); for (int i=0; i<52; i++) { ptr->remove(str); if (i<26) { pLeft->append(str); } else { pRight->append(str); } } } void initialize(ListType listType) { void fillSuit(int suit, char* str, ListType listType); char buffer[10]; for (int suit=0; suit<4; suit++) { for (int card=0; card<13; card++) { switch(card) { case 0: fillSuit(suit, "Ace ", listType); break; case 1: fillSuit(suit, "King ", listType); break; case 2: fillSuit(suit, "Queen ", listType); break; case 3: fillSuit(suit, "Jack ", listType); break; default: itoa(14 - card, buffer, 10); fillSuit(suit, buffer, listType); break; } } } }
กก
The result is like following:
I omitted all intermediate result as it is too many, if you really like to check.
......
before no.2times shuffle:< | Ace spade King spade Queen spade Jack spade Ace
diamond King diamond Queen diamond Jack diamond 10spade 9spade 8spade 10diamond
9diamond 8diamond 7diamond 6diamond 7spade 5diamond 4diamond 3diamond 6spade
2diamond Ace club King club Queen club Jack club 5spade 4spade 3spade 10club
9club 8club 2spade Ace heart King heart Queen heart Jack heart 7club 6club 5club
4club 3club 10heart 2club 9heart 8heart 7heart 6heart 5heart 4heart 3heart
2heart >
before no.3times shuffle:< | Ace spade King spade Queen spade 5spade 4spade
3spade 10club 9club 8club 2spade Ace heart King heart Queen heart Jack heart
7club Jack spade Ace diamond King diamond Queen diamond 6club 5club 4club 3club
10heart 2club 9heart 8heart 7heart 6heart Jack diamond 10spade 5heart 4heart
3heart 9spade 2heart 8spade 10diamond 9diamond 8diamond 7diamond 6diamond 7spade
5diamond 4diamond 3diamond 6spade 2diamond Ace club King club Queen club Jack
club >
before no.4times shuffle:< | 8heart 7heart 6heart Jack diamond 10spade Ace spade
5heart 4heart 3heart 9spade King spade Queen spade 5spade 4spade 3spade 2heart
8spade 10club 9club 8club 2spade Ace heart 10diamond 9diamond 8diamond King
heart Queen heart 7diamond 6diamond 7spade 5diamond 4diamond Jack heart 3diamond
6spade 7club Jack spade Ace diamond King diamond 2diamond Ace club King club
Queen diamond 6club Queen club Jack club 5club 4club 3club 10heart 2club 9heart
>
before no.5times shuffle:< | 8heart Queen heart 7diamond 6diamond 7heart 6heart
Jack diamond 10spade 7spade 5diamond 4diamond Jack heart 3diamond Ace spade
5heart 6spade 7club 4heart 3heart Jack spade Ace diamond King diamond 2diamond
Ace club 9spade King spade Queen spade 5spade 4spade King club Queen diamond
3spade 6club 2heart 8spade 10club 9club Queen club Jack club 5club 4club 8club
2spade 3club 10heart 2club 9heart Ace heart 10diamond 9diamond 8diamond King
heart >
before no.6times shuffle:< | 8heart Queen heart 7diamond Queen spade 5spade
4spade King club 6diamond 7heart 6heart Jack diamond Queen diamond 3spade 6club
10spade 7spade 5diamond 4diamond 2heart 8spade 10club 9club Queen club Jack
heart 3diamond Ace spade 5heart Jack club 5club 6spade 7club 4heart 3heart Jack
spade 4club 8club 2spade 3club 10heart Ace diamond King diamond 2diamond Ace
club 9spade King spade 2club 9heart Ace heart 10diamond 9diamond 8diamond King
heart >
after all shuffling
< | 8heart Queen heart 7diamond Queen spade 5spade 4spade King club 6diamond
7heart 5heart Jack club 5club 6spade 7club 6heart Jack diamond Queen diamond
3spade 6club 4heart 3heart 10spade 7spade Jack spade 4club 5diamond 4diamond
2heart 8club 8spade 10club 9club Queen club Jack heart 3diamond Ace spade 2spade
3club 10heart Ace diamond King diamond 2diamond Ace club 9spade King spade 2club
9heart Ace heart 10diamond 9diamond 8diamond King heart >