ECS 60 Homework 5: Operation Miraq Salvation -- Warrantless Wiretapping

Due: Sunday, June 7 at 2200 hours.

Hand out: my reference program. Sample input (small file, medium file, large file). They are also available at ~cs60/homework/5/ on CSIF Linux machines, in case you don't have enough disk quota to store them in your home directory.

Hand in: Makefile and all the necessary program files. When I type "make" with no command line argument, your Makefile should create an executable named avl. Your program should compile on CSIF Linux machines and have the same input/output behavior as my reference program.

Note: This is a group homework. You should work in groups of two. Only one person from each group shall hand in all the files.
On the first two lines of Makefile, write each team member's email username at ucdavis.edu, last name, and first name (one person per line) as comments. For example:
# bsimpson; Simpson, Bart
# mburns; Burns, Montgomery
If you fail to follow this specification, you will lose points.

Description

In this last episode of the Miraq trilogy, after a quagmire decisive victory, the Mamerican forces planned to occupy peace keep in Miraq for the next 500 5 years. To monitor terrorist activities, the Commanding General of the Mamerican forces wanted to wiretap on all Internet communications to detect words that are used at abnormal frequencies.

Build an AVL tree to store words and their frequencies. Store each frequency in a 4-byte unsigned integer. Prevent the unsigned integer from overflowing. In other words, if a frequency grows beyond the maximum value of a 4-byte unsigned integer, cap the frequency at the maximum value.

Read input from cin and write output to cout.

Input: The input contains words separated by delimiters.

• A word is a continuous sequence of one or more uppercase or lowercase letters ('A'-'Z' and 'a'-'z'). A word may contain mixed uppercase and lowercase letters. All the other characters are considered delimiters and should be ignored.
• Words are case insensitive. When comparing the order of two Words, use the lexicographical order, e.g., by using strcasecmp().
• No word is longer than 1024 characters. If the input contains a sequence of more than 1024 letters, split the sequence into words of 1024 letters, except for the last word, which may be shorter than 1024 letters.
• Insert words into the AVL tree in the order by which they first appear in the input. For example, if the word Miraq first appears before the first occurrence of the word Mamerica, then insert Miraq into the AVL tree before inserting Mamerica.

Output:

• In the first section, on each line, print:
  • a word in lowercase letters, followed by one space character, and
  • the frequency of the word, followed by one space character, and
  • the balance factor of the AVL tree node containing the word.

  Order the lines in the lexicographical order of the words.

• In the second section, print the height of the AVL tree (that contains all the words from the input), followed by a newline character. The height of an empty tree is 0, and the height of a tree with a single node is 1.

The output of your program must exactly match the output of my reference program.

You may use Program 10.3. However, you need to complete its missing part and fix a bug in it. You may not use STL except the string class.