```The Art and Science of
CHAPTER 11
Arrays and ArrayLists
Little boxes, on a hillside, little boxes made of ticky-tacky
Little boxes, little boxes, little boxes, all the same
There’s a green one and a pink one and a blue one and a yellow one
And they're all made out of ticky-tacky and they all look just the same
—Malvina Reynolds, “Little Boxes,” 1962
11.1
11.2
11.3
11.4
11.5
11.6
11.7
11.8
Introduction to arrays
Internal representation of arrays
Passing arrays as parameters
Using arrays for tabulation
Initialization of arrays
Multidimensional arrays
Image processing
The ArrayList class
ERIC S. ROBERTS
Java
An Introduction
to Computer Science
Introduction to Arrays
• An array is a collection of individual data values with two
distinguishing characteristics:
1. An array is ordered. You must be able to count off the
values: here is the first, here is the second, and so on.
2. An array is homogeneous. Every value in the array must
have the same type.
• The individual values in an array are called elements. The
type of those elements (which must be the same because
arrays are homogeneous) is called the element type. The
number of elements is called the length of the array.
• Each element is identified by its position number in the array,
which is called its index. In Java, index numbers always
begin with 0 and therefore extends up to one less than the
length of the array.
Declaring an Array Variable
• As with any other variable, array variables must be declared
before you use them. In Java, the most common syntax for
declaring an array variable looks like this:
type[] name = new type[n];
where type is the element type, name is the array name, and n
is an integer expression indicating the number of elements.
• This declaration syntax combines two operations. The part of
the line to the left of the equal sign declares the variable; the
part to the right creates an array value with the specified
number of elements and then assigns it to the array variable.
• Even though the two operations are distinct, it will help you
avoid errors if you make a habit of initializing your arrays
when you declare them.
An Example of Array Declaration
• The following declaration creates an array called intArray
consisting of 10 values of type int:
int[] intArray = new int[10];
• This easiest way to visualize arrays is to think of them as a
linear collection of boxes, each of which is marked with its
index number. You might therefore diagram the intArray
variable by drawing something like this:
intArray
0
0
0
0
0
0
0
0
0
0
0
1
2
3
4
5
6
7
8
9
• Java automatically initializes each element of a newly created
array to its default value, which is zero for numeric types,
false for values of type boolean, and null for objects.
Array Selection
• Given an array such as the intArray variable at the bottom
of this slide, you can get the value of any element by writing
the index of that element in brackets after the array name.
This operation is called selection.
• You can, for example, select the initial element by writing
intArray[0]
• The result of a selection operation is essentially a variable. In
particular, you can assign it a new value. The following
statement changes the value of the last element to 42:
intArray[9] = 42;
intArray
0
0
0
0
0
0
0
0
0
0
42
0
1
2
3
4
5
6
7
8
9
Cycling through Array Elements
• One of the most useful things about array selection is that the
index does not have to be a constant. In many cases, it is
useful to have the index be the control variable of a for loop.
• The standard for loop pattern that cycles through each of the
array elements in turn looks like this:
for (int i = 0; i < array.length; i++) {
Operations involving the ith element of the array
}
Selecting the length field returns the number of elements.
• As an example, you can reset every element in intArray to
zero using the following for loop:
for (int i = 0; i < intArray.length; i++) {
intArray[i] = 0;
}
Exercise: Summing an Array
Write a method sumArray that takes an array of integers and
returns the sum of those values.
/**
* Calculates the sum of an integer array.
* @param array An array of integers
* @return The sum of the values in the array
*/
private int sumArray(int[] array) {
int sum = 0;
for (int i = 0; i < array.length; i++) {
sum += array[i];
}
return sum;
}
• From time to time, the fact that Java starts index numbering at
0 can be confusing. In particular, if you are interacting with a
user who may not be Java-literate, it often makes more sense
to let the user work with index numbers that begin with 1.
• There are two standard approaches for shifting between Java
1. Use Java’s index numbers internally and then add one
whenever those numbers are presented to the user.
2. Use index values beginning at 1 and ignore element 0 in
each array. This strategy requires allocating an additional
element for each array but has the advantage that the
internal and external index numbers correspond.
Arrays and Graphics
• Arrays turn up frequently in graphical programming. Any
time that you have repeated collections of similar objects, an
array provides a convenient structure for storing them.
• As a aesthetically pleasing illustration of both the use of
arrays and the possibility of creating dynamic pictures using
nothing but straight lines, the text presents the YarnPattern
program, which simulates the following process:
–
–
–
–
Place a set of pegs at regular intervals around a rectangular border.
Tie a piece of colored yarn around the peg in the upper left corner.
Loop that yarn around the peg a certain distance DELTA ahead.
Continue moving forward DELTA pegs until you close the loop.
A Larger Sample Run
YarnPattern
The YarnPattern Program
import acm.graphics.*;
import acm.program.*;
import java.awt.*;
/**
* This program creates a pattern that simulates the process of
* winding a piece of colored yarn around an array of pegs along
* the edges of the canvas.
*/
public class YarnPattern extends GraphicsProgram {
public void run() {
initPegArray();
int thisPeg = 0;
int nextPeg = -1;
while (thisPeg != 0 || nextPeg == -1) {
nextPeg = (thisPeg + DELTA) % N_PEGS;
GPoint p0 = pegs[thisPeg];
GPoint p1 = pegs[nextPeg];
GLine line = new GLine(p0.getX(), p0.getY(), p1.getX(), p1.getY());
line.setColor(Color.MAGENTA);
thisPeg = nextPeg;
}
}
page 1 of 2
skip code
The YarnPattern Program
/*
Initializes
the array of pegs */
import
acm.graphics.*;
private
void
initPegArray() {
import acm.program.*;
pegIndex = 0;
importint
java.awt.*;
for (int i = 0; i < N_ACROSS; i++) {
pegs[pegIndex++] = new GPoint(i * PEG_SEP, 0);
/**
} program creates a pattern that simulates the process of
* This
for (int
i = 0;
< N_DOWN;
{ an array of pegs along
* winding
a piece
of icolored
yarni++)
around
pegs[pegIndex++]
= new GPoint(N_ACROSS * PEG_SEP, i * PEG_SEP);
* the edges
of the canvas.
}
*/
(intYarnPattern
i = N_ACROSS;
i > 0;
i--) {
publicfor
class
extends
GraphicsProgram
{
pegs[pegIndex++] = new GPoint(i * PEG_SEP, N_DOWN * PEG_SEP);
}
public
void run() {
for
(int i = N_DOWN; i > 0; i--) {
initPegArray();
= new GPoint(0, i * PEG_SEP);
intpegs[pegIndex++]
thisPeg = 0;
}int nextPeg = -1;
} while (thisPeg != 0 || nextPeg == -1) {
= (thisPeg
+ DELTA) % N_PEGS;
/* PrivatenextPeg
constants
*/
GPoint
p0
=
pegs[thisPeg];
private static final int DELTA = 67;
/* How many pegs to advance
*/
= pegs[nextPeg];
privateGPoint
staticp1final
int PEG_SEP = 10; /* Pixels separating each peg
*/
GLine
line
=
new
GLine(p0.getX(),
p0.getY(),
p1.getX(),
p1.getY());
private static final int N_ACROSS = 50; /* Pegs across (minus a corner) */
privateline.setColor(Color.MAGENTA);
static final int N_DOWN = 30;
/* Pegs down (minus a corner)
*/
private static final int N_PEGS = 2 * N_ACROSS + 2 * N_DOWN;
thisPeg = nextPeg;
}
/* Private
instance variables */
}
private
GPoint[] pegs = new GPoint[N_PEGS];
}
page 2 of 2
A Digression on the ++ Operator
• The YarnPattern program illustrates a new form of the ++
operator in the various statements with the following form:
pegs[pegIndex++] = new GPoint(x, y);
• The pegIndex++ expression adds one to pegIndex just as
if has all along. The question is what value is used as the
index, which depends on where the ++ operator appears:
– If the ++ operator comes after a variable, the variable is incremented
after the value of the expression is determined. Thus, in this example,
the expression pegs[pegIndex++] therefore selects the element of
the array at the current value of pegIndex and then adds one to
pegIndex afterwards, which moves it on to the next index position.
– If the ++ operator comes before a variable, the variable is incremented
first and the new value is used in the surrounding context.
• The -- operator behaves similarly but subtracts one from the
Internal Representation of Arrays
• Arrays in Java are implemented as objects, which means that
they are stored in the heap. The value stored in an array
variable is simply a reference to the actual array.
• Consider, for example, the following declaration:
double[] scores = new double[5];
• The variable scores is allocated on the stack and is assigned
the address of a newly allocated array in the heap:
heap
stack
1000
length
5
1004
scores[0]
0.0
1008
scores[1]
0.0
1010
scores[2]
0.0
1018
scores[3]
0.0
1020
scores[4]
0.0
1028
scores
1000
FFFC
Passing Arrays as Parameters
• When you pass an array as a parameter to a method or return
a method as a result, only the reference to the array is actually
passed between the methods.
• The effect of Java’s strategy for representing arrays internally
is that the elements of an array are effectively shared between
the caller and callee. If a method changes an element of an
array passed as a parameter, that change will persist after the
method returns.
• The next slide contains a simulated version of a program that
performs the following actions:
1. Generates an array containing the integers 0 to N-1.
2. Prints out the elements in the array.
3. Reverses the elements in the array.
4. Prints out the reversed array on the console.
The ReverseArray Program
public void run() {
int n = readInt("Enter number of elements: ");
private String
arrayToString(int[]
array)
int[]reverseArray(int[]
void
createIndexArray(int
array)
n) {{ {
int[]
intArray
=
createIndexArray(n);
String
str
int[]
for
(int
array
i =
=="";
0;
new
i <
int[n];
array.length / 2; i++) {
println("Forward:
"
+
arrayToString(intArray));
private
void
swapElements(int[]
array,
p1, int p2) {
for
(int
i++)int
{
forswapElements(array,
( intii==0;
0;ii<<array.length;
n;i,
i++
array.length
) {
- i - 1);
reverseArray(intArray);
int temp
array[p1];
(i > =0)
str += ", ";
} if
array[i]
= i;
println("Reverse:
" + arrayToString(intArray));
array[p1]
= array[p2];
str += array[i];
} }
n
intArray
} array[p2] = temp;
}
return array;
in
array
i
array
} return "[" + str + "]";
10
temp
p1
p2
array
}
}
5
4
3
2
1
0
10
0123456789
str
i 109
array
0
0
0, 1,
0,
1 2,
2 3,
3 4,
4 5,
5 6,
6 7,
7 8,
8 9
10
0123456789
09
180
270
063
054
540
630
720
810
09
0
1
2
3
4
5
6
7
8
9
ReverseArray
Enter number of elements: 10
Forward: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Reverse: [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
skip simulation
Using Arrays for Tabulation
• Arrays turn out to be useful when you have a set of data
values and need to count how many values fall into each of a
set of ranges. This process is called tabulation.
• Tabulation uses arrays in a slightly different way from those
applications that use them to store a list of data. When you
implement a tabulation program, you use each data value to
compute an index into an integer array that keeps track of
how many values fall into that category.
• The example of tabulation used in the text is a program that
counts how many times each of the 26 letters appears in a
sequence of text lines. Such a program would be very useful
in solving codes and ciphers, as described on the next slide.
Cryptograms
• A cryptogram is a puzzle in which a message is encoded by
replacing each letter in the original text with some other letter.
The substitution pattern remains the same throughout the
message. Your job in solving a cryptogram is to figure out
this correspondence.
• The usual strategy for solving a cryptogram is to assume that
the most common letters in the coded message correspond to
the most common letters in English, which are E, T, A, O, I, N,
S, H, R, D, L, and U.
• Instead of counting each of the characters by hand, it would
make things easier if you had a program to do the job. You
type in the coded message, and out pops a table showing how
often each letter appears.
Implementation Strategy
The basic idea behind the program to count letter frequencies is
to use an array with 26 elements to keep track of how many times
each letter appears. As the program reads the text, it increments
the array element that corresponds to each letter.
T W AS
BR I L L IG
01 01 0 0 0 0 10 0 210 0 0 120 0 0 0 0 0 01 10 10 0 0 01 0 0 0
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
CountLetterFrequencies
import acm.program.*;
/**
* This program creates a table of the letter frequencies in a
* paragraph of input text terminated by a blank line.
*/
public class CountLetterFrequencies extends ConsoleProgram {
public void run() {
println("This program counts letter frequencies.");
println("Enter a blank line to indicate the end of the text.");
initFrequencyTable();
while (true) {
if (line.length() == 0) break;
countLetterFrequencies(line);
}
printFrequencyTable();
}
/* Initializes the frequency table to contain zeros */
private void initFrequencyTable() {
frequencyTable = new int[26];
for (int i = 0; i < 26; i++) {
frequencyTable[i] = 0;
}
}
page 1 of 2
skip code
CountLetterFrequencies
import
acm.program.*;
/*
Counts
the letter frequencies in a line of text */
private void countLetterFrequencies(String line) {
/**
for (int i = 0; i < line.length(); i++) {
* This program
a table of the letter frequencies in a
char ch creates
= line.charAt(i);
* paragraph of input text terminated by a blank line.
if (Character.isLetter(ch)) {
*/
int index = Character.toUpperCase(ch) - 'A';
public class CountLetterFrequencies extends ConsoleProgram {
frequencyTable[index]++;
public} void run() {
}println("This program counts letter frequencies.");
} println("Enter a blank line to indicate the end of the text.");
initFrequencyTable();
while the
(true)
{
/* Displays
frequency
table */
String
line
=
private void printFrequencyTable() {
(line.length()
break;
for if
(char
ch = 'A'; ch==<=0)'Z';
ch++) {
countLetterFrequencies(line);
int index = ch - 'A';
} println(ch + ": " + frequencyTable[index]);
}printFrequencyTable();
}}
/* Private
Initializes
the frequency
to contain zeros */
/*
instance
variables table
*/
private int[]
void initFrequencyTable()
{
private
frequencyTable;
frequencyTable = new int[26];
for (int i = 0; i < 26; i++) {
}
frequencyTable[i] = 0;
}
}
page 2 of 2
skip code
Initializing Arrays
• Java makes it easy to initialize the elements of an array as part
of a declaration. The syntax is
type[] name = { elements };
where elements is a list of the elements of the array separated
by commas. The length of the array is automatically set to be
the number of values in the list.
• For example, the following declaration initializes the variable
powersOfTen to the values 100, 101, 102, 103, and 104:
int[] powersOfTen = { 1, 10, 100, 1000, 10000 };
This declaration creates an integer array of length 5 and
initializes the elements as specified.
Constant Lookup Tables
• One of the most common applications of array initialization is
to create constant arrays used to look up a value by its index
number. Such arrays are called lookup tables.
• As an example, suppose that you are using the integers 1
through 12 to represent the names of the months from January
to December. You can easily convert these integers to the
corresponding month name by declaring the following table:
private static String[] MONTH_NAMES = {
null /* Included because there is no month #0 */,
"January", "February", "March", "April",
"May", "June", "July", "August",
"September", "October", "November", "December"
};
You can then use the expression MONTH_NAMES[month] to
convert a numeric month to its name.
Multidimensional Arrays
• Because the elements of an array can be of any Java type,
those elements can themselves be arrays. Arrays of arrays are
called multidimensional arrays.
• In Java, you can create a multidimensional array by using
multiple brackets in both the type and the initialization parts
of the declaration. For example, you can create array space
for a 3 x 3 tic-tac-toe board using the following declaration:
char[][] board = new char[3][3];
• This declaration creates a two-dimensional array of characters
that is organized like this:
board[0][0] board[0][1] board[0][2]
board[1][0] board[1][1] board[1][2]
board[2][0] board[2][1] board[2][2]
Initializing Multidimensional Arrays
• You can initialize a multidimensional array when you declare
it by using nested braces to reflect the levels of array nesting.
• For example, you can declare and initialize a multiplication
table for the digits 0 to 9 like this:
private static int[][] MULTIPLICATION_TABLE = {
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 },
{ 0, 2, 4, 6, 8, 10, 12, 14, 16, 18 },
{ 0, 3, 6, 9, 12, 15, 18, 21, 24, 27 },
{ 0, 4, 8, 12, 16, 20, 24, 28, 32, 36 },
{ 0, 5, 10, 15, 20, 25, 30, 35, 40, 45 },
{ 0, 6, 12, 18, 24, 30, 36, 42, 48, 56 },
{ 0, 7, 14, 21, 28, 35, 42, 49, 56, 63 },
{ 0, 8, 16, 24, 32, 40, 48, 56, 64, 72 },
{ 0, 9, 18, 27, 36, 45, 54, 63, 72, 81 }
};
Exercise: Multidimensional Arrays
Write a single Java statement that declares and initializes a twodimensional array named chessboard so that the array contains
a representation of the initial position in a game of chess:
The individual elements should be characters using the standard
symbols for the pieces:
Solution: Chessboard Problem
private char[][] chessboard = {
{ 'r', 'n', 'b', 'q', 'k', 'b',
{ 'p', 'p', 'p', 'p', 'p', 'p',
{ ' ', ' ', ' ', ' ', ' ', ' ',
{ ' ', ' ', ' ', ' ', ' ', ' ',
{ ' ', ' ', ' ', ' ', ' ', ' ',
{ ' ', ' ', ' ', ' ', ' ', ' ',
{ 'P', 'P', 'P', 'P', 'P', 'P',
{ 'R', 'N', 'B', 'Q', 'K', 'B',
};
'n',
'p',
' ',
' ',
' ',
' ',
'P',
'N',
'r'
'p'
' '
' '
' '
' '
'P'
'R'
},
},
},
},
},
},
},
},
Image Processing
• Suppose that you have a file
named JTFLogo.gif containing
the logo for the ACM Java Task
Force shown on the right.
• As you know from the discussion
of the GImage class in Chapter 9,
the image actually consists of a
set of pixels arranged in a twodimensional array, as shown in
the expanded image.
• The GImage class allows you to
convert the data for the image
into a two-dimensional array of
pixel values. Once you have this
array, you can work with the data
to change the image.
Pixel Arrays
• If you have a GImage object, you can obtain the underlying
pixel array by calling the getPixelArray, which returns a
two-dimensional array of type int.
• For example, if you wanted to get the pixels from the image
file JTFLogo.gif, you could do so with the following code:
GImage logo = new GImage("JTFLogo.gif");
int[][] pixels = logo.getPixelArray();
• The first subscript in a pixel array selects a row in the image,
beginning at the top. The height of the image is therefore
given by the expression pixels.length.
• The second subscript in a pixel array selects an individual
pixel within a row, beginning at the left. You can use the
expression pixels[0].length to determine the width of
the image.
Pixel Values
• Each individual element in a pixel array is an int in which
the 32 bits are interpreted as follows:
1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1
transparency ()
red
green
blue
• The first byte of the pixel value specifies the transparency of
the color, which is described in more detail on the next slide.
• The next three bytes indicate the amount of red, green, and
blue in the pixel, in which each value varies from 0 to 255.
Together, these three bytes form the RGB value of the color,
which is typically expressed using six hexadecimal digits.
The color in the example has the RGB value 0x996633,
which is a light brown:
Transparency
• The first byte of the pixel value specifies the transparency of
the color, which indicates how much of the background
shows through. This value is often denoted using the Greek
letter alpha ().
• Transparency values vary from 0 to 255. The value 0 is used
to indicate a completely transparent color in which only the
background appears. The value 255 indicates an opaque color
that completely obscures the background. The standard color
constants all have alpha values of 255.
• Fully transparent colors are particularly useful in
images, because they make it possible to display
images that do not have rectangular outlines. For
example, if the gray pixels in the corners of the
JTFLogo.gif image have an alpha value of 0, the
background will show through those parts of the logo.
Image Manipulation
• You can use the facilities of the GImage class to manipulate
images by executing the following steps:
1.
2.
3.
4.
Read an existing image from a file into a GImage object.
Call getPixelArray to get the pixels.
Write the code to manipulate the pixel values in the array.
Call the GImage constructor to create a new image.
• The program on the next slide shows how you can apply this
technique to flip an image vertically. The general strategy for
inverting the image is simply to reverse the elements of the
pixel array, using the same technique as the reverseArray
method on an earlier slide.
The FlipVertical Program
public void run() {
GImage original = new GImage("Candle.gif");
private GImage flipVertical(GImage image) {
GImage flipped = flipVertical(original);
int[][] array = image.getPixelArray();
double y = (getHeight() - original.getHeight()) / 2;
int height = array.length;
double x1 = (getWidth() - IMAGE_SEP) / 2;
for (int p1 = 0; p1 < height / 2; p1++) {
double x0 = x1 - original.getWidth() - IMAGE_SEP;
int p2 = height - p1 - 1;
int[] temp = array[p1];
flipped
original
array[p1] = array[p2];
}
array[p2] = temp;
x0
x1
y
array
image
}
164
305
24
return new GImage(array);
height
}
100
FlipVertical
skip simulation
Bitwise Operators
• If you need to change the colors of individual pixels inside a
pixel array, you need to learn about Java’s operators for
working with individual bits in the binary representation of an
integer. These operators are called the bitwise operators.
• The bitwise operators are summarized in the following table
and then described in more detail on the next few slides:
x & y
Bitwise AND. The result has a 1 bit wherever both x and y have 1s.
x | y
Bitwise OR. The result has a 1 bit wherever either x or y have 1s.
x ^ y
Exclusive OR. The result has a 1 bit wherever x and y differ.
~x
Bitwise NOT. The result has a 1 bit wherever x has a 0.
x << n Left shift. Shift the bits in x left n positions, shifting in 0s.
x >> n Right shift (arithmetic). Shift x right n bits, preserving the sign.
x >>> n Right shift (logical). Shift x right n bits, shifting in 0s.
The Bitwise AND Operator
• The bitwise AND operator (&) takes two integer
operands, x and y, and computes a result that has
a 1 bit in every position in which both x and y
have 1 bits. A table for the & operator appears to
the right.
0
1
0 0
0
1 0
1
• The primary application of the & operator is to select certain
bits in an integer, clearing the unwanted bits to 0. This
• For example, you can select the blue component of a pixel
values by ANDing the complete value with 0xFF, as follows:
1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1
& 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1
The Bitwise OR Operator
• The bitwise OR operator (|) takes two integer
operands, x and y, and computes a result that has
a 1 bit in every position in which either x or y has
a 1 bit, as shown in the table on the right.
0
1
0 0
1
1 1
1
• The primary use of the | operator is to assemble a single
integer value from other values, each of which contains a
subset of the desired bits.
• As an example, you can use the | operator to convert an RGB
value into an opaque pixel value by ORing the 24-bit RGB
value with 0xFF000000, as follows:
0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1
| 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1
The Exclusive OR Operator
• The exclusive OR or XOR operator (^) takes two
integer operands, x and y, and computes a result
that has a 1 bit in every position in which x and y
have different bit values, as shown on the right.
0
1
0 0
1
1 1
0
• The XOR operator has many applications in programming,
most of which are beyond the scope of this text.
• As an example, you can use XOR to create a complementary
color for a given RGB value by XORing it with 0xFFFFFF:
1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1
^ 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 1 0 0 1 1 0 1 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0
• Complementing a color twice restores the original color.
The Bitwise NOT Operator
• The bitwise NOT operator (~) takes a single operand x and
returns a value that has a 1 wherever x has a 0, and vice versa.
• You can use the bitwise NOT operator to create a mask in
which you mark the bits you want to eliminate as opposed to
the ones you want to preserve.
• For example, the expression ~0xFF creates a mask that clears
the blue component of a color. The mask looks like this:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
• You can then use this mask to clear the blue byte in a color:
1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1
& 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0
The Shift Operators
• Java defines three operators that have the effect of shifting the
bits in a word by a given number of bit positions.
• The expression x << n shifts the bits in the integer x leftward
n positions. Spaces appearing on the right are filled with 0s.
• The expressions x >> n and x >>> n both shift the bits in the
integer x rightward n positions. The difference between the
two operators lies only in the bit value shifted in as empty
spaces appear on the left.
• The >> operator performs what computer scientists call an
arithmetic shift in which the leading bit in the value of x
never changes. Thus, if the first bit is a 1, the >> operator
fills spaces with 1s; if it is a 0, the spaces are filled with 0s.
• The >>> operator performs a logical shift in which the spaces
appearing at the left are always filled with 0s.
Exercise: Shift Operators
Suppose that the integer variable pixel contains the following
bit pattern, which corresponds to a light-brown color:
1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1
1. What is the value of pixel << 2?
1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1 0 0
2. What is the value of pixel >> 8?
1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1
3. What is the value of pixel >>> 24?
0 0 0 1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1
Manipulating Pixel Values
• The bitwise operators make it possible to work with the
components of a pixel value. For example, the expression
(pixel >> 16) & 0xFF isolates the red component:
1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 1 0 1 1 0 0 1 1 0 0 0 1 1 0 0 1 1
1 1 1 1 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 1
0 0 0 1
0 1
0 0 0 1
0 0 1
0 1
0 0 0 1
0 1
0 0 0
1 0 1
0 1 0
1 0 1
0 1
0 0 variables
0 0 0 0 0 0
0 0 0b 0hold
0 0 0the
0 0individual
0 0 0 0 1 RGB
1 1 1 values,
1 1 1 1
• If0 the
r,0g0, and
you can use the following expression to compute the pixel
value for the corresponding opaque color:
(0xFF << 24) | (r << 16) | (g << 8) | b
• The GImage class exports several static methods to support
this style of pixel manipulation, as shown on the next slide.
Static Methods in GImage
/** Returns the alpha component from an RGB value. */
public static int getAlpha(int pixel) {
return (pixel >> 24) & 0xFF;
}
/** Returns the red component from an RGB value. */
public static int getRed(int pixel) {
return (pixel >> 16) & 0xFF;
}
/** Returns the green component from an RGB value. */
public static int getGreen(int pixel) {
return (pixel >> 8) & 0xFF;
}
/** Returns the blue component from an RGB value. */
public static int getBlue(int pixel) {
return pixel & 0xFF;
}
/** Creates an opaque pixel value from the color components */
public static int createRGBPixel(int r, int g, int b) {
return createRGBPixel(r, g, b, 0xFF);
}
/** Creates a pixel value from the color components, including alpha */
public static int createRGBPixel(int r, int g, int b, int alpha) {
return (alpha << 24) | (r << 16) | (g << 8) | b;
}
Creating a Grayscale Image
• As an illustration of how to use the bitwise operators to
manipulate colors in an image, the text implements a method
called createGrayscaleImage that converts a color image
into a black-and-white image, as shown in the sample run at
the bottom of this slide.
• The code to implement this method appears on the next slide.
CreateGrayscale
The CreateGrayscale Program
/* Creates a grayscale version of the original image */
private GImage createGrayscaleImage(GImage image) {
int[][] array = image.getPixelArray();
int height = array.length;
int width = array[0].length;
for (int i = 0; i < height; i++) {
for (int j = 0; j < width; j++) {
int pixel = array[i][j];
int r = GImage.getRed(pixel);
int g = GImage.getGreen(pixel);
int b = GImage.getBlue(pixel);
int xx = computeLuminosity(r, g, b);
array[i][j] = GImage.createRGBPixel(xx, xx, xx);
}
}
return new GImage(array);
}
/* Calculates the luminosity of a pixel using the NTSC formula */
private int computeLuminosity(int r, int g, int b) {
return GMath.round(0.299 * r + 0.587 * g + 0.114 * b);
}
The ArrayList Class
• Although arrays are conceptually important as a data
structure, they are not used as much in Java as they are in
most other languages. The reason is that the java.util
package includes a class called ArrayList that provides the
standard array behavior along with other useful operations.
• The main differences between Java arrays and ArrayLists
stem from the fact that ArrayList is a Java class rather than
a special form in the language. As a result, all operations on
ArrayLists are indicated using method calls. For example,
the most obvious differences include:
– You create a new ArrayList by calling the ArrayList constructor.
– You get the number of elements by calling the size method rather
than by selecting a length field.
– You use the get and set methods to select individual elements.
• The next slide summarizes the most important methods in the
ArrayList class. The notation <T> indicates the base type.
Methods in the ArrayList Class
Adds a new element to the end of the ArrayList; the return value is always true.
Inserts a new element into the ArrayList before the position specified by index.
<T> remove(int index)
Removes the element at the specified position and returns that value.
boolean remove(<T> element)
Removes the first instance of element, if it appears; returns true if a match is found.
void clear()
Removes all elements from the ArrayList.
int size()
Returns the number of elements in the ArrayList.
<T> get(int index)
Returns the object at the specified index.
<T> set(int index, <T> value)
Sets the element at the specified index to the new value and returns the old value.
int indexOf(<T> value)
Returns the index of the first occurrence of the specified value, or -1 if it does not appear.
boolean contains(<T> value)
Returns true if the ArrayList contains the specified value.
boolean isEmpty()
Returns true if the ArrayList contains no elements.
Generic Types in Java 5.0
• The <T> notation used on the preceding slide is a new feature
of Java that was introduced with version 5.0 of the language.
In the method descriptions, the <T> notation is a placeholder
for the element type used in the array. Class definitions that
include a type parameter are called generic types.
• When you declare or create an ArrayList, it is a good idea
to specify the element type in angle brackets. For example, to
declare and initialize an ArrayList called names that
contains elements of type String, you would write
ArrayList<String> names = new ArrayList<String>();
• The advantage of specifying the element type is that Java now
knows what type of value the ArrayList contains. When
you call set, Java can ensure that the value matches the
element type. When you call get, Java knows what type of
value to expect, eliminating the need for a type cast.
Boxing and Unboxing
• Generic types benefit substantially from the technique of
boxing and unboxing, which was initially discussed in the
slides for Chapter 7.
• As of Java Standard Edition 5.0, Java automatically converts
values back and forth between a primitive type and the
corresponding wrapper class. This feature makes it possible
to store primitive values in an ArrayList, even though the
elements of any ArrayList must be a Java class.
• For example, suppose that you execute the following lines:
ArrayList<Integer> list = new ArrayList<Integer>();
In the second statement, Java uses boxing to enclose 42 in a
wrapper object of type Integer. When Java executes the
third statement, it unboxes the Integer to obtain the int.
Using ArrayList without Java 5.0
• The ArrayList class is still useful if you don’t have Java 5.0
available, although it is not nearly as convenient.
• Because generic types do not exist in older versions of Java,
the element type for ArrayList is defined to be Object.
Although this strategy means you can store an object of any
class in the ArrayList, you need to cast the result of
methods like get to the desired type.
• Given that older versions of Java also lack automatic boxing
and unboxing, you have to perform these operations yourself:
ArrayList list = new ArrayList();
• The next sets of slides show the implementation of a program
to reverse a list of integers, both with and without Java 5.0.
Reversing an ArrayList (Java 5.0)
import acm.program.*;
import java.util.*;
/**
* This program reads in a list of integers and then displays that list in
* reverse order. This version uses an ArrayList<Integer> to hold the values.
*/
public class ReverseArrayList extends ConsoleProgram {
public void run() {
println("This program reverses the elements in an ArrayList.");
println("Use " + SENTINEL + " to signal the end of the list.");
reverseArrayList(list);
printArrayList(list);
}
/* Reads the data into the list */
ArrayList<Integer> list = new ArrayList<Integer>();
while (true) {
int value = readInt(" ? ");
if (value == SENTINEL) break;
}
return list;
}
page 1 of 2
skip code
Reversing an ArrayList (Java 5.0)
import
acm.program.*;
/*
Prints
the data from the list, one element per line */
import
java.util.*;
private
void printArrayList(ArrayList list) {
for (int i = 0; i < list.size(); i++) {
/**
int value = (Integer) list.get(i);
* This program
reads in a list of integers and then displays that list in
println(value);
* reverse
order. This version uses an ArrayList<Integer> to hold the values.
}
*/}
public class ReverseArrayList extends ConsoleProgram {
/* Reverses
the run()
data in
public void
{ an ArrayList */
private
void reverseArrayList(ArrayList
list) { in an ArrayList.");
println("This
program reverses the elements
for
(int i = 0;
< list.size()
2; i++)the
{ end of the list.");
println("Use
" +i SENTINEL
+ " to/ signal
swapElements(list,
i, =list.size()
- i - 1);
ArrayList<Integer>
list
}reverseArrayList(list);
} printArrayList(list);
}
/* Exchanges two elements in an ArrayList */
void
swapElements(ArrayList
list, int p1, int p2) {
/* private
data
into the list */
int temp
private
ArrayList<Integer>
list.set(p1,
list.get(p2));
ArrayList<Integer>
list = new ArrayList<Integer>();
list.set(p2,
while (true) temp);
{
}
int value = readInt(" ? ");
if (value == SENTINEL) break;
constants */
private
static final int SENTINEL = 0;
}
return list;
} }
page 2 of 2
Reversing an ArrayList (pre 5.0)
import acm.program.*;
import java.util.*;
/**
* This program reverses a list of integers. This version is written
* without Java 5.0 and must therefore do its own boxing and unboxing.
*/
public class ReverseArrayList extends ConsoleProgram {
public void run() {
println("This program reverses the elements in an ArrayList.");
println("Use " + SENTINEL + " to signal the end of the list.");
reverseArrayList(list);
printArrayList(list);
}
/* Reads the data into the list */
ArrayList list = new ArrayList();
while (true) {
int value = readInt(" ? ");
if (value == SENTINEL) break;
}
return list;
}
page 1 of 2
skip code
Reversing an ArrayList (pre 5.0)
import
acm.program.*;
/*
Prints
the data from the list, one element per line */
import
java.util.*;
private
void printArrayList(ArrayList list) {
for (int i = 0; i < list.size(); i++) {
/**
Integer valueAsInteger = (Integer) list.get(i);
* This program
reverses a list of integers. This version is written
println(valueAsInteger.intValue());
* without
Java 5.0 and must therefore do its own boxing and unboxing.
}
*/}
public class ReverseArrayList extends ConsoleProgram {
/* Reverses
the run()
data in
public void
{ an ArrayList */
private
void reverseArrayList(ArrayList
list) { in an ArrayList.");
println("This
program reverses the elements
for
(int i = 0;
< list.size()
2; i++)the
{ end of the list.");
println("Use
" +i SENTINEL
+ " to/ signal
swapElements(list,
i, list.size() - i - 1);
ArrayList
}reverseArrayList(list);
} printArrayList(list);
}
/* Exchanges two elements in an ArrayList */
/* private
data
into the list */
void
swapElements(ArrayList
list, int p1, int p2) {
private
ArrayList
{
Object temp = list.get(p1);
ArrayList list
= new ArrayList();
list.set(p1,
list.get(p2));
while (true) temp);
{
list.set(p2,
int value = readInt(" ? ");
}
if (value == SENTINEL) break;
constants */Integer(value));
}
private
static final int SENTINEL = 0;
return list;
} }
page 2 of 2
The End
Implementation Strategy
The basic idea behind the program to count letter frequencies is
to use an array with 26 elements to keep track of how many times
each letter appears. As the program reads the text, it increments
the array element that corresponds to each letter.
TW AS BR IL L IG
A B C D E F G H I
J
K L
M N O P Q R S T U V W X Y Z
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
```