/*
	File: testRecursionWithCstrings.cpp
	John Sterling -- jsterling@poly.edu
	CS1124
	Polytechnic University

	Demonstrates various recursive algorithms based on C-Strings.
*/

#include <iostream>
using namespace std;

void printReverse(char[]);
void printReverse2(char*);
int lengthOfString(char*);
void stringCopy(char*, char*);

int main() {

	char cString[] = "I am a c-string";

	// C++ provides us with an easy way to print out c-strings.
	// Just use the output operator with the address of the 
	// beginning of the array.
	// This *only* works for null-terminated arrays of characters,
	//   not for any other type of array.
	cout << cString << endl;

	// We call two different functions that print our cstring in reverse.
	// See the comments on the function definitions for how they work.
	printReverse(cString);
	cout << endl;
	printReverse2(cString);
	cout << endl;

	cout << "The length of cString is " << lengthOfString(cString) << " characters\n"
		<< "   but that's not counting the NULL at the end\n";

	// We will use anotherCString to copy cString into.
	// lengthOfString(cString) returned 15, but we need an array
	// with at least 16 characters to have enough room for
	// cString, so that we have room for the '\0'.
	// We initialized it so that we could print out something.
	char anotherCString[16] = "Another string";
	cout << "anotherCString before the copy:\n" << anotherCString << endl;
	stringCopy(anotherCString, cString);
	cout << "anotherCString after the copy:\n" << anotherCString << endl;

	return 0;

}

// printReverse takes a null-terminated array of characters 
// (also known as a "c-string") and
// prints them in reverse using recursion
// The idea of the function is:
//    1) print all the characters *except* the first one in 
//       reverse (using a recursive call)
//    2) then print the first character
void printReverse(char a[]) {
	// We test to make sure that the array that has been passed
	// doesn't start with the character '\0'.
	// This test could also be written:
	//    if (a[0] != '\0') {
	if (a[0]) {
		// we pass in the address of the *second* character in the array
		//   so that the recursive call will start there.
		printReverse(&a[1]);
		// after printing all the rest of the characters in reverse
		//    we finally print the first character.
		cout << a[0];
	}
}

// printReverse2 works just like printReverse.  The only difference
// is that we view the paramater as a pointer to the beginning of
// the null-terminated character array. 
void printReverse2(char* p) {
	// Test to see that the character that p is pointing to 
	//    isn't NULL.
	if (*p) {
		// We pass in the address of the next character.
		// This recursive call will print all the rest of the characters
		// in reverse.
		printReverse2(p + 1);
		// Finally, print out the character at the beginning.
		cout << *p;
	}
}

// lengthOfString behaves just like the library function strlen.
// It returns the "length" of the c-string that is passed
// to it, without counting the NULL character at the end.
// So, lengthOfString("") returns 0.
// We chose to think of the parameter as a pointer to characters, but
// we could have treated it as an array of characters (as we did in
// printReverse).
int lengthOfString(char* p) {
	// If we're pointing at the last character in the string
	//   then the length is zero.
	// REMEMBER that we need to dereference p!!!
	if (*p == NULL)
		return 0;
	else
		// Otherwise we add one to the length of the rest of the
		// string and return that. 
		// Note that we pass the address of the next character in
		// the string to the recursive call.
		return 1 + lengthOfString(p + 1);
}

// This will work just like the library function strcpy.
// The cstring pointed to by source will be copied into the array
// pointed to by target.
// WARNING:  There must be enough room allocated in the target array
// for all the characters in the source array.  Otherwise the result
// of running this function is unpredictable.  (E.g., program may crash.)
void stringCopy(char* target, char* source) {
	// We want to copy over the character, no matter what it is
	// so we do that even before testing to see if we're done.
	*target = *source;
	// Now that we've copied it, if the character was '\0'
	// then we're done.
	if (*source == '\0') 
		return;
	// Otherwise, we copy the rest of the string into the rest of the target.
	else 
		stringCopy(target+1, source+1);
}