IMT2021 Algoritmiske Metoder - Obligatorisk oppgave 4

algmet_oblig4.cpp

/**	Algmet Oblig 4
  *	Snorre Brecheisen (******)
  *	10HBSPA
  *************************************/
/** INCLUDES **/
#include <fstream>
#include <iostream>
using namespace std;
/** CLASSES/NODES **/
struct node {
	char key;
	node *l, *r, *under;
	int number, level;
	node (char* k, node *ll, node *rr, node* u, int num, int lv) {
		key = k[lv];
		l = ll;
		r = rr;
		under = u;
		number = num;
		level = lv;
}};
/** GLOBALS **/
int alphaStart = int('A');
int alphaEnd = int('Z');
char keys[2] = {alphaStart-1, alphaStart-1};
node *z = new node(keys, z, z, z, 0, 0);
node *tree = new node(keys, z, z, z, 0, 0);
/** FUNCTION DECLARATIONS **/
void traverse(node *n, ofstream* out);
void print(node *n, ofstream* out);
void readSet(char* c, ifstream* in);
void insert(char* c, int i, node *top);
/** MAIN **/
int main () {
	ifstream* in = new ifstream("OPPG_17.DTA");	// Infile
	ofstream* out = new ofstream("OPPG_17.RES");// Outfile
	char *chars = new char[2];
	node *temp = NULL;					// Create temp nodes
	node *temp2 = NULL;
	while (!((*in).eof())) {			// Read our infile
		readSet(chars,in);
		insert(chars, 0, tree);
	}
	in->close();						// Close the infile
	traverse (tree, out);
	return 0;
}
/** FUNCTIONS **/
void readSet(char* c, ifstream* in) {	// Reads a set from the file.
	char temp = (*in).peek();			// Peek at the next character
	if(temp == '\n') {					// Skip it if '\n'
		(*in).ignore();
	}
	(*in).get(c,3);						// Read the set to c
	(*in).ignore();
}
void insert(char* c, int i, node *top) {// Inserts a set into the tree
	node *hi = NULL;
	node *lo = top;
	char k = c[i];
	while (lo != z && lo->key != k) {	// Traverse the tree looking for
		hi = lo;						// k
		if (k < lo->key) {
			lo = lo->l;
		} else if (k > lo->key) {
			lo = lo->r;
	}}
	if (lo == z) {						// If we've reached the end
		lo = new node (c, z, z, z, 1, i);//Make a new node here
		if (k < lo->key) {
			hi->l = lo;
		} else if (k > lo->key) {
			hi->r = lo;
		}
		if (i == 0) {					// If in top tree
			lo->under = new node(keys, z, z, z, 0, 0);// Create
			insert(c, i+1, lo->under);	// new subtree and insert
		}
	} else {
		if (i == 0) {					// If in top tree
			insert(c, i+1, lo->under);	// Insert a node in subtree
		} else {
			lo->number++;				// Add to the count for this combination
}}}
void traverse (node *n, ofstream *out) {// Traverses nodes and fetches print
	if (n != z) {
		traverse (n->l, out);
		print (n, out);
		traverse (n->r, out);
}}
void print (node *n, ofstream *out) {	// Prints node data
	if (n->under != z) {
		(*out) << n->key << endl;
		traverse (n->under, out);
	} else {
		(*out) << '\t' << n->key << '\t' << n->number << endl;
}}