wanted a data structure assignment
Ashmeet
SourceCode.zipChap12/ArrayStack/jsjf/ArrayStack.java
Chap12/ArrayStack/jsjf/ArrayStack.java
package
jsjf
;
import
jsjf
.
exceptions
.
*
;
import
java
.
util
.
Arrays
;
/**
* An array implementation of a stack in which the bottom of the
* stack is fixed at index 0.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
ArrayStack
<
T
>
implements
StackADT
<
T
>
{
private
final
static
int
DEFAULT_CAPACITY
=
100
;
private
int
top
;
private
T
[]
stack
;
/**
* Creates an empty stack using the default capacity.
*/
public
ArrayStack
()
{
this
(
DEFAULT_CAPACITY
);
}
/**
* Creates an empty stack using the specified capacity.
*
@param
initialCapacity the initial size of the array
*/
public
ArrayStack
(
int
initialCapacity
)
{
top
=
0
;
stack
=
(
T
[])(
new
Object
[
initialCapacity
]);
}
/**
* Adds the specified element to the top of this stack, expanding
* the capacity of the array if necessary.
*
@param
element generic element to be pushed onto stack
*/
public
void
push
(
T element
)
{
if
(
size
()
==
stack
.
length
)
expandCapacity
();
stack
[
top
]
=
element
;
top
++
;
}
/**
* Creates a new array to store the contents of this stack with
* twice the capacity of the old one.
*/
private
void
expandCapacity
()
{
stack
=
Arrays
.
copyOf
(
stack
,
stack
.
length
*
2
);
}
/**
* Removes the element at the top of this stack and returns a
* reference to it.
*
@return
element removed from top of stack
*
@throws
EmptyCollectionException if stack is empty
*/
public
T pop
()
throws
EmptyCollectionException
{
if
(
isEmpty
())
throw
new
EmptyCollectionException
(
"stack"
);
top
--
;
T result
=
stack
[
top
];
stack
[
top
]
=
null
;
return
result
;
}
/**
* Returns a reference to the element at the top of this stack.
* The element is not removed from the stack.
*
@return
element on top of stack
*
@throws
EmptyCollectionException if stack is empty
*/
public
T peek
()
throws
EmptyCollectionException
{
if
(
isEmpty
())
throw
new
EmptyCollectionException
(
"stack"
);
return
stack
[
top
-
1
];
}
/**
* Returns true if this stack is empty and false otherwise.
*
@return
true if this stack is empty
*/
public
boolean
isEmpty
()
{
// To be completed as a Programming Project
return
true
;
// temp
}
/**
* Returns the number of elements in this stack.
*
@return
the number of elements in the stack
*/
public
int
size
()
{
// To be completed as a Programming Project
return
0
;
// temp
}
/**
* Returns a string representation of this stack.
*
@return
a string representation of the stack
*/
public
String
toString
()
{
// To be completed as a Programming Project
return
""
;
// temp
}
}
Chap12/ArrayStack/jsjf/exceptions/EmptyCollectionException.java
Chap12/ArrayStack/jsjf/exceptions/EmptyCollectionException.java
package
jsjf
.
exceptions
;
/**
* Represents the situation in which a collection is empty.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
EmptyCollectionException
extends
RuntimeException
{
/**
* Sets up this exception with an appropriate message.
*
@param
collection the name of the collection
*/
public
EmptyCollectionException
(
String
collection
)
{
super
(
"The "
+
collection
+
" is empty."
);
}
}
Chap12/ArrayStack/jsjf/StackADT.java
Chap12/ArrayStack/jsjf/StackADT.java
package
jsjf
;
/**
* Defines the interface to a stack collection.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
interface
StackADT
<
T
>
{
/**
* Adds the specified element to the top of this stack.
*
@param
element element to be pushed onto the stack
*/
public
void
push
(
T element
);
/**
* Removes and returns the top element from this stack.
*
@return
the element removed from the stack
*/
public
T pop
();
/**
* Returns without removing the top element of this stack.
*
@return
the element on top of the stack
*/
public
T peek
();
/**
* Returns true if this stack contains no elements.
*
@return
true if the stack is empty
*/
public
boolean
isEmpty
();
/**
* Returns the number of elements in this stack.
*
@return
the number of elements in the stack
*/
public
int
size
();
/**
* Returns a string representation of this stack.
*
@return
a string representation of the stack
*/
public
String
toString
();
}
Chap12/PostfixTester/PostfixEvaluator.java
Chap12/PostfixTester/PostfixEvaluator.java
import
java
.
util
.
Stack
;
import
java
.
util
.
Scanner
;
/**
* Represents an integer evaluator of postfix expressions. Assumes
* the operands are constants.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
PostfixEvaluator
{
private
final
static
char
ADD
=
'+'
;
private
final
static
char
SUBTRACT
=
'-'
;
private
final
static
char
MULTIPLY
=
'*'
;
private
final
static
char
DIVIDE
=
'/'
;
private
Stack
<
Integer
>
stack
;
/**
* Sets up this evaluator by creating a new stack.
*/
public
PostfixEvaluator
()
{
stack
=
new
Stack
<
Integer
>
();
}
/**
* Evaluates the specified postfix expression. If an operand is
* encountered, it is pushed onto the stack. If an operator is
* encountered, two operands are popped, the operation is
* evaluated, and the result is pushed onto the stack.
*
@param
expr string representation of a postfix expression
*
@return
value of the given expression
*/
public
int
evaluate
(
String
expr
)
{
int
op1
,
op2
,
result
=
0
;
String
token
;
Scanner
parser
=
new
Scanner
(
expr
);
while
(
parser
.
hasNext
())
{
token
=
parser
.
next
();
if
(
isOperator
(
token
))
{
op2
=
(
stack
.
pop
()).
intValue
();
op1
=
(
stack
.
pop
()).
intValue
();
result
=
evaluateSingleOperator
(
token
.
charAt
(
0
),
op1
,
op2
);
stack
.
push
(
new
Integer
(
result
));
}
else
stack
.
push
(
new
Integer
(
Integer
.
parseInt
(
token
)));
}
return
result
;
}
/**
* Determines if the specified token is an operator.
*
@param
token the token to be evaluated
*
@return
true if token is operator
*/
private
boolean
isOperator
(
String
token
)
{
return
(
token
.
equals
(
"+"
)
||
token
.
equals
(
"-"
)
||
token
.
equals
(
"*"
)
||
token
.
equals
(
"/"
)
);
}
/**
* Performs integer evaluation on a single expression consisting of
* the specified operator and operands.
*
@param
operation operation to be performed
*
@param
op1 the first operand
*
@param
op2 the second operand
*
@return
value of the expression
*/
private
int
evaluateSingleOperator
(
char
operation
,
int
op1
,
int
op2
)
{
int
result
=
0
;
switch
(
operation
)
{
case
ADD
:
result
=
op1
+
op2
;
break
;
case
SUBTRACT
:
result
=
op1
-
op2
;
break
;
case
MULTIPLY
:
result
=
op1
*
op2
;
break
;
case
DIVIDE
:
result
=
op1
/
op2
;
}
return
result
;
}
}
Chap12/PostfixTester/PostfixTester.java
Chap12/PostfixTester/PostfixTester.java
import
java
.
util
.
Scanner
;
/**
* Demonstrates the use of a stack to evaluate postfix expressions.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
PostfixTester
{
/**
* Reads and evaluates multiple postfix expressions.
*/
public
static
void
main
(
String
[]
args
)
{
String
expression
,
again
;
int
result
;
Scanner
in
=
new
Scanner
(
System
.
in
);
do
{
PostfixEvaluator
evaluator
=
new
PostfixEvaluator
();
System
.
out
.
println
(
"Enter a valid post-fix expression one token "
+
"at a time with a space between each token (e.g. 5 4 + 3 2 1 - + *)"
);
System
.
out
.
println
(
"Each token must be an integer or an operator (+,-,*,/)"
);
expression
=
in
.
nextLine
();
result
=
evaluator
.
evaluate
(
expression
);
System
.
out
.
println
();
System
.
out
.
println
(
"That expression equals "
+
result
);
System
.
out
.
print
(
"Evaluate another expression [Y/N]? "
);
again
=
in
.
nextLine
();
System
.
out
.
println
();
}
while
(
again
.
equalsIgnoreCase
(
"y"
));
}
}
Chap13/LinkedStack/jsjf/exceptions/EmptyCollectionException.java
Chap13/LinkedStack/jsjf/exceptions/EmptyCollectionException.java
package
jsjf
.
exceptions
;
/**
* Represents the situation in which a collection is empty.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
EmptyCollectionException
extends
RuntimeException
{
/**
* Sets up this exception with an appropriate message.
*
@param
collection the name of the collection
*/
public
EmptyCollectionException
(
String
collection
)
{
super
(
"The "
+
collection
+
" is empty."
);
}
}
Chap13/LinkedStack/jsjf/LinearNode.java
Chap13/LinkedStack/jsjf/LinearNode.java
package
jsjf
;
/**
* Represents a node in a linked list.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
LinearNode
<
T
>
{
private
LinearNode
<
T
>
next
;
private
T element
;
/**
* Creates an empty node.
*/
public
LinearNode
()
{
next
=
null
;
element
=
null
;
}
/**
* Creates a node storing the specified element.
*
@param
elem element to be stored
*/
public
LinearNode
(
T elem
)
{
next
=
null
;
element
=
elem
;
}
/**
* Returns the node that follows this one.
*
@return
reference to next node
*/
public
LinearNode
<
T
>
getNext
()
{
return
next
;
}
/**
* Sets the node that follows this one.
*
@param
node node to follow this one
*/
public
void
setNext
(
LinearNode
<
T
>
node
)
{
next
=
node
;
}
/**
* Returns the element stored in this node.
*
@return
element stored at the node
*/
public
T getElement
()
{
return
element
;
}
/**
* Sets the element stored in this node.
*
@param
elem element to be stored at this node
*/
public
void
setElement
(
T elem
)
{
element
=
elem
;
}
}
Chap13/LinkedStack/jsjf/LinkedStack.java
Chap13/LinkedStack/jsjf/LinkedStack.java
package
jsjf
;
import
jsjf
.
exceptions
.
*
;
/**
* Represents a linked implementation of a stack.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
LinkedStack
<
T
>
implements
StackADT
<
T
>
{
private
int
count
;
private
LinearNode
<
T
>
top
;
/**
* Creates an empty stack.
*/
public
LinkedStack
()
{
count
=
0
;
top
=
null
;
}
/**
* Adds the specified element to the top of this stack.
*
@param
element element to be pushed on stack
*/
public
void
push
(
T element
)
{
LinearNode
<
T
>
temp
=
new
LinearNode
<
T
>
(
element
);
temp
.
setNext
(
top
);
top
=
temp
;
count
++
;
}
/**
* Removes the element at the top of this stack and returns a
* reference to it.
*
@return
element from top of stack
*
@throws
EmptyCollectionException if the stack is empty
*/
public
T pop
()
throws
EmptyCollectionException
{
if
(
isEmpty
())
throw
new
EmptyCollectionException
(
"stack"
);
T result
=
top
.
getElement
();
top
=
top
.
getNext
();
count
--
;
return
result
;
}
/**
* Returns a reference to the element at the top of this stack.
* The element is not removed from the stack.
*
@return
element on top of stack
*
@throws
EmptyCollectionException if the stack is empty
*/
public
T peek
()
throws
EmptyCollectionException
{
// To be completed as a Programming Project
return
null
;
// temp
}
/**
* Returns true if this stack is empty and false otherwise.
*
@return
true if stack is empty
*/
public
boolean
isEmpty
()
{
// To be completed as a Programming Project
return
true
;
// temp
}
/**
* Returns the number of elements in this stack.
*
@return
number of elements in the stack
*/
public
int
size
()
{
// To be completed as a Programming Project
return
0
;
// temp
}
/**
* Returns a string representation of this stack.
*
@return
string representation of the stack
*/
public
String
toString
()
{
// To be completed as a Programming Project
return
""
;
// temp
}
}
Chap13/LinkedStack/jsjf/StackADT.java
Chap13/LinkedStack/jsjf/StackADT.java
package
jsjf
;
/**
* Defines the interface to a stack collection.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
interface
StackADT
<
T
>
{
/**
* Adds the specified element to the top of this stack.
*
@param
element element to be pushed onto the stack
*/
public
void
push
(
T element
);
/**
* Removes and returns the top element from this stack.
*
@return
the element removed from the stack
*/
public
T pop
();
/**
* Returns without removing the top element of this stack.
*
@return
the element on top of the stack
*/
public
T peek
();
/**
* Returns true if this stack contains no elements.
*
@return
true if the stack is empty
*/
public
boolean
isEmpty
();
/**
* Returns the number of elements in this stack.
*
@return
the number of elements in the stack
*/
public
int
size
();
/**
* Returns a string representation of this stack.
*
@return
a string representation of the stack
*/
public
String
toString
();
}
Chap13/MazeTester/Maze.java
Chap13/MazeTester/Maze.java
import
java
.
util
.
*
;
import
java
.
io
.
*
;
/**
* Maze represents a maze of characters. The goal is to get from the
* top left corner to the bottom right, following a path of 1's. Arbitrary
* constants are used to represent locations in the maze that have been TRIED
* and that are part of the solution PATH.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
Maze
{
private
static
final
int
TRIED
=
2
;
private
static
final
int
PATH
=
3
;
private
int
numberRows
,
numberColumns
;
private
int
[][]
grid
;
/**
* Constructor for the Maze class. Loads a maze from the given file.
* Throws a FileNotFoundException if the given file is not found.
*
*
@param
filename the name of the file to load
*
@throws
FileNotFoundException if the given file is not found
*/
public
Maze
(
String
filename
)
throws
FileNotFoundException
{
Scanner
scan
=
new
Scanner
(
new
File
(
filename
));
numberRows
=
scan
.
nextInt
();
numberColumns
=
scan
.
nextInt
();
grid
=
new
int
[
numberRows
][
numberColumns
];
for
(
int
i
=
0
;
i
<
numberRows
;
i
++
)
for
(
int
j
=
0
;
j
<
numberColumns
;
j
++
)
grid
[
i
][
j
]
=
scan
.
nextInt
();
}
/**
* Marks the specified position in the maze as TRIED
*
*
@param
row the index of the row to try
*
@param
col the index of the column to try
*/
public
void
tryPosition
(
int
row
,
int
col
)
{
grid
[
row
][
col
]
=
TRIED
;
}
/**
* Return the number of rows in this maze
*
*
@return
the number of rows in this maze
*/
public
int
getRows
()
{
return
grid
.
length
;
}
/**
* Return the number of columns in this maze
*
*
@return
the number of columns in this maze
*/
public
int
getColumns
()
{
return
grid
[
0
].
length
;
}
/**
* Marks a given position in the maze as part of the PATH
*
*
@param
row the index of the row to mark as part of the PATH
*
@param
col the index of the column to mark as part of the PATH
*/
public
void
markPath
(
int
row
,
int
col
)
{
grid
[
row
][
col
]
=
PATH
;
}
/**
* Determines if a specific location is valid. A valid location
* is one that is on the grid, is not blocked, and has not been TRIED.
*
*
@param
row the row to be checked
*
@param
column the column to be checked
*
@return
true if the location is valid
*/
public
boolean
validPosition
(
int
row
,
int
column
)
{
boolean
result
=
false
;
// check if cell is in the bounds of the matrix
if
(
row
>=
0
&&
row
<
grid
.
length
&&
column
>=
0
&&
column
<
grid
[
row
].
length
)
// check if cell is not blocked and not previously tried
if
(
grid
[
row
][
column
]
==
1
)
result
=
true
;
return
result
;
}
/**
* Returns the maze as a string.
*
*
@return
a string representation of the maze
*/
public
String
toString
()
{
String
result
=
"\n"
;
for
(
int
row
=
0
;
row
<
grid
.
length
;
row
++
)
{
for
(
int
column
=
0
;
column
<
grid
[
row
].
length
;
column
++
)
result
+=
grid
[
row
][
column
]
+
""
;
result
+=
"\n"
;
}
return
result
;
}
}
Chap13/MazeTester/MazeSolver.java
Chap13/MazeTester/MazeSolver.java
import
java
.
util
.
*
;
/**
* MazeSolver attempts to traverse a Maze using a stack. The goal is to get from the
* given starting position to the bottom right, following a path of 1's. Arbitrary
* constants are used to represent locations in the maze that have been TRIED
* and that are part of the solution PATH.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
MazeSolver
{
private
Maze
maze
;
/**
* Constructor for the MazeSolver class.
*/
public
MazeSolver
(
Maze
maze
)
{
this
.
maze
=
maze
;
}
/**
* Attempts to traverse the maze using a stack. Inserts special
* characters indicating locations that have been TRIED and that
* eventually become part of the solution PATH.
*
*
@param
row row index of current location
*
@param
column column index of current location
*
@return
true if the maze has been solved
*/
public
boolean
traverse
()
{
boolean
done
=
false
;
Position
pos
=
new
Position
();
Deque
<
Position
>
stack
=
new
LinkedList
<
Position
>
();
stack
.
push
(
pos
);
while
(
!
(
done
)
&&
!
stack
.
isEmpty
())
{
pos
=
stack
.
pop
();
maze
.
tryPosition
(
pos
.
getx
(),
pos
.
gety
());
// this cell has been tried
if
(
pos
.
getx
()
==
maze
.
getRows
()
-
1
&&
pos
.
gety
()
==
maze
.
getColumns
()
-
1
)
done
=
true
;
// the maze is solved
else
{
pushNewPos
(
pos
.
getx
()
-
1
,
pos
.
gety
(),
stack
);
pushNewPos
(
pos
.
getx
()
+
1
,
pos
.
gety
(),
stack
);
pushNewPos
(
pos
.
getx
(),
pos
.
gety
()
-
1
,
stack
);
pushNewPos
(
pos
.
getx
(),
pos
.
gety
()
+
1
,
stack
);
}
}
return
done
;
}
/**
* Push a new attempted move onto the stack
*
@param
x represents x coordinate
*
@param
y represents y coordinate
*
@param
stack the working stack of moves within the grid
*
@return
stack of moves within the grid
*/
private
void
pushNewPos
(
int
x
,
int
y
,
Deque
<
Position
>
stack
)
{
Position
npos
=
new
Position
();
npos
.
setx
(
x
);
npos
.
sety
(
y
);
if
(
maze
.
validPosition
(
x
,
y
))
stack
.
push
(
npos
);
}
}
Chap13/MazeTester/MazeTester.java
Chap13/MazeTester/MazeTester.java
import
java
.
util
.
*
;
import
java
.
io
.
*
;
/**
* MazeTester determines if a maze can be traversed.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
MazeTester
{
/**
* Creates a new maze, prints its original form, attempts to
* solve it, and prints out its final form.
*/
public
static
void
main
(
String
[]
args
)
throws
FileNotFoundException
{
Scanner
scan
=
new
Scanner
(
System
.
in
);
System
.
out
.
print
(
"Enter the name of the file containing the maze: "
);
String
filename
=
scan
.
nextLine
();
Maze
labyrinth
=
new
Maze
(
filename
);
System
.
out
.
println
(
labyrinth
);
MazeSolver
solver
=
new
MazeSolver
(
labyrinth
);
if
(
solver
.
traverse
())
System
.
out
.
println
(
"The maze was successfully traversed!"
);
else
System
.
out
.
println
(
"There is no possible path."
);
System
.
out
.
println
(
labyrinth
);
}
}
Chap13/MazeTester/Position.java
Chap13/MazeTester/Position.java
/**
* Represents a single position in a maze of characters.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
Position
{
private
int
x
;
private
int
y
;
/**
* Constructs a position and sets the x & y coordinates to 0,0.
*/
Position
()
{
x
=
0
;
y
=
0
;
}
/**
* Returns the x-coordinate value of this position.
*
@return
the x-coordinate of this position
*/
public
int
getx
()
{
return
x
;
}
/**
* Returns the y-coordinate value of this position.
*
@return
the y-coordinate of this position
*/
public
int
gety
()
{
return
y
;
}
/**
* Sets the value of the current position's x-coordinate.
*
@param
a value of x-coordinate
*/
public
void
setx
(
int
a
)
{
x
=
a
;
}
/**
* Sets the value of the current position's x-coordinate.
*
@param
a value of y-coordinate
*/
public
void
sety
(
int
a
)
{
y
=
a
;
}
}
Chap13/MazeTester/testfile.txt
5 5 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 1 1 0 0 0 0 1 1
Chap13/MazeTester/testfile2.txt
21 35 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 1 0 1 1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 1 0 1 1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 1 0 1 1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 1 0 1 1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 1 0 1 1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 1 0 1 1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 0 1
Chap13/MazeTester/testfile3.txt
21 35 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 1 0 1 1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 1 0 1 1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 1 0 1 1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 1 0 1 1 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 0 1
Chap13/MazeTester/testfile4.txt
9 13 1 1 1 0 1 1 0 0 0 1 1 1 1 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 0 1 0 0 0 0 0 0 1 1 1 0 1 0 1 1 1 1 1 1 0 1 1 1 0 1 0 1 1 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1
Chap14/CircularArrayQueue/jsjf/CircularArrayQueue.java
Chap14/CircularArrayQueue/jsjf/CircularArrayQueue.java
package
jsjf
;
import
jsjf
.
exceptions
.
*
;
/**
* CircularArrayQueue represents an array implementation of a queue in
* which the indexes for the front and rear of the queue circle back to 0
* when they reach the end of the array.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
CircularArrayQueue
<
T
>
implements
QueueADT
<
T
>
{
private
final
static
int
DEFAULT_CAPACITY
=
100
;
private
int
front
,
rear
,
count
;
private
T
[]
queue
;
/**
* Creates an empty queue using the specified capacity.
*
@param
initialCapacity the initial size of the circular array queue
*/
public
CircularArrayQueue
(
int
initialCapacity
)
{
front
=
rear
=
count
=
0
;
queue
=
(
T
[])
(
new
Object
[
initialCapacity
]);
}
/**
* Creates an empty queue using the default capacity.
*/
public
CircularArrayQueue
()
{
this
(
DEFAULT_CAPACITY
);
}
/**
* Adds the specified element to the rear of this queue, expanding
* the capacity of the queue array if necessary.
*
@param
element the element to add to the rear of the queue
*/
public
void
enqueue
(
T element
)
{
if
(
size
()
==
queue
.
length
)
expandCapacity
();
queue
[
rear
]
=
element
;
rear
=
(
rear
+
1
)
%
queue
.
length
;
count
++
;
}
/**
* Creates a new array to store the contents of this queue with
* twice the capacity of the old one.
*/
private
void
expandCapacity
()
{
T
[]
larger
=
(
T
[])
(
new
Object
[
queue
.
length
*
2
]);
for
(
int
scan
=
0
;
scan
<
count
;
scan
++
)
{
larger
[
scan
]
=
queue
[
front
];
front
=
(
front
+
1
)
%
queue
.
length
;
}
front
=
0
;
rear
=
count
;
queue
=
larger
;
}
/**
* Removes the element at the front of this queue and returns a
* reference to it.
*
@return
the element removed from the front of the queue
*
@throws
EmptyCollectionException if the queue is empty
*/
public
T dequeue
()
throws
EmptyCollectionException
{
if
(
isEmpty
())
throw
new
EmptyCollectionException
(
"queue"
);
T result
=
queue
[
front
];
queue
[
front
]
=
null
;
front
=
(
front
+
1
)
%
queue
.
length
;
count
--
;
return
result
;
}
/**
* Returns a reference to the element at the front of this queue.
* The element is not removed from the queue.
*
@return
the first element in the queue
*
@throws
EmptyCollectionException if the queue is empty
*/
public
T first
()
throws
EmptyCollectionException
{
// To be completed as a Programming Project
return
null
;
// temp
}
/**
* Returns true if this queue is empty and false otherwise.
*
@return
true if this queue is empty
*/
public
boolean
isEmpty
()
{
// To be completed as a Programming Project
return
true
;
// temp
}
/**
* Returns the number of elements currently in this queue.
*
@return
the size of the queue
*/
public
int
size
()
{
// To be completed as a Programming Project
return
0
;
// temp
}
/**
* Returns a string representation of this queue.
*
@return
the string representation of the queue
*/
public
String
toString
()
{
// To be completed as a Programming Project
return
""
;
// temp
}
}
Chap14/CircularArrayQueue/jsjf/exceptions/EmptyCollectionException.java
Chap14/CircularArrayQueue/jsjf/exceptions/EmptyCollectionException.java
package
jsjf
.
exceptions
;
/**
* Represents the situation in which a collection is empty.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
EmptyCollectionException
extends
RuntimeException
{
/**
* Sets up this exception with an appropriate message.
*
@param
collection the name of the collection
*/
public
EmptyCollectionException
(
String
collection
)
{
super
(
"The "
+
collection
+
" is empty."
);
}
}
Chap14/CircularArrayQueue/jsjf/QueueADT.java
Chap14/CircularArrayQueue/jsjf/QueueADT.java
package
jsjf
;
/**
* QueueADT defines the interface to a queue collection.
*
*
@author
Java Foundation
*
@version
4.0
*/
public
interface
QueueADT
<
T
>
{
/**
* Adds one element to the rear of this queue.
*
@param
element the element to be added to the rear of the queue
*/
public
void
enqueue
(
T element
);
/**
* Removes and returns the element at the front of this queue.
*
@return
the element at the front of the queue
*/
public
T dequeue
();
/**
* Returns without removing the element at the front of this queue.
*
@return
the first element in the queue
*/
public
T first
();
/**
* Returns true if this queue contains no elements.
*
@return
true if this queue is empty
*/
public
boolean
isEmpty
();
/**
* Returns the number of elements in this queue.
*
@return
the integer representation of the size of the queue
*/
public
int
size
();
/**
* Returns a string representation of this queue.
*
@return
the string representation of the queue
*/
public
String
toString
();
}
Chap14/Codes/Codes.java
Chap14/Codes/Codes.java
import
java
.
util
.
*
;
/**
* Codes demonstrates the use of queues to encrypt and decrypt messages.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
Codes
{
/**
* Encode and decode a message using a key of values stored in
* a queue.
*/
public
static
void
main
(
String
[]
args
)
{
int
[]
key
=
{
5
,
12
,
-
3
,
8
,
-
9
,
4
,
10
};
Integer
keyValue
;
String
encoded
=
""
,
decoded
=
""
;
String
message
=
"All programmers are playwrights and all "
+
"computers are lousy actors."
;
Queue
<
Integer
>
encodingQueue
=
new
LinkedList
<
Integer
>
();
Queue
<
Integer
>
decodingQueue
=
new
LinkedList
<
Integer
>
();
// load key queues
for
(
int
scan
=
0
;
scan
<
key
.
length
;
scan
++
)
{
encodingQueue
.
add
(
key
[
scan
]);
decodingQueue
.
add
(
key
[
scan
]);
}
// encode message
for
(
int
scan
=
0
;
scan
<
message
.
length
();
scan
++
)
{
keyValue
=
encodingQueue
.
remove
();
encoded
+=
(
char
)
(
message
.
charAt
(
scan
)
+
keyValue
);
encodingQueue
.
add
(
keyValue
);
}
System
.
out
.
println
(
"Encoded Message:\n"
+
encoded
+
"\n"
);
// decode message
for
(
int
scan
=
0
;
scan
<
encoded
.
length
();
scan
++
)
{
keyValue
=
decodingQueue
.
remove
();
decoded
+=
(
char
)
(
encoded
.
charAt
(
scan
)
-
keyValue
);
decodingQueue
.
add
(
keyValue
);
}
System
.
out
.
println
(
"Decoded Message:\n"
+
decoded
);
}
}
Chap14/LinkedQueue/jsjf/exceptions/EmptyCollectionException.java
Chap14/LinkedQueue/jsjf/exceptions/EmptyCollectionException.java
package
jsjf
.
exceptions
;
/**
* Represents the situation in which a collection is empty.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
EmptyCollectionException
extends
RuntimeException
{
/**
* Sets up this exception with an appropriate message.
*
@param
collection the name of the collection
*/
public
EmptyCollectionException
(
String
collection
)
{
super
(
"The "
+
collection
+
" is empty."
);
}
}
Chap14/LinkedQueue/jsjf/LinearNode.java
Chap14/LinkedQueue/jsjf/LinearNode.java
package
jsjf
;
/**
* Represents a node in a linked list.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
LinearNode
<
T
>
{
private
LinearNode
<
T
>
next
;
private
T element
;
/**
* Creates an empty node.
*/
public
LinearNode
()
{
next
=
null
;
element
=
null
;
}
/**
* Creates a node storing the specified element.
*
@param
elem element to be stored
*/
public
LinearNode
(
T elem
)
{
next
=
null
;
element
=
elem
;
}
/**
* Returns the node that follows this one.
*
@return
reference to next node
*/
public
LinearNode
<
T
>
getNext
()
{
return
next
;
}
/**
* Sets the node that follows this one.
*
@param
node node to follow this one
*/
public
void
setNext
(
LinearNode
<
T
>
node
)
{
next
=
node
;
}
/**
* Returns the element stored in this node.
*
@return
element stored at the node
*/
public
T getElement
()
{
return
element
;
}
/**
* Sets the element stored in this node.
*
@param
elem element to be stored at this node
*/
public
void
setElement
(
T elem
)
{
element
=
elem
;
}
}
Chap14/LinkedQueue/jsjf/LinkedQueue.java
Chap14/LinkedQueue/jsjf/LinkedQueue.java
package
jsjf
;
import
jsjf
.
exceptions
.
*
;
/**
* LinkedQueue represents a linked implementation of a queue.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
LinkedQueue
<
T
>
implements
QueueADT
<
T
>
{
private
int
count
;
private
LinearNode
<
T
>
head
,
tail
;
/**
* Creates an empty queue.
*/
public
LinkedQueue
()
{
count
=
0
;
head
=
tail
=
null
;
}
/**
* Adds the specified element to the tail of this queue.
*
@param
element the element to be added to the tail of the queue
*/
public
void
enqueue
(
T element
)
{
LinearNode
<
T
>
node
=
new
LinearNode
<
T
>
(
element
);
if
(
isEmpty
())
head
=
node
;
else
tail
.
setNext
(
node
);
tail
=
node
;
count
++
;
}
/**
* Removes the element at the head of this queue and returns a
* reference to it.
*
@return
the element at the head of this queue
*
@throws
EmptyCollectionException if the queue is empty
*/
public
T dequeue
()
throws
EmptyCollectionException
{
if
(
isEmpty
())
throw
new
EmptyCollectionException
(
"queue"
);
T result
=
head
.
getElement
();
head
=
head
.
getNext
();
count
--
;
if
(
isEmpty
())
tail
=
null
;
return
result
;
}
/**
* Returns a reference to the element at the head of this queue.
* The element is not removed from the queue.
*
@return
a reference to the first element in this queue
*
@throws
EmptyCollectionsException if the queue is empty
*/
public
T first
()
throws
EmptyCollectionException
{
// To be completed as a Programming Project
return
null
;
// temp
}
/**
* Returns true if this queue is empty and false otherwise.
*
@return
true if this queue is empty
*/
public
boolean
isEmpty
()
{
// To be completed as a Programming Project
return
true
;
// temp
}
/**
* Returns the number of elements currently in this queue.
*
@return
the number of elements in the queue
*/
public
int
size
()
{
// To be completed as a Programming Project
return
0
;
// temp
}
/**
* Returns a string representation of this queue.
*
@return
the string representation of the queue
*/
public
String
toString
()
{
// To be completed as a Programming Project
return
""
;
// temp
}
}
Chap14/LinkedQueue/jsjf/QueueADT.java
Chap14/LinkedQueue/jsjf/QueueADT.java
package
jsjf
;
/**
* QueueADT defines the interface to a queue collection.
*
*
@author
Java Foundation
*
@version
4.0
*/
public
interface
QueueADT
<
T
>
{
/**
* Adds one element to the rear of this queue.
*
@param
element the element to be added to the rear of the queue
*/
public
void
enqueue
(
T element
);
/**
* Removes and returns the element at the front of this queue.
*
@return
the element at the front of the queue
*/
public
T dequeue
();
/**
* Returns without removing the element at the front of this queue.
*
@return
the first element in the queue
*/
public
T first
();
/**
* Returns true if this queue contains no elements.
*
@return
true if this queue is empty
*/
public
boolean
isEmpty
();
/**
* Returns the number of elements in this queue.
*
@return
the integer representation of the size of the queue
*/
public
int
size
();
/**
* Returns a string representation of this queue.
*
@return
the string representation of the queue
*/
public
String
toString
();
}
Chap14/TicketCounter/Customer.java
Chap14/TicketCounter/Customer.java
/**
* Customer represents a waiting customer.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
Customer
{
private
int
arrivalTime
,
departureTime
;
/**
* Creates a new customer with the specified arrival time.
*
@param
arrives the arrival time
*/
public
Customer
(
int
arrives
)
{
arrivalTime
=
arrives
;
departureTime
=
0
;
}
/**
* Returns the arrival time of this customer.
*
@return
the arrival time
*/
public
int
getArrivalTime
()
{
return
arrivalTime
;
}
/**
* Sets the departure time for this customer.
*
@param
departs the departure time
**/
public
void
setDepartureTime
(
int
departs
)
{
departureTime
=
departs
;
}
/**
* Returns the departure time of this customer.
*
@return
the departure time
*/
public
int
getDepartureTime
()
{
return
departureTime
;
}
/**
* Computes and returns the total time spent by this customer.
*
@return
the total customer time
*/
public
int
totalTime
()
{
return
departureTime
-
arrivalTime
;
}
}
Chap14/TicketCounter/TicketCounter.java
Chap14/TicketCounter/TicketCounter.java
import
java
.
util
.
*
;
/**
* TicketCounter demonstrates the use of a queue for simulating a line of customers.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
TicketCounter
{
private
final
static
int
PROCESS
=
120
;
private
final
static
int
MAX_CASHIERS
=
10
;
private
final
static
int
NUM_CUSTOMERS
=
100
;
public
static
void
main
(
String
[]
args
)
{
Customer
customer
;
Queue
<
Customer
>
customerQueue
=
new
LinkedList
<
Customer
>
();
int
[]
cashierTime
=
new
int
[
MAX_CASHIERS
];
int
totalTime
,
averageTime
,
departs
,
start
;
// run the simulation for various number of cashiers
for
(
int
cashiers
=
0
;
cashiers
<
MAX_CASHIERS
;
cashiers
++
)
{
// set each cashiers time to zero initially
for
(
int
count
=
0
;
count
<
cashiers
;
count
++
)
cashierTime
[
count
]
=
0
;
// load customer queue
for
(
int
count
=
1
;
count
<=
NUM_CUSTOMERS
;
count
++
)
customerQueue
.
add
(
new
Customer
(
count
*
15
));
totalTime
=
0
;
// process all customers in the queue
while
(
!
(
customerQueue
.
isEmpty
()))
{
for
(
int
count
=
0
;
count
<=
cashiers
;
count
++
)
{
if
(
!
(
customerQueue
.
isEmpty
()))
{
customer
=
customerQueue
.
remove
();
if
(
customer
.
getArrivalTime
()
>
cashierTime
[
count
])
start
=
customer
.
getArrivalTime
();
else
start
=
cashierTime
[
count
];
departs
=
start
+
PROCESS
;
customer
.
setDepartureTime
(
departs
);
cashierTime
[
count
]
=
departs
;
totalTime
+=
customer
.
totalTime
();
}
}
}
// output results for this simulation
averageTime
=
totalTime
/
NUM_CUSTOMERS
;
System
.
out
.
println
(
"Number of cashiers: "
+
(
cashiers
+
1
));
System
.
out
.
println
(
"Average time: "
+
averageTime
+
"\n"
);
}
}
}
Chap15/ArrayList/jsjf/ArrayList.java
Chap15/ArrayList/jsjf/ArrayList.java
package
jsjf
;
import
jsjf
.
exceptions
.
*
;
import
java
.
util
.
*
;
/**
* ArrayList represents an array implementation of a list. The front of
* the list is kept at array index 0. This class will be extended
* to create a specific kind of list.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
abstract
class
ArrayList
<
T
>
implements
ListADT
<
T
>
,
Iterable
<
T
>
{
private
final
static
int
DEFAULT_CAPACITY
=
100
;
private
final
static
int
NOT_FOUND
=
-
1
;
protected
int
rear
;
protected
T
[]
list
;
protected
int
modCount
;
/**
* Creates an empty list using the default capacity.
*/
public
ArrayList
()
{
this
(
DEFAULT_CAPACITY
);
}
/**
* Creates an empty list using the specified capacity.
*
*
@param
initialCapacity the integer value of the size of the array list
*/
public
ArrayList
(
int
initialCapacity
)
{
rear
=
0
;
list
=
(
T
[])(
new
Object
[
initialCapacity
]);
modCount
=
0
;
}
/**
* Creates a new array to store the contents of this list with
* twice the capacity of the old one. Called by descendant classes
* that add elements to the list.
*/
protected
void
expandCapacity
()
{
// To be completed as a Programming Project
}
/**
* Removes and returns the last element in this list.
*
*
@return
the last element in the list
*
@throws
EmptyCollectionException if the element is not in the list
*/
public
T removeLast
()
throws
EmptyCollectionException
{
// To be completed as a Programming Project
return
null
;
// temp
}
/**
* Removes and returns the first element in this list.
*
*
@return
the first element in the list
*
@throws
EmptyCollectionException if the element is not in the list
*/
public
T removeFirst
()
throws
EmptyCollectionException
{
// To be completed as a Programming Project
return
null
;
// temp
}
/**
* Removes and returns the specified element.
*
*
@param
element the element to be removed and returned from the list
*
@return
the removed elememt
*
@throws
ElementNotFoundException if the element is not in the list
*/
public
T remove
(
T element
)
{
T result
;
int
index
=
find
(
element
);
if
(
index
==
NOT_FOUND
)
throw
new
ElementNotFoundException
(
"ArrayList"
);
result
=
list
[
index
];
rear
--
;
// shift the appropriate elements
for
(
int
scan
=
index
;
scan
<
rear
;
scan
++
)
list
[
scan
]
=
list
[
scan
+
1
];
list
[
rear
]
=
null
;
modCount
++
;
return
result
;
}
/**
* Returns a reference to the element at the front of this list.
* The element is not removed from the list. Throws an
* EmptyCollectionException if the list is empty.
*
*
@return
a reference to the first element in the list
*
@throws
EmptyCollectionException if the list is empty
*/
public
T first
()
throws
EmptyCollectionException
{
// To be completed as a Programming Project
return
null
;
// temp
}
/**
* Returns a reference to the element at the rear of this list.
* The element is not removed from the list. Throws an
* EmptyCollectionException if the list is empty.
*
*
@return
a reference to the last element of this list
*
@throws
EmptyCollectionException if the list is empty
*/
public
T last
()
throws
EmptyCollectionException
{
// To be completed as a Programming Project
return
null
;
// temp
}
/**
* Returns true if this list contains the specified element.
*
*
@param
target the target element
*
@return
true if the target is in the list, false otherwise
*/
public
boolean
contains
(
T target
)
{
return
(
find
(
target
)
!=
NOT_FOUND
);
}
/**
* Returns the array index of the specified element, or the
* constant NOT_FOUND if it is not found.
*
*
@param
target the target element
*
@return
the index of the target element, or the
* NOT_FOUND constant
*/
private
int
find
(
T target
)
{
int
scan
=
0
;
int
result
=
NOT_FOUND
;
if
(
!
isEmpty
())
while
(
result
==
NOT_FOUND
&&
scan
<
rear
)
if
(
target
.
equals
(
list
[
scan
]))
result
=
scan
;
else
scan
++
;
return
result
;
}
/**
* Returns true if this list is empty and false otherwise.
*
*
@return
true if the list is empty, false otherwise
*/
public
boolean
isEmpty
()
{
// To be completed as a Programming Project
return
true
;
// temp
}
/**
* Returns the number of elements currently in this list.
*
*
@return
the number of elements in the list
*/
public
int
size
()
{
// To be completed as a Programming Project
return
0
;
// temp
}
/**
* Returns a string representation of this list.
*
*
@return
the string representation of the list
*/
public
String
toString
()
{
// To be completed as a Programming Project
return
""
;
// temp
}
/**
* Returns an iterator for the elements currently in this list.
*
*
@return
an iterator for the elements in the list
*/
public
Iterator
<
T
>
iterator
()
{
return
new
ArrayListIterator
();
}
/**
* ArrayListIterator iterator over the elements of an ArrayList.
*/
private
class
ArrayListIterator
implements
Iterator
<
T
>
{
int
iteratorModCount
;
int
current
;
/**
* Sets up this iterator using the specified modCount.
*
*
@param
modCount the current modification count for the ArrayList
*/
public
ArrayListIterator
()
{
iteratorModCount
=
modCount
;
current
=
0
;
}
/**
* Returns true if this iterator has at least one more element
* to deliver in the iteration.
*
*
@return
true if this iterator has at least one more element to deliver
* in the iteration
*
@throws
ConcurrentModificationException if the collection has changed
* while the iterator is in use
*/
public
boolean
hasNext
()
throws
ConcurrentModificationException
{
if
(
iteratorModCount
!=
modCount
)
throw
new
ConcurrentModificationException
();
return
(
current
<
rear
);
}
/**
* Returns the next element in the iteration. If there are no
* more elements in this iteration, a NoSuchElementException is
* thrown.
*
*
@return
the next element in the iteration
*
@throws
NoSuchElementException if an element not found exception occurs
*
@throws
ConcurrentModificationException if the collection has changed
*/
public
T next
()
throws
ConcurrentModificationException
{
if
(
!
hasNext
())
throw
new
NoSuchElementException
();
current
++
;
return
list
[
current
-
1
];
}
/**
* The remove operation is not supported in this collection.
*
*
@throws
UnsupportedOperationException if the remove method is called
*/
public
void
remove
()
throws
UnsupportedOperationException
{
throw
new
UnsupportedOperationException
();
}
}
}
Chap15/ArrayList/jsjf/ArrayOrderedList.java
Chap15/ArrayList/jsjf/ArrayOrderedList.java
package
jsjf
;
import
jsjf
.
exceptions
.
*
;
/**
* ArrayOrderedList represents an array implementation of an ordered list.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
ArrayOrderedList
<
T
>
extends
ArrayList
<
T
>
implements
OrderedListADT
<
T
>
{
/**
* Creates an empty list using the default capacity.
*/
public
ArrayOrderedList
()
{
super
();
}
/**
* Creates an empty list using the specified capacity.
*
*
@param
initialCapacity the initial size of the list
*/
public
ArrayOrderedList
(
int
initialCapacity
)
{
super
(
initialCapacity
);
}
/**
* Adds the specified Comparable element to this list, keeping
* the elements in sorted order.
*
*
@param
element the element to be added to the list
*/
public
void
add
(
T element
)
{
if
(
!
(
element
instanceof
Comparable
))
throw
new
NonComparableElementException
(
"OrderedList"
);
Comparable
<
T
>
comparableElement
=
(
Comparable
<
T
>
)
element
;
if
(
size
()
==
list
.
length
)
expandCapacity
();
int
scan
=
0
;
// find the insertion location
while
(
scan
<
rear
&&
comparableElement
.
compareTo
(
list
[
scan
])
>
0
)
scan
++
;
// shift existing elements up one
for
(
int
shift
=
rear
;
shift
>
scan
;
shift
--
)
list
[
shift
]
=
list
[
shift
-
1
];
// insert element
list
[
scan
]
=
element
;
rear
++
;
modCount
++
;
}
}
Chap15/ArrayList/jsjf/ArrayUnorderedList.java
Chap15/ArrayList/jsjf/ArrayUnorderedList.java
package
jsjf
;
import
jsjf
.
exceptions
.
*
;
/**
* ArrayUnorderedList represents an array implementation of an unordered list.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
ArrayUnorderedList
<
T
>
extends
ArrayList
<
T
>
implements
UnorderedListADT
<
T
>
{
/**
* Creates an empty list using the default capacity.
*/
public
ArrayUnorderedList
()
{
super
();
}
/**
* Creates an empty list using the specified capacity.
*
*
@param
initialCapacity the initial size of the list
*/
public
ArrayUnorderedList
(
int
initialCapacity
)
{
super
(
initialCapacity
);
}
/**
* Adds the specified element to the front of this list.
*
*
@param
element the element to be added to the front of the list
*/
public
void
addToFront
(
T element
)
{
// To be completed as a Programming Project
}
/**
* Adds the specified element to the rear of this list.
*
*
@param
element the element to be added to the list
*/
public
void
addToRear
(
T element
)
{
// To be completed as a Programming Project
}
/**
* Adds the specified element after the specified target element.
* Throws an ElementNotFoundException if the target is not found.
*
*
@param
element the element to be added after the target element
*
@param
target the target that the element is to be added after
*/
public
void
addAfter
(
T element
,
T target
)
{
if
(
size
()
==
list
.
length
)
expandCapacity
();
int
scan
=
0
;
// find the insertion point
while
(
scan
<
rear
&&
!
target
.
equals
(
list
[
scan
]))
scan
++
;
if
(
scan
==
rear
)
throw
new
ElementNotFoundException
(
"UnorderedList"
);
scan
++
;
// shift elements up one
for
(
int
shift
=
rear
;
shift
>
scan
;
shift
--
)
list
[
shift
]
=
list
[
shift
-
1
];
// insert element
list
[
scan
]
=
element
;
rear
++
;
modCount
++
;
}
}
Chap15/ArrayList/jsjf/exceptions/ElementNotFoundException.java
Chap15/ArrayList/jsjf/exceptions/ElementNotFoundException.java
package
jsjf
.
exceptions
;
/**
* ElementNotFoundException represents the situation in which a target element
* is not present in a collection
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
ElementNotFoundException
extends
RuntimeException
{
/**
* Sets up this exception with an appropriate message.
*/
public
ElementNotFoundException
(
String
collection
)
{
super
(
"The target element is not in this "
+
collection
);
}
}
Chap15/ArrayList/jsjf/exceptions/EmptyCollectionException.java
Chap15/ArrayList/jsjf/exceptions/EmptyCollectionException.java
package
jsjf
.
exceptions
;
/**
* Represents the situation in which a collection is empty.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
EmptyCollectionException
extends
RuntimeException
{
/**
* Sets up this exception with an appropriate message.
*
@param
collection the name of the collection
*/
public
EmptyCollectionException
(
String
collection
)
{
super
(
"The "
+
collection
+
" is empty."
);
}
}
Chap15/ArrayList/jsjf/exceptions/NonComparableElementException.java
Chap15/ArrayList/jsjf/exceptions/NonComparableElementException.java
package
jsjf
.
exceptions
;
/**
* NonComparableElementException represents the situation in which an attempt
* is made to add an element that is not comparable to an ordered collection
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
NonComparableElementException
extends
RuntimeException
{
/**
* Sets up this exception with an appropriate message.
*
*
@param
collection the exception message to deliver
*/
public
NonComparableElementException
(
String
collection
)
{
super
(
"The "
+
collection
+
" requires Comparable elements."
);
}
}
Chap15/ArrayList/jsjf/ListADT.java
Chap15/ArrayList/jsjf/ListADT.java
package
jsjf
;
import
java
.
util
.
Iterator
;
/**
* ListADT defines the interface to a general list collection. Specific
* types of lists will extend this interface to complete the
* set of necessary operations.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
interface
ListADT
<
T
>
extends
Iterable
<
T
>
{
/**
* Removes and returns the first element from this list.
*
*
@return
the first element from this list
*/
public
T removeFirst
();
/**
* Removes and returns the last element from this list.
*
*
@return
the last element from this list
*/
public
T removeLast
();
/**
* Removes and returns the specified element from this list.
*
*
@param
element the element to be removed from the list
*/
public
T remove
(
T element
);
/**
* Returns a reference to the first element in this list.
*
*
@return
a reference to the first element in this list
*/
public
T first
();
/**
* Returns a reference to the last element in this list.
*
*
@return
a reference to the last element in this list
*/
public
T last
();
/**
* Returns true if this list contains the specified target element.
*
*
@param
target the target that is being sought in the list
*
@return
true if the list contains this element
*/
public
boolean
contains
(
T target
);
/**
* Returns true if this list contains no elements.
*
*
@return
true if this list contains no elements
*/
public
boolean
isEmpty
();
/**
* Returns the number of elements in this list.
*
*
@return
the integer representation of number of elements in this list
*/
public
int
size
();
/**
* Returns an iterator for the elements in this list.
*
*
@return
an iterator over the elements in this list
*/
public
Iterator
<
T
>
iterator
();
/**
* Returns a string representation of this list.
*
*
@return
a string representation of this list
*/
public
String
toString
();
}
Chap15/ArrayList/jsjf/OrderedListADT.java
Chap15/ArrayList/jsjf/OrderedListADT.java
package
jsjf
;
/**
* OrderedListADT defines the interface to an ordered list collection. Only
* Comparable elements are stored, kept in the order determined by
* the inherent relationship among the elements.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
interface
OrderedListADT
<
T
>
extends
ListADT
<
T
>
{
/**
* Adds the specified element to this list at the proper location
*
*
@param
element the element to be added to this list
*/
public
void
add
(
T element
);
}
Chap15/ArrayList/jsjf/UnorderedListADT.java
Chap15/ArrayList/jsjf/UnorderedListADT.java
package
jsjf
;
/**
* UnorderedListADT defines the interface to an unordered list collection.
* Elements are stored in any order the user desires.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
interface
UnorderedListADT
<
T
>
extends
ListADT
<
T
>
{
/**
* Adds the specified element to the front of this list.
*
*
@param
element the element to be added to the front of this list
*/
public
void
addToFront
(
T element
);
/**
* Adds the specified element to the rear of this list.
*
*
@param
element the element to be added to the rear of this list
*/
public
void
addToRear
(
T element
);
/**
* Adds the specified element after the specified target.
*
*
@param
element the element to be added after the target
*
@param
target the target is the item that the element will be added
* after
*/
public
void
addAfter
(
T element
,
T target
);
}
Chap15/Josephus/Josephus.java
Chap15/Josephus/Josephus.java
import
java
.
util
.
*
;
/**
* Demonstrates the use of an indexed list to solve the Josephus problem.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
Josephus
{
/**
* Continue around the circle eliminating every nth soldier
* until all of the soldiers have been eliminated.
*/
public
static
void
main
(
String
[]
args
)
{
int
numPeople
,
skip
,
targetIndex
;
List
<
String
>
list
=
new
ArrayList
<
String
>
();
Scanner
in
=
new
Scanner
(
System
.
in
);
// get the initial number of soldiers
System
.
out
.
print
(
"Enter the number of soldiers: "
);
numPeople
=
in
.
nextInt
();
in
.
nextLine
();
// get the number of soldiers to skip
System
.
out
.
print
(
"Enter the number of soldiers to skip: "
);
skip
=
in
.
nextInt
();
// load the initial list of soldiers
for
(
int
count
=
1
;
count
<=
numPeople
;
count
++
)
{
list
.
add
(
"Soldier "
+
count
);
}
targetIndex
=
skip
;
System
.
out
.
println
(
"The order is: "
);
// Treating the list as circular, remove every nth element
// until the list is empty
while
(
!
list
.
isEmpty
())
{
System
.
out
.
println
(
list
.
remove
(
targetIndex
));
if
(
list
.
size
()
>
0
)
targetIndex
=
(
targetIndex
+
skip
)
%
list
.
size
();
}
}
}
Chap15/LinkedList/jsjf/exceptions/ElementNotFoundException.java
Chap15/LinkedList/jsjf/exceptions/ElementNotFoundException.java
package
jsjf
.
exceptions
;
/**
* ElementNotFoundException represents the situation in which a target element
* is not present in a collection
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
ElementNotFoundException
extends
RuntimeException
{
/**
* Sets up this exception with an appropriate message.
*/
public
ElementNotFoundException
(
String
collection
)
{
super
(
"The target element is not in this "
+
collection
);
}
}
Chap15/LinkedList/jsjf/exceptions/EmptyCollectionException.java
Chap15/LinkedList/jsjf/exceptions/EmptyCollectionException.java
package
jsjf
.
exceptions
;
/**
* Represents the situation in which a collection is empty.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
EmptyCollectionException
extends
RuntimeException
{
/**
* Sets up this exception with an appropriate message.
*
@param
collection the name of the collection
*/
public
EmptyCollectionException
(
String
collection
)
{
super
(
"The "
+
collection
+
" is empty."
);
}
}
Chap15/LinkedList/jsjf/exceptions/NonComparableElementException.java
Chap15/LinkedList/jsjf/exceptions/NonComparableElementException.java
package
jsjf
.
exceptions
;
/**
* NonComparableElementException represents the situation in which an attempt
* is made to add an element that is not comparable to an ordered collection
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
NonComparableElementException
extends
RuntimeException
{
/**
* Sets up this exception with an appropriate message.
*
*
@param
collection the exception message to deliver
*/
public
NonComparableElementException
(
String
collection
)
{
super
(
"The "
+
collection
+
" requires Comparable elements."
);
}
}
Chap15/LinkedList/jsjf/LinearNode.java
Chap15/LinkedList/jsjf/LinearNode.java
package
jsjf
;
/**
* LinearNode represents a node in a linked list.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
LinearNode
<
E
>
{
private
LinearNode
<
E
>
next
;
private
E element
;
/**
* Creates an empty node.
*/
public
LinearNode
()
{
next
=
null
;
element
=
null
;
}
/**
* Creates a node storing the specified element.
*
*
@param
elem the element to be stored within the new node
*/
public
LinearNode
(
E elem
)
{
next
=
null
;
element
=
elem
;
}
/**
* Returns the node that follows this one.
*
*
@return
the node that follows the current one
*/
public
LinearNode
<
E
>
getNext
()
{
return
next
;
}
/**
* Sets the node that follows this one.
*
*
@param
node the node to be set to follow the current one
*/
public
void
setNext
(
LinearNode
<
E
>
node
)
{
next
=
node
;
}
/**
* Returns the element stored in this node.
*
*
@return
the element stored in this node
*/
public
E getElement
()
{
return
element
;
}
/**
* Sets the element stored in this node.
*
*
@param
elem the element to be stored in this node
*/
public
void
setElement
(
E elem
)
{
element
=
elem
;
}
}
Chap15/LinkedList/jsjf/LinkedList.java
Chap15/LinkedList/jsjf/LinkedList.java
package
jsjf
;
import
jsjf
.
exceptions
.
*
;
import
java
.
util
.
*
;
/**
* LinkedList represents a linked implementation of a list.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
abstract
class
LinkedList
<
T
>
implements
ListADT
<
T
>
,
Iterable
<
T
>
{
protected
int
count
;
protected
LinearNode
<
T
>
head
,
tail
;
protected
int
modCount
;
/**
* Creates an empty list.
*/
public
LinkedList
()
{
count
=
0
;
head
=
tail
=
null
;
modCount
=
0
;
}
/**
* Removes the first element in this list and returns a reference
* to it. Throws an EmptyCollectionException if the list is empty.
*
*
@return
a reference to the first element of this list
*
@throws
EmptyCollectionException if the list is empty
*/
public
T removeFirst
()
throws
EmptyCollectionException
{
// To be completed as a Programming Project
return
null
;
// temp
}
/**
* Removes the last element in this list and returns a reference
* to it. Throws an EmptyCollectionException if the list is empty.
*
*
@return
the last element in this list
*
@throws
EmptyCollectionException if the list is empty
*/
public
T removeLast
()
throws
EmptyCollectionException
{
// To be completed as a Programming Project
return
null
;
// temp
}
/**
* Removes the first instance of the specified element from this
* list and returns a reference to it. Throws an EmptyCollectionException
* if the list is empty. Throws a ElementNotFoundException if the
* specified element is not found in the list.
*
*
@param
targetElement the element to be removed from the list
*
@return
a reference to the removed element
*
@throws
EmptyCollectionException if the list is empty
*
@throws
ElementNotFoundException if the target element is not found
*/
public
T remove
(
T targetElement
)
throws
EmptyCollectionException
,
ElementNotFoundException
{
if
(
isEmpty
())
throw
new
EmptyCollectionException
(
"LinkedList"
);
boolean
found
=
false
;
LinearNode
<
T
>
previous
=
null
;
LinearNode
<
T
>
current
=
head
;
while
(
current
!=
null
&&
!
found
)
if
(
targetElement
.
equals
(
current
.
getElement
()))
found
=
true
;
else
{
previous
=
current
;
current
=
current
.
getNext
();
}
if
(
!
found
)
throw
new
ElementNotFoundException
(
"LinkedList"
);
if
(
size
()
==
1
)
// only one element in the list
head
=
tail
=
null
;
else
if
(
current
.
equals
(
head
))
// target is at the head
head
=
current
.
getNext
();
else
if
(
current
.
equals
(
tail
))
// target is at the tail
{
tail
=
previous
;
tail
.
setNext
(
null
);
}
else
// target is in the middle
previous
.
setNext
(
current
.
getNext
());
count
--
;
modCount
++
;
return
current
.
getElement
();
}
/**
* Returns the first element in this list without removing it.
*
*
@return
the first element in this list
*
@throws
EmptyCollectionException if the list is empty
*/
public
T first
()
throws
EmptyCollectionException
{
// To be completed as a Programming Project
return
null
;
// temp
}
/**
* Returns the last element in this list without removing it.
*
*
@return
the last element in this list
*
@throws
EmptyCollectionException if the list is empty
*/
public
T last
()
throws
EmptyCollectionException
{
// To be completed as a Programming Project
return
null
;
// temp
}
/**
* Returns true if the specified element is found in this list and
* false otherwise. Throws an EmptyCollectionException if the list
* is empty.
*
*
@param
targetElement the element that is sought in the list
*
@return
true if the element is found in this list
*
@throws
EmptyCollectionException if the list is empty
*/
public
boolean
contains
(
T targetElement
)
throws
EmptyCollectionException
{
// To be completed as a Programming Project
return
true
;
// temp
}
/**
* Returns true if this list is empty and false otherwise.
*
*
@return
true if the list is empty, false otherwise
*/
public
boolean
isEmpty
()
{
// To be completed as a Programming Project
return
true
;
// temp
}
/**
* Returns the number of elements in this list.
*
*
@return
the number of elements in the list
*/
public
int
size
()
{
// To be completed as a Programming Project
return
0
;
// temp
}
/**
* Returns a string representation of this list.
*
*
@return
a string representation of the list
*/
public
String
toString
()
{
// To be completed as a Programming Project
return
""
;
// temp
}
/**
* Returns an iterator for the elements in this list.
*
*
@return
an iterator over the elements of the list
*/
public
Iterator
<
T
>
iterator
()
{
return
new
LinkedListIterator
();
}
/**
* LinkedIterator represents an iterator for a linked list of linear nodes.
*/
private
class
LinkedListIterator
implements
Iterator
<
T
>
{
private
int
iteratorModCount
;
// the number of elements in the collection
private
LinearNode
<
T
>
current
;
// the current position
/**
* Sets up this iterator using the specified items.
*
*
@param
collection the collection the iterator will move over
*
@param
size the integer size of the collection
*/
public
LinkedListIterator
()
{
current
=
head
;
iteratorModCount
=
modCount
;
}
/**
* Returns true if this iterator has at least one more element
* to deliver in the iteration.
*
*
@return
true if this iterator has at least one more element to deliver
* in the iteration
*
@throws
ConcurrentModificationException if the collection has changed
* while the iterator is in use
*/
public
boolean
hasNext
()
throws
ConcurrentModificationException
{
if
(
iteratorModCount
!=
modCount
)
throw
new
ConcurrentModificationException
();
return
(
current
!=
null
);
}
/**
* Returns the next element in the iteration. If there are no
* more elements in this iteration, a NoSuchElementException is
* thrown.
*
*
@return
the next element in the iteration
*
@throws
NoSuchElementException if the iterator is empty
*/
public
T next
()
throws
ConcurrentModificationException
{
if
(
!
hasNext
())
throw
new
NoSuchElementException
();
T result
=
current
.
getElement
();
current
=
current
.
getNext
();
return
result
;
}
/**
* The remove operation is not supported.
*
*
@throws
UnsupportedOperationException if the remove operation is called
*/
public
void
remove
()
throws
UnsupportedOperationException
{
throw
new
UnsupportedOperationException
();
}
}
}
Chap15/LinkedList/jsjf/LinkedOrderedList.java
Chap15/LinkedList/jsjf/LinkedOrderedList.java
package
jsjf
;
import
jsjf
.
exceptions
.
*
;
/**
* LinkedOrderedList represents a singly linked implementation of an
* ordered list.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
LinkedOrderedList
<
T
>
extends
LinkedList
<
T
>
implements
OrderedListADT
<
T
>
{
/**
* Creates an empty list.
*/
public
LinkedOrderedList
()
{
super
();
}
/**
* Adds the specified element to this list at the location determined by
* the element's natural ordering. Throws a NonComparableElementException
* if the element is not comparable.
*
*
@param
element the element to be added to this list
*
@throws
NonComparableElementException if the element is not comparable
*/
public
void
add
(
T element
)
{
// To be completed as a Programming Project
}
}
Chap15/LinkedList/jsjf/LinkedUnorderedList.java
Chap15/LinkedList/jsjf/LinkedUnorderedList.java
package
jsjf
;
import
jsjf
.
exceptions
.
*
;
/**
* LinkedUnorderedList represents a singly linked implementation of an
* unordered list.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
LinkedUnorderedList
<
T
>
extends
LinkedList
<
T
>
implements
UnorderedListADT
<
T
>
{
/**
* Creates an empty list.
*/
public
LinkedUnorderedList
()
{
super
();
}
/**
* Adds the specified element to the front of this list.
*
*
@param
element the element to be added to the list
*/
public
void
addToFront
(
T element
)
{
// To be completed as a Programming Project
}
/**
* Adds the specified element to the rear of this list.
*
*
@param
element the element to be added to the list
*/
public
void
addToRear
(
T element
)
{
// To be completed as a Programming Project
}
/**
* Adds the specified element to this list after the given target.
*
*
@param
element the element to be added to this list
*
@param
target the target element to be added after
*
@throws
ElementNotFoundException if the target is not found
*/
public
void
addAfter
(
T element
,
T target
)
{
// To be completed as a Programming Project
}
}
Chap15/LinkedList/jsjf/ListADT.java
Chap15/LinkedList/jsjf/ListADT.java
package
jsjf
;
import
java
.
util
.
Iterator
;
/**
* ListADT defines the interface to a general list collection. Specific
* types of lists will extend this interface to complete the
* set of necessary operations.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
interface
ListADT
<
T
>
extends
Iterable
<
T
>
{
/**
* Removes and returns the first element from this list.
*
*
@return
the first element from this list
*/
public
T removeFirst
();
/**
* Removes and returns the last element from this list.
*
*
@return
the last element from this list
*/
public
T removeLast
();
/**
* Removes and returns the specified element from this list.
*
*
@param
element the element to be removed from the list
*/
public
T remove
(
T element
);
/**
* Returns a reference to the first element in this list.
*
*
@return
a reference to the first element in this list
*/
public
T first
();
/**
* Returns a reference to the last element in this list.
*
*
@return
a reference to the last element in this list
*/
public
T last
();
/**
* Returns true if this list contains the specified target element.
*
*
@param
target the target that is being sought in the list
*
@return
true if the list contains this element
*/
public
boolean
contains
(
T target
);
/**
* Returns true if this list contains no elements.
*
*
@return
true if this list contains no elements
*/
public
boolean
isEmpty
();
/**
* Returns the number of elements in this list.
*
*
@return
the integer representation of number of elements in this list
*/
public
int
size
();
/**
* Returns an iterator for the elements in this list.
*
*
@return
an iterator over the elements in this list
*/
public
Iterator
<
T
>
iterator
();
/**
* Returns a string representation of this list.
*
*
@return
a string representation of this list
*/
public
String
toString
();
}
Chap15/LinkedList/jsjf/OrderedListADT.java
Chap15/LinkedList/jsjf/OrderedListADT.java
package
jsjf
;
/**
* OrderedListADT defines the interface to an ordered list collection. Only
* Comparable elements are stored, kept in the order determined by
* the inherent relationship among the elements.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
interface
OrderedListADT
<
T
>
extends
ListADT
<
T
>
{
/**
* Adds the specified element to this list at the proper location
*
*
@param
element the element to be added to this list
*/
public
void
add
(
T element
);
}
Chap15/LinkedList/jsjf/UnorderedListADT.java
Chap15/LinkedList/jsjf/UnorderedListADT.java
package
jsjf
;
/**
* UnorderedListADT defines the interface to an unordered list collection.
* Elements are stored in any order the user desires.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
interface
UnorderedListADT
<
T
>
extends
ListADT
<
T
>
{
/**
* Adds the specified element to the front of this list.
*
*
@param
element the element to be added to the front of this list
*/
public
void
addToFront
(
T element
);
/**
* Adds the specified element to the rear of this list.
*
*
@param
element the element to be added to the rear of this list
*/
public
void
addToRear
(
T element
);
/**
* Adds the specified element after the specified target.
*
*
@param
element the element to be added after the target
*
@param
target the target is the item that the element will be added
* after
*/
public
void
addAfter
(
T element
,
T target
);
}
Chap15/POSTester/Course.java
Chap15/POSTester/Course.java
import
java
.
io
.
Serializable
;
/**
* Represents a course that might be taken by a student.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
Course
implements
Serializable
{
private
String
prefix
;
private
int
number
;
private
String
title
;
private
String
grade
;
/**
* Constructs the course with the specified information.
*
*
@param
prefix the prefix of the course designation
*
@param
number the number of the course designation
*
@param
title the title of the course
*
@param
grade the grade received for the course
*/
public
Course
(
String
prefix
,
int
number
,
String
title
,
String
grade
)
{
this
.
prefix
=
prefix
;
this
.
number
=
number
;
this
.
title
=
title
;
if
(
grade
==
null
)
this
.
grade
=
""
;
else
this
.
grade
=
grade
;
}
/**
* Constructs the course with the specified information, with no grade
* established.
*
*
@param
prefix the prefix of the course designation
*
@param
number the number of the course designation
*
@param
title the title of the course
*/
public
Course
(
String
prefix
,
int
number
,
String
title
)
{
this
(
prefix
,
number
,
title
,
""
);
}
/**
* Returns the prefix of the course designation.
*
*
@return
the prefix of the course designation
*/
public
String
getPrefix
()
{
return
prefix
;
}
/**
* Returns the number of the course designation.
*
*
@return
the number of the course designation
*/
public
int
getNumber
()
{
return
number
;
}
/**
* Returns the title of this course.
*
*
@return
the prefix of the course
*/
public
String
getTitle
()
{
return
title
;
}
/**
* Returns the grade for this course.
*
*
@return
the grade for this course
*/
public
String
getGrade
()
{
return
grade
;
}
/**
* Sets the grade for this course to the one specified.
*
*
@param
grade the new grade for the course
*/
public
void
setGrade
(
String
grade
)
{
this
.
grade
=
grade
;
}
/**
* Returns true if this course has been taken (if a grade has been received).
*
*
@return
true if this course has been taken and false otherwise
*/
public
boolean
taken
()
{
return
!
grade
.
equals
(
""
);
}
/**
* Determines if this course is equal to the one specified, based on the
* course designation (prefix and number).
*
*
@return
true if this course is equal to the parameter
*/
public
boolean
equals
(
Object
other
)
{
boolean
result
=
false
;
if
(
other
instanceof
Course
)
{
Course
otherCourse
=
(
Course
)
other
;
if
(
prefix
.
equals
(
otherCourse
.
getPrefix
())
&&
number
==
otherCourse
.
getNumber
())
result
=
true
;
}
return
result
;
}
/**
* Creates and returns a string representation of this course.
*
*
@return
a string representation of the course
*/
public
String
toString
()
{
String
result
=
prefix
+
" "
+
number
+
": "
+
title
;
if
(
!
grade
.
equals
(
""
))
result
+=
" ["
+
grade
+
"]"
;
return
result
;
}
}
Chap15/POSTester/POSTester.java
Chap15/POSTester/POSTester.java
import
java
.
io
.
IOException
;
/**
* Demonstrates the use of a list to manage a set of objects.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
POSTester
{
/**
* Creates and populates a Program of Study. Then saves it using serialization.
*/
public
static
void
main
(
String
[]
args
)
throws
IOException
{
ProgramOfStudy
pos
=
new
ProgramOfStudy
();
pos
.
addCourse
(
new
Course
(
"CS"
,
101
,
"Introduction to Programming"
,
"A-"
));
pos
.
addCourse
(
new
Course
(
"ARCH"
,
305
,
"Building Analysis"
,
"A"
));
pos
.
addCourse
(
new
Course
(
"GER"
,
210
,
"Intermediate German"
));
pos
.
addCourse
(
new
Course
(
"CS"
,
320
,
"Computer Architecture"
));
pos
.
addCourse
(
new
Course
(
"THE"
,
201
,
"The Theatre Experience"
));
Course
arch
=
pos
.
find
(
"CS"
,
320
);
pos
.
addCourseAfter
(
arch
,
new
Course
(
"CS"
,
321
,
"Operating Systems"
));
Course
theatre
=
pos
.
find
(
"THE"
,
201
);
theatre
.
setGrade
(
"A-"
);
Course
german
=
pos
.
find
(
"GER"
,
210
);
pos
.
replace
(
german
,
new
Course
(
"FRE"
,
110
,
"Beginning French"
,
"B+"
));
System
.
out
.
println
(
pos
);
pos
.
save
(
"ProgramOfStudy"
);
}
}
Chap15/POSTester/ProgramOfStudy
Chap15/POSTester/ProgramOfStudy.java
Chap15/POSTester/ProgramOfStudy.java
import
java
.
io
.
FileInputStream
;
import
java
.
io
.
FileOutputStream
;
import
java
.
io
.
IOException
;
import
java
.
io
.
ObjectInputStream
;
import
java
.
io
.
ObjectOutputStream
;
import
java
.
io
.
Serializable
;
import
java
.
util
.
Iterator
;
import
java
.
util
.
LinkedList
;
import
java
.
util
.
List
;
/**
* Represents a Program of Study, a list of courses taken and planned, for an
* individual student.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
ProgramOfStudy
implements
Iterable
<
Course
>
,
Serializable
{
private
List
<
Course
>
list
;
/**
* Constructs an initially empty Program of Study.
*/
public
ProgramOfStudy
()
{
list
=
new
LinkedList
<
Course
>
();
}
/**
* Adds the specified course to the end of the course list.
*
*
@param
course the course to add
*/
public
void
addCourse
(
Course
course
)
{
if
(
course
!=
null
)
list
.
add
(
course
);
}
/**
* Finds and returns the course matching the specified prefix and number.
*
*
@param
prefix the prefix of the target course
*
@param
number the number of the target course
*
@return
the course, or null if not found
*/
public
Course
find
(
String
prefix
,
int
number
)
{
for
(
Course
course
:
list
)
if
(
prefix
.
equals
(
course
.
getPrefix
())
&&
number
==
course
.
getNumber
())
return
course
;
return
null
;
}
/**
* Adds the specified course after the target course. Does nothing if
* either course is null or if the target is not found.
*
*
@param
target the course after which the new course will be added
*
@param
newCourse the course to add
*/
public
void
addCourseAfter
(
Course
target
,
Course
newCourse
)
{
if
(
target
==
null
||
newCourse
==
null
)
return
;
int
targetIndex
=
list
.
indexOf
(
target
);
if
(
targetIndex
!=
-
1
)
list
.
add
(
targetIndex
+
1
,
newCourse
);
}
/**
* Replaces the specified target course with the new course. Does nothing if
* either course is null or if the target is not found.
*
*
@param
target the course to be replaced
*
@param
newCourse the new course to add
*/
public
void
replace
(
Course
target
,
Course
newCourse
)
{
if
(
target
==
null
||
newCourse
==
null
)
return
;
int
targetIndex
=
list
.
indexOf
(
target
);
if
(
targetIndex
!=
-
1
)
list
.
set
(
targetIndex
,
newCourse
);
}
/**
* Creates and returns a string representation of this Program of Study.
*
*
@return
a string representation of the Program of Study
*/
public
String
toString
()
{
String
result
=
""
;
for
(
Course
course
:
list
)
result
+=
course
+
"\n"
;
return
result
;
}
/**
* Returns an iterator for this Program of Study.
*
*
@return
an iterator for the Program of Study
*/
public
Iterator
<
Course
>
iterator
()
{
return
list
.
iterator
();
}
/**
* Saves a serialized version of this Program of Study to the specified
* file name.
*
*
@param
fileName the file name under which the POS will be stored
*
@throws
IOException
*/
public
void
save
(
String
fileName
)
throws
IOException
{
FileOutputStream
fos
=
new
FileOutputStream
(
fileName
);
ObjectOutputStream
oos
=
new
ObjectOutputStream
(
fos
);
oos
.
writeObject
(
this
);
oos
.
flush
();
oos
.
close
();
}
/**
* Loads a serialized Program of Study from the specified file.
*
*
@param
fileName the file from which the POS is read
*
@return
the loaded Program of Study
*
@throws
IOException
*
@throws
ClassNotFoundException
*/
public
static
ProgramOfStudy
load
(
String
fileName
)
throws
IOException
,
ClassNotFoundException
{
FileInputStream
fis
=
new
FileInputStream
(
fileName
);
ObjectInputStream
ois
=
new
ObjectInputStream
(
fis
);
ProgramOfStudy
pos
=
(
ProgramOfStudy
)
ois
.
readObject
();
ois
.
close
();
return
pos
;
}
}
Chap16/ArrayListIterator/jsjf/ArrayList.java
Chap16/ArrayListIterator/jsjf/ArrayList.java
package
jsjf
;
import
jsjf
.
exceptions
.
*
;
import
java
.
util
.
*
;
/**
* ArrayList represents an array implementation of a list. The front of
* the list is kept at array index 0. This class will be extended
* to create a specific kind of list.
*
* Solution to Programming Project 15.8 (full implementation)
*
*
@author
Java Foundations
*
@version
4.0
*/
public
abstract
class
ArrayList
<
T
>
implements
ListADT
<
T
>
,
Iterable
<
T
>
{
private
final
static
int
DEFAULT_CAPACITY
=
100
;
private
final
static
int
NOT_FOUND
=
-
1
;
protected
int
rear
;
protected
T
[]
list
;
protected
int
modCount
;
/**
* Creates an empty list using the default capacity.
*/
public
ArrayList
()
{
this
(
DEFAULT_CAPACITY
);
}
/**
* Creates an empty list using the specified capacity.
*
*
@param
initialCapacity the integer value of the size of the array list
*/
public
ArrayList
(
int
initialCapacity
)
{
rear
=
0
;
list
=
(
T
[])(
new
Object
[
initialCapacity
]);
modCount
=
0
;
}
/**
* Creates a new array to store the contents of this list with
* twice the capacity of the old one. Called by descendant classes
* that add elements to the list.
*/
protected
void
expandCapacity
()
{
list
=
Arrays
.
copyOf
(
list
,
list
.
length
*
2
);
}
/**
* Removes and returns the last element in this list.
*
*
@return
the last element in the list
*
@throws
EmptyCollectionException if the element is not in the list
*/
public
T removeLast
()
throws
EmptyCollectionException
{
if
(
isEmpty
())
throw
new
EmptyCollectionException
(
"ArrayList"
);
T result
;
rear
--
;
result
=
list
[
rear
];
list
[
rear
]
=
null
;
modCount
++
;
return
result
;
}
/**
* Removes and returns the first element in this list.
*
*
@return
the first element in the list
*
@throws
EmptyCollectionException if the element is not in the list
*/
public
T removeFirst
()
throws
EmptyCollectionException
{
if
(
isEmpty
())
throw
new
EmptyCollectionException
(
"ArrayList"
);
T result
=
list
[
0
];
rear
--
;
// shift the elements
for
(
int
scan
=
0
;
scan
<
rear
;
scan
++
)
list
[
scan
]
=
list
[
scan
+
1
];
list
[
rear
]
=
null
;
modCount
++
;
return
result
;
}
/**
* Removes and returns the specified element.
*
*
@param
element the element to be removed and returned from the list
*
@return
the removed element
*
@throws
ElementNotFoundException if the element is not in the list
*/
public
T remove
(
T element
)
{
T result
;
int
index
=
find
(
element
);
if
(
index
==
NOT_FOUND
)
throw
new
ElementNotFoundException
(
"ArrayList"
);
result
=
list
[
index
];
rear
--
;
// shift the appropriate elements
for
(
int
scan
=
index
;
scan
<
rear
;
scan
++
)
list
[
scan
]
=
list
[
scan
+
1
];
list
[
rear
]
=
null
;
modCount
++
;
return
result
;
}
/**
* Returns a reference to the element at the front of this list.
* The element is not removed from the list. Throws an
* EmptyCollectionException if the list is empty.
*
*
@return
a reference to the first element in the list
*
@throws
EmptyCollectionException if the list is empty
*/
public
T first
()
throws
EmptyCollectionException
{
if
(
isEmpty
())
throw
new
EmptyCollectionException
(
"ArrayList"
);
return
list
[
0
];
}
/**
* Returns a reference to the element at the rear of this list.
* The element is not removed from the list. Throws an
* EmptyCollectionException if the list is empty.
*
*
@return
a reference to the last element of this list
*
@throws
EmptyCollectionException if the list is empty
*/
public
T last
()
throws
EmptyCollectionException
{
if
(
isEmpty
())
throw
new
EmptyCollectionException
(
"ArrayList"
);
return
list
[
rear
-
1
];
}
/**
* Returns true if this list contains the specified element.
*
*
@param
target the target element
*
@return
true if the target is in the list, false otherwise
*/
public
boolean
contains
(
T target
)
{
return
(
find
(
target
)
!=
NOT_FOUND
);
}
/**
* Returns the array index of the specified element, or the
* constant NOT_FOUND if it is not found.
*
*
@param
target the target element
*
@return
the index of the target element, or the
* NOT_FOUND constant
*/
private
int
find
(
T target
)
{
int
scan
=
0
;
int
result
=
NOT_FOUND
;
if
(
!
isEmpty
())
while
(
result
==
NOT_FOUND
&&
scan
<
rear
)
if
(
target
.
equals
(
list
[
scan
]))
result
=
scan
;
else
scan
++
;
return
result
;
}
/**
* Returns true if this list is empty and false otherwise.
*
*
@return
true if the list is empty, false otherwise
*/
public
boolean
isEmpty
()
{
return
(
rear
==
0
);
}
/**
* Returns the number of elements currently in this list.
*
*
@return
the number of elements in the list
*/
public
int
size
()
{
return
rear
;
}
/**
* Returns a string representation of this list.
*
*
@return
the string representation of the list
*/
public
String
toString
()
{
String
result
=
""
;
for
(
int
scan
=
0
;
scan
<
rear
;
scan
++
)
result
=
result
+
list
[
scan
]
+
"\n"
;
return
result
;
}
/**
* Returns an iterator for the elements currently in this list.
*
*
@return
an iterator for the elements in the list
*/
public
Iterator
<
T
>
iterator
()
{
return
new
ArrayListIterator
();
}
/**
* ArrayListIterator iterator over the elements of an ArrayList.
*/
private
class
ArrayListIterator
implements
Iterator
<
T
>
{
int
iteratorModCount
;
int
current
;
/**
* Sets up this iterator using the specified modCount.
*
*
@param
modCount the current modification count for the ArrayList
*/
public
ArrayListIterator
()
{
iteratorModCount
=
modCount
;
current
=
0
;
}
/**
* Returns true if this iterator has at least one more element
* to deliver in the iteration.
*
*
@return
true if this iterator has at least one more element to deliver
* in the iteration
*
@throws
ConcurrentModificationException if the collection has changed
* while the iterator is in use
*/
public
boolean
hasNext
()
throws
ConcurrentModificationException
{
if
(
iteratorModCount
!=
modCount
)
throw
new
ConcurrentModificationException
();
return
(
current
<
rear
);
}
/**
* Returns the next element in the iteration. If there are no
* more elements in this iteration, a NoSuchElementException is
* thrown.
*
*
@return
the next element in the iteration
*
@throws
NoSuchElementException if an element not found exception occurs
*
@throws
ConcurrentModificationException if the collection has changed
*/
public
T next
()
throws
ConcurrentModificationException
{
if
(
!
hasNext
())
throw
new
NoSuchElementException
();
current
++
;
return
list
[
current
-
1
];
}
/**
* The remove operation is not supported in this collection.
*
*
@throws
UnsupportedOperationException if the remove method is called
*/
public
void
remove
()
throws
UnsupportedOperationException
{
throw
new
UnsupportedOperationException
();
}
}
}
Chap16/ArrayListIterator/jsjf/ArrayOrderedList.java
Chap16/ArrayListIterator/jsjf/ArrayOrderedList.java
package
jsjf
;
import
jsjf
.
exceptions
.
*
;
/**
* ArrayOrderedList represents an array implementation of an ordered list.
*
* Solution to Programming Project 15.9 (full implementation)
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
ArrayOrderedList
<
T
>
extends
ArrayList
<
T
>
implements
OrderedListADT
<
T
>
{
/**
* Creates an empty list using the default capacity.
*/
public
ArrayOrderedList
()
{
super
();
}
/**
* Creates an empty list using the specified capacity.
*
*
@param
initialCapacity the initial size of the list
*/
public
ArrayOrderedList
(
int
initialCapacity
)
{
super
(
initialCapacity
);
}
/**
* Adds the specified Comparable element to this list, keeping
* the elements in sorted order.
*
*
@param
element the element to be added to the list
*/
public
void
add
(
T element
)
{
if
(
!
(
element
instanceof
Comparable
))
throw
new
NonComparableElementException
(
"OrderedList"
);
Comparable
<
T
>
comparableElement
=
(
Comparable
<
T
>
)
element
;
if
(
size
()
==
list
.
length
)
expandCapacity
();
int
scan
=
0
;
// find the insertion location
while
(
scan
<
rear
&&
comparableElement
.
compareTo
(
list
[
scan
])
>
0
)
scan
++
;
// shift existing elements up one
for
(
int
shift
=
rear
;
shift
>
scan
;
shift
--
)
list
[
shift
]
=
list
[
shift
-
1
];
// insert element
list
[
scan
]
=
element
;
rear
++
;
modCount
++
;
}
}
Chap16/ArrayListIterator/jsjf/ArrayUnorderedList.java
Chap16/ArrayListIterator/jsjf/ArrayUnorderedList.java
package
jsjf
;
import
jsjf
.
exceptions
.
*
;
/**
* ArrayUnorderedList represents an array implementation of an unordered list.
*
* Solution to Programming Project 15.10 (full implementation)
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
ArrayUnorderedList
<
T
>
extends
ArrayList
<
T
>
implements
UnorderedListADT
<
T
>
{
/**
* Creates an empty list using the default capacity.
*/
public
ArrayUnorderedList
()
{
super
();
}
/**
* Creates an empty list using the specified capacity.
*
*
@param
initialCapacity the initial size of the list
*/
public
ArrayUnorderedList
(
int
initialCapacity
)
{
super
(
initialCapacity
);
}
/**
* Adds the specified element to the front of this list.
*
*
@param
element the element to be added to the front of the list
*/
public
void
addToFront
(
T element
)
{
if
(
size
()
==
list
.
length
)
expandCapacity
();
// shift elements up one
for
(
int
scan
=
rear
;
scan
>
0
;
scan
--
)
list
[
scan
]
=
list
[
scan
-
1
];
list
[
0
]
=
element
;
rear
++
;
modCount
++
;
}
/**
* Adds the specified element to the rear of this list.
*
*
@param
element the element to be added to the list
*/
public
void
addToRear
(
T element
)
{
if
(
size
()
==
list
.
length
)
expandCapacity
();
list
[
rear
]
=
element
;
rear
++
;
modCount
++
;
}
/**
* Adds the specified element after the specified target element.
* Throws an ElementNotFoundException if the target is not found.
*
*
@param
element the element to be added after the target element
*
@param
target the target that the element is to be added after
*/
public
void
addAfter
(
T element
,
T target
)
{
if
(
size
()
==
list
.
length
)
expandCapacity
();
int
scan
=
0
;
// find the insertion point
while
(
scan
<
rear
&&
!
target
.
equals
(
list
[
scan
]))
scan
++
;
if
(
scan
==
rear
)
throw
new
ElementNotFoundException
(
"UnorderedList"
);
scan
++
;
// shift elements up one
for
(
int
shift
=
rear
;
shift
>
scan
;
shift
--
)
list
[
shift
]
=
list
[
shift
-
1
];
// insert element
list
[
scan
]
=
element
;
rear
++
;
modCount
++
;
}
}
Chap16/ArrayListIterator/jsjf/exceptions/ElementNotFoundException.java
Chap16/ArrayListIterator/jsjf/exceptions/ElementNotFoundException.java
package
jsjf
.
exceptions
;
/**
* ElementNotFoundException represents the situation in which a target element
* is not present in a collection
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
ElementNotFoundException
extends
RuntimeException
{
/**
* Sets up this exception with an appropriate message.
*/
public
ElementNotFoundException
(
String
collection
)
{
super
(
"The target element is not in this "
+
collection
);
}
}
Chap16/ArrayListIterator/jsjf/exceptions/EmptyCollectionException.java
Chap16/ArrayListIterator/jsjf/exceptions/EmptyCollectionException.java
package
jsjf
.
exceptions
;
/**
* Represents the situation in which a collection is empty.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
EmptyCollectionException
extends
RuntimeException
{
/**
* Sets up this exception with an appropriate message.
*
@param
collection the name of the collection
*/
public
EmptyCollectionException
(
String
collection
)
{
super
(
"The "
+
collection
+
" is empty."
);
}
}
Chap16/ArrayListIterator/jsjf/exceptions/NonComparableElementException.java
Chap16/ArrayListIterator/jsjf/exceptions/NonComparableElementException.java
package
jsjf
.
exceptions
;
/**
* NonComparableElementException represents the situation in which an attempt
* is made to add an element that is not comparable to an ordered collection
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
NonComparableElementException
extends
RuntimeException
{
/**
* Sets up this exception with an appropriate message.
*
*
@param
collection the exception message to deliver
*/
public
NonComparableElementException
(
String
collection
)
{
super
(
"The "
+
collection
+
" requires Comparable elements."
);
}
}
Chap16/ArrayListIterator/jsjf/ListADT.java
Chap16/ArrayListIterator/jsjf/ListADT.java
package
jsjf
;
import
java
.
util
.
Iterator
;
/**
* ListADT defines the interface to a general list collection. Specific
* types of lists will extend this interface to complete the
* set of necessary operations.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
interface
ListADT
<
T
>
extends
Iterable
<
T
>
{
/**
* Removes and returns the first element from this list.
*
*
@return
the first element from this list
*/
public
T removeFirst
();
/**
* Removes and returns the last element from this list.
*
*
@return
the last element from this list
*/
public
T removeLast
();
/**
* Removes and returns the specified element from this list.
*
*
@param
element the element to be removed from the list
*/
public
T remove
(
T element
);
/**
* Returns a reference to the first element in this list.
*
*
@return
a reference to the first element in this list
*/
public
T first
();
/**
* Returns a reference to the last element in this list.
*
*
@return
a reference to the last element in this list
*/
public
T last
();
/**
* Returns true if this list contains the specified target element.
*
*
@param
target the target that is being sought in the list
*
@return
true if the list contains this element
*/
public
boolean
contains
(
T target
);
/**
* Returns true if this list contains no elements.
*
*
@return
true if this list contains no elements
*/
public
boolean
isEmpty
();
/**
* Returns the number of elements in this list.
*
*
@return
the integer representation of number of elements in this list
*/
public
int
size
();
/**
* Returns an iterator for the elements in this list.
*
*
@return
an iterator over the elements in this list
*/
public
Iterator
<
T
>
iterator
();
/**
* Returns a string representation of this list.
*
*
@return
a string representation of this list
*/
public
String
toString
();
}
Chap16/ArrayListIterator/jsjf/OrderedListADT.java
Chap16/ArrayListIterator/jsjf/OrderedListADT.java
package
jsjf
;
/**
* OrderedListADT defines the interface to an ordered list collection. Only
* Comparable elements are stored, kept in the order determined by
* the inherent relationship among the elements.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
interface
OrderedListADT
<
T
>
extends
ListADT
<
T
>
{
/**
* Adds the specified element to this list at the proper location
*
*
@param
element the element to be added to this list
*/
public
void
add
(
T element
);
}
Chap16/ArrayListIterator/jsjf/UnorderedListADT.java
Chap16/ArrayListIterator/jsjf/UnorderedListADT.java
package
jsjf
;
/**
* UnorderedListADT defines the interface to an unordered list collection.
* Elements are stored in any order the user desires.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
interface
UnorderedListADT
<
T
>
extends
ListADT
<
T
>
{
/**
* Adds the specified element to the front of this list.
*
*
@param
element the element to be added to the front of this list
*/
public
void
addToFront
(
T element
);
/**
* Adds the specified element to the rear of this list.
*
*
@param
element the element to be added to the rear of this list
*/
public
void
addToRear
(
T element
);
/**
* Adds the specified element after the specified target.
*
*
@param
element the element to be added after the target
*
@param
target the target is the item that the element will be added
* after
*/
public
void
addAfter
(
T element
,
T target
);
}
Chap16/LinkedListIterator/jsjf/exceptions/ElementNotFoundException.java
Chap16/LinkedListIterator/jsjf/exceptions/ElementNotFoundException.java
package
jsjf
.
exceptions
;
/**
* ElementNotFoundException represents the situation in which a target element
* is not present in a collection
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
ElementNotFoundException
extends
RuntimeException
{
/**
* Sets up this exception with an appropriate message.
*/
public
ElementNotFoundException
(
String
collection
)
{
super
(
"The target element is not in this "
+
collection
);
}
}
Chap16/LinkedListIterator/jsjf/exceptions/EmptyCollectionException.java
Chap16/LinkedListIterator/jsjf/exceptions/EmptyCollectionException.java
package
jsjf
.
exceptions
;
/**
* Represents the situation in which a collection is empty.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
EmptyCollectionException
extends
RuntimeException
{
/**
* Sets up this exception with an appropriate message.
*
@param
collection the name of the collection
*/
public
EmptyCollectionException
(
String
collection
)
{
super
(
"The "
+
collection
+
" is empty."
);
}
}
Chap16/LinkedListIterator/jsjf/exceptions/NonComparableElementException.java
Chap16/LinkedListIterator/jsjf/exceptions/NonComparableElementException.java
package
jsjf
.
exceptions
;
/**
* NonComparableElementException represents the situation in which an attempt
* is made to add an element that is not comparable to an ordered collection
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
NonComparableElementException
extends
RuntimeException
{
/**
* Sets up this exception with an appropriate message.
*
*
@param
collection the exception message to deliver
*/
public
NonComparableElementException
(
String
collection
)
{
super
(
"The "
+
collection
+
" requires Comparable elements."
);
}
}
Chap16/LinkedListIterator/jsjf/LinearNode.java
Chap16/LinkedListIterator/jsjf/LinearNode.java
package
jsjf
;
/**
* LinearNode represents a node in a linked list.
*
*
@author
Java Foundations
*
@version
4.0
*/
public
class
LinearNode
<
E
>
{
private
LinearNode
<
E
>
next
;
private
E element
;
/**
* Creates an empty node.
*/
public
LinearNode
()
{
next
=
null
;
element
=
null
;
}
/**
* Creates a node storing the specified element.
*
*
@param
elem the element to be stored within the new node
*/
public
LinearNode
(
E elem
)
{
next
=
null
;
element
=
elem
;
}
/**
* Returns the node that follows this one.
*
*
@return
the node that follows the current one
*/
public
LinearNode
<
E
>
getNext
()
{
return
next
;
}
/**
* Sets the node that follows this one.
*
*
@param
node the node to be set to follow the current one
*/
public
void
setNext
(
LinearNode
<
E
>
node
)
{
next
=
node
;
}
/**
* Returns the element stored in this node.
*
*
@return
the element stored in this node
*/
public
E getElement
()
{
return
element
;
}
/**
* Sets the element stored in this node.
*
*
@param
elem the element to be stored in this node
*/
public
void
setElement
(
E elem
)
{
element
=
elem
;
}
}
Chap16/LinkedListIterator/jsjf/LinkedList.java
Chap16/LinkedListIterator/jsjf/LinkedList.java
package
jsjf
;
import
jsjf
.
exceptions
.
*
;
import
java
.
util
.
*
;
/**
* LinkedList represents a linked implementation of a list.
*
* Solution to Programming Project 15.11 (full implementation)
*
*
@author
Java Foundations
*
@version
4.0
*/
public
abstract
class
LinkedList
<
T
>
implements
ListADT
<
T
>
,
Iterable
<
T
>
{
protected
int
count
;
protected
LinearNode
<
T
>
head
,
tail
;
protected
int
modCount
;
/**
* Creates an empty list.
*/
public
LinkedList
()
{
count
=
0
;
head
=
tail
=
null
;
modCount
=
0
;
}
/**
* Removes the first element in this list and returns a reference
* to it. Throws an EmptyCollectionException if the list is empty.
*
*
@return
a reference to the first element of this list
*
@throws
EmptyCollectionException if the list is empty
*/
public
T removeFirst
()
throws
EmptyCollectionException
{
if
(
isEmpty
())
throw
new
EmptyCollectionException
(
"LinkedList"
);
LinearNode
<
T
>
result
=
head
;
head
=
head
.
getNext
();
if
(
head
==
null
)
tail
=
null
;
count
--
;
modCount
++
;
return
result
.
getElement
();
}
/**
* Removes the last element in this list and returns a reference
* to it. Throws an EmptyCollectionException if the list is empty.
*
*
@return
the last element in this list
*
@throws
EmptyCollectionException if the list is empty
*/
public
T removeLast
()
throws
EmptyCollectionException
{
if
(
isEmpty
())
throw
new
EmptyCollectionException
(
"LinkedList"
);
LinearNode
<
T
>
previous
=
null
;
LinearNode
<
T
>
current
=
head
;
while
(
current
.
getNext
()
!=
null
)
{
previous
=
current
;
current
=
current
.
getNext
();
}
LinearNode
<
T
>
result
=
tail
;
tail
=
previous
;
if
(
tail
==
null
)
// only one element in list
head
=
null
;
else
tail
.
setNext
(
null
);
count
--
;
modCount
++
;
return
result
.
getElement
();
}
/**
* Removes the first instance of the specified element from this
* list and returns a reference to it. Throws an EmptyCollectionException
* if the list is empty. Throws a ElementNotFoundException if the
* specified element is not found in the list.
*
*
@param
targetElement the element to be removed from the list
*
@return
a reference to the removed element
*
@throws
EmptyCollectionException if the list is empty
*
@throws
ElementNotFoundException if the target element is not found
*/
public
T remove
(
T targetElement
)
throws
EmptyCollectionException
,
ElementNotFoundException
{
if
(
isEmpty
())
throw
new
EmptyCollectionException
(
"LinkedList"
);
boolean
found
=
false
;
LinearNode
<
T
>
previous
=
null
;
LinearNode
<
T
>
current
=
head
;
while
(
current
!=
null
&&
!
found
)
if
(
targetElement
.
equals
(
current
.
getElement
()))
found
=
true
;
else
{
previous
=
current
;
current
=
current
.
getNext
();
}
if
(
!
found
)
throw
new
ElementNotFoundException
(
"LinkedList"
);
if
(
size
()
==
1
)
// only one element in the list
head
=
tail
=
null
;
else
if
(
current
.
equals
(
head
))
// target is at the head
head
=
current
.
getNext
();
else
if
(
current
.
equals
(
tail
))
// target is at the tail
{
tail
=
previous
;
tail
.
setNext
(
null
);
}
else
// target is in the middle
previous
.
setNext
(
current
.
getNext
());
count
--
;
modCount
++
;
return
current
.
getElement
();
}
/**
* Returns the first element in this list without removing it.
*
*
@return
the first element in this list
*
@throws
EmptyCollectionException if the list is empty
*/
public
T first
()
throws
EmptyCollectionException
{
if
(
isEmpty
())
throw
new
EmptyCollectionException
(
"LinkedList"
);
return
head
.
getElement
();
}
/**
* Returns the last element in this list without removing it.
*
*
@return
the last element in this list
*
@throws
EmptyCollectionException if the list is empty
*/
public
T last
()
throws
EmptyCollectionException
{
if
(
isEmpty
())
throw
new
EmptyCollectionException
(
"LinkedList"
);
return
tail
.
getElement
();
}
/**
* Returns true if the specified element is found in this list and
* false otherwise. Throws an EmptyCollectionException if the list
* is empty.
*
*
@param
targetElement the element that is sought in the list
*
@return
true if the element is found in this list
*
@throws
EmptyCollectionException if the list is empty
*/
public
boolean
contains
(
T targetElement
)
throws
EmptyCollectionException
{
if
(
isEmpty
())
throw
new
EmptyCollectionException
(
"LinkedList"
);
boolean
found
=
false
;
LinearNode
<
T
>
current
=
head
;
while
(
current
!=
null
&&
!
found
)
if
(
targetElement
.
equals
(
current
.
getElement
()))
found
=
true
;
else
current
=
current
.
getNext
();
return
found
;
}
/**
* Returns true if this list is empty and false otherwise.
*
*
@return
true if the list is empty, false otherwise
*/
public
boolean
isEmpty
()
{
return
(
count
==
0
);
}
/**
* Returns the number of elements in this list.
*
*
@return
the number of elements in the list
*/
public
int
size
()
{
return
count
;
}
/**
* Returns a string representation of this list.
*
*
@return
a string representation of the list
*/
public
String
toString
()
{
LinearNode
<
T
>
current
=
head
;
String
result
=
""
;
while
(
current
!=
null
)
{
result
=
result
+
current
.
getElement
()
+
"\n"
;
current
=
current
.
getNext
();
}
return
result
;
}
/**
* Returns an iterator for the elements in this list.
*
*
@return
an iterator over the elements of the list
*/
public
Iterator
<
T
>
iterator
()
{
return
new
LinkedListIterator
();
}
/**
* LinkedIterator represents an iterator for a linked list of linear nodes.
*/
private
class
LinkedListIterator
implements
Iterator
<
T
>
{
private
int
iteratorModCount
;
// the number of elements in the collection
private
LinearNode
<
T
>
current
;
// the current position
/**
* Sets up this iterator using the specified items.
*
*
@param
collection the collection the iterator will move over
*
@param
size the integer size of the collection
*/
public
LinkedListIterator
()
{
current
=
head
;
iteratorModCount
=
modCount
;
}
/**
* Returns true if this iterator has at least one more element
* to deliver in the iteration.
*
*
@return
true if this iterator has at least one more element to deliver
* in the iteration
*
@throws
ConcurrentModificationException if the collection has changed
* while the iterator is in use
*/
public
boolean
hasNext
()
throws
ConcurrentModificationException
{
if
(
iteratorModCount
!=
modCount
)
throw
new
ConcurrentModificationException
();
return
(
current
!=
null
);
}
/**
* Returns the next element in the iteration. If there are no
* more elements in this iteration, a NoSuchElementException is
* thrown.
*
*
@return
the next element in the iteration
*
@throws
NoSuchElementException if the iterator is empty
*/
public
T next
()
throws
ConcurrentModificationException
{
if
(
!
hasNext
())
throw
new
NoSuchElementException
();
T result
=
current
.
getElement
();
current
=
current
.
getNext
();