Population

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.

    B.The problem

    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.

C.The idea of program

    This is a simplified version of my original assignment.

    D.The major functions

    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 >