Transcript Arrays, Container ADT, Collections

CS 340 DATA
STRUCTURES
Lecture: Arrays, Collections
Today’s Topics
• More on arrays
• Shallow copies, deep copies, and cloning
• Sorting & searching in arrays
• Introduction to containers
Arrays
• An array is a “first-class object,” unlike a C/C++
array, which is just a bunch of contiguous
memory locations.
• As for all objects, the array name is a reference to
the actual object.
• This object has space sufficient for
• the number of references you specify, if your array holds
objects, or
• the number of primitive values you specify, if your array
holds primitive types,
• plus space to hold the array length.
Arrays of Primitives
int[] a
=
new int[3]; // compiler does initialization
3 0
0
0
a.length a[0] a[1] a[2]
int[] a
=
This is schematic only,
e.g., length may not be
first in memory.
{41, 32, 19}; // compiler does initialization
3 41 32 19
a.length a[0] a[1] a[2]
Arrays of Primitives (cont.)
• Here are two common (compile) errors:
int[] a;
a[2] = 5;
int[] b;
int len = b.length;
• But this is OK:
int[] a = {41, 32, 19};
int[] b;
b = a;
int len = b.length;
// a uninitialized
// b uninitialized
Arrays of Objects
class Stock {
int sharesHeld = 0;
double currentPrice = 100.00;
}
Stock[] a
=
new Stock[3];
// initialization to 
3   
a
a.length a[0] a[1] a[2]
The array components
a[0], a[1] and a[2] are
null () references.
Arrays of Objects
for (int i = 0; i < 3; i++)
a[i] = new Stock();
3
a
f0
f12 f24
a.length a[0] a[1] a[2]
Stock
Stock
Stock
Passing Arrays to Methods
public class Stock {
Stock() {}
Stock(int s, double p, String name) {
sharesHeld = s;
currentPrice = p;
symbol = name;
}
int sharesHeld = 0;
double currentPrice = 100.00;
String symbol;
public String toString() {
String s = new String();
s += sharesHeld + " shares of " + symbol + " at $" + currentPrice;
return s;
}
}
Investor
public class Investor {
Stock[] portfolio;
Advisor ohTrustedOne;
double value;
Investor() {portfolio = new Stock[0];}
Investor(Stock[] p, Advisor a) {
portfolio = p;
ohTrustedOne = a;
value = ohTrustedOne.findValue(p);
}
// more below
Investor (cont.)
String describePortfolio() {
String s = new String();
s += "My portfolio is: \n";
for (int i = 0; i < portfolio.length; i++)
s += portfolio[i] + "\n";
s += "The total value is $" + value;
return s;
}
void askAdvice() {
ohTrustedOne.advise(portfolio);
}
}
Advisor
public class Advisor {
double findValue(Stock[] p) {
double value = 0;
for (int i = 0; i < p.length; i++)
value += p[i].currentPrice * p[i].sharesHeld;
return value;
}
void advise(Stock[] p) { swindle(p); }
void swindle(Stock[] p) {
for (int i = 0; i < p.length; i++)
p[i].sharesHeld /= 2;
}
}
Test Passing Arrays
public class TestInvestments {
public static void main(String[] args) {
Stock[] p = new Stock[] {new Stock(1000, 53.45, "GnMotr"),
new Stock(100, 29.05, "GenElec"),
new Stock(220, 44.08, "GenMills")};
Advisor deweyCheethamAndHowe = new Advisor();
Investor sucker = new Investor(p, deweyCheethamAndHowe);
System.out.println(sucker.describePortfolio());
sucker.askAdvice();
System.out.println(sucker.describePortfolio());
}
}
Dangers in Passing Arrays
• The called method gets a reference to the actual array,
and can modify it.
• Using final is a possibility, but not in this example (at least
not easily).
• If you are cautious, you can make a copy and send that.
Copies of Arrays
• Shallowest: make a copy of the array reference
• Shallow: make a new array of references of the same
type and size, and copy into it the existing array of
references
• Deep: the above, plus make copies of all the objects
themselves
• The method System.arraycopy() does a shallow copy—
arghhh!
Deep Copy of an Array
Stock[] copyPortfolio() { // illustrates returning an array
Stock[] copy = new Stock[portfolio.length];
for (int i = 0; i < portfolio.length; i++) {
Stock s = new Stock();
s.currentPrice = portfolio[i].currentPrice;
s.sharesHeld = portfolio[i].sharesHeld;
s.symbol = new String(portfolio[i].symbol);
copy[i] = s;
}
return copy;
}
Aside: Cloning
• Java doesn’t have the equivalent of C++’s copy
constructor, but does have cloning.
• If a class implements the Cloneable interface, then you
can make a “duplicate copy” by calling clone().
• To implement, override Object’s clone() method as a
public method in your class.
• clone() returns an Object, which you can then cast to the
correct type.
Cloning Example
public class SimpleObject implements Cloneable {
private int i;
SimpleObject(int i) {this.i = i;}
public String toString() {
String s = new String();
s += "I'm a SimpleObject with i = " + i;
s += " and address " + super.toString();
return s;
}
Cloning Example (cont.)
public Object clone() {
Object o = null;
try {
o = super.clone();
}
catch(CloneNotSupportedException e) {
System.out.println("SimpleClass can't clone.");
}
return o;
}
}
Cloning Example (cont.)
public class CloneTest {
public static void main(String[] args) {
SimpleObject s1 = new SimpleObject(1);
System.out.println(s1);
SimpleObject s2 = (SimpleObject) s1.clone();
System.out.println(s2);
}
}
One run produces this:
I'm a SimpleObject with i = 1 and address SimpleObject@158269a
I'm a SimpleObject with i = 1 and address SimpleObject@15829aa
Arrays Are “Type-Safe”
• You explicitly declare the type of objects held in
the array.
• The compiler checks to make sure your usage
agrees with your declaration.
• A very common usage is to write a class
hierarchy, then use an array of the type “highest”
in the hierarchy (an array of Nodes, for example).
• Polymorphism is then used to work with the array
elements.
The Arrays Class
• In java.util
• Provides many versions of the static methods:
• asList()
• binarySearch()
• equals()
• fill()
Versions of these for byte, char,
• sort()
double, float, int, long, Object
and short. The Object versions of
binarySearch() and sort() allow
you to specify a comparator.
Sorting Students
public static void main(String[] args) {
Student s1 = new Student("Fred", 3.0F);
Student s2 = new Student("Sam", 3.5F);
Student s3 = new Student("Steve", 2.1F);
Student[] students = new Student[] {s1, s2, s3};
for (int i = 0; i < students.length; i++)
System.out.println(students[i].getName()
+ "\t" + students[i].getGpa());
Arrays.sort(students);
for (int i = 0; i < students.length; i++)
System.out.println(students[i].getName()
+ "\t" + students[i].getGpa());
}
Sorting Students (cont.)
• This gives, as expected, the following:
Fred
Sam
Steve
Steve
Fred
Sam
3.0
3.5
2.1
2.1
3.0
3.5
This example used the natural
comparison method compareTo()
that we provided in the Student
class (which implemented the
Comparable interface). That
comparison method compared
gpas.
sort() also allows you to specify
a different comparison method
if you want…
Sorting With a Comparator
• The Comparator interface allows you to define “objects
that know how to compare two things.”
• This interface expects you to define the compare()
method (and perhaps also the equals() method).
• Let’s try it for Students.
Student Comparator
import java.util.*;
public class CompareStudentNames implements Comparator {
public int compare(Object s1, Object s2) {
return
((Student) s1).getName().compareTo(
((Student) s2).getName());
}
}
Let’s Try It
Student s1 = new Student("Sam", 3.5F); // note I changed
Student s2 = new Student("Steve", 2.1F); // the order of
Student s3 = new Student("Fred", 3.0F); // the students!
Student[] students = new Student[] {s1, s2, s3};
for (int i = 0; i < students.length; i++)
System.out.println(students[i].getName()
+ "\t" + students[i].getGpa());
Arrays.sort(students, new CompareStudentNames());
for (int i = 0; i < students.length; i++)
System.out.println(students[i].getName()
+ "\t" + students[i].getGpa());
Now Try Filling
Arrays.fill(students, s1);
for (int i = 0; i < students.length; i++)
System.out.println(students[i].getName()
+ "\t" + students[i].getGpa());
students[1].setName("Gautam");
for (int i = 0; i < students.length; i++)
System.out.println(students[i].getName()
+ "\t" + students[i].getGpa());
This is probably not what we want!
This gives:
Fred
Fred
Fred
Gautam
Gautam
Gautam
3.0
3.0
3.0
3.0
3.0
3.0
The Java Container Classes
• A container class object could be
• your bookcase
• your photo album
• your suitcase
• your “junk drawer” in the kitchen
• your apartment
• Containers hold Object references, so can be dangerous.
• We can learn to live with danger…
Container Classes: Collection
• List and Set, essentially, with some specializations. They
store individual objects, and give you
• add(Object)
• remove(Object)
• contains(Object)
• size()
• other methods too
Container Classes: Map
• These hold pairs of things, a key and a value.
• Pairs are held in a map, ordered by the key
• Methods include
• containsKey(Object key)
• containsValue(Object value)
• put(Object key, Object value)
• get(Object key)
• remove(Object key)
The Java Collection Classes
interface
Collection
AbstractCollection
interface
List
AbstractList
ArrayList
AbstractSequentialList
LinkedList
interface
Set
AbstractSet
HashSet
interface
SortedSet
TreeSet
The Java Map Classes
interface
M ap
AbstractM ap
HashMap
WeakHashMap
interface
SortedM ap
TreeMap