/* ============== BINARY TREE PROGRAM ============== ELEC1010 Assignment By Martin Spikings and Alex Wood This program takes a filename at the command-line, puts its contents in an alphabetically-sorted binary search tree and then prints the data in reverse alphabetical order, as well as analysing the time taken to find a given word in the tree. Tested and working with: - gcc 3.4.6 on Red Hat (2.6.9-42) - gcc 4.0.1 on OS X Tiger 10.4.9 (Darwin 8.9.1) - gcc 4.1.2 (djgpp) on XP Pro SP2 (2600)*/#include <stdio.h>#include <stdlib.h>#include <string.h>#include <sys/stat.h>#include <time.h>int debugMode = 0; /* Needs to be here to shadow to all these nice functions *//*This is what a data node looks like, children.*/struct node { char* datum; /*a clever thing to do is to have a pointer here, and store the data on the heap*/ int count; /*an 'instances' count rather than duplicating nodes. Improves lookup times for a slight overhead when placing nodes. Used as a depth record for query nodes.*/ int depth; /* not used by data nodes, which is a bit wasteful, but better than having a whole new set of stuff for query nodes */ struct node* left; struct node* right;};/* Need an initial count variable as for data nodes this is '1', and for query nodes, which record the depth at which it was found, '0'. */struct node* createNode (char* newDatum, int initialCount) { struct node* newNode; newNode = malloc (sizeof (struct node)); if (newNode == NULL) { fprintf (stderr, "[ERROR] No memory available. Processing cannot continue. Try restarting your computer.\n\n"); exit (EXIT_FAILURE); } /* Copy over all the given properties to our node*/ newNode->datum = newDatum; newNode->count = initialCount; newNode->depth = 0; /* This will be inserted as a leaf, having no children at first */ newNode->left = NULL; newNode->right = NULL; if (debugMode) { printf ("[DEBUG] Node created.\n\n"); } return newNode;}/*This function adds a datum to a specified tree. Wait, it connects an already-formed node. That way, we don't duplicate the node-creation stuff (malloc and all that).*/int placeNode (struct node* newNode, struct node* thisNode) { if (debugMode) { printf ("[DEBUG] placeNode() is starting at 0x%x to try to find a home for the node at 0x%x...\n\n", thisNode, newNode); } if (thisNode->datum == NULL) { /*Put the datum in the root if we start there in an empty (null-string) tree.*/ if (debugMode) { printf ("[DEBUG] Trying to put '%s' in the root.\n\n", newNode->datum); } thisNode->datum = newNode->datum; thisNode->count = newNode->count; thisNode->depth = newNode->depth; return 1; } else { if (debugMode) { printf ("[DEBUG] The root is not empty. Hunting for space...\n\n"); } if (strcmp (newNode->datum, thisNode->datum) == 0) { /* That was easy. The word's already in the tree. Don't store it again, just use the count. */ thisNode->count = thisNode->count + 1; } else if (strcmp (newNode->datum, thisNode->datum) > 0) { if (thisNode->right) { /*If there's a node to the right, go there.*/ if (debugMode) { printf ("[DEBUG] Going right at '%s' with '%s'.\n", thisNode->datum, newNode->datum); } placeNode (newNode, thisNode->right); return 0; } else { /*Otherwise, we've found our space.*/ thisNode->right = newNode; if (debugMode) { printf ("[DEBUG] Added leaf '%s' to the right of '%s'.\n\n", newNode->datum, thisNode->datum); } return 1; } } else { if (thisNode->left) { /*If there's a node to the left, go there.*/ if (debugMode) { printf ("[DEBUG] Going left at '%s' with '%s'.\n", thisNode->datum, newNode->datum); } placeNode (newNode, thisNode->left); return 0; } else { /*Otherwise, we've found our space.*/ thisNode->left = newNode; if (debugMode) { printf ("[DEBUG] Added leaf '%s' to the left of '%s'.\n\n", newNode->datum, thisNode->datum); } return 1; } } }}/*This prints the contents of the search tree, in ascending or descending order, to the named destination stream if toFile, otherwise stdout (order specified by direction).*/int traverse (struct node* thisNode, int direction, int toFile, FILE* destination) { /*Modes are '1' for forward, '2' for backward.*/ char nodeDescriptionLine[50]; if (thisNode->depth == 0) { /* A data node, or a query node for a datmu which doesn't appear in the data tree. Either way, depth is invalid/unnecessary. */ strcpy (nodeDescriptionLine, "\"%s\" (x%d)\n"); } else { strcpy (nodeDescriptionLine, "\"%s\" appears %d time(s) at a depth of %d node(s).\n"); } if (direction == 1) { /* Left, print, right. Ascending order. */ if (thisNode->left != NULL) { traverse (thisNode->left, 1, toFile, destination); } if (toFile) { /* Wish I could find a name for a/the FILE pointer to stdout */ fprintf (destination, nodeDescriptionLine, thisNode->datum, thisNode->count, thisNode->depth); } else { /* Not very pretty, but can't find a better way above the level of file descriptors */ printf (nodeDescriptionLine, thisNode->datum, thisNode->count, thisNode->depth); } if (thisNode->right != NULL) { traverse (thisNode->right, 1, toFile, destination); } } else if (direction == 2) { /* Go right first, 'cos we're doing it in descending order */ if (thisNode->right != NULL) { traverse (thisNode->right, 2, toFile, destination); } if (toFile) { /* Wish I could find a name for a/the FILE pointer to stdout */ fprintf (destination, nodeDescriptionLine, thisNode->datum, thisNode->count, thisNode->depth); } else { /* Not very pretty, but can't find a better way above the level of file descriptors */ printf (nodeDescriptionLine, thisNode->datum, thisNode->count, thisNode->depth); } /*Left last.*/ if (thisNode->left != NULL) { traverse (thisNode->left, 2, toFile, destination); } } return 1;}/*Runs through the whole data tree, and for each node, runs through the whole query tree to check the node against the data being searched for. fixedQueryNode forbids the subroutine from wandering around trying to find a more left-most*/int locate (struct node* thisDataNode, struct node* thisQueryNode, int* depth, int fixedQueryNode, long int* queryNodeCount, long int* dataNodeCount, long int* queryNodeMatchedCount, long int* depthSum, int* depthMax, double* lookupTime) { int strcmpResult; /* No need to do the comparison three times. Imagine that's more expensive than creating and assigning a variable. */ int startTime; int finishTime; /* If we can go left in the query tree, and have found the present query word (or a definite lack of it in the data tree), move on to the next query node, otherwise stick with the same query and go through the data tree again */ if (fixedQueryNode == 0 && thisQueryNode->left != NULL) { *queryNodeCount = *queryNodeCount + 1; locate (thisDataNode, thisQueryNode->left, depth, 0, queryNodeCount, dataNodeCount, queryNodeMatchedCount, depthSum, depthMax, lookupTime); } /* Run through the data tree with this particular query node and do a little timing. */ startTime = clock (); strcmpResult = strcmp (thisQueryNode->datum, thisDataNode->datum); /* Do the important bit! */ finishTime = clock (); /* Update some statistics */ *lookupTime = *lookupTime + ((finishTime - startTime) / CLOCKS_PER_SEC); *dataNodeCount = *dataNodeCount + 1; /* Records how many data nodes have been examined, in total, for the whole query. */ if (*depth > *depthMax) { /* A new low is reached. */ *depthMax = *depth; } if (debugMode) { printf ("[DEBUG] Current query node: \"%s\".\n[DEBUG] Current data node: \"%s\".\n\n", thisQueryNode->datum, thisDataNode->datum); } if (strcmpResult == 0) { /* Found this query node in the data tree! Gejubel. */ if (debugMode) { printf ("[DEBUG] Found %d instance(s) of query node \"%s\" in data tree at a depth of %d levels.\n\n", thisDataNode->count, thisDataNode->datum, *depth); } thisQueryNode->count = thisDataNode->count; /* Copying the instances count from the data tree to the query tree */ thisQueryNode->depth = *depth; /* Recording the depth of this particular node */ *depthSum = *depthSum + thisQueryNode->depth; /* Used for some extra statistics */ *queryNodeMatchedCount = *queryNodeMatchedCount + 1; /* Update the success rate figure. */ } else if (strcmpResult > 0 && (thisDataNode->right != NULL)) { /* The query datum belongs to the right, if it's anywhere. */ *depth = *depth + 1; locate (thisDataNode->right, thisQueryNode, depth, 1, queryNodeCount, dataNodeCount, queryNodeMatchedCount, depthSum, depthMax, lookupTime); *depth = *depth - 1; } else if (thisDataNode->left != NULL){ /* Present data node is too 'big'. Go left if there's anything there. */ *depth = *depth + 1; locate (thisDataNode->left, thisQueryNode, depth, 1, queryNodeCount, dataNodeCount, queryNodeMatchedCount, depthSum, depthMax, lookupTime); *depth = *depth - 1; } /* Now we've looked at the present data node. If we can go right in the query tree, and aren't going through the data tree some more with the same query node, start querying a different word. */ if (fixedQueryNode == 0 && thisQueryNode->right != NULL) { *queryNodeCount = *queryNodeCount + 1; locate (thisDataNode, thisQueryNode->right, depth, 0, queryNodeCount, dataNodeCount, queryNodeMatchedCount, depthSum, depthMax, lookupTime); }}/*Retrives the contents of the specified file and adds it to the tree.*/int getFile (char* wordFilePath, struct node* rootNode, int initialCount) { FILE* wordFile; struct stat wordFileProperties; /* Will be used to determine the size and such */ char* fileBuffer; char fileChar; char* thisWord; char* thisChar; struct node* thisNode; if ((wordFile = fopen (wordFilePath, "r")) != 0) { /*If the file was openable...*/ stat (wordFilePath, &wordFileProperties); if (debugMode) { printf ("[DEBUG] Opened '%s' (%d bytes) successfully.\n\n", wordFilePath, wordFileProperties.st_size); } /* A nice helpful warning or two! */ if (debugMode && wordFileProperties.st_size > 20480) { /*Debug mode is pretty verbose! Running this program on its own source results in about 9MiB of data being put to stdout. Give fair warning, and a little pause to highlight it.*/ fprintf (stderr, "[WARNING] Debug mode is on and a non-trivial file is being processed. This will result in considerable output.\n\n"); /* Revise warning size with some experimentation*/ sleep (10); } if (wordFileProperties.st_size > 104857600) { fprintf (stderr, "[WARNING] A large file is being processed. This may take a minute.\n\n"); /* A bit of an arbitrarily-picked file size, yes. Still, a little more helpful than just hanging for a while with no warning for big files. */ } fileBuffer = malloc (wordFileProperties.st_size); /* If we only use spaces and line-breaks for word-delimiting, and don't store both spaces and terminators, we don't need more memory than the size of the file */ /* Just in case there's no memory allocatable, fail gracefully. */ if (fileBuffer == NULL) { fprintf (stderr, "[ERROR] Not enough memory available to read the input file into memory. Is it exceptionally large? Consider breaking it up.\n\n"); exit (EXIT_FAILURE); } fileChar = '\0'; /* For the present character, before it gets chucked on the heap */ thisWord = fileBuffer; /* Points to where we'll start putting words */ thisChar = fileBuffer; /* New word and a new character too, you see */ while (!feof (wordFile)) { fileChar = fgetc (wordFile); if (fileChar > 32) { /* Use all non-printing characters, tabs, spaces, and line breaks as delimiters, and don't write them out.*/ if (debugMode) { printf ("[DEBUG] Adding character '%c' at 0x%x...\n", fileChar, thisChar); } /* This results in a lot of output in debug mode! */ *thisChar = fileChar; thisChar++; if (debugMode) { printf ("[DEBUG] Word is now \"%s\"...\n\n", thisWord); } /* This also resutls in a lot of output in debug mode. */ } else if (thisChar > thisWord) { *thisChar = '\0'; /* Add end-of-string terminator.*/ if (debugMode) { printf ("[DEBUG] Creating node with full word (\"%s\")...\n", thisWord); } /*Make it a n,ode, and add it to the tree. */ thisNode = createNode (thisWord, initialCount); if (debugMode) { printf ("[DEBUG] Placing node...\n\n"); } placeNode (thisNode, rootNode); thisChar++; /* Added the terminator, remember. Don't overwrite it with the beginning of the next word. */ thisWord = thisChar; /* Where to start the next word */ if (debugMode) { printf ("[DEBUG] Incremented 'thisWord' pointer to 0x%x.\n\n", thisWord); } } } return 1; } else { fprintf (stderr, "[ERROR] Couldn't open the file '%s'. Does it definitely exist?\n\n", wordFilePath); exit (EXIT_FAILURE); }}int writeReport (char* outputPath, struct node* queryRootNode, long int queryNodeCount, long int dataNodeCount, long int queryNodeMatchedCount, long int depthSum, int depthMax, double lookupTime) { /* This function has the query result written to a file instead of stdout if an output file is specified. */ FILE* outputFile; if (debugMode) { printf ("[DEBUG] Opening output file for writing...\n\n"); } outputFile = fopen (outputPath, "w"); if (outputFile != NULL) { fprintf (outputFile, "Query results\n=============\n\n"); /*The traverse function will write the body of the result to the file for us. The query itself was run by locate() before we were called, and the results put in the query tree. */ traverse (queryRootNode, 1, 1, outputFile); /* All we actually prnit to the file, really, is these nice statistics provided by locate() in main. That's the function that runs the query, you see. */ fprintf (outputFile, "\n\nStatistics\n==========\n\nA total of %d word(s) queried, resulting in %d data node lookup(s).\nThis is an average of %d lookup(s) per query word, or an efficency\nof %.1f%% over the whole query. The average query result was found at\na depth of %.1f nodes, with the deepest result found at level %d.\n\nIn all, %d query word(s) were not found (%.1f%% of all query words) in\nthe data file. A total time of %.1fms was spent running comparisons.\n", queryNodeCount, dataNodeCount, dataNodeCount / queryNodeCount, 100 * ((float) queryNodeCount / (float) dataNodeCount), (float) depthSum / (float) queryNodeMatchedCount, depthMax, (queryNodeCount - queryNodeMatchedCount), 100 * (((float) queryNodeCount - (float)queryNodeMatchedCount) / (float) queryNodeCount), lookupTime * 1000); fclose (outputFile); if (debugMode) { printf ("[DEBUG] Closed output file."); } return 1; } else { fprintf (stderr, "[WARNING] Couldn't open the specified output file for writing the query result. Do you have permissions to write to the specified path?\n\n"); /* Silly user. */ return 0; }}int main (int argc, char* argv[]) { /* Create an empty tree for the data. */ struct node* rootNode = malloc (sizeof (struct node)); if (rootNode == NULL) { fprintf (stderr, "[ERROR] No memory available. Processing cannot continue. Try restarting your computer.\n\n"); /* Impressed if you got this. */ exit (EXIT_FAILURE); } /* A nice empty node. */ rootNode->datum = NULL; rootNode->left = NULL; rootNode->right = NULL; if (debugMode) { printf ("[DEBUG] Root created at 0x%x.\n\n", rootNode); } /*See if a file has been passed, and if it has, read it in.*/ if (argc > 1) { /* We're going to need to note down where to find the various arguments. */ int dataFileCount = 0; /* Let's kick up if the user tries to specify more than one data file */ int queryFileCount = 0; /* ... or query file. */ int outputFileCount = 0; /* ... */ int dataFilePosition = 0; /* Store the offsets in the parameter array of the files for data*/ int queryFilePosition = 0; /* ... and query. */ int outputFilePosition = 0; if (argc > 8) { /* Remember not to count the program call itself as an argument in the description. */ fprintf (stderr, "[WARNING] More than seven parameters were passed. Only seven parameters are used, at most, simultaneously. If you are trying to process a file with a space in the filename, did you remember to put it in quote marks?\n\n", argc); } /* Scan through and examine the input parameters */ int i; for (i = 0; i < argc; i++) { if (strcmp ("--h", argv[i]) == 0 || strcmp ("/?", argv[i]) == 0) { /* If they asked for the syntax, don't bother actually doing anything. Print it and quit straight away. */ printf ("\nSorts the contents of a text file with the option of comparing its contents against a query file. Gives binary tree statistics.\n\n %s -i \"data file\" [-d] [-o \"output report file\"] [-q \"query file\"]\n\n i: path to a text file with words delimited by any unprintable characters\n\n d: debug mode\n o: path for an output file to be created/overwritten with a report\n q: path to a query file containing search strings, similarly delimited\n\n", basename (argv[0])); exit (EXIT_SUCCESS); } if ((strcmp ("-d", argv[i])) == 0 && i != dataFilePosition && i != queryFilePosition && i != outputFilePosition) { /* Debug mode flag */ debugMode = 1; printf ("[DEBUG] Debug mode activated.\n\n"); } if ((strcmp ("-i", argv[i])) == 0 && i != queryFilePosition && i != outputFilePosition) { /* The last bit is to check that we're not going to get confused by having a query file called "-i". Similarly in the other bit.*/ /* Input file parameter prefix */ if (debugMode) { printf ("[DEBUG] Found a data file argument prefix at offset %d.\n\n", i); } if (i < (argc - 1)) { if (dataFileCount == 0) { dataFileCount = 1; dataFilePosition = i + 1; /* Store the position of the actual input argument. */ } else { fprintf (stderr, "[ERROR] More than one data file specified! Did you mean to specify both a query and data file? Check the syntax by running with just --h.\n\n"); exit (EXIT_FAILURE); } } else { /* The prefixing flag is there, but a path wasn't given */ fprintf (stderr, "[WARNING] Input file argument without a path was given. Did you forget to add it?\n\n"); } } if ((strcmp ("-q", argv[i])) == 0 && i != dataFilePosition && i != outputFilePosition) { /* If the data file is "-q", let's not try to parse the next argument as a query file!*/ /* Query file parameter prefix */ if (debugMode) { printf ("[DEBUG] Found a query file argument prefix at offset %d.\n\n", i); } if (i < (argc - 1)) { if (queryFileCount == 0) { queryFileCount = 1; queryFilePosition = i + 1; /* Store the position of the query file string.*/ } else { fprintf (stderr, "[ERROR] More than one query file specified! Did you mean to specify both a query and data file? Check the syntax by running with just --h.\n\n"); exit (EXIT_FAILURE); } } else { /* The prefixing flag is there, but a path wasn't given! */ fprintf (stderr, "[WARNING] A query file argument without a path was given. Did you forget to add it?\n\n"); } } if ((strcmp ("-o", argv[i])) == 0 && i != dataFilePosition && i != queryFilePosition) { /* Prefix for the output file for the query report. */ if (debugMode) { printf ("[DEBUG] Found an output file argument prefix at offset %d.\n\n", i); } if (i < (argc - 1)) { if (outputFileCount == 0) { outputFileCount = 1; outputFilePosition = i + 1; /* Store the position of the output file argument. */ } else { fprintf (stderr, "[ERROR] More than one output file specified! Check the syntax by running with just --h.\n\n"); exit (EXIT_FAILURE); } } else { /* The prefixing flag is there, but a path wasn't given */ fprintf (stderr, "[WARNING] An output file argument without a path was given. Did you forget to add it?\n\n"); } } } if (dataFileCount == 0) { fprintf (stderr, "[ERROR] No input file specified. Check the syntax by running with --h.\n\n"); exit (EXIT_FAILURE); /* Whoops. Silly you. */ } /* This is where the real processing begins. */ if (getFile (argv[dataFilePosition], rootNode, 1)) { /* Try and read the data file in to the tree. Exciting. */ printf ("Tree created from the input file. Here is the tree, printed in-order, in reverse. Words are followed by the occurence count in parentheses.\n\nThe tree\n========\n\n"); traverse (rootNode, 2, 0, NULL); /* Print the tree. */ } if (queryFileCount == 1) { /* Running locate too. with the query file. */ /* Create an empty tree for the query. */ struct node* queryRootNode; queryRootNode = malloc (sizeof (struct node)); if (queryRootNode == NULL) { fprintf (stderr, "[ERROR] No memory available. Processing cannot continue. Try restarting your computer.\n\n"); exit (EXIT_FAILURE); } queryRootNode->datum = NULL; queryRootNode->left = NULL; queryRootNode->right = NULL; if (debugMode) { printf ("[DEBUG] Query file root created at 0x%x.\n\n", rootNode); } /* Read the query file to its tree. */ if (getFile (argv[queryFilePosition], queryRootNode, 0)) { /* This is pretty much all for statistics-gleaning by chucking this lot around between a couple of subroutines. */ int depth = 1; /* The datum at the root node has a depth of 1, not 0. */ long int queryNodeCount = 1; /* /* Query node should be initially one, as only incremented when moving node,... */ long int dataNodeCount = 0; /*... while data node incremented on each comparison (so root node causes incrementation) */ long int queryNodeMatchedCount = 0; /* To keep track of how many query nodes we successfully locate. */ long int depthSum = 0; /* Will be used to give averages and such. Sum of the depths of all successfully-located query terms found in the data tree.*/ int depthMax = 0; /* The deepest level probed in the data tree. */ double lookupTime = 0; /* Time taken to do comparisons. Usually absolutely miniscule, but a nice statistic all the same. */ struct node* queryThisNode = queryRootNode /* This is where we start the query. */; if (debugMode) { printf ("[DEBUG] Running query...\n"); } /* Now to traverse the query tree, and for each node, look for its datum in the data tree. */ locate (rootNode, queryRootNode, &depth, 0, &queryNodeCount, &dataNodeCount, &queryNodeMatchedCount, &depthSum, &depthMax, &lookupTime); /* If we have an output file for the query result, write it there, otherwise print it. */ if (outputFileCount == 1) { /* Chuck stuff to the given output file. */ writeReport (argv[outputFilePosition], queryRootNode, queryNodeCount, dataNodeCount, queryNodeMatchedCount, depthSum, depthMax, lookupTime); } else { /* Da da da daaaaa. */ printf ("\n\nQuery results\n=============\n\n"); traverse (queryRootNode, 1, 0, NULL); printf ("\n\nStatistics\n==========\n\nA total of %d word(s) queried, resulting in %d data node lookup(s).\nThis is an average of %d lookup(s) per query word, or an efficency\nof %.1f%% over the whole query. The average query result was found at\na depth of %.1f nodes, with the deepest result found at level %d.\n\nIn all, %d query word(s) were not found (%.1f%% of all query words) in\nthe data file. A total time of %.1fms was spent running comparisons.\n\n", queryNodeCount, dataNodeCount, dataNodeCount / queryNodeCount, 100 * ((float) queryNodeCount / (float) dataNodeCount), (float) depthSum / (float) queryNodeMatchedCount, depthMax, (queryNodeCount - queryNodeMatchedCount), 100 * (((float) queryNodeCount - (float)queryNodeMatchedCount) / (float) queryNodeCount), lookupTime * 1000); } } } } else { fprintf (stderr, "[ERROR] No parameters given. Check the syntax by running with --h.\n\n"); exit (EXIT_FAILURE); }}