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. 

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 >