hey ppl can any of you help me i got this assignment which i dont
even know how to start and its due soon can u ppl help me


For this assignment, you are required to implement several classes,
which are described below.
2.1 Priority Queue classes
_ PriorityQueue A priority queue, or PQ, is a modi_cation of a
regular queue. Like the queues
you have already learned about, a PQ has an underlying FIFO (_rst-in,
_rst-out) behaviour,
1
but queue elements also have an associated priority value: high-
priority items can buy their
way to the front of the queue.
Thus, the ordering of a priority queue has the following properties:
{ The elements are ordered according to the elements' priority value.
Usually low numbers
indicate high priority, so that elements of priority 0 appear at the
head of the queue,
and elements of in_nite priority at the tail.
{ Elements of equal priority appear in order of arrival (as in
regular queue ordering).
PriorityQueue is an interface that represents the high-level
behaviour of a PQ. It should
provide the same methods as regular queues, but it works with items
that have priorities |
PQ items, if you will. Therefore, it has these methods:
{ enqueue(PQItem)
{ dequeue
{ isEmpty
{ head
{ size
All the methods of the PriorityQueue interface have the same
signatures and return types
as the corresponding methods of the Queue interface, except that
enqueue takes a parameter
of type PQItem. PQItem is another interface, with just one method,
getPriority. Here is
that method's return type and signature:
{ int getPriority()
What kinds of objects go in the PQ? Any kind of object can be stored
in your PQ, as long as
its class implements the PQItem interface. For example, you might
model a queue of airline
passengers in which di_erent categories of customers are served in
order of category.
In this assignment you will write two implementations of
PriorityQueue, one based on linked
lists and the other based on a specialized data structure called a
heap. It may help to add a
toString method to both classes so that you can retrieve and examine
the contents of a PQ
all at once.
_ LinkedPQ
The _rst implementation for the PriorityQueue class is the LinkedPQ.
This is the priority
queue that is implemented using a linked list.
_ HeapPQ
The second implementation for the PriorityQueue class is the HeapPQ.
This is an array-based
heap, as described in lecture during week 8 of the term. A heap is a
complete tree de_ned
with the following property, called the heap-order property:
{ The value of any node in the tree is smaller than the value of any
node in its subtrees.
This describes the heap-order property for a min-heap. For this
implementation, assume that
the structure of the heap is a binary tree, and remember that a
complete tree is one where
the tree is _lled one level at a time, from left to right.
2
2.2 CodeTable
We provide the CodeTable class, which contains the lookup table and
its supported operations.
See the Javadoc in the doc directory for more information. (Open up
index.html.) CodeTable
relies on a tree of TreeNodes, which described in the next section.
2.3 The coding tree
To encode or decode a sequence of bits into the equivalent sequence
of alphanumeric characters,
you will need to construct a coding tree. The coding tree is a binary
tree where each leaf node corresponds
to a particular alphanumeric character. Each leaf stores the
character and the character's
frequency (the number of times it occurs), while the internal nodes
store the total frequency of the
characters in the node's subtrees.
_ TreeNode
TreeNode implements PQItem. The priority of a TreeNode is the
frequency of its character
in the training _le. This abstract class represents a single node in
the coding tree. It
is a superclass of the LeafNode and InternalNode classes, described
below. The low-level
implementation of this class is largely up to you; however, you must
have at least the following
public methods:
{ isLeaf()
{ isInternal()
{ getFrequency()
_ LeafNode
This class represents the leaves of the coding tree, and is thus the
only node type that stores
both a frequency and a character value. You must provide at least
this public method, which
returns the character value. (This method is used by CodeTable.)
{ getValue()
_ InternalNode
This class represents the internal nodes of the coding tree. You must
provide at least these
public methods, which return the left and right children of this
node. The return type for
both is TreeNode. (These are also used by CodeTable.)
{ getLeft()
{ getRight()
To produce the coding tree from a PQ of TreeNodes, repeatedly perform
the following steps until
there is only one item in the PQ:
Remove the two subtrees with the lowest total frequency (keeping in
mind that a leaf
node is also a subtree). Combine these two subtrees together with a
new root node,
which is an InternalNode. The frequency of this new InternalNode is
the sum of the
frequencies of its two children. Put this new node into the PQ.
3
2.4 Decoding
To decode a sequence of bits, start at the root of the coding tree,
and use the sequence of binary
digits to traverse the tree from root to leaf. If a 0 is encountered
in the bit sequence, traverse the
left subtree of the current node, and if a 1 is encountered, traverse
the right subtree. When a leaf
is encountered, another character has been decoded, and the decoding
sequence starts again from
the root node, using the next digit in the binary sequence.
2.5 Encoding
The encoding operation complements the decoding algorithm mentioned
above. However, the
structure used to support this operation is a lookup table of values,
making this operation more
straightforward than its counterpart.
For this assignment, the table will store translations between
characters and binary encodings. So
each entry will be made up of two elements: the character as the key
element, and the binary string
as the data value. In order to obtain the binary representation for a
character, the character is
fed into the lookup table, and the corresponding binary sequence is
returned. We have provided
CodeTable. You need to _ll it with the entries.
Building this table requires that the decoding tree be explored
recursively to _nd all of the leaves in
the tree, along with the tree traversal that corresponds to each
leaf. This table-building is initiated
in the Translator class, but the design for the actual recursive
method that builds the table is left
to the discretion of the designer.
2.6 Translator (main class)
This class is responsible for taking in the location of the operation
to perform, the data _le, the
input _le and the output _le. These parameters will be passed into
the program when the class is
invoked at the command line, in the following manner:
Translator <operation> <data file> <input file> <output file>
In this case, the value of the <operation> parameter will be either
encode (translate characters
to binary, writing the result to <output file>) or decode (translate
binary to characters, also
writing the result to <output file>). In order to accomplish this,
the following methods should
be in the Translator class:
_ encode(String)
_ decode(String)
You should also have other methods in this class to perform smaller
functions, instead of putting
all of your functionality in your main method. Keeping your main
method short will help the
marker understand the approach you used in your implementation, and
will make the code of your
Translator class easier for you to read and maintain.
The basic algorithm for the main method is:
4
1. read in the training _le, determining the frequency of each
character in this _le; at the same
time, build a list of TreeNodes that record this frequency information
2. build the coding tree from the TreeNode list to perform the
encoding or decoding operation
on the input _le
3. Once these steps are complete one of these happens (saving the
result in <output file>):
(a) using the coding tree, create a lookup table and encode the
contents of <input file>
(b) using the coding tree, decode a binary sequence read from <input
file>
We have provided code that opens the _les for reading. It also does
some error checking.
Every character in the input _le, including newlines and spaces, is
considered part of the input and
should be put in the list. To read a single character, make a
BufferedReader for the input _le and
then use method read instead of readLine. You need to typecast from a
byte to a char. Here is
an example:
char c = (char) br.read();
Look up method read in class java.io.Reader to _nd out how to check
for the end of a _le.
3 E_ciency Analysis
The e_ciency of one algorithm over another may be analyzed by
counting the number of times
that a particularly expensive operation takes place. In general this
analysis focuses on memory
operations (assignments and comparisons). For this assignment we
focus only on comparisons.
Your analysis will take place in the two PriorityQueue structures
that you have been asked to
implement. In these two classes count every comparison that occurs
(that is, every time an if
statement or loop condition is evaluated). (Yes, we know this makes
your PQ code ugly.) Your
program should produce a _le called "report.txt" that contains the
number of occurrences of each
operation in the following form:
Linked List Implementation
--------------------------
Comparisons: ###
Heap Implementation
-------------------
Comparisons: ###
4 Testing
Include a JUnit test class, TestPQ, whose purpose it is to test the
operations of both of your
PriorityQueue classes. We expect you to have very little duplicate
code in this test class.
5
5 Style
Steve says he likes the style from A2 and wants to reuse it. Don't
blame Paul, he encouraged Steve
to change it. The style checker is handout number 7 in the General
Handouts section.
6 Suggested approach
We recommend doing the parts of the assignment in this order, testing
after each step:
1. Compile and run the Translator code.
2. Run the style checker on Translator and _x any problems.
3. Write the TreeNode class.
4. Write LinkedPQ and the tester for it; you can test with TreeNodes.
5. Write code that reads the training _le character by character and
stores the characters in a
list.
6. Modify that code so that it maintains the frequency of each
character, by building a list of
LeafNodes and updating the frequency appropriately.
7. Build the coding tree from that list.
8. Make a CodeTable from the coding tree and make sure the table
looks reasonable.
9. Write code to encode an input _le.
10. Write code to decode an input _le.
11. Write HeapPQ and modify the tester to test it.