Transcript ch10_nn

Chapter 10 –ArrayLists and an Introduction to
the Java Collections Framework

The ArrayList Class









How to Create an ArrayList Object
Adding Elements to an ArrayList Object
How to Access an Element Within an ArrayList
How to Update an ArrayList Object
Additional ArrayList Methods
Printing or Concatenating an ArrayList
Storing Primitives in an ArrayList
ArrayList Example Using Anonymous Objects and
a For-Each Loop
ArrayList Objects Versus Standard Arrays
1
Chapter 10 –ArrayLists and an Introduction to
the Java Collections Framework






The LinkedList Class
The List Interface
Comparing Method Execution Times
Queues, Stacks, and the ArrayDeque Class
Overview of the Java Collections Framework
Collections Example – Information Flow in a Network
of Friends
2
The ArrayList Class



The ArrayList class provides the basic functionality
that comes with a standard array, plus it provides
additional functionality.
The basic functionality: An ArrayList stores an
ordered collection of values and allows access to the
values via an index.
The added functionality: An ArrayList grows and
shrinks dynamically by inserting and deleting
elements at any specified location.
3
How to Create an ArrayList Object

The ArrayList class is defined in the Java API's java.util
package, so for files that use the ArrayList class, import it
like this:
import java.util.ArrayList;

To initialize an ArrayList reference variable, in a declaration,
use this syntax:
ArrayList<element-type> reference-variable = new ArrayList<>();

For example, here's how to initialize an ArrayList reference
variable named students:
ArrayList<Student> students = new ArrayList<>();
Use angled brackets to
surround the type for the
elements, and the type must be
a class name (not a primitive).
Use empty angled brackets (the
diamond operator).
4
How to Create an ArrayList Object

Let's compare the syntaxes for creating ArrayList
objects, regular objects, and standard arrays. Here's
the same ArrayList example as before:
ArrayList<Student> students = new ArrayList<>();

Here's an object example:
Mouse gus = new Mouse();

Here's a standard-array example:
Student[] students = new Student[100];
5
Adding Elements to an ArrayList Object

To add an element to the end of an ArrayList
object, use this syntax:
ArrayList-reference-variable.add(item);


The item that's added must be the same type as the
type specified in the ArrayList's declaration.
Write a code fragment that creates this ArrayList
object:
computerScientists
0
"Ada Lovelace"
1
"Grace Hopper"
2
"Marissa Mayer"
6
Java API






API stands for application programming interface.
The Java API is the interface to the huge library of pre-built Java
classes.
As a programmer, you don't need to know the internals of those
classes; you just need to know how to use them. Or said another
way, you just need to know how to interface with them.
To interface with them, you need to use their public methods.
To use a method, you need to know what type of argument(s) to
pass to it and what type of value it returns. A method's API
shows the method's parameters and its return type.
The standard way to show that information is to show the
method's heading. For example, here's the API heading for the
Math class's pow method:
public static double pow(double num, double power)
7
How to Access an Element Within an ArrayList


With standard arrays, you use square brackets to access and
update an element. ArrayList objects don't use square
brackets. Instead, they use a get method to access an element
and a set method to update an element.
Here's the API heading for the ArrayList's get method:
public E get(int index)

Semantics:

The index parameter specifies the position of the desired element
within the ArrayList calling object. As with standard arrays, the


first element is at position 0, the second element is at position 1, etc.
If index refers to a nonexistent element, then a runtime error
occurs.
If index is valid, then get returns the element at the specified
position.
8
How to Access an Element Within an ArrayList

Note the E return type for the ArrayList's get
method:
public E get(int index)

The E stands for element. It represents the data type
of the ArrayList's elements. It's the same as the
element-type specified in the ArrayList's
initialization:
ArrayList<element-type> reference-variable = new ArrayList<>();
9
How to Update an ArrayList Object

The set method allows you to assign a value to an
existing ArrayList element. Here's its API heading:
public E set(int index, E elem)

Semantics:




The index parameter specifies the position of the element
you're interested in.
If index refers to a nonexistent element, then a runtime
error occurs.
If index is valid, then set assigns the elem parameter to
the specified element, overlaying whatever was there
originally.
E represents the data type of the ArrayList's elements.
10
How to Update an ArrayList Object

Draw a picture of the colors ArrayList after this
code fragment executes:
String mixedColor;
ArrayList<String> colors = new ArrayList<>();
colors.add("red");
colors.add("green");
colors.add("blue");
mixedColor = colors.get(0) + colors.get(1);
colors.set(2, mixedColor);
11
Additional ArrayList Methods

public void add(int index, E elem)


public void clear()


Search for the first occurrence of the elem parameter within the list. If it's
found, return its index position. If it's not found, return -1.
Return true if the list contains no elements.
public E remove(int index)


Object is a generic class
that can be used as a
class type for any object.
public boolean isEmpty()


Remove all elements from the list.
public int indexOf(Object elem)


Starting with the specified index position, shift the original elements to
higher-indexed positions. Then insert the elem parameter at the specified
index position.
Remove the element at the specified index position, shift all higher-indexed
elements to lower-indexed positions, and return the removed element.
public int size()

Return the number of elements in the list.
12
Example ArrayList Program
import java.util.ArrayList;
public class HungerGames
{
public static void main(String[] args)
{
int deceasedIndex; // index of deceased tribute
String deceased;
// name of deceased tribute
ArrayList<String> tributes = new ArrayList<>();
tributes.add("Cato");
tributes.add("Katniss");
tributes.add("Peeta");
tributes.add("Rue");
tributes.add(1, "Finnick");
deceasedIndex = (int) (Math.random() * tributes.size());
deceased = tributes.remove(deceasedIndex);
System.out.println(deceased + " is no longer in the game.");
System.out.println("Remaining: " + tributes);
} // end main
} // end HungerGames
14
Printing or Concatenating an ArrayList


If you attempt to print or concatenate an ArrayList,
the ArrayList returns a comma-separated list of
ArrayList elements surrounded by square brackets,
[].
For example, in the HungerGames program, if Peeta is
removed, the last line prints this:
Remaining: [Cato, Finnick, Katniss, Rue]
15
Storing Primitives in an ArrayList





As mentioned previously, ArrayLists store references. For
example, in the HungerGames program, tribe is an ArrayList
of strings, and strings are reference types.
If you need to store primitives in an ArrayList, you can't do it
directly, but you can do it if the primitives are wrapped in
wrapper classes.
Ever since Java 5.0, the "wrapping" process has been done
behind the scenes. For ArrayLists, it's done automatically if a
wrapper class is used in an ArrayList declaration.
The StockAverage program on the next slide reads int stock
values and stores them in an ArrayList. After all stock values
are entered, the program calculates the average stock value.
Why is an ArrayList appropriate for calculating a stock
average?
16
Storing Primitives in an ArrayList
import java.util.Scanner;
import java.util.ArrayList;
public class StockAverage
Must be a
{
wrapper class,
public static void main(String[] args)
not a primitive.
{
Scanner stdIn = new Scanner(System.in);
ArrayList<Double> stocks = new ArrayList<>();
double stock;
// a stock value
double stockSum = 0;
// sum of stock values
System.out.print("Enter a stock value (-1 to quit): ");
stock = stdIn.nextDouble();
while (stock >= 0)
Automatic boxing (“autoboxing”)
{
takes place here.
stocks.add(stock);
System.out.print("Enter a stock value (-1 to quit): ");
stock = stdIn.nextDouble();
} // end while
17
Storing Primitives in an ArrayList
for (int i=0; i<stocks.size(); i++)
{
stock = stocks.get(i);
stockSum += stock;
}
Where does
automatic
unboxing take
place?
if (stocks.size() != 0)
{
System.out.printf("\nAverage stock value = $%.2f\n",
stockSum / stocks.size());
}
} // end main
} // end class StockAverage
18
ArrayList Example Using Anonymous
Objects and a For-Each Loop


When storing objects in an ArrayList, it's common to create
an object and add it to the ArrayList all in the same
statement.
For example, the upcoming BearStore program stores Bear
objects in an ArrayList. In storing a Bear object, the
program creates a Bear object and adds it to the bears
ArrayList, all in the same statement:
bears.add(new Bear("Acme", "brown teddy"));

An anonymous object is an object that's instantiated, but it's
not stored in a variable (and with no variable, there's no name
for it; thus, we say it's "anonymous").
19
ArrayList Example Using Anonymous
Objects and a For-Each Loop
import java.util.Scanner;
import java.util.ArrayList;
public class BearStore
{
ArrayList<Bear> bears = new ArrayList<>();
//**********************************************************
// Fill store with specified number of standard teddy bears.
public void addStdBears(int num)
{
anonymous object
for (int i=0; i<num; i++)
{
bears.add(new Bear("Acme", "brown teddy"));
}
} // end addStdBears
20
ArrayList Example Using Anonymous
Objects and a For-Each Loop
//**********************************************************
// Fill store with specified number of customized bears.
public void addUserSpecifiedBears(int num)
{
for (int i=0; i<num; i++)
{
bears.add(getUserSpecifiedBear());
}
} // end addUserSpecifiedBears
//**********************************************************
// Prompt user for a customized bear name and return bear.
private Bear getUserSpecifiedBear()
{
Scanner stdIn = new Scanner(System.in);
String maker, type;
System.out.print("Enter bear's maker: ");
maker = stdIn.nextLine();
System.out.print("Enter bear's type: ");
type = stdIn.nextLine();
return new Bear(maker, type);
anonymous
} // end getUserSpecifiedBear
object
21
ArrayList Example Using Anonymous
Objects and a For-Each Loop
//**********************************************************
// Print all the bears in the store.
public void displayInventory()
{
for (Bear bear : bears)
{
bear.display();
}
} // end displayInventory
//**********************************************************
public static void main(String[] args)
{
BearStore store = new BearStore();
store.addStdBears(3);
store.addUserSpecifiedBears(2);
store.displayInventory();
} // end main
} // end BearStore class
22
ArrayList Example Using Anonymous
Objects and a For-Each Loop
public class Bear
{
private final String MAKER; // bear's manufacturer
private final String TYPE; // type of bear
//**********************************************************
public Bear(String maker, String type)
{
MAKER = maker;
TYPE = type;
}
public void display()
{
System.out.println(MAKER + " " + TYPE);
}
} // end Bear class
23
Anonymous Objects

The bear store program contains several examples of
using anonymous objects. In general, you'll see
anonymous objects being used in two circumstances:

Passing a newly created object into a method or
constructor. For example:
bears.add(new Bear("Acme", "brown teddy"));

Returning a newly created object from a method. For
example:
return new Bear(maker, type);
24
25
For-Each Loop

Note the for-each loop in the BearStore's
displayInventory method:
public void displayInventory()
{
for (Bear bear : bears)
{
bear.display();
}
} // end displayInventory

Read this as "for each
bear in bears, …"
For each iteration
through the loop,
bear accesses the
next element in the
bears ArrayList.
For-each loop syntax for an ArrayList:
for (<element-type> <element-name> : <ArrayList-reference-variable>)
For-Each Loop

Note that using the for-each loop is an option, not a
requirement. Here's an alternative
displayInventory implementation that uses a
standard for loop:
public void displayInventory()
{
for (int i=0; i<bears.size(); i++)
{
bears.get(i).display();
}
} // end displayInventory

The for-each loop implementation is preferred
because it is simpler.
26
27
ArrayList Objects Versus Standard Arrays
Benefits of an ArrayList Over Benefits of a Standard Array
Over an ArrayList
a Standard Array
1.
2.
It's easy to increase the size
of an ArrayList – just call
add.
It's easy for a programmer
to insert or remove an
element to or from the
interior of an ArrayList –
just call add or remove and
specify the element's index
position.
1.
2.
A standard array uses []'s to
access array elements
(which is easier than using
get and set methods).
A standard array is more
efficient with storing
primitive values.
The LinkedList Class

28
A linked list is like an ArrayList, in that in holds a collection of
related data, but instead of using an underlying array to store the
data, it uses a chain of references:
front
A linked list with 3
elements (holding a, b, and c):
back
a
b
c
front
After adding x between
the b and c elements:
back
a
b
x
front
After removing the b element:
c
back
a
x
c
The List Interface


ArrayList and LinkedList implement many of the
same methods, like:
get, set, add, remove, clear, and size.
That’s because they both implement the same List
interface. In Java API documentation, you’ll see:
public class ArrayList<E> implements List<E>
public class LinkedList<E> implements List<E>


29
<E> stand for element type.
implements means the class promises to implement
all methods specified by the interface.
The List Interface - continued




In the past, you’ve declared variables with a primitive type or a class
name at the left, like this:
double distance;
Student student;
You can also declare a variable with an interface at the left, like this:
List<String> iPhoneApps;
First, you could assign an ArrayList object to iPhoneApps. Then,
later, you could assign a LinkedList object to the same variable:
iPhoneApps = new ArrayList<String>;
...
iPhoneApps = new LinkedList<String>;
The same List method call would do the same kind of thing with either
type of collection, but of course, the detailed implementations would
differ.
30
LinkedList vs. ArrayList Performance



With a LinkedList, It’s easiest to find, add, or remove
elements that are near one of the two ends.
Once an element has been found, it’s easier to remove it from
a LinkedList (change a pair of references) than from an
ArrayList (shift all higher elements to lower array indices).
However, finding an indexed element is much slower in a
LinkedList than in an ArrayList, because:
Instead of jumping right to the indexed position, the computer
must step in from an end until the step count equals the index
number (when starting at the head) or equals the length minus
the index number (when starting at the tail).
31
Measuring Method Execution Time



32
Measure the average time to get each element at a random index and
then set each element at a different random index.
Assume a getIndices(length)helper method returns an array of all
integers between zero and length in a random sequence with no
duplications.
First do it for an ArrayList. Then do it for a LinkedList.
public static void main(String[] args)
{
String operationType = "average get and set time";
int length = 1000;
int[] indicesA = getIndices(length);
int[] indicesB = getIndices(length);
ArrayList<Double> list = new ArrayList<>();
Double element;
long time0, time1;
A getIndices method (hidden)
private static int[] getIndices (int length)
{
Random random = new Random();
ArrayList<Integer> integers = new ArrayList<>();
int[] indices = new int[length];
for (int i=0; i<length; i++)
{
integers.add(random.nextInt(i+1), new Integer(i));
}
for (int i=0; i<length; i++)
{
indices[i] = integers.get(i);
}
return indices;
} // end getIndices
33
Measuring Method Execution Time
// Populate the list
for (int i=0; i<length; i++)
{
list.add(new Double(i));
}

To determine a method’s execution time, surround the method call with
calls to System.nanoTime(), which returns current time in
nanoseconds (billionths of a second):
time0 = System.nanoTime();
for (int i=1; i<length; i++)
{
element = list.get(indicesA[i]);
list.set(indicesB[i], element);
}
time1 = System.nanoTime();
34
Comparing Method Access Times
System.out.println(list.getClass());
System.out.printf("for length = %d, %s = %,d ns\n",
length, operationType, (time1 - time0) / length);
} // end main
Output:
class java.util.ArrayList
for length = 1000, average get and set time = 174 ns

Replace ArrayList by LinkedList and repeat, to obtain:
Output:
class java.util.LinkedList
for length = 1000, average get and set time = 1,455 ns
35
Comparing Method Mutate Times
36

Substitute:
String operationType = "average remove and add time";
And replace the for loop body with this:
element = list.remove(indicesA[i]);
list.add(indicesB[i], element);

Then the comparison generates results like these:

Output:
class java.util.ArrayList
for length = 1000, average remove and add time = 1,082 ns

Replace ArrayList by LinkedList and repeat, to obtain:
Output:
class java.util.LinkedList
for length = 1000, average remove and add time = 2,543 ns
Queues


37
A queue is a first-in first-out (FIFO) waiting line.
We add elements to the back (tail), and we remove elements from
the front (head).
back
front
After adding a, b, and then c:
After a remove operation:
After adding d:
a
b
c
back
front
b
c
back
front
b
c
d
Queues − continued



Although we could implement a queue with a LinkedList or an
ArrayList, Java’s ArrayDeque is more efficient.
An ArrayDeque is backed by an array.
The backing array’s length is initially 16, and its length doubles each time
the current length is inadequate.

The backing array is circular – links connect opposite ends.

Pointers identify current head and tail elements.

Adding increments tail pointer. Deleting increments head pointer.


The ArrayDeque class implements the Deque (pronounced “deck”)
interface.
To access Java’s Deque interface and ArrayDeque class:
import java.util.*;
// for Queue and ArrayDeque
38
Restaurant Queue Example
public static void main(String[] args)
{
String servedPerson; // from the queue's head
Queue<String> chipotlesQueue = new ArrayDeque<>();
chipotlesQueue.add("Alexa");
chipotlesQueue.add("Carolyn");
while (!chipotlesQueue.isEmpty())
{
servedPerson = chipotlesQueue.remove();
System.out.println("What is your order, " +
servedPerson + "?");
}
} // end main
39
Stacks


40
A stack is a last-in first-out (LIFO) storage container.
We add (push) and remove (pop) elements at the top.
c
b
a
top
After a pop operation:
b
a
top
After pushing d:
d
b
a
top
After pushing a, b, and then c:
Driveway-Parking Stack Example
/*************************************************************
* DrivewayParking.java
* Dean & Dean
*
* This program uses stacks to help a driveway parking service.
*************************************************************/
import java.util.*; // ArrayDeque, Scanner
public class DrivewayParking
{
private ArrayDeque<String> driveway1 = new ArrayDeque<>();
private ArrayDeque<String> driveway2 = new ArrayDeque<>();
//*********************************************************
public static void main(String[] args)
{
Scanner stdIn = new Scanner(System.in);
char action;
String licensePlate;
DrivewayParking attendant = new DrivewayParking();
41
Driveway-Parking Stack Example
42
do
{
attendant.describeDriveways();
System.out.print("Enter +license to add, " +
"-license to remove, or q to quit: ");
licensePlate = stdIn.nextLine();
action = licensePlate.charAt(0);
licensePlate = licensePlate.substring(1);
switch (action)
{
case '+':
attendant.parkCar(licensePlate);
break;
case '-':
if (!attendant.getCar(licensePlate))
System.out.println("Sorry, couldn't find it.");
} // end switch
} while (action != 'q');
} // end main
Driveway-Parking Stack Example
public void describeDriveways()
{
System.out.println("driveway1 " + driveway1);
System.out.println("driveway2 " + driveway2);
} // end describeDriveways()
//*********************************************************
// This method parks a car in the least full driveway.
private void parkCar(String licensePlate)
{
if (driveway1.size() <= driveway2.size())
driveway1.push(licensePlate);
else
driveway2.push(licensePlate);
} // end parkCar
43
Driveway-Parking Stack Example
private boolean getCar(String licensePlate)
{
String otherPlate;
if (driveway1.contains(licensePlate)) {
otherPlate = driveway1.pop();
while (!otherPlate.equals(licensePlate)) {
driveway2.push(otherPlate);
otherPlate = driveway1.pop();}
return true;
}
else if (driveway2.contains(licensePlate)) {
otherPlate = driveway2.pop();
while (!otherPlate.equals(licensePlate)) {
driveway1.push(otherPlate);
otherPlate = driveway2.pop();}
return true;
}
else
return false;
} // end getCar
} // end class DrivewayParking
44
Driveway-Parking Stack Example
Output:
driveway1 []
driveway2 []
Enter +license to add,
driveway1 [1234]
driveway2 []
Enter +license to add,
driveway1 [1234]
driveway2 [2345]
Enter +license to add,
driveway1 [3456, 1234]
driveway2 [2345]
Enter +license to add,
driveway1 []
driveway2 [3456, 2345]
Enter +license to add,
-license to remove, or q to quit: +1234
-license to remove, or q to quit: +2345
-license to remove, or q to quit: +3456
-license to remove, or q to quit: -1234
-license to remove, or q to quit: q
45
Java Collections Framework





The Java collections framework has two interface hierarchies,
the collection hierarchy, and the map hierarchy.
The Collection interface specifies methods common to the
List, Queue, and Set interfaces, like add, contains,
isEmpty, set, size, and remove.
All classes that implement the Collection interface provide a
one-parameter constructor that converts any type of collection
to any other type of collection.
The collection hierarchy includes a special kind of queue, called a
priority queue, which inserts higher priority elements closer to
the head of the queue.
A map uses a unique key, like an id number, to provide rapid
access to other (more complex) objects.
46
Java Collections Framework
47
<<interface>>
Collection<E>
<<interface>>
List<E>
<<interface>>
Set<E>
<<interface>>
SortedSet<E>
HashSet<E>
<<interface>>
Queue<E>
ArrayList<E>
LinkedHashSet<E>
<<interface>>
NavigableSet<E>
PriorityQueue<E>
<<interface>>
Deque<E>
LinkedList<E>
TreeSet<E>
Collections
ArrayDeque<E>
Java Collections Framework − Maps
<<interface>>
Map<K,V>
<<interface>>
SortedMap<K,V>
HashMap<K,V>
<<interface>>
NavigableSet<E>
<<interface>>
NavigableMap<K,V>
TreeMap<K,V>
LinkedHashMap<K,V>
48
Java Collections Framework − Maps





A map relates an object in a key set to another object that could
be in another set, a list, or a queue.
A map is like a mathematical function. You provide an
independent key, and it returns a dependent value.
To add a value of type V identified by a key of type K to a Java
Map, use this method:
public V put(K key, V value)
To retrieve a reference to the value identified by key, use this
method:
public V get(Object key)
To remove and return the value identified by key, use this
method:
public E remove(K key)
49
Collections Example – Information Flow in a
Network of Friends

Assume:







A set of citizens.
Each citizen is connected to a random set of friends.
Each friendship is mutual (a bidirectional connection).
Give one citizen a new message with request to pass it on to all
his or her friends, asking them to do likewise.
Continue until all who can be reached have been informed.
Major operations: build network; distribute message.
Details:


Store set of citizens with a set of friends for each citizen.
Make sure dissemination process terminates: Add each newly
informed citizen to a sender’s queue. Remove citizens from that
queue to propagate message to that sender’s friends. Do not add
previously informed citizens to sender’s queue. As more citizens
become informed, fewer are added to the queue, and it empties.
50
CommunityDriver.java
/*******************************************************
* CommunityDriver.java
* Dean & Dean
*
* Create citizens & friendships and propagate a message.
*******************************************************/
import java.util.*; // for Scanner, Map, and Set
public class CommunityDriver
{
public static void main(String[] args)
{
Scanner stdIn = new Scanner(System.in);
Community community;
Map<Integer, Citizen> citizens;
Set<Integer> informedCitizens;
51
CommunityDriver.java − continued
// Create the network.
System.out.print(
"Enter citizen & relation quantities: ");
community =
new Community(stdIn.nextInt(), stdIn.nextInt());
citizens = community.getCitizens();
System.out.println("Citizen\tFriends");
for (Integer id : citizens.keySet())
{
// Citizen’s toString method displays citizen info:
System.out.println(citizens.get(id));
}
52
CommunityDriver.java − continued
// Propagate a message through it.
System.out.print("Enter information source ID: ");
informedCitizens =
community.spreadWord(stdIn.nextInt());
System.out.println("Citizen\tDelay");
for (Integer citizenID : informedCitizens)
{
System.out.printf("%d\t%d\n",
citizenID, citizens.get(citizenID).getDelay());
}
} // end main
} // end CommunityDriver
53
Community.java− constructor
54
private Map<Integer, Citizen> citizens = new HashMap<>();
public Community(int citizenQuantity, int relationQuantity)
{
Random random = new Random(0);
Citizen citizen;
// any citizen object
int self, other;
// ID numbers
for (int i=0; i<citizenQuantity; i++)
{
citizen = new Citizen();
citizens.put(citizen.ID, citizen); // ID is public
}
for (int j=0; j<relationQuantity; j++)
{
self = random.nextInt(citizens.size());
do
{
other = random.nextInt(citizens.size());
} while (other == self || citizens.get(self).getFriends().contains(other));
citizens.get(self).addFriend(other);
citizens.get(other).addFriend(self);
}
} // end constructor
Community.java− spreadWord method
public Set<Integer> spreadWord(int sender)
{
Set<Integer> informedCitizens = new LinkedHashSet<>();
Queue<Integer> sendersQueue = new ArrayDeque<>();
citizens.get(sender).setDelay(0);
// for originator
informedCitizens.add(sender);
sendersQueue.add(sender);
do
{
sender = sendersQueue.remove();
for (Integer friend : citizens.get(sender).getFriends())
{
if (!informedCitizens.contains(friend))
{
citizens.get(friend).setDelay(
citizens.get(sender).getDelay() + 1);
informedCitizens.add(friend);
sendersQueue.add(friend);
}
} // end for each uninformed friend
} while (!sendersQueue.isEmpty());
return informedCitizens;
} // end spreadWord
55
56
Citizen.java
/*************************************************************
* Citizen.java
* Dean & Dean
*
* This represents an element in a network of citizens.
*************************************************************/
import java.util.*;
// Set & TreeSet
public class Citizen
{
private static int nextID = 0;
// for unique IDs
public final int ID = nextID++;
// cannot change!
private Set<Integer> friends = new TreeSet<>();
private int delay;
//**********************************************************
// <simple-methods>
public String toString()
{
return String.format("%d\t%s", ID, friends);
} // end toString
} // end class Citizen
Example Network of Friends
Enter citizen & relation quantities: 16 16
Citizen Friends
0
[8, 9, 15]
1
[4, 8]
2
[4, 5]
3
[9]
4
[1, 2, 5, 10]
5
[2, 4, 11]
6
[9, 10]
7
[]
8
[0, 1]
9
[0, 3, 6, 12]
10
[4, 6]
11
[5, 13]
12
[9]
13
[11]
14
[15]
15
[0, 14]
57
Example Message Dissemination
Enter information source ID: 4
Citizen Delay
4
0
1
1
2
1
5
1
10
1
8
2
11
2
6
2
0
3
13
3
9
3
15
4
3
4
12
4
14
5
58
4
1
2
5
10
8
11
6
0
13
9
15
3
14
7
12