CS222, Data Structures

//Shawn O'Neil - Hash Table. ADD, DELETE, MEAN, GRADE implemented. PRINT works, but prints the
//entire thing in no particular order.
//CS222 - Winter 03.
#include <iostream>
#include <string>
#include "htable.h"
//#include "list.h"
using namespace std;

#define NOTFOUND 1
#define OUTRANGE 2
#define DUPLICATE 3
#define NONONZERO 4


//Hash Table constructor
HTable::HTable()
	{
	for(int i = 0; i < 5; i++)
		{
		scores[i] = 0;
		numbers[i] = 0;
		}
	}

//Hash Table destructor
HTable::~HTable()
	{
	}

//Given a name, looks up its position in the table
int HTable::lookup(string thename)
	{
	int current = 0;
	for(int i = 0; i < thename.length(); i++)
		{
		current = (current*256+(1+(int)(unsigned char)thename[i]))%25013;
		}
	return current;
	}

//Adds a name to the table
void HTable::add(string thename)
	{
	t[lookup(thename)].add(thename);
	}

//deletes a name from the table
void HTable::del(string thename)
	{
	t[lookup(thename)].del(thename, this);
	}

//Sets thenames grade on test number to score, throws outrange if score or test are no good
void HTable::grade(int number, double score, string thename)
	{
	if(score <= 0)
		throw OUTRANGE;
	else if(number != 1 && number != 2 && number != 3 && number != 4 && number != 5)
		throw OUTRANGE;
	else
		{
		t[lookup(thename)].grade(number, score, thename);
		scores[number] += score;
		numbers[number]++;
		}
	}

//returns the mean on test
double HTable::mean(int test)
	{
	if(numbers[test] == 0)
		throw NONONZERO;
	else return scores[test]/numbers[test];
	}

//prints the entire hash table in no particular order
void HTable::print()
	{
	//dont be stupid, you cant full print a hash table! well, ill
	//implement some approximation...
	for(int i = 0; i < 25013; i++)
	t[i].fullprint();
	}

//Used by delete, at the node in the linked list level to fix the totals so the mean funciton will work
void HTable::redogrades(int test, double score)
	{
	scores[test] -= score;
	numbers[test]--;
	}

//Main method, use ADD , DELETE, GRADE, MEAN, and PRINT (only if you really want to...)
int mainf(int argc, char **argv)
	{
	cout << "Happy birthday euclid." << endl;
	HTable t;
	string action;
	int number;
	double grade;
	string name;
	while(cin >> action, cin)
		{
		cin.ignore();
		if(action == "ADD")
			{
			getline(cin, name);
			try
				{
				t.add(name);
				cout << "Successfully added " << name << "." << endl;
				cout << endl;
				}
			catch(int e)
				{
				if(e == NOTFOUND)
					cout << "Could not add, ERROR" << endl;
				else if(e == DUPLICATE)
					cout << "Could not add " << name << ". Name already exists." << endl;
				else if(e == OUTRANGE)
					cout << "Could not add, ERROR" << endl;
				cout << endl;
				}
			}

		else if(action == "PRINT")
			{
			try
				{
			//	cout << endl;
				cout << "Statistics: " << endl;
				t.print();
				cout << endl;
				}
			catch(int e)
				{
				if(e == NOTFOUND)
					cout << "Could not print, ERROR" << endl;
				else if(e == DUPLICATE)
					cout << "Could not print, ERROR" << endl;
				else if(e == OUTRANGE)
					cout << "Could not print, ERROR" << endl;
				cout << endl;
				}
			}

		else if(action == "GRADE")
			{
			cin >> number;
			cin.ignore();
			cin >> grade;
			cin.ignore();
			getline(cin, name);
			try
				{
				t.grade(number, grade, name);
				cout << "Set " << name << "'s grade on test " << number << " to " << grade << "." << endl;
				cout << endl;
				}
			catch(int e)
				{
				if(e == NOTFOUND)
					cout << "Could not grade " << name << ", no match in database." << endl;
				else if(e == DUPLICATE)
					cout << "Could not grade, ERROR" << endl;
				else if(e == OUTRANGE)
					cout << "Could not grade " << name << ", test or number or score out of range" << endl;
				cout << endl;
				}
			}

		else if(action == "DELETE")
			{
			getline(cin, name);
			try
				{
				t.del(name);
				cout << "Successfully deleted " << name << "." << endl;
				cout << endl;
				}
			catch(int e)
				{
				if(e == NOTFOUND)
					cout << "Could not delete " << name << ", no match in database." << endl;
				else if(e == DUPLICATE)
					cout << "Could not delete, ERROR" << endl;
				else if(e == OUTRANGE)
					cout << "Could not delete " << name << ", test number out of range ERROR" << endl;
				cout << endl;
				}
			}

		else if(action == "MEAN")
			{
			cin >> number;
			try
				{
				double mean = t.mean(number);
				if(mean != 0)
					cout << "The mean on test " << number << " is " << t.mean(number) << endl;
				else
					cout << "There are no nonzero means in the database for test " << number << endl;
				cout << endl;
				}
			catch(int e)
				{
				if(e == NOTFOUND)
					cout << "Could not get mean for test " << number << ", no match in database ERROR" << endl;
				else if(e == DUPLICATE)
					cout << "Could not get mean, ERROR" << endl;
				else if(e == OUTRANGE)
					cout << "Could not get mean for test " << number << ", test number out of range." << endl;
				else if(e == NONONZERO)
					cout << "Could not get mean for test " << number << ", no nonzero test scores." << endl;
				cout << endl;
				}
			}

		}
	cout << "Bye, thanks for using." << endl;
	}

#ifndef _LLH_
#define _LLH_
class HTable;
#include <iostream>
#include <string>
#include "list.h"
using namespace std;



class HTable
	{
	  private:
	    LL t[25013];
		 double scores[5];
		 int numbers[5];
	  public:
	    HTable();
	    ~HTable();
		 void add(string thename);
		 void grade(int number, double score, string thename);
		 void del(string thename);
		 double mean(int test);

	    int lookup(string name);
		 void redogrades(int test, double score);
		 void print();
	};

#endif

#include <iostream>
#include <string>
#include "htable.h"
using namespace std;

#define NOTFOUND 1
#define OUTRANGE 2
#define DUPLICATE 3

//Linked List constructor
LL::LL()
	{
	root = NULL;
	}

//Linked List destructor
LL::~LL()
	{
	delete root;
	}

//Add a name to the linked list
void LL::add(string thename)
	{
	if(root != NULL)
		{
		root -> add(thename);
		}
	else
		{
		root = new Node();
		root->setname(thename);
		}
	}

//Delete a name from the linked list
void LL::del(string thename, HTable *table)
	{
	if(root == NULL)
		throw NOTFOUND;
	else
		root->del(thename, NULL, root, table);
	}

//prints a name in the linked list, throws not found if name doesnt exist
void LL::print(string thename)
	{
	if(root != NULL)
		root->print(thename);
	else
		throw NOTFOUND;
	}

//prints the entire linked list
void LL::fullprint()
	{
	if(root != NULL)
		{
		root->fullprint();
		cout << endl;
		}
	}

//Sets the grade for thename on test number to score
void LL::grade(int number, double score, string thename)
	{
	if(number != 1 && number != 2 && number != 3 && number != 4 && number != 5)
		throw OUTRANGE;
	if(root != NULL)
		root->grade(number, score, thename);
	else
		throw NOTFOUND;
	}

//Node constructor
Node::Node()
	{
	next = NULL;
	grade1 = grade2 = grade3 = grade4 = grade5 = 0;
	}

//Node destructor
Node::~Node()
	{
	if(next != NULL)
		delete next;
	}

//Node add method, adds to THE END OF THE LINKED LIST
void Node::add(string thename)
	{
	if(name == thename)
		throw DUPLICATE;
	else if(next != NULL)
		next->add(thename);
	else
		{
		next = new Node();
		next -> setname(thename);
		}
	}

//Sets thenames grade on test number to score
void Node::grade(int number, double score, string thename)
	{
	if(thename == name)
		{
		if(number == 1)
			grade1 = score;
		else if(number == 2)
			grade2 = score;
		else if(number == 3)
			grade3 = score;
		else if(number == 4)
			grade4 = score;
		else if(number == 5)
			grade5 = score;
		}
	else if(next != NULL)
		{
		next->grade(number, score, thename);
		}
	else
		throw NOTFOUND;
	}

//prints the stuff for the thename
void Node::print(string thename)
	{
	if(name == thename)
		{
		cout << name << " : " << grade1 << " , " << grade2 << " , " << grade3 << " , " << grade4 << " , " << grade5 << endl;
		}
	else
		{
		if(next == NULL)
			throw NOTFOUND;
		else
			next->print(thename);
		}
	}

//prints the node and everything after it
void Node::fullprint()
	{
	cout << name << " : "<<grade1 <<" , "<< grade2<< " , "<< grade3 << " , " << grade4 << " , " << grade5 <<endl;
	if(next != NULL)
		next->fullprint();
	}

//deletes thename from the list. uses table to set the mean stuff so that will work
void Node::del(string thename, Node *parent, Node *&root, HTable *table)
	{
	if(name == thename)
		{
		if(parent != NULL)
			parent->setnext(next);
		else
			root=next;
		next = NULL;
		if(grade1 != 0)
			table->redogrades(1, grade1);
		if(grade2 != 0)
			table->redogrades(2, grade2);
		if(grade3 != 0)
			table->redogrades(3, grade3);
		if(grade4 != 0)
			table->redogrades(4, grade4);
		if(grade5 != 0)
			table->redogrades(5, grade5);
		delete this;
		}
	else if(next != NULL)
		{
		next->del(thename, this, root, table);
		}
	else
		{
		throw NOTFOUND;
		}
	}

//sets the name for this node
void Node::setname(string newname)
	{
	name = newname;
	}

//sets the next pointer for this node
void Node::setnext(Node *q)
	{
	next = q;
	}

/*int main()
	{
	LL h;
	try
		{
		h.add("hi");
		}
	catch(int e)
		{
		if(e == 1)
			cout << "notfound" << endl;
		else if(e == 2)
			cout << "outrange" << endl;
		else if(e == 3)
			cout << "duplicate" << endl;
		}
	h.fullprint();
	try
		{
		h.add("hi");
		}
	catch(int e)
		{
		if(e == 1)
			cout << "notfound" << endl;
		else if(e == 2)
			cout << "outrange" << endl;
		else if(e == 3)
			cout << "duplicate" << endl;
		}
	h.fullprint();
	try
		{
		h.add("bob");
		}
	catch(int e)
		{
		if(e == 1)
			cout << "notfound" << endl;
		else if(e == 2)
			cout << "outrange" << endl;
		else if(e == 3)
			cout << "duplicate" << endl;
		}
	h.fullprint();
	try
		{
		h.print("hi");
		}
	catch(int e)
		{
		if(e == 1)
			cout << "notfound" << endl;
		else if(e == 2)
			cout << "outrange" << endl;
		else if(e == 3)
			cout << "duplicate" << endl;
		}
	h.fullprint();
	try
		{
		h.del("hi");
		}
	catch(int e)
		{
		if(e == 1)
			cout << "notfound" << endl;
		else if(e == 2)
			cout << "outrange" << endl;
		else if(e == 3)
			cout << "duplicate" << endl;
		}
	h.fullprint();
	try
		{
		h.del("bob");
		}
	catch(int e)
		{
		if(e == 1)
			cout << "notfound" << endl;
		else if(e == 2)
			cout << "outrange" << endl;
		else if(e == 3)
			cout << "duplicate" << endl;
		}
	h.fullprint();
	}
	*/

#ifndef _LLP_
#define _LLP_
class LL;
class Node;
#include <iostream>
#include <string>
#include "htable.h"
using namespace std;

class LL
	{
		private:
			Node *root;
		public:
			LL();
			~LL();
			void add(string thename);
			void print(string thename);
			void fullprint();
			void grade(int number, double score, string thename);
			void del(string thename, HTable *table);
	};
	
class Node
	{
		private:
			string name;
			Node *next;
			double grade1, grade2, grade3, grade4, grade5;
		public:
			Node();
			~Node();
			void print(string thename);
			void grade(int number, double score, string thename);
			void del(string thename, Node *q, Node *&root, HTable *table);
			
			void setnext(Node *q);   
			void fullprint();
			void add(string thename);
			void setname(string newname);
			
	};
#endif

//CS222 Program 5, AVL tree with delete
//Shawn O'Neil
#include <iostream>
#include <string>
#include "tree1.h"
using namespace std;

#define EMPTYTREE 1
#define DUPLICATE 2
#define NOMATCH 3
#define OUTRANGE 4
#define NONONZERO 5

//tree constructor
Tree::Tree()
	{
	root = NULL;
	}

//tree destructor
Tree::~Tree()
	{
	delete root;
	}

//adds a node to the tree
void Tree::add(string name)
	{
	if(root == NULL)
		{
		root = new Node();
		root->setname(name);
		root->setparent(NULL);
		}
	else
		root->add(name, root);
	}

//sets a grade for the node of thename
void Tree::grade(int number, double score, string thename)
	{
	if(number != 1 && number != 2 && number != 3 && number != 4 && number != 5)
		throw OUTRANGE;
	if(score < 0)
		throw OUTRANGE;
	else if(root != NULL)
		root->grade(number, score, thename);
	else
		throw EMPTYTREE;
	}

//prints the tree
void Tree::print()
	{
	if(root != NULL)
		root->print();
	else
		throw EMPTYTREE;
	}

//deletes a node from the tree, with the name of name
void Tree::del(string name)
	{
	if(root != NULL)
		root->del(name, root);
	else
		throw EMPTYTREE;
	}

//gets the mean of all the nonzero particular exams in the tree
double Tree::mean(int exam)
	{
	if(exam != 1 && exam != 2 && exam != 3 && exam != 4 && exam != 5)
		throw OUTRANGE;
	else if(root != NULL)
		{
		double total =  root->gettotal(exam);
		double number = root->getnumber(exam);
		if(number != 0)
			return total/number;
		else
			throw NONONZERO;
		}
	else
		throw EMPTYTREE;
	}

//checks to see if the tree is empty. dont think its actually used...
bool Tree::empty()
	{
	return root == NULL;
	}

//node constructor
Node::Node()
	{
	parent = left = right = NULL;
	grade1 = grade2 = grade3 = grade4 = grade5 = 0;
	height = 0;
	}

//node destructor
Node::~Node()
	{
	if(left != NULL)
		delete left;
	if(right != NULL)
		delete right;
	//cout << "destructing: " << name << endl;
	}

//adds a name to the tree, *&root is used by by the computeheights method, for the AVL in case it needs to rotate and set a new root
void Node::add(string thename, Node *&root)
	{
	if(name != thename)
		{
		if(thename < name)
			{
			if(left != NULL)
				left->add(thename, root);
			else
				{
				left = new Node();
				left->setparent(this);
				left->setname(thename);
				left->computeheights(root);
				}
			}
		else
			{
			if(right != NULL)
				right->add(thename, root);
			else
				{
				right = new Node();
				right->setparent(this);
				right->setname(thename);
				right->computeheights(root);
				}
			}
		}
	else
		throw DUPLICATE;
	}

//sets the node n as a child of the current node
void Node::resetchild(Node *n)
	{
	string thename = n->getname();
	if(thename < name)
		left = n;
	else
		right = n;
	n->setparent(this);
	}

//sets the child with the name thename to null. used when deleting a node
void Node::setchildtonull(string thename)
	{
	//cout << "setting " << thename << " to null. left is " << endl;// left->getname() << " right is " << right->getname() << endl;
	if(left != NULL)
		if(left->getname() == thename)
			left = NULL;
	if(right != NULL)
		if(right->getname() == thename)
			right = NULL;
	}

//returns the name
string Node::getname()
	{
	return name;
	}

//returns a particular grade
double Node::getgrade(int number)
	{
	if(number == 1)
		return grade1;
	else if(number == 2)
		return grade2;
	else if(number == 3)
		return grade3;
	else if(number == 4)
		return grade4;
	else
		return grade5;

	}

//gets total number of nodes with nonzero grades from this point down
double Node::getnumber(int exam)
	{
	double total = 0;
	if(exam == 1 && grade1 != 0)
		total += 1;
	else if(exam == 2 && grade2 != 0)
		total += 1;
	else if(exam == 3 && grade3 != 0)
		total += 1;
	else if(exam == 4 && grade4 != 0)
		total += 1;
	else if(exam == 5 && grade5 != 0)
		total += 1;
	if(left != NULL)
		total = total + left->getnumber(exam);
	if(right != NULL)
		total = total + right->getnumber(exam);
	return total;
	}

//gets total of the grades for exam number exam from this point down
double Node::gettotal(int exam)
	{
	double mytotal = 0;
	if(exam == 1)
		mytotal = mytotal + grade1;
	else if(exam == 2)
		mytotal = mytotal + grade2;
	else if(exam == 3)
		mytotal = mytotal + grade3;
	else if(exam == 4)
		mytotal = mytotal + grade4;
	else if(exam == 5)
		mytotal = mytotal + grade5;
	if(left != NULL)
		mytotal = mytotal + left->gettotal(exam);
	if(right != NULL)
		mytotal = mytotal + right->gettotal(exam);
	return mytotal;
	}

//this is used to get the immediate successor of a node, short version used by delete
Node * Node::slideleft()
	{
	if(left == NULL)
		return this;
	else
		return left->slideleft();
	}

//deletes a node from the tree. if the node we want to delete is the parent,
//then it usees *&root  to set the root of the tree
void Node::del(string thename, Node *&root)
	{
	if(name == thename)
		{
		if(left == NULL && right == NULL)
			{
			if(parent != NULL)
				{
				parent->setchildtonull(name);
				parent->computeheights(root);
				}
			else
				root = NULL;
			delete this;
			}
		else if(left == NULL)
			{
			if(parent != NULL)
				{
				Node *q = parent;
				q->resetchild(right);
				q->computeheights(root);
				}
			else
				{
				root = right;
				right->setparent(NULL);
				}
			right = NULL;
			delete this;
			}
		else if(right == NULL)
			{
			if(parent != NULL)
				{
				Node *q = parent;
				q->resetchild(left);
				q->computeheights(root);
				}
			else
				{
				root = left;
				left->setparent(NULL);
				}
			left = NULL;
			delete this;
			}
		else
			{
			Node *p = right->slideleft();
			name = p->getname();
			grade1 = p->getgrade(1);
			grade2 = p->getgrade(2);
			grade3 = p->getgrade(3);
			grade4 = p->getgrade(4);
			grade5 = p->getgrade(5);
			p->del(p->getname(),root);
			}
		}
	else
		{
		if(thename < name)
			{
			if(left == NULL)
				throw NOMATCH;
			else
				left->del(thename, root);
			}
		else
			{
			if(right == NULL)
				throw NOMATCH;
			else
				right->del(thename, root);
			}
		}
	}

//sets the parent node
void Node::setparent(Node *n)
	{
	parent = n;
	}

//sets the name, duh
void Node::setname(string thename)
	{
	name = thename;
	}

//Returns the mean of all the nonzero scores on a particular test from this point down
double Node::mean(int exam)
	{
	double leftmean = 0;
	double rightmean = 0;
	double memean = 0;

	if(exam == 1)
		memean = grade1;
	else if(exam == 2)
		memean = grade2;
	else if(exam == 3)
		memean = grade3;
	else if(exam == 4)
		memean = grade4;
	else if(exam == 5)
		memean = grade5;

	if(right != NULL)
		rightmean = right->mean(exam);
	if(left != NULL)
		leftmean = left->mean(exam);

	int count = 0;
	if(leftmean != 0)
		count++;
	if(rightmean != 0)
		count++;
	if(memean != 0)
		count++;

	if(count == 0)
		return 0;
	return (leftmean+rightmean+memean)/count;
	}

// Sets the grade for a particular test for the node.
void Node::grade(int number, double score, string thename)
	{
	if(name == thename)
		{
		if(number == 1)
			grade1 = score;
		else if(number == 2)
			grade2 = score;
		else if(number == 3)
			grade3 = score;
		else if(number == 4)
			grade4 = score;
		else if(number == 5)
			grade5 = score;
		}
	else if(thename < name)
		{
		if(left != NULL)
			left->grade(number, score, thename);
		else
			throw NOMATCH;
		}
	else
		{
		if(right != NULL)
			right->grade(number, score, thename);
		else
			throw NOMATCH;
		}
	}

int Node::getheight()
	{
	return height;
	}

void Node::computeheights(Node *&root)
	{
	int lh = 0;
	int rh = 0;
	if(left == NULL && right == NULL)
		{
		height = 1;
		if(parent != NULL)
			parent->computeheights(root);
		}
	else
		{
		if(left != NULL)
			lh = left->getheight();
		if(right != NULL)
			rh = right->getheight();


		if(rh - lh > 1)	//too heavy on the right
			{
			//cout << "too heavy on right" << endl;
			int zigheight = 0;
			int dirheight = 0;
			if(right != NULL)
				if(right->left != NULL)
					zigheight = right->left->getheight();
			if(right != NULL)
				if(right->right != NULL)
					dirheight = right->right->getheight();
			if(zigheight > dirheight)		//needs a double rotation
				{
				right->rotateright(root);		//tell the those two to recomputer their heights w/out recursion
				Node *q = parent;
				rotateleft(root);
				if(q != NULL)
					q->computeheights(root);
				}
			else									//single rotation
				{
				Node *q = parent;
				rotateleft(root);				//add a part to recompute the heigts of the two invovled w/out recursion
				if(q != NULL)
					q->computeheights(root);
				}
			}
		else if(lh - rh > 1)	//too heavy on the left
			{
			//cout << "too heavy on left" << endl;
			int zigheight = 0;
			int dirheight = 0;
			if(left != NULL)
				if(left->right != NULL)
					zigheight = left->right->getheight();
			if(left != NULL)
				if(left->left != NULL)
					dirheight = left->left->getheight();
			if(zigheight > dirheight)		//double rotation
				{
				left->rotateleft(root);
				Node *q = parent;
				rotateright(root);
				if(q != NULL)
					q->computeheights(root);
				}
			else									//single rotation
				{
				Node *q = parent;
				rotateright(root);
				if(q != NULL)
					q->computeheights(root);
				}
			}
		else								//not heavier on either side, computer my height and pass it up
			{
			//cout << "still avl from here down" << endl;
			if(lh > rh)
				height = lh + 1;
			else
				height = rh + 1;
			if(parent != NULL)
				parent->computeheights(root);
			}
		}
		//if rh and lh are more than one off, rotate
		//but first check to see if the zigzag child is greater than the height of the direct grandchild
		//if so, rotate zigzag child up twice (i.e., rotate zigzag grandchild up(absolute recomputing the two involved), then have it call its new parent
		//compute heights (recursive) CASE DOUBLE ROTATION?
		//recompute the heigts of yourself and THEN the other one that you rotated (the two involved) based off of what
		//know their childrens heights are, but dont recurse this up the tree, so make a definatecomputeheights method.
	}

Node * Node::getleft(){
	return left;}

void Node::setleft(Node *n){
	left = n;}

Node * Node::getright(){
	return right;}

void Node::setright(Node *n){
	right = n;}

void Node::absheight(){
	int lh = 0;
	int rh = 0;
	if(left != NULL)
		lh = left->getheight();
	if(right != NULL)
		rh = right->getheight();
	if(rh > lh)
		height = rh + 1;
	else
		height = lh + 1;}

void Node::rotateleft(Node *&root){
	Node *q = parent;
	Node *r = right;
	Node *z = r->getleft();
	parent = r;
	r->setleft(this);
	right = z;
	if(z != NULL) z->setparent(this);
	if(q == NULL) root = r;
	else q->resetchild(r);
	r->setparent(q);
	absheight();
	r->absheight();
	//cout << "Rotated left. " << endl;
	}

void Node::rotateright(Node *&root){
	Node *q = parent;
	Node *l = left;
	Node *z = l->getright();
	parent = l;
	l->setright(this);
	left = z;
	if(z != NULL) z->setparent(this);
	if(q == NULL) root = l;
	else q->resetchild(l);
	l->setparent(q);
	absheight();
	l->absheight();
	//cout << "Rotated right. " << endl;
	}

//Print method for the node, inorder. Prints name, and grades.
void Node::print()
	{
	if(left != NULL)
		left->print();
	cout << name << " : " << grade1 << " , " << grade2 << " , " << grade3 << " , " << grade4 << " , " << grade5 << endl;//" height: " << height <<endl;
	if(right != NULL)
		right->print();
	}

int main(int argc, char ** argv)
	{
	cout << "Happy birthday euclid." << endl;
	Tree t;
	string action;
	int number;
	double grade;
	string name;
	while(cin >> action, cin)
		{
		cin.ignore();
		if(action == "ADD")
			{
			getline(cin, name);
			try
				{
				t.add(name);
				cout << "Successfully added " << name << "." << endl;
				cout << endl;
				}
			catch(int e)
				{
				if(e == NOMATCH)
					cout << "Could not add, ERROR" << endl;
				else if(e == EMPTYTREE)
					cout << "Could nto add, ERROR" << endl;
				else if(e == DUPLICATE)
					cout << "Could not add " << name << ". Name already exists." << endl;
				else if(e == OUTRANGE)
					cout << "Could not add, ERROR" << endl;
				cout << endl;
				}
			}

		else if(action == "PRINT")
			{
			try
				{
			//	cout << endl;
				cout << "Statistics: " << endl;
				t.print();
				cout << endl;
				}
			catch(int e)
				{
				if(e == NOMATCH)
					cout << "Could not print, ERROR" << endl;
				else if(e == EMPTYTREE)
					cout << "Database Empty, could not print." << endl;
				else if(e == DUPLICATE)
					cout << "Could not print, ERROR" << endl;
				else if(e == OUTRANGE)
					cout << "Could not print, ERROR" << endl;
				cout << endl;
				}
			}

		else if(action == "GRADE")
			{
			cin >> number;
			cin.ignore();
			cin >> grade;
			cin.ignore();
			getline(cin, name);
			try
				{
				t.grade(number, grade, name);
				cout << "Set " << name << "'s grade on test " << number << " to " << grade << "." << endl;
				cout << endl;
				}
			catch(int e)
				{
				if(e == NOMATCH)
					cout << "Could not grade " << name << ", no match in database." << endl;
				else if(e == EMPTYTREE)
					cout << "Could not grade " << name << ", database empty" << endl;
				else if(e == DUPLICATE)
					cout << "Could not grade, ERROR" << endl;
				else if(e == OUTRANGE)
					cout << "Could not grade " << name << ", test number out of range" << endl;
				cout << endl;
				}
			}

		else if(action == "DELETE")
			{
			getline(cin, name);
			try
				{
				t.del(name);
				cout << "Successfully deleted " << name << "." << endl;
				cout << endl;
				}
			catch(int e)
				{
				if(e == NOMATCH)
					cout << "Could not delete " << name << ", no match in database." << endl;
				else if(e == EMPTYTREE)
					cout << "Could not delete " << name << ", database empty" << endl;
				else if(e == DUPLICATE)
					cout << "Could not delete, ERROR" << endl;
				else if(e == OUTRANGE)
					cout << "Could not delete " << name << ", test number out of range ERROR" << endl;
				cout << endl;
				}
			}

		else if(action == "MEAN")
			{
			cin >> number;
			try
				{
				double mean = t.mean(number);
				if(mean != 0)
					cout << "The mean on test " << number << " is " << t.mean(number) << endl;
				else
					cout << "There are no nonzero means in the database for test " << number << endl;
				cout << endl;
				}
			catch(int e)
				{
				if(e == NOMATCH)
					cout << "Could not get mean for test " << number << ", no match in database ERROR" << endl;
				else if(e == EMPTYTREE)
					cout << "Could not get mean for test " << number << ", database empty" << endl;
				else if(e == DUPLICATE)
					cout << "Could not get mean, ERROR" << endl;
				else if(e == OUTRANGE)
					cout << "Could not get mean for test " << number << ", test number out of range." << endl;
				else if(e == NONONZERO)
					cout << "Could not get mean for test " << number << ", no nonzero grades in database." << endl;
				cout << endl;
				}
			}

		}
	cout << "Bye, thanks for using." << endl;
	}

#ifndef _LLH_
#define _LLH_
#include <iostream>
#include <string>
using namespace std;

class Tree;
class Node;

class Tree
	{
	  private:
	    Node *root;
	  public:
	    Tree();
	    ~Tree();
	    void add(string name);
	    void grade(int number, double score, string thename);
	    void print();
	    void del(string name);
	    double mean(int exam);
	    bool empty();
	};
	
class Node
	{
	  private:
	    Node *parent;
	    Node *left;
	    Node *right;
	    double grade1, grade2, grade3, grade4, grade5;
		 int height;
	    string name;
	  public:
	    Node();
	    ~Node();
	    void setparent(Node *n);
	    void setname(string thename);
	    void add(string thename, Node *&root);
	    double mean(int exam);
	    void grade(int number, double score, string thename);
	    void print();
	    void del(string thename, Node *&root);
	    string getname();
	    void setchildtonull(string thename);
	    Node * slideleft();
	    double getgrade(int number);
	    double getnumber(int exam);
	    double gettotal(int exam);
		 void computeheights(Node *&root);
		 void rotateleft(Node *&root);
		 void rotateright(Node *&root);
		 void absheight();
		 Node * getleft();
		 void setleft(Node *n);
		 Node * getright();
		 void setright(Node *n);
		 int getheight();
	    void resetchild(Node *n);
	};
	
#endif

//  Shawn O'Neil - Program 1 for CS222
//  Integer Division for very long strings.
//  Fixed the powers of 10 quotient bug

#include <iostream>
#include <string>
#include <assert.h>
using namespace std;

string add(string n, string d);
string subtract(string top, string bottom);
void RemLead0(string &s);
string RemLastChar(string s);
bool isSmaller(string one, string two);
bool checkAllNumbers(string n);
void divide(string top, string bot, string &q, string &r);

int main()
	{
 	cout << "Enter an integer:  ";
 	string n;
 	getline (cin,n);
 	cout << "Enter another integer:  ";
 	string d;
 	getline (cin,d);
	RemLead0(d);
	RemLead0(n);
	if(!checkAllNumbers(n))
		{
		cout << "Numerator contains non-number characters. Quitting. " << endl;
		return 1;
		}
	if(!checkAllNumbers(d))
		{
		cout << "Denominator contains non-number characters. Quitting. " << endl;
		return 1;
		}
	if(d == "0")
		{
		cout << "Divide by zero error. Quitting. " << endl;
		return 1;
		}
	string q = "";
	string r = "";
 	divide(n,d,q,r);
	cout << q << "  remainder  " << r << endl;
	}


// A method to divide two strings.
void divide(string top, string bot, string &q, string &r)
	{
	string quo = "";
	string temp = bot;
	if(top == bot)
		{
		q = "1";
		r = "0";
		return;
		}
	int counter = 0;
	while(isSmaller(temp, top))
		{
		temp = temp +"0";
		counter++;
		}
	temp = RemLastChar(temp);
	counter--;
	for(int i = counter; counter >= 0; counter--)
		{
		i = i;	//so my computer doesn't bitch about unused i
		int count = 0;
		while(isSmaller(temp, top))
			{
			top = subtract(top, temp);
			count++;
			}
		quo = quo + (char)(count + '0');
		temp = RemLastChar(temp);
		}
	q = quo;
	r = top;
	}

// Subtracts the bot string from the top string, checking to make sure the top string is bigger. Uses the nines compliment method.
string subtract(string top, string bot)
	{
	int lentop = top.length()-1;
	int lenbot = bot.length()-1;
	if(isSmaller(top, bot) && top != bot)
		cout << "Subtraction resulted in negative number. Not responsible for really messed up answers. " << endl;
	for(int i = 0; i < lentop - lenbot; i++)
		{
		bot = "0" + bot;
		lenbot++;
		}

	string nines = "";
	for(int i = 0; i < lenbot + 1; i++)
		{
		nines = nines + (char)((9 - (bot[i]-'0'))+'0');
		}
	string ninesplus1 = add(nines, "1");
	string subtotal = add(ninesplus1, top);
	string answer = subtotal.substr(1);
	RemLead0(answer);
	return answer;
	}

// Adds two numerical strings n, and d.
string add(string n, string d)
	{
	int len1 = n.length()-1;
	int len2 = d.length()-1;
	int carry = 0;
	string sum  = "";

	while(len1 >= 0 || len2 >= 0)
		{
		int digit1, digit2;

		if(len1 >= 0) digit1 = n[len1]-'0';
		else digit1 = 0;

		if(len2 >= 0) digit2 = d[len2]-'0';
		else digit2 = 0;

		int i = digit1+digit2+carry;
		if(i  > 9)							//or carry = i > 9 ? 1 : 0;
			carry = 1;						//OR carry = i / 10;
		else
			carry = 0;
		int digit = i%10;
		sum = ( (char)(digit + '0') )+ sum;
		len1--;
		len2--;
		}
	if(carry == 1)
		sum = '1' + sum;
	return sum;
	}
//Returns true if all characters in the string are numbers, false otherwise.
bool checkAllNumbers(string n)
	{
	for(int i = 0; i < (int)n.length(); i++)
		{
		if('0' > n[i] || n[i] > '9')
			return false;
		}
	return true;
	}

// Returns a string just like the one it takes, but without the last character.
string RemLastChar(string s)
	{
	string answer = "";
	for(int i = 0; i < (int)s.length() - 1; i++)
		{
		answer = answer + s[i];
		}
	return answer;
	}

// Checks to see if numerical string one is smaller than string two. If it is, it returns true.
// I could've sworn one could do this with built in c++ string libraries, but for some reason I couln't get it to work.
bool isSmaller(string one, string two)
	{
	int lenone = one.length();
	int lentwo = two.length();
	//cout << "one: " << one <<" len1: " << lenone << " two: "<< two <<" len2: " << lentwo << endl;
	if(lentwo > lenone)
		{
		//cout << one << " is smaller than " << two << endl;
		return true;
		}
	if(lenone == lentwo)
		{
		int i = 0;
		while(one[i] == two[i] && i != lenone-1)
			{
			i++;
			}
		if(one[i] <= two[i])
			{
			//cout << one << " is smaller than " << two << endl;
			return true;
			}
		else
			{
			//cout << one << " is not smaller than " << two << endl;
			return false;
			}
		}
	//cout << one << " is not smaller than " << two << endl;
	return false;
	}

// Removes the leading 0's from a string. If the string is all 0's, it leaves the last one on.
void RemLead0(string &s)
	{
	while(s[0] =='0')		/// or while(s != "0" && s[0] == '0')
		{
		if(s == "0") break;	//and take this out
		s = s.substr(1);
		}
	}

//CS222 Shawn O'Neil Program 2, Linked List Merge Sort
//Working Version
#include <iostream>
#include "ll.h"
using namespace std;


int main()
	{
	LL M;
	M.addfront("G");
	M.addfront("C");
	M.addfront("H");
	M.addfront("C");
	M.addfront("I");
	M.addfront("K");
	M.addfront("A");
	M.addfront("D");
	M.addfront("D");
	M.addfront("E");
	M.addfront("B");
	M.addfront("F");
	M.addfront("J");
	M.print();
	cout << endl;
	M.sort();
	M.print();
	}

LL::LL()
	{
	head = NULL;
	}

LL::~LL()
	{
	}

//Prints the Linked List
void LL::print()
	{
	if(head != NULL)
		head->print();
	}

//Splits the linked list from head down
void LL::split()
	{
	if(head != NULL)
		head =  head->split();
	}

//Sorts the linked list from head down
void LL::sort()
	{
	if(head != NULL)
		head = head->sort();
	}

//Adds a node to the front of the linked list.
void LL::addfront(string str)
	{
	if(head != NULL)
		head = new LLN(str, head);
	else
		head = new LLN(str, NULL);
	}


LLN::LLN(string str, LLN *n)
	{
	s = str;
	next = n;
	}

LLN::~LLN()
	{
	}

//Sorts the linked list from this node downward - doesn't work, probably broken merge
LLN * LLN::sort()
	{
	if(next == NULL)
		{
		return this;
		}
	else
		{
		LLN *list = this;
		LLN *one = split();
		one = one->sort();
		list = list->sort();
		list = list->merge(one);
		return list;
		}
	}

//Splits the linked list from this point downward Returns pointer to the head of other list
LLN * LLN::split()
	{
	if(next != NULL)
		{
		LLN *temp = next;
		next = temp->split();
		return temp;
		}
	else
		{
		return NULL;
		}
	}

//Merges two sorted linked lists, returns head of sorted linked list - I believe this is broken
LLN * LLN::merge(LLN *o)
	{
	if(o == NULL)
		{
		return this;
		}
	if(next == NULL)
		{
		if(s <= o->s)
			{
			next = o;
			return this;
			}
		}
	LLN *temp;
	if(s <= o->s)
		{
		temp = this;
		temp->next = o->merge(next);
		}
	else
		{
		temp = o;
		temp->next = merge(o->next);
		}
	return temp;
	}

//Prints the linked list from this point downward
void LLN::print()
	{
	cout << s << endl;
	if(next != NULL)
		next->print();
	}

#ifndef _LLH_
#define _LLH_
#include <string>
using namespace std;

class LL;
class LLN;

class LL
	{
	  private:
	LLN *head;
	  public:
	LL ();
	~LL ();
	void print ();
	void split();
	void addfront (string str);
	void sort (); //Sorts a LL in alphabetical order
	};

class LLN
	{
	  private:
  	LLN *next;
  	string s;
 	  public:
	LLN (string str, LLN *n);
	~LLN ();
	void print ();

	LLN *sort (); //Sorts the list from this point down;
                //returns the new head of this sorted list

	LLN *split (); //Splits the list in half.  If original list is
                 //1->2->3->4->5->... , the new lists are 1->3->5->...
                 //and 2->4->6->... this is still node 1 (of course) and
                 //the pointer to node 2 is returned.

	LLN *merge (LLN *o); //merges two sorted lists.  this is the head of
                       //one list; o is the head of the other.  The new
                       //head of the merged list is returned.
	};
#endif