Binary search trees - Data Structures and Problem Solving Using Java - page 768

19.36 Implement TreeSet method descendingIterator , which returns an iter-
ator that views items in the set in decreasing order.
19.37 Add the headSet , subSet , and tailSet methods to the TreeSet class. The
behavior of these methods is specified in the Java API documentation.
19.38 List method subList ( from , to ) returns a view of the list ranging
from positions from , inclusive, to to , exclusive. Add subList to the
ArrayList implementation in Chapter 15 (you can either modify
weiss

. util . ArrayList or extend it in another package, or extend

. util . ArrayList ). In the Java library, subList is written in terms
of the List interface, but write yours in terms of ArrayList . You will
need to define a nested class SubList that extends ArrayList , and have
subList return a reference to a new instance of SubList . To keep
matters simple, have SubList maintain a reference to the primary
ArrayList , store the size of the sublist, and store the offset into the
primary ArrayList . You can also have all the mutators in the SubList
throw an exception, so the returned sublist is in effect immutable.
Your SubList class must itself provide an inner SubListIterator class
that implements weiss

java

ListIterator . Test your code on the
method in Figure 19.89. Observe that sublists can create sublists,
that all refer to smaller portions of the same primary ArrayList .
What is the running time of your code?

.

util

.

Use the subList method that you wrote to implement the recursive
maximum contiguous subsequence sum algorithm in Figure 7.20 for
ArrayList s. Use iterators on the two sublists to handle the two loops.
Note that as of Java 6, the implementation will be fairly slow if you

19.39

1 public static Random r = new Random( );
2
3 public static long sum( ArrayList<Integer> arr )
4 {
5 if( arr.size( ) == 0 )
6 return 0;
7 else
8 {
9 int idx = r.nextInt( arr.size( ) );
10
11 return arr.get( idx ) +
12 sum( arr.subList( 0, idx ) ) +
13 sum( arr.subList( idx + 1, arr.size( ) ) );
14 }
15 }

figure 19.89
Recursion and array
sublists. An example
for Exercise 19.38.