archive-edu.com » EDU » H » HWS.EDU

Total: 727

Choose link from "Titles, links and description words view":

Or switch to "Titles and links view".
  • Javanotes 7.0, Section 8.2 -- Writing Correct Programs
    where a solution is computed and printed we know that the preconditions are fulfilled In the other parts we know that one of the preconditions fails to hold In any case the program is correct System out println Enter your values for A B and C System out print A A TextIO getlnDouble System out print B B TextIO getlnDouble System out print C C TextIO getlnDouble if A 0 B B 4 A C 0 disc B B 4 A C x B Math sqrt disc 2 A System out println A solution of A X X B X C 0 is x else if A 0 System out println The value of A cannot be zero else System out println Since B B 4 A C is less than zero the System out println equation A X X B X C 0 has no solution Whenever you write a program it s a good idea to watch out for preconditions and think about how your program handles them Often a precondition can offer a clue about how to write the program For example every array reference such as A i has a precondition The index must be within the range of legal indices for the array For A i the precondition is that 0 i A length The computer will check this condition when it evaluates A i and if the condition is not satisfied the program will be terminated In order to avoid this you need to make sure that the index has a legal value There is actually another precondition namely that A is not null but let s leave that aside for the moment Consider the following code which searches for the number x in the array A and sets the value of i to be the index of the array element that contains x i 0 while A i x i As this program segment stands it has a precondition namely that x is actually in the array If this precondition is satisfied then the loop will end when A i x That is the value of i when the loop ends will be the position of x in the array However if x is not in the array then the value of i will just keep increasing until it is equal to A length At that time the reference to A i is illegal and the program will be terminated To avoid this we can add a test to make sure that the precondition for referring to A i is satisfied i 0 while i A length A i x i Now the loop will definitely end After it ends i will satisfy either i A length or A i x An if statement can be used after the loop to test which of these conditions caused the loop to end i 0 while i A length A i x i if i A length System out println x is not in the array else System out println x is in position i 8 2 2 Robust Handling of Input One place where correctness and robustness are important and especially difficult is in the processing of input data whether that data is typed in by the user read from a file or received over a network Files and networking will be covered in Chapter 11 which will make essential use of material that will be covered in the next section of this chapter For now let s look at an example of processing user input Examples in this textbook use my TextIO class for reading input from the user This class has built in error handling For example the function TextIO getDouble is guaranteed to return a legal value of type double If the user types an illegal value then TextIO will ask the user to re enter their response your program never sees the illegal value However this approach can be clumsy and unsatisfactory especially when the user is entering complex data In the following example I ll do my own error checking Sometimes it s useful to be able to look ahead at what s coming up in the input without actually reading it For example a program might need to know whether the next item in the input is a number or a word For this purpose the TextIO class includes the function TextIO peek This function returns a char which is the next character in the user s input but it does not actually read that character If the next thing in the input is an end of line then TextIO peek returns the new line character n Often what we really need to know is the next non blank character in the user s input Before we can test this we need to skip past any spaces and tabs Here is a function that does this It uses TextIO peek to look ahead and it reads characters until the next character in the input is either an end of line or some non blank character The function TextIO getAnyChar reads and returns the next character in the user s input even if that character is a space By contrast the more common TextIO getChar would skip any blanks and then read and return the next non blank character We can t use TextIO getChar here since the object is to skip the blanks without reading the next non blank character Reads past any blanks and tabs in the input Postcondition The next character in the input is an end of line or a non blank character static void skipBlanks char ch ch TextIO peek while ch ch t Next character is a space or tab read it and look at the character that follows it ch TextIO getAnyChar ch TextIO peek end skipBlanks In fact this operation is so common that it is built into TextIO The method TextIO skipBlanks does essentially the same thing as the skipBlanks

    Original URL path: http://math.hws.edu/javanotes/c8/s2.html (2016-02-07)
    Open archived version from archive


  • Javanotes 7.0, Section 8.3 -- Exceptions and try..catch
    be returned by e getMessage And the method e printStackTrace writes a stack trace to standard output that tells which subroutines were active when the exception occurred A stack trace can be very useful when you are trying to determine the cause of the problem Note that if an exception is not caught by the program then the default response to the exception prints the stack trace to standard output 8 3 2 The try Statement To catch exceptions in a Java program you need a try statement We have been using such statements since Section 3 7 but the full syntax of the try statement is more complicated than what was presented there The try statements that we have used so far had a syntax similar to the following example try double determinant M 0 0 M 1 1 M 0 1 M 1 0 System out println The determinant of M is determinant catch ArrayIndexOutOfBoundsException e System out println M is the wrong size to have a determinant e printStackTrace Here the computer tries to execute the block of statements following the word try If no exception occurs during the execution of this block then the catch part of the statement is simply ignored However if an exception of type ArrayIndexOutOfBoundsException occurs then the computer jumps immediately to the catch clause of the try statement This block of statements is said to be an exception handler for ArrayIndexOutOfBoundsException By handling the exception in this way you prevent it from crashing the program Before the body of the catch clause is executed the object that represents the exception is assigned to the variable e which is used in this example to print a stack trace However the full syntax of the try statement has many options It will take a while to go through them For one thing a try catch statement can have more than one catch clause This makes it possible to catch several different types of exception with one try statement In the above example in addition to the possible ArrayIndexOutOfBoundsException there is a possible NullPointerException which will occur if the value of M is null We can handle both possible exceptions by adding a second catch clause to the try statement try double determinant M 0 0 M 1 1 M 0 1 M 1 0 System out println The determinant of M is determinant catch ArrayIndexOutOfBoundsException e System out println M is the wrong size to have a determinant catch NullPointerException e System out print Programming error M doesn t exist Here the computer tries to execute the statements in the try clause If no error occurs both of the catch clauses are skipped If an ArrayIndexOutOfBoundsException occurs the computer executes the body of the first catch clause and skips the second one If a NullPointerException occurs it jumps to the second catch clause and executes that Note that both ArrayIndexOutOfBoundsException and NullPointerException are subclasses of RuntimeException It s possible to catch all RuntimeExceptions with a single catch clause For example try double determinant M 0 0 M 1 1 M 0 1 M 1 0 System out println The determinant of M is determinant catch RuntimeException err System out println Sorry an error has occurred System out println The error was err The catch clause in this try statement will catch any exception belonging to class RuntimeException or to any of its subclasses This shows why exception classes are organized into a class hierarchy It allows you the option of casting your net narrowly to catch only a specific type of exception Or you can cast your net widely to catch a wide class of exceptions Because of subclassing when there are multiple catch clauses in a try statement it is possible that a given exception might match several of those catch clauses For example an exception of type NullPointerException would match catch clauses for NullPointerException RuntimeException Exception or Throwable In this case only the first catch clause that matches the exception is executed Of course catching RuntimeException would catch many more types of exception than the two that we are interested in It is possible to combine several specific exception types in a single catch clause For example try double determinant M 0 0 M 1 1 M 0 1 M 1 0 System out println The determinant of M is determinant catch NullPointerException ArrayIndexOutOfBoundsException err System out println Sorry an error has occurred System out println The error was err Here the two exception types are combined with a the vertical line character that is also used in the boolean or operator This example will catch errors of type NullPointerException or ArrayIndexOutOfBoundsException and no other types The example I ve been using here is not realistic because you are not very likely to use exception handling to guard against null pointers and bad array indices This is a case where careful programming is better than exception handling Just be sure that your program assigns a reasonable non null value to the array M You would certainly resent it if the designers of Java forced you to set up a try catch statement every time you wanted to use an array This is why handling of potential RuntimeExceptions is not mandatory There are just too many things that might go wrong This also shows that exception handling does not solve the problem of program robustness It just gives you a tool that will in many cases let you approach the problem in a more organized way I have still not completely specified the syntax of the try statement The next variation is the possibility of a finally clause at the end of a try statement With this addition syntax of the try statement can be described as try statements optional catch clauses optional finally clause Note that the catch clauses are also listed as optional The try statement can include zero or more catch clauses and optionally a finally clause The try statement must include one or the other That is a try statement can have either a finally clause or one or more catch clauses or both The syntax for a catch clause is catch exception class names variable name statements where exception class names can be a single exception class or several classes separated by The syntax for a finally clause is finally statements The semantics of the finally clause is that the block of statements in the finally clause is guaranteed to be executed as the last step in the execution of the try statement whether or not any exception occurs and whether or not any exception that does occur is caught and handled The finally clause is meant for doing essential cleanup that under no circumstances should be omitted One example of this type of cleanup is closing a network connection Although you don t yet know enough about networking to look at the actual programming in this case we can consider some pseudocode try open a network connection communicate over the connection catch IOException e report the error finally if the connection was successfully opened close the connection The finally clause ensures that the network connection will definitely be closed whether or not an error occurs during the communication The pseudocode in this example follows a general pattern that can be used to robustly obtain a resource use the resource and then release the resource The pattern of obtaining a resource then using the resource and then releasing the resource is very common Note that the resource can only be released if no error occurred while obtaining it And if it was successfully obtained then it should be closed whether or not an error occurs while using it This pattern is so common that it leads to one last option in the try statement syntax With this option you only need code to obtain the resource and you don t need to worry about releasing it That will happen automatically at the end of the try statement In order for this to work the resource must be represented by an object that implements an interface named AutoCloseable which defines a single method named close with no parameters Standard Java classes that represent things like files and network connections already implement AutoClosable So does the Scanner class which was introduced in Subsection 2 4 6 In that section I showed how to use a Scanner to read from System in Although I didn t do it in that section it s considered good form to close a Scanner after using it Here is an example that uses the resource pattern in a try statement to make sure that the Scanner is closed automatically try Scanner in new Scanner System in Use the Scanner to read from standard input catch Exception e some error occurred while using the Scanner The statement that allocates the resource goes in parentheses after the word try The statement must have the form of a variable declaration that includes an initialization of the variable The variable is local to the try statement You can actually declare several variables in the parentheses separated by semicolons In this example we can be sure that in close will definitely be called by the system at the end of the try statement as long as the Scanner was successfully initialized This is all getting quite complicated and I won t continue the discussion here The sample program TryStatementDemo java demonstrates a try statement with all its options and it includes a lot of comments to help you understand what can happen when you run the program 8 3 3 Throwing Exceptions There are times when it makes sense for a program to deliberately throw an exception This is the case when the program discovers some sort of exceptional or error condition but there is no reasonable way to handle the error at the point where the problem is discovered The program can throw an exception in the hope that some other part of the program will catch and handle the exception This can be done with a throw statement You have already seen an example of this in Subsection 4 3 8 In this section we cover the throw statement more fully The syntax of the throw statement is throw exception object The exception object must be an object belonging to one of the subclasses of Throwable Usually it will in fact belong to one of the subclasses of Exception In most cases it will be a newly constructed object created with the new operator For example throw new ArithmeticException Division by zero The parameter in the constructor becomes the error message in the exception object if e refers to the object the error message can be retrieved by calling e getMessage You might find this example a bit odd because you might expect the system itself to throw an ArithmeticException when an attempt is made to divide by zero So why should a programmer bother to throw the exception Recall that if the numbers that are being divided are of type int then division by zero will indeed throw an ArithmeticException However no arithmetic operations with floating point numbers will ever produce an exception Instead the special value Double NaN is used to represent the result of an illegal operation In some situations you might prefer to throw an ArithmeticException when a real number is divided by zero An exception can be thrown either by the system or by a throw statement The exception is processed in exactly the same way in either case Suppose that the exception is thrown inside a try statement If that try statement has a catch clause that handles that type of exception then the computer jumps to the catch clause and executes it The exception has been handled After handling the exception the computer executes the finally clause of the try statement if there is one It then continues normally with the rest of the program which follows the try statement If the exception is not immediately caught and handled the processing of the exception will continue When an exception is thrown during the execution of a subroutine and the exception is not handled in the same subroutine then that subroutine is terminated after the execution of any pending finally clauses Then the routine that called that subroutine gets a chance to handle the exception That is if the subroutine was called inside a try statement that has an appropriate catch clause then that catch clause will be executed and the program will continue on normally from there Again if the second routine does not handle the exception then it also is terminated and the routine that called it if any gets the next shot at the exception The exception will crash the program only if it passes up through the entire chain of subroutine calls without being handled In fact even this is not quite true In a multithreaded program only the thread in which the exception occurred is terminated A subroutine that might generate an exception can announce this fact by adding a clause throws exception class name to the header of the routine For example Returns the larger of the two roots of the quadratic equation A x x B x C 0 provided it has any roots If A 0 or if the discriminant B B 4 A C is negative then an exception of type IllegalArgumentException is thrown static public double root double A double B double C throws IllegalArgumentException if A 0 throw new IllegalArgumentException A can t be zero else double disc B B 4 A C if disc 0 throw new IllegalArgumentException Discriminant zero return B Math sqrt disc 2 A As discussed in the previous section the computation in this subroutine has the preconditions that A 0 and B B 4 A C 0 The subroutine throws an exception of type IllegalArgumentException when either of these preconditions is violated When an illegal condition is found in a subroutine throwing an exception is often a reasonable response If the program that called the subroutine knows some good way to handle the error it can catch the exception If not the program will crash and the programmer will know that the program needs to be fixed A throws clause in a subroutine heading can declare several different types of exception separated by commas For example void processArray int A throws NullPointerException ArrayIndexOutOfBoundsException 8 3 4 Mandatory Exception Handling In the preceding example declaring that the subroutine root can throw an IllegalArgumentException is just a courtesy to potential readers of this routine This is because handling of IllegalArgumentExceptions is not mandatory A routine can throw an IllegalArgumentException without announcing the possibility And a program that calls that routine is free either to catch or to ignore the exception just as a programmer can choose either to catch or to ignore an exception of type NullPointerException For those exception classes that require mandatory handling the situation is different If a subroutine can throw such an exception that fact must be announced in a throws clause in the routine definition Failing to do so is a syntax error that will be reported by the compiler Exceptions that require mandatory handling are called checked exceptions The compiler will check that such exceptions are handled by the program Suppose that some statement in the body of a subroutine can generate a checked exception one that requires mandatory handling The statement could be a throw statement which throws the exception directly or it could be a call to a subroutine that can throw the exception In either case the exception must be handled This can be done in one of two ways The first way is to place the statement in a try statement that has a catch clause that handles the exception in this case the exception is handled within the subroutine so that no caller of the subroutine can ever see the exception The second way is to declare that the subroutine can throw the exception This is done by adding a throws clause to the subroutine heading which alerts any callers to the possibility that the exception might be generated when the subroutine is executed The caller will in turn be forced either to handle the exception in a try statement or to declare the exception in a throws clause in its own header Exception handling is mandatory for any exception class that is not a subclass of either Error or RuntimeException These checked exceptions generally represent conditions that are outside the control of the programmer For example they might represent bad input or an illegal action taken by the user There is no way to avoid such errors so a robust program has to be prepared to handle them The design of Java makes it impossible for programmers to ignore the possibility of such errors Among the checked exceptions are several that can occur when using Java s input output routines This means that you can t even use these routines unless you understand something about exception handling Chapter 11 deals with input output and uses checked exceptions extensively 8 3 5 Programming with Exceptions Exceptions can be used to help write robust programs They provide an organized and structured approach to robustness Without exceptions a program can become cluttered with if statements that test for various possible error conditions With exceptions it becomes possible to write a clean implementation of an algorithm that will handle all the normal cases The exceptional cases can be handled elsewhere in a catch clause of a try statement When a program encounters an exceptional condition and has no way of handling it immediately the program can throw an exception In some cases it makes sense to throw an exception belonging to one of Java s predefined classes such as IllegalArgumentException or IOException However if there is no standard class

    Original URL path: http://math.hws.edu/javanotes/c8/s3.html (2016-02-07)
    Open archived version from archive

  • Javanotes 7.0, Section 9.1 -- Recursion
    then you can solve problems of any size Ultimately of course the big problems have to be reduced possibly in many many steps to the very smallest problems the base cases Doing so might involve an immense amount of detailed bookkeeping But the computer does that bookkeeping not you As a programmer you lay out the big picture the base cases and the reduction of big problems to smaller problems The computer takes care of the details involved in reducing a big problem in many steps all the way down to base cases Trying to think through this reduction in detail is likely to drive you crazy and will probably make you think that recursion is hard Whereas in fact recursion is an elegant and powerful method that is often the simplest approach to solving a complex problem A common error in writing recursive subroutines is to violate one of the two rules There must be one or more base cases and when the subroutine is applied recursively it must be applied to a problem that is smaller than the original problem If these rules are violated the result can be an infinite recursion where the subroutine keeps calling itself over and over without ever reaching a base case Infinite recursion is similar to an infinite loop However since each recursive call to the subroutine uses up some of the computer s memory a program that is stuck in an infinite recursion will run out of memory and crash before long In Java the program will crash with an exception of type StackOverflowError 9 1 2 Towers of Hanoi We have been studying an algorithm binary search that can easily be implemented with a while loop instead of with recursion Next we turn to a problem that is easy to solve with recursion but difficult to solve without it This is a standard example known as The Towers of Hanoi The problem involves a stack of various sized disks piled up on a base in order of decreasing size The object is to move the stack from one base to another subject to two rules Only one disk can be moved at a time and no disk can ever be placed on top of a smaller disk There is a third base that can be used as a spare The starting situation for a stack of ten disks is shown in the top half of the following picture The situation after a number of moves have been made is shown in the bottom half of the picture These illustrations are from a sample program from Chapter 12 TowersOfHanoiGUI java which displays an animation of the step by step solution of the problem however that program uses some techniques that you haven t learned yet The problem is to move ten disks from Stack 0 to Stack 1 subject to the rules given above Stack 2 can be used as a spare location Can we reduce this to smaller problems of the same type possibly generalizing the problem a bit to make this possible It seems natural to consider the size of the problem to be the number of disks to be moved If there are N disks in Stack 0 we know that we will eventually have to move the bottom disk from Stack 0 to Stack 1 But before we can do that according to the rules the first N 1 disks must be on Stack 2 Once we ve moved the N th disk to Stack 1 we must move the other N 1 disks from Stack 2 to Stack 1 to complete the solution But moving N 1 disks is the same type of problem as moving N disks except that it s a smaller version of the problem This is exactly what we need to do recursion The problem has to be generalized a bit because the smaller problems involve moving disks from Stack 0 to Stack 2 or from Stack 2 to Stack 1 instead of from Stack 0 to Stack 1 In the recursive subroutine that solves the problem the stacks that serve as the source and destination of the disks have to be specified It s also convenient to specify the stack that is to be used as a spare even though we could figure that out from the other two parameters The base case is when there is only one disk to be moved The solution in this case is trivial Just move the disk in one step Here is a version of the subroutine that will print out step by step instructions for solving the problem Solve the problem of moving the number of disks specified by the first parameter from the stack specified by the second parameter to the stack specified by the third parameter The stack specified by the fourth parameter is available for use as a spare Stacks are specified by number 0 1 or 2 static void towersOfHanoi int disks int from int to int spare if disks 1 There is only one disk to be moved Just move it System out printf Move disk 1 from stack d to stack d n from to else Move all but one disk to the spare stack then move the bottom disk then put all the other disks on top of it towersOfHanoi disks 1 from spare to System out printf Move disk d from stack d to stack d n disks from to towersOfHanoi disks 1 spare to from This subroutine just expresses the natural recursive solution The recursion works because each recursive call involves a smaller number of disks and the problem is trivial to solve in the base case when there is only one disk To solve the top level problem of moving N disks from Stack 0 to Stack 1 it should be called with the command TowersOfHanoi N 0 1 2 The subroutine is demonstrated by the sample program TowersOfHanoi java Here for example is the output from the program when it is run with the number of disks set equal to 4 Move disk 1 from stack 0 to stack 2 Move disk 2 from stack 0 to stack 1 Move disk 1 from stack 2 to stack 1 Move disk 3 from stack 0 to stack 2 Move disk 1 from stack 1 to stack 0 Move disk 2 from stack 1 to stack 2 Move disk 1 from stack 0 to stack 2 Move disk 4 from stack 0 to stack 1 Move disk 1 from stack 2 to stack 1 Move disk 2 from stack 2 to stack 0 Move disk 1 from stack 1 to stack 0 Move disk 3 from stack 2 to stack 1 Move disk 1 from stack 0 to stack 2 Move disk 2 from stack 0 to stack 1 Move disk 1 from stack 2 to stack 1 The output of this program shows you a mass of detail that you don t really want to think about The difficulty of following the details contrasts sharply with the simplicity and elegance of the recursive solution Of course you really want to leave the details to the computer You might think about what happens when the precondition that the number of disks is positive is violated The result is an example of infinite recursion There is by the way a story that explains the name of this problem According to this story on the first day of creation a group of monks in an isolated tower near Hanoi were given a stack of 64 disks and were assigned the task of moving one disk every day according to the rules of the Towers of Hanoi problem On the day that they complete their task of moving all the disks from one stack to another the universe will come to an end But don t worry The number of steps required to solve the problem for N disks is 2 N 1 and 2 64 1 days is over 50 000 000 000 000 years We have a long way to go In the terminology of Section 8 5 the Towers of Hanoi algorithm has a run time that is Θ 2 n where n is the number of disks that have to be moved Since the exponential function 2 n grows so quickly the Towers of Hanoi problem can be solved in practice only for a small number of disks By the way in addition to the graphical Towers of Hanoi program mentioned above there are two more demo programs that you might want to look at Each program provides a visual demonstration of a recursive algorithm In Maze java recursion is used to solve a maze In LittlePentominos java it is used to solve a well known kind of puzzle LittlePentominos java also requires the file MosaicPanel java It would be useful to run the programs and watch them for a while but the source code uses some techniques that won t be covered until Chapter 12 The Maze program first creates a random maze It then tries to solve the maze by finding a path through the maze from the upper left corner to the lower right corner This problem is actually very similar to a blob counting problem that is considered later in this section The recursive maze solving routine starts from a given square and it visits each neighboring square and calls itself recursively from there The recursion ends if the routine finds itself at the lower right corner of the maze When it can t find a solution from a square it backs up out of that square and tries somewhere else This common technique is referred to as recursive backtracking The LittlePentominos program is an implementation of a classic puzzle A pentomino is a connected figure made up of five equal sized squares There are exactly twelve figures that can be made in this way not counting all the possible rotations and reflections of the basic figures The problem is to place the twelve pentominos on an 8 by 8 board in which four of the squares have already been marked as filled The recursive solution looks at a board that has already been partially filled with pentominos The subroutine looks at each remaining piece in turn It tries to place that piece in the next available place on the board If the piece fits it calls itself recursively to try to fill in the rest of the solution If that fails then the subroutine goes on to the next piece another example of recursive backtracking A generalized version of the pentominos program with many more features can be found at http math hws edu xJava PentominosSolver 9 1 3 A Recursive Sorting Algorithm Turning next to an application that is perhaps more practical we ll look at a recursive algorithm for sorting an array The selection sort and insertion sort algorithms which were covered in Section 7 4 are fairly simple but they are rather slow when applied to large arrays Faster sorting algorithms are available One of these is Quicksort a recursive algorithm which turns out to be the fastest sorting algorithm in most situations The Quicksort algorithm is based on a simple but clever idea Given a list of items select any item from the list This item is called the pivot In practice I ll just use the first item in the list Move all the items that are smaller than the pivot to the beginning of the list and move all the items that are larger than the pivot to the end of the list Now put the pivot between the two groups of items This puts the pivot in the position that it will occupy in the final completely sorted array It will not have to be moved again We ll refer to this procedure as QuicksortStep QuicksortStep is not recursive It is used as a subroutine by Quicksort The speed of Quicksort depends on having a fast implementation of QuicksortStep Since it s not the main point of this discussion I present one without much comment Apply QuicksortStep to the list of items in locations lo through hi in the array A The value returned by this routine is the final position of the pivot item in the array static int quicksortStep int A int lo int hi int pivot A lo Get the pivot value The numbers hi and lo mark the endpoints of a range of numbers that have not yet been tested Decrease hi and increase lo until they become equal moving numbers bigger than pivot so that they lie above hi and moving numbers less than the pivot so that they lie below lo When we begin A lo is an available space since its value has been moved into the local variable pivot while hi lo while hi lo A hi pivot Move hi down past numbers greater than pivot These numbers do not have to be moved hi if hi lo break The number A hi is less than pivot Move it into the available space at A lo leaving an available space at A hi A lo A hi lo while hi lo A lo pivot Move lo up past numbers less than pivot These numbers do not have to be moved lo if hi lo break The number A lo is greater than pivot Move it into the available space at A hi leaving an available space at A lo A hi A lo hi end while At this point lo has become equal to hi and there is an available space at that position This position lies between numbers less than pivot and numbers greater than pivot Put pivot in this space and return its location A lo pivot return lo end QuicksortStep With this subroutine in hand Quicksort is easy The Quicksort algorithm for sorting a list consists of applying QuicksortStep to the list then applying Quicksort recursively to the items that lie to the left of the new position of the pivot and to the items that lie to the right of that position Of course we need base cases If the list has only one item or no items then the list is already as sorted as it can ever be so Quicksort doesn t have to do anything in these cases Apply quicksort to put the array elements between position lo and position hi into increasing order static void quicksort int A int lo int hi if hi lo The list has length one or zero Nothing needs to be done so just return from the subroutine return else Apply quicksortStep and get the new pivot position Then apply quicksort to sort the items that precede the pivot and the items that follow it int pivotPosition quicksortStep A lo hi quicksort A lo pivotPosition 1 quicksort A pivotPosition 1 hi As usual we had to generalize the problem The original problem was to sort an array but the recursive algorithm is set up to sort a specified part of an array To sort an entire array A using the quickSort subroutine you would call quicksort A 0 A length 1 Quicksort is an interesting example from the point of view of the analysis of algorithms Section 8 5 because its average case run time differs greatly from its worst case run time Here is a very informal analysis starting with the average case Note that an application of quicksortStep divides a problem into two sub problems On the average the subproblems will be of approximately the same size A problem of size n is divided into two problems that are roughly of size n 2 these are then divided into four problems that are roughly of size n 4 and so on Since the problem size is divided by 2 on each level there will be approximately log n levels of subdivision The amount of processing on each level is proportional to n On the top level each element in the array is looked at and possibly moved On the second level where there are two subproblems every element but one in the array is part of one of those two subproblems and must be looked at and possibly moved so there is a total of about n steps in both subproblems combined Similarly on the third level there are four subproblems and a total of about n steps in the four subproblems on that level With a total of n steps on each level and approximately log n levels in the average case the average case run time for Quicksort is Θ n log n This analysis assumes that quicksortStep divides a problem into two approximately equal parts However in the worst case each application of quicksortStep divides a problem of size n into a problem of size 0 and a problem of size n 1 This happens when the pivot element ends up at the beginning or end of the array In this worst case there are n levels of subproblems and the worst case run time is Θ n 2 The worst case is very rare it depends on the items in the array being arranged in a very special way so the average performance of Quicksort can be very good even though it is not so good in certain rare cases There are sorting algorithms that have both an average case and a worst case run time of Θ n log n One example is MergeSort which you can look up if you are interested 9 1 4 Blob Counting Next we will look at counting the number of squares in a group of connected squares I call a group of squares a blob and the sample program that we will consider is Blobs java The program displays a grid of small white and gray

    Original URL path: http://math.hws.edu/javanotes/c9/s1.html (2016-02-07)
    Open archived version from archive

  • Javanotes 7.0, Section 9.2 -- Linked Data Structures
    int item One of the integers in the list IntNode next Pointer to the next node in the list If head is a variable of type IntNode that points to a linked list of integers we can find the sum of the integers in the list using int sum 0 IntNode runner head while runner null sum sum runner item Add current item to the sum runner runner next System out println The sum of the list of items is sum It is also possible to use recursion to process a linked list Recursion is rarely the natural way to process a list since it s so easy to use a loop to traverse the list However understanding how to apply recursion to lists can help with understanding the recursive processing of more complex data structures A non empty linked list can be thought of as consisting of two parts the head of the list which is just the first node in the list and the tail of the list which consists of the remainder of the list after the head Note that the tail is itself a linked list and that it is shorter than the original list by one node This is a natural setup for recursion where the problem of processing a list can be divided into processing the head and recursively processing the tail The base case occurs in the case of an empty list or sometimes in the case of a list of length one For example here is a recursive algorithm for adding up the numbers in a linked list of integers if the list is empty then return 0 since there are no numbers to be added up otherwise let listsum the number in the head node let tailsum be the sum of the numbers in the tail list recursively add tailsum to listsum return listsum One remaining question is how do we get the tail of a non empty linked list If head is a variable that points to the head node of the list then head next is a variable that points to the second node of the list and that node is in fact the first node of the tail So we can view head next as a pointer to the tail of the list One special case is when the original list consists of a single node In that case the tail of the list is empty and head next is null Since an empty list is represented by a null pointer head next represents the tail of the list even in this special case This allows us to write a recursive list summing function in Java as Compute the sum of all the integers in a linked list of integers param head a pointer to the first node in the linked list public static int addItemsInList IntNode head if head null Base case The list is empty so the sum is zero return 0 else Recursive case The list is non empty Find the sum of the tail list and add that to the item in the head node Note that this case could be written simply as return head item addItemsInList head next int listsum head item int tailsum addItemsInList head next listsum listsum tailsum return listsum I will finish by presenting a list processing problem that is easy to solve with recursion but quite tricky to solve without it The problem is to print out all the strings in a linked list of strings in the reverse of the order in which they occur in the list Note that when we do this the item in the head of a list is printed out after all the items in the tail of the list This leads to the following recursive routine You should convince yourself that it works and you should think about trying to do the same thing without using recursion public static void printReversed Node head if head null Base case The list is empty and there is nothing to print return else Recursive case The list is non empty printReversed head next Print strings from tail in reverse order System out println head item Then print string from head node In the rest of this section we ll look at a few more advanced operations on a linked list of strings The subroutines that we consider are instance methods in a class that I wrote named StringList An object of type StringList represents a linked list of strings The class has a private instance variable named head of type Node that points to the first node in the list or is null if the list is empty Instance methods in class StringList access head as a global variable The source code for StringList is in the file StringList java and it is used in a sample program named ListDemo java so you can take a look at the code in context if you want One of the methods in the StringList class searches the list looking for a specified string If the string that we are looking for is searchItem then we have to compare searchItem to each item in the list This is an example of basic list traversal and processing However in this case we can stop processing if we find the item that we are looking for Searches the list for a specified item param searchItem the item that is to be searched for return true if searchItem is one of the items in the list or false if searchItem does not occur in the list public boolean find String searchItem Node runner A pointer for traversing the list runner head Start by looking at the head of the list head is an instance variable while runner null Go through the list looking at the string in each node If the string is the one we are looking for return true since the string has been found in the list

    Original URL path: http://math.hws.edu/javanotes/c9/s2.html (2016-02-07)
    Open archived version from archive

  • Javanotes 7.0, Section 9.3 -- Stacks, Queues, and ADTs
    pointer to the last node in the list If head is a pointer to the first node of the list it would always be possible to get a pointer to the last node of the list by saying Node tail This will point to the last node in the list tail head Start at the first node while tail next null tail tail next Move to next node At this point tail next is null so tail points to the last node in the list However it would be very inefficient to do this over and over every time an item is enqueued For the sake of efficiency we ll keep a pointer to the last node in an instance variable This complicates the class somewhat we have to be careful to update the value of this variable whenever a new node is added to the end of the list Given all this writing the QueueOfInts class is not all that difficult public class QueueOfInts An object of type Node holds one of the items in the linked list that represents the queue private static class Node int item Node next private Node head null Points to first Node in the queue The queue is empty when head is null private Node tail null Points to last Node in the queue Add N to the back of the queue public void enqueue int N Node newTail new Node A Node to hold the new item newTail item N if head null The queue was empty The new Node becomes the only node in the list Since it is both the first and last node both head and tail point to it head newTail tail newTail else The new node becomes the new tail of the list The head of the list is unaffected tail next newTail tail newTail Remove and return the front item in the queue Throws an IllegalStateException if the queue is empty public int dequeue if head null throw new IllegalStateException Can t dequeue from an empty queue int firstItem head item head head next The previous second item is now first If we have just removed the last item then head is null if head null The queue has become empty The Node that was deleted was the tail as well as the head of the list so now there is no tail Actually the class would work fine without this step tail null return firstItem Return true if the queue is empty boolean isEmpty return head null end class QueueOfInts Queues are typically used in a computer as in real life when only one item can be processed at a time but several items can be waiting for processing For example In a Java program that has multiple threads the threads that want processing time on the CPU are kept in a queue When a new thread is started it is added to the back of the queue A thread is removed from the front of the queue given some processing time and then if it has not terminated is sent to the back of the queue to wait for another turn Events such as keystrokes and mouse clicks are stored in a queue called the event queue A program removes events from the event queue and processes them It s possible for several more events to occur while one event is being processed but since the events are stored in a queue they will always be processed in the order in which they occurred A web server is a program that receives requests from web browsers for pages It is easy for new requests to arrive while the web server is still fulfilling a previous request Requests that arrive while the web server is busy are placed into a queue to await processing Using a queue ensures that requests will be processed in the order in which they were received Queues are said to implement a FIFO policy First In First Out Or as it is more commonly expressed first come first served Stacks on the other hand implement a LIFO policy Last In First Out The item that comes out of the stack is the last one that was put in Just like queues stacks can be used to hold items that are waiting for processing although in applications where queues are typically used a stack would be considered unfair To get a better handle on the difference between stacks and queues consider the sample program DepthBreadth java I suggest that you try out the program The program shows a grid of squares Initially all the squares are white When you click on a white square the program will gradually mark all the squares in the grid starting from the one where you click To understand how the program does this think of yourself in the place of the program When the user clicks a square you are handed an index card The location of the square its row and column is written on the card You put the card in a pile which then contains just that one card Then you repeat the following If the pile is empty you are done Otherwise remove an index card from the pile The index card specifies a square Look at each horizontal and vertical neighbor of that square If the neighbor has not already been encountered write its location on a new index card and put the card in the pile You are done when there are no more index cards waiting in the pile to be processed In the program while a square is in the pile waiting to be processed it is colored red that is red squares have been encountered but not yet processed When a square is taken from the pile and processed its color changes to gray Once a square has been colored gray its color won t change again Eventually all the squares have been processed and the

    Original URL path: http://math.hws.edu/javanotes/c9/s3.html (2016-02-07)
    Open archived version from archive

  • Javanotes 7.0, Section 9.4 -- Binary Trees
    order and all the items in the right subtree follow judy in alphabetical order So we know that judy is output in its proper alphabetical position But the same argument applies to the subtrees Bill will be output after alice and before fred and its descendents Fred will be output after dave and before jane and joe And so on Suppose that we want to search for a given item in a binary search tree Compare that item to the root item of the tree If they are equal we re done If the item we are looking for is less than the root item then we need to search the left subtree of the root the right subtree can be eliminated because it only contains items that are greater than or equal to the root Similarly if the item we are looking for is greater than the item in the root then we only need to look in the right subtree In either case the same procedure can then be applied to search the subtree Inserting a new item is similar Start by searching the tree for the position where the new item belongs When that position is found create a new node and attach it to the tree at that position Searching and inserting are efficient operations on a binary search tree provided that the tree is close to being balanced A binary tree is balanced if for each node the left subtree of that node contains approximately the same number of nodes as the right subtree In a perfectly balanced tree the two numbers differ by at most one Not all binary trees are balanced but if the tree is created by inserting items in a random order there is a high probability that the tree is approximately balanced If the order of insertion is not random however it s quite possible for the tree to be very unbalanced During a search of any binary sort tree every comparison eliminates one of two subtrees from further consideration If the tree is balanced that means cutting the number of items still under consideration in half This is exactly the same as the binary search algorithm and the result is a similarly efficient algorithm In terms of asymptotic analysis Section 8 5 searching inserting and deleting in a binary search tree have average case run time Θ log n The problem size n is the number of items in the tree and the average is taken over all the different orders in which the items could have been inserted into the tree As long as the actual insertion order is random the actual run time can be expected to be close to the average However the worst case run time for binary search tree operations is Θ n which is much worse than Θ log n The worst case occurs for particular insertion orders For example if the items are inserted into the tree in order of increasing size then every item that is inserted moves always to the right as it moves down the tree The result is a tree that looks more like a linked list since it consists of a linear string of nodes strung together by their right child pointers Operations on such a tree have the same performance as operations on a linked list Now there are data structures that are similar to simple binary sort trees except that insertion and deletion of nodes are implemented in a way that will always keep the tree balanced or almost balanced For these data structures searching inserting and deleting have both average case and worst case run times that are Θ log n Here however we will look at only the simple versions of inserting and searching The sample program SortTreeDemo java is a demonstration of binary sort trees The program includes subroutines that implement inorder traversal searching and insertion We ll look at the latter two subroutines below The main routine tests the subroutines by letting you type in strings to be inserted into the tree In SortTreeDemo nodes in the binary tree are represented using the following static nested class including a simple constructor that makes creating nodes easier An object of type TreeNode represents one node in a binary tree of strings private static class TreeNode String item The data in this node TreeNode left Pointer to left subtree TreeNode right Pointer to right subtree TreeNode String str Constructor Make a node containing str Note that left and right pointers are null item str end class TreeNode A static member variable of type TreeNode points to the binary sort tree that is used by the program private static TreeNode root Pointer to the root node in the tree When the tree is empty root is null A recursive subroutine named treeContains is used to search for a given item in the tree This routine implements the search algorithm for binary trees that was outlined above Return true if item is one of the items in the binary sort tree to which root points Return false if not static boolean treeContains TreeNode root String item if root null Tree is empty so it certainly doesn t contain item return false else if item equals root item Yes the item has been found in the root node return true else if item compareTo root item 0 If the item occurs it must be in the left subtree return treeContains root left item else If the item occurs it must be in the right subtree return treeContains root right item end treeContains When this routine is called in the main routine the first parameter is the static member variable root which points to the root of the entire binary sort tree It s worth noting that recursion is not really essential in this case A simple non recursive algorithm for searching a binary sort tree follows the rule Start at the root and move down the

    Original URL path: http://math.hws.edu/javanotes/c9/s4.html (2016-02-07)
    Open archived version from archive

  • Javanotes 7.0, Section 9.5 -- A Simple Recursive Descent Parser
    I should also mention that many variations of BNF are in use The one that I ve described here is one that is well suited for recursive descent parsing When we try to parse a phrase that contains a syntax error we need some way to respond to the error A convenient way of doing this is to throw an exception I ll use an exception class called ParseError defined as follows An object of type ParseError represents a syntax error found in the user s input private static class ParseError extends Exception ParseError String message super message end nested class ParseError Another general point is that our BNF rules don t say anything about spaces between items but in reality we want to be able to insert spaces between items at will To allow for this I ll always call the routine TextIO skipBlanks before trying to look ahead to see what s coming up next in input TextIO skipBlanks skips past any whitespace such as spaces and tabs in the input and stops when the next character in the input is either a non blank character or the end of line character Let s start with a very simple example A fully parenthesized expression can be specified in BNF by the rules expression number expression operator expression operator where number refers to any non negative real number An example of a fully parenthesized expression is 34 17 8 2 7 Since every operator corresponds to a pair of parentheses there is no ambiguity about the order in which the operators are to be applied Suppose we want a program that will read and evaluate such expressions We ll read the expressions from standard input using TextIO To apply recursive descent parsing we need a subroutine for each rule in the grammar Corresponding to the rule for operator we get a subroutine that reads an operator The operator can be a choice of any of four things Any other input will be an error If the next character in input is one of the legal operators read it and return it Otherwise throw a ParseError static char getOperator throws ParseError TextIO skipBlanks char op TextIO peek look ahead at the next char without reading it if op op op op TextIO getAnyChar read the operator to remove it from the input return op else if op n throw new ParseError Missing operator at end of line else throw new ParseError Missing operator Found op instead of or end getOperator I ve tried to give a reasonable error message depending on whether the next character is an end of line or something else I use TextIO peek to look ahead at the next character before I read it and I call TextIO skipBlanks before testing TextIO peek in order to ignore any blanks that separate items I will follow this same pattern in every case When we come to the subroutine for expression things are a little more interesting The rule says that an expression can be either a number or an expression enclosed in parentheses We can tell which it is by looking ahead at the next character If the character is a digit we have to read a number If the character is a we have to read the followed by an expression followed by an operator followed by another expression followed by a If the next character is anything else there is an error Note that we need recursion to read the nested expressions The routine doesn t just read the expression It also computes and returns its value This requires semantical information that is not specified in the BNF rule Read an expression from the current line of input and return its value throws ParseError if the input contains a syntax error private static double expressionValue throws ParseError TextIO skipBlanks if Character isDigit TextIO peek The next item in input is a number so the expression must consist of just that number Read and return the number return TextIO getDouble else if TextIO peek The expression must be of the form expression operator expression Read all these items perform the operation and return the result TextIO getAnyChar Read the double leftVal expressionValue Read and evaluate first operand char op getOperator Read the operator double rightVal expressionValue Read and evaluate second operand TextIO skipBlanks if TextIO peek According to the rule there must be a here Since it s missing throw a ParseError throw new ParseError Missing right parenthesis TextIO getAnyChar Read the switch op Apply the operator and return the result case return leftVal rightVal case return leftVal rightVal case return leftVal rightVal case return leftVal rightVal default return 0 Can t occur since op is one of the above But Java syntax requires a return value else No other character can legally start an expression throw new ParseError Encountered unexpected character TextIO peek in input end expressionValue I hope that you can see how this routine corresponds to the BNF rule Where the rule uses to give a choice between alternatives there is an if statement in the routine to determine which choice to take Where the rule contains a sequence of items expression operator expression there is a sequence of statements in the subroutine to read each item in turn When expressionValue is called to evaluate the expression 34 17 8 2 7 it sees the at the beginning of the input so the else part of the if statement is executed The is read Then the first recursive call to expressionValue reads and evaluates the subexpression 34 17 8 the call to getOperator reads the operator and the second recursive call to expressionValue reads and evaluates the second subexpression 2 7 Finally the at the end of the expression is read Of course reading the first subexpression 34 17 8 involves further recursive calls to the expressionValue routine but it s better not to think too deeply about that Rely on the recursion

    Original URL path: http://math.hws.edu/javanotes/c9/s5.html (2016-02-07)
    Open archived version from archive

  • Javanotes 7.0, Section 10.2 -- Lists and Sets
    to make it easy to use a LinkedList as if it were a stack or a queue See Section 9 3 For example we can use a LinkedList as a stack by using the methods named push and pop or as a queue by using add and remove to implement the enqueue and dequeue operations If list is an object of type List T then the method list iterator defined in the interface Collection T returns an Iterator that can be used to traverse the list from beginning to end However for Lists there is a special type of Iterator called a ListIterator which offers additional capabilities ListIterator T is an interface that extends the interface Iterator T The method list listIterator returns an object of type ListIterator T A ListIterator has the usual Iterator methods hasNext next and remove but it also has methods hasPrevious previous add obj and set obj that make it possible to move backwards in the list to add an item at the current position of the iterator and to replace one of the items in the list To understand how these work it s best to think of an iterator as pointing to a position between two list elements or at the beginning or end of the list In this diagram the items in a list are represented by squares and arrows indicate the possible positions of an iterator If iter is of type ListIterator T then iter next moves the iterator one space to the right along the list and returns the item that the iterator passes as it moves The method iter previous moves the iterator one space to the left along the list and returns the item that it passes The method iter remove removes an item from the list the item that is removed is the item that the iterator passed most recently in a call to either iter next or iter previous The method iter set obj works similarly it replaces the item that would be removed by iter remove There is also a method iter add obj that adds the specified object to the list at the current position of the iterator where obj must be of type T This can be between two existing items or at the beginning of the list or at the end of the list By the way the lists that are used in class LinkedList T are doubly linked lists That is each node in the list contains two pointers one to the next node in the list and one to the previous node This makes it possible to efficiently implement both the next and previous methods of a ListIterator Also to make the addLast and getLast methods of a LinkedList efficient the class LinkedList T includes a tail pointer that points to the last node in the list As an example of using a ListIterator suppose that we want to maintain a list of items that is always sorted into increasing order When adding an item to the list we can use a ListIterator to find the position in the list where the item should be added Once the position has been found we use the same list iterator to place the item in that position The idea is to start at the beginning of the list and to move the iterator forward past all the items that are smaller than the item that is being inserted At that point the iterator s add method can be used to insert the item To be more definite suppose that stringList is a variable of type List String Assume that that the strings that are already in the list are stored in ascending order and that newItem is a string that we would like to insert into the list The following code will place newItem in the list in its correct position so that the modified list is still in ascending order ListIterator String iter stringList listIterator Move the iterator so that it points to the position where newItem should be inserted into the list If newItem is bigger than all the items in the list then the while loop will end when iter hasNext becomes false that is when the iterator has reached the end of the list while iter hasNext String item iter next if newItem compareTo item 0 newItem should come BEFORE item in the list Move the iterator back one space so that it points to the correct insertion point and end the loop iter previous break iter add newItem Here stringList might be of type ArrayList String or of type LinkedList String The algorithm that is used to insert newItem into the list will be about equally efficient for both types of lists and it will even work for other classes that implement the interface List String You would probably find it easier to design an insertion algorithm that uses array like indexing with the methods get index and add index obj However that algorithm would be horribly inefficient for LinkedLists because random access is so inefficient for linked lists By the way the insertion algorithm works when the list is empty It might be useful for you to think about why this is true 10 2 2 Sorting Sorting a list is a fairly common operation and there should really be a sorting method in the List interface There is not presumably because it only makes sense to sort lists of certain types of objects However methods for sorting lists are available as static methods in the class java util Collections This class contains a variety of static utility methods for working with collections The methods are generic that is they will work for collections of objects of various types You have already seen similar methods for arrays in the Arrays class Suppose that list is of type List T The command Collections sort list can be used to sort the list into ascending order The items in the list should implement the interface Comparable T see Subsection 10 1 6 The method Collections sort will work for example for lists of String and for lists of any of the wrapper classes such as Integer and Double There is also a sorting method that takes a Comparator as its second argument Collections sort list comparator In this method the comparator will be used to compare the items in the list As mentioned in the previous section a Comparator is an object that defines a compare method that can be used to compare two objects We ll see an example of using a Comparator in Section 10 4 The sorting method that is used by Collections sort is the so called merge sort algorithm which has both worst case and average case run times that are Θ n log n for a list of size n Although the average run time for MergeSort is a little slower than that of QuickSort its worst case performance is much better than QuickSort s QuickSort was covered in Subsection 9 1 3 MergeSort also has a nice property called stability that we will encounter at the end of Subsection 10 4 3 The Collections class has at least two other useful methods for modifying lists Collections shuffle list will rearrange the elements of the list into a random order Collections reverse list will reverse the order of the elements so that the last element is moved to the beginning of the list the next to last element to the second position and so on Since an efficient sorting method is provided for Lists there is no need to write one yourself 10 2 3 TreeSet and HashSet A set is a collection of objects in which no object occurs more than once Sets implement all the methods in the interface Collection T but do so in a way that ensures that no element occurs twice in the set For example if set is an object of type Set T then set add obj will have no effect on the set if obj is already an element of the set Java has two classes that implement the interface Set T java util TreeSet and java util HashSet In addition to being a Set a TreeSet has the property that the elements of the set are arranged into ascending sorted order An Iterator or a for each loop for a TreeSet will always visit the elements of the set in ascending order A TreeSet cannot hold arbitrary objects since there must be a way to determine the sorted order of the objects it contains Ordinarily this means that the objects in a set of type TreeSet T should implement the interface Comparable T and that obj1 compareTo obj2 should be defined in a reasonable way for any two objects obj1 and obj2 in the set Alternatively an object of type Comparator T can be provided as a parameter to the constructor when the TreeSet is created In that case the compare method of the Comparator will be used to compare objects that are added to the set A TreeSet does not use the equals method to test whether two objects are the same Instead it uses the compareTo or compare method This can be a problem Recall from Subsection 10 1 6 that compareTo can consider two objects to be the same for the purpose of the comparison even though the objects are not equal For a TreeSet this means that only one of those objects can be in the set For example if the TreeSet contains mailing addresses and if the compareTo method for addresses just compares their zip codes then the set can contain only one address in each zip code Clearly this is not right But that only means that you have to be aware of the semantics of TreeSets and you need to make sure that compareTo is defined in a reasonable way for objects that you put into a TreeSet This will be true by the way for Strings Integers and many other built in types since the compareTo method for these types considers two objects to be the same only if they are actually equal In the implementation of a TreeSet the elements are stored in something similar to a binary sort tree See Subsection 9 4 2 However the data structure that is used is balanced in the sense that all the leaves of the tree are at about the same distance from the root of the tree This ensures that all the basic operations inserting deleting and searching are efficient with worst case run time Θ log n where n is the number of items in the set The fact that a TreeSet sorts its elements and removes duplicates makes it very useful in some applications Exercise 7 7 asked you to write a program that would read a file and output an alphabetical list of all the words that occurred in the file with duplicates removed The words were to be stored in an ArrayList so it was up to you to make sure that the list was sorted and contained no duplicates The same task can be programmed much more easily using a TreeSet instead of a list A TreeSet automatically eliminates duplicates and an iterator for the set will automatically visit the items in the set in sorted order An algorithm for the program using a TreeSet would be TreeSet String words new TreeSet String while there is more data in the input file Let word the next word from the file Convert word to lower case words add word Adds the word only if not already present for String w words for each String w in words Output w words are output in sorted order If you would like to see a complete working program you can find it in the file WordListWithTreeSet java As another example suppose that coll is any Collection of Strings This would also work for any other type for which compareTo is properly defined We can use a TreeSet to sort the items of coll and remove the duplicates simply by saying TreeSet String set new TreeSet String set addAll coll The second statement adds all the elements of the collection to the set Since it s a Set duplicates are ignored Since it s a TreeSet the elements of the set are sorted If you would like to have the data in some other type of data structure it s easy to copy the data from the set For example to place the answer in an ArrayList you could say TreeSet String set new TreeSet String set addAll coll ArrayList String list new ArrayList String list addAll set Now in fact every one of Java s collection classes has a constructor that takes a Collection as an argument All the items in that Collection are added to the new collection when it is created So if coll is of type Collection String then new TreeSet String coll creates a TreeSet that contains the same elements as coll but with duplicates removed and in sorted order This means that we can abbreviate the four lines in the above example to the single command ArrayList String list new ArrayList String new TreeSet String coll This makes a sorted list of the elements of coll with no duplicates Although the repeated type parameter String makes it a bit ugly to look at this is still a nice example of the power of generic programming A HashSet stores its elements in a hash table a type of data structure that I will discuss in the next section The operations of finding adding and removing elements are implemented very efficiently in hash tables even more so than for TreeSets The elements of a HashSet are not stored in any particular order and so do not need to implement the Comparable interface They do however need to define a proper hash code as we ll see in the next section The equals method is used to determine whether two objects in a HashSet are to be considered the same An Iterator for a HashSet will visit its elements in what seems to be a completely arbitrary order and it s possible for the order to change completely when a new element is added Use a HashSet instead of a TreeSet when the elements it contains are not comparable or when the order is not important or when the small advantage in efficiency is important A note about the mathematics of sets In mathematical set theory the items in a set are called members or elements of that set Important operations include adding an element to a set removing an element from a set and testing whether a given entity is an element of a set Operations that can be performed on two sets include union intersection and set difference All these operations are defined in Java for objects of type Set but with different names Suppose that A and B are Sets Then A add x adds the element x to the set A A remove x removes the element x from the set A A contains x tests whether x is an element of the set A A addAll B computes the union of A and B A retainAll B computes the intersection of A and B A removeAll B computes the set difference A B There are of course differences between mathematical sets and sets in Java Most important perhaps sets in Java must be finite while in mathematics most of the fun in set theory comes from working with infinity In mathematics a set can contain arbitrary elements while in Java a set of type Set T can only contain elements of type T The operation A addAll B acts by modifying the value of A while in mathematics the operation A union B computes a new set without changing the value of A or B See Exercise 10 2 for an example of mathematical set operations in Java 10 2 4 EnumSet Enumerated types or enums were introduced in Subsection 2 3 4 Suppose that E is an enumerated type Since E is a class it is possible to create objects of type TreeSet E and HashSet E However because enums are so simple trees and hash tables are not the most efficient implementation for sets of enumerated type values Java provides the class java util EnumSet as an alternative way to create such sets Sets of enumerated type values are created using static methods in the class EnumSet For example if e1 e2 and e3 are values belonging to the enumerated type E then the method EnumSet of e1 e2 e3 creates and returns a set of type EnumSet E that contains exactly the elements e1 e2 and e3 The set implements the interface Set E so all the usual set and collection operations are available The implementation of these operations is very efficient The implementation uses what is called a bit vector A bit is a quantity that has only two possible values zero and one A set of type EnumSet E is represented by a bit vector that contains one bit for each enum constant in the enumerated type E the bit corresponding to the enum constant e is 1 if e is a member of the set and is 0 if e is not a member of the set The bit vectors for two sets of type EnumSet E can be very easily combined to represent such operations as the union and intersection of two sets The bit vector representation is feasible for EnumSets but not for other sets in Java because an enumerated type contains only a small finite number of enum constants Java actually has a class named BitSet that uses bit vectors to represent finite sets of non negative integers

    Original URL path: http://math.hws.edu/javanotes/c10/s2.html (2016-02-07)
    Open archived version from archive