Laboratory Training 2

Working with Java Collections

1 Training Assignment

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 of the course "Object-oriented programming (first part)". 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 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.3 Arithmetic Mean

Implement a program in which real numbers are entered, then displayed in ascending order of absolute values, and their arithmetic mean is calculated. Use PriorityQueue.

1.4 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.5 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.6 Implementation of an Array of Points through a List of Real Numbers (Advanced Task)

Implement the functionality of the abstract class AbstractArrayOfPoints, given in the example of the Laboratory Training # 1 of the course "Object-oriented programming" (first part), through the use of the list of real numbers. Each pair of numbers in the list should correspond to the point.

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 Overview of Container Classes and Interfaces

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. This is Vector, Enumeration, Stack, BitSet and some others. For example, the Vector class provides a function similar to ArrayList. These containers do not provide a standardized interface, they do not allow the user to abandon 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 generalized 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 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.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 elements in this collection
`boolean isEmpty()`	Returns `true` if this collection contains no elements
`boolean contains(Object o)`	Returns `true` if this collection contains the specified element
`Iterator<E> iterator`	Returns an iterator (an object that consistently points to the elements)
`Object[] toArray()`	Returns an array of `Object` containing all of the elements in this collection
`<T> T[] toArray(T[] a)`	Returns an array of `T` containing all of the elements 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 element from this collection, if it is present
`boolean containsAll(Collection<?> c)`	Returns `true` if this collection contains all of the elements in 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 elements 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.in.iwanoff.java.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 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.

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> a1 = 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 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 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.

2.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 + " ");
}

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.in.iwanoff.java.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.5 Working with 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.in.iwanoff.java.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.in.iwanoff.java.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.in.iwanoff.java.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 + " ");
        }
    }
}

Note. In the example above, an anonymous class is used to determine the order of the elements. The use of anonymous classes, lambda-expressions and references to methods is described in the guidelines for Laboratory training # 3 of the course "Object-Oriented Programming".

2.6 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.in.iwanoff.java.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.in.iwanoff.java.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.in.iwanoff.java.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.in.iwanoff.java.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.7 Static Methods of the Collections Class. Algorithms

2.7.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.7.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). 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.8 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 TreeMap class guarantees alphabetic order of words (keys).

package ua.in.iwanoff.java.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.in.iwanoff.java.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).

2.9 Internal Representation of Sets and Associative Containers

2.9.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.9.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.10 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.in.iwanoff.java.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 RuntimeException("Not implemented!");     
        }

    }

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

    @SuppressWarnings("resource")
    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 RuntimeException("Not implemented");   
        }
    }

    @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.in.iwanoff.java.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.

3 Sample Programs

3.1 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.in.iwanoff.java.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.2 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.in.iwanoff.java.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.3 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.in.iwanoff.java.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.4 Implementation of the Class that Represents an Array of Points with the Help of the List

Another possible implementation of the representation of the array of points defined in the example to the laboratory training # 1 from the course "Object-Oriented Programming", is based on the use of the list of points. We create a new package to the project that contains the AbstractArrayOfPoints class. Then we add ListOfPointObjects class. In order to enable usage of AbstractArrayOfPoints and Point classes, we add appropriate import statements.

The source code of the class will be the following:

package ua.in.iwanoff.java.second;

import java.util.ArrayList;
import ua.in.iwanoff.oop.first.AbstractArrayOfPoints;
import ua.in.iwanoff.oop.first.Point;

public class ListOfPointObjects extends AbstractArrayOfPoints {
    ArrayList<Point> p = new ArrayList<>();

    @Override
    public void setPoint(int i, double x, double y) {
        p.get(i).setPoint(x, y);
    }

    @Override
    public double getX(int i) {
        return p.get(i).getX();
    }

    @Override
    public double getY(int i) {
        return p.get(i).getY();
    }

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

    @Override
    public void addPoint(double x, double y) {
        p.add(new Point(x, y));
    }

    @Override
    public void removeLast() {
        p.remove(count() - 1);
    }

    public static void main(String[] args) {
        new ListOfPointObjects().test();
    }
}

The results should be identical to those obtained before.

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.in.iwanoff.java.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.in.iwanoff.java.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.in.iwanoff.java.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.in.iwanoff.java.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.in.iwanoff.java.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.in.iwanoff.java.second;

import ua.in.iwanoff.oop.first.AbstractCensus;
import ua.in.iwanoff.oop.first.AbstractCountry;
import ua.in.iwanoff.oop.first.CensusWithData;
import ua.in.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.in.iwanoff.java.second;

import ua.in.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.in.iwanoff.java.second;

import ua.in.iwanoff.oop.first.AbstractCensus;
import ua.in.iwanoff.oop.first.AbstractCountry;
import ua.in.iwanoff.oop.first.CensusWithData;
import ua.in.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

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 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 (eg., List) compared to the definition of references to classes that implement these interfaces (eg., ArrayList)?
What are advantages of iterators compared to the index of the container item?
When is it better to use ArrayList compared to LinkedList?
When is it better to use LinkedList compared to ArrayList?
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?

Bases of Java

Developed by Leo V. Ivanov

Laboratory Assignments: