Math 121: Introduction to Computing Handout #22 The Demo Programs in Folder Assignment5 A. Arrays. The concept of an array as a linear list of data, i.e., as the programming manifestation of a list, is not a difficult one. There is some new syntax associated with arrays, but that also should come easily. In learning about arrays, the harder concepts to master are 1. How arrays are represented internally. Understanding the internal representation of arrays is important for building your intuition about how array parameters work. 2. How to use arrays effectively in applications. Even though the mechanics of arrays are simple, it may not always be apparent when to use them. For applications that involve lists of data values, arrays come up naturally. There are, however, several circumstances in which the idea of using an array is harder to see. The Roberts text includes an extensive discussion of the representation of arrays. This handout focuses on the second question in the context of a specific application that uses arrays in two rather different contexts. The program LetterFrequency.java creates a table of the frequency of letters appearing in a text file. Such a program could be used in solving cryptograms, simple letter-substitution ciphers in which each letter in the plaintext message is replaced by some other letter. As an example, given a file containing the following cryptogram: UTK UR VAKGK LKT NG HKTNBG VU VAK UVAKE; QTF GU UR VAKGK. MANIA NG VAK TQVBEQO LQT, QTF MANIA VAK GXNENV? MAU FKINXAKEG VAKL? -- GAQZKGXKQEK, IULKFY UR KEEUEG the LetterFrequency program should produce the following output for this file:– 2 – This program takes account of the following requirements: • The program should count only the letters in the file. All other characters should be ignored. • The program should ignore the case of each letter. Thus, if the file contains both an uppercase A and a lowercase a, the program should treat them as the same letter and make two entries in the corresponding counting array. • The report at the end should be in order by letter and should not include any letters that do not appear in the cryptogram. Letter-frequency programs are useful because they suggest what letters in the cryptogram might correspond to the most common letters in English. For example, in the sample run above, the characters K, A, and G each occur frequently and therefore might represent letters such as E or T in the original. The program List.java illustrates by toy example how a FORTRAN programmer would implement list-management and garbage collection in the bad old days. Here the data are characters, so that part of memory is allocated as an array of characters. A second array, of integers, encodes the list of character array entries that is in use, and the list of character array entries that is free. Finally, individual integers point to the heads of the two lists. Since array indexing starts at 0, the value -1 connotes a null pointer. B. The ArrayList and HashMap Classes Most of the power associated with modern, object-oriented languages such as Java does not come from the language itself but instead derives from the vast array of standard library classes that accompanies the language itself. For Java, that set of libraries is called the Java Development Kit, or JDK for short. The two classes ArrayList and HashMap form part of a much larger structure called the Java Collections Framework, which was added to the JDK as part of release 1.2 (we’re now up to JDK version 1.5). As its name implies, the Java Collections Framework is designed to make it easier for programmers to work with collections of data of various kinds. The ArrayList class is designed to make it easier to work with ordered lists of data without having to take account of the low-level details of arrays. The HashMap class provides the ability to organize a collection, not by a linear order, but rather by setting up an association between a set of keys and a corresponding set of values. Given any class in a toolkit like the JDK, it is possible to understand that class from a variety of perspectives. From a holistic perspective, each class is defined in terms by its abstract behavior. In this view, the important information about a class consists of the public methods it exports and a high-level model of what those methods do. From a reductionistic perspective, on the other hand, a class is defined in terms of its underlying implementation. At this level, the important information lies in the actual code for the methods it contains. If you are creating a class, you need to be concerned about each of these perspectives. In the more likely case that you are using a class as a tool, you can limit yourself to the more holistic, abstract view. In programming parlance, code that– 3 – makes use of a class—and by extension the programmers who write that code—are called clients of that class. As a general rule, clients can remain blissfully ignorant of the implementation of a class and concentrate solely on the abstraction it presents to the outside world. In Math 121, our primary concern is to learn how to use classes as clients, but the algorithms and data structures course will look more deeply into how these classes are implemented and how clever algorithms make them as efficient as possible. The ArrayList class A detailed description of this class appears in the Roberts text. The most important methods for the ArrayList class appear in Figure 10-4. This handout focuses on the relative advantages and disadvantages of ArrayLists with respect to Java arrays and, more specifically, the complexity of using wrapper classes to store primitive data values in an ArrayList. The most important advantages that ArrayLists offer over arrays are the following: • An ArrayList can change its size dynamically without forcing the client to take care of the details. Once allocated, an array has a fixed length. Although it is possible to simulate the behavior of an ArrayList by reallocating a new array with the desired size and reassigning that value to the array