Laboratory Training 4
Working with 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 #2. 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).
When working with set, you should consistently create multiple sets sorted according to different criteria.
Test both implementations. The results should match.
1.2 Enumeration for Representation of Months of the Year
Create enumeration that represents months of the year. It is necessary to define the constructor
and store the number of days (for non-leap year). Add methods of getting previous and next month, and a function
that returns a season for particular month. Create static method that prints all months. Test enumeration
in main() function of some test class.
1.3 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.4 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.5 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.6 Data about Users
Present data about users in an associative array (username / password) with the assumption that all usernames are different. Display user information with a password length of more than 6 characters.
1.7 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.8 Implementation of the Doubly-Linked List (Advanced Task)
Implement a generic class representing a doubly-linked list.
1.9 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.10 Implementation of the Red-Black Tree (Advanced Task, at the Student's Choice)
Independently implement associative array based on a red-black tree.
2 Instructions
2.1 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;
Integer i = (Integer) p.second;// Runtime error
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 no 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 DoubleFuncimplements Function<Double> { @Overridepublic Double func(Double x) {return x * 1.5; } }class IntFuncimplements Function<Integer> { @Overridepublic 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.java.fourth;public class AverageTest {public static <Eextends 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:
package ua.inf.iwanoff.java.fourth;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.java.fourth;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.java.fourth;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; } @Overridepublic String toString() {return Arrays.toString(arr); } }
Another class will be created for testing:
package ua.inf.iwanoff.java.fourth;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.1.4 Use of Optional Class
An example of a standard generic type is class Optional.
Optional values are containers for values that can sometimes be empty. Traditionally, for uncertain values,
the value null was used. Using the null constant
can be inconvenient because it can lead to the throwing of the NullPointerException exception,
which complicates debugging and maintenance of the program.
A generic Optional class allows you to save the reference value to some object, and also to
check if the value is set. For example, some method returns a numeric value, but for some arguments the argument
cannot return something definite. This method can return an Optional type object and this value
can then be used in the calling function. Suppose some function calculates and returns the reciprocal value
and returns an "empty" object if the argument is equal to 0. The main() function performs
the calculation for the reciprocal numbers for array items:
ppackage ua.inf.iwanoff.java.fourth;import java.util.Optional;public class OptionalDemo {static Optional<Double> reciprocal(double x) { Optional<Double> result = Optional.empty();if (x != 0) { result = Optional.of(1 / x); }return result; }public static void main(String[] args) {double [] arr = { -2, 0, 10 }; Optional<Double> y;for (double x : arr) { System.out.printf("x = %6.3f ", x); y = reciprocal(x);if (y.isPresent()) { System.out.printf("y = %6.3f%n", y.get()); }else { System.out.printf("The value cannot be calculated%n"); } } } }
If you do not check for the presence of a value (isPresent()), a java.util.NoSuchElementException
will
be thrown when you try to call the get() function for the "empty" value. It can be
caught instead of calling the isPresent() function.
In some cases, the null value should not be considered as possible. In this
case, use ofNullable() to store the value. For example:
Integer k =null ; Optional<Integer> opt = Optional.ofNullable(k); System.out.println(opt.isPresent());// false
Assume that if the reciprocal() function described before does not return a value in the case
of division by zero, the y variable should be assigned to 0. Traditionally, in this case, the
if ... else statement
or conditional operation is used:
y = reciprocal(x);double z = y.isPresent() ? y.get() : 0;
The orElse() method allows you to make the code more compact:
double z = reciprocal(x).orElse(0.0);
In addition to the generic Optional class, you can also use classes optimized for primitive
types: OptionalInt, OptionalLong, OptionalBoolean, etc. The previous
example (calculation of the reciprocal value) could be realized in this way (using OptionalDouble):
package ua.inf.iwanoff.java.fourth;import java.util.OptionalDouble;public class OptionalDoubleDemo {static OptionalDouble reciprocal(double x) { OptionalDouble result = OptionalDouble.empty();if (x != 0) { result = OptionalDouble.of(1 / x); }return result; }public static void main(String[] args) {double [] arr = {-2, 0, 10}; OptionalDouble y;for (double x : arr) { System.out.printf("x = %6.3f ", x); y = reciprocal(x);if (y.isPresent()) { System.out.printf("y = %6.3f%n", y.getAsDouble()); }else { System.out.printf("The value cannot be calculated%n"); } } } }
As can be seen from the example, the result can be obtained using the getAsDouble() method instead
of get().
2.1.5 Generic Functional Interfaces
We have previously discussed the use of functional interfaces to provide callbacks. Some of the standard interfaces
described in the java.util.function package are implemented as generic interfaces:
| Interface | Description |
|---|---|
BiConsumer<T,U> |
Represents an operation that accepts two input arguments and returns no result |
BiFunction<T,U,R> |
Represents a function that accepts two arguments and produces a result |
BinaryOperator<T> |
Represents an operation upon two operands of the same type, producing a result of the same type as the operands |
BiPredicate<T,U> |
Represents a predicate (boolean-valued function) of two arguments |
Consumer<T> |
Represents an operation that accepts a single input argument and returns no result |
DoubleFunction<R> |
Represents a function that accepts a double-valued argument and produces a result |
Function<T,R> |
Represents a function that accepts one argument and produces a result |
IntFunction<R> |
Represents a function that accepts an int-valued argument and produces a result |
LongFunction<R> |
Represents a function that accepts a long-valued argument and produces a result |
ObjDoubleConsumer<T> |
Represents an operation that accepts a T-valued and a double-valued
argument, and returns no result |
ObjIntConsumer<T> |
Represents an operation that accepts a T-valued and a int-valued
argument, and returns no result |
ObjLongConsumer<T> |
Represents an operation that accepts a T-valued and a long-valued
argument, and returns no result |
Predicate<T> |
Represents a predicate (boolean-valued function) of one argument |
Supplier<T> |
Represents a supplier of results |
ToDoubleBiFunction<T,U> |
Represents a function that accepts two arguments and produces a double-valued
result |
ToDoubleFunction<T> |
Represents a function that produces a double-valued result |
ToIntBiFunction<T,U> |
Represents a function that accepts two arguments and produces an int-valued
result |
ToIntFunction<T> |
Represents a function that produces an int-valued
result |
ToLongBiFunction<T,U> |
Represents a function that accepts two arguments and produces a long-valued
result |
ToLongFunction<T> |
Represents a function that produces a long-valued result |
UnaryOperator<T> |
Represents an operation on a single operand that produces a result of the same type as its operand |
For example, you can manually create a functional interface StringFunction and use that interface
to test functions:
interface StringToIntFunction {int apply(String s); }class StringFunctionPrinter {static void printResult(StringToIntFunction function, String s) { System.out.printf("s = %s, f(s) = %s", s, function.apply(s)); }static void test() { printResult(String::length, "Test"); } }
You can use the standard generic interface ToIntFunction<T> without creating a new interface:
class StringFunctionPrinter {static void printResult(ToIntFunction<String> function, String s) { System.out.printf("s = %s, f(s) = %s", s, function.applyAsInt(s)); }static void test() { printResult(String::length, "Test"); } }
The use of other generic functional interfaces is similar.
2.2 Container Classes and Interfaces. Working with Lists
2.2.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
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.2.2 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> list =new ArrayList<String>(); list.add("have"); list.add("good"); list.add("day"); list.add(1, "a");// Inserts a new string before "good"
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> list2 = Arrays.asList(arr);
List<String> list3 = 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(list3);// [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:
for (int i = 0; i < list.size(); i++) { System.out.println(list.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:
list.set(2, "nice"); list.remove(1); System.out.println(list);// [have, nice, day]
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(list.subList(1, 3));// [nice, day]
The removeRange(m, n) method removes all the elements whose index is between
m, inclusive, and n, exclusive. You can also remove all the elements from
the list using the clear() method. The contains() method returns
true if this list contains the specified element. For example:
if (list.contains("day")) { System.out.println(list); }
The toArray() method returns a reference to an array of references to copies of objects
stored in the list:
Object [] a = list.toArray(); System.out.println(a[1]);// nice
In order to get an array of the required type instead of an array of references to Object, you can
specify a parameter
– an arbitrary array of items of the corresponding type, in particular, an empty one. For example:
String [] arr = list.toArray(new String[] { }); arr[0] = "very";// Changing the items of the new array System.out.println(Arrays.toString(arr));// [very, nice, day]
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 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.java.fourth;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.4 Static Methods of the Collections Class. Algorithms
2.4.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.4.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.5 Working with Sets and Maps
2.5.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.java.fourth;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.java.fourth;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.java.fourth;import java.util.*;public class CompTest {public static void main(String args[]) { TreeSet<String> ts =new TreeSet<String>(new Comparator<String>() { @Overridepublic 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.5.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.java.fourth;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.java.fourth;import java.util.*;public class TreeMapKeyimplements Comparable<TreeMapKey> {private String name;public String getName() {return name; }public TreeMapKey(String name) {super ();this .name = name; } @Overridepublic 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.6 Internal Representation of Sets and Associative Containers
2.6.1 Implementation of Sets and Associative Containers using Hashing
To store data in HashSet and HashMap, the hashing is used. 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.6.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.7 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.java.fourth;import java.util.Iterator;import java.util.Scanner;import java.util.StringTokenizer;public class Sentenceimplements Iterable<String> {private String text;public Sentence(String text) {this .text = text; }private class WordsIteratorimplements Iterator<String> { StringTokenizer st =new StringTokenizer(text); @Overridepublic boolean hasNext() {return st.hasMoreTokens(); } @Overridepublic String next() {return st.nextToken(); } @Overridepublic 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 InnerIteratorimplements Iterator<E> {int cursor = -1; @Overridepublic boolean hasNext() {return cursor < arr.length - 1; } @SuppressWarnings("unchecked") @Overridepublic E next() {return arr[++cursor]; } @Overridepublic void remove() {throw new UnsupportedOperationException(); } } @Overridepublic Iterator<E> iterator() {return new InnerIterator(); }//... }
To create a full-fledged custom container, it's the 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.java.fourth;import java.util.AbstractList;public class MyListextends AbstractList<String> { String[] arr = { "one", "two", "three" }; @Overridepublic String get(int index) {return arr[index]; } @Overridepublic 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 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.java.fourth;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.java.fourth;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 Item
The following program finds index of the maximum item 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.java.fourth;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.java.fourth;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.java.fourth;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 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.java.fourth;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; } @Overridepublic 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.7 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.java.fourth;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<>(); @Overridepublic E get(int index) {return (E)arr.get(index - 1); } @Overridepublic int size() {return arr.size(); } @Overridepublic void add(int index, E item) { arr.add(index - 1, item); } @Overridepublic boolean add(E e) {return arr.add(e); } @Overridepublic E set(int index, E item) {return (E)arr.set(index - 1, item); } @Overridepublic E remove(int index) {return (E)arr.remove(index - 1); } @Overridepublic int indexOf(Object o) {return arr.indexOf(o) + 1; } @Overridepublic int lastIndexOf(Object o) {return arr.lastIndexOf(o) + 1; } @Overridepublic 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.8 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. This will allow us to use the most of the previously developed tools. The classes will be added to the previously created project.
The first class
will store the data in the ArrayList container.
The class code will be as follows:
package ua.inf.iwanoff.java.fourth;import ua.inf.iwanoff.java.third.AbstractCountry;import ua.inf.iwanoff.java.third.Census;import java.util.Arrays;import java.util.List;import java.util.ArrayList;/** * Class for presenting the country in which the censuses are carried out. * Census data are represented with ArrayList */ public class CountryWithArrayListextends AbstractCountry {private List<Census> list =new ArrayList<>();/** * Returns reference to the census by index in a sequence * @param i census index * @return reference to the census with given index */ @Overridepublic Census getCensus(int i) {return list.get(i); }/** * Sets a reference to a new census within the sequence * according to the specified index. * @param i census index * @param census a reference to a new census */ @Overridepublic void setCensus(int i, Census census) { list.set(i, census); }/** * Adds a reference to a new census to the end of the sequence * @param census a reference to a new census * @return {@code true} if the reference has been added * {@code false} otherwise */ @Overridepublic boolean addCensus(Census census) {if (list.contains(census)) {return false ; }return list.add(census); }/** * Returns the number of censuses in the sequence * @return count of censuses */ @Overridepublic int censusesCount() {return list.size(); }/** * Removes all the censuses from the sequence */ @Overridepublic void clearCensuses() { list.clear(); }/** * Puts data from an array of censuses into a sequence * @param censuses array of references to censuses */ @Overridepublic void setCensuses(Census[] censuses) { list =new ArrayList<>(Arrays.asList(censuses)); }/** * Returns an array of censuses obtained from the sequence * @return array of references to censuses */ @Overridepublic Census[] getCensuses() {return list.toArray(new Census[0]); }/** * Returns a list of censuses * @return list of references to censuses */ public List<Census> getList() {return list; }/** * Puts a list of censuses into the object * @param list arbitrary list of censuses */ public void setList(List<Census> list) {this .list = list; } }
Now we can create a class that stores data in the set. Since the beginning of the censuses should be arranged in
ascending order of the year. The
CountryWithSet class code will be as follows:
package ua.inf.iwanoff.java.fourth;import ua.inf.iwanoff.java.third.AbstractCountry;import ua.inf.iwanoff.java.third.Census;import java.util.Arrays;import java.util.Comparator;import java.util.SortedSet;import java.util.TreeSet;/** * Class for presenting the country in which the censuses are carried out. * Census data are represented with a set */ public class CountryWithSetextends AbstractCountry {private SortedSet<Census> set =new TreeSet<>(Comparator.comparing(Census::getYear));/** * Returns reference to the census by index in a sequence * @param i census index * @return reference to the census with given index */ @Overridepublic Census getCensus(int i) {return set.toArray(new Census[0])[i]; }/** * Sets a reference to a new census within the sequence * according to the specified index. * @param i census index * @param census a reference to a new census */ @Overridepublic void setCensus(int i, Census census) { Census oldCensus = getCensus(i); set.remove(oldCensus); set.add(census); }/** * Adds a reference to a new census to the end of the sequence * @param census a reference to a new census * @return {@code true} if the reference has been added * {@code false} otherwise */ @Overridepublic boolean addCensus(Census census) {return set.add(census); }/** * Returns the number of censuses in the sequence * @return count of censuses */ @Overridepublic int censusesCount() {return set.size(); }/** * Removes all the censuses from the sequence */ @Overridepublic void clearCensuses() { set.clear(); }/** * Puts data from an array of censuses into a sequence * @param censuses array of references to censuses */ @Overridepublic void setCensuses(Census[] censuses) { set =new TreeSet<>(Comparator.comparing(Census::getYear)); set.addAll(Arrays.asList(censuses)); }/** * Returns an array of censuses obtained from the sequence * @return array of references to censuses */ @Overridepublic Census[] getCensuses() {return set.toArray(new Census[0]); }/** * Returns a set of censuses * @return set of references to censuses */ public SortedSet<Census> getSet() {return set; }/** * Puts a set of censuses into the object * @param set arbitrary set of censuses */ public void setSet(SortedSet<Census> set) {this .set = set; } }
Since the set is ordered by a certain attribute, and it is not possible to sort it, to obtain sorted sequences, we can create different variants of data sets. We create a class that provides functions for sorting the sequence defined by the set:
package ua.inf.iwanoff.java.fourth;import ua.inf.iwanoff.java.third.Census;import java.util.Comparator;import java.util.SortedSet;import java.util.TreeSet;/** * Provides static methods for sorting sequential censuses, * represented by the set */ public class SetSorting {/** * Sorts the sequence of censuses by population * * @param country reference to a country */ public static void sortByPopulation(CountryWithSet country) { SortedSet<Census> newSet =new TreeSet<>(); newSet.addAll(country.getSet()); country.setSet(newSet); }/** * Sorts the sequence of censuses in the alphabetic order of comments * * @param country reference to a country */ public static void sortByComments(CountryWithSet country) { SortedSet<Census> newSet =new TreeSet<>(Comparator.comparing(Census::getComments)); newSet.addAll(country.getSet()); country.setSet(newSet); } }
Other static methods can be used directly from the example given in the example of the previous training.
We create a class that represents a console application:
package ua.inf.iwanoff.java.fourth;import ua.inf.iwanoff.java.third.AbstractCountry;import ua.inf.iwanoff.java.third.StringRepresentations;import static ua.inf.iwanoff.java.fourth.SetSorting.sortByComments;import static ua.inf.iwanoff.java.fourth.SetSorting.sortByPopulation;import static ua.inf.iwanoff.java.third.CountryDemo.*;/** * Country testing program */ public class ArrayListSetDemo {/** * Tests sorting methods * for a sequence represented by a set * * @param country reference to a country */ public static void testSetSorting(CountryWithSet country) { sortByPopulation(country); System.out.println("\nSorting by population:"); System.out.println(StringRepresentations.toString(country)); sortByComments(country); System.out.println("\nSorting comments alphabetically:"); System.out.println(StringRepresentations.toString(country)); }/** * Demonstration of work with a country * @param args command line arguments (not used) */ public static void main(String[] args) { AbstractCountry country = setCountryData(new CountryWithArrayList()); testSearch(country); testSorting(country); System.out.println("----------------------------------------"); country = setCountryData(new CountryWithSet()); testSearch(country); testSetSorting((CountryWithSet) country); } }
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.
- 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.
- 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 items
- Initialize a list of integers with an array of initial values. Find the product of nonzero items.
- 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.
- 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 words in the sentence.
- Create a function that calculates the square root, if possible, and returns an
OptionalDoubleobject.
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?
- What is the usage of
Optionalclass? - Is it possible to use the
Optionalclass with primitive types? - What is a collection?
- 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
LinkedListcompared toArrayList(and vice versa)? - What data structure is used to implement
LinkedList? - What algorithms does the
Collectionsclass provide? - What is a set different from the list?
- Give examples of associative arrays.
- What is the difference between
MapandSortedMapinterfaces? - 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?