1. The list you work with is made up of items of the Node class. You must look at the framework's Node.java file to understand how to use Node objects. Part 1 starter code ------------------- Here is code to get you started. It includes comments showing where you need to put your own code: // Create node to insert: Node node = new Node(i); if (head == null) { // List is empty, so node is the new head: head = node; numberNodes++; animate(head); return; } Node current = head; Node previous = null; // Traverse list to find insert point: // Insert between previous and current: // Case 1: insert at the beginning: // else Case 2: insert in the middle or at the end of the list Part 2 starter code ------------------- Here is code to get you started on part 2. It includes comments showing where you need to put your own code: Node current = head; Node previous = null; // Look for node to delete: // If not found, return false: if (current == null) { return false; } animate(head, current, Visualizer.ACTION_DELETE); // Delete node: // Case 1: Its the head node: // else Case 2: Its not the head node: Part 1 notes ------------ First note the following provided code: // Create node to insert: Node node = new Node(i); This code sets up a Node object called node with the value of the passed in parameter "i". This will be the node we must insert into the list. Consider what code is needed under the comment: // Traverse list to find insert point: You will need a while loop that will look through the list item by item. Notice the 2 lines of code that were provided just before this comment: Node current = head; Node previous = null; First look at the framework's Node class and notice its key functions: getData(), setData(), getNext(), and setNext(). getData() and setData() get/set the the value of the node you call it on. getNext() and setData() get/set a reference (link) to the next node in the list. You will need to make use of these functions in this assignment. Your traversal loop should iterate as long as current is not null and the value of the current node is less than or equal to the value you are supposed to insert, which was passed in to the insert function as the int parameter "i". To get the value of the current node you must use current's getData() function. As long as the current value is less than or equal to i, you must keep looking further through the list to find the insert point. In order to do this, you must change the values of previous and current within your traversal loop. The first thing you must do inside your while loop is to call the framework animate method passing it head and current (in that order). Next, you will change previous to be the value of current. Then you will change current to refer to the next item in the list. You get the next item by using current's getNext() function. That is all you do in your loop. If your loop is correct, it will simply look through the list until it finds the insertion point. The insertion point will be between the values of previous and current. Your traversal loop does not do the insert. It just looks through the list and ends with previous and current bounding the insertion point. Next you see the comment: // Insert between previous and current: // Case 1: insert at the beginning: You need an if statement to detect case 1. When will it be case 1? What is the condition that implies that you are inserting at the beginning of the list? Note that besides previous and current, you also have access to a variable called "head" that points to (refers to) the head of the list. Keep in mind that the list is an ordered list. It starts at head (with the smallest value) and then the other values follow in order from smaller to larger until you reach the end of the list, which is indicated by a null link from the last item. You will be inserting at the beginning of the list when current is equal to head (current == head). What do you do inside this "if" block? First, you will call animate as follows: animate(head, head, Visualizer.ACTION_INSERT_BEFORE); Then you will insert the new node (the object called "node") between previous and head. You need to change node's link to point to the current head of the list. then you need to change head to point to node. You do not need to do anything to previous because it should already be null in this case. Next you see the comment: // else Case 2: insert in the middle or at the end of the list That means case 2 must be an "else" block following your case 1 "if" block. What do you need to do in case 2? First, call animate as: animate(head, previous, Visualizer.ACTION_INSERT_AFTER); Then you need to insert node between previous and current. Look at the pictures in your book in figures 14.17a through 14.17d. You see that you must set the link in node to point to current and you must set the link in previous to point to node. Part 2 notes ------------ Consider what code should follow the comment: // Look for node to delete: You should use a while loop to look through the linked list to find the node to delete, which is the node with the value equal to the passed in parameter i. That means your while loop should keep looking as long as the current pointer is not null and the value of the current node is not i. The first statement of this while loop must be: animate(head, current); Within the loop after that, you should make sure you have not reached a node with a data value greater than i. If you have encountered such a node, then, since the list is sorted, you know that the list cannot possibly contain i because all further values will also be greater than i. So, if you reach this situation, you should exit the function right there with a false return value. Otherwise, you have not exceeded i yet and you need to keep the loop going. To do this you need to update previous and current. previous will get the value of current and current will get the value of current's next node link. You can review the part 1 comments to remember about the Node functions needed in your code. After your loop, your code needs to know whether the node was found or not. If current is null, then you reached the end of the list without finding a matching node to delete. If this happens it is again time to be done with the function by returning false. Remember that if you have an if statement whose body returns false, there is no need for the code that follows that if statement to be wrapped in an else block. It is better to do like this: if (some condition) { some code; some more code; return false; // or true } // no need for else here. // Just start the code that can only happen if the "if" was not taken. next statement; Now back to discussing the starter code. There is another animate call here (see starter code). Then we need to consider the next comment: // Delete node: // Case 1: Its the head node: How do we know it is the head node we need to delete? This should be very obvious. When current == head. In this case, we are deleting the head node from the list. The way this is done is to change the list's head pointer to point to the next node after the current head. Once that is done, no one will see the old head again because you have to start at head and it has been changed. So, this effectively deletes the old head from the list. Do not do a return here because the starter comments indicate that the following code needs to be the else block for this code: // else Case 2: Its not the head node: If it is not the head node we are deleting, then it is some other node in the list (pointed to by current). To delete it, you just need to move the highway around it so it is bypassed. That means you will change previous' next node link to be the next node link of current. This will cause current (the deleted node) to no longer be on the highway, so to speak. Anyone going through the list after this will come to previous and then they will go to the node after current. The ending brace of this else block ends your part 2 code. 

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~``

/* Visualizer * Anderson, Franceschi */

import javax.swing.*; import java.awt.*; //import java.awt.event.*; import java.util.ArrayList;

public class Visualizer extends JPanel { public static final int nodeWidth = 100; public static final int nodeHeight = 100; public static final int halfWidth = nodeWidth / 2; public static final int halfHeight = nodeHeight / 2; public static final int qrtrWidth = nodeWidth / 4; public static final int qrtrHeight = nodeHeight / 4;

public static final int nodeSpacer = halfWidth;

/** node is drawn normally **/ public static final int ACTION_NONE = 0; /** node is drawn highlighted **/ public static final int ACTION_HIGHLIGHT = 1; /** indicator is drawn after node **/ public static final int ACTION_INSERT_AFTER = 2; /** indicator is drawn before node **/ public static final int ACTION_INSERT_BEFORE = 3; /** node is drawn with delete indicator **/ public static final int ACTION_DELETE = 4; /** node is drawn with retrieve indicator **/ public static final int ACTION_RETRIEVE = 5;

private int initialHeight = 0; private ArrayList nodeData = new ArrayList( );

/** * * creates a new Visualizer with the given width * and height in pixels. sets the preferred size * to those values, and makes the Visualizer visible. * **/ public Visualizer( int width, int height ) { super( );

initialHeight = height;

setSize( width,height ); setPreferredSize( new Dimension( width, height ) ); setVisible( true ); validate( );

} // end default constructor

/** * * draws all nodes currently contained in the list of nodes. * **/ protected void paintComponent( Graphics g ) { super.paintComponent( g );

for( int n = 0; n < nodeData.size( ); n++) { nodeData.get( n ).draw( g ); }

// the following lines let the scrollpane know to update revalidate( ); } // end paintComponent

/** * * convenience method that is the same as calling * drawList(Node, null, Visualizer.ACTION_NONE) * so that the list is drawn with no nodes highlighted. * **/ public synchronized void drawList( Node head ) { nodeData.clear( ); Node current = head; //highlightData = target; //this.action = action; int x = nodeSpacer; int y = 50;

while( current != null ) { nodeData.add( new NodeWrapper( current, x, y, ACTION_NONE ) );

current = current.getNext( ); x += ( nodeWidth+nodeSpacer ); } setPreferredSize( new Dimension (x + nodeWidth + nodeSpacer, initialHeight ) ); repaint( ); } // end drawList

/** * * convenience method that is the same as calling * drawList(Node,Object,Visualizer.ACTION_HIGHLIGHT) * so that the list is drawn with a node that has a data * object matching the given object highlighted. * **/ public synchronized void drawList( Node head, int highlight ) { drawList( head, highlight, Visualizer.ACTION_HIGHLIGHT ); } // end drawList with a node highlighted

public synchronized void drawList( Node head, Node highlight ) { drawList( head, highlight, Visualizer.ACTION_HIGHLIGHT ); } // end drawList with a node highlighted

/** * * draws graphical representations of link list nodes. starting * from the head node, the list is traversed in order and each * node is displayed. if a node contains a data object that is * equal to target, that node will be drawn in such a way * as to stand out from the other nodes according to the * specified action. * * @param head the head Node of a linked list. * * @param highlight a data object to be matched against the data * objects in the list. if a match is found, that * node will be highlighted. to not highlight any * nodes, send null as the highlight parameter. * * @param action the action to display upon finding a matching node. * See the ACTION_actiontype final static ints * specified by this class. * **/ public synchronized void drawList( Node head, int target, int action ) { nodeData.clear( ); Node current = head; //highlightData = target; //this.action = action; int x = nodeSpacer; int y = 50;

while( current != null ) { if( target == current.getData( ) ) { nodeData.add( new NodeWrapper( current, x, y, action ) ); action = ACTION_NONE; } else { nodeData.add( new NodeWrapper( current,x , y, ACTION_NONE ) ); } current = current.getNext( ); x += ( nodeWidth + nodeSpacer ); } setPreferredSize( new Dimension( x + nodeWidth + nodeSpacer, initialHeight ) );

repaint( ); } // end draw list (head, target, action)

/** * Draws the list as described in drawList(Node, int, int), except that * here, the target node is found by reference instead of by value. * * @param head * @param target * @param action */ public synchronized void drawList( Node head, Node target, int action ) { nodeData.clear( ); Node current = head; //highlightData = target; //this.action = action; int x = nodeSpacer; int y = 50;

while( current != null ) { if( target == current ) { nodeData.add( new NodeWrapper( current, x, y, action) ); action = ACTION_NONE; } else { nodeData.add( new NodeWrapper( current, x, y, ACTION_NONE ) ); } current = current.getNext( ); x += ( nodeWidth + nodeSpacer ); } setPreferredSize( new Dimension( x + nodeWidth + nodeSpacer, initialHeight ) );

repaint( ); } // end draw list (head, target, action)

/** draw the reference to null **/ private void drawNullRef( Graphics g, int x, int y ) { int startY = y + ( ( int ) ( nodeHeight * ( 3.0f / 4.0f) ) ); int endY = y + ( int ) ( ( nodeHeight *1.5f ) ); g.drawLine( x, startY, x, endY ); g.drawLine( x - 10, endY, x + 10, endY ); g.drawLine( x - 5, endY + 5, x + 5, endY + 5 ); } // end draw null ref

/** draw reference arrows from node to node **/ private void drawRefs( Graphics g, NodeWrapper wn ) { int x = wn.getX( ); int y = wn.getY( ); Node n = wn.getNode( ).getNext( );

if( n == null ) { drawNullRef( g, x + halfWidth, y ); } else { for( int i = 0; i < nodeData.size( ); i++ ) { NodeWrapper nw = nodeData.get( i ); if( n == nw.getNode( ) ) { int targetX = nw.getX( ); int targetY = nw.getY( ); g.fillOval( x + halfWidth, y + ( (int ) ( nodeHeight * ( 3.0f / 4.0f ) ) ) - 3, 6, 6 ); g.drawLine( x + halfWidth, y + ( ( int ) ( nodeHeight * ( 3.0f / 4.0f ) ) ), x + nodeWidth + 13, y + ( ( int ) ( nodeHeight * ( 3.0f / 4.0f ) ) ) ); g.drawLine( x + nodeWidth + 13, y + ( ( int ) ( nodeHeight * ( 3.0f / 4.0f ) ) ), targetX - 13, targetY + 15 ); g.drawLine( targetX - 13, targetY + 15, targetX, targetY + 15 );

g.drawLine( targetX, targetY + 15, targetX - 7, targetY + 10 ); g.drawLine( targetX, targetY + 15, targetX - 7, targetY + 20 );

break; } } } } // end draw refs

/** * * detect if there is a node at the given the x,y coordinate. if * there is, it will be highlighted and that node will be returned. * * @return the node at the given coordinate, or null if there is no * node at the coordinate * **/ public Node selectNode( int mouseX, int mouseY ) { int x = 0; int y = 0;

int size = nodeData.size( ); Node n = null; for( int i = 0; i < size; i++ ) { x = nodeData.get( i ).getX( ); y = nodeData.get( i ).getY( );

if( x < mouseX && mouseX < x + nodeWidth && y < mouseY && mouseY < y + nodeHeight ) { // if it was selected, hightlight it ( nodeData.get( i ) ).setAction( ACTION_HIGHLIGHT );

// output.put( "panel clicked: \"" + ( nodeData.get( i ) ).getNode( ).getData( )+"\" selected" ); n = ( nodeData.get( i ) ).getNode( );

} else { // otherwise, no special treatment ( nodeData.get( i ) ).setAction( ACTION_NONE ); } } repaint( ); return n; } // end selectNode at coordinate

/** wraps a Node with extra information so it can be displayed in the Visualizer. **/ private class NodeWrapper { int nodeAction = ACTION_NONE; Node node = null; int x = 0; int y = 0;

NodeWrapper( Node n, int x, int y, int action ) { this.nodeAction = action; this.node = n; this.x = x; this.y = y;

}

public Node getNode( ) { return node; }

public int getX( ) { return x; }

public int getY( ) { return y; }

public void setAction( int action ) { this.nodeAction = action; }

/** draw the node at current x,y coord with current action type **/ void draw( Graphics g ) { // draw the node representation g.setColor( Color.BLACK ); g.drawRect( x, y, nodeWidth, nodeHeight ); // main rectangle g.drawLine( x, y + halfHeight, x + nodeWidth, y + halfHeight ); //horizontal line //g.drawLine( x + halfWidth, y + halfHeight, x + halfWidth,y+nodeHeight ); // vertical line

// in case the data.toString is really long, this will shrink the // font size so that it fits in the node drawing. int fontSize = 16; Font font = new Font( "SansSerif", Font.PLAIN, fontSize ); FontMetrics metrics = getFontMetrics( font ); String str = ""+node.getData( ); while( fontSize > 0 && metrics.stringWidth( str ) > nodeWidth - 10 ) { //System.out.println( "str: " + str + " width: " + metrics.stringWidth( str ) + " size: " + fontSize ); font = new Font( "SansSerif", Font.PLAIN, fontSize-- ); metrics = getFontMetrics( font ); }

g.setFont( font );

g.drawString( str, x + 5, y + 20 ); // data as a string

// draw the reference arrows drawRefs( g, this );

// determine which action should be used, draw anything special for it. if( nodeAction == ACTION_HIGHLIGHT ) { g.setColor( Color.BLUE ); g.drawRect( x, y, nodeWidth, nodeHeight ); // main rectangle g.drawLine( x, y + halfHeight, x + nodeWidth, y + halfHeight ); //horizontal line // g.drawLine(x+halfWidth,y+halfHeight,x+halfWidth,y+nodeHeight); // vertical line g.drawString(str,x+5,y+20); g.setColor(Color.magenta); drawRefs(g,this); } else if( nodeAction == ACTION_INSERT_BEFORE ) { g.setColor( Color.GREEN ); int offset = nodeSpacer>>1; g.drawLine( x - offset, y, x - offset, y - 30 ); // arrow shaft g.drawLine( x - offset, y, x - offset + 5, y - 10 ); // arrow left g.drawLine( x - offset, y, x - offset - 5, y - 10 ); // arrow right } else if( nodeAction == ACTION_INSERT_AFTER ) { g.setColor( Color.GREEN ); int offset = nodeSpacer >> 1; g.drawLine( x + nodeWidth + offset, y, x + nodeWidth + offset, y - 30 ); // arrow shaft g.drawLine( x + nodeWidth + offset, y, x + nodeWidth + offset + 5, y - 10 ); // arrow left g.drawLine( x + nodeWidth + offset, y, x + nodeWidth + offset - 5, y - 10 ); // arrow right } else if( nodeAction == ACTION_DELETE ) { g.setColor( Color.red ); g.drawLine( x - 10, y - 10, x + nodeWidth + 10, y + nodeHeight + 10 ); g.drawLine( x - 10, y + nodeHeight + 10, x + nodeWidth + 10, y - 10 ); } else if( nodeAction == ACTION_RETRIEVE ) { g.setColor( Color.YELLOW ); g.drawRect( x - 10, y - 10, nodeWidth + 20, nodeHeight + 20 ); } // end drawing decision block

} // end draw

} // end node wrapper

} // end visualizer

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

/* Node * Anderson, Franceschi */

public class Node { /** reference to the next node in the list **/ private Node nextNode;

/** the data object held by this node **/ private int data;

/** * * construct a new node with the given Object as data * **/ public Node( int i ) { data = i; }

/** * * construct a new node with the given Object as data * and references to the next and previous nodes. * **/ public Node( int i, Node next ) { data = i; nextNode = next; }

/** * * set the reference to the next node * **/ public void setNext( Node n ) { nextNode = n; }

/** * * return the reference to the next node * @return reference to the next node, or null if there is no next node * **/ public Node getNext( ) { return nextNode; }

/** * * set the data object held by this node * **/ public void setData( int i ) { data = i; }

/** * * get the data object held by this node * **/ public int getData( ) { return data; }

} // end node class

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

/* LinkList * Anderson, Franceschi */

/** * this class is a concrete implementation of the AbstractList. * * properties of this implementation are such that: - the list is singly linked * - data contained in the nodes is limited to integers - nodes are sorted in * ascending order of data - duplicate data is allowed - note that duplicate * data may cause inconsistent behavior in the Visualizer because the delete * method searches for the first instance of data. if a node besides the first * one is highlighted, the first one will still be deleted. */ public class LinkList extends AbstractList { private Node head = null;

public LinkList() { super(500, 400); v.drawList(head); }

public LinkList(Node head) { super(500, 400); // set size for visualizer // set up the list head = head;

animate(head); }

public void insert(int i) { // ***** Student writes the body of this method *****

// code the insert method of a linked list of ints // the int to insert in the linked list is i

// we call the animate method inside the body of this method // as you traverse the list looking for the place to insert, // call animate as follows:

// animate(head, current); // where head is the instance variable head of the linked list // current is the node that you are visiting

// you can start coding now

// in order to improve the animation (this is optional): // just before inserting, i.e. connecting the nodes, // make the call

// animate(head, previous, Visualizer.ACTION_INSERT_AFTER);

// where head is the instance variable head of the linked list // previous is the node (not null) after which to insert

// if you are inserting at the beginning of the list, // just before inserting, make the call

// animate(head, head, Visualizer.ACTION_INSERT_BEFORE);

// where head is the instance variable head of the linked list // // Part 1 student code starts here:

// Part 1 student code ends here.

numberNodes++; // call animate again to show the status of the list animate(head); }

public boolean delete(int i) { // ***** Student writes the body of this method *****

// code the delete method of a linked list of ints // the int to delete in the linked list is i // if deletion is successful, return true // otherwise, return false

// we call the animate method inside the body of this method // as you traverse the list looking for the node to delete, // call animate as follows:

// animate(head, current);

// where head is the instance variable head of the linked list // current is the node that you are visiting

// you can start coding now

// in order to improve the animation (this is optional): // just before deleting, i.e. connecting the nodes, // make the call

// animate(head, current, Visualizer.ACTION_DELETE);

// where head is the instance variable head of the linked list // current is the node that you are deleting // // Part 2 student code starts here:

// Part 2 student code ends here.

// At this point, the item has been deleted. // Decrement the number of nodes: numberNodes--; // Call animate again to show the status of the list: animate(head); return true; }

public int count() { int n = 0; Node current = head; while (current != null) { animate(head, current); n++; current = current.getNext(); } return n; }

public void traverse() { traversal = ""; Node current = head; while (current != null) { animate(head, current); traversal += (current.getData() + " "); current = current.getNext(); } v.drawList(head); }

public void clear() { head = null; v.drawList(head); }

public void animate(Node h, Node nd) { v.drawList(h, nd); delay(1000); }

public void animate(Node h) { v.drawList(h); }

public void animate(Node h, Node nd, int mode) { v.drawList(h, nd, mode); delay(1000); } }

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

/* LinkedListPractice * Anderson, Franceschi */

import java.awt.*; import java.awt.event.*; import javax.swing.*;

public class LinkedListPractice extends JFrame { /* INSTANCE VARIABLES These variables are directly responsible for handling the student code: instantiating an object of the student's list, displaying it graphically, manipulating it by calling the various methods. */

/** * rationale: use AbstractList so that an instructor can have * students create any other list type and still * be able to use all the same method calls. The only * change that needs to be made to this code is * changing the instantiation to whatever type the * instructor wants. **/ private AbstractList list;

/** * this class is on its honor to not modify the Visualizer. * the list instance returns a reference to its Visualizer * so that this class can add it in to the JFrame, but this * class should never directly modify that instance. **/ private Visualizer v;

/* GUI ELEMENTS */

// controls private JPanel controls; // holds the following: private JPanel dataPanel; // text box and label private JButton insertNode; private JButton deleteNode; private JButton traverseList; private JButton clearList; private JButton countNodes;

private JTextField data; // text box and label private JLabel dataLabel; // for dataPanel

// output private JScrollPane outputPane; // holds the output text area private JTextArea outputArea; // the output text area private String outputDisplay = ""; // message to outputArea private JScrollPane visualPane; // holds the Visualizer

private boolean mouseDisabled = false; // prevent clicking while drawing

private static int MAX_DATA_LENGTH = 4; // max chars allowed in the data field

/* CONSTRUCTOR */

/** * instantiates a new ListControl with the given width and height. * sets up the controls, initializes the Visualizer, makes everything * visible. * **/ public LinkedListPractice( int width, int height ) { super( ); // call to Object( ) for completeness setTitle( " Linked List Visualizer" );

// set up the list and visualizer list = new LinkList( ); v = list.getVisualizer( ); visualPane = new JScrollPane( v );

// instantiate GUI list controls

dataPanel = new JPanel( ); dataPanel.setLayout( new GridLayout( 2,1 ) );

data = new JTextField( ); dataLabel = new JLabel( "Node Data:" );

dataPanel.add( dataLabel ); dataPanel.add( data );

controls = new JPanel( ); controls.setLayout( new GridLayout( 6, 1 ) );

insertNode = new JButton( "insert" ); deleteNode = new JButton( "delete" ); traverseList = new JButton( "traverse" ); countNodes = new JButton( "count" ); clearList = new JButton( "clear" );

// set up handlers for controls // private inner classes seem more readable // than anonymous inner classes or one large handler data.addKeyListener( new DataListener( ) ); insertNode.addActionListener( new ActionInsert( ) ); deleteNode.addActionListener( new ActionDelete( ) ); traverseList.addActionListener( new ActionTraverse( ) ); countNodes.addActionListener( new ActionCount( ) ); clearList.addActionListener( new ActionClear( ) );

// add controls to the control pane controls.add( dataPanel ); controls.add( insertNode ); controls.add( deleteNode ); controls.add( traverseList ); controls.add( countNodes ); controls.add( clearList );

// set up GUI output outputArea = new JTextArea( 5, 40 ); outputPane = new JScrollPane( outputArea ); outputArea.setEditable( false );

// set up ListControl GUI setDefaultCloseOperation( JFrame.EXIT_ON_CLOSE ); getContentPane( ).setLayout( new BorderLayout( ) ); getContentPane( ).add( visualPane,BorderLayout.CENTER ); getContentPane( ).add( controls,BorderLayout.WEST ); getContentPane( ).add( outputPane,BorderLayout.SOUTH );

setSize( width,height ); setVisible( true ); doLayout( ); validate( ); } // end default constructor

/* METHODS */

/** turn off all the buttons so they can't be clicked during operations **/ private void disableButtons( ) { insertNode.setEnabled( false ); deleteNode.setEnabled( false ); traverseList.setEnabled( false ); clearList.setEnabled( false ); countNodes.setEnabled( false ); mouseDisabled = true; }

/** turn on the buttons **/ private void enableButtons( ) { insertNode.setEnabled( true ); deleteNode.setEnabled( true ); traverseList.setEnabled( true ); clearList.setEnabled( true ); countNodes.setEnabled( true ); mouseDisabled = false; }

/** give focus to the text field and select any text it holds **/ private void selectData( ) { data.select( 0, data.getText( ).length( ) ); data.requestFocusInWindow( ); }

private int getData( ) throws NumberFormatException { return ( new Integer( data.getText( ) ) ).intValue( ); }

/* PRIVATE INNER CLASSES - action handlers each class is for a specific button, so the event source is not checked

for any method that requires nodes to be highlighted, a new thread is created and started to handle calling the method. this allows the GUI to handle the highlighting and delay routines appropriately. */

private class ActionInsert implements ActionListener { public void actionPerformed( ActionEvent e ) { //SwingUtilities.invokeLater( new InsertThread( ) ); ( new InsertThread( ) ).start( ); }

private class InsertThread extends Thread { public void run( ) { disableButtons( ); try { int i = getData( ); outputDisplay += "insert called with " + i + " as data "; outputArea.setText( outputDisplay ); list.insert(i); } catch ( Exception e ) { outputDisplay += "invalid number "; outputArea.setText( outputDisplay ); } enableButtons( ); selectData( ); } } } // end ActionInsert

private class ActionDelete implements ActionListener { public void actionPerformed( ActionEvent e ) { ( new DeleteThread( ) ).start( ); }

private class DeleteThread extends Thread { public void run( ) { disableButtons( ); outputDisplay += ( "delete called with " + data.getText( ) + ": " ); outputArea.setText( outputDisplay ); try { boolean deleted = list.delete( new Integer( data.getText( ) ).intValue( ) ); outputDisplay += "node " + ( (deleted)?"deleted ":"not found " ); outputArea.setText( outputDisplay ); } catch( NumberFormatException nfe ) { outputDisplay += ( "data not an integer " ); outputArea.setText( outputDisplay ); } enableButtons( ); selectData( ); } } }

private class ActionTraverse implements ActionListener { public void actionPerformed( ActionEvent e ) { outputDisplay += "traversing the list: "; outputArea.setText( outputDisplay ); ( new Thread( ){ public void run( ){ disableButtons( ); list.traverse( ); outputDisplay += ( list.getTraversal( ) + " " ); outputArea.setText( outputDisplay ); enableButtons( ); selectData( ); } }).start( ); } } // end ActionTraverse

private class ActionCount implements ActionListener { public void actionPerformed( ActionEvent e ) { ( new CountThread( ) ).start( ); }

private class CountThread extends Thread { public void run( ) { disableButtons( ); outputDisplay += "count called: "; outputArea.setText( outputDisplay ); int n = list.count( ); outputDisplay += ( "number of nodes = " + n + " " ); outputArea.setText( outputDisplay ); enableButtons( ); selectData( ); } } } // end ActionCount

private class ActionClear implements ActionListener { public void actionPerformed( ActionEvent e ) { ( new ClearThread( ) ).start( ); }

private class ClearThread extends Thread { public void run( ) { disableButtons( ); outputDisplay += "clear list called "; outputArea.setText( outputDisplay ); list.clear( ); enableButtons( ); selectData( ); } } } // end ActionClear

/** detects when key is entered in to data text field, and ensures that the field is limited to MAX_DATA_LENGTH. **/ private class DataListener extends KeyAdapter { int key = 0; // which key was pressed //keyPressed will detect back space, but doesn't properly consume // the event, so the field still gets it. so, trap the key here // and assign it to variable key. thankfully by its very nature // keyPressed happens before keyTyped. public void keyPressed( KeyEvent e ) { key = e.getKeyCode( ); }

// keyTyped will properly consume the event, but can't detect when // backspace was pressed. it also lets arrow keys, home, etc. through. // key has been trapped by keyPressed, so it can be properly compared // to backspace, and consumed if it is not back space and field is // over 15 chars. public void keyTyped( KeyEvent e ) { // must compare to MAX_DATA_LENGTH-1 because the key currently being examined // will be the last character in the field.

if( key == KeyEvent.VK_BACK_SPACE ) { // never consume backspace return; } if( data.getText( ).length( ) > MAX_DATA_LENGTH-1 || key < KeyEvent.VK_0 || key > KeyEvent.VK_9 ) { // if field is full, or invalid value entered, consume the key e.consume( ); return; } } }

public static void main( String args[] ) { LinkedListPractice app = new LinkedListPractice( 600, 400 ); } }

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

/* AbstractList * Anderson, Franceschi */

public abstract class AbstractList { /* INSTANCE VARIABLES */

/** * a Visualizer instance is maintained here so that the student * can call it from the child class without worrying about the * implementation of the Visualizer. This is intended to mimic * the use of a Graphic object in the Swing or AWT package. **/ protected Visualizer v;

protected int numberNodes; protected String traversal; // holds current traversal of the list

/* CONSTRUCTORS */

/** * instantiate with the given GUI width and height for the Visualizer. * **/ public AbstractList( int width, int height ) { v = new Visualizer( width, height ); numberNodes = 0; }

/* METHODS STUDENTS MUST OVERRIDE */

/** * * insert an object in to the list. * **/ public abstract void insert( int i );

/** * * delete a node from the list based on reference. * * @ return true if the node was deleted, false otherwise **/

/** * * delete a node from the list based on data. * * @return true if the node was deleted, false otherwise * **/ public abstract boolean delete( int i );

/** * * returns the number of Nodes in the list. * **/ public abstract int count( );

/** * * walks the list and displays the data it contains. * **/ public abstract void traverse( );

/** * * removes all nodes from the list. * **/ public abstract void clear( );

/* METHODS FOR CONTROLLING VISUALIZER */

/** * * sets the width and height in pixels for the visualizer. * **/ public void setSize( int width, int height ) { v.setSize( width, height ); v.validate( ); }

/** * * returns a reference to the Visualizer being used by this object. * Any object calling this method is on its honor to not modify * the Visualizer. * **/ public Visualizer getVisualizer( ) { return v; }

/** * * simple delay routine that makes the thread sleep for the given * number of milliseconds. useful for when a node is being * highlighted by the visualizer. * **/ public void delay( int milliseconds ) { try { Thread.sleep( milliseconds ); } catch ( Exception e ) { System.out.println(" e: "+e ); } }

/* * * the following are wrapper methods to make calling the visualizer * a little more convienient. see the wrapped Visualizer methods * for more information. * */ /* public void drawList( Node headNode ) { v.drawList( headNode ); }

public void drawList( Node headNode, int highlight ) { v.drawList( headNode, highlight ); }

public void drawList( Node headNode, Node highlight ) { v.drawList( headNode, highlight ); }

public void drawList( Node headNode, int target, int action ) { v.drawList( headNode, target, action ); }

public void drawList( Node headNode, Node target, int action ) { v.drawList( headNode, target, action ); } */ public String getTraversal( ) { return traversal; }

} // end abstract list