[go: up one dir, main page]
Scribd
Upload
46 views5 pages

Worksheet 12.02 - Iterators and Data Structures: Lakeside School, Seattle, WA 1

This document provides an introduction and worksheet on iterators and data structures in Java, including Sets, Iterators, Stacks, Queues, and Maps. It explains that Sets are unordered collections that do not allow duplicate elements and are faster to search than lists. Iterators are needed to loop through a Set since they are unordered. The worksheet then provides examples of creating a Set of Points to represent dart throws, using iterators to loop through the Set, and removing elements that meet certain criteria. It also defines Stacks, Queues, Sets, and Maps as common data structures in Java and provides an in-class exercise to create a program testing one of these structures.

Uploaded by

Walker
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
46 views5 pages

Worksheet 12.02 - Iterators and Data Structures: Lakeside School, Seattle, WA 1

This document provides an introduction and worksheet on iterators and data structures in Java, including Sets, Iterators, Stacks, Queues, and Maps. It explains that Sets are unordered collections that do not allow duplicate elements and are faster to search than lists. Iterators are needed to loop through a Set since they are unordered. The worksheet then provides examples of creating a Set of Points to represent dart throws, using iterators to loop through the Set, and removing elements that meet certain criteria. It also defines Stacks, Queues, Sets, and Maps as common data structures in Java and provides an in-class exercise to create a program testing one of these structures.

Uploaded by

Walker
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 5

Creating Data Structures

Computer Science III, 2016

Worksheet 12.02 Iterators and Data Structures


Lists are reasonably intuitive and we can do a lot with them. A Set is an unordered
collection that does not allow duplicate elements, and it turns out that searching a
Set is a lot quicker than searching a list. It is still useful to loop through all the
elements of a Set, but as they are unordered it is necessary to create a helper
object called an Iterator in order to do so. This worksheet gives an introduction to
Sets and Iterators.
1. Create a class named Darts in a file named Darts.java. Import java.util.*
and java.awt.*.
a. In the main method use the code below to create a Set named tosses that
contains 5 Point objects. Each point represents the x and y coordinates of a
dart that was tossed at a dart board. The numbers represent millimeters
from the center of the bulls-eye in the x or y direction.

Set<Point> tosses = new HashSet<Point>(); //Create set


tosses.add(new Point(10,10)); //Add some elements
tosses.add(new Point(-58,100));
tosses.add(new Point(15,-30));
tosses.add(new Point(100,-45));
tosses.add(new Point(2,-4));
System.out.println(tosses); //Print the set
Did you notice anything about the order in which the points were printed
compared to the order in which you added them to the set?
b. Add the following lines to test a few important methods in the Set class.

tosses.remove(new Point(10,10));
System.out.println(tosses);
System.out.println( tosses.contains(new Point(-58,100)) );
System.out.println( tosses.size() );
What method inside of the Point class allows .contains() and .remove() to
work like this?

Lakeside School, Seattle, WA

Creating Data Structures

Computer Science III, 2016

2. Anything that implements a List<E> interface has an order to it usually


denoted by indices. But how would we loop through Collection<E> objects like
Set<E> that dont have order?
This is where an Iterator can help. Putting an iterator on a Set is somewhat
like putting a Scanner on a file or String. An iterator has three basic operations:
a hasNext operation that tells you whether or not there are any values
left.
a next operation which moves the iterator to the next value AND returns
the value
A remove operation for removing the last element pointed to by this
iterator.
Anything that inherits from Collection<E> must implement a method that will
return you the iterator on that collection. In the Javadoc this looks like:
Iterator<E>

iterator()
Returns an iterator over the elements in this collection.

a. Add the following to your main method of Darts:


System.out.println("Iterating through the Set:");
Iterator<Point> tossesIter = tosses.iterator();
while( tossesIter.hasNext() )
{
Point toss = tossesIter.next();
System.out.println(toss);
}
Tricky, Tricky: If you still need an index but want to use an Iterator, this is
totally legal.
Iterator<Point> tossesIter = tosses.iterator();
for (int ii = 0; tossesIter.hasNext(); ii++)
{
Point toss = tossesIter.next();
System.out.println("Toss" + ii + ": " + toss);
}
b. Removing from a list: Lets say you wanted to delete any toss that was more
than 100 millimeters from the center of the dart board. Here is how:
System.out.println("Removing bad throws:");
Iterator<Point> iter = tosses.iterator();
while( iter.hasNext() )
{
Point toss = iter.next();
double distance = Math.sqrt(toss.getX()*toss.getX()
+toss.getY()*toss.getY());
Lakeside School, Seattle, WA

Creating Data Structures

Computer Science III, 2016

if (distance > 100)


iter.remove();
}
System.out.println(tosses);
Note that you did NOT use the remove method from the Collection<E>
interface (in this case, tosses.remove()).
c. Dont do this:

Iterator<Point> tossesIter = tosses.iterator();


while( tossesIter.hasNext() )
{
Point toss = tossesIter.next();
System.out.println(toss);
tosses.add(new Point(12, -13)); //This will not work!!
}
Well you can certainly try it but youd get a
ConcurrentModificationException because youre attempting to modify a
Set while youre iterating through it.
d. Implicit iterator usage: You can use the iterator implicitly by using a for-each
loop. Try this out:

System.out.println("Iterating with a for-each loop:");


for (Point p : tosses)
{
System.out.println(p);
}
What are you able to do with an explicit iterator that you cant do with an
implicit one?

e. Optional challenge write a static method named playRound that adds some
number of randomly located tosses to the Set. Assume the tosses are within
250 mm vertically and horizontally from the center of the board. Then write
a method called scoreRound that iterates through the Set and computes the
score with the following system:
10 points if you are within 10 mm of the center
5 points if you are within 20 mm of the center
2 points if you are within 100 mm
1 point if you are within 200 mm

Lakeside School, Seattle, WA

Creating Data Structures

Computer Science III, 2016

3. Java has many types of data structures, but the ones we will study here are the
following:

A Stack is a data structure that stores elements in a Last-In-First-Out (or


LIFO) organization. A Stack is a concrete template class in Java.
o The term Push is generally used to say adding items to the top of a
stack
o The term Pop is used to say Pulling items off the top of a stack

A Queue is a data structure that stores elements in a First-In-First-Out (or


FIFO) organization. A Queue is as interface in Java, but there are concrete
Queue classes like a PriorityQueue
o The term Enqueue is generally used to say adding items to the end of the
queue
o The term Dequeue is used to say pulling items from the front of the
queue

A Set (which we saw in this worksheet) is a collection that stores a group of


Elements and prevents duplicates. Set<E> is an interface in java,
implemented as concrete classes HashSet<E> and TreeSet<E>. Each have
interesting properties we will study in the next weeks. Typically you think of
the following operations on a set.

Set
Operation

Method

Description

union

addAll

Set of all elements that are in A, B or


both

intersection

retainAll

Set of all elements that are in both A


and B

difference

removeAl
l

Set of all elements that are in A but


not B

superset/subs
et

contains
All

Returns true if A is a superset


(contains all of) B

A Map is an unordered collection that associates objects called keys with


objects called values so values elements they can be found very quickly. Each
key can appear at most once (no duplicate keys) and a key maps to at most
one value, and you cannot easily map backwards from value to key. Maps in
Java are implement as the Map<K, V> interface as HashMap and TreeMap
concrete classes.
Lakeside School, Seattle, WA

Creating Data Structures

Computer Science III, 2016

IN-CLASS EXERCISE
Find a partner who is also at this point in the worksheet. Work together to
create an application to test one of these data structures your choice
among Stack, Queue, or Map. First go to the JavaDoc to see the constructor
syntax and the available methods. Then you will write a short test program
that uses your groups data structure (along the same lines as the Darts
program you just wrote).
This test program should
o Construct the data structure
o Add a few elements
o Print the structure using its toString().
o Demonstrate the use of any other methods that seem important
o Print the elements using an iterator and a loop

Lakeside School, Seattle, WA

You might also like