// Filename:	cstring.cpp
// Author:	<Insert your name> (<Insert your email address>)
// Assignment:	Unit 8
// Date:	<Insert the current date here>
// Version:	1

#include <iostream.h>
#include "cstring.hpp"

//
// For each function below that uses recursion, rewrite it so that
// it uses iteration instead.
//


//
// Default constructor
//
cstring::cstring()
{
    firstch = 0;
    next = NULL;
}

//
// Constructor that specifies the first character
//
cstring::cstring(char ch)
{
    firstch = ch;
    next = NULL;
}

//
// operator >> - reads a cstring from an input stream
//
istream&
operator >>(istream& s, cstring*& str)
{
    char ch;

    s.get(ch);
    if (ch == '\n') {
	// termination step
	str = NULL;
    }
    else {
	// recursive step 
	str = new cstring(ch);
	s >> str->next;
    }
    
    return s;
}

//
// operator << - writes a cstring to an output stream
//
ostream&
operator <<(ostream& s, cstring *str)
{
    // termination step: does nothing if str == NULL
    
    if (str != NULL) {  
	// recursive step
	s << str->firstch;
	s << str->next;
    }
    
    return s;
}

//
// length - returns the number of characters in a cstring
//
int
length(cstring *str)
{
    if (str == NULL)
	return  0;	// termination
    else
	return (1 + length(str->next));
}

//
// extract - returns the character in position i, where the first character
// is in position 1.
// If the cstring is < i characters long, returns 0.
// If the index i is < 1, returns -1.
//
char
extract(cstring *str, int i)
{
    if (i < 1) {
	cout << "ERROR - INVALID POSITION";
	return -1;
    }
    else if (str == NULL || i < 1) 
	return 0;
    else if (i == 1)
	return str->firstch;	// termination
    else
	return extract(str->next, i-1);
}

//
// index - returns the position of the first occurrence of character ch
// in the given cstring.  If there is none, returns 0.
//
int
index(cstring *str, char ch)
{
    if (str == NULL)
	return 0;
    else if (str->firstch == ch)
	return 1;	// termination
    else {
	int temp = index(str->next, ch);
	return (temp == 0 ? 0 : temp + 1);
    }
}

//
// copystr - returns a copy of the given cstring
//
cstring*
copystr(cstring *str)
{
    if (str == NULL)
	return NULL;    // termination 
    else {
	cstring *temp = new cstring(str->firstch);
	temp->next = copystr(str->next);
	return temp;
    }	
}

//
// concat - returns the concatenation of two cstrings
//
cstring*
concat(cstring *str1, cstring *str2)
{
    cstring *temp = new cstring;

    if (str1 == NULL)
	temp = copystr(str2);	// termination
    else {  
	temp->firstch = str1->firstch;
	temp->next = concat(str1->next, str2);
    }

    return temp;
}

//
// split - splits a cstring into two substrings:
// head, which is a copy of the first n characters, and
// tail, which is a copy of the rest of the cstring
//
void
split(cstring *str, int n, cstring*& head, cstring*& tail)
{
    if (str == NULL) {
	// termination
	head = NULL;
	tail = NULL;
    }
    else if (n <= 0) {
	// another termination 
	head = NULL;
	tail = copystr(str);
    }
    else { 
	head = new cstring(str->firstch);
	cstring *resthead;
	split(str->next, n-1, resthead, tail);
	head->next = resthead;
    }
}

//
// point - returns a pointer to character i in the given cstring.
// If the string is too short, returns NULL.
//
cstring*
point(cstring *str, int i)
{
    if (i < 1) {
	cout << "ERROR - INVALID POSITION";
	return NULL;
    }
    else if (str == NULL)
	return NULL;
    else if (i == 1)
	return str;
    else
	return point(str->next, i-1);
}

//
// cdelete - deletes the character in position i of the given string.
// (non-recursive)
//
void
cdelete(cstring*& str, int i)
{
    if (i < 1) 
	cout << "ERROR - INVALID POSITION";
    else if (str == NULL)
	cout << "ERROR - STRING TOO SHORT";
    else if (i == 1) {
	cstring *temp = str;
	str = str->next;
	delete temp;
    }
    else {
	cstring *temp = point(str, i-1);
	if (temp != NULL && temp->next != NULL) {
	    cstring *to_del = temp->next;
	    temp->next = temp->next->next;
	    delete to_del;
	} else
	    cout << "ERROR - STRING TOO SHORT";
    }
}

//
// insert - inserts character ch before position i of the given string
// (non-recursive)
//
void
insert(cstring*& str, int i, char ch)
{
    if (i < 1) {
	cout << "ERROR - INVALID POSITION";
	return;
    }
	
    cstring *newrec = new cstring(ch);

    if (i == 1) {
	newrec->next = str;
	str = newrec;
    }
    else {
	cstring *temp = point(str, i-1);
	if (temp == NULL)
	    cout << "ERROR - STRING TOO SHORT";
	else {
	    newrec->next = temp->next;
	    temp->next = newrec;
	}
    }
}

//
// insert_sorted - inserts character ch in the correct position
// in a sorted list of characters (i.e., a sorted cstring)
//
void
insert_sorted(cstring*& str, char ch)
{
    cstring *newrec = new cstring(ch);

    // Find where the character belongs.
    cstring *prev, *trav;
    prev = NULL;
    trav = str;
    while (trav != NULL && trav->firstch < ch) {
	prev = trav;
	trav = trav->next;
    }

    // Insert the new record.
    if (prev == NULL) {
	//
	// We never advanced the pointers, so newrec
	// goes at the start of the list.
	//
	str = newrec;
    }
    else
	prev->next = newrec;
    newrec->next = trav;
}
