CHAPTER 9. LINKED DATA STRUCTURES AND RECURSION
467
there are also techniques for examining the tree and detecting certain types of programming
errors, such as an attempt to reference a local variable before it has been assigned a value. (The
Java compiler, of course, will reject the program if it contains such an error.) It’s also possible
to manipulate the tree to optimize the program. In optimization, the tree is transformed to
make the program more efficient before the code is generated.
And so we are back where we started inChapter 1, looking at programming languages,
compilers, and machine language. But looking at them, I hope, with a lot more understanding
and a much wider perspective.
Pdf password encryption - C# PDF Digital Signature Library: add, remove, update PDF digital signatures in C#.net, ASP.NET, MVC, WPF
Help to Improve the Security of Your PDF File by Adding Digital Signatures
create secure pdf online; pdf security options
Pdf password encryption - VB.NET PDF Digital Signature Library: add, remove, update PDF digital signatures in vb.net, ASP.NET, MVC, WPF
Guide VB.NET Programmers to Improve the Security of Your PDF File by Adding Digital Signatures
convert locked pdf to word doc; decrypt pdf password online
Exercises
468
Exercises for Chapter 9
1. In many textbooks, the first examples of recursion are the mathematical functions factorial
(solution)
and fibonacci. These functions are defined for non-negative integers using the following
recursive formulas:
factorial(0) = 1
factorial(N) = N*factorial(N-1)
for N > 0
fibonacci(0) = 1
fibonacci(1) = 1
fibonacci(N) = fibonacci(N-1) + fibonacci(N-2)
for N > 1
Write recursive functions to compute factorial(N) and fibonacci(N) for a given non-
negative integer N, and write a main() routine to test your functions.
(In fact, factorial and fibonacci are really not very good examples of recursion, since
the most natural way to compute them is to use simple for loops. Furthermore, fibonacci
is a particularly bad example, since the natural recursive approach to computing this
function is extremely inefficient.)
2. Exercise 7.6 asked you to read a file, make an alphabetical list of all the words that occur
(solution)
in the file, and write the list to another file. In that exercise, you were asked to use an
ArrayList<String> to store the words. Write a new version of the same program that stores
the words in a binary sort tree instead of in an arraylist. You can use the binary sort tree
routines fromSortTreeDemo.java, which was discussed inSubsection9.4.2.
3. Suppose that linked lists of integers are made from objects belonging to the class
(solution)
class ListNode {
int item;
// An item in the list.
ListNode next; // Pointer to the next node in the list.
}
Write a subroutine that will make a copy of a list, with the order of the items of the list
reversed. The subroutine should have a parameter of type ListNode, and it should return
avalue of type ListNode. The original list should not be modified.
You should also write a main() routine to test your subroutine.
4.Subsection9.4.1 explains how to use recursion to print out the items in a binary tree in
(solution)
various orders. That section also notes that a non-recursive subroutine can be used to
print the items, provided that a stack or queue is used as an auxiliary data structure.
Assuming that a queue is used, here is an algorithm for such a subroutine:
Add the root node to an empty queue
while the queue is not empty:
Get a node from the queue
Print the item in the node
if node.left is not null:
add it to the queue
if node.right is not null:
add it to the queue
C# PDF Password Library: add, remove, edit PDF file password in C#
outputFilePath = Program.RootPath + "\\" 3_pw_a.pdf"; // Create a setting object with user password which is Hello World"); // Set encryption level to AES
change pdf document security properties; change security on pdf
Online Remove password from protected PDF file
Find your password-protected PDF and upload it. If there is no strong encryption on your file, it will be unlocked and ready to download within seconds.
secure pdf remove; create pdf security
Exercises
469
Write a subroutine that implements this algorithm, and write a program to test the sub-
routine. Note that you will need a queue of TreeNodes, so you will need to write a class
to represent such queues.
(Note that the order in which items are printed by this algorithm is different from all
three of the orders considered inSubsection9.4.1.)
5. InSubsection9.4.2, I say that “if the [binary sort] tree is created by inserting items in a
(solution)
random order, there is a high probability that the tree is approximately balanced.” For
this exercise, you will do an experiment to test whether that is true.
The depth of a node in a binary tree is the length of the path from the root of the tree
to that node. That is, the root has depth 0, its children have depth 1, its grandchildren
have depth 2, and so on. In a balanced tree, all the leaves in the tree are about the same
depth. For example, in a perfectly balanced tree with 1023 nodes, all the leaves are at
depth 9. In an approximately balanced tree with 1023 nodes, the average depth of all the
leaves should be not too much bigger than 9.
On the other hand, even if the tree is approximately balanced, there might be a few
leaves that have much larger depth than the average, so we might also want to look at the
maximum depth among all the leaves in a tree.
For this exercise, you should create a random binary sort tree with 1023 nodes. The
items in the tree can be real numbers, and you can create the tree by generating 1023
random real numbers and inserting them into the tree, using the usual treeInsert()
method for binary sort trees. Once you have the tree, you should compute and output the
average depth of all the leaves in the tree and the maximum depth of all the leaves. To
do this, you will need three recursive subroutines: one to count the leaves, one to find the
sum of the depths of all the leaves, and one to find the maximum depth. The latter two
subroutines should have an int-valued parameter, depth, that tells how deep in the tree
you’ve gone. When you call this routine from the main program, the depth parameter is
0; when you call the routine recursively, the parameter increases by 1.
6. The parsing programs in Section 9.5 work with expressions made up of numbers and
(solution)
operators. We can make things a little more interesting by allowing the variable “x” to
occur. This would allow expression such as “3*(x-1)*(x+1)”, for example. Make a new
version of the sample programSimpleParser3.java that can work with such expressions.
In your program, the main() routine can’t simply print the value of the expression, since
the value of the expression now depends on the value of x. Instead, it should print the
value of the expression for x=0, x=1, x=2, and x=3.
The original program will have to be modified in several other ways. Currently, the
program uses classes ConstNode, BinOpNode, and UnaryMinusNode to represent nodes
in an expression tree. Since expressions can now include x, you will need a new class,
VariableNode, to represent an occurrence of x in the expression.
In the original program, each of the node classes has an instance method,
“double value()”, which returns the value of the node. But in your program, the
value can depend on x, so you should replace this method with one of the form
“double value(double xValue)”, where the parameter xValue is the value of x.
Finally, the parsing subroutines in your program will have to take into account the
fact that expressions can contain x. There is just one small change in the BNF rules for
the expressions: A <factor> is allowed to be the variable x:
<factor> ::= <number> | <x-variable> | "(" <expression> ")"
VB.NET PDF Password Library: add, remove, edit PDF file password
String = Program.RootPath + "\\" 3_pw_a.pdf" ' Create a setting object with user password which is PasswordSetting("Hello World") ' Set encryption level to
add security to pdf document; secure pdf file
C# PDF File Permission Library: add, remove, update PDF file
outputFilePath = Program.RootPath + "\\" 3_pw_a.pdf"; // Create a setting object with user password "Hello World". Hello World"); // Set encryption level to
copy from locked pdf; creating secure pdf files
Exercises
470
where <x-variable> can be either a lower case or an upper case “X”. This change in the
BNF requires a change in the factorTree() subroutine.
7. This exercise builds on the previous exercise, Exercise 9.6. To understand it, you should
(solution)
have some background in Calculus. The derivative of an expression that involves the
variable x can be defined by a few recursive rules:
•The derivative of a constant is 0.
•The derivative of x is 1.
•If A is an expression, let dA be the derivative of A. Then the derivative of -A is -dA.
•If A and B are expressions, let dA be the derivative of A and let dB be the derivative
of B. Then the derivative of A+B is dA+dB.
•The derivative of A-B is dA-dB.
•The derivative of A*B is A*dB + B*dA.
•The derivative of A/B is (B*dA - A*dB) / (B*B).
For this exercise, you should modify your program from the previous exercise so that
it can compute the derivative of an expression. You can do this by adding a derivative-
computing method to each of the node classes. First, add another abstract method to the
ExpNode class:
abstract ExpNode derivative();
Then implement this methodin eachof the four subclasses of ExpNode. Allthe information
that you need is in the rules given above. In your main program, instead of printing the
stack operations for the original expression, you should print out the stack operations
that define the derivative. Note that the formula that you get for the derivative can be
much more complicated than it needs to be. For example, the derivative of 3*x+1 will be
computed as (3*1+0*x)+0. This is correct, even though it’s kind of ugly, and it would be
nice for it to be simplified. However, simplifying expressions is not easy.
As an alternative to printing out stack operations, you might want to print the deriva-
tive as afully parenthesized expression. You can do this by adding a printInfix() routine
to each node class. It would be nice to leave out unnecessary parentheses, but again, the
problem of deciding which parentheses can be left out without altering the meaning of the
expression is a fairly difficult one, which I don’t advise you to attempt.
(There is one curious thing that happens here: If you apply the rules, as given, to an
expression tree, the result is no longer a tree, since the same subexpression can occur at
multiple points in the derivative. For example, if you build a node to represent B*B by
saying “new BinOpNode(’*’,B,B)”, then the left and right children of the new node are
actually the same node! This is not allowed in a tree. However, the difference is harmless
in this case since, like a tree, the structure that you get has no loops in it. Loops, on the
other hand, would be a disaster in most of the recursive tree-processing subroutines that
we have written, since it would lead to infinite recursion. The type of structure that is
built by the derivative functions is technically referred to as a directed acyclic graph.)
VB.NET PDF File Permission Library: add, remove, update PDF file
As String = Program.RootPath + "\\" 3_pw_a.pdf" ' Create a password setting object with user password "Hello World Hello World") ' Set encryption level to
pdf password encryption; decrypt pdf password
VB.NET PDF File Compress Library: Compress reduce PDF size in vb.
NET class. Also able to uncompress PDF file in VB.NET programs. Support PDF encryption in VB.NET class applications. A professional
pdf encryption; create encrypted pdf
Quiz
471
Quiz on Chapter 9
(answers)
1. Explain what is meant by a recursive subroutine.
2. Consider the following subroutine:
static void printStuff(int level) {
if (level == 0) {
System.out.print("*");
}
else {
System.out.print("[");
printStuff(level - 1);
System.out.print(",");
printStuff(level - 1);
System.out.println("]");
}
}
Show the output that would be produced by the subroutine calls printStuff(0),
printStuff(1), printStuff(2), and printStuff(3).
3. Suppose that a linked list is formed from objects that belong to the class
class ListNode {
int item;
// An item in the list.
ListNode next; // Pointer to next item in the list.
}
Write a subroutine that will count the number of zeros that occur in a given linked list
of ints. The subroutine should have a parameter of type ListNode and should return a
value of type int.
4. What are the three operations on a stack?
5. What is the basic difference between a stack and a queue?
6. What is an activation record? What role does a stack of activation records play in a
computer?
7. Suppose that a binary tree of integers is formed from objects belonging to the class
class TreeNode {
int item;
// One item in the tree.
TreeNode left; // Pointer to the left subtree.
TreeNode right; // Pointer to the right subtree.
}
Write a recursive subroutine that will find the sum of all the nodes in the tree. Your
subroutine should have a parameter of type TreeNode, and it should return a value of
type int.
8. What is a postorder traversal of a binary tree?
9. Suppose that a <multilist> is defined by the BNF rule
VB.NET Word: How to Convert Word Document to PNG Image Format in
and document formats, including converting Word to PDF in VB protection by utilizing the modern Advanced Encryption Standard that converts a password to a
create pdf the security level is set to high; creating a secure pdf document
C# Image: How to Annotate Image with Freehand Line in .NET Project
Tutorials on how to add freehand line objects to PDF, Word and TIFF SDK; Protect sensitive image information with redaction and encryption annotation objects;
pdf password unlock; change pdf document security
Quiz
472
<multilist> ::= <word> | "(" [ <multilist> ]... ")"
where a <word> can be any sequence of letters. Give five different <multilist>’s that
can be generated by this rule. (This rule, by the way, is almost the entire syntax of
the programming language LISP! LISP is known for its simple syntax and its elegant and
powerful semantics.)
10. Explain what is meant by parsing a computer program.
C# Image: C#.NET Code to Add HotSpot Annotation on Images
Protect sensitive information with powerful redaction and encryption annotation objects to provide powerful & profession imaging controls, PDF document, image
pdf security remover; convert secure pdf to word
C# Image: Add Watermark to Images Within RasterEdge .NET Imaging
powerful and reliable color reduction products, image encryption decryption, and even to provide powerful & profession imaging controls, PDF document, image to
pdf unlock; change security settings on pdf
Chapter 10
Generic Programming and
Collection Classes
H
ow to avoid reinventing the wheel? Many data structures and algorithms, such as
those fromChapter9, have been studied, programmed, and re-programmed by generations of
computer science students. This is a valuable learning experience. Unfortunately, they have
also been programmed and re-programmed by generations of working computer professionals,
taking up time that could be devoted to new, more creative work. A programmer who needs
alist or a binary tree shouldn’t have to re-code these data structures from scratch. They are
well-understood and have been programmed thousands of times before. The problem is how to
make pre-written, robust data structures available to programmers. In this chapter, we’ll look
at Java’s attempt to address this problem.
10.1 Generic Programming
G
eneric programming refers to writing code that will work for many types of data. We
(online)
encountered the term in Section 7.3, where we looked at dynamic arrays of integers. The
source code presented there for working with dynamic arrays of integers works only for data
of type int. But the source code for dynamic arrays of double, String, JButton, or any other
type would be almost identical, except for the substitution of one type name for another. It
seems silly to write essentially the same code over and over. As we saw inSubsection7.3.3,
Java goes some distance towards solving this problem by providing the ArrayList class. An
ArrayList is essentially a dynamic array of values of type Object. Since every class is a subclass
of Object, objects of any type can be stored in an ArrayList. Java goes even further by providing
“parameterized types,” which were introduced in Subsection 7.3.4. There we saw that the
ArrayList type can be parameterized, as in “ArrayList<String>”, to limit the values that can
be stored in the list to objects of a specified type. Parameterized types extend Java’s basic
philosophy of type-safe programming to generic programming.
The ArrayList class is just one of several standard classes that are used for generic pro-
gramming in Java. We will spend the next few sections looking at these classes and how they
are used, and we’ll see that there are also generic methods and generic interfaces (seeSubsec-
tion 5.7.1). Alltheclassesandinterfacesdiscussedinthesesectionsaredefinedinthepackage
java.util, and you will need an import statement at the beginning of your program to get
access to them. (Before you start putting “import java.util.*” at the beginning of every
program, you should know that some things in java.util have names that are the same as
473
CHAPTER 10. GENERIC PROGRAMMING AND COLLECTION CLASSES
474
things in other packages. For example, both java.util.List and java.awt.List exist, so it
is often better to import the individual classes that you need.)
In the final section of this chapter, we will see that it is possible to define new generic classes,
interfaces, and methods. Until then, we will stick to using the generics that are predefined in
Java’s standard library.
It is no easy task to design a library for generic programming. Java’s solution has many
nice features but is certainly not the only possible approach. It is almost certainly not the
best, and has a few features that in my opinion can only be called bizarre, but in the context
of the overall design of Java, it might be close to optimal. To get some perspective on generic
programming in general, it might be useful to look very briefly at generic programming in two
other languages.
10.1.1 Generic Programming in Smalltalk
Smalltalk was one of the very first object-oriented programminglanguages. It is stillused today,
although its use is not very common. It has not achieved anything like the popularity of Java
or C++, but it is the source of many ideas used in these languages. In Smalltalk, essentially
all programming is generic, because of two basic properties of the language.
First of all, variables in Smalltalk are typeless. A data value has a type, such as integer or
string, but variables do not have types. Any variable can hold data of any type. Parameters
are also typeless, so a subroutine can be applied to parameter values of any type. Similarly,
adata structure can hold data values of any type. For example, once you’ve defined a binary
tree data structure in SmallTalk, you can use it for binary trees of integers or strings or dates
or data of any other type. There is simply no need to write new code for each data type.
Secondly, all data values are objects, and all operations on objects are defined by methods
in a class. This is true even for types that are “primitive” in Java, such as integers. When the
“+” operator is used to add two integers, the operation is performed by calling a method in the
integer class. When you define a new class, you can define a “+” operator, and you will then
be able to add objects belonging to that class by saying “a + b” just as if you were adding
numbers. Now, suppose that you write a subroutine that uses the “+” operator to add up the
items in a list. The subroutine can be applied to a list of integers, but it can also be applied,
automatically, to any other data type for which “+” is defined. Similarly, a subroutine that
uses the “<" operator to sort a list can be applied to lists containing any type of data for which
“<” is defined. There is no need to write a different sorting subroutine for each type of data.
Put these two features together and you have a language where data structures and al-
gorithms will work for any type of data for which they make sense, that is, for which the
appropriate operations are defined. This is real generic programming. This might sound pretty
good, and you might be asking yourself why all programming languages don’t work this way.
This type of freedom makes it easier to write programs, but unfortunately it makes it harder
to write programs that are correct and robust (seeChapter8). Once you have a data structure
that can contain data of any type, it becomes hard to ensure that it only holds the type of
data that you want it to hold. If you have a subroutine that can sort any type of data, it’s
hard to ensure that it will only be applied to data for which the “<” operator is defined. More
particularly, there is no way for a compiler to ensure these things. The problem will only show
up at run time when an attempt is made to apply some operation to a data type for which it
is not defined, and the program will crash.
CHAPTER 10. GENERIC PROGRAMMING AND COLLECTION CLASSES
475
10.1.2 Generic Programming in C++
Unlike Smalltalk, C++ is a very strongly typed language, even more so than Java. Every
variable has a type, and can only hold data values of that type. This means that the kind
of generic programming that is used in Smalltalk is impossible in C++. Furthermore, C++
does not have anything corresponding to Java’s Object class. That is, there is no class that
is a superclass of all other classes. This means that C++ can’t use Java’s style of generic
programming with non-parameterized generic types either. Nevertheless, C++ has a powerful
and flexible system of generic programming. It is made possible by a language feature known
as templates. In C++, instead of writing a different sorting subroutine for each type of data,
you can write a single subroutine template. The template is not a subroutine; it’s more like a
factory for making subroutines. We can look at an example, since the syntax of C++ is very
similar to Java’s:
template<class ItemType>
void sort( ItemType A[], int count ) {
// Sort items in the array, A, into increasing order.
// The items in positions 0, 1, 2, ..., (count-1) are sorted.
// The algorithm that is used here is selection sort.
for (int i = count-1; i > 0; i--) {
int position
of
max = 0;
for (int j = 1; j <= count ; j++)
if ( A[j] > A[position
of
max] )
position
of
max = j;
ItemType temp = A[count];
A[count] = A[position
of
max];
A[position
of
max] = temp;
}
}
This piece ofcode defines a subroutine template. If youremovethe first line, “template<class
ItemType>”, and substitute the word “int” for the word“ItemType” in the rest of the template,
you get a subroutine for sorting arrays of ints. (Even though it says “class ItemType”, you
can actually substitute any type for ItemType, including the primitive types.) If you substitute
“string” for “ItemType”, you get a subroutine for sorting arrays of strings. This is pretty much
what the compiler does with the template. If your program says “sort(list,10)” where list
is an array of ints, the compiler uses the template to generate a subroutine for sorting arrays
of ints. If you say “sort(cards,10)” where cards is an array of objects of type Card, then the
compiler generates a subroutine for sorting arrays of Cards. At least, it tries to. The template
uses the “>” operator to compare values. If this operator is defined for values of type Card, then
the compiler will successfully use the template to generate a subroutine for sorting cards. If
“>” is not defined for Cards, then the compiler will fail—but this will happen at compile time,
not, as in Smalltalk, at run time where it would make the program crash.
In addition to subroutine templates, C++ also has templates for making classes. If you
write a template for a binary tree class, you can use it to generate classes for binary trees of
ints, binary trees of strings, binary trees of dates, and so on—all from one template. The most
recent version of C++ comes with a large number of pre-written templates called the Standard
Template Library or STL. The STL is quite complex. Many people would say that it’s much
too complex. But it is also one of the most interesting features of C++.
CHAPTER 10. GENERIC PROGRAMMING AND COLLECTION CLASSES
476
10.1.3 Generic Programming in Java
Java’s generic programming features have gone through several stages of development. The
original version of Java had just a few generic data structure classes, such as Vector, that could
hold values of type Object. Java version 1.2 introduced a much larger group of generics that
followed the same basic model. These generic classes and interfaces as a group are known as
the Java Collection Framework. The ArrayList class is part of the Collection Framework.
The original Collection Framework was closer in spirit to Smalltalk than it was to C++, since
adata structure designed to hold Objects can be used with objects of any type. Unfortunately,
as in Smalltalk, the result is a category of errors that show up only at run time, rather than
at compile time. If a programmer assumes that all the items in a data structure are strings
and tries to process those items as strings, a run-time error will occur if other types of data
have inadvertently been added to the data structure. In Java, the error will most likely occur
when the program retrieves an Object from the data structure and tries to type-cast it to type
String. If the object is not actually of type String, the illegal type-cast will throw an error of
type ClassCastException.
Java 5.0 introduced parameterized types, such as ArrayList<String>. This made it possible to
create generic data structures that can be type-checked at compile time rather than at run time.
With these data structures, type-casting is not necessary, so ClassCastExceptions are avoided.
The compiler will detect any attempt to add an object of the wrong type to the data structure;
it will report a syntax error and will refuse to compile the program. In Java 5.0, all of the
classes and interfaces in the Collection Framework, and even some classes that are not part of
that framework, have been parameterized. Java’s parameterized classes are similar to template
classes in C++ (although the implementation is very different), and their introduction moves
Java’s generic programming model closer to C++ and farther from Smalltalk. In this chapter,
Iwill use the parameterized types almost exclusively, but you should remember that their use
is not mandatory. It is still legal to use a parameterized class as a non-parameterized type,
such as a plain ArrayList.
Note that there is a significant difference between parameterized classes in Java and tem-
plate classes in C++. A template class in C++ is not really a class at all—it’s a kind of factory
for generating classes. Every time the template is used with a new type, a new compiled class
is created. With a Java parameterized class, there is only one compiled class file. For example,
there is only one compiled class file, ArrayList.class, for the parameterized class ArrayList.
The parameterized types ArrayList<String> and ArrayList<Integer> both use the same compiled
class file, as does the plain ArrayList type. The type parameter—String or Integer—just tells the
compiler to limit the type of object that can be stored in the data structure. The type parame-
ter has no effect at run time and is not even known at run time. The type information is said to
be “erased” at run time. This type erasure introduces a certain amount of weirdness. For ex-
ample, you can’t test “if (list instanceof ArrayList<String>)” because the instanceof
operator is evaluated at run time, and at run time only the plain ArrayList exists. Even worse,
you can’t create an array that has base type ArrayList<String> by using the new operator, as in
“new ArrayList<String>[N]”. This is because the new operator is evaluated at run time, and
at run time there is no such thing as “ArrayList<String>”; only the non-parameterized type
ArrayList exists at run time.
Fortunately, most programmers don’t have to deal with such problems, since they turn up
only in fairly advanced programming. Most people who use the Java Collection Framework will
not encounter them, and they will get the benefits of type-safe generic programming with little
difficulty.
Documents you may be interested
Documents you may be interested