~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~`` /* Visu
ID: 3914559 • Letter: #
Question
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~``
/* 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<NodeWrapper> nodeData = new ArrayList<NodeWrapper>( );
/**
*
* 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_<i>actiontype</i> 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
Explanation / Answer
/* 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:
Node node = new Node(i);
Node current = head;
Node previous = null;
while(current != null && current.getData() <= i) {
animate(head, current);
previous = current;
current = current.getNext();
}
if (current == head) {
// List is empty, so node is the new head:
animate(head, head, Visualizer.ACTION_INSERT_BEFORE);
node.setNext(head);
head = node;
} else {
animate(head, previous, Visualizer.ACTION_INSERT_AFTER);
node.setNext(current);
previous.setNext(node);
}
// 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:
Node current = head;
Node previous = null;
while(current != null && current.getData() != i) {
animate(head, current);
if (current.getData() > i) {
return false;
}
previous = current;
current = current.getNext();
}
if( current == null) {
return false;
}
animate(head, current, Visualizer.ACTION_DELETE);
if( current == head) {
head = head.getNext();
} else {
previous.setNext(current.getNext());
}
// 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);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.