Previous Next ua

Laboratory Training 2

Working with Java Generics and Collections

1 Training Tasks

1.1 Individual Task

Add new classes to the hierarchy of classes created by implementing of the individual task given in the Laboratory training #1. You should add derived classes that represent the first of the entities of the individual task. The first class should represent data using list (ArrayList), the second should use set (SortedSet).

Use Collections class to sort the list. When working with set, you should consistently create multiple sets sorted according to different criteria.

Test both implementations. The results of the programs should match.

1.2 Creation of a Library that Provides Generic Functions for Working with Arrays

Create a class with static generic methods that implement this functionality:

swap of two groups of items
swap of all neighbour items (with even and odd indices)
inserting items of another array in the specified location
replacement of some group with items of another array

Demonstrate the work of all methods using data of different types (Integer, Double, String).

1.3 Creation of a Library that Provides Generic Functions for Working with Lists of Numbers

Create a class that contains static generic functions for implementing such actions with a list of numbers (objects derived from Number):

finding the index of the first zero element
counting of the number of negative numbers
return the last negative element

Test all functions on lists of numbers of different types.

1.4 Finding Different Words in a Sentence

Enter a sentence, create a collection (SortedSet) of different words in a sentence, and display all these words in alphabetical order.

1.5 Data about Users

Present data about users in an associative array (username / password) with the assumption that all user names are different. Display user information with a password length of more than 6 characters.

1.6 Creating a Custom Container Based on an Array

Create a generic class to represent a one-dimensional array, whose index of items varies from a certain value from to value to inclusive. These values can be either positive or negative. The class must implement the Collection interface. It is advisable to use the AbstractList class as a base class.

1.7 Implementation of the Doubly-Linked List (Advanced Task)

Implement a generic class representing a doubly-linked list.

1.8 Implementation of the Element Removal Functions from the Tree (Advanced Task)

Add to the example 3.8 the function of deleting a given item from a tree.

1.9 Implementation of the Red-Black Tree (Advanced Task, Optional)

Independently implement associative array based on a red-black tree.

2 Instructions

2.1 Enumerations

Java 5 (since JDK 1.5) supports new reference type called enum (enumeration). Enumeration represents a list of possible values that a variable of this type can receive. In simplest case, their usage looks like one in C++ or C#.

enum DayOfWeek {
    SUNDAY,
    MONDAY,
    TUESDAY,
    WEDNESDAY,
    THURSDAY,
    FRIDAY,
    SATURDAY
}
  
...

DayOfWeek d = DayOfWeek.WEDNESDAY;

Listed constants are public. The enum type itself can be public or default. Names of possible values should be written using uppercase letters, because in fact they are constants. These constants are associated with integer values. In the following example, these values range respectively from 0 to 6. You can get these integer values using the ordinal() method. Constant can be obtained using the name() method. For example:

DayOfWeek d = DayOfWeek.WEDNESDAY;
System.out.println(d.name() + " " + d.ordinal());

The values() static function returns array of enumeration items:

for (int i = 0; i < DayOfWeek.values().length; i++) {
    System.out.println(DayOfWeek.values()[i]);
}

The static valueOf() function allows you to get the item of enumeration by its name. For example, you can get the integer value associated with a specific item:

System.out.println(DayOfWeek.valueOf("FRIDAY").ordinal());

In general, Java enumerations provide opportunities for defining and overloading methods, creating additional fields, and so on. For example, the DayOfWeek enumeration can be extended by printAll() static method:

static void printAll() {
    for (DayOfWeek d : values()) {
      System.out.println(d);
    }
}

You can overload the output of enumeration via toString() function:

enum Gender {
    MALE, FEMALE;

    @Override
    public String toString() {
        switch (this) {
            case MALE:
                return "male gender";
            case FEMALE:
                return "female gender";
        }
        return "something impossible!";
    }

}

public class GenderTest {
    public static void main(String[] args) {
        Gender g = Gender.FEMALE;
        System.out.println(g);
    }
}

The constants can be associated with some values. For example, an enumeration "Satellite of Mars" contains field "Distance from the center of Mars". We must also add a constructor and additional field and getter:

package ua.in.iwanoff.oop.second;

enum MoonOfMars {
    PHOBOS(9377), DEIMOS(23460);

    private double distance;

    private MoonOfMars(double distance) {
        this.distance = distance;
    }

    double getDistance() {
        return distance;
    }

    @Override
    public String toString() {
        return name() + ". " + distance + " km. from Mars";
    }

}

public class MoonsOfMarsTest {
    public static void main(String[] args) {
        MoonOfMars m = MoonOfMars.PHOBOS;
        System.out.println(m); // PHOBOS. 9377.0 km from Mars
    }

}

As can be seen, the presence of constructor requires definition of constants with actual parameters.

2.2 Generics

2.1.1 The Concept of Generic Programming

Often there is a need for so-called container classes that contain objects of arbitrary types. Sometimes, objects of different types held in containers require applying the same actions. The code for processing objects of different types looks almost the same. This is especially true if the different types of data needed to implement algorithms such as quick sorting or processing linked lists, binary trees, etc. In such cases, the code is the same for all types of objects.

Generic programming is a programming paradigm that provides a description of the data storage rules and algorithms in general form, regardless of the specific data types. Specific data types to which actions are applied are specified later. The mechanisms separating data structures and algorithms, as well as the formulation of abstract descriptions of data requirements are defined differently in different programming languages. First, generic programming opportunities presented in the seventies of the twentieth century in CLU and Ada languages (generic functions) and were later implemented in the ML language (parametric polymorphism).

The idea of generic programming is implemented in C++ most fully and flexibly thanks to the templates mechanism. A template in C++ is a code snippet that describes a generalized work on some abstract type, specified as a template parameter. This piece of code (class or function)) can be finally compiled only after template instantiation, i.e. after substituting a specific type instead of a template parameter. The Standard Template Library (STL) is based on the use of template functions and parameterized classes. STL includes a description of standard container classes and their generic algorithms.

To implement generic programming, Java offers generics - a special language feature that appeared in the language syntax starting with the Java 5 version.

2.1.2 Problems of Creating Universal Containers in Java 2

Suppose we need to create a container to store a pair of objects of the same type. The simplest container class (Pair) will contain two references to the Object class:

public class Pair {
    Object first, second;

    public Pair(Object first, Object second) {
        this.first = first;
        this.second = second;
    }
  
}

Since Object is the base class for all reference types, you can, for example, use this class to store a pair of strings:

Pair p = new Pair("Surname", "Name");

This approach has some drawbacks:

To read objects, you need to use explicit type conversion:

    String s = (String) p.first; // Instead of String s = p.first;

You cannot be sure that the pair stores objects of the type you need:

    Integer i = (Integer) p.second; // Runtime error

You cannot guarantee that both fields are the same type:

    Pair p1 = new Pair("Surname", new Integer(2)); // No any error messages

Similar problems occurred in the Java 2 with standard container classes. This resulted in potential runtime errors that could not be found at compile time.

2.1.3 The Syntax of Generics

Starting with version 5, Java allows you to create and use generics - a syntax construct that can be used for definition of classes and functions with extra parameters, which contain additional information about data types. These parameters are taken in angular brackets. Generics provide the ability to create and use type safe containers. Classes described using such parameters are called generic classes. When you create a generalized class object, you must specify names instead of the parameters. Only reference types can be used. The previous example can be implemented using generics.

public class Pair<T> {
    T first, second;

    public Pair(T first, T second) {
        this.first = first;
        this.second = second;
    }
  
    public static void main(String[] args) {
        Pair<String> p = new Pair<String>("Surname", "Name");
        String s = p.first; // Get string value without type casting
        Pair<Integer> p1 = new Pair<Integer>(1, 2); // You can use integer constants
        int i = p1.second;  // Get integer value without type casting
    }
}

Note: Java 7 (and above) allows you to not repeat the actual parameter of generic after the constructor name. For example:

Pair<Integer> p1 = new Pair<>(1, 2);

If you try to add a couple different data types, the compiler will generate an error. Is also erroneous attempt to explicitly convert type:

Pair<String> p = new Pair<String>("1", "2");
Integer i = (Integer) p.second; // Compiler error

The data type with the parameter in angle brackets (e.g. Pair<String>) is called parameterized type.

Generics are similar to C++ templates on their external presentation and use. But unlike the C++ templates, there are not several different types of Pair, but one. In fact, the class fields contain references to the Object type. Parameter type information is used by the compiler to check and automatically cast types in the source code.

In addition to generic classes, you can create generic interfaces. The parameter can be used in the description of functions declared in the interface. Interfaces can be implemented by both generic and non-generic classes. By the implementation in non-generic class, generic parameter can be replaced by some reference type. For example:

interface Function<T> {
    T func(T x);
}

class DoubleFunc implements Function<Double> {

    @Override
    public Double func(Double x) {
        return x * 1.5;
    }
}

class IntFunc implements Function<Integer> {

    @Override
    public Integer func(Integer x) {
        return x % 2;
    }
}

Generic classes and interfaces in Java are neither new types nor templates. This is just mechanism that tells the compiler to further type check and add type conversions.

Java also allows you to create generic functions inside both generic and non-generic classes:

public class ArrayPrinter {

    public static<T> void printArray(T[] a) {
        for (T x : a) {
            System.out.print(x + "\t");
        }
        System.out.println();
    }
  
    public static void main(String[] args) {
        String[] as = {"First", "Second", "Third"};
        printArray(as);
  `     Integer[] ai = {1, 2, 4, 8};
        printArray(ai);
    }

}

As you can see from the example, the call of a generic function does not require an explicit type definition. Sometimes such a definition is necessary, for example, when the function does not have generic type parameters. If this function is static, its class must be explicitly indicated. For example:

public class TypeConverter {

    public static <T>T convert(Object object) {
        return (T) object;
    }
  
    public static void main(String[] args) {
        Object o = "Some Text";
        String s = TypeConverter.<String>convert(o);
        System.out.println(s);
    }

}

Recommended names of formal parameters are names of a single capital letter. Generics can have two or more parameters. In the following example, the pair may contain references to objects of different types:

public class PairOfDifferentObjects<T, E> {
    T first;
    E second;

    public PairOfDifferentObjects(T first, E second) {
        this.first = first;
        this.second = second;
    }
  
    public static void main(String[] args) {
        PairOfDifferentObjects<Integer, String> p = 
            new PairOfDifferentObjects<Integer, String>(1000, "thousand");
        PairOfDifferentObjects<Integer, Integer> p1 = 
            new PairOfDifferentObjects<Integer, Integer>(1, 2);
        //...
    }
}

You can apply to objects of the generic parameter type only actions that are allowed for objects in the Object class. Sometimes it is desirable to expand the functionality to specify the type. For example, if you want to call methods declared in a particular class or interface, you can apply the following parameter syntax: <T extends SomeBaseType> or <T extends FirstType & SecondType>, etc. The word extends is used for both classes and interfaces.

For example, you can create a generic function for calculating the arithmetic mean of some numerical values stored in an array. The standard Double, Float, Integer, Long, and other numeric wrapper classes have a common abstract base class java.lang.Number that declares, in particular, the doubleValue() method, which allows you to get the number stored in the object in the form of a double value. This fact can be used to calculate the arithmetic mean. The created function can work with arrays of numbers of different types:

package ua.inf.iwanoff.oop.second;

public class AverageTest {

    public static<E extends Number> double average(E[] arr) {
        double result = 0;
        for (E elem : arr) {
            result += elem.doubleValue();
        }
        return result / arr.length;
    }

    public static void main(String[] args) {
        Double[] doubles = { 1.0, 1.1, 1.5 };
        System.out.println(average(doubles)); // 1.2
        Integer[] ints = { 10, 20, 3, 4 };
        System.out.println(average(ints));    // 9.25
    }
}

The syntax of generics involves the use of so-called wildcards (the '?' character). Wildcards are used, for example, to describe references to an unknown type. Using wildcards makes generics classes and functions more compatible. The wildcards provide the way to create functions that are non-generic by themselves, but use generics as arguments.

Here is an example of creating a generic class that represents an array of a certain type. We can also add a static function to output to the console elements of an array of arbitrary type, which demonstrates the use of wildcards:

public class MyArray<T> {
    private T[] arr;

    public MyArray(T... arr) {
        this.arr = arr;
    }

    public int size() {
        return arr.length;
    }

    public T get(int i) {
        return arr[i];
    }

    public void set(int i, T t) {
        arr[i] = t;
    }
  
    public static void printGenericArray(MyArray<?> a) {
        for (int i = 0; i < a.size(); i++) {
            System.out.print(a.get(i) + "\t");
        }
        System.out.println();
    }

}

Our array can be tested in some another class:

package ua.inf.iwanoff.oop.second;
	
public class MyArrayTest {
    public static void main(String[] args) {
        MyArray<String> arr1 = new MyArray<>("First", "Second", "Third");
        MyArray.printGenericArray(arr1);
        MyArray<?> arr2 = new MyArray<>(1, 2, 3); // MyArray<?> instead of MyArray<Integer>
        MyArray.printGenericArray(arr2);
    }
}

You cannot create arrays of generic type objects:

T arr = new T[10]; // Error!

In our example, this problem can be solved using references to the Object class. In addition, for ease of use, the constructor can be implemented as a function with a variable number of parameters. It will also be useful to add an item to the end of the array. An alternative implementation of the class can be as follows:

package ua.inf.iwanoff.oop.second;

import java.util.Arrays;

public class MyArray<T> {
    private Object[] arr = {};

    public MyArray(T... arr) {
        this.arr = arr;
    }

    public MyArray(int size) {
        arr = new Object[size];
    }

    public int size() {
        return arr.length;
    }

    public T get(int i) {
        return (T)arr[i];
    }

    public void set(int i, T t) {
        arr[i] = t;
    }

    public void add(T t) {
        Object[] temp = new Object[arr.length + 1];
        System.arraycopy(arr, 0, temp, 0, arr.length);
        arr = temp;
        arr[arr.length - 1] = t;
    }

    public void remove(int i) {
        Object[] temp = new Object[arr.length - 1];
        System.arraycopy(arr, 0, temp, 0, i);
        System.arraycopy(arr, i + 1, temp, i, arr.length - i - 1);
        arr = temp;
    }

    @Override
    public String toString() {
        return Arrays.toString(arr);
    }

}

Another class will be created for testing:

package ua.inf.iwanoff.oop.second;

public class TestClass {

    public static void main(String[] args) {
        MyArray<String> a = new MyArray<>("1", "2");
        String s = a.get(a.size() - 1);
        System.out.println(s);     // 2
        a.set(1, "New");
        System.out.println(a);     // 1 New
        MyArray<Double> b = new MyArray<>(3);
        b.set(0, 1.0);
        b.set(1, 2.0);
        b.set(2, 4.0);
        b.remove(2);
        b.add(8.0);
        System.out.println(b);     // [1.0, 2.0, 8.0]
    }

}

The functionality of a class can be extended by adding a new element inside an array, deleting all elements, etc.

You can restrict the use of the function parameter type to certain derived classes, such as MyArray<? super String>. Then, MyArray<Integer> is not possible.

2.3 Container Classes and Interfaces. Working with Lists

2.3.1 Overview

Java tools to work with collection provide a unified architecture for representing and managing data sets. This architecture allows you to work with collections regardless of the details of their internal representation. The tools for working with collections include more than a dozen interfaces, as well as standard implementations of these interfaces and a set of algorithms for working with them.

A collection is an object representing a group of objects. The use of collections helps to increase the efficiency of programs through the use of high-performance algorithms, and also helps to create a reusable code. The main components of working with collections are:

interfaces
standard implementation of interfaces
algorithms
tools for working with arrays

In addition, Java 8 supports Java 1.1 containers. These are Vector, Enumeration, Stack, BitSet and some others. For example, the Vector class provides functions similar to ArrayList. These containers did not provide a standardized interface in the first version, they do not allow the user to omit excessive synchronization, which is relevant only in a multithreaded environment, and therefore not sufficiently effective. As a result, they are considered obsolete and not recommended for use. Instead, you should use the corresponding generic Java 5 containers.

Standard Java container classes allow you to store a collection of references to objects whose classes derived from Object class. Container classes are implemented in the java.util package. Starting with Java 5, all container classes are implemented as generic.

There are two base interfaces those declare functionality of container classes: Collection (derived from Iterable) and Map. The Collection interface is a base interface for List, Set, Queue and Deque (double-ended queue) interfaces.

The List interface represents an ordered collection (also known as a sequence) whose elements can be repeated.

The Set interface is implemented by classes HashSet and LinkedHashSet. The SortedSet interface, derived from Set, is implemented by the TreeSet class. The Map interface is implemented by the HashMap class. The SortedMap, derived from Map, is implemented by the TreeMap class.

The HashSet, LinkedHashSet, and HashMap classes use so-called hash codes to identify the items. A hash code is a unique sequence of bits of fixed length. For each object, this sequence is considered unique. Hash codes provide quick access to data for some key. The mechanism for obtaining hash codes ensures their almost complete uniqueness. All Java objects can generate hash codes: the hashCode() method is defined for the Object class.

For most collections, there are both "normal" implementations and implementations that are safe from the viewpoint of multithreading, for example, CopyOnWriteArrayList, ArrayBlockingQueue, etc.

2.3.2 Collection Interface

The Collection interface is the base for most Collection Framework interfaces and declares the most common collection methods:

Method	Description
`int size()`	Returns the number of items in this collection
`boolean isEmpty()`	Returns `true` if this collection contains no items
`boolean contains(Object o)`	Returns `true` if this collection contains the specified item
`Iterator<E> iterator()`	Returns an iterator (an object that consistently points to the items)
`Object[] toArray()`	Returns an array of `Object` containing all of the items in this collection
`<T> T[] toArray(T[] a)`	Returns an array of `T` containing all of the items in this collection
`boolean add(E e)`	Adds an item to the collection. Returns `true` if the object is added
`boolean remove(Object o)`	Removes a single instance of the specified item from this collection, if it is present
`boolean containsAll(Collection<?> c)`	Returns `true` if this collection contains all of the items of the specified collection
`boolean addAll(Collection<? extends E> c)`	Adds items to a collection. Returns `true` if objects are added
`boolean removeAll(Collection<?> c)`	Removes objects that are present in the specified collection
`boolean retainAll(Collection<?> c)`	Leaves objects that are present in another collection
`void clear()`	Removes all of the items from collection

Note: the table does not list methods with default implementation, added in Java 8.

The following example demonstrates how the interface methods work. In the example, the ArrayList class is used as the simplest implementation of the Collection interface:

package ua.inf.iwanoff.oop.second;

import java.util.*;

public class CollectionDemo {

    public static void main(String[] args) {
        Collection<Integer> c = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
        System.out.println(c.size());      // 5
        System.out.println(c.isEmpty());   // false
        System.out.println(c.contains(4)); // true
        c.add(6);
        System.out.println(c);             // [1, 2, 3, 4, 5, 6]
        c.remove(1);
        System.out.println(c);             // [2, 3, 4, 5, 6]
        Collection<Integer> c1 = new ArrayList<>(Arrays.asList(3, 4));
        System.out.println(c.containsAll(c1));// true
        c.addAll(c1);
        System.out.println(c);             // [2, 3, 4, 5, 6, 3, 4]
        Collection<Integer> c2 = new ArrayList<>(c); // copy 
        c.removeAll(c1);
        System.out.println(c);             // [2, 5, 6]
        c2.retainAll(c1);
        System.out.println(c2);            // [3, 4, 3, 4]
        c.clear();
        System.out.println(c);             // []       
    }

}

2.3.3 Working with Lists

The List interface describes an ordered collection (sequence). The most used standard implementations of List interface are ArrayList and LinkedList. The ArrayList class is a resizable-array implementation of the List interface. The LinkedList class stores objects using the so-called linked list.

There is also a standard abstract implementation of the list, the AbstractList class. This class derived from AbstractCollection provides a number of useful tools. Practically all methods except get() and size() are implemented. However, for a specific implementation of the list, most functions should be overridden. The AbstractList class is the base class for the ArrayList. The AbstractSequentialList class derived from AbstractList is the base class for the LinkedList class.

You can create an empty list of references to objects of some type (SomeType) using the constructor that takes no arguments:

List<SomeType> al = new ArrayList<SomeType>();

You can also directly define the reference to ArrayList:

ArrayList<SomeType> al = new ArrayList<SomeType>();

The second approach is sometimes less desirable, because it reduced flexibility of a program. The first option makes it easy to replace ArrayList implementation with any other implementation of List interface, which is more consistent with the requirements of a particular task. In the second case, we can call methods specific to ArrayList, so switching to another implementation will be difficult.

An object of ArrayList class contains an array elementData of type Object. The physical size of the array (capacity), if you do not call the constructor with an explicit indication of this size, is set to 10. Each addition of an item involves calling the internal method ensureCapacity(), which in case of filling the array creates a new array with copying existing items. The size of the new array is calculated by the formula (old_size * 3) / 2 + 1.

When you delete items, the physical size of the array does not decrease. To save memory after repeatedly deleting items, it is advisable to call the trimToSize() method.

Once you have created an empty list object, you can put object references in it using the add() method. The add() method with one argument of reference type adds an element to the end of the list. The add() method with two arguments inserts a new element into a list before a given index, so it can be used to insert an element at any position in a list except the last. The following code fragment shows the use of the add() method:

List<String> al = new ArrayList<String>();
al.add("abc");
al.add("def");
al.add("xyz");
al.add(2, "ghi"); // Inserts a new string before "xyz"

You can add all elements of other collection to your list using addAll() method.

You can create a new list using the existing one. The new list contains references to copies of the items. For example:

List<String> a11 = new ArrayList<String>(al);

You can create a list from an existing array using static asList() method of java.util.Arrays class. An array can be created directly in the function parameter list. For example:

String[] arr = {"one", "two", "three"};
List<String> a2 = Arrays.asList(arr);
List<String> a3 = Arrays.asList("four", "five");

Lists provide overloaded toString() function, which allows, for example, to show all the elements of the list on the screen without using loops. Items are displayed in square brackets:

System.out.println(a3); // [four, five]

Lists allow you to work with individual elements. The size() method returns the number of elements in a list. As with arrays, list items can be accessed by index, but using the get() and set() methods, not by [] operator. The get() method returns the element at the specified position in this list. Like arrays, list objects are indexed starting at zero. In the following example, all previously added strings are printed using println() method:

List<String> al = new ArrayList<String>();
al.add("abc");
al.add("def");
al.add("xyz");
for (int i = 0; i < al.size(); i++) {
    System.out.println(al.get(i));
}

The set() method allows you to change the object stored at a specified position, while the remove() method removes the object at the specified position:

al.set(0, "new");
al.remove(2);
System.out.println(al); // [new, def]

The subList(fromIndex, toIndex) function returns a list composed of elements beginning with an index fromIndex and not including an item with a toIndex index. For example:

System.out.println(al.subList(1, 3)); // [def, xyz]

The removeRange(m, n) method removes all of the elements whose index is between m, inclusive, and n, exclusive. You can also remove all of the elements from the list using the clear() method. The contains() method returns true if this list contains the specified element. For example:

if (al.contains("abc")) {
    System.out.println(al);
}

The toArray() method returns a reference to an array of references to copies of objects stored in the list.

Object [] a = al.toArray();
System.out.println(a[1]);    // def
(al.toArray()) [2] = "text"; // the modification of a new array

You can use wrapper classes Integer and Double if you want to store numeric values in container.

In those cases where the operations of adding and removing elements in arbitrary places are more often than selecting an arbitrary element, it is advisable to use the LinkedList class, which stores objects using the so-called linked list. The linked list that implemented in Java by the LinkedList container is a doubly linked list, where each element contains a reference to the previous and the next elements.

For convenient work , the addFirst(), addLast(), removeFirst(), and removeLast() methods are added.

LinkedList<String> list = new LinkedList<String>();
list.addLast("last"); // The same as list.add("last");
list.addFirst("first");
System.out.println(list); // [first, last]
list.removeFirst();
list.removeLast();
System.out.println(list); // []

These specific features are added in LinkedList, because they cannot be effectively implemented in ArrayList.

Linked lists in Java support working with individual items, but these functions cannot be implemented effectively.

2.3.4 Iterators

An iterator is a special auxiliary object that is used for the sequential passage of the elements of the collection (list). Like the containers themselves, iterators are based on the interface. The Iterator interface defined in java.util package. An object that implements the Iterator interface provides three methods for dealing with the collection:

boolean hasNext(); // returns true if the iteration has more elements 
Object  next();    // returns the next element in the iteration 
void    remove();  // removes the last element returned by the iterator

After the first next() invocation, iterator points to the first element. Java collections return iterators from iterator() method.

List<String> s = new ArrayList<String>();
s.add("First");
s.add("Second");
for (Iterator<String> i = s.iterator(); i.hasNext(); ) {
    System.out.println(i.next());
}

As can be seen from the example above, the iterator is also a generic type.

An alternate form of the for (for each) loop allows you to bypass the list without explicitly creating the iterator:

List<Integer> a = new ArrayList<Integer>();
a.add(1);
a.add(2);
a.add(3);
a.add(4);
for (Integer i : a) {
    System.out.print(i + " ");
}

As for arrays, the alternative form of the for loop does not allow you to change the values of elements, or delete them.

The special kind of list iterator, ListIterator, provides additional iteration capabilities, in particular, passing through the list in reverse order. In the following example, to check whether the word is a palindrome, a list of characters and a ListIterator are used, which provides the reverse order:

package ua.inf.iwanoff.oop.second;

import java.util.*;

public class ListIteratorTest {

    public static void main(String[] args) {
        String palStr = "racecar";
        List<Character> palindrome = new LinkedList<Character>();
        for (char ch : palStr.toCharArray()) {
            palindrome.add(ch);
        }
        System.out.println("Input string is: " + palStr);
        ListIterator<Character> iterator = palindrome.listIterator();
        ListIterator<Character> revIterator = palindrome.listIterator(palindrome.size());
        boolean result = true;
        while (revIterator.hasPrevious() && iterator.hasNext()) {
            if (iterator.next() != revIterator.previous()) {
                result = false;
                break;
            }
        }
        if (result) {
            System.out.print("Input string is a palindrome");
        }
        else {
            System.out.print("Input string is not a palindrome");
        }
    }

}

2.3.5 Additional Features for Standard Containers

Starting with Java 8, the standard interfaces of the java.util package are supplemented with methods that focus on using lambda expressions and references to methods. To ensure compatibility with previous versions, new interfaces provide the default implementation of the new methods. In particular, the Iterable interface defines the forEach() method, which allows you to perform some actions in the loop that do not change the elements of the collection. You can specify an action using a lambda expression or a reference to a method. For example:

public class ForEachDemo {
    static int sum = 0;
    
    public static void main(String[] args) {
        Iterable<Integer> numbers = new ArrayList(Arrays.asList(2, 3, 4));
        numbers.forEach(n -> sum += n);
        System.out.println(sum);
    }
}

In the above example, the sum of collection elements is calculated. The variable that holds the sum is described as a static class field, since lambda expressions cannot change local variables.

The Collection interface defines the removeIf() method, which allows you to remove items from the collection if items match a certain filter rule. In the following example, odd items are removed from the collection of integers. The forEach() method is used for columnwise output the collection items:

Collection<Integer> c = new ArrayList(Arrays.asList(2, 4, 11, 8, 12, 3));
c.removeIf(k -> k % 2 != 0);
// The rest of the items are displayed columnwise:
c.forEach(System.out::println);

The List interface provides methods replaceAll() and sort(). The second one can be used instead of the analogous static method of the Collections class, but the definition of the sorting feature is obligatory:

List<Integer> list = new ArrayList(Arrays.asList(2, 4, 11, 8, 12, 3));
list.replaceAll(k -> k * k); // replace the numbers with their second powers
System.out.println(list);    // [4, 16, 121, 64, 144, 9]
list.sort(Integer::compare);
System.out.println(list);    // [4, 9, 16, 64, 121, 144]
list.sort((i1, i2) -> Integer.compare(i2, i1));
System.out.println(list);    // [144, 121, 64, 16, 9, 4]

2.4 Working with Queues and Stacks

A queue in the broad sense is a data structure that is filled in by element, and it allows getting objects from it according to a certain rule. In the narrow sense, this rule is "First In - First Out" (FIFO). In a queue organized on the principle of FIFO, adding an element is possible only at the end of the queue, and getting is only possible from the beginning of the queue.

In the container library, the queue is represented by the Queue interface. Methods declared this interface are listed in the table below:

Type of operation	Throws an exception	Returns a special value
Adding	`add(e)`	`offer(e)`
Obtaining an item with removing	`remove()`	`poll()`
Obtaining an item without removing	`element()`	`peek()`

The offer() method returns false if the item could not be added, for example, if the queue has a limited number of items. In this case, the add() method throws an exception. Similarly, remove() and element() throw an exception if the queue is empty, but poll() and peek() in this case return null.

The most convenient way to implement the queue is the use of the LinkedList class that implements the Queue interface. For example:

package ua.inf.iwanoff.oop.second;

import java.util.LinkedList;
import java.util.Queue;

public class SimpleQueueTest {
 
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.add("First");
        queue.add("Second");
        queue.add("Third");
        queue.add("Fourth");
        String s;
        while ((s = queue.poll()) != null) {
            System.out.print(s + " "); // First Second Third Fourth
        }
    }

}

The PriorityQueue class arranges the elements according to the comparator (the object that implements the Comparator interface) specified in the constructor as a parameter. If an object is created using a constructor without parameters, the elements will be ordered in a natural way (ascending for numbers, in alphabetical order for strings). For example:

package ua.inf.iwanoff.oop.second;

import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueTest {
 
    public static void main(String[] args) {
        Queue<String> queue = new PriorityQueue<>();
        queue.add("First");
        queue.add("Second");
        queue.add("Third");
        queue.add("Fourth");
        String s;
        while ((s = queue.poll()) != null) {
            System.out.print(s + " "); // First Fourth Second Third
        }
    }

}

The Deque interface (double-ended-queue) provides the ability to add and remove items from both ends. Methods declared in this interface are listed below:

Type of operation	Working with the first element	Working with the last element
Adding	`addFirst(e) offerFirst(e)`	`addLast(e) offerLast(e)`
Obtaining an item with removing	`removeFirst() pollFirst()`	`removeLast() pollLast()`
Obtaining an item without removing	`getFirst() peekFirst()`	`getLast() peekLast()`

Each pair represents the function that throws an exception, and the function that returns some special value. There are also methods for removing the first (or last) occurrence of a given element (removeFirstOccurence() and removeLastOccurence(), respectively).

You can use whether the special ArrayDeque class or LinkedList to implement the interface.

A stack is a data structure organized on the principle "last in – first out" (LIFO). There are three stack operations: adding element (push), removing element (pop) and reading head element (peek).

In JRE 1.1, the stack is represented by the Stack class. For example:

package ua.inf.iwanoff.oop.second;

import java.util.Stack;

public class StackTest {
  
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        stack.push("First");
        stack.push("Second");
        stack.push("Third");
        stack.push("Fourth");
        String s;
        while (!stack.isEmpty()) {
            s = stack.pop();
            System.out.print(s + " "); // Fourth Third Second First
        }
    }

}

This class is currently not recommended for use. Instead, you can use the Deque interface, which declares the similar methods. For example:

package ua.inf.iwanoff.oop.second;

import java.util.ArrayDeque;
import java.util.Deque;

public class AnotherStackTest {

    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();
        stack.push("First");
        stack.push("Second");
        stack.push("Third");
        stack.push("Fourth");
        String s;
        while (!stack.isEmpty()) {
            s = stack.pop();
            System.out.print(s + " "); // Fourth Third Second First
        }
    }

}

Stacks are often used in various algorithms. In particular, it is often possible to implement a complex algorithm without recursion with the help of a stack.

2.5 Static Methods of the Collections Class. Algorithms

2.5.1 Creating Special Containers using the Collections Class

As the Arrays class for arrays, collections have an assistant Collections class. This class provides a number of functions for working with collections, including lists. A large group of functions is designed to create collections of different types. The following example demonstrates the creation of collections using static Collections methods: respectively, a blank list (emptyList()), singleton (singletonList()), and a read-only list ((unmodifiableList()) , or a read-only collection (unmodifiableCollection()):

import java.util.*;

public class CollectionsCreationDemo {
    public static void main(String[] args) {
        List<Integer> emptyList = Collections.emptyList();
        System.out.println(emptyList); // []
        List<Integer> singletonList = Collections.singletonList(10);
        System.out.println(singletonList); // [10]
        List<Integer> list = new ArrayList<>(Arrays.<Integer>asList(1, 2, 3));
        List<Integer> unmodifiableList = Collections.unmodifiableList(list);
        Collection<Integer> collection = Collections.unmodifiableCollection(list);
    }
}

All of the above functions create read-only collections.

Similarly, methods that create the corresponding sets are emptySet(), singleton(), and unmodifiableSet().

2.5.2 Algorithms

The algorithm of the collection library is a certain function that implements the work with the collection (obtaining a certain result or converting the elements of the collection). In the Java Collections API, this function is usually static and generic.

Like Arrays class, Collections class contains static functions for sorting and filling collections (sort() and fill() accordingly), with the same rules of usage. In addition, there are a large number of static functions to process lists without looping. This, for example, max() (searches for the maximum element), min() (finds the minimum element), indexOfSubList() (searches index of the first complete occurrence of some list), frequency() (determines the count of occurrence of a particular element within the list), reverse() (allocates elements in reverse order), rotate() (provides cyclic shift of elements), shuffle() (shuffles elements), nCopies() (creates a new list with a specific number of identical elements). The use of these functions can be illustrated by the following example:

List<Integer> a = Arrays.asList(0, 1, 2, 3, 3, -4);
System.out.println(Collections.max(a)); // 3 
System.out.println(Collections.min(a)); // -4
System.out.println(Collections.frequency(a, 2)); // 1 time
System.out.println(Collections.frequency(a, 3)); // 2 times
Collections.reverse(a);   // reverse order
System.out.println(a);    // [-4, 3, 3, 2, 1, 0]
Collections.rotate(a, 3); // cyclic shift by 3 positions
System.out.println(a);    // [2, 1, 0, -4, 3, 3]
List<Integer> sublist = Collections.nCopies(2, 3); // the new list contains 2 threes 
System.out.println(Collections.indexOfSubList(a, sublist)); // 4
Collections.shuffle(a);   // shuffle elements
System.out.println(a);    // elements in random order
Collections.sort(a);
System.out.println(a);    // [-4, 0, 1, 2, 3, 3]
List<Integer> b = new ArrayList<Integer>(a);
Collections.fill(b, 8);
System.out.println(b);    // [8, 8, 8, 8, 8, 8]
Collections.copy(b, a);
System.out.println(b);    // [-4, 0, 1, 2, 3, 3]
System.out.println(Collections.binarySearch(b, 2)); // 3
Collections.swap(b, 0, 5);
System.out.println(b);    // [3, 0, 1, 2, 3, -4]
Collections.replaceAll(b, 3, 10);
System.out.println(b);    // [10, 0, 1, 2, 10, -4]

The Collections class also provides methods specifically for working with lists, for example, getting the starting position of the first and last occurrence of the specified sublist in the list (indexOfSubList(), lastIndexOfSubList()), etc.

2.6 Working with Sets and Maps

2.6.1 Sets

A set is a collection that does not contain the same elements. The three main implementations of the Set interface are HashSet, LinkedHashSet and TreeSet. Like lists, sets are generic types. HashSet and LinkedHashSet classes use hash codes to identify an item. The TreeSet class uses a binary tree to store elements and guarantees their particular order.

The add() method adds an element to a set and returns true if the element was previously absent. Otherwise, the item is not added, and the add() method returns false. All elements of the set are cleared using the clear() method.

Set<String> s = new HashSet<String>();
System.out.println(s.add("First"));  // true
System.out.println(s.add("Second")); // true
System.out.println(s.add("First"));  // false
System.out.println(s);               // [First, Second]
s.clear();            
System.out.println(s);               // []

The remove() method removes the specified element from the set, if present. The method contains() returns true if this set contains the specified element.

In the following example, ten random values in the range from -9 to 9 are added to the set of integers:

package ua.inf.iwanoff.oop.second;

import java.util.*;

public class SetOfIntegers {

    public static void main(String[] args) {
        Set<Integer> set = new TreeSet<Integer>();
        Random random = new Random();
        for (int i = 0; i < 10; i++) {
            Integer k = random.nextInt() % 10;
            set.add(k);
        }
        System.out.println(set);
    }

}

The resulting set usually contains less than 10 numbers, since individual values can be repeated. Since we use TreeSet, the numbers are stored and displayed in ascending order. In order to add ten different numbers, the program should be modified, with the use of the while instead of for:

while (set.size() < 10) {
    . . .
}

It is possible to create an array that contains copies of the set items. In this way, items can be accessed by index. For example, we can output set elements in reverse order:

Set<Integer> set = new HashSet<>(Arrays.asList(1, 2, 4));
Object[] arr = set.toArray();
for (int i = set.size() - 1; i >= 0; i--) {
    System.out.println(arr[i]);
}

Since the set can contain only different elements, it can be used to count different words, letters, numbers, etc.: a set is created and the size() method is invoked. Applying TreeSet, you can display words and letters alphabetically. In the following example, sentences are entered and all the different letters of the sentence (not including separators) are displayed in alphabetical order:

package ua.inf.iwanoff.oop.second;

import java.util.*;

public class Sentence {
  
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // The nextLine() function reads the string to the end of line:
        String sentence = scanner.nextLine();
        // Create a set of separators:
        Set<Character> delimiters = new HashSet<Character>(
            Arrays.asList(' ', '.', ',', ':', ';', '?', '!', '-', '(', ')', '\"'));
        // Create a set of letters:
        Set<Character> letters = new TreeSet<Character>();
        // Add all letters except separators:
        for (int i = 0; i < sentence.length(); i++) {
            if (!delimiters.contains(sentence.charAt(i))) {
                letters.add(sentence.charAt(i));
            }
        }
        System.out.println(letters);
    }
  
}

You can specify the sort order of TreeSet elements by implementing the Comparable interface, or by passing the reference to the class object that implements the Comparator interface into the TreeSet constructor. For example, you can sort the tree in reverse order:

package ua.inf.iwanoff.oop.second;

import java.util.*;

public class CompTest {

    public static void main(String args[]) {
        TreeSet<String> ts = new TreeSet<String>(new Comparator<String>() 
        { 
            @Override
            public int compare(String s1, String s2) {
                return s2.compareTo(s1);
            }
        });
        ts.add("C");
        ts.add("E");
        ts.add("D");
        ts.add("B");
        ts.add("A");
        ts.add("F");
        for (String element : ts)
            System.out.print(element + " ");
        }
    }
}

2.6.2 Associative Containers

Associative arrays hold pairs of references to objects. Associative arrays are also generic types. Associative arrays in Java are represented by generic Map interface. The most-used implementation of Map interface is HashMap. SortedMap, an interface derived from Map, assumes storing of pairs, which are sorted by key. The NavigableMap interface, appearing on the java SE 6, extends the SortedMap and adds new key search capabilities. This interface is implemented by the TreeMap class.

Each value (object) that is stored in the associative array is associated with the specific value of another object (key). You can add a new pair using put(key, value) method. If the map previously contained a mapping for this key, the old value is replaced by the specified value. The method returns previous value associated with specified key, or null if there was no mapping for key. The get(Object key) method returns the object by the given key. To check whether key (value) presents in a map, the methods containsKey() and containsValue() are used.

At the logical level, an associative array can be represented through three auxiliary collections:

keySet: set of keys;
values: list of values;
entrySet: set of key-value pairs.

Due to the functions keySet(), values(), and entrySet(), you can perform certain actions, e.g. successive passage of the elements.

The following program counts entering of different words in a statement. Words and their counts are stored in a map. Usage of the TreeMap class guarantees alphabetic order of words (keys).

package ua.inf.iwanoff.oop.second;

import java.util.*;

public class WordsCounter {
    public static void main(String[] args) {
        Map<String, Integer> m = new TreeMap<String, Integer>();
        String s = "the first men on the moon";
        StringTokenizer st = new StringTokenizer(s);
        while (st.hasMoreTokens()) {
            String word = st.nextToken();
            Integer count = m.get(word);
            m.put(word, (count == null) ? 1 : count + 1);
        }
        for (String word : m.keySet()) {
            System.out.println(word + " " + m.get(word));
        }
    }

}

Using keySet() involves a separate search for each value by the key. It is more recommended to bypass the associative array through a set of pairs:

for (Map.Entry<?, ?> entry : m.entrySet())
    System.out.println(entry.getKey() + " " + entry.getValue());

The entrySet() method allows you to get representation of the associative array in the form of the Set collection.

The TreeMap sort order can also be changed by sending to the TreeMap constructor as a parameter an object that implements the Comparator interface, or by setting the key as the object that implements the Comparable interface:

package ua.inf.iwanoff.oop.second;

import java.util.*;

public class TreeMapKey implements Comparable<TreeMapKey> {
    private String name;

    public String getName() {
        return name;
    }

    public TreeMapKey(String name) {
        super();
        this.name = name;
    }

    @Override
    public int compareTo(TreeMapKey o) {
        return name.substring(o.getName().indexOf(" ")).trim()
            .compareToIgnoreCase(o.getName().substring(o.getName().indexOf(" ")).trim());
    }

    public static void main(String args[]) {
        TreeMap<TreeMapKey, Integer> tm = new TreeMap<TreeMapKey, Integer>();
        tm.put(new TreeMapKey("Peter Johnson"), new Integer(1982));
        tm.put(new TreeMapKey("John Peterson"), new Integer(1979));
        tm.put(new TreeMapKey("Jacob Nickson"), new Integer(1988));
        tm.put(new TreeMapKey("Nick Jacobson"), new Integer(1980));
        for (Map.Entry<TreeMapKey, Integer> me : tm.entrySet()) {
            System.out.print(me.getKey().getName() + ": ");
            System.out.println(me.getValue());
        }
        System.out.println();
    }

}

The Hashtable class is one of the implementations of the Map interface. Hashtable in addition to size has a capacity (buffer size, selected for elements of the array). In addition, it is characterized by the load factor - the portion of the buffer, after which the capacity automatically increases. The Hashtable() constructor without parameters creates an empty object with a capacity of 101 elements and a load index of 0.75.

The Properties class derived from Hashtable stores pairs of strings. If in a particular task keys and values of the associative array elements are of the String type, it is more convenient to use the Properties class. In the Properties class, methods are getProperty(String key) and setProperty(String key, String value).

Starting with Java 8, new methods have been added to the Map interface. The added methods listed in the table:

Method	Description
`V getOrDefault(Object key, V& defaultValue)`	Returns a value, or a default value, if the key is missing
`V putIfAbsent(K key, V value)`	Adds a pair if the key is missing and returns the value
`boolean remove(Object key, Object value)`	Removes a pair if it is present
`boolean replace(K key, V oldValue, V newValue)`	Replaces value with the new one if pair is present
`V replace(K key, V value)`	Replaces the value if the key is present, returns the old value
`V compute(K key, BiFunction<?& super K, super V, ? extends V> remappingFunction)`	Invokes the function to construct a new value. A new pair is added, a pair that existed before is deleted, and a new value is returned
`V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)`	If a specified key is present, a new function is called to create a new value, and the new value replaces the previous one.
`V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)`	Returns the value by the key. If the key is missing, a new pair is added, the value is calculated by function
`V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction)`	If the key is absent, then a new pair is entered and the value `v` is returned. Otherwise, the given function returns a new value based on the previous value and the key is updated to access this value. and then it returns
`void forEach(BiConsumer<? super K, ? super V> action)`	Performs a given action on each element

The following example demonstrates the use of some of these methods:

import java.util.HashMap;
import java.util.Map;

public class MapDemo {

    static void print(Integer i, String s) {
        System.out.printf("%3d %10s %n", i, s);
    }

    public static void main(String[] args) {
        Map<Integer, String> map = new HashMap<>();
        map.put(1, "one");
        map.put(2, "two");
        map.put(7, "seven");
        map.forEach(MapDemo::print); // columnwise output
        System.out.println(map.putIfAbsent(7, "eight")); // seven
        System.out.println(map.putIfAbsent(8, "eight")); // null
        System.out.println(map.getOrDefault(2, "zero")); // two
        System.out.println(map.getOrDefault(3, "zero")); // zero
        map.replaceAll((i, s) -> i > 1 ? s.toUpperCase() : s);
        System.out.println(map); // {1=one, 2=TWO, 7=SEVEN, 8=EIGHT}
        map.compute(7, (i, s) -> s.toLowerCase());
        System.out.println(map); // {1=one, 2=TWO, 7=seven, 8=EIGHT}
        map.computeIfAbsent(2, (i) -> i + "");
        System.out.println(map); // nothing changed
        map.computeIfAbsent(4, (i) -> i + "");
        System.out.println(map); // {1=one, 2=TWO, 4=4, 7=seven, 8=EIGHT}
        map.computeIfPresent(5, (i, s) -> s.toLowerCase());
        System.out.println(map); // nothing changed
        map.computeIfPresent(2, (i, s) -> s.toLowerCase());
        System.out.println(map); // {1=one, 2=two, 4=4, 7=seven, 8=EIGHT}
        // Adding a new pair:
        map.merge(9, "nine", (value, newValue) -> value.concat(newValue));
        System.out.println(map.get(9));                  // nine
        // The text is concatenated with the previous one:
        map.merge(9, " as well", (value, newValue) -> value.concat(newValue));
        System.out.println(map.get(9));                  // nine as well
    }
}

2.7 Internal Representation of Sets and Associative Containers

2.7.1 Implementation of Sets and Associative Containers using Hashing

To store data in HashSet and HashMap, the so-called hashing is used. Hashing is the process of obtaining from an object a unique code using some formal algorithm. In a broad sense, the result is a sequence of bits of fixed length, in the particular case, this is a simple integer. This conversion is performed by a so-called hash function. The hash function should meet the following requirement: the hash function should return the same hash code each time it is applied to identical or equal objects.

.All Java objects inherit the standard implementation of a hashCode() function defined in the Object class. This function returns a hash code obtained by converting an object's internal address to a number, which ensures the creation of a unique code for each individual object.

Specific standard classes implement their hash functions. For example, for a string, the value of the hash function is calculated by the formula:

s[0]*31^n-1 + s[1]*31^n-2 + ... + s[n-1]

Here s[0], s[1], etc. are codes of the corresponding characters.

Containers constructed using hashing do not guarantee a certain order of storage items, but provide relatively high efficiency of search, addition and removing operations.

The mechanisms of data storage in the HashSet and HashMap classes is similar. Let's consider the representation of data on an example of the HashMap container. The nested Entry class represents a key-value pair:

static class Entry<K,V> implements Map.Entry<K,V> {
    final K key;
    V value;
    Entry<K,V> next;
    int hash;
    // ... Next, constructor and a number of auxiliary methods are implemented 
}

Objects of this class are stored in an array. First, the array is designed to store 16 items, but then its size can vary. Items of this array are called baskets, because they store references to the lists of elements (in the next field). When adding a new key-value pair, the basket number (the cell number of the array) into which the new entry puts will be calculated according to the key's hash code. In this case, the value of the hash code is projected onto an array taking into account its real size. If the basket is empty, then the reference to the added element is stored in it, if there is already an element there, then a traversal over a linked list is done and a new element is added after the last element. If an element with the same key was found in the list, the value will be replaced.

The efficiency of adding, retrieving and deleting operations depends on the implementation of the hash function. If it returns a constant value, the container is converted into a linked list with low efficiency.

2.7.2 Implementation of Containers Based on Binary Trees

A binary tree represents a tree-like data structure (graph without cycles), in which each vertex (node) has no more than two descendants (children). They are called respectively the left child and right child. In turn, they can act as vertex subtree. We can talk about the left and right subtree.

A binary tree can be used for storing objects that are ordered by a specific criterion (ordering by key). In this case we speak about the so-called binary search tree, which satisfies such rules:

the left and right subtrees are also binary search trees;
in all nodes of the left subtree of some node the value of the keys is less than the value of the key in this node;
in all nodes of the right subtree of the same node the value of the keys is not less than the value of the key in this node.

Usually binary search trees implement such basic operations:

adding item
getting (searching) item
deleting item (node)
bypass the tree

The binary tree is called perfectly balanced if for each of its vertices, the number of vertices in the left and right subtree differs by no more than 1. In an unbalanced tree, this rule is not followed. The simplest implementation of a tree gives an unbalanced tree. Depending on the order of adding elements, the tree can be balanced or completely unbalanced. Suppose a binary tree maintains integer values. If the numbers from 1 to 7 are added in a certain order (for example, 4, 2, 3, 1, 6, 7, 5), a perfectly balanced tree may come out:

If you add numbers in ascending order, a highly unbalanced tree will be created:

We can say about a different degree of balance. Unbalance reduces performance when looking for an item. However, the creation of perfectly balanced trees causes computational difficulties when adding and removing. In practice, partially balanced trees are often used.

The so-called red-black tree is a binary search tree that automatically maintains a certain balance. This allows you to effectively implement the basic operations (adding, searching and deleting). Each node of the tree is placed in accordance with the color - red or black. Fictitious leaf nodes that contain no data attached to each node. There are additional requirements:

the root of the tree should be black
all leaf nodes are black
both children of each red node are black
each simple path from this node to any leaf node that is its descendant contains the same number of black nodes

For example, a red-black tree might be as follows (from the site en.wikipedia.org):

When adding a new node (always red), it is sometimes needed to repaint the tree and rotate it. Adding nodes, taking into account the constraints and the "rotation" with the transfer of nodes, makes the tree self-balancing. Red-black trees are used to build TreeSet and TreeMap containers.

2.8 Creating Custom Containers

In spite of the large number of standard container classes, there is sometimes a need to create custom containers. These can be, for example, complex trees, more flexible lists, specialized collections of items, etc.

In some cases, it is only necessary to bypass elements of some sequence using the alternative form of the for loop. It's enough to implement the Iterable<> interface. It requires the implementation of the function that returns an iterator. Often, the implementation of an iterator needs the creation an internal non-static class. The following example creates a Sentence with an iterator that moves around the individual words. The program displays the words of the entered sentence in separate lines:

package ua.inf.iwanoff.oop.second;

import java.util.Iterator;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Sentence implements Iterable<String> {
    private String text;

    public Sentence(String text) {
        this.text = text;
    }

    private class WordsIterator implements Iterator<String> {
        StringTokenizer st = new StringTokenizer(text);

        @Override
        public boolean hasNext() {
            return st.hasMoreTokens();
        }

        @Override
        public String next() {
            return st.nextToken();
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();     
        }

    }

    public Iterator<String> iterator() {
        return new WordsIterator();
    }

    public static void main(String[] args) {
        String text = new Scanner(System.in).nextLine();
        Sentence sentence = new Sentence(text);
        for (String word : sentence) {
            System.out.println(word);
        }
    }

}

In most cases the creation of iterators required definition of the so-called cursor, the variable referring to the current element of the sequence. In this case, the implementation of the next() method involves moving the cursor and returning the reference to the current element. For example:

public class SomeArray<E> implements Iterable<E> {
    private E[] arr;

    ...

    private class InnerIterator implements Iterator<E> {
        int cursor = -1;

        @Override
        public boolean hasNext() {
            return cursor < arr.length – 1;
        }

        @SuppressWarnings("unchecked")
        @Override
        public E next() {   
            return arr[++cursor];
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException();   
        }
    }

    @Override
    public Iterator<E> iterator() {
        return new InnerIterator();
    }
  ...
}

To create a full-fledged custom container, it's best way to use existing abstract classes. These are AbstractCollection<E>, AbstractList<E>, AbstractMap<K,V>, AbstractQueue<E>, AbstractSet<E>, as well as some abstract auxiliary classes. For example, in order to create your own read only list, it's formally enough to override two abstract methods, get() and size(). When working with read-only lists, methods such as add(), set(), remove(), and others that are intended to change the list generate an UnsupportedOperationException exception. The following example creates the simplest read only list:

package ua.inf.iwanoff.oop.second;

import java.util.AbstractList;

public class MyList extends AbstractList<String> {
    String[] arr = { "one", "two", "three" };

    @Override
    public String get(int index) {
        return arr[index];
    }

    @Override
    public int size() {
        return arr.length;
    }

    public static void main(String[] args) {
        MyList list = new MyList();
        for (String elem : list) {
            System.out.println(elem); {
        }
        System.out.println(list.subList(0, 2));  // [one, two]
        System.out.println(list.indexOf("two")); // 1
        list.add("four"); // Exception "UnsupportedOperationException"
    }
}

In order to implement the container for reading and writing, it is necessary to override some extra methods. In the example 3.9, an appropriate container is implemented

2.9 Testing in Java. Using JUnit

2.9.1 Overview

Testing is one of the most important components of the software development process. Software testing is performed in order to obtain information about the quality of the software product. There are many approaches and techniques for testing and verifying software.

The paradigm of test-driven development (development through testing) defines the technique of software development, based on the use of tests to stimulate the writing of code, and to verify it. Code development is reduced to repeating the test-code-test cycle with subsequent refactoring.

The level of testing at which the least possible component to be tested, such as a single class or function, is called unit testing. Appropriate testing technology assumes that tests are developed in advance, before writing the real code, and the development of the code of the unit (class) is completed when its code passes all the tests.

2.9.2 Java Tools for Diagnosing Runtime Errors

Many modern programming languages, including Java, include syntactic assertions. The assert keyword has appeared in Java since version JDK 1.4 (Java 2). The assert work can be turned on or off. If the execution of diagnostic statements is enabled, the work of assert is as follows: an expression of type boolean is executed and if the result is true, the program continues, otherwise an exception of java.lang.AssertionError throws. Suppose, according to the logic of the program, the variable c must always be positive. Execution of such a fragment of the program will not lead to any consequences (exceptions, emergency stop of the program, etc.):

int a = 10;
int b = 1;
int c = a - b;
assert c > 0;

If, due to an incorrect software implementation of the algorithm, the variable c still received a negative value, the execution of a fragment of the program will lead to the throwing of an exception and an abnormal termination of the program, if the processing of this exception was not provided:

int a = 10;
int b = 11;
int c = a - b;
assert c > 0; // exception is thrown

After the assertion, you can put a colon, followed by a string of the message. Example:

int a = 10;
int b = 11;
int c = a - b;
assert c > 0 : "c cannot be negative";

In this case, the corresponding string is the exception message string.

Assert execution is usually disabled in integrated development environments. To enable assert execution in the Eclipse environment, use the Run | Run Configurations menu function, in the appropriate dialog box on the Arguments tab in the VM arguments input area, enter -ea and run the program.

Note: IntelliJ IDEA environment has a similar Run | Edit Configurations menu function. In the Run/Debug Configurations window, enter -ea in the VM Options input line.

In these examples, the values that are checked with assert are not entered from the keyboard, but are defined in the program to demonstrate the correct use of assert - the search for logical errors, rather than checking the correctness of user input. Exceptions, conditional statements, etc. should be used to verify the correctness of the data entered. The use of assertion validation is not allowed, because in the future the program will be started without the -ea option and all assertions will be ignored. The expression specified in the statement should not include actions that are important in terms of program functionality. For example, if the assertion check is the only place in the program from which a very important function is called,

public static void main(String[] args) {
    //...
    assert f() : "failed";
    //...
}

public static boolean f() {
    // Very important calculations
    return true;
}

then after disabling assertions the function will not be called at all.

2.9.3 Basics of Using JUnit

In contrast to the use of diagnostic statements, which performs testing of algorithms "from the inside", unit testing provides verification of a particular unit as a whole, testing "outside" the functionality of the unit.

The most common unit testing support for Java software is JUnit, an open unit testing library. JUnit allows:

create tests for individual classes;
create test suits;
create a series of tests on repeating sets of objects.

Now the JUnit 5 version is now relevant. But also a very widespread is JUnit 4 version.

To create a test, you need to create a class that needs to be tested, as well as create a public class for testing with a set of methods that implement specific tests. Each test method must be public, void, and have no parameters. The method must be marked with an annotation @Test:

public class MyTestCase { 
    ...
    @Test
    public void testXXX() { 
    ...
    } 
    ...
}

Note: to use the @Test and other similar annotations should be added import statements import org.junit.jupiter.api.*; for JUnit 5) or import org.junit.*; (for JUnit 4) .

Within such methods, you can use the following assertion methods:

assertTrue(expression);                 // Fails the test if false
assertFalse(expression);                // Fails the test if true
assertEquals(expected, actual);         // Fails the test if not equivalent
assertNotNull(new MyObject(params));    // Fails the test if null
assertNull(new MyObject(params));       // Fails the test if not null
assertNotSame(expression1, expression2);// Fails the test if both links refer to the same object
assertSame(expression1, expression2);   // Fails the test if the objects are different
fail(message)                           // Immediately terminates the test with a failure message

Here MyObject is a class that is being tested. These Assertion class methods (Assert class methods for JUnit 4) are accessed using static import: import static org.junit.jupiter.api.Assertion.*; (for JUnit 5) or import static org.junit.Assert.*;. These methods also are implemented with an additional message parameter of type String, which specifies the message that will be displayed if the test failed.

The IntelliJ IDEA provides built-in JUnit support. Suppose a new project has been created. The project contains a class with two functions (static and non-static) that should be tested:

package ua.inf.iwanoff.oop.second;

public class MathFuncs {
    public static int sum(int a, int b) {
        return a + b;
    }

    public int mult(int a, int b) {
        return a * b;
    }
}

Within the project, we can manually create a folder, for example, tests. Next we should set Mark Directory as | Test Sources Root with the context menu.

Returning to the MathFuncs class, choosing it in the code editor, through the context menu we can generate tests: Generate... | Test.... In the dialog that opened, we select the version of the JUnit library. The desired option is JUnit5. We can also correct the class name that we offer: MathFuncsTest. In most cases, the correction of this name is not needed. Then we select the names of methods that are subject to testing. In our case, there are sum() and mult(). Such a code will be received:

package ua.inf.iwanoff.oop.second;

import static org.junit.jupiter.api.Assertions.*;

class MathFuncsTest {

    @org.junit.jupiter.api.Test
    void sum() {
    }

    @org.junit.jupiter.api.Test
    void mult() {
    }
}

IntelliJ IDEA indicates errors in this code (Cannot resolve symbol 'junit'). By clicking Alt+Enter, we get a hint: Add 'JUnit 5.7.0' to classpath. Taking advantage of this prompt, we add the relevant library and get the code without errors.

We can optimize the code by adding imports. We add testing of MathFuncs class methods into MathFuncsTest methods. To test the work of mult() we need to create an object:

package ua.inf.iwanoff.oop.second;

import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;

class MathFuncsTest {

    @Test
    void sum() {
        assertEquals(MathFuncs.sum(4, 5), 9);
    }

    @Test
    void mult() {
        assertEquals(new MathFuncs().mult(3, 4), 12);
    }
}

You can run tests to run through the Run menu. The normal completion of the process indicates no errors during verification. If you add a code that distorts computing in the MathFuncs class, for example

    public int mult(int a, int b) {
        return a * b + 1;
    }

running tests will result in AssertionFailedError message. You can see how many tests have been successful, and how much it is not passed.

If some actions need to be taken before performing the test function, for example, to format the values of variables, then such initialization is made in a separate static method, which is preceded by an annotation @BeforeAll(@BeforeClass in JUnit 4):

@BeforeAll
public static void setup(){
      ...
}

Similarly, the methods in which the actions needed after testing are preceded by@AfterAll annotation (@AfterClass in JUnit 4). Methods must be public static void.

In our example, we can create an object in advance, as well as add messages after the tests are completed:

package ua.inf.iwanoff.oop.second;

import org.junit.jupiter.api.*;
import static org.junit.jupiter.api.Assertions.*;

class MathFuncsTest {
    private static MathFuncs funcs;

    @BeforeAll
    public static void init() {
        funcs = new MathFuncs();
    }

    @Test
    void sum() {
        assertEquals(MathFuncs.sum(4, 5), 9);
    }

    @Test
    void mult() {
        assertEquals(funcs.mult(3, 4), 12);
    }

    @AfterAll
    public static void done() {
        System.out.println("Tests finished");
    }
}

Annotation @BeforeEach (@Before in JUnit 4) indicates that the method is called before each test method. Accordingly, @AfterEach (@After in JUnit 4) indicates that the method is called after each successful test method. Methods marked by these annotations should not be static.

You can also test methods that return void. Calling such a method involves performing an action (for example, creating a file, changing the value of a field, etc.). It is necessary to check whether such action took place. For example:

void setValue(into value) {
    this.value = value;
}

...

public void testSetValue() {
    someObject.setValue(123);
    assertEquals(123, someObject.getValue());
}

However, as a rule, testing the simplest access methods (setters and getters) seems excessive and is not recommended.

3 Sample Programs

3.1 Generic Function that Searches for a Given Item

Suppose we need to implement a static generic function that return index the first occurrence of a specific value. The function should return index of that element, or -1 if there is none. A class with the required function would look as follows:

package ua.inf.iwanoff.oop.second;

public class ElementFinder {

    public static <E>int indexOf(E[] arr, E elem) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i].equals(elem)) {
                return i;
            }
        }
        return -1;
    }
  
    public static void main(String[] args) {
        Integer[] a = {1, 2, 11, 4, 5};
        System.out.println(indexOf(a, 11));    // 2
        System.out.println(indexOf(a, 12));    // -1
        String[] b = {"one", "two"};
        System.out.println(indexOf(b, "one")); // 0
    }

}

To compare objects, we need to use equals() method instead of ==.

3.2 Sum of List Elements of Double Type

The following program reads real numbers from keyboard adding them to list, and then finds their sum.

package ua.inf.iwanoff.oop.second;

import java.util.*;

public class SumOfElements {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Double> a = new ArrayList<>();
        double d = 1; // the initial value should not be 0
        while (d != 0) {
            d = scanner.nextDouble();
            a.add(d);
        }
        double sum = 0;
        for (double x : a) { // implicit iterator
            sum += x;
        }
        System.out.println("Sum is " + sum);
    }

}

Reading numbers from the keyboard is carried out until the user enters a value of 0.

3.3 Index of the Maximum Element

The following program finds index of the maximum element in a list of integer numbers. To fill out the list we can use an array with the initial values of the elements. An array is implicitly created while executing the asList() function.

package ua.inf.iwanoff.oop.second;

import java.util.*;

public class MaxElement {

    public static void main(String[] args) {
        List<Integer> a = Arrays.asList(2, 3, -7, 8, 11, 0);
        int indexOfMax = 0;
        for (int i = 1; i < a.size(); i++) {
            if (a.get(i) > a.get(indexOfMax)) {
                indexOfMax = i;
            }
        }
        System.out.println(indexOfMax + " " + a.get(indexOfMax));
    }

}

Iterator cannot be used because the index is needed.

3.4 Country Data in the Associative Array

Country data (name and territory) can be stored in associative array. The output is carried out in alphabetical order of the countries:

package ua.inf.iwanoff.oop.second;

import java.util.Map;
import java.util.SortedMap;
import java.util.TreeMap;

public class Countries {

    public static void main(String[] args) {
        SortedMap<String, Double> countries = new TreeMap<>();
        countries.put("Ukraine", 603700.0);
        countries.put("Germany", 357021.0);
        countries.put("France", 547030.0);
        for (Map.Entry<?, ?> entry : countries.entrySet())
            System.out.println(entry.getKey() + " " + entry.getValue());  
    }

}

3.5 Letters of Sentence in Alphabetical Order

In the example below, sentence is entered and all the different letters (except separators) are displayed in alphabetical order:

package ua.inf.iwanoff.oop.second;

import java.util.*;

public class Sentence {
  
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // The nextLine() function reads the line to the end:
        String sentence = scanner.nextLine();
        // Create a set of separators:
        Set<Character> delimiters = new HashSet<Character>(
            Arrays.asList(' ', '.', ',', ':', ';', '?', '!', '-', '(', ')', '\"'));
        // Create a set of letters:
        Set<Character> letters = new TreeSet<Character>();
        // Add all the letters except separators:
        for (int i = 0; i < sentence.length(); i++) {
            if (!delimiters.contains(sentence.charAt(i))) {
                letters.add(sentence.charAt(i));
            }
        }
        System.out.println(letters);
    }
  
}

3.6 The Product of the Entered Numbers

In the example below, integers are entered, displayed as a decrease, and their product is calculated. The entering ends with zero:

package ua.inf.iwanoff.oop.second;

import java.util.*;

public class Product {

    @SuppressWarnings("resource")
    public static void main(String[] args) {
        Queue<Integer> queue = new PriorityQueue<>(100, new Comparator<Integer>() {
            @Override
            public int compare(Integer i1, Integer i2) {
                return -Double.compare(i1, i2);
            }
        });
        Scanner scanner = new Scanner(System.in);
        Integer k;
        do {
            k = scanner.nextInt();
            if (k != 0) {
                queue.add(k);
            }
        }
        while (k != 0);
        int p = 1;
        while ((k = queue.poll()) != null) {
            p *= k;
            System.out.print(k + " "); 
        }
        System.out.println();
        System.out.println(p);
    }

}

3.7 Creation of a Singly Linked List

The following example creates and fills a singly linked list:

package ua.inf.iwanoff.oop.second;

public class SinglyLinkedList<E> {

    private class Node {
        E    data;
        Node next;
        Node(E data, Node next) {
            this.data = data;
            this.next = next;
        }
    }

    private Node first = null;
    private Node last  = null;
    private int  count = 0;

    public void add(E elem) {
        Node newNode = new Node(elem, null);
        if (last == null) {
            first = newNode;
        }
        else {
            last.next = newNode;
        }
        last = newNode;
        count++;
    }

    public void removeFirstOccurrence(E value) {
        // Separately check the first element
        if (first != null && first.data.equals(value)) { 
            first = first.next; 
            count--; 
        }
        else {
            Node link = first;
            while (link.next != null) {
                if (link.next.data.equals(value)) {
                    link.next = link.next.next;
                    count--;
                }
                if (link.next == null) {
                    last = link;
                    break; // the last item was removed
                }
                link = link.next;
            }
        }
    }

    public final int size() {
        return count;
    }

    @Override
    public String toString() {
        String s = "size = " + size() + "\n[";
        Node link = first;
        while (link != null) {
            s += link.data;
            link = link.next;
            if (link != null) {
                s += ", ";
            }
        }
        s += "]\n";
        return s;
    }

    public static void main(String[] args) {
        SinglyLinkedList<Integer> list = new SinglyLinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        System.out.println(list);
        // Remove the intermediate element:
        list.removeFirstOccurrence(3); 
        System.out.println(list);
        // Remove the first element:
        list.removeFirstOccurrence(1);
        System.out.println(list);
        // Remove the last element:
        list.removeFirstOccurrence(4);
        System.out.println(list);
    }
}

3.8 Creating a Binary Tree

The following example creates and fills a plain (unbalanced) binary tree containing a pair of integer / string:

package ua.inf.iwanoff.oop.second;

public class BinaryTree {

    // Class for node representation
    public static class Node {
        int    key;
        String value;
        Node   leftChild;
        Node   rightChild;
        Node(int key, String name) {
            this.key = key;
            this.value = name;
        }
        @Override
        public String toString() {
            return "Key: " + key + " Value:" + value;
        }
    }

    private Node root;

    public void addNode(int key, String value) {
        // Create a new node:
        Node newNode = new Node(key, value);
        if (root == null) { // first added node
            root = newNode;
        }
        else {
            // Begin bypass:
            Node currentNode = root;
            Node parent;
            while (true) {
                parent = currentNode;
                // Check the keys:
                if (key < currentNode.key) {
                    currentNode = currentNode.leftChild;
                    if (currentNode == null) {
                        // Place the node in the appropriate place:
                        parent.leftChild = newNode;
                        return;
                    }
                }
                else { 
                    currentNode = currentNode.rightChild;
                    if (currentNode == null) {
                        // Place the node in the appropriate place:
                        parent.rightChild = newNode;
                        return;
                    }
                }
            }
        }
    }

    // Bypass the nodes in order of increasing the keys
    public void traverseTree(Node currentNode) {
        if (currentNode != null) {
            traverseTree(currentNode.leftChild);
            System.out.println(currentNode);
            traverseTree(currentNode.rightChild);
        }
    }

    public void traverseTree() {
        traverseTree(root);
    }

    // Search the node by key
    public Node findNode(int key) {
        Node focusNode = root;
        while (focusNode.key != key) {
            if (key < focusNode.key) {
                focusNode = focusNode.leftChild;
            }
            else {
                focusNode = focusNode.rightChild;
            }
            // Not found:
            if (focusNode == null) {
                return null;
            }
        }
        return focusNode;
    }

    // Test:
    public static void main(String[] args) {
        BinaryTree continents = new BinaryTree();
        continents.addNode(1, "Europe");
        continents.addNode(3, "Africa");
        continents.addNode(5, "Australia");
        continents.addNode(4, "America");
        continents.addNode(2, "Asia");
        continents.addNode(6, "Antarctica");
        continents.traverseTree();
        System.out.println("\nContinent with key 4:");
        System.out.println(continents.findNode(4));
    }
}

3.9 Creating a New Container Based on the ArrayList

In the following example, a class is implemented to represent an array whose indexing begins with 1. It is necessary to redefine all methods associated with the index. Inside, we can use ArrayList:

package ua.inf.iwanoff.oop.second;

import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;

@SuppressWarnings("unchecked")
public class ArrayFromOne<E> extends AbstractList<E> {
    ArrayList<Object> arr = new ArrayList<>();

    @Override
    public E get(int index) {
        return (E)arr.get(index – 1);
    }

    @Override
    public int size() {
        return arr.size();
    }

    @Override
    public void add(int index, E element) {
        arr.add(index – 1, element);
    }

    @Override
    public boolean add(E e) {
        return arr.add(e);
    }

    @Override
    public E set(int index, E element) {
        return (E)arr.set(index – 1, element);
    }

    @Override
    public E remove(int index) {
        return (E)arr.remove(index – 1);
    }

    @Override
    public int indexOf(Object o) {
        return arr.indexOf(o) + 1;
    }

    @Override
    public int lastIndexOf(Object o) {
        return arr.lastIndexOf(o) + 1;
    }

    @Override
    public Iterator<E> iterator() {
        return (Iterator<E>)arr.iterator();
    }

    public static void main(String[] args) {
        ArrayFromOne<Integer> a = new ArrayFromOne<>();
        a.add(1);
        a.add(2);
        System.out.println(a.get(1) + " " + a.get(2)); // 1 2
        System.out.println(a.indexOf(2));              // 2
        a.set(1, 3);
        for (Integer k : a) {
            System.out.print(k + " ");                 // 3 2
        }
        System.out.println();
        a.remove(2);
        System.out.println(a);                         // [3]
        a.addAll(Arrays.asList(new Integer[]{ 4, 5 }));
        System.out.println(a.get(3));                  // 5
    }

}

The @SuppressWarnings("unchecked") annotation before the class is required to suppress the warnings associated with explicit type casting.

3.10 Storing Census Data in a List and in a Set

Suppose we need to create classes for working with censuses. The first of them will store data using a list, the second with a set. We can add such classes to the pre-created hierarchy. The first class will store the data in the list. For sorting, it's advisable to use the sort() method of the Collections class. The class code will be as follows:

package ua.inf.iwanoff.oop.second;

import ua.inf.iwanoff.oop.first.AbstractCensus;
import ua.inf.iwanoff.oop.first.AbstractCountry;
import ua.inf.iwanoff.oop.first.CensusWithData;
import ua.inf.iwanoff.oop.first.CompareByComments;

import java.util.*;

public class CountryWithList extends AbstractCountry {
    private String name;
    private double area;
    private List<AbstractCensus> list = new ArrayList<>();

    @Override
    public String getName() {
        return name;
    }

    @Override
    public void setName(String name) {
        this.name = name;
    }

    @Override
    public double getArea() {
        return area;
    }

    @Override
    public void setArea(double area) {
        this.area = area;
    }

    @Override
    public AbstractCensus getCensus(int i) {
        return list.get(i);
    }

    @Override
    public void setCensus(int i, AbstractCensus census) {
        list.set(i, census);
    }

    @Override
    public boolean addCensus(AbstractCensus census) {
        return list.add(census);
    }

    @Override
    public boolean addCensus(int year, int population, String comments) {
        return list.add(new CensusWithData(year, population, comments));
    }

    @Override
    public int censusesCount() {
        return list.size();
    }

    @Override
    public void clearCensuses() {
        list.clear();
    }

    @Override
    public void sortByPopulation() {
        Collections.sort(list);
    }

    @Override
    public void sortByComments() {
        Collections.sort(list, new CompareByComments());
    }

    @Override
    public void setCensuses(AbstractCensus[] censuses) {
        list = new ArrayList<>(Arrays.asList(censuses));
    }

    @Override public AbstractCensus[] getCensuses() {
        return list.toArray(new AbstractCensus[0]);
    }

    public static void main(String[] args) {
        new CountryWithList().createCountry().testCountry();
    }
}

Now we can create a class that stores data in the set. Since the set is immediately ordered on a certain attribute and it is not possible to sort it, it is possible to create different variants of data sets for the getting ordered sequences.

Since the beginning of the censuses should be arranged in ascending order of the year. Therefore, we should create a separate class for the corresponding comparison:

package ua.inf.iwanoff.oop.second;

import ua.inf.iwanoff.oop.first.AbstractCensus;
import java.util.Comparator;

public class CompareByYear implements Comparator<AbstractCensus> {

    public int compare(AbstractCensus c1, AbstractCensus c2) {
        return Integer.compare(c1.getYear(), c2.getYear());
    }

}

The CountryWithSet class code will be as follows:

package ua.inf.iwanoff.oop.second;

import ua.inf.iwanoff.oop.first.AbstractCensus;
import ua.inf.iwanoff.oop.first.AbstractCountry;
import ua.inf.iwanoff.oop.first.CensusWithData;
import ua.inf.iwanoff.oop.first.CompareByComments;

import java.util.Arrays;
import java.util.SortedSet;
import java.util.TreeSet;

public class CountryWithSet extends AbstractCountry {
    private String name;
    private double area;
    private SortedSet<AbstractCensus> set = new TreeSet<>(new CompareByYear());

    @Override
    public String getName() {
        return name;
    }

    @Override
    public void setName(String name) {
        this.name = name;
    }

    @Override
    public double getArea() {
        return area;
    }

    @Override
    public void setArea(double area) {
        this.area = area;
    }

    @Override
    public AbstractCensus getCensus(int i) {
        return set.toArray(new AbstractCensus[0])[i];
    }

    @Override
    public void setCensus(int i, AbstractCensus census) {
        AbstractCensus oldCensus = getCensus(i);
        set.remove(oldCensus);
        set.add(census);
    }

    @Override
    public boolean addCensus(AbstractCensus census) {
        return set.add(census);
    }

    @Override
    public boolean addCensus(int year, int population, String comments) {
        return set.add(new CensusWithData(year, population, comments));
    }

    @Override
    public int censusesCount() {
        return set.size();
    }

    @Override
    public void clearCensuses() {
        set.clear();
    }

    @Override
    public void sortByPopulation() {
        SortedSet<AbstractCensus> newSet = new TreeSet<>();
        newSet.addAll(set);
        set = newSet;
    }

    @Override
    public void sortByComments() {
        SortedSet<AbstractCensus> newSet = new TreeSet<>(new CompareByComments());
        newSet.addAll(set);
        set = newSet;
    }

    @Override
    public void setCensuses(AbstractCensus[] censuses) {
        set = new TreeSet<>(new CompareByYear());
        set.addAll(Arrays.asList(censuses));
    }

    @Override
    public AbstractCensus[] getCensuses() {
        return set.toArray(new AbstractCensus[0]);
    }

    public static void main(String[] args) {
        new CountryWithSet().createCountry().testCountry();
    }
}

The results of the programs should be identical.

4 Exercises

Implement a static generic function of obtaining the index of the last occurrence of an item with a certain value. Test the function on two arrays of different types.
Create a static generic function to replace the order of items in the opposite. Test function on two arrays of different types.
Implement a static generic function for determining the number of occurrences some item in an array. Test function on two arrays of different types.
Implement a static generic function of a cyclic shift of an array to a given number of items. Test function on two arrays of different types.
Implement a static generic search function for an item index, from which some array is completely included in another. Test function on two arrays of different types.
Read from keyboard integer values and add them to a list. Find the product of the elements.
Initialize a list of floating point values with an array of initial values. Find the sum of positive elements.
Initialize a list of integers with an array of initial values. Find the product of nonzero elements.
Initialize a list of integers with an array of initial values. Create a new list composed of even elements of the original list.
Initialize a list of floating point values with an array of initial values. Create a new list composed of positive elements of the original list.
Initialize a list of strings with an array of initial values. Find and display a list item (string) with the maximum length.
Initialize a list of strings with an array of initial values. Find and display index of string with the smallest length.
Enter the number of elements of the future set of integers and the range of numbers. Fill this set with random values. Output elements in ascending order.
Enter the number of elements of the future set of real numbers and the range of numbers. Fill this set with random values. Output the elements in descending order.
Fill a set of integers with random positive even values (no more than a definite number). Output the result.
Enter the word and output all the different letters of the word in alphabetical order.
Enter a sentence and calculate the number of different letters from which the sentence is composed. Do not include spaces or punctuation marks.
Enter a sentence and calculate the number of different words in the sentence.
Initialize a list of integers with an array of initial values. Find the sum of the maximum and minimum elements. Use features of Collections class.
Initialize a list of strings with an array of initial values. Allocate items in reverse order. Use features of Collections class.

5 Quiz

What are the problems associated with creating generic containers?
In what cases it is necessary to create generic classes?
What is a parameterized type?
How are generics different from C ++ templates?
Why use generic functions?
Is it possible to create objects of generic types?
Is it possible to create arrays of generic types?
Why you cannot store integer and floating point numbers directly in the container class, but only references?
How to restrict the type of generics parameter and what opportunities it provides?
What is the usage of a wildcard in the description of the parameters?
Can I use wildcards when creating local variables?
What is a collection?
What are the basic interfaces declared in the java.util package?
What containers are considered obsolete?
Why integers and real numbers cannot be stored directly in the collection, but only references?
How can you get a list from an array?
How can you store integer and floating point values in Java lists?
What is the advantage of definition of references to interfaces (e.g., List) compared to the definition of references to classes that implement these interfaces (e.g., ArrayList)?
What are advantages of iterators compared to the index of the container item?
When is it better to use LinkedList compared to ArrayList (and vice versa)?
What data structure is used to implement LinkedList?
What are the Queue interface methods used to add items?
Why are the methods for working with the queue implemented in two versions: with exception throwing and without exception throwing?
What is the use of the PriorityQueue class?
Can ArrayDeque implement the queue?
What are the stacks used for?
What are the standard ways to implement the stack?
What algorithms does the Collections class provide?
What is a set different from the list?
Give examples of associative arrays.
What is the difference between Map and SortedMap interfaces?
What is hashing?
How can "baskets" be used to store data in a hash table?
What is a binary tree?
What is a balanced and unbalanced tree?
What is a red-black tree and what are its advantages?
How to create your own container?
How to implement a read-only container?

Previous Next

Object-Oriented Programming (Part 1)

Developed by Leo V. Ivanov

Laboratory Training 2 – Working with Java Generics and Collections