// File:		cstring.cpp
// ------------------------------------------------------------------
// Author:		Russell Lowke, russ@mocaz.com
// TF:          Francis Crick
// Date:        8/4/2002
// Assignment:	Unit 8
// Version:	1
//
// Description: Iterative version of cstring
// 

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


//
// 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     c = '\0';
	cstring* letter     = NULL;
	cstring* prevLetter = NULL;
	
	while( c != '\n' ) {
		
		s.get(c);							// get input
		if ( c == '\n' ) {
			if (prevLetter == NULL) {
				str = NULL;					// first char is '\n'
			} else {
				prevLetter->next = NULL;	// set last letter
			}
		} else {
		
			letter = new cstring(c);		// new letter
			
			if ( ! prevLetter ) {
				str = letter;				// set head of list
				
			} else {
				prevLetter->next = letter;	// link to previous letter
			}
			
			prevLetter = letter;			// letter to previous
			
		}
	}

    return s;
}


//
// operator << - writes a cstring to an output stream
//
ostream& operator <<(ostream& s, cstring *str)
{
   	while(str != NULL) {
		s << str->firstch;					// output this char
		str = str->next;					// move to next
	}
	
    return s;
}


//
// length - returns the number of characters in a cstring
//
int length(cstring *str)
{
	int counter  = 0;
	
	while(str != NULL) {
		counter++;							// count it
		str = str->next;					// move to next
	}

    return counter;
}

//
// 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)
{
	int counter = 0;
	
    if ( i < 1 ) {							// test for crap
		cout << "ERROR - INVALID POSITION";
		return -1;
    } else if ( str == NULL ) {
		return 0;
    } else {
    
	    while(str != NULL) {
	    	counter++;
	    	if (i == counter) {				// is this the one?
	    		return str->firstch;		// tell this char
	    	}
			str = str->next;				// move to next
		}
    }
    
    return 0;
}


//
// 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)
{
    int counter  = 0;
    
    while(str != NULL) {
    	counter++;
    	if (str->firstch == ch) {			// is this the one?
    		 return counter;				// tell the count
    	}
		str = str->next;					// move to next
	}
    
    return 0;
}


//
// copystr - returns a copy of the given cstring
//
cstring* copystr(cstring *str)
{
	cstring *head       = NULL; 			// head of new list
	cstring *letter     = NULL;
	cstring *prevLetter = NULL;
	
	while(str != NULL) {
		
		letter = new cstring( str->firstch );
		if ( ! prevLetter ) {				// if first char (no previous)
			head = letter;					// set the head of the list					
		} else {
			prevLetter->next = letter;		// link previous to this
		}
		
		prevLetter = letter;				// new previous
		str = str->next;					// move to next
	}
	
	if ( prevLetter != NULL ) {
		prevLetter->next = NULL;			// end list with NULL
	}
	
    return head;
}


//
// concat - returns the concatenation of two cstrings
//
cstring* concat(cstring *str1, cstring *str2)
{
	// copy the strings
	cstring* cpyA = copystr(str1);
	cstring* cpyB = copystr(str2);
	
	if (cpyA == NULL) {
		return cpyB;							// there is first str
	}
	
	//
	// link the end of cpyA to the front of cpyB
	//
	cstring* temp = point(cpyA, length(cpyA) );	// find end of cpyA
	temp->next = cpyB;							// link to front of cpyB
	
	return cpyA;
}


//
// 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)
{
	cstring* temp = NULL;
	head = NULL;
	tail = NULL;
	
	if (str == NULL) {
		// skip
		
	} else if ( (n <= 0) || n > length(str)  ) {
		head = copystr(str);
	} else {
		
		head = copystr(str);					// duplicate str
	    temp = point(head, n); 					// find split pt
	    if ( temp != NULL ) {
	    	tail = temp->next;					// set tail to split pt
	    	temp->next = NULL;					// NULL to end of head
	    }
	}
}


//
// 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)
{

    int counter  = 0;
    
 	if (i < 1) {								// test for crap
		cout << "ERROR - INVALID POSITION";
		return NULL;
    }
    else if (str == NULL) {
		return NULL;
		
	} else if (i > length(str)) {				// test for length
    	return NULL;
    	
    } else {
	    while(str != NULL) {					// step through list
	    	counter++;
	    	if (i == counter) {					// is this the one?
	    		return str;						// tell the ptr
	    	}
			str = str->next;					// move to next
		}
    }
    
    return NULL;

}



//
// 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;
}
