Pledge of Honor |
1 (15 pts) | 2.a (25 pts) | 2.b (20pts) | 3 (40 pts) | Total (100 pts) |
Download and unzip heap.zip for the source code to be used in this problem. The class Heapifier provides two key methods: siftUp and siftDown to maintain the heap structure for an array of Comparable. The class RACHeap is implements the IRAContainer interface using an array of Comparable that satisfies the heap property. RACHeap is an example of what is called a priority queue. The objects in the RACHeap are compared based on their priorities. The smaller (with respect to compareTo) the object, the higher the priority. The class TestObject inside the JUnit test class TestRACHeap is an example of such a Comparable class.
There are situations when the priority of an object in a priority queue changes requiring the priority queue to be updated to maintain the proper ordering. Complete the method update in RACHeap as specified in the provided stub code.
Roughly speaking, a computer's memory can be modeled as an array of integers.
Your task is to write a class for managing the free, or unused, parts of a
computer's memory. Download and unzip memory.zip for
the source code to be used in this problem. In the provided code, this class
Allocator implements the interface:
interface IAllocator {
int allocate(int count);
void free(int index, int count);
}
The method allocate() returns the starting index
of the first contiguous group of unused locations of size "count" in memory. If,
however, there is no sufficiently large contiguous group of unused locations,
then allocate() returns -1. The method
free() adds the "count" contiguous locations
starting at "index" to the allocator's collection of unused memory.
The class Allocator utilizes a binary search tree (BST)
_memory consisting of objects of
class Range. representing contiguous block of
available memory. This class has the following
definition.
class Range {
int index;
int count;
}
Here index denotes the starting index of the
array of available memory. count denotes
the number of available units of memory.
2.a
Initially, the BST will hold a single Range
object covering all of memory. As allocation requests are made,
Range objects are either removed in their
entirely from the BST or reduced in count. For example, if
allocate() is called with size 500 and the first
Range object of sufficient size is (index: 1000,
count: 750), then the Range object becomes
(index: 1500, count: 250). Write the code for the anonymous inner class
_alloc as indicated in the provided class
Allocator.
Note: Allocator has method
called insert(int index, int count). This
method is for the purpose of testing the method allocate without using the
method free. The provided JUnit test class
TestAllocator uses the method
insert to enter disjoint contiguous blocks of
memory and tests the correctness of allocate.
You may want to comment out the assertEquals
statements and run the test class to see how it behaves.
2.b Analogously, when memory is freed, adjoining Range
objects are expanded to include the newly freed memory. For example, if
the allocator hold Range objects (index: 5000,
count: 1000) and (index: 6500, count: 500) and the memory at index 6000 of count
500 is freed, the allocator will replace the two previous
Range objects by a single
Range object (index: 5000, count: 2000).
Write the pseudo-code for the anonymous inner class
_freer as indicated in the provided class
Allocator. The pseudo-code should clearly describe the
various cases where adjoining Range objects need or need not be coalesced
and the steps to handle these cases. Working code is not required.
To see where we are going, download and run the demo (executable jar file--select "Open" when downloading): postfix.jar As you can see this is a really cheap postfix calculator: it does not support subtraction nor division. Nevertheless, it seems to calculate arithmetic expression in postfix notation correctly. It also displays the content of the stack and the accumulator that are internal to the calculator. What do we mean by an "postfix" expression? A binary operation is said to be in postfix notation if the operator (e.g. +) follows the two operands. There are also "infix" and "prefix" expressions. The following table shows an example of each form of notation.
Adding two numbers x, y together
Infix Notation x + y Prefix Notation + x y Postfix Notation x y +
Note that it is an Honor Code violation to attempt to decompile any of the demos in this problem.
A postfix calculator, a.k.a. Reverse Polish Notation (RPN) calculator, is a calculator that computes arithmetic expressions in postfix notation. Internally it uses a stack, S, to store the operands in a postfix expression. It also has an accumulator, acc, to maintain the current input and to display the result of a computation. The RPN calculator does not maintain a "pending operation" as the infix calculator (see lab #13) does. Whenever a operation is entered, the RPN calculator immediately performs the operation by doing the following:
Pop the stack: S.get()
Add the result to the accumulator: S.get() + acc
Store the result back in the accumulator: acc = S.get() + acc
Push the result back onto the stack: S.put(acc).
The following table illustrates how an RPN calculator works. Use the above postfix.jar demo to study the behaviors of the calculator.
Infix expression | Postfix Expression | Key Sequence | Internal Calculation | acc | S (grows to right) |
34 + 56 | 34 56 + | Enter 34 | acc = 34 | 34 | empty |
Push | S.put(acc) | 34 | 34 | ||
Enter 56 | acc = 56 | 56 | 34 | ||
+ | acc = S.get() + acc = 34 + 56 S.put(acc) |
90 | 90 | ||
Clear | acc = 0; S.clear() |
0 | empty | ||
3 + ( 4 * 5) | 3 4 5 * + | Enter 3 | acc = 3 | 3 | empty |
Push | S.put(acc ) | 3 | 3 | ||
Enter 4 | acc = 4 | 4 | 3 | ||
Push | S.put(acc ) | 4 | 3 4 | ||
Enter 5 | acc = 5 | 5 | 3 4 | ||
* | acc = S.get() * acc = 4 * 5 S.put(acc ) |
20 | 3 20 | ||
+ | acc = S.get() + S.get() = 3 + 20 S.put(acc ) |
23 | 23 | ||
Clear | acc = 0; S.clear() |
0 | empty | ||
(3 + 4) * 5 | 3 4 + 5 * | Enter 3 | acc = 3 | 3 | empty |
Push | S.put(acc ) | 3 | 3 | ||
Enter 4 | acc = 4 | 4 | 3 | ||
+ | acc = S.get() + acc = 3 + 4 S.put(acc ) |
7 | 7 | ||
Enter 5 | acc = 5 | 5 | 7 | ||
* | acc = S.get() + acc = 7 * 5 S.put(acc ) |
35 | 35 | ||
Clear | acc = 0; S.clear() |
0 | empty | ||
(3 + 4) * (5 + 6) | 3 4 + 5 6 + * | Enter 3 | acc = 3 | 3 | empty |
Push | S.put(acc ) | 3 | 3 | ||
Enter 4 | acc = 4 | 4 | 3 | ||
+ | acc = S.get() + acc = 3 + 4 S.put(acc ) |
7 | 7 | ||
Enter 5 | acc = 5 | 5 | 7 | ||
Push | S.put(acc ) | 5 | 7 5 | ||
Enter 6 | acc = 6 | 6 | 7 5 | ||
+ | acc = S.get() + acc = 5 + 6 S.put(acc ) |
11 | 7 11 | ||
* | acc = S.get() * S.get() = 11 *
7 S.put(acc ) |
77 | 77 | ||
Clear | acc = 0; S.clear() |
0 | empty | ||
3 * (4 + 5) * 2 | 3 4 5 + * 2 * | Enter 3 | acc = 3 | 3 | empty |
Push | S.put(acc ) | 3 | 3 | ||
Enter 4 | acc = 4 | 4 | 3 | ||
Push | S.put(acc ) | 4 | 3 4 | ||
Enter 5 | acc = 5 | 5 | 3 4 | ||
+ | acc = S.get() + acc = 4 + 5 S.put(acc ) |
9 | 3 9 | ||
* | acc = S.get() * S.get() = 9 * 3 S.put(acc ) |
27 | 27 | ||
Enter 2 | acc = 2 | 2 | 27 | ||
* | acc = S.get() * acc = 27 * 2 S.put(acc ) |
54 | 54 |
Your job is to design and implement a postfix calculator like the above demo with a simpler interface. This calculator has on the outside:
10 buttons labeled 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, respectively, to enter digit characters
one button labeled . to enter the decimal point
one button labeled +, to perform addition
one button labeled *, to perform multiplication
one button labeled "Push", to enter the display into the internal stack.
one button labeled C, to clear all entries in the calculator and reset the calculator to its pristine initial state
and a display text field for me to view the input and the result of my desired computation.
This calculator is to correctly compute any syntactically legal postfix expression. Entering any malformed postfix expression should result in an error. Click here to download and run the demo of the calculator you are going to produce: rpn.jar. The behaviors of this RPN calculator can be modeled as a finite state machine that is similar to the infix calculator done in lab #13. In fact, it has the same number of states as that infix calculator. Because the infix calculator and the postfix calculator differ in their internal representations, the actions performed in each state transition will differ.
Click here to download and save the source code of that you will need to use to implement your calculator: rpnsource.zip. Most of the files are the source code of the data structures you have learned in this semester: immutable list, mutable list, restrict access container. You need only complete the code for RNPMachine.java in the model package. You are free to add any number of non-public fields and methods to RNPMachine.java. You are free to add any number of non-public classes to support your RNPMachine class. RPNView.java in the view package is the view with the main method. You need not modify the view at all.
Hint: It helps to analyze the state transitions first. Below is the state transition for the start state to help you get started!
Start State |
||
event |
actions performed |
next state |
enterDigit(0) |
display 0 |
start state |
enterDigit(d != 0) |
display d |
accum state |
enterPoint() |
display 0. |
point state |
enterOp(op)/do op[err] |
display Error! |
error state |
enterOp(op)/do op[no err] |
perform op w/ operand from stack and from display push acc onto stack display acc |
comp state |
push()/push[err] |
display Error! |
error state |
push()/push[no err] |
push display onto stack |
start state |
clear() |
acc = 0 display 0 empty stack |
start state |