Transcript An Example

Programming and Problem Solving
With Java
Chapter 12: Lists
Writing ListClasses
Example: Infinite Precision Arithmetic
Example: Sorting a Lsit
Example: A Set Type
Doubly Linked Lists
Computer Security
Copyright 1999, James M. Slack
Introduction
Dynamic data structure
Grows and shrinks as program runs
Example: Java’s standard Vector class
Lists
Used often in everyday life (groceries, to-do, …)
Will also look at sets in this chapter
Dynamic data structures in later chapters
Stacks
Queues
Trees
Programming and Problem Solving With Java
2
Introduction
Characteristics of lists
There’s a first element
There’s a last element
All others have predecessor and successor
Operations on lists
Add element
Delete element
Search for element
Sort the elements
Programming and Problem Solving With Java
3
Writing List Classes: CharList
Character list class
Allows adding and deleting characters from either end
Operations
toString
insertFirst
insertLast
empty
removeFirst
removeLast
Programming and Problem Solving With Java
Returns contents in a string.
Put new character value at beginning
Put new character value at end
Returns true if empty
Remove node at beginning, return value
Remove node at end, return value
4
Writing List Classes: CharList
Short example
// Short demonstration of how to use the CharList
// class
import CharList;
public class DemoCharList
{
public static void main(String[] args)
{
CharList myCharList = new CharList();
[H i ! ]
Removed H
[i ! ]
// Insert some characters
myCharList.insertFirst('i');
myCharList.insertLast('!');
myCharList.insertFirst('H');
// Use the toString() method
System.out.println(myCharList);
// Remove character
System.out.println("Removed "
+ myCharList.removeFirst());
}
}
// Use the toString() method again
System.out.println(myCharList);
Programming and Problem Solving With Java
5
Writing List Classes: CharList
Longer example (uses TextMenu class)
//
//
//
//
//
This program lets you add characters onto
either end of a linked list, and remove them from either
end. It makes sure you don't try to remove characters
from an empty list. This is a demonstration of how to use
the CharList class.
import Keyboard;
import TextMenu;
import CharList;
Te xtM e nu
public class CharListTest extends TextMenu
{
static final int ADD_FIRST_COMMAND = 1;
static final int ADD_LAST_COMMAND = 2;
static final int REMOVE_FIRST_COMMAND = 3;
static final int REMOVE_LAST_COMMAND = 4;
CharList
CharListTe s t
// Constructor - set up menu for the editor
public CharListTest()
{
super("Character List Menu");
list = new CharList();
addSelection("Add first", '1', ADD_FIRST_COMMAND);
addSelection("Add last", '2', ADD_LAST_COMMAND);
addSelection("Remove first", '3', REMOVE_FIRST_COMMAND);
addSelection("Remove last", '4', REMOVE_LAST_COMMAND);
addSelection("Quit", '5', TextMenu.QUIT);
}
Programming and Problem Solving With Java
6
Writing List Classes: CharList
// Event dispatcher
public int handleEvent(int event)
throws java.io.IOException
{
switch (event)
{
case ADD_FIRST_COMMAND:
list.insertFirst(Keyboard.readChar(
"Enter character to add to beginning: "));
break;
case ADD_LAST_COMMAND:
list.insertLast(Keyboard.readChar(
"Enter character to add to end: "));
break;
case REMOVE_FIRST_COMMAND:
if (list.empty())
{
System.out.println("List is empty!");
}
else
{
System.out.println("Removed " + list.removeFirst()
+ " from beginning of list");
}
break;
case REMOVE_LAST_COMMAND:
if (list.empty())
{
System.out.println("List is empty!");
}
else
{
System.out.println("Removed " + list.removeLast()
+ " from end of list");
}
break;
}
System.out.println("List is now: " + list);
return event;
}
Programming and Problem Solving With Java
7
Writing List Classes: CharList
// Instance variables
CharList list;
public static void main(String[] args)
throws java.io.IOException
{
CharListTest listExample = new CharListTest();
}
}
listExample.run();
+--- Character List Menu --| 1) Add first
2) Add last
| 4) Remove last
5) Quit
| Enter selection: 1
Enter character to add to beginning: b
List is now: [b ]
+--- Character List Menu --| 1) Add first
2) Add last
| 4) Remove last
5) Quit
| Enter selection: 1
Enter character to add to beginning: a
List is now: [a b ]
+--- Character List Menu --| 1) Add first
2) Add last
| 4) Remove last
5) Quit
| Enter selection: 2
Enter character to add to end: c
List is now: [a b c ]
Programming and Problem Solving With Java
3) Remove first
3) Remove first
3) Remove first
8
Writing List Classes: CharList
CharList is linked structure: each character on the
list keeps track of its successor
CharListNode is separate class
Space for the character
Reference to next character in list
Data value
'A'
Reference to next
node in the list
Last node references null (special value)
Programming and Problem Solving With Java
9
Writing List Classes: CharList
CharListNode class
class CharListNode
{
// Constructor
public CharListNode(char item, CharListNode next)
{
setItem(item);
setNext(next);
}
// getItem: Returns the item value
public char getItem() { return item; }
Data value
'A'
// getNext: Returns the next item
public CharListNode getNext() { return next; }
// setItem: Sets the item to the given value
public void setItem(char item)
{
this.item = item;
}
Reference to next
node in the list
// setNext: Sets the next item to the given object
public void setNext(CharListNode next)
{
this.next = next;
}
// Instance vaiables
private char item;
private CharListNode next;
Programming}and Problem Solving With Java
10
Writing List Classes: CharList
CharList class
References first and last nodes of the list
Reference
to first node
CharList
CharListNode
'A'
CharListNode
'B'
CharListNode
'C'
CharListNode
'D'
null
Reference
to last node
Number
of nodes
4
Constructor
// Default constructor
public CharList()
{
first = null;
last = null;
numNodes = 0;
}
Programming and Problem Solving With Java
Reference
to first node
Makes empty
CharList
Reference
to last node
Number
of nodes
CharList
null
null
0
11
Writing List Classes: CharList
Inserting a new node: insertFirst()
// insertFirst: Inserts a new item at the beginning of the list.
public void insertFirst(char item)
{
CharListNode newNode = new CharListNode(item, first);
}
newNode
numNodes++;
first = newNode;
if (last == null)
{
// Special case: An empty list.
// This new node is the last node in the list.
last = newNode;
}
'E'
After creating
the new node
'A'
'B'
4
Programming and Problem Solving With Java
newNode
'C'
'D'
null
'E'
After making
the new node
the first node
'A'
'B'
'C'
'D'
5
12
null
Writing List Classes: CharList
Inserting a new node: insertLast()
// insertLast: Inserts a new item at the end of the list
public void insertLast(char item)
{
CharListNode newNode = new CharListNode(item, null);
}
numNodes++;
if (first == null)
{
// Special case: this node is the first node in the list.
first = newNode;
}
else
{
// General case: this is not the only node in the list.
// Make the last node point to this one and make this
// the new last node.
last.setNext(newNode);
}
last = newNode;
After making
the new node
the last node
After creating
the new node
newNode
'E'
'A'
'B'
'C'
4
Programming and Problem Solving With Java
'D'
null
newNode
'E'
null
'A'
'B'
'C'
'D'
5
13
Writing List Classes: CharList
Removing a node:
removeFirst()
Before
removing first
node
node
'A'
'B'
'C'
'D'
null
'D'
null
'D'
null
4
Link around
first node
node
'A'
'B'
'C'
4
Delete first
node
node
'B'
Programming and Problem Solving With Java
3
'C'
14
Writing List Classes: CharList
Removing a node: removeFirst()
// removeFirst: Remove the first element from the list and
//
return its value. If item is currentNode,
//
then sets currentNode to next node, unless
//
deleting the last node. In that case, sets
//
currentNode to previous node.
// Note: The list cannot be empty
public char removeFirst()
{
Debug.assert(!empty(),
"CharList.removeFirst(): List is empty");
CharListNode node = first;
// Remove the first node from the list.
first = first.getNext();
if (empty())
{
// Special case: this is the only node in the list.
last = null;
}
numNodes--;
}
// Return the value of the removed node.
return node.getItem();
Programming and Problem Solving With Java
15
Writing List Classes: CharList
Before
removing last
node
Removing a node:
removeLast()
'A'
node
'B'
'C'
'D'
null
'D'
null
'D'
null
4
Find the node
before the last
'A'
previousNode
'B'
node
'C'
4
Take last node
out of list
'A'
Programming and Problem Solving With Java
3
previousNode
'B'
'C'
node
null
16
Writing List Classes: CharList
Removing
a
node:
removeLast()
// removeLast: Remove the last element from the list and
//
return its value. If item is currentNode,
//
then sets currentNode to next node, unless
//
deleting the last node. In that case, sets
//
currentNode to previous node.
// Note: The list cannot be empty
public char removeLast()
{
Debug.assert(!empty(), "CharList.removeLast(): List is empty");
CharListNode node = last, previousNode;
if (last == first)
{
// Special case: only one node in the list
last = first = null;
}
else
{
// General case: find second-to-last node
previousNode = first;
while (previousNode.getNext() != last)
{
previousNode = previousNode.getNext();
}
// Make second-to-last the last node
previousNode.setNext(null);
last = previousNode;
}
}
numNodes--;
// Return the value of the removed node.
return node.getItem();
Programming and Problem Solving With Java
17
Writing List Classes: CharList
empty(), count(), toString()
// empty: Returns true if the list is empty
public boolean empty()
{
return first == null;
}
// count: Returns the number of elements in the list
public int count()
{
return numNodes;
}
// toString: Returns a string representing the contents of
//
the list
public String toString()
{
CharListNode node = first;
String result = "[";
while (node != null)
{
result = result + node.getItem() + " ";
node = node.getNext();
}
}
return result + "]";
Programming and Problem Solving With Java
18
Writing List Classes: CharList
Problems with the CharList class
Can’t tell if particular value in the list (without displaying
the list and examining the output)
Can't insert a value in the middle
Can't remove a value from the middle
Can't traverse the list, except to display every element
Can't get a value from the list without removing it
Can't change a value in the list without removing it and
inserting the new value
Can only store characters
Programming and Problem Solving With Java
19
A General List Class
Additional features over CharList:
Store into the middle (not just ends)
Remove from middle
Check whether a particular value is in the list
Get values of elements inside the list
Store any object -- not just characters
To store and retrieve elements from middle of list
Need way to refer to list position
Will add current node marker
Will have methods for moving current node marker
Programming and Problem Solving With Java
20
A General List Class
List operations
append: Attach another list to end
count: Return number of nodes
toString: Return String version of list’s contents
find: Search for value. If in list, set the current node there
get: Return value in current node
goFirst: Change current node to beginning
goLast: Change current node to end
goNext: Change current node to next node
goPrevious: Change current node to previous node
insert: Put new value after current node
insertFirst: Put new value at beginning
Programming and Problem Solving With Java
21
A General List Class
List operations (continued)
insertLast: Put new value at end
isDefined: Return true if current node defined
empty: Return true if list empty
isFirst: Return true if current node is first node
isLast: Return true if current node is last node
put: Change value of current node
remove: Remove current node, return its value
removeFirst: Remove node at beginning of the list, return
its value
removeLast: Remove node at end of list, and return its
value
Programming and Problem Solving With Java
22
A General List Class: Line Editor
Today, most editors are full-screen
Move cursor with keys or mouse
Type at position of cursor
Older style: line editor
Make changes to one line at a time
Must specify line to change with a command
Not as easy to use as full-screen editor
Much easier to write, though
Programming and Problem Solving With Java
23
A General List Class: Line Editor
Example of line editor: MS-DOS edlin
C:\>edlin Hello.java
New file
*I
1:*class Hello
2:*{
3:* public static void main(String[] args)
4:* {
5:*
System.out.println("Hello!");
6:* }
7:*}
8:*^C
Line
commands
*1I
*L
*E
C:\>
1:*// Says Hello
2:*
3:*^C
1: // Says Hello
2:
3:*class Hello
4: {
5:
public static void main(String[] args)
6:
{
7:
System.out.println("Hello!");
8:
}
9: }
Programming and Problem Solving With Java
Current line
(marked
with *)
24
A General List Class: Line Editor
Will use List class to make line editor
Store each line in a list node
Commands
Show all lines with line numbers
Insert lines after a given line number
Delete a line
Quit the program
To insert lines
Type as many lines as desired
Type just period on line to end
Programming and Problem Solving With Java
25
A General List Class: Line Editor
Example run of line editor
+--- Edit Menu --| s) Show all lines
i) Insert lines
d) Delete a line
| q) Quit
| Enter selection: i
(Enter just a period to stop inserting lines)
: This is the first line in the editor. The
: editor is in insert mode. When a period is
: typed by itself, insert mode stops.
: .
+--- Edit Menu --| s) Show all lines
i) Insert lines
d) Delete a line
| q) Quit
| Enter selection: s
1: This is the first line in the editor. The
2: editor is in insert mode. When a period is
3: typed by itself, insert mode stops.
+--- Edit Menu --| s) Show all lines
i) Insert lines
d) Delete a line
| q) Quit
| Enter selection: i
After which line: 2
(Enter just a period to stop inserting lines)
: --- This is the new third line. --: .
Programming and Problem Solving With Java
26
A General List Class: Line Editor
Example run of line editor (continued)
+--- Edit Menu --| s) Show all lines
i) Insert lines
d) Delete a line
| q) Quit
| Enter selection: s
1: This is the first line in the editor. The
2: editor is in insert mode. When a period is
3: --- This is the new third line. --4: typed by itself, insert mode stops.
+--- Edit Menu --| s) Show all lines
| q) Quit
| Enter selection: d
Line to delete: 3
i) Insert lines
d) Delete a line
+--- Edit Menu --| s) Show all lines
i) Insert lines
d) Delete a line
| q) Quit
| Enter selection: s
1: This is the first line in the editor. The
2: editor is in insert mode. When a period is
3: typed by itself, insert mode stops.
+--- Edit Menu --| s) Show all lines
i) Insert lines
| q) Quit
| Enter selection: q
Are you sure you want to quit? (y/n): y
Programming and Problem Solving With Java
d) Delete a line
27
A General List Class: Line Editor
Design of the line editor program
Will use the TextMenu framework for menus
Will use the List class to store lines
Te xtMe nu
Lis t
EditApplication
Programming and Problem Solving With Java
28
A General List Class: Line Editor
Methods in EditApplication class
EditApplication(): Constructor, initializes menu
handleEvent(): Event dispatcher
goToLine(): Changes current line to user-specified line
number
insertLines(): Prompts user for a line number, then
prompts user for lines to insert after that. Stops when
user enters line with just a period.
deleteLine(): Prompts user for a line number, then
deletes that line
displayLines(): Display all lines
Programming and Problem Solving With Java
29
A General List Class: Line Editor
EditApplication constructor
// Constructor - set up menu for the editor
public EditApplication()
{
super("Edit Menu");
editBuffer = new List();
addSelection("Show all lines", 's', SHOW_COMMAND);
addSelection("Insert lines", 'i', INSERT_COMMAND);
addSelection("Delete a line", 'd', DELETE_COMMAND);
addSelection("Quit", 'q', TextMenu.QUIT);
}
EditApplication constants
static final int SHOW_COMMAND = 1;
static final int INSERT_COMMAND = 2;
static final int DELETE_COMMAND = 3;
EditApplication main()
public static void main(String[] args)
throws java.io.IOException
{
EditApplication editor = new EditApplication();
}
editor.run();
Programming and Problem Solving With Java
30
A General List Class: Line Editor
EditApplication handleEvent()
// Event dispatcher for the editor
public int handleEvent(int event)
throws java.io.IOException
{
switch (event)
{
case SHOW_COMMAND:
displayLines();
break;
case INSERT_COMMAND:
insertLines();
break;
case DELETE_COMMAND:
deleteLine();
break;
case TextMenu.QUIT:
if (Keyboard.readChar(
"Are you sure you want to quit? (y/n)", "yn") != 'y')
{
event = TextMenu.CANCEL_QUIT;
}
break;
}
return event;
}
Programming and Problem Solving With Java
31
A General List Class: Line Editor
EditApplication insertLines() steps
Ask the user where to begin inserting new lines.
Move to that line in the list.
Read a line from the user.
As long as the line isn't just a period, do the following
steps.
•Insert the line into the list.
•Move to the new line, so the next line will be inserted after it.
•Read the next line from the user.
Programming and Problem Solving With Java
32
A General List Class: Line Editor
EditApplication
insertLines()
// insertLines: Prompts user for a line number, then prompts
//
user for lines to insert after that line.
//
Stops when the user enters a line with just
//
a period on it.
void insertLines()
throws java.io.IOException
{
String line;
if (!editBuffer.empty())
{
goToLine(Keyboard.readInt("After which line: ", 1,
editBuffer.count()));
}
}
System.out.println(
"(Enter just a period to stop inserting lines)");
line = Keyboard.readString(": ");
while (!line.equals("."))
{
if (editBuffer.isDefined())
{
editBuffer.insert(line);
editBuffer.goNext();
}
else
{
editBuffer.insertFirst(line);
editBuffer.goFirst();
}
line = Keyboard.readString(": ");
}
Programming and Problem Solving With Java
33
A General List Class: Line Editor
EditApplication gotoLine()
// goToLine: Changes the current line to a specific line number
// Note: lineNum must be in the range 1 to number of lines
//
in buffer
void goToLine(int lineNum)
{
// Check precondition
Debug.assert(lineNum >= 1 && lineNum <= editBuffer.count(),
"EditApplication.goToLine(): Invalid line number");
}
editBuffer.goFirst();
for(int i = 1; i < lineNum; i++)
{
editBuffer.goNext();
}
Programming and Problem Solving With Java
34
A General List Class: Line Editor
EditApplication deleteLine() steps
Ask the user which line to delete
Move to that line
Delete that line
EditApplication deleteLine()
// deleteLine: Prompts user for a line number, then deletes
//
that line
void deleteLine()
throws java.io.IOException
{
if (editBuffer.empty())
{
System.out.println("No lines");
}
else
{
goToLine(Keyboard.readInt("Line to delete: ", 1,
editBuffer.count()));
editBuffer.remove();
}
}
Programming and Problem Solving With Java
35
A General List Class: Line Editor
EditApplication displayLines()
// displayLines: Display all lines in the buffer
void displayLines()
{
int lineNumber = 0;
}
for(editBuffer.goFirst();
editBuffer.isDefined();
editBuffer.goNext())
{
lineNumber++;
System.out.println(lineNumber + ": " + editBuffer.get());
}
Shows how to use for statement to traverse
elements of a list
Move to first line with goFirst()
Test whether past end of list with isDefined()
Move to next line with goNext()
Programming and Problem Solving With Java
36
A General List Class: Implementation
List is a container type
Holds elements of another type
Array is another container type
Common implementation of a container as a linked
type
Class for each node of the container
Class for the container itself
Used this implementation with CharList
CharListNode
CharList
Will store an Object value in each node
Programming and Problem Solving With Java
37
A General List Class: Implementation
ListNode class
class ListNode
{
// Constructor
ListNode(Object item, ListNode next)
{
setItem(item);
setNext(next);
}
// getItem: Returns the item value
public Object getItem() { return item; }
// getNext: Returns the next item
public ListNode getNext() { return next; }
// setItem: Sets the item to the given value
public void setItem(Object item)
{
this.item = item;
}
// setNext: Sets the next item to the given object
public void setNext(ListNode next)
{
this.next = next;
}
// Instance variables
Object item;
ListNode next;
Programming}and Problem Solving With Java
38
A General List Class: Implementation
List class structure
Reference to
first node
List
ListNode
1
ListNode
2
ListNode
3
ListNode
4
null
Reference to
last node
Reference to
current node
Number
of nodes
4
Instance variables
// Instance variables
int numNodes;
ListNode first,
last,
currentNode;
Programming and Problem Solving With Java
//
//
//
//
The number of nodes in the list
Reference to the first node
Reference to the last node
Reference to the current node
39
A General List Class: Implementation
List constructor
// Default constructor
public List()
{
first = null;
last = null;
currentNode = null;
numNodes = 0;
}
List insertFirst (similar to CharList)
// insertFirst: Inserts a new item at the beginning of the list.
public void insertFirst(Object item)
{
ListNode newNode = new ListNode(item, first);
}
numNodes++;
first = newNode;
if (last == null)
{
// Special case: An empty list.
// This new node is the last node in the list.
last = newNode;
}
Programming and Problem Solving With Java
40
A General List Class: Implementation
List insertLast (similar to CharList)
// insertLast: Inserts a new item at the end of the list
public void insertLast(Object item)
{
ListNode newNode = new ListNode(item, null);
}
numNodes++;
if (first == null)
{
// Special case: this node is the first node in
// the list.
first = newNode;
}
else
{
// General case: this is not the only node in the list.
// Make the last node point to this one and make
// this the new last node.
last.setNext(newNode);
}
last = newNode;
Programming and Problem Solving With Java
41
A General List Class: Implementation
List insert()
Puts new node after currentNode
Caller responsible for setting currentNode first
// insert: Inserts a new item after a node pointed to by
//
currentNode.
// Note: currentNode must be defined
public void insert(Object item)
{
Debug.assert(isDefined(),
"List.insert(): currentNode undefined");
ListNode newNode = new ListNode(item, currentNode.getNext());
}
numNodes++;
currentNode.setNext(newNode);
if (currentNode == last)
{
// Special case: this is the new last node.
last = newNode;
}
Programming and Problem Solving With Java
42
A General List Class: Implementation
List put()
// put: Changes the value of the currentNode node to item
// Note: currentNode must be defined
public void put(Object item)
{
Debug.assert(isDefined(),
"List.put(): currentNode undefined");
currentNode.setItem(item);
}
List get()
// get: Returns the value in the currentNode
// Note: currentNode must be defined
public Object get()
{
Debug.assert(isDefined(),
"List.get(): currentNode undefined");
return currentNode.getItem();
}
Programming and Problem Solving With Java
43
A General List Class: Implementation
List removeFirst()
Uses removeNode() helper method
// removeFirst: Remove the first element from the list and
//
return its value. If item is currentNode,
//
then sets currentNode to next node,
//
unless deleting the last node. In that case,
//
sets currentNode to previous node.
// Note: The list must not be empty
public Object removeFirst()
{
Debug.assert(!empty(),
"List.removeFirst(): List is empty");
}
Object returnValue = first.getItem();
removeNode(first, null);
return returnValue;
Programming and Problem Solving With Java
44
A General List Class: Implementation
List removeLast()
Uses removeNode() helper method
// removeLast: Remove the last element from the list
//
and return its value. If item is
//
currentNode, then sets currentNode
//
to next node, unless deleting the last
//
node. In that case, sets currentNode to
//
previous node.
// Note: The list must not be empty
public Object removeLast()
{
Debug.assert(!empty(),
"List.removeLast(): List is empty");
}
// Set last to node before last one
Object returnValue = last.getItem();
removeNode(last, findPreviousNode(last));
return returnValue;
Programming and Problem Solving With Java
45
A General List Class: Implementation
List remove()
// remove: Removes item referenced by currentNode, and
//
returns its value. Sets currentNode to next
//
node, unless deleting the last node. In that
//
case, sets currentNode to previous node.
// Note: currentNode must be defined
public Object remove()
{
Debug.assert(isDefined(),
"List.remove(): currentNode undefined");
Object returnValue = currentNode.getItem();
removeNode(currentNode,
findPreviousNode(currentNode));
return returnValue;
}
List append()
// append: Appends elements of the source list to this one
public void append(List source)
{
for (source.goFirst();
source.isDefined();
source.goNext())
{
insertLast(source.get());
}
}
Programming and Problem Solving With Java
46
A General List Class: Implementation
List find()
// find: If a particular value is in the list, sets
//
currentNode to that node and returns true.
//
Otherwise, leaves currentNode as it was and
//
returns false.
public boolean find(Object data)
{
ListNode node = first;
// Find node containing the data value
while (node != null && !(node.getItem().equals(data)))
{
node = node.getNext();
}
}
if (node == null)
{
return false;
}
currentNode = node;
return true;
Programming and Problem Solving With Java
47
A General List Class: Implementation
List goFirst()
// goFirst: Sets currentNode to beginning of list
public void goFirst()
{
currentNode = first;
}
List goList()
// goLast: Sets currentNode to end of list
public void goLast()
{
currentNode = last;
}
List goNext()
// goNext: Sets currentNode to next element in the list
// Note: currentNode must be defined
public void goNext()
{
Debug.assert(isDefined(),
"List.goNext(): currentNode undefined");
currentNode = currentNode.getNext();
}
Programming and Problem Solving With Java
48
A General List Class: Implementation
List goPrevious()
// goPrevious: Sets currentNode to previous element in
//
the list
// Note: currentNode must be defined
public void goPrevious()
{
Debug.assert(isDefined(),
"List.goPrevious(): currentNode undefined");
currentNode = findPreviousNode(currentNode);
}
Programming and Problem Solving With Java
49
A General List Class: Implementation
Removing a node
previousNode
node
1
2
Before
removing
3
4
null
4
null
4
previousNode
node
1
2
Link around
node
3
3
Programming and Problem Solving With Java
50
A General List Class: Implementation
List//removeNode()
removeNode: Removes the given node from the list, adjusts
//
first, last, and currentNode
//
if necessary. If node is currentNode,
//
then sets currentNode to next node,
//
unless deleting the last node. In that
//
case, sets currentNode to previous node.
void removeNode(ListNode node, ListNode previousNode)
{
if (node == first)
{
first = first.getNext();
}
else
{
previousNode.setNext(node.getNext());
}
if (last == node)
{
last = previousNode;
}
// Reset currentNode, if necessary
if (currentNode == node)
{
if (currentNode.next == null)
{
currentNode = previousNode;
}
else
{
currentNode = currentNode.getNext();
}
}
numNodes--;
Programming}and Problem Solving With Java
51
A General List Class: Implementation
List findPreviousNode()
Modified linear search
Must find the node before the one we want
// findPreviousNode: Returns the node before the given
//
node, or null if the node is the
//
first node in the list.
// Pre: node must be a valid node in the list
ListNode findPreviousNode(ListNode node)
{
ListNode previousNode;
if (node == first)
{
return null;
}
}
previousNode = first;
while (previousNode.getNext() != node)
{
previousNode = previousNode.getNext();
}
return previousNode;
Programming and Problem Solving With Java
52
Infinite Precision Arithmetic
Range of long may not be enough
 -9,223,372,036,854,775,808  9,223,372,036,854,775,807
Can make a type that holds any number of digits
// Sample use of the InfinitePrecision class.
import InfinitePrecision;
public class TestInfinitePrecision
{
public static void main(String[] args)
{
InfinitePrecision first = new InfinitePrecision(
"4958614030582059703402389481948372634758695783");
InfinitePrecision second = new InfinitePrecision(
"8089614672364869790583723648597007904201129034");
}
}
System.out.println("The sum of:
System.out.println("
and:
System.out.println("
is:
The sum of:
and:
is:
Programming and Problem Solving With Java
" + first);
" + second);
" + first.add(second));
4958614030582059703402389481948372634758695783
8089614672364869790583723648597007904201129034
13048228702946929493986113130545380538959824817
53
Infinite Precision Arithmetic
InfinitePrecision instance variable
// Instance variables
List digits = new List();
InfinitePrecision default constructor
Use this when we want to assign 0 to the number
// Default Constructor
// Note: An empty list is treated as zero
public InfinitePrecision()
{
}
Programming and Problem Solving With Java
54
Infinite Precision Arithmetic
InfinitePrecision constructor with long argument
// Constructor: Sets the number to that given in the
//
long integer
public InfinitePrecision(long number)
{
// Put digits in number from right to left
while (number != 0)
{
digits.insertFirst(new Integer((int) (number % 10)));
number = number / 10;
}
}
Trace on new InfnitePrecision(12345);
number
digits (list)
0
12345
[]
1
1234
[5]
2
123
[4, 5]
3
12
[3, 4, 5]
4
1
[2, 3, 4, 5]
5
0
[1, 2, 3, 4, 5]
step
Programming and Problem Solving With Java
55
Infinite Precision Arithmetic
InfinitePrecision constructor with string argument
// Constructor: Sets the number to that given in the string
// Note: The string should have only digits
public InfinitePrecision(String number)
{
int i = 0;
}
while (i < number.length())
{
Debug.assert(Character.isDigit(number.charAt(i)),
"InfinitePrecision(): invalid character in string");
digits.insertLast(
new Integer(Character.digit(number.charAt(i), 10)));
i++;
}
Trace on new InfnitePrecision(“12345”);
i
number
digits (list)
0
"12345"
[]
1
"12345"
[1]
2
"12345"
[1, 2]
3
"12345"
[1, 2, 3]
4
"12345"
[1, 2, 3, 4]
5
"12345"
[1, 2, 3, 4, 5]
Programming and Problem Solving With Java
56
Infinite Precision Arithmetic
Adding two infinite precision numbers
Use the manual technique from right to left
Carry
1
1
2
6
7
4
8
2
5
3
4
2
7
+
Programming and Problem Solving With Java
57
Infinite Precision Arithmetic
InfinitePrecision add() (part1)
// add: Returns sum of this value and the other
//
InfinitePrecision value
InfinitePrecision add(InfinitePrecision otherValue)
{
InfinitePrecision result = new InfinitePrecision();
int carry = 0;
digits.goLast();
otherValue.digits.goLast();
// Add digits from right to left
while (digits.isDefined()
&& otherValue.digits.isDefined())
{
result.digits.insertFirst(new Integer(
(((Integer) digits.get()).intValue()
+ ((Integer) otherValue.digits.get()).intValue()
+ carry) % 10));
carry = (((Integer) digits.get()).intValue()
+ ((Integer) otherValue.digits.get()).intValue()
+ carry) / 10;
}
digits.goPrevious();
otherValue.digits.goPrevious();
Programming and Problem Solving With Java
58
Infinite Precision Arithmetic
InfinitePrecision add() (part2)
// Append any remaining digits from this value to result's
// left
for (; digits.isDefined(); digits.goPrevious())
{
result.digits.insertFirst(new Integer(
(((Integer) digits.get()).intValue()
+ carry) % 10));
carry = (((Integer) digits.get()).intValue()
+ carry) / 10;
}
// Append any remaining digits from other value to result's
// left
for (; otherValue.digits.isDefined();
otherValue.digits.goPrevious())
{
result.digits.insertFirst(new Integer(
(((Integer) otherValue.digits.get()).intValue()
+ carry) % 10));
carry = (((Integer) otherValue.digits.get()).intValue()
+ carry) / 10;
}
if (carry != 0)
{
result.digits.insertFirst(new Integer(carry));
}
}
return result;
Programming and Problem Solving With Java
59
Infinite Precision Arithmetic
InfinitePrecision toString()
// toString: Returns a String version of the number
public String toString()
{
String result = "";
if (digits.empty())
{
return "0";
}
else
{
}
}
for (digits.goFirst();
digits.isDefined();
digits.goNext())
{
result = result + digits.get();
}
return result;
Programming and Problem Solving With Java
60
Making List work with Primitives
Can store objects in a List directly
List myList = new List();
myList.insertFirst(“a string”);
Must wrap primitives
myList.insertFirst(new Integer(1234));
myList.insertLast(new Double(6.39));
Can overload List methods so they work with
primitives
// insertFirst: Inserts a new int at the beginning of the
//
list (Overloaded version for int)
public void insertFirst(int item)
{
insertFirst(new Integer(item));
}
Now can store integers directly
myList.insertFirst(1234);
Should also overload for other primitives (long, float, ...)
Programming and Problem Solving With Java
61
Making List work with Primitives
Must cast values from a list, and unwrap primitives
String aString = (String) myList.get();
int anInt = ((Integer) myList.get()).intValue();
Unfortunately, can’t override get() to return int
Overriding works only when parameters differ
To retrieve primitives from List easily
Write getInt() for retrieving integers, getDouble() for
doubles, etc.
// getInt: Returns the int value in the currentNode
//
(Overloaded version for int)
// Note: currentNode must be defined
public int getInt()
{
return ((Integer) get()).intValue();
}
This is why Keyboard class has readInt(), readString(), ...
Use of getInt() is more readable than get()
int anInt = myList.getInt();
Programming and Problem Solving With Java
62
Sorting a List
Two ways to sort a list
Keep it sorted all the time
Users can’t put elements where they want
Sort only when needed
More flesxible
Users can put elements anywhere - can sort later if ncessary
Problem
List stores Object values
Objects have no order -- how to sort them??
Specific objects (dates, strings, ...) do have an order,
though
Can’t put sort() in List class
Programming and Problem Solving With Java
63
Sorting a List: Comparators
Can make a subclass of List that allows sorting
Put responsibility for sorting in separate class
Write a Comparator class
Comparator: object that compares two other objects
Tells which object is less
Comparator compares Object values
Comparator is an abstract class
Why? Can’t compare Object values
Use as a template for subclasses of Comparator
Programming and Problem Solving With Java
64
Sorting a List: Comparators
Comparator class
public abstract class Comparator
{
// compareTo: returns negative number if a < b
//
0 if a == b
//
positive number if a > b
abstract public int compareTo(Object a, Object b);
}
Subclass of Comparator for comparing strings
public class StringComparator extends Comparator
{
// compareTo: returns negative number if a < b
//
0 if a == b
//
positive number if a > b
public int compareTo(Object a, Object b)
{
return ((String) a).compareTo((String) b);
}
}
Programming and Problem Solving With Java
65
Sorting a List: Comparators
Subclass of Comparator for comparing integers
public class IntegerComparator extends Comparator
{
// compareTo: returns negative number if a < b
//
0 if a == b
//
positive number if a > b
public int compareTo(Object a, Object b)
{
int inta = ((Integer) a).intValue();
int intb = ((Integer) b).intValue();
}
}
if (inta < intb)
{
return -1;
}
if (inta > intb)
{
return 1;
}
return 0;
Programming and Problem Solving With Java
66
Sorting a List: SortableList
Skeleton for SortableList class
import List;
import Comparator;
public class SortableList extends List
{
// Constructor
public SortableList(Comparator comparator)
{
this.comparator = comparator;
}
//
//
//
//
}
--------------------------------------------------------------Sort method can go here. It should use comparator.compareTo()
to compare elements of the list.
---------------------------------------------------------------
// Instance variables
Comparator comparator;
Inherits all the methods of List: insert(), remove(), ...
Can use any sorting algorithm in SortableList
Programming and Problem Solving With Java
67
Sorting a List: Quick Sort
Quick sort
Very fast and efficient
On average, the fastest known sorting algorithm
Can be very slow occasionally
Works well with lists (and arrays)
Programming and Problem Solving With Java
68
Quick Sort
Step 1: Choose a
pivot element
{4, 2, 6, 1, 3, 7, 5}
Pivot
4
How quick sort works
 Choose pivot
 Make list of elements
less than pivot
 Make list of elements
greater than pivot
 Sort both lists
(using quick sort)
 Combine the sorted
lists
Step 2: Make a list
of elements less
than the pivot
[4, 2, 6, 1, 3, 7, 5]
Less
than
pivot
[2, 3, 1]
Step 3: Make a list
of elements more
than the pivot
Pivot
4
[4, 2, 6, 1, 3, 7, 5]
Less
than
pivot
[2, 3, 1]
4
[6, 7, 5]
Step 4: Sort sublists
and append
Less
than
pivot
[1, 2, 3]
Programming and Problem Solving With Java
Greater
than
pivot
Pivot
Greater
than
pivot
Pivot
4
[1, 2, 3, 4, 5, 6, 7]
[5, 6, 7]
69
Quick Sort
Choice of pivot is critical in quick sort
Ideally, the pivot should be the middle value of the list
If list is already sorted, choosing first element gives very
slow sort (why?)
Common pivot selection technique for array
Choose middle value of:
array[0]
array[array.length-1]
array[array.length / 2]
Even better: choose random element as the pivot
Can’t get middle element from list (efficiently)
Ideas for choosing a
pivot value for a list??
Programming and Problem Solving With Java
70
SortableList quickSort()
// quickSort: Sorts the list
public void quickSort()
{
SortableList lessList = new SortableList(comparator);
SortableList greaterList = new SortableList(comparator);
Object pivot, element;
goFirst();
if (!isEmpty())
{
pivot = removeFirst();
while (!isEmpty())
{
element = removeFirst();
if (comparator.compareTo(element, pivot) < 0)
{
lessList.insertFirst(element);
}
else
{
greaterList.insertFirst(element);
}
}
lessList.quickSort();
greaterList.quickSort();
}
}
// Append lists to get result
append(lessList);
insertLast(pivot);
append(greaterList);
Programming and Problem Solving With Java
71
SortableList quickSort()
Demonstration of SortableList
// Demonstrates the use of the SortableList class,
// which contains a quick sort algorithm.
import SortableList;
import StringComparator;
public class TestSortableList
{
public static void main(String[] args)
{
SortableList myList = new SortableList(new StringComparator());
myList.insertFirst("banana");
myList.insertFirst("orange");
myList.insertFirst("apple");
myList.insertFirst("grape");
myList.insertFirst("pear");
myList.insertFirst("strawberry");
myList.insertFirst("cherry");
}
}
System.out.println("Before sort: " + myList);
myList.quickSort();
System.out.println("After sort: " + myList);
Before sort: [cherry strawberry pear grape apple orange banana ]
After sort: [apple banana cherry grape orange pear strawberry ]
Programming and Problem Solving With Java
72
SortableList quickSort()
Another Demonstration of SortableList
// Demonstrates the use of the SortableList class,
// which contains a quick sort algorithm.
import SortableList;
import IntegerComparator;
public class TestSortableList2
{
public static void main(String[] args)
{
SortableList myList = new SortableList(new IntegerComparator());
myList.insertFirst(3);
myList.insertFirst(8);
myList.insertFirst(2);
myList.insertFirst(1);
myList.insertFirst(4);
myList.insertFirst(7);
myList.insertFirst(5);
}
}
// Note use of special insertFirst()
// made especially for int type
// (Otherwise, would need to use
// new Integer(3), for example,
// instead of 3)
System.out.println("Before sort: " + myList);
myList.quickSort();
System.out.println("After sort: " + myList);
Before sort: [5 7 4 1 2 8 3 ]
After sort: [1 2 3 4 5 7 8 ]
Programming and Problem Solving With Java
73
A Set Type
Set: heterogeneous, unordered collection of
elements without duplicate values
Common set operations
Operation
Symbol
Description
Example
Union

The union of two sets is
everything that is in
either set.
{1,2} {2 ,3}  {1,2 ,3}
Intersection

{1,2} {2,3}  {2}
Difference

The intersection of two
sets is everything that is
in both sets.
Programming and Problem Solving With Java
The difference of two
sets is everything that is
the first set but not in the
second.
{1,2}  {2,3}  {1}
74
A Set Type
Set operations
Union
A
Intersection
A
B
Difference
B
Programming and Problem Solving With Java
A
B
75
A Set Type
Demonstration of how to use the Set class
// Demonstrates use of the Set class
import Set;
public class TestSet
{
public static void main(String[] args)
{
// Make two sets
Set a = new Set();
Set b = new Set();
Set a is
Set b is
a union b is
a intersect b is
a difference b is
// Put 1 and 2 in set a
a.add("1");
a.add("2");
// Put 2 and 3 in set b
b.add("2");
b.add("3");
}
}
// Display results
System.out.println("Set a is
System.out.println("Set b is
System.out.println("a union b is
System.out.println("a intersect b is
System.out.println("a difference b is
Programming and Problem Solving With Java
"
"
"
"
"
+
+
+
+
+
{2 1}
{3 2}
{1 3 2}
{2}
{1}
a);
b);
a.union(b));
a.intersect(b));
a.difference(b));
76
A Set Type: Implementation
Store set elements in a list
// Instance variables
List data = new List();
Constructor for Set
// Default constructor
public Set()
{
}
add() method must not insert duplicate values
// add: Adds an element to a set if not already in the set.
//
If the element is already in the set, it is not
//
added again.
public void add(Object item)
{
if (!isMember(item))
{
data.insertFirst(item);
}
}
Programming and Problem Solving With Java
77
A Set Type: Implementation
Set remove() method
// remove: Removes the given item from the set. Does nothing
//
if the element is not in the set.
public void remove(Object item)
{
if (data.find(item))
{
data.remove();
}
}
Easy to write
List class methods do all the work
Programming and Problem Solving With Java
78
A Set Type: Implementation
Set union() method
// union: Returns the union of this set and otherSet, that
//
is, all items in either set.
public Set union(Set otherSet)
{
Set result = new Set();
// Copy everything from otherSet to result
result.data.append(otherSet.data);
// Add items from this set to the result (The add() member
// method will make sure that no element is added twice.)
for (data.goFirst();
data.isDefined();
data.goNext())
{
result.add(data.get());
}
}
return result;
Another approach: use add() for both sets
Not as efficient - don’t need to check for duplicates until
second set added
Programming and Problem Solving With Java
79
A Set Type: Implementation
Set intersect() method
// intersect: Returns the intersection of this set and
//
otherSet, that is, all items in both sets.
public Set intersect(Set otherSet)
{
Set result = new Set();
}
// Copy items from this set that are also in otherSet to
// result
for (data.goFirst();
data.isDefined();
data.goNext())
{
if (otherSet.isMember(data.get()))
{
result.add(data.get());
}
}
return result;
Programming and Problem Solving With Java
80
A Set Type: Implementation
Set difference() method
// difference: Returns the difference of this set and
//
otherSet, that is, all items in this set but
//
not in otherSet.
public Set difference(Set otherSet)
{
Set result = new Set();
// Copy those items from this set that are not in otherSet
// to result
for (data.goFirst();
data.isDefined();
data.goNext())
{
if (!otherSet.isMember(data.get()))
{
result.add(data.get());
}
}
}
return result;
Programming and Problem Solving With Java
81
A Set Type: Implementation
Set toString() method
// toString: Returns the set's contents as a string in
//
standard displayable format: {1, 3, 2}
public String toString()
{
String listStr = data.toString();
}
return "{"
+ listStr.substring(1, listStr.length() - 2)
+ "}";
Programming and Problem Solving With Java
82
A Set Type: Implementation
Set count(), empty(), isFull(), isMember() methods
// count: Returns the number of items in the set
public int count()
{
return data.count();
}
// empty: Returns true if the set is empty, false
//
otherwise
public boolean empty()
{
return data.empty();
}
// isFull: Returns true if the set is not empty, false
//
otherwise (always return false for list
//
implemention)
public boolean isFull()
{
return false;
}
// isMember: Returns true if item is in the set, false
//
otherwise
boolean isMember(Object item)
{
return data.find(item);
}
Programming and Problem Solving With Java
83
Doubly Linked Lists
Singly linked list
Each node references its successor
Can only move from node to next node
Doubly linked list
Each node references successor and predecessor
Advantage: Can delete node without searching for
successor and predecessor
Advantage: Can go through list backward
Reference to
first node
DList
DListNode
null
1
DListNode
DListNode
2
3
null
Reference to
last node
Reference to
current node
Number
of nodes
3
Programming and Problem Solving With Java
84
Doubly Linked Lists
Problems with doubly linked lists
Takes more memory than singly linked
Lots of special cases in implementation
Can remove many special cases with
Dummy header: unused node
Circular references
Reference
to header
node
Reference
to current
node
DList
Header
1
2
2
Number of
nodes
Programming and Problem Solving With Java
85
Doubly Linked Lists
Empty doubly linked list
Reference
to header
node
DList
Reference
to current
node
NULL
Header
0
Number of
nodes
Note: reference to end of list not necessary
Programming and Problem Solving With Java
86
Doubly Linked List: Implementation
DoubleListNode class
class DoubleListNode
{
// Default Constructor
public DoubleListNode()
{
this(null, null, null); // (This is the default action, but it
// doesn't hurt to be explicit)
}
// Constructor
public DoubleListNode(Object item,
DoubleListNode previous,
DoubleListNode next)
{
this.item = item;
this.previous = previous;
this.next = next;
}
// getItem: Returns the item value
public Object getItem() { return item; }
// getNext: Returns the next item
public DoubleListNode getNext() { return next; }
Programming and Problem Solving With Java
87
Doubly Linked List: Implementation
DoubleListNode class (continued)
// getPrevious: Returns the previous item
public DoubleListNode getPrevious() { return previous; }
// setItem: Sets the item to the given value
public void setItem(Object item)
{
this.item = item;
}
// setNext: Sets the next item to the given object
public void setNext(DoubleListNode next)
{
this.next = next;
}
// setPrevious: Sets the previous item to the given object
public void setPrevious(DoubleListNode previous)
{
this.previous = previous;
}
}
// Instance variables
DoubleListNode next, previous;
Object item;
Programming and Problem Solving With Java
88
Doubly Linked List: Implementation
DoubleList instance variables
// Instance variables
DoubleListNode header;
DoubleListNode currentNode;
int numNodes;
DoubleList constructor
// Reference to dummy header
// Reference to current node
// Number of nodes in list
// Default constructor
public DoubleList()
{
numNodes = 0;
}
// Allocate dummy header node
header = new DoubleListNode();
header.setPrevious(header);
header.setNext(header);
Programming and Problem Solving With Java
Reference
to header
node
DList
Reference
to current
node
NULL
Header
0
Number of
nodes
89
Doubly Linked List: Implementation
Inserting a
node at
the
beginning
of a list
After creating
the new node
temp
3
Reference
to header
node
Reference
to current
node
DList
Header
1
2
2
Number of
nodes
After inserting
the new node
temp
3
Reference
to header
node
Reference
to current
node
Number of
nodes
Programming and Problem Solving With Java
DList
Header
1
2
3
90
Doubly Linked List: Implementation
DoubleList insert() method
// insertFirst: Inserts a new item at the beginning of the
//
list
public void insertFirst(Object item)
{
DoubleListNode oldFirstNode = header.getNext();
DoubleListNode newNode
= new DoubleListNode(item, header, oldFirstNode);
}
numNodes++;
oldFirstNode.setPrevious(newNode);
header.setNext(newNode);
Programming and Problem Solving With Java
91
Doubly Linked List: Implementation
Removing
a value
from a
list
Before
removing
Ref erence
to header
node
Ref erence
to current
node
DList
Header
1
2
1
2
2
Number of
nodes
Link around
node
Ref erence
to header
node
Ref erence
to current
node
DList
Header
2
Number of
nodes
Adjust current
node
Ref erence
to header
node
Ref erence
to current
node
Number of
nodes
Programming and Problem Solving With Java
DList
Header
2
1
92
Doubly Linked List: Implementation
DoubleList remove()
// remove: Removes item referenced by currentNode, and
//
returns its value. Sets currentNode to next
//
node, unless deleting the last node. In that
//
case, sets currentNode to previous node.
// Note: currentNode must be defined
public Object remove()
{
Debug.assert(isDefined(),
"DoubleList.remove(): currentNode undefined");
Object returnValue = currentNode.getItem();
removeNode(currentNode);
return returnValue;
}
Programming and Problem Solving With Java
93
Doubly Linked List: Implementation
DoubleList removeNode()
// removeNode: Removes the given node from the list, adjusts
//
first, last, and currentNode
//
if necessary. If node is currentNode,
//
then sets currentNode to next node,
//
unless deleting the last node. In that
//
case, sets currentNode to previous node.
void removeNode(DoubleListNode node)
{
DoubleListNode nextNode = node.getNext(),
previousNode = node.getPrevious();
previousNode.setNext(nextNode);
nextNode.setPrevious(previousNode);
numNodes--;
}
// Reset currentNode, if necessary
if (currentNode == node)
{
if (currentNode.next == header)
{
currentNode = previousNode;
}
else
{
currentNode = nextNode;
}
}
Programming and Problem Solving With Java
94
Doubly Linked List: Implementation
DoubleList find()
// find: If a particular value is in the list, sets
//
currentNode to that node and returns true.
//
Otherwise, leaves currentNode as it was and
//
returns false.
public boolean find(Object data)
{
DoubleListNode node = header.getNext();
// Find node containing the data value
while (node != header && !(node.getItem().equals(data)))
{
node = node.getNext();
}
}
if (node == header)
{
return false;
}
currentNode = node;
return true;
Programming and Problem Solving With Java
95
Computer Security: Layers
Layers of security
Protected Information
Encryption
Inference and access controls
Database authentication
Operating system authentication
Intrusion detection
Intrusion prevention
Programming and Problem Solving With Java
ATTACK
Personnel screening
96
Computer Security: Layers
Physical security: intrusion prevention and detection
Fences
Lack of windows
Walls that extend to the roof
Mechanical and electronic locks
Guards
Adequate lighting
Automated entry booths
Uninterruptible power supplies
Power filters and surge suppressors
Smoke and fire detection
Automatic fire extinguishers
Programming and Problem Solving With Java
97
Computer Security: Layers
Operating system
Identification: unique name for each user
Authentication: confirmation of user by computer and
vice versa
Authentication techniques
Check what user knows (password, ...)
Check what user carries (smartcard, ...)
Check who user is (retina scan, voice print, ...)
Password recommendations (US DoD)
Users should be able to change
Should be machine generated
System should display last login time
Programming and Problem Solving With Java
98
Computer Security: Disclosure
Disclosure of information can be harmful
Military and government disclosure: national security
Commercial disclosure: trade secrets, customer lists, ...
US Laws forbidding disclosure of personal
information
Right to Financial Privacy (1978)
Privacy Act (1974)
(Other countries have similar laws)
Programming and Problem Solving With Java
99
Computer Security: Disclosure
Covert channel
 Unconventional method of
information transfer
Types of covert channels
 Storage
 Timing
Very difficult to identify
covert channels
Programming and Problem Solving With Java
Message not allowed
User A
User B
Message
Move
disk
head
Detect
head
movement
Disk Drive
100
Computer Security: Disclosure
Indirect disclosure: inference or aggregation
Inference
Can guess value by adding outside information
Example: Anderson is only female manager
Can guess Anderson’s salary from FSalary - TSalary
•FSalary, total salary of all females
•TSalary, total salary of all non-manager females
Aggregation
Can guess value by combining nonsensitive values
Example: knowing 1 CIA phone number is Ok
Knowing ALL CIA phone numbers is NOT Ok
Programming and Problem Solving With Java
101
Computer Security: Modification
Data modification or destruction more serious to
commercial computers
Usually caused by disgruntled employees
Trapdoor: turns off normal security checking
Example: no password for some accounts
Trojan horse: malicious program hidden in another
Virus: self-perpetuating Trojan horse, attaches to
other programs
Worm: self-perpetuating program takes over idle
machines in a network
Time bombs and logic bombs
Programming and Problem Solving With Java
102
Computer Security: Military
Focus: control of disclosure
Sensitivity levels
Unclassified
Confidential
Secret
Top secret
Compartments: topic areas
Nuclear
Spy
...
NUC
SPY
Top Secret
Secret
Confidential
o3
o1
o2
Unclassified
Each object has security level
Each user has clearance
Programming and Problem Solving With Java
103
Computer Security: Military
Mandatory access control (MAC)
Enforcement of military security
Unauthorized disclosure is illegal
Discretionary access control (DAC)
Owner of data decides who can access it
Most common commercial security technique
Used in many operating systems (NT, Unix, VAX VMS)
MAC and DAC combined = military security
Programming and Problem Solving With Java
104
Computer Security: Military
Modes of operation for military computers
Dedicated: users cleared for all data, can access all data
System-high: users cleared for all data, can access some
data
Compartmented: users cleared for most restricted data,
can access some data
Multilevel: users not cleared for all data, can access
some data
Most military computers run in system-high mode
Military would like to move to multilevel
Cheaper
Easier to keep data consistent
Programming and Problem Solving With Java
105
Computer Security: Military
DoD security classifications
Level D
No security
Level C (C1, C2)
Discretionary access control
NT, VAX VMS, some variants of Unix are C2
C2 is minimum for commercial security
Level B (B1, B2, B3)
Level C features
Plus mandatory access control
Level A
Level B features
Plus formal proof of correctness
Programming and Problem Solving With Java
106
Computer Security: Access Control
Discretionary access control (DAC)
Allows data owner to choose who else can access
Little protection against Trojan horse attacks
Implementation of DAC
Capabilities
Access control lists
Protection bits
Capabilities
Files
FILE1
FILE2
User A
Files
FILE1
FILE2
FILE3
User B
System associates access rights
with each user
User C
Advantage: more protection
against Trojan horse attacks
Disadvantage: revoking rights
is difficult
Programming and Problem Solving With Java
Rights
R, W
R
Files
FILE2
FILE3
Rights
R
R, W
R, W
Rights
R
R, W
107
Computer Security: Access Control
Access control lists
Another way to implement DAC
Stores list of authorized users
with each resource
US National Computer
Center recommends this
approach
Users Rights
User A R, W
User B R
FILE1
FILE2
Users
User A
User B
User C
Rights
R
R, W
R
FILE3
Users Rights
User B R, W
User C R, W
Programming and Problem Solving With Java
108
Computer Security: Access Control
Protection bits
Another way to implement DAC
9 bits (Boolean values) per object
Owner read
Owner write
Owner execute
Group read
Group write
Group execute
Others read
Others write
Others execute
Used with many Unix variants
% ls -l newmodel.txt
-rw-rw---- 1 slack
219 Jan
6 14:07 newmodel.txt
% chmod u-w newmodel.txt
-r--rw---- 1 slack
219 Jan
6 14:07 newmodel.txt
Change projection with chmod
Simplest approach to implement DAC
But weak protection -- doesn’t qualify for level C security
Programming and Problem Solving With Java
109
Computer Security: Commercial
Commercial security emphasizes prevention of
unauthorized modification
Most common unauthorized modification
Programming and Problem Solving With Java
110
Computer Security: Commercial
Major types of undesirable changes
Unauthorized user inserts false information deliberately
Authorized user inserts false information accidentally
Prevent unauthorized changes with security
techniques
MAC
DAC
How to prevent accidental changes?
Programming and Problem Solving With Java
111
Computer Security: Commercial
Can’t prevent all accidental changes
Prevent most of them with integrity constraints
(business rules)
Age of employees must be between 18 and 80
No employee can earn more than his or her manager
Integrity
Validity (no false information)
Completeness (all true information included)
Integrity usually enforced at database level
Correct state: when data satisfies all Integrity constraints
Database system tries to keep data in correct state
Programming and Problem Solving With Java
112
Computer Security: Commercial
Transaction: group of changes to data
Must take database from one correct state to another
correct state
Transaction example
Integrity constraint: Sales + value of inventory is constant
Customer buys shoes: steps in database
1. Subtract value of shoes from inventory
2. Add amount of sale to sum of today’s sales
Incorrect state between steps
Correct state only after both steps completed
Programming and Problem Solving With Java
113
Computer Security: Commercial
Types of database integrity constraints
Structure-based: part of the database structure
Value-based: based on values in the database
Structure-based example
Can only store an integer in an Age field (defined as
Integer)
Value-based example
No employee can earn more than his or her manager
Programming and Problem Solving With Java
114
Computer Security: Commercial
Clark-Wilson model of integrity
Looks
like
objectoriented!!
Only transaction procedures can change data
Users can only use transaction
procedures -- can’t access data directly
Task: several transactions
Separation of duties: make sure a different person
handles each transaction in a task
Example: Paying a supplier
Receive new inventory
Approve supplier’s invoice
Request payment to supplier
Print check
Programming and Problem Solving With Java
115
Computer Security: Individual
Choose a good password
Shouldn’t be easy to guess
Don’t use name of friend, pet, hometown, ...
Don’t use a word in English
Should be easy to remember, but nonsensical to others
How to choose a password
Use a mnemonic (“The frog jumped up and kicked the
horse.”  Tfjuakth)
Concatenate two unrelated words (“cube” + “branch” 
cubebranch)
Keep your password safe
Don’t write it down anywhere
Don’t let others user your account
Programming and Problem Solving With Java
116
Computer Security: Individual
Encryption
Scrambles data according to an encryption key
Makes data useless to others
Must use decryption key to get original data back
Encryption by rotation
A B C D E F G H I
J K L ...
Plaintext: “This is a test.”
Encrypted text (key of 3): “Wklv%lv%whvw1”
Common encryption techniques
DES
Blowfish
PGP
Programming and Problem Solving With Java
117
Computer Security: Individual
Protect against viruses
Use virus protection programs
Keep their virus lists current
Protect against fire, flood, theft
Insurance
Backup
Back up your data
Copy to diskette, Zip disk, tape
Full backup: all the data on the computer
Incremental backup: changes since last full backup
Programming and Problem Solving With Java
118
Computer Security: Individual
Backup procedure
Have at least two backups -- one offsite
Newest full
backup
on tape
Previous
full backup
on tape
Newest
incremental
backup
on floppies
Previous
incremental
backup
on floppies
Programming and Problem Solving With Java
Ready for
reuse
Ready for
reuse
119