// File:		cstring.cpp
// ------------------------------------------------------------------
// Author:		<your name>, <your e-mail address>
// TF:          <your TF's name>
// Date:        <current date>
// Assignment:	Unit 8
// Version:	1
//
// Description:
// 

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

//
// For each function below that uses recursion, rewrite it so that
// it uses iteration instead.  The functions to write are indicated
// with a TODO.
//


//
// 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)
{
    // TODO - WRITE THIS FUNCTION ITERATIVELY
}

//
// operator << - writes a cstring to an output stream
//
ostream&
operator <<(ostream& s, cstring *str)
{
    // TODO - WRITE THIS FUNCTION ITERATIVELY
}

//
// length - returns the number of characters in a cstring
//
int
length(cstring *str)
{
    // TODO - WRITE THIS FUNCTION ITERATIVELY
}

//
// 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)
{
    // TODO - WRITE THIS FUNCTION ITERATIVELY
}

//
// 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)
{
    // TODO - WRITE THIS FUNCTION ITERATIVELY
}

//
// copystr - returns a copy of the given cstring
//
cstring*
copystr(cstring *str)
{
    // TODO - WRITE THIS FUNCTION ITERATIVELY
}

//
// concat - returns the concatenation of two cstrings
//
cstring*
concat(cstring *str1, cstring *str2)
{
    // TODO - WRITE THIS FUNCTION ITERATIVELY
}

//
// 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)
{
    // TODO - WRITE THIS FUNCTION ITERATIVELY
}

//
// 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)
{
    // TODO - WRITE THIS FUNCTION ITERATIVELY
}

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