3.17 Lecture 3

Introduction to Systems Programming - Lectures - Class 3.pdf

Let’s discuss about printScopes, the scopes and life cycles of all Xs.

The fields cannot have two identical variable, but if we've declared a variable in fields, then we can declare it again in the same body, but still cannot declared twice in same body.

If not, we cannot declare a variable in a same body repeatedly. But we can declare it in different body, since the variable only exist in that body.

Collection

A collection object can store an arbitrary number of other objects.

Java libraries

Groups of useful classes.
We do not need to write everything from scratch
We may reuse previously developed solutions!
Java organizes libraries in packages.
Object grouping into collections is a recurring need in programming.

Array List

An unsorted but ordered flexible-sized list: ArrayList.

The java.util package contains classes that implement many collection implementations.

Thus we need to import java.util package in the beginning like this import java.util.ArrayList;

So we use ArrayList at the head of the class to define a files field:

private ArrayList<String> files;

We will say this is “a list of strings” (implemented over arrays).

Generic Classes

ArrayList implements all the functionalities of a list:
add, get, size, remove....
if we remove index i objects, then i-th will be complemented by i+1-th object
ArrayList is a general-purpose collection class—i.e., not restricted in what it can store.

The type parameter indicates the kind of objects that we want a list to be composed of:

private ArrayList<Person> members;
private ArrayList<TicketMachine> machines;
Members refers to an ArrayList that can store Person objects
Machines can refer to an ArrayList to store TicketMachine objects.
ArrayList is a generic classes since it gets parameterized with a second type
Therefore, we always have to specify two types: the type of the collection itself (here: ArrayList) and the type of the elements that we plan to store in the collection (here: String).

Diamond notation

Note that when creating the ArrayList instance, we have written the following statement: files = new ArrayList<>();

This is the diamond notation because the two angle brackets create a diamond shape
We know the new statement has the following form: new type-name(parameters);
And we know the full type name for our collection is ArrayList<String>
Therefore, with an empty parameter list, the statement to create the new collection object is files = new ArrayList<String>();
Using the diamond notation is merely a shortcut notation.

The structure of an ArrayList object

It is able to increase its internal capacity as required: as more items are added, it simply makes enough room for them.

Characteristics of the list collections

They can increment their size as needed.
They maintain a private size counter:
size() is the corresponding query.
They maintain the objects of the collection in a sequential order.
Each element/value has a specific index.
Inserting/deleting elements will affect the indexes of existing elements in the list.
The details of how the list’s functionalities are implemented are kept hidden.
Does it matter?
Can we use list collections without knowing how these are internally implemented?

Iteration

Quite often we will want to perform certain actions an arbitrary number of times.
E.g., print all file names in the music organizer.
How many files does a music organizer have?
The vast majority of programming languages provide us with sentences that allow us to repeat (or iterate through) actions.
Java provides various kinds of iteration statements.
We will start by seeing the for-each iteration statement.
We will often need to repeat some actions multiple times.
Iteration provides us with a mechanism to control how many times we repeat such actions.
In the context of collections, we will often need to repeat some actions for every element in a collection.

For-each loop

for(ElementType element : collection) {
    loop body
}
==
for each element in collection do: {
    loop body
}
Example
public void listAllFiles() { 
    for(String filename : files) { 
        System.out.println(filename);
    }

The collection must be of type T.
E.g., ArrayList<T> in this case.
The interpretation of this statement is:
For every element (which we named elem) in the collection (which we named collection), execute the following statements (the "statements to be repeated").
We cannot modify the arrylist inside the body

Selective Processing

public ArrayList<String> findFiles(String searchString) {
    ArrayList<String> foundFiles = new ArrayList<String>();
    for (String filename : files) {
        if (filename.contains(searchString)) {
            foundFiles.add(filename);
        }
    }
    return foundFiles;
}

Through statement nesting, we can put conditional statements inside iteration statements, and get selective processing.

Characteristics of For-Each Loops

Syntactically simple, with clear semantics.
Termination of iteration occurs naturally.
One cannot alter the collection (an error will occur if one tries to).
We do not explicitly have an index to work with.
For-Each loops also work with collections that do not have ordering (do not support indexed access).
One should not prematurely exit a for-each loop (before visiting all collection elements).
E.g., if we are looking for the first element that matches a condition.
This can be generalized to: loops should always end when the condition to loop becomes false.
For-each loops correspond to a form of iteration known as "definite iteration."

Element Search is an "Indefinite" Iteration

In general, we cannot predict (before a search is performed) exactly how many objects or places we will have to traverse or visit.
Although in many cases we may have an absolute limit (number of elements, number of positions, etc.).
Infinite iteration is a possibility.

Typically an error.

The While-Loop

A for-each loop repeats the loop body once per each item in a collection.
We often need more flexibility than what the for-each loop provides.
We can use a boolean condition to decide if we want to continue or not with the iteration.
The while loop provides such control level.

The While-Loop Syntax

while (booleanExpression) {
    // while's body
}

The booleanExpression must be an expression of type boolean.
E.g., i < size.
The interpretation of this statement is:
While the condition (which we named booleanExpression) is true, execute the following statements (the "while's body").

The While-Loop (Key Notes)

A for-each loop repeats the loop body once per each item in a collection.
We often need more flexibility than what the for-each loop provides.
We can use a boolean condition to decide if we want to continue or not with the iteration.
The while loop provides such control level.

The While-Loop, an Example

public int div(int a, int b) {
    assert a >= 0 : "a must be positive";
    assert b > 0 : "b must be greater than zero";
    int res = 0;
    while (a >= b) {
        a = a - b;
        res = res + 1;
    }
    return res;
}

For-Each and While (Comparison)

For-Each Loop:

for (T elem : collection) {
    doSomething(elem);
}

Equivalent While Loop:

int index = 0;
while (index < getSize(collection)) {
    T elem = getElemAt(collection, index);
    doSomething(elem);
    index++;
}

For-Each and While, Using ArrayList

for (T elem : collection) {
    doSomething(elem);
}

Equivalent While Loop:

int index = 0;
while (index < collection.size()) {
    T elem = collection.get(index);
    doSomething(elem);
    index++;
}

For-Each vs While

For-Each:
Simpler and easier to write.
Safer: termination is guaranteed.
While:
It’s not limited to collections.
We have to be careful: we may end up having infinite loops.

Search in a collection

A fundamental task.
From the point of view of iteration, it’s inherently “indefinite”.
We have to consider both success (element found) as failure (search is exhausted).
Both success and failure are cases that must make the loop condition false.
Remember that the collection may be empty!

Search in a collection (Code)

int index = 0;
boolean found = false;
while(index < files.size() && !found) {
    String file = files.get(index);
    if(file.contains(searchString)) {
        // We don't need to keep looking.
        found = true;
    }
    else {
        index++;
    }
}
// Either we found it at index,
// or we searched the whole collection.

While-loop does not need collections!

public boolean isPrime(int value) {
    assert value >= 0 : "value must be positive";
    int divisors = 0;
    int divisor = 1;
    while (divisor <= value) {
        if (value % divisor == 0) {
            divisors++;
        }
        divisor++;
    }
    return divisors == 2;
}

The iterator type

Definition & Purpose
An iterator is an object that enables traversal over all elements in a collection.
It provides a mechanism to access elements sequentially without exposing the underlying structure.
Iteration in Programming
Iteration is a fundamental tool in nearly every programming project.
Programming languages offer various iteration mechanisms tailored for different situations.
This content focuses on a method that sits between using a while loop and a for-each loop.
Using an Iterator in Java
Instead of an integer index, an iterator object is used to track the current position in the collection.
Naming Conventions:
- Iterator (uppercase "I") is the Java class.
- iterator (lowercase "i") is the method that returns an iterator object.
- Java Collections and Iterator
The ArrayList class provides a method called iterator() that returns an Iterator object.
To use Iterator in Java, you need to import:
- java.util.ArrayList
- java.util.Iterator
- Iterator Methods
An iterator provides four methods; two are central to iteration:
- hasNext() : Checks if there is another element in the collection.
- next() : Retrieves the next element in the collection.
- Both methods are used in expressions since they return values.
- Pseudo-code Example

The common pattern for using an iterator:

Iterator<ElementType> it = myCollection.iterator();
while(it.hasNext()) {
  // Retrieve the next element
  ElementType element = it.next();
  // Process the element
  // (e.g., do something with that element)
}

We first use the iterator method of the ArrayList class to obtain an Iterator object.

Iterator is also a generic type, so we parameterize it with the type of the elements in the collection

To repeatedly check whether there are any more elements, use it.hasNext()

To get the next element, use it.next()

It is the Iterator object that we ask to return the next item, and not the collection object.

All interaction with the collection is done via the Iterator.

Example

Summary of iteration

Comparison of Iteration Approaches
For-each Loop:
- Standard technique for processing all elements (definite iteration).
- Most concise and easy to understand.
- Least flexible if only part of the collection needs processing.
- While Loop Versions:
- More flexible as they allow the iteration to be stopped in the middle (indefinite iteration).
- Particularly useful when processing only a portion of a collection.
- ArrayList Specifics vs. Other Collections
For an ArrayList, both while loop methods (using an index or an iterator) perform equally well.
Some collections may not support efficient access by index, making the index-based while loop approach unsuitable.
Iterator Approach
The most recent solution, using an Iterator, is applicable to all collections in the Java class library.
It is a universal code pattern, making it important for future projects and scenarios where collection types vary.

Removing elements

Challenge with Removing Elements During Iteration
Removing elements while iterating can lead to errors if the collection is modified during the process.
For example, attempting to remove an element using the collection’s remove method inside a for-each loop can trigger a ConcurrentModificationException.
Issues with For-each Loop Removal
The for-each loop does not expose the iterator used internally.
Modifying the collection (e.g., removing the current element) disrupts the iteration process, causing confusion about which element comes next.
Proper Approach: Using an Iterator
Iterator’s remove Method:
- The Iterator interface includes a remove method specifically designed for safely removing the last element returned by next().
- This method keeps the iterator synchronized with the collection after removal.
- Example Code:
```
Iterator<Track> it = tracks.iterator();
while(it.hasNext()) {
    Track t = it.next();
    String artist = t.getArtist();
    if(artist.equals(artistToRemove)) {
        it.remove();
    }
}
```
- Note: Always use the iterator’s remove method rather than the collection’s remove method.

`null` in Java

The reserved word null in Java represents the absence of an object reference.
When an object variable is declared but not assigned a specific object, it holds the value null.
Instance variables (fields) of a class that are not explicitly initialized are set to null by default.
Attempting to call a method or access a field on a null reference results in a NullPointerException.

Example

public class Lot
{
    private Bid highestBid;

    public Lot(...)
    {
        this.highestBid = null;
    }

3.17 Lecture 3

Collection

Java libraries

Array List

Generic Classes

Diamond notation

The structure of an ArrayList object

Characteristics of the list collections

Iteration

For-each loop

Selective Processing

Characteristics of For-Each Loops

Element Search is an "Indefinite" Iteration

The While-Loop

The While-Loop Syntax

The While-Loop (Key Notes)

The While-Loop, an Example

For-Each and While (Comparison)

For-Each and While, Using ArrayList

For-Each vs While

Search in a collection

Search in a collection (Code)

While-loop does not need collections!

The iterator type

Example

Summary of iteration

Removing elements

​null​​ in Java

Example

`null` in Java