Assignment •  Development Guide •  Code •  Checklist •

HW5 Development Guide

 

You should use this guide to help you to complete your assignment. You should follow it step by step, resolving errors before going on to the next step. Refer to the HW5 Assignment page for the descriptions for each method you need to write. Once you can follow this guide without errors, you should come up with more test cases to test your program.

Note: Before step 8, it is okay that there are memory leaks after you press^D. However, after step 8 (in which you will implement the jettison methods) you should not see any memory leaks after ^D terminates the program.
Another Note: If you are not working on the ieng6 server, you might get differet sizes of the objects when checking your memory usage.

1. Add return statements in each method to make sure the program compiles with make.
2. Write the method ListEngine Constructor. The initial allocation of the ListEngine should not contain nodes.
   Once you're done, we're going to run through ListEngine with jdb to make sure everything is getting initialized correctly:

   In your terminal use jdb to execute your program, $ jdb Driver1
   Open another terminal to use as your jdb terminal, copy paste what you got from the jdb window to execute your program.
   $ \jdb -attach 80[xx]
   In your jdb terminal
   main[1] stop in List$ListEngine.<init>
   main[1] run
   Breakpoint hit: "thread=main", List$ListEngine.<init>(), line=66 bci=0
   66    public ListEngine (Base sample, String caller) {
   main[1] next
   …repeat until you have reached the bottom of your method.
   main[1] print occupancy
     occupancy = 0
   main[1] print end
     end = null
   
   main[1] print this.sample
     this.sample = null
   main[1] print List.listCounter
     List.listCounter = 1
   Note: You should also test this with Driver2, and you should see this.sample is not null.

   Now, test your Driver1 executable as follows:

   % ./Driver1 -x
   [List 1 has been allocated]
   
   The commands are:
       is(e)mpty, (o)ccupancy, (c)heck memory,
       (a)dvance pre, advance (n)ext,
       p(u)sh, (p)op, (t)op,
       (i)nsert, (r)emove, (v)iew
       (w)rite, (W)rite reverse,
   
   Please enter a command: w
   
   ------------ TRACKED MEMORY ------------
   36 bytes of heap memory, created in baseStack in Driver.main calling BaseStack Ctor
       calling List Ctor calling ListEngine Ctor for the ListEngine object.
   
   List 1 has 0 items in it.
   
   
   The commands are:
       is(e)mpty, (o)ccupancy, (c)heck memory,
       (a)dvance pre, advance (n)ext,
       p(u)sh, (p)op, (t)op,
       (i)nsert, (r)emove, (v)iew
       (w)rite, (W)rite reverse,
   
   Please enter a command: ^D
   
   // You will see some memory leaks after you end the program until you have finished step 8.
   // This is expected because we have not yet implemented the jettison methods.
   

3. Now we would like to be able to insert items into the list. We will be tackling three different situations: inserting at the front, the end, and then insert at any location in the list.
   
   The first step to take is to write the constructor and insert of NodeEngine and insert of ListEngine methods for the front and end cases. The insert of ListEngine will utilize insert of Node, which use insert of NodeEngine as a helper method by initializing a new node and reattaching pointers to include the new node into the list. Since insert of Node inserts after the caller (end), you'll want to return the new Node and reassign the value. Thus, your insert of NodeEngine should create a new Node that hold the new NodeEngine and send it back.
   
   Also we will be writing the isEmpty method that checks whether the list is empty before we insert. Then, you will write the locate method to inform insert where to insert based on the parameter that is passed in. locate calls checkToGoForward, but since we are not going to test checkToGoForward yet, you can just have it return true for now.
   
   Lastly, we would write the advancePre and advanceNext methods to facilitate writing out the list. The advancePre method is used to move the end pointer of the list to the previous node pointer. The advanceNext method is the opposite of advancePre in that you move the end pointer of the list to the next node pointer instead. There is a section below for testing both advancePre and advanceNext.
   
   After writing the methods, which are
   • ListEngine: advanceNext
   • ListEngine: advancePre
   • ListEngine: insert (For the insert at front/end case)
   • ListEngine: locate
   • ListEngine: checkToGoForward (not really functioning)
   • ListEngine: isEmpty
   • NodeEngine: Constructor
   • NodeEngine: insert
   we will briefly check functionality with jdb:

   $ jdb Driver1
   Set up the two terminals like before.
   $ \jdb -attach 80[xx]
   In your jdb terminal
   main[1] stop in List$ListEngine$Node$NodeEngine.insert
   main[1] run
   The commands are:
       is(e)mpty, (o)ccupancy, (c)heck memory,
       (a)dvance pre, advance (n)ext,
       p(u)sh, (p)op, (t)op,
       (i)nsert, (r)emove, (v)iew
       (w)rite, (W)rite reverse,
   
   Please enter a command: i
   
   Please enter a number to insert into list: 10
   Specify 1 for FRONT, 0 for END, or location number
   Please enter choice: 1
   
   At this point the breakpoint should not be reached yet because we only allocated one node. Continue with the second prompt.
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: i
   
   Please enter a number to insert into list: 20
   Specify 1 for FRONT, 0 for END, or location number
   Please enter choice: 1
   
   Now we will have reached the breakpoint at ListEngine's insert. Type 'cont' so we can insert a third node and look at them all at once.
   main[1] cont
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: i
   
   Please enter a number to insert into list: 30
   Specify 1 for FRONT, 0 for END, or location number
   Please enter choice: 1
   
   main[1] next
   Repeat until you pass your variable reassignments to include the new 30 node into the list. Right now, the linked list looks like 30->20->10, with 10 as the end, -> indicates a next pointer.
   Assuming our newly created node is called 'newNode', we can check the next and pre fields of newNode and the thisNode (the first parameter to NodeEngine's insert, aka the end before inserting newNode).
   main[1] print newNode.nodeEngine.data
   newNode.nodeEngine.data = "30"
   main[1] print newNode.nodeEngine.next.nodeEngine.data
   newNode.nodeEngine.next.nodeEngine.data = "20"
   This value should match that of thisNode since we are inserting before it as the new front now.
   main[1] print newNode.nodeEngine.pre.nodeEngine.data
   newNode.nodeEngine.pre.nodeEngine.data = "10"
   This value should match our 'last' node's value (first one we put in) since we are implementing a circular linked list so to the newNode (which is at the beginning of the list) pointer's pre field points to the end of the list.
   main[1] print thisNode.nodeEngine.data
   thisNode.nodeEngine.data = "10"
   This value should match that of the most recent element you inserted since we've been inserting at the front each time (20)
   main[1] print thisNode.nodeEngine.next.nodeEngine.data
   thisNode.nodeEngine.next.nodeEngine.data = "30"
   This value should match that of the FIRST element we INSERTED into the list since it came before the previous number (10)
   main[1] print thisNode.nodeEngine.pre.nodeEngine.data
   thisNode.nodeEngine.pre.nodeEngine.data = "20"
   This value should match that of the newNode since we inserted newNode in front of the thisNode.
   

   Now try this on your own with inserting at the end! You should see similar results but your linked list is reversed.
   
   From now on, you should run all of the following tests on both Driver1 and Driver2 and get the same results.
   
   As part of testing this new code, answer the questions below and include the answers in a comment block in the List.java file.
   
   Debugger Questions: Please include the answers to these questions as a comment block at the top of your List.java file.
   
   Using the debugger, insert three nodes into your list. List the values of the following pointers after the three insertions:
   
   1. end:
   2. Node 1 data:
   3. Node 1 pre:
   4. Node 1 next:
   5. Node 2 data:
   6. Node 2 pre:
   7. Node 2 next:
   8. Node 3 data:
   9. Node 3 pre:
   10. Node 3 next:
   
   Verify that the answers make sense, and then run the following test:
   

   % ./Driver1 -x
   [List 1 has been allocated]
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: i
   
   Please enter a number to insert into list: 1
   Specify 1 for FRONT, 0 for END, or location number
   Please enter choice: 0
   [List 1 - Inserting node]
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: i
   
   Please enter a number to insert into list: 2
   Specify 1 for FRONT, 0 for END, or location number
   Please enter choice: 0
   [List 1 - Inserting node]
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: i
   
   Please enter a number to insert into list: 3
   Specify 1 for FRONT, 0 for END, or location number
   Please enter choice: 0
   [List 1 - Inserting node]
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: i
   
   Please enter a number to insert into list: 4
   Specify 1 for FRONT, 0 for END, or location number
   Please enter choice: 1
   [List 1 - Inserting node]
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: i
   
   Please enter a number to insert into list: 5
   Specify 1 for FRONT, 0 for END, or location number
   Please enter choice: 1
   [List 1 - Inserting node]
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: i
   
   Please enter a number to insert into list: 6
   Specify 1 for FRONT, 0 for END, or location number
   Please enter choice: 1
   [List 1 - Inserting node]
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: w
   
   List 1 has 6 items in it.
   
   element 1: 6
   [List 1 - Advancing next]
   element 2: 5
   [List 1 - Advancing next]
   element 3: 4
   [List 1 - Advancing next]
   element 4: 1
   [List 1 - Advancing next]
   element 5: 2
   [List 1 - Advancing next]
   element 6: 3
   [List 1 - Advancing next]
   
   ------------ TRACKED MEMORY ------------
   36 bytes of heap memory, created in baseStack in Driver.main calling BaseStack Ctor
       calling List Ctor calling ListEngine Ctor for the ListEngine object.
   16 bytes of heap memory, created in Driver.main calling Ctor for the MyRec object.
   32 bytes of heap memory, created in Node Ctor calling NodeEngine Ctor for the NodeEngine object.
   16 bytes of heap memory, created in Driver.main calling Ctor for the MyRec object.
   32 bytes of heap memory, created in Node Ctor calling NodeEngine Ctor for the NodeEngine object.
   16 bytes of heap memory, created in Driver.main calling Ctor for the MyRec object.
   32 bytes of heap memory, created in Node Ctor calling NodeEngine Ctor for the NodeEngine object.
   16 bytes of heap memory, created in Driver.main calling Ctor for the MyRec object.
   32 bytes of heap memory, created in Node Ctor calling NodeEngine Ctor for the NodeEngine object.
   16 bytes of heap memory, created in Driver.main calling Ctor for the MyRec object.
   32 bytes of heap memory, created in Node Ctor calling NodeEngine Ctor for the NodeEngine object.
   16 bytes of heap memory, created in Driver.main calling Ctor for the MyRec object.
   32 bytes of heap memory, created in Node Ctor calling NodeEngine Ctor for the NodeEngine object.
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: u
   
   Please enter a number to push to stack: 3333
   [List 1 - Inserting node]
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: w
   
   List 1 has 7 items in it.
   
   element 1: 6
   [List 1 - Advancing next]
   element 2: 5
   [List 1 - Advancing next]
   element 3: 4
   [List 1 - Advancing next]
   element 4: 1
   [List 1 - Advancing next]
   element 5: 2
   [List 1 - Advancing next]
   element 6: 3
   [List 1 - Advancing next]
   element 7: 3333
   [List 1 - Advancing next]
   
   ------------ TRACKED MEMORY ------------
   36 bytes of heap memory, created in baseStack in Driver.main calling BaseStack Ctor
       calling List Ctor calling ListEngine Ctor for the ListEngine object.
   16 bytes of heap memory, created in Driver.main calling Ctor for the MyRec object.
   32 bytes of heap memory, created in Node Ctor calling NodeEngine Ctor for the NodeEngine object.
   16 bytes of heap memory, created in Driver.main calling Ctor for the MyRec object.
   32 bytes of heap memory, created in Node Ctor calling NodeEngine Ctor for the NodeEngine object.
   16 bytes of heap memory, created in Driver.main calling Ctor for the MyRec object.
   32 bytes of heap memory, created in Node Ctor calling NodeEngine Ctor for the NodeEngine object.
   16 bytes of heap memory, created in Driver.main calling Ctor for the MyRec object.
   32 bytes of heap memory, created in Node Ctor calling NodeEngine Ctor for the NodeEngine object.
   16 bytes of heap memory, created in Driver.main calling Ctor for the MyRec object.
   32 bytes of heap memory, created in Node Ctor calling NodeEngine Ctor for the NodeEngine object.
   16 bytes of heap memory, created in Driver.main calling Ctor for the MyRec object.
   32 bytes of heap memory, created in Node Ctor calling NodeEngine Ctor for the NodeEngine object.
   16 bytes of heap memory, created in Driver.main calling Ctor for the MyRec object.
   32 bytes of heap memory, created in Node Ctor calling NodeEngine Ctor for the NodeEngine object.
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: ^D
   
   // You will see some memory leaks after you end the program until you have finished step 8.
   // This is expected because we have not yet implemented the jettison methods.
   

4. Specifically test the methods advancePre and advanceNext. Test as follows:

   % ./Driver1
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: u
   
   Please enter a number to push to stack: 1
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: u
   
   Please enter a number to push to stack: 2
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: u
   
   Please enter a number to push to stack: 3
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: u
   
   Please enter a number to push to stack: 4
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: u
   
   Please enter a number to push to stack: 5
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: w
   
   List 1 has 5 items in it.
   
   element 1: 1
   element 2: 2
   element 3: 3
   element 4: 4
   element 5: 5
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: a
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: w
   
   List 1 has 5 items in it.
   
   element 1: 5
   element 2: 1
   element 3: 2
   element 4: 3
   element 5: 4
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: n
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: w
   
   List 1 has 5 items in it.
   
   element 1: 1
   element 2: 2
   element 3: 3
   element 4: 4
   element 5: 5
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: ^D
   
   // Again, you will see some memory leaks after you end the program until you have finished step 8.
   // This is expected because we have not yet implemented the jettison methods.

5. Write the method checkToGoForward. Test with values of where other than 0 or 1.
   Note: When you insert directly in the middle of the list, coming from either the front or from the end is correct. Therefore, although the drivers in the public area come show "Advancing next", your solution may show "Advancing pre" in that case. Test as follows:
   
   We first test with an easy case.
   
   

   % ./Driver1 -x
   [List 1 has been allocated]
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: i
   
   Please enter a number to insert into list: 1
   Specify 1 for FRONT, 0 for END, or location number
   Please enter choice: 1
   [List 1 - Inserting node]
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: i
   
   Please enter a number to insert into list: 2
   Specify 1 for FRONT, 0 for END, or location number
   Please enter choice: 1
   [List 1 - Inserting node]
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: i
   
   Please enter a number to insert into list: 3
   Specify 1 for FRONT, 0 for END, or location number
   Please enter choice: 1
   [List 1 - Inserting node]
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: i
   
   Please enter a number to insert into list: 4
   Specify 1 for FRONT, 0 for END, or location number
   Please enter choice: 1
   [List 1 - Inserting node]
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: w
   
   List 1 has 4 items in it:
   [List 1 - Advancing next]
   element 1: 4
   [List 1 - Advancing next]
   element 2: 3
   [List 1 - Advancing next]
   element 3: 2
   [List 1 - Advancing next]
   element 4: 1
   [List 1 - Advancing next]
   ------------ TRACKED MEMORY ------------
   36 bytes of heap memory, created in baseStack in Driver.main calling BaseStack Ctor
       calling List Ctor calling ListEngine Ctor for the ListEngine object.
   16 bytes of heap memory, created in Driver.main calling Ctor for the MyRec object.
   32 bytes of heap memory, created in Node Ctor calling NodeEngine Ctor for the NodeEngine object.
   16 bytes of heap memory, created in Driver.main calling Ctor for the MyRec object.
   32 bytes of heap memory, created in Node Ctor calling NodeEngine Ctor for the NodeEngine object.
   16 bytes of heap memory, created in Driver.main calling Ctor for the MyRec object.
   32 bytes of heap memory, created in Node Ctor calling NodeEngine Ctor for the NodeEngine object.
   16 bytes of heap memory, created in Driver.main calling Ctor for the MyRec object.
   32 bytes of heap memory, created in Node Ctor calling NodeEngine Ctor for the NodeEngine object.
   Please enter a command: i
   Please enter a number to insert into list: 8888
   Specify 1 for FRONT, 0 for END, or location number
   Please enter choice: 4
   [List 1 - Inserting node]
   [List 1 - Advancing pre]
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: w
   List 1 has 5 items in it:
   [List 1 - Advancing next]
   element 1: 4
   [List 1 - Advancing next]
   element 2: 3
   [List 1 - Advancing next]
   element 3: 2
   [List 1 - Advancing next]
   element 4: 8888
   [List 1 - Advancing next]
   element 5: 1
   [List 1 - Advancing next]
   
   ------------ TRACKED MEMORY ------------
   36 bytes of heap memory, created in baseStack in Driver.main calling BaseStack Ctor
       calling List Ctor calling ListEngine Ctor for the ListEngine object.
   16 bytes of heap memory, created in Driver.main calling Ctor for the MyRec object.
   32 bytes of heap memory, created in Node Ctor calling NodeEngine Ctor for the NodeEngine object.
   16 bytes of heap memory, created in Driver.main calling Ctor for the MyRec object.
   32 bytes of heap memory, created in Node Ctor calling NodeEngine Ctor for the NodeEngine object.
   16 bytes of heap memory, created in Driver.main calling Ctor for the MyRec object.
   32 bytes of heap memory, created in Node Ctor calling NodeEngine Ctor for the NodeEngine object.
   16 bytes of heap memory, created in Driver.main calling Ctor for the MyRec object.
   32 bytes of heap memory, created in Node Ctor calling NodeEngine Ctor for the NodeEngine object.
   16 bytes of heap memory, created in Driver.main calling Ctor for the MyRec object.
   32 bytes of heap memory, created in Node Ctor calling NodeEngine Ctor for the NodeEngine object.
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: ^D
   
   // Memory leaks are expected.
   
   

   Now we will test with a harder case.

   Note that in the first insertion, we advanced pre, and on the second insertion, we advanced next. This indicates that our checkToGoForward> is correctly choosing the optimum path to travel.
6. Specifically test isEmpty. Test as follows:

   % ./Driver1 -x
   [List 1 has been allocated]
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: e
   
   Stack is empty.
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: u
   
   Please enter a number to push to stack: 1111
   [List 1 - Inserting node]
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: u
   
   Please enter a number to push to stack: 2222
   [List 1 - Inserting node]
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: e
   
   Stack is not empty.
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: ^D
   
   // This is the LAST PLACE where memory Leaks are expected in all the tests shown on dev guide.
   
   

7. Write the method writeReverseList. It should be very similar to writeList. To test, insert multiple items into the list, write the list with the w command and with the W command. The lists should have reversed order.
8. Write the method jettisonList in ListEngine, and the two jettisonNodeAndData, jettisonNodeOnly in NodeEngine. You should jettison both the NodeEngine and the data in jettisonNodeAndData, and only the Node in jettisonNodeOnly. Now, redo all the test cases above, and after you press ^D, you should NOT see any memory leaks at the end of the execuzation.
Note: Starting from here, after you press ^D, you should not see any memory leaks.

9. Write the methods view of ListEngine and view of NodeEngine. view of ListEngine will be called by the view of List, which is called in Main. view of ListEngine will call view of Node, which will call view of NodeEngine to send back the data. Remember this because you can not access a list's fields inside of a Node method. Also keep in mind that we can only view from the front or the end of the list. Which list fields can help with this? For view of NodeEngine, think about what we should be returning and which field of the NodeEngine corresponds to this. The end goal of the view method is to be able to view from the front of the list, from the end of it, or from any location that you want to view.
   
   Once you are done, test as follows:

   % ./Driver1 -x
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: u
   
   Please enter a number to push to stack: 1
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: u
   
   Please enter a number to push to stack: 2
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: u
   
   Please enter a number to push to stack: 3
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: u
   
   Please enter a number to push to stack: 4
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: u
   
   Please enter a number to push to stack: 5
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: w
   
   List 1 has 5 items in it.
   
   element 1: 1
   element 2: 2
   element 3: 3
   element 4: 4
   element 5: 5
   
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: v
   Specify 1 for FRONT, 0 for END, or location number
   Please enter choice: 0
   
   Number viewed from list is: 5
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: v
   Specify 1 for FRONT, 0 for END, or location number
   Please enter choice: 1
   
   Number viewed from list is: 1
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: v
   Specify 1 for FRONT, 0 for END, or location number
   Please enter choice: 2
   [List 1 - Viewing node]
   
   Number viewed from list is: 2
   The commands are:
       is(e)mpty, (i)nsert, (p)op,
       (a)dvance pre, advance (n)ext,
       (r)emove, (t)op, p(u)sh,
       (v)iew, (w)rite, (W)rite reverse,
   
   Please enter a command: ^D
   No memory leaks! All memory has been correctly deallocated.
   

   
   
10. Write the methods remove in ListEngine and remove in NodeEngine. These should be similar to the views, except that the elements are removed from the list. There are two jettison methods for NodeEngine, and you are supposed to call the one that removes only the Node and not the data.
    The end goal of the remove method is to be able to remove from the front of the list, from the end of it, or from any location that you want to remove.
    You will use jdb to test it so that you know that all the pre and next pointers of NodeEngine are pointing to the right places. Below is some sample output for you to compare the results.
    
    

    % ./Driver1 -x
    [List 1 has been allocated]
    
    The commands are:
        is(e)mpty, (i)nsert, (p)op,
        (a)dvance pre, advance (n)ext,
        (r)emove, (t)op, p(u)sh,
        (v)iew, (w)rite, (W)rite reverse,
    
    Please enter a command: r
    
    Specify 1 for FRONT, 0 for END, or location number
    Please enter choice: 0
    [List 1 - Removing node]
    Remove from empty list!!!
    
    WARNING: remove FAILED
    
    
    The commands are:
        is(e)mpty, (i)nsert, (p)op,
        (a)dvance pre, advance (n)ext,
        (r)emove, (t)op, p(u)sh,
        (v)iew, (w)rite, (W)rite reverse,
    
    Please enter a command: u
    
    Please enter a number to push to stack: 1
    [List 1 - Inserting node]
    
    The commands are:
        is(e)mpty, (i)nsert, (p)op,
        (a)dvance pre, advance (n)ext,
        (r)emove, (t)op, p(u)sh,
        (v)iew, (w)rite, (W)rite reverse,
    
    Please enter a command: u
    
    Please enter a number to push to stack: 2
    [List 1 - Inserting node]
    
    The commands are:
        is(e)mpty, (i)nsert, (p)op,
        (a)dvance pre, advance (n)ext,
        (r)emove, (t)op, p(u)sh,
        (v)iew, (w)rite, (W)rite reverse,
    
    Please enter a command: u
    
    Please enter a number to push to stack: 3
    [List 1 - Inserting node]
    
    The commands are:
        is(e)mpty, (i)nsert, (p)op,
        (a)dvance pre, advance (n)ext,
        (r)emove, (t)op, p(u)sh,
        (v)iew, (w)rite, (W)rite reverse,
    
    Please enter a command: u
    
    Please enter a number to push to stack: 4
    [List 1 - Inserting node]
    
    The commands are:
        is(e)mpty, (i)nsert, (p)op,
        (a)dvance pre, advance (n)ext,
        (r)emove, (t)op, p(u)sh,
        (v)iew, (w)rite, (W)rite reverse,
    
    Please enter a command: u
    
    Please enter a number to push to stack: 5
    [List 1 - Inserting node]
    
    Please enter a command: r
    
    Specify 1 for FRONT, 0 for END, or location number
    Please enter choice: 0
    [List 1 - Removing node]
    
    Number removed from list is: 5
    
    Please enter a command: r
    
    Specify 1 for FRONT, 0 for END, or location number
    Please enter choice: 3
    [List 1 - Removing node]
    [List 1 - Advancing next]
    
    Number removed from list is: 3
    
    The commands are:
        is(e)mpty, (i)nsert, (p)op,
        (a)dvance pre, advance (n)ext,
        (r)emove, (t)op, p(u)sh,
        (v)iew, (w)rite, (W)rite reverse,
    
    Please enter a command: w
    
    Please enter a command: w
    List 1 has 3 items in it:
    [List 1 - Advancing next]
    element 1: 1
    [List 1 - Advancing next]
    element 2: 2
    [List 1 - Advancing next]
    element 3: 4
    [List 1 - Advancing next]
    
    ------------ TRACKED MEMORY ------------
    36 bytes of heap memory, created in baseStack in Driver.main calling BaseStack Ctor
    calling List Ctor calling ListEngine Ctor for the ListEngine object.
    16 bytes of heap memory, created in Driver.main calling Ctor for the MyRec object.
    32 bytes of heap memory, created in Node Ctor calling NodeEngine Ctor for the NodeEngine object.
    16 bytes of heap memory, created in Driver.main calling Ctor for the MyRec object.
    32 bytes of heap memory, created in Node Ctor calling NodeEngine Ctor for the NodeEngine object.
    16 bytes of heap memory, created in Driver.main calling Ctor for the MyRec object.
    32 bytes of heap memory, created in Node Ctor calling NodeEngine Ctor for the NodeEngine object.
    
    The commands are:
        is(e)mpty, (i)nsert, (p)op,
        (a)dvance pre, advance (n)ext,
        (r)emove, (t)op, p(u)sh,
        (v)iew, (w)rite, (W)rite reverse,
    
    Please enter a command: ^D [List 1 has been jettisoned]
    
    No memory leaks! All memory has been correctly deallocated.
    
    

    Now test your code with the insert, remove, insert (push, pop, push)

    % ./Driver1 -x
    [List 1 has been allocated]
    
    The commands are:
        is(e)mpty, (i)nsert, (p)op,
        (a)dvance pre, advance (n)ext,
        (r)emove, (t)op, p(u)sh,
        (v)iew, (w)rite, (W)rite reverse,
    
    Please enter a command: u
    
    Please enter a number to push to stack: 1
    [List 1 - Inserting node]
    
    The commands are:
        is(e)mpty, (i)nsert, (p)op,
        (a)dvance pre, advance (n)ext,
        (r)emove, (t)op, p(u)sh,
        (v)iew, (w)rite, (W)rite reverse,
    
    Please enter a command: p
    
    [List 1 - Removing node]
    [List 1 - Advancing next]
    
    Number popped from list is: 1
    
    The commands are:
        is(e)mpty, (i)nsert, (p)op,
        (a)dvance pre, advance (n)ext,
        (r)emove, (t)op, p(u)sh,
        (v)iew, (w)rite, (W)rite reverse,
    
    Please enter a command: u
    
    Please enter a number to push to stack: 1
    [List 1 - Inserting node]
    
    The commands are:
        is(e)mpty, (i)nsert, (p)op,
        (a)dvance pre, advance (n)ext,
        (r)emove, (t)op, p(u)sh,
        (v)iew, (w)rite, (W)rite reverse,
    
    Please enter a command: w
    
    List 1 has 1 items in it:
    [List 1 - Advancing next]
    element 1: 1
    [List 1 - Advancing next]
    ------------ TRACKED MEMORY ------------
    36 bytes of heap memory, created in baseStack in Driver.main calling BaseStack Ctor
    calling List Ctor calling ListEngine Ctor for the ListEngine object.
    16 bytes of heap memory, created in Driver.main calling Ctor for the MyRec object.
    32 bytes of heap memory, created in Node Ctor calling NodeEngine Ctor for the NodeEngine object.
    
    The commands are:
        is(e)mpty, (i)nsert, (p)op,
        (a)dvance pre, advance (n)ext,
        (r)emove, (t)op, p(u)sh,
        (v)iew, (w)rite, (W)rite reverse,
    
    Please enter a command: ^D
    
    

11. At this point, you should test both your Drivers extensively. We have provided you 2 public executables, which you can run via

    $ ~/../public/hw5/java/Driver1 [-x]
    

    $ ~/../public/hw5/java/Driver2 [-x]
    

12. Be sure to test that the output of your calculator still makes sense and matches the solution, you can access the public executable via
    

    $ ~/../public/hw5/java/Calc [-x]
    

    
    
13. Make sure that you have fully commented your program and added method and file headers for any files and methods you edited. Note that for this assignment you must comment the methods of BaseStack.java. This is an exception to the rule that you do not have to comment methods which you did not write. Make sure your style follows the Style Outline for CSE 12. Then turn in your program by following The Turnin Procedure.

    Note that, in order for your homework to be collected correctly, you must name your file List.java and the file must be located in a folder called hw5/java in your home directory.

 

Assignment •  Development Guide •  Code •  Checklist •