COS126

• Download ToyStory.java

/******************************************************************************
 *  Name:    Reference Solution
 *  NetID:   refsoln
 *  Precept: P00
 *
 *  Description: Renumbers TOY programs.
 ******************************************************************************/

public class ToyStory {

    // a symbol table whose keys are memory locations and whose values are instructions
    private ST<String, String> code = new ST<String, String>();

    // adds each line to the ST, where a line is a String in the format: "XX: XXXX"
    public ToyStory(String[] lines) {
        for (String line : lines)
            code.put(line.substring(0, 2), line.substring(4));
    }

    // return a String containing the program, in the form: "XX: XXXX\nXX: XXXX\n"
    public String toString() {
        StringBuilder result = new StringBuilder();
        for (String line : code.keys())
            result.append(line + ": " + code.get(line) + "\n");
        return result.toString();
    }

    // returns true if there is an instruction defined at memory location 'mem'
    public boolean isDefined(String mem) {
        return code.contains(mem);
    }

    // returns true if instruction at 'mem' has op code C or D and ends in 'addr'
    // assumes that there is an instruction defined at 'mem'
    public boolean containsJumpTo(String mem, String addr) {
        String instruction = code.get(mem);

        char opCode = instruction.charAt(0);

        return (opCode == 'C' || opCode == 'D') &&
                instruction.substring(2).equals(addr);
    }

    // FOR FULL CREDIT, MUST CORRECTLY USE containsJumpTo() AND increment() (SEE BELOW)
    // finds all instructions that jump to 'addr' and changes them to jump to 'addr'+1
    public void incrementAllJumpsTo(String addr) {
        for (String mem : code.keys())
            if (containsJumpTo(mem, addr))
                code.put(mem, code.get(mem).substring(0, 2) + increment(code.get(mem).substring(2)));

    }

    // DO NOT EDIT THIS METHOD
    // IT IS PROVIDED TO MAKE INCREMENTING EASIER IN THE METHOD ABOVE
    // takes a 2-hex-digit number as input, gives the next 2-digit-hex number as output
    // for example, increment("19") returns "1A"
    public static String increment(String addr) {
        return String.format("%02X", Integer.parseInt(addr, 16) + 1);
    }

    // EXTRA CREDIT
    // FOR ONE POINT, IMPLEMENT A WORKING NON-RECURSIVE SOLUTION
    // FOR TWO POINTS, IMPLEMENT A WORKING RECURSIVE SOLUTION
    // move all consecutive instructions at and after memory address 'min' down
    // to the following memory address. also, maintains connections between all
    // jumps and the instructions they jump to by calling incrementAllJumpsTo()
    public void renumberAfter(String min) {
        if (isDefined(increment(min)))
            renumberAfter(increment(min));
        code.put(increment(min), code.get(min));
        incrementAllJumpsTo(min);
        code.remove(min);
    }

    // DO NOT EDIT THIS METHOD
    // IT IS PROVIDED TO HELP YOU TEST YOUR EXTRA CREDIT SOLUTION
    // associates 'mem' with 'instruction' and updates the existing code accordingly
    public void addLine(String mem, String instruction) {
        // before we add this line, let's push everything down
        if (isDefined(mem)) renumberAfter(mem);

        // then add this line
        code.put(mem, instruction);
    }

    // YOU MAY EDIT THIS METHOD BUT CODE WRITTEN HERE WILL NOT BE GRADED
    public static void main(String[] args) {

        // THIS IS JUST A DUMMY TOY PROGRAM TO TEST YOUR CODE
        String[] toy = {"10: 1000", "11: C010"};

        // READ IT IN, PRINT IT OUT
        ToyStory story = new ToyStory(toy);
        StdOut.println(story.toString());

        // ARE THERE INSTRUCTIONS DEFINED AT THESE MEMORY LOCATIONS?
        StdOut.println(story.isDefined("10")); // TRUE
        StdOut.println(story.isDefined("12")); // FALSE

        // DO THE FOLLOWING LINES CONTAIN JUMPS TO THESE ADDRESSES?
        StdOut.println(story.containsJumpTo("11", "10")); // TRUE
        StdOut.println(story.containsJumpTo("11", "11")); // FALSE

        // LET'S CHANGE ALL JUMPS TO 10 TO JUMP TO 11 INSTEAD
        story.incrementAllJumpsTo("10");
        StdOut.println(story); // RESULT: "10: 1000\n11: C011\n"
    }
}