Java: Learning to Program with Robots 10-3

Java: Learning to Program with Robots 10-3

Chapter 10

Arrays

Chapter Overview

Arrays are one of the fundamental means of structuring large amounts of data. We have touched on structures that act similar to arrays (Strings and ArrayList), but this is where we dive into indexed structures.

We start by assuming we have an array filled with data and examine the kinds of things we can do with it. Only after we’ve proved its usefulness do we bother with the details of creating and filling the array. Later sections deal with dynamic arrays, arrays of primitive types, and multi-dimensional arrays.

This chapter has a large example woven through it rather than including one that stands alone.

Table of Contents

Chapter Overview 1

Table of Contents 1

Chapter Objectives 2

Introduce/Review the Concepts 2

10.1 Using Arrays 2

10.1.1 Visualizing an Array 4

10.1.2 Accessing One Array Element 4

10.1.3 Swapping Array Elements 5

10.1.4 Processing All the Elements in an Array 6

10.1.5 Processing Matching Elements 7

10.1.6 Searching for a Specified Element 8

10.1.7 Finding an Extreme Element 9

10.1.8 Sorting an Array 10

10.1.9 Comparing Arrays and Files 12

10.2 Creating an Array 12

10.1.1 Declaration 13

10.1.2 Allocation 13

10.1.3 Initialization 13

10.3 Passing and Returning Arrays 15

10.4 Dynamic Arrays 17

10.4.1 Partially Filled Arrays 17

10.4.2 Resizing Arrays 18

10.4.3 Combining Approaches 20

10.5 Arrays of Primitive Types 21

Case Study 1: Number of Friends in Common 22

Case Study 2: Distribution of Number of Friends 23

Introduce/Review the Concepts 24

10.6 Multi-Dimensional Arrays 24

10.6.1 2D Array Algorithms 25

10.6.2 Allocating and Initializing a 2D Array 26

10.6.3 Arrays of Arrays 26

10.7 GUI: Animation 27

Summary 29

10.8 Patterns 29

10.9 Summary and Concept Map 30

Assignments 31

Key Terms 31

Chapter Objectives

Introduce/Review the Concepts

10.1 Using Arrays

www.myspace.com is a Web site to network people. An individual may post information about themselves, including pictures, audio clips, blog entries, etc. Online friends are listed, along with their pictures. Friends may also add messages to the web page.
Obviously, there are many lists here:
·  MySpace needs a list of all of the people enrolled.
·  Each person has a list of all their friends, a list of all their blog entries, a list of all the pictures, a list of all the comments their friends have made, etc.
We want to learn how to manipulate lists like this in a Java program. /

The file myspace.txt contains information from 1,500 people with pages at www.myspace.com (with identifiers changed to protect their identity). For each person, the data includes a fictitious name and id number, their actual gender, age, home town, country, date of last login, and a list of their friends (capped at 40).

Teaching Tip

Just for fun, consider generating your own data file with students from your class. The program that crawls MySpace is included in the instructor materials. It’s called HarvestMySpace. There’s a method named anonymize that should be commented out if you want your students to see their actual network. The program currently does not harvest the name.

FYI: The program does a level-order traversal of the friendship tree (graph, actually). The shallowest spanning tree looks roughly as shown on the right. The lowest level is not necessarily completely filled.
For the data provided, the original person has 28 friends listed, 520 friends of friends, and 951 friends of friends of friends. /
We could use an ArrayList for this (if you covered them in Chapter 8). But how is an ArrayList implemented? With one of the more fundamental programming constructs, present in almost every programming language: the array. /

10.1.1 Visualizing an Array

We’ll start assuming we have an array populated with data. We’ll discuss creating arrays and filling them with data later.

Items to discuss:
·  persons is a reference variable.
·  “Fields” are specified with numbers (the index).
·  Index can be a literal or a calculated value (huge advantage!).
·  A public final instance variable, length, says how many elements there are.
·  Index values run between 0 and length-1.
·  It’s easy to specify how many elements should be in the array. /

10.1.2 Accessing One Array Element

The lines of code appear in pairs – the first without arrays and the second the same task with arrays. The conclusion should be that you can do anything with one element in the array that you can do with a simple variable of the same type. /

10.1.3 Swapping Array Elements

Trace this carefully to help students become more familiar with arrays – particularly that they can use variables to access elements. Note the assumption that we are calling a particular method call: swap(1,2). It could just as easily be swap(5, 2). /

10.1.4 Processing All the Elements in an Array

Doing something with all the elements in the array is a common activity. Note that these examples work no matter if there are 4 people in the array or 4 million.
This is the first use of the length instance variable. Point out that both tasks have the same structure to loop over all the elements. /
The foreach loop is a handy shortcut. /

10.1.5 Processing Matching Elements

Quick Quiz
1. Change countMinors to use a for-each loop.
public int countMinors2()
{ int count = 0;
for(Person p : this.persons)
{ if (p.getAge() < 18)
{ count += 1;
}
}
return count;
}
2. Write a method with two parameters, minAge and gender. It prints the names and ages of all the persons who match the gender and are at least minAge years old. /

/** Print the names and ages of persons meeting age and gender criteria. */

public void print(int minAge, Gender gender)

{ for(Person p : this.persons)

{ if (p.getAge() >= minAge & p.getGender() == gender)

{ System.out.println(p.getName() + " " + p.getAge());

}

}

}

10.1.6 Searching for a Specified Element

Early returns out of loops is a contentious subject among CS educators. After years of struggling to get my students to write loops without an early return, I read a paper by Eric Roberts at Stanford (see http://doi.acm.org/10.1145/199688.199815). I was persuaded. If you’re not, delete this slide and go with the next one.
Issues to discuss:
·  Two cases: element is found, element isn’t found.
·  What to return in each case. /
·  Checking for not-found case in the client code.
·  That return immediately terminates execution of the method (in the early return version). /

10.1.7 Finding an Extreme Element

I’ve found that good naming can really help with this algorithm. Naming the holder variable youngestSoFar or minSoFar or ___SoFar helps emphasize the process that’s happening and the possibility that the value might change.
Issues:
·  This compares the first element to itself.
·  Fails if the array happens to be empty. /
·  If more than one meets the criteria…
·  Sometimes it’s useful to return the index instead of the object. /

10.1.8 Sorting an Array

The diagrams at the bottom show a sample array to start with (left) and the way it should finish (right). The arrays of letters below each one is an abbreviation we’ll use in a trace. Notice that the letters are the same as the first initial in the more complete picture. /
Take a few moments to trace the algorithm. Note that the “sorted part” starts out completely empty! That’s OK.
Point out the patterns in the pcode. A variation of process all elements (the overall loop), find an extreme, and swap. /
Here’s a version of the code that uses helper methods to make the code clear. /
Here’s the algorithm again, written as a single method. It sorts by age, to get rid of the complexities of comparing strings.
You may want to mention that the Java library has sorting methods in the class java.util.Arrays. Using them is considerably easier than writing your own sort method and the code probably runs faster. Using them relies on polymorphism (Chapter 12). More coverage then. /

10.1.9 Comparing Arrays and Files

Arrays and files are sometimes confused by students because they both store many records. Take a moment to contrast them.
Summarize to say they’re complimentary. Use a file for long-term storage. Read them into an array for processing, then write them to a file again. (Yes, this simplifies files – they can be random access; we often read only the record from the file that we need rather than the whole thing into an array, etc. But don’t needlessly complicate things for them.) /

10.2 Creating an Array

Here’s the overview of what we need to do. /

10.1.1 Declaration

10.1.2 Allocation

If you know the size of the array at compile time, the declaration and allocation can be combined. If you don’t, keep them separate. /

10.1.3 Initialization

You might do this for small arrays. What about large ones? /
Problem: how do you know how large to make the array?
Reading the array twice is s-l-o-w. It works, but we can do better! /
Here’s another approach: store the number of records at the beginning of the file.
Note: We’ll explore still another approach when we learn how to reallocate an array. /

10.3 Passing and Returning Arrays

The general principle we want to illustrate is that you can pass arrays to methods and return them from a method. We’ll do this by considering an interesting algorithm, extracting a subset from an array.
Note that returning the values in an array gives us a lot of flexibility (compared to, for example, printing them). /
A couple of things to note:
·  An array can be allocated and used within a method – just like any other temporary variable.
·  That array (subset) can be passed as an argument to a method (fillSubset).
·  An array can be returned, too. /
The fillSubset algorithm is tricky! Spend some time tracing it. /
Here’s the code for fillSubset. The helper method countSubset is left as an exercise for the students.
Notes:
·  The array is passed in as a parameter. Perhaps review that ss is an alias to the array declared in extractSubset. Changes made via ss will be reflected in the object (array) it references.
·  We have two ints, one to keep track of our progress in each array.
·  Once the subset array is full, we can stop the loop. /

10.4 Dynamic Arrays

So far, we haven’t added anything to an array; nor have we deleted elements. To be useful, that needs to change. For example, MySpace must be able to add new members to its overall list. Each member’s page has an associated list of friends, blog entries, etc., which may also have elements added or deleted.

We’ll look at two main approaches, with their pitfalls. Finally, we’ll see that the best solution is a combination of the two.

10.4.1 Partially Filled Arrays

Talking points:
·  The two parts of an array. When we add an element, one part grows, one part shrinks.
·  Either part of the array may be empty.
·  By convention, 0..size-1 holds the valid entries and size..length-1 is space for growth.
·  This explicitly separates the size (number of elements stored) from the length (number of elements it can store). /

·  size can be interpreted two different ways:

·  The number of elements currently stored in the array.

·  The index of the next empty/free position in the array.

Note the use of this.size rather than this.persons.length to determine the number of elements to print.
Quick Quiz
Modify add..
public void add(Person p)
{ if (this.size < this.length)
{ this.persons[this.size] = p;
this.size += 1;
} else
{ System.out.println(…);
} /

Inserting into a Sorted Array

This problem forms the basis of Problem 10.8. Decide how thoroughly you want to discuss it.
One point that can trip up students is that the elements need to be shuffled down, starting with the last element and moving up. /

Problems with Partially Filled Arrays

Discussion

Partially filled arrays allow us to add and delete elements, as we wanted. But what are the problems with partially filled arrays?

1. There is still a hard upper limit that can’t be exceeded.

2. Wasted space.

10.4.2 Resizing Arrays

The diagram fades out the old array to illustrate it being replaced with the new one.
The array is not sorted, so we just add the new element at the end. If it were sorted, an algorithm like the one just discussed could be incorporated. /
The code to do this is not hard! To the rest of the program, it appears as if the array simply has one more element than it did before.
But, there is a problem here. Step 2 takes a lot of time! /
150,000 elements is not particularly many, yet it takes nearly 13 minutes! /

10.4.3 Combining Approaches