Population

Sort Machine

    A.First Edition

    This is my first edition of a sort machine which is a class doing both trimming and sorting of a string.

    B.The problem

Write a function to sort a character string in ascending alphabetic order.
The function should also convert all lower case letter to upper case letter.
You should remove all characters that are not alphabetic (i.e. take out spaces,
numbers, and punctuation).
The function must receive a pointer to the string, and return a pointer to
the string. Recall that strings end in '\0' and you should not sort this character.
For example the string "This is a string!", should be sorted as "AGHIIINRSSSTT".
(Hint: You can use the bubble sort algorithm.)
Write a driver program to test your function.
กก
C.The idea of program

    There are two major feature about my class as mentioned in the remark part of my program:

    1. I made the storage of string flexible by implementing it like dynamic array so that it can increase length

    according to input. I defined constant "MaxLength" for class which must be passed in and initialized before

    constructor. Then by record number of "relocating", I can increase one "MaxLength" every time my string found

    out it need more memory. At destructor, the dynamic allocated memory is freed.

    2. I made several flags for my class so that programmer can choose different sorting algorithms like bubble

    sort, quick sort etc. and sorting type as ascending or descending.

    D.The major functions

    1. char* SortMachine::trimStr(const char* const str)

    It first trims off all other char except letters, also make all them big cases. As the passing parameter str

    can not be changed in any way, I made both the contents and pointer itself const. During trimming, it checks

    the length of input string, see if the length exceeds size of my array, a "relocate" is called by add more

    space to original array. So it is like the way of dynamic array.

    2. SortMachine::SortMachine(const char* const str, int defaultLength)

    This constructor with defaultLength which is used to initialize the constant "MaxLength".

    C.Further improvement

    1. add more sorting algorithms.

    2. make it more general so that any type of data can be sort, not only char.

    กก

    /***************************************************************************
    ////Author: Qingzhe Huang
    ////Date: Jul 13, 2003
    ////Name of program: Sorting Machine
    ///////////////////////////////////////////////////////////////////////////

    I arbitarily made my program a class, as I see some opportunity that it is fairly
    a common job to do sorting for a string, plus some extra job like "trimming".
    And what's more I made my string a kind of "dynamic" array which can increase
    length according input by "realloc" new length of mem to sting pointer.
    Basically there two major features of my class:
    	1. In my class, I set up several flag to enable it to sort in different algorithms,
    	like bubble sort, quick sort and maybe more in future. Also, I make it possible to
    	sort it in both ascending and descending by open a method called "setParam" which
    	allow program to set all sorting parameters---sortType, isAscending, maybe more in
    	future.
    	2. For the trimming part, I made a my array like dynamic array so that it can increase
    	automatically realloc memory by adding  20 bytes more to old size. So, I defined a
    	constant "MaxLength" and use the method introduced in lecture to initialize it
    	before constructor. A "relocCounter" to record how many times reloc is invoked, so
    	by increment this counter, 20 more bytes are added to "reallocate" for string.
    	And this 20bytes is passed by default in constructor to set the constant "MaxLength",
    	so it is also changeable by programmer.
    	At destructor, the dynamic allocated memory is freed.
    /////////////////////////////////////////////////////////////////////////////
    ////Possible improvement:
    // 1. add more sorting algorithms
    // 2. make it more general so that any type of data can be sort,not only char
    ****************************************************************************/

    #include <iostream>

    using namespace std;

    enum SortType
    {BubbleSort, QuickSort};

    class SortMachine
    {
    private:
    	const int MaxLength; //default pre-allocate array length
    	int relocCounter;//record number of reloc in case string length is longer than size
    	char* myStr;
    	bool ascending;  //default is ascending, however, you can set by setParam
    	SortType sortType; //enum indicate bubbleSort or quickSort
    	int size; //it is the size of mem alloc for str, not length,
    	int length;//this is indeed the length of myStr
    	void doQuickSort(int start, int end);
    	int partition(int start, int end); //I am not sure if it is better to put in protected
    	void swap(int i, int j);//because like these functions should be deriveable in child class
    	bool smaller(int i, int j);//this is an ackward method to implement descending
    	bool smallerEqual(int i, int j);
    protected:
    	//I put all initialize part here instead of constructor, simply because it is a painful
    	//in c++ that you cannot control the constructor of parent class, they are always called
    	//not like in Delphi,you can have fully control of ancestor's constructor
    	//so, in this case, all derived class can have opportunity to modify the ancestor's
    	//initialize method, where if put in constructor, you cannot do it.
    	void initialize();
    	//the passed parameter should not be changed either value or pointer itself
    	char* trimStr(const char* const str);
    	void relocStr();
    	void quickSort();
    	void bubbleSort();
    public:
    	SortMachine(int defaulLength = 20);
    	SortMachine(const char* const str, int defaultLength =20);
    	~SortMachine();
    	void setStr(const char* const str);//it trims and assign to myStr
    	void setParam(SortType mySortType = BubbleSort, bool isAscending = true);
    	const char* getStr() { return myStr;}
    	void sortStr();
    };

    int main()
    {
    	SortMachine s;
    	char str[80];
    	cin.getline(str, 80);
    	s.setStr(str);
    	s.setParam(QuickSort, false);
    	s.sortStr();
    	cout<<s.getStr()<<endl;

    	return 0;
    }

    //this is put into protected as derived class may need to modify
    void SortMachine::initialize()
    {
    	//it is absurd to use this name to represent how many times reloc happened,
    	relocCounter =0;
    	ascending = true;
    	sortType = BubbleSort;
    	size = 0;
    	myStr = NULL;
    }

    //this constructor with only a default size of
    SortMachine::SortMachine(int defaultLength)
    :MaxLength(defaultLength) //initialize constant in class
    {
    	initialize();
    }

    //the constructor with both input str and default length of my array
    SortMachine::SortMachine(const char* const str, int defaultLength)
    :MaxLength(defaultLength)//initialize constant in class
    {
    	initialize();
    	myStr = trimStr(str);
    }

    //we need to free the memory what allocated
    SortMachine::~SortMachine()
    {
    	free((void*)(myStr));
    }

    void SortMachine::setStr(const char* const str)
    {
    	myStr = trimStr(str);
    }

    //as the str is not supposed to be changed either contents or itself, I made const both ways
    char* SortMachine::trimStr(const char* const str)
    {
    	int counter =0;
    	char* target;
    	char* source;

    	//first make sure user is not naughty
    	if (str==NULL)
    	{
    		return NULL;
    	}
    	//this is the default size of mystr
    	size = MaxLength;//at first it is MaxLength
    	myStr =(char*)malloc(size);

    	target = myStr;
    	source = (char*)str;

    	while (*source!=NULL)
    	{
    		if (*source>='A'&&*source<='Z')//I prefer not to use ASCII number for compatible reason
    		{
    			*target = *source;
    			target++;
    			counter++;

    			//this means we must reloc mem for myStr, as NULL is not write at end
    			if (counter==size)
    			{
    				relocStr();
    				target = myStr+counter; //restore position of target
    			}
    		}
    		else
    		{
    			if (*source>='a'&&*source<='z')//I prefer not to use ASCII number for compatible
    			{
    				*target = *source + 'A' - 'a';//it is better not use ASCII number
    				target++;
    				counter++;
    				if (counter==size)
    				{
    					relocStr();
    					target = myStr+counter; //restore position of target
    				}
    			}
    		}
    		source++;//in any case, we move to next char
    	}
    	*target = NULL; //write last NULL at end.
    	length = counter;
    	return myStr;
    }

    void SortMachine::relocStr()
    {
    	char* temp;
    	relocCounter++;
    	size = (1+relocCounter)*MaxLength;
    	//better to test before assign myStr, so, if exception, we didn't destroy what we have
    	//I read this from some book
    	temp = (char*)realloc((void*)(myStr), size);
    	if (temp!=NULL)
    	{
    		myStr = temp;
    	}
    	else
    	{
    		cout<<"Fail to reloc!";
    	}
    }

    void SortMachine::sortStr()
    {
    	switch (sortType)
    	{
    	case BubbleSort:
    		bubbleSort();
    		break;
    	case QuickSort:
    		quickSort();
    		break;
    	}
    }

    void SortMachine::setParam(SortType mySortType, bool isAscending)
    {
    	sortType = mySortType;
    	ascending = isAscending;
    }

    void SortMachine::quickSort()
    {
    	doQuickSort(0, length-1);
    }

    void SortMachine::doQuickSort(int start, int end)
    {
    	int pos;
    	if (start<end)
    	{
    		pos = partition(start, end);
    		doQuickSort(start, pos-1);
    		doQuickSort(pos+1, end);
    	}
    }

    int SortMachine::partition(int start, int end)
    {
    //	char ch;
    	int i;
    	i = start-1;
    //	ch = myStr[end];
    	for (int j=start; j<end; j++)
    	{
    		//if (myStr[j]<=ch)
    		if (smallerEqual(j, end))
    		{
    			i++;
    			swap(i,j);
    		}
    	}
    	swap(i+1, j);
    	return i+1;
    }

    void SortMachine::bubbleSort()
    {
    	for (int i=0; i< length-1; i++)
    	{
    		for (int j=i+1; j<length; j++)
    		{
    			//if (myStr[i]>myStr[j])
    			if (smaller(j, i))
    			{
    				//swap
    				swap(i, j);
    			}
    		}
    	}
    }

    void SortMachine::swap(int i, int j)
    {
    	char ch;
    	if (i!=j)
    	{
    		ch = myStr[i];
    		myStr[i] = myStr[j];
    		myStr[j] = ch;
    	}
    }

    //I made this to make descending sorting possible
    bool SortMachine::smaller(int i, int j)
    {
    	if (ascending)
    	{
    		return myStr[i]<myStr[j];
    	}
    	else
    	{
    		return myStr[i]>=myStr[j];
    	}
    }

    //I made this to make descending sorting possible
    bool SortMachine::smallerEqual(int i, int j)
    {
    	if (ascending)
    	{
    		return myStr[i]<=myStr[j];
    	}
    	else
    	{
    		return myStr[i]>myStr[j];
    	}
    }