submit itec320-01 huffman_pkg.ads huffman_pkg.adb tree_pkg.adb tree_pkg.ads code_strings.adb
Now available: You can see an example of this program at assignment checker (which uses gnoga to integrate the GUI, web server, and problem solution). On-campus or VPN session required.
In this assignment you will work with pointers, trees, and Huffman codes. You will implement procedures
to_huffman and to_ascii that convert between Huffman and ASCII representations of a string.
Huffman codes are used for compressing data by using shorter bit strings to represent more frequent characters and
longer bit strings for less frequent ones. In this assignment you will find the frequency of the characters of a
string, then create the code for that string, and finally convert the string to its Huffman encoding.
Original String: "The cat in the Hat" Frequency and character encodings: : 4 00 H: 1 11010 T: 1 11011 a: 2 010 c: 1 0110 e: 2 100 h: 2 101 i: 1 0111 n: 1 1100 t: 3 111 Encoded string: 110111011000001100101110001111100001111011000011010010111 With spacing : 11011 101 100 00 0110 010 111 00 0111 1100 00 111 101 100 00 11010 010 111The encoded string would take about 57 bits vs 18*8=144 bits for ASCII. The original string contains four spaces (coded as 00), three 't's (coded as 111), etc. To help the human reader, the second encoded string includes spaces between the bits for the individual letters. As you can see, this is a prefix code: no codeword is a prefix of another word (hmm, prefix-free would be a better name). Having a prefix code is important for converting coded strings back into ASCII.
subtype Bit is Character range '0' .. '1'; -- ASCII String subtype A_String is String; -- Huffman String subtype H_String is String with dynamic_predicate => (for all c of H_String => c in Bit); -- Readable Huffman String subtype RH_String is String with dynamic_predicate => (for all c of RH_String => c in Bit | ' '); type A_String_Ptr is access A_String; type H_String_Ptr is access H_String; type Frequency_Table is array (Character) Of Natural; type Huffman_Table is array (Character) Of H_String_Ptr; function create_freq_table (s : A_String) return Frequency_Table; function create_huffman_table (s : A_String) return Huffman_Table; function to_huffman (s: A_String; c : Huffman_Table; spaces : Boolean := false) return RH_String; function to_huffman (s: A_String; spaces : Boolean := false) return RH_String with post => to_huffman'result = to_huffman(s, create_huffman_table(s), spaces) and (( spaces and to_huffman'result in RH_String) or (not spaces and to_huffman'result in H_String)); function to_ascii (s : H_String; ft : Frequency_Table) return A_String with post => to_huffman(to_ascii'result, false) = s; -- You might want to add this procedure to your package: -- Print the Huffman tree for s -- procedure print_tree (s: A_String); end huffman_pkg;The notation
to_huffman'result, for example, refers to the result returned by the function
to_huffman. In to_huffman'result, spaces are included between letters when the parameter
true. The subtypes A_String and H_String would be better if they were defined as new types, but subtypes are simpler! Of course, to_ascii and to_huffman are inverses.
generic type Item_Type is private; with procedure put(i : Item_Type); package Tree_Pkg is type Tree is private; Empty : constant Tree; function is_leaf (t : Tree) return Boolean with pre => not is_empty (t); function is_empty (t : Tree) return Boolean; function new_tree (i : Item_Type; l, r : Tree) return Tree; function left (t : Tree) return Tree with pre => not is_empty (t); function right (t : Tree) return Tree with pre => not is_empty (t); function data (t : Tree) return Item_Type with pre => not is_empty (t); procedure put_pre_order (t : Tree); private ... end Tree_Pkg;
with huffman_pkg; use huffman_pkg; procedure someclient is s : constant String := "The cat in the Hat"; f_table : Frequency_Table := create_freq_table (s); h_table : Huffman_Table := create_huffman_table (s); begin put_f_table (f_table); put_h_table (h_table); put_line (to_huffman (s, false)); put_line (to_huffman (s, true)); put_line (to_ascii (to_huffman (s, false), create_freq_table (s)));
pragma assertion_policy(check)is included at the beginning of the program (ie above with statements).
Your program should have well-designed data, good decomposition, and make good use of language features. Use good style, including good indentation, descriptive constant, variable, type, function, procedure, and package names, and named constants. Also use good commenting style, remembering that the first thing in any program file should be a comment that gives a brief overview of what the file contains (and should do). Follow these commenting guidelines.
When debugging programs, run-time exceptions are a common occurrence. One way to find the line at which an exception occurs is to place put statements in your program so you can follow it's execution. Another way is to use the gdb debugger (ie gnu debugger): these instructions show you how. Note that you can also use gvd (the gnu visual debugger) to debug your program and find the source of an exception as well as other information.
Use the submit command to turn your program in for grading. You may submit as many times as you like, but since only the last submission is kept, if the last one is late, then your assignment is late. Always remember to use the -ls option of submit to check that your submission was received.