Practice 09
The material for the practical course¶
Collections¶
Simple arrays can have shortcomings in the ways we have seen before. So called collections are, in part, used to overcome these shortvomings. Collections, like arrays, are used to store a particular type, but also have additional functionality. Their use is convenient and can greatly simplify our work. Two of them will be discussed below, the list and the set, and we will also come across the concept of associative array (mapping, dictionary, map). More about collections
Lists¶
For arrays, for example, it can still be a big problem that we must specify a maximum size for them before uploading. This also means that, as a precaution, we can sometimes store unnecessarily large arrays, most of which will remain unfilled. This information is often only revealed at runtime and not when the program is written (e.g. an arbitrary number of elements is received in command line parameter), or, even more problematic, we may not know how many elements we want to store in the array when it is created at runtime (e.g. the user specifies an arbitrary number of elements in the console, which must be stored). Therefore, using a simple array can cause serious difficulties.
A further problem is that the length property of arrays, which we have seen before, stores the maximum number of items, so if you carelessly repeat a loop, for example, that many times, you can easily refer to an item that does not exist, and you may even get a NullPointerException type exception. So, we have to store in a variable how many elements are actually in the array and keep track of that, but this can also be a potential source of errors.
This problem is illustrated by the following example, which reads in an arbitrary number of floating point numbers and prints their multiplication (incorrectly in most cases):
import java.util.Scanner;
public class IncorrectAdditionFromConsole {
public static void main(String[] args) {
double[] numbers = new double[100];
Scanner sc = new Scanner(System.in);
//read a number until we get 1
int i=-1;
do {
i++;
numbers[i]=sc.nextDouble(); //fails if user wants more than 100 numbers (runs out)
} while(numbers[i]!=1);
//calculate the product of the numbers obtained
int product=0;
for(i=0;i<numbers.length;i++) {
product*=numbers[i]; //fails if user has not given exactly 100 numbers (nulls)
}
System.out.println(product);
}
}
In other cases, handling arrays can also be complicated, even if you handle them well. This can be seen, for example, in a simplified solution to the acceptIntoHerd method of the Herd class of the animal example:
private int maximum = 100;
private Animal[] tags = new Animal[maximum];
private int current=0;
public void acceptIntoHerd(Animal what) {
if (current < maximum) {
tags[current]=what;
current++;
}
}
This code works correctly, but it is very complicated and cannot handle a herd that exceeds the maximum.
These problems can be solved with lists (List), which work very similarly to an array, but are much more flexible. Like an array, it can still store items of one type, but it can be of any size, small for a small amount of data and large for a large amount of data. This is not only important for memory saving, as there will be exactly as many elements as we add. It's basically the same as the dynamic array we've already seen in Basics of Programming, but there's no need to use pointers to allocate and deallocate, it's very simple to use. Its declaration can look like this:
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Lists {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>(); //array implementation
List<Integer> list2 = new LinkedList<>(); //linked list implementation
}
}
The List class of the java.util package is an interface, which, from what we already know, means that it does not perform its operations by itself, that is the job of the classes implementing it. However, its implementations are usable, and we can choose from them. These can be, for example, ArrayList and LinkedList, but there are other implementations available, more about them here.
The two classes perform exactly the same tasks, they differ only in their underlying functionality, but all their operations and their correctness are the same. The ArrayList is based on an array implementation, and the LinkedList is based on linked lists. The two list types are therefore completely identical in use, because they both implement the same interface.
Generic type assignment¶
The declaration may seem a bit strange at first. Here, the type of the stored data is specified between <> (duckbills). So a List<Double> type is a list that stores floating point items. As you can see, it is not the simple primitive types that are specified here, but their wrapper classes. After the equals sign we have to instantiate with the constructor of a concrete implementation, in Java 7.0 and above it is not important to specify the type again, it is enough to type the empty duckbill (diamond operator), making things easier. There is no need to specify a maximum size, the newly created list is always empty and has 0 elements.
The syntax you have just seen indicates generic type assignment. You can learn more about this in the lecture. In practice, it is a static polymorphism, a type parameter is given, because the class itself is written to be as general as possible, and we don't need to write separate classes IntegerList, StringList, AnimalList, etc., but we use a generic class as a template, and the actual type is defined between the duckbills.
Generic classes¶
Of course, this is not only for lists and maps, we can also create such classes without any further ado. In the following section, we present a very simple class:
public class HiddenValue<GenericType> {
private GenericType value;
public HiddenValue(GenericType value) {
this.value = value;
}
public GenericType getValue() {
return value;
}
public void setValue(GenericType value) {
this.value = value;
}
@Override
public String toString() {
return "HiddenValue [value=" + value + "]";
}
}
This is a class that can store a value of some type, for which there is a getter and a setter function, and a toString method. So, if I say when instantiating HiddenValue<String> value = new HiddenValue<>("I like apples!");, then I can store a text in the resulting object, and so on.
public static void main(String[] args) {
HiddenValue<String> value = new HiddenValue<>("I like apples!"); // I can store a text this way
value.setValue("Will it work?"); // Yes
//value.setValue(103); //It won't work
HiddenValue<Integer> integerValue = new HiddenValue<>(120); // I can store an integer this way
HiddenValue<Animal> animalValue = new HiddenValue<>(new Bear("Jason")); // I can store an animal this way
}
Back to lists¶
They are quite simple to use, adding a new element is done with the add method, which expects an element like the list itself. In this case the list is dynamically expanded, so if the statement is issued in its default state, the element at index 0 is created, or for existing elements, the new element is available at the next free index. A new element can also be inserted at any index, in which case the element at that index and all elements with a higher index than it move up one index. This can be done with the add(index, element); method, similar to the add method, but the desired index must be specified before the element. The list has a size (beware, this is not length! and not a property!) method which stores the number of elements in the list, which changes automatically as the list grows/shrinks.
A particular element is not referred to here by [], but by calling the get behaviour, for example list.get(0) to get the element with index 0. Apart from the exterior, this is indexable in the same way as the array.
Deleting elements is also quite intuitive. This can be called with the remove method. There are two types of this. You can either specify the index, or you can specify a specific element whose first instance is deleted.
If we have a list of
Integerelements, we have to be careful, because if we want to delete by element instead of index, it will not work by default, since the int and wrapper types can be mixed up very easily. In such a case, if you want to remove an element with a given value, you must always cast, for example, instead oflist.remove(3), you should writelist.remove((Integer)3), orlist.remove(Integer.valueOf(3)), or evenlist.remove(new Integer(3)).
These commands are illustrated in the following example code:
List<Double> list = new ArrayList<>(); //Can be treated as a List due to polymorphism.
//insert at the end of the list
list.add(1.2);
list.add(2.1);
list.add(3.10);
list.add(2.1);
list.add(3.05);
//insert to the first place -> 3.55, 1.2, 2.1, 3.1, 2.1, 3.05
list.add(0, 3.55);
//delete the first item -> 1.2, 2.1, 3.1, 2.1, 3.05
list.remove(0);
//delete the first 2.1 value -> 1.2, 3.1, 2.1, 3.05
list.remove(2.1);
You can add another list to a list using the lists addAll method, which takes the other collection as a parameter.
Traversal¶
There are several methods for traversing lists.
A familiar method is to traverse by index, as is done for arrays:
Another option is to use iterator. An iterator is an object (which implements the Iterator design pattern, which will be discussed in more detail in the lecture) that can traverse all the elements of a collection one by one. When declaring it, you can also specify the type with <>, and then call the iterator() method of the list instead of the new keyword, which will construct the corresponding iterator. The iterator must be stepped through as it is being used until the last element is reached. This is usually best done with a loop (usually a while loop). To query whether you are at the last element, use the hasNext() method of the iterator, which returns boolean. This does not automatically set the iterator to the next element, that is done by the next() method, which returns the next element after the step. When calling this, care must be taken that it steps the iterator every call regardless of the loop, so if the value is not stored in a temporary variable (e.g. double temp = it.next();), you can fall into the trap of stepping twice between two checks, retrieving the next next one, which is no longer guaranteed to exist, and is guaranteed to fail after the last element is stepped through.
Iterator<Double> it = list.iterator();
while(it.hasNext()) {
Double element = it.next();
System.out.print(element + " ");
}
A third option is to traverse the for loop element-by-element. This makes it very easy and intuitive to use. Instead of the usual for structure, there are no semicolons or stop conditions. An element is declared with the type of the elements in the list, followed by the name of the list separated by a colon. Each time the loop runs, the next element will be placed in the declared element. This for loop also works with an iterator in the background, the difference from the previous solution is that in this case we don't know about it. :)
The acceptIntoHerd method of the above example can be simplified with lists to the following:
private List<Animal> members = new ArrayList<>();
public void acceptIntoHerd(Animal what) {
members.add(what);
}
Removal¶
As mentioned earlier, you can delete an item from the list using the remove method. This sounds simple, but it won't work in one case: if you want to delete from the list, say, while it is being traversed. Feel free to try to delete all items that are, say, less than 1.5:
List<Double> list = new ArrayList<>();
list.add(1.2);
list.add(2.1);
list.add(3.10);
list.add(2.1);
list.add(3.05);
for(double element : list) {
if(element < 1.5){
list.remove(element);
}
}
For such cases, the iterator already described comes in handy. When invoking the iterator, you can simply delete any element you don't like, using the remove method of the iterator.
Iterator<Double> it = list.iterator();
while(it.hasNext()) {
double element = it.next();
if(element < 1.5){
it.remove();
}
}
If you want to delete all the elements in the list, you can use the clear() method of lists.
Sets¶
The so-called set (Set) is very similar to a list, both in function and in operation. It is also an interface, and there are two types of it, HashSet, which indicates a [hash_table][hash_table] implementation, and TreeSet, which indicates a [red_black tree][red_black] implementation. The use of these implementations is also identical.
As with lists, they can store an arbitrary number of elements of a type, and are dynamically expanded in the same way. The add and remove methods can be used in the same way. There are two fundamental differences from lists:
-
Sets may contain each element only once. So, as when we talk about mathematical sets, we do not keep track of how many pieces of an element are in it, only whether it contains a certain element (e.g. a number) or not. However, this may raise the question of what happens if we add an element 2 to a set of numbers, then an element 3, then a new element 2. In this case it is understandable that the 2 will only be included once, but what happens to the indices? The answer is given in the next section:
-
The elements of a set are not ordered by index. So you cannot query them by index, so it is not stored in which order the elements are placed, only whether they are included.
Their declaration is very similar to that of lists:
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;
public class Sets {
public static void main(String[] args) {
Set<Integer> set = new HashSet<>(); // hash table implementation
Set<Integer> set2 = new TreeSet<>(); //red-black tree implementation
}
}
Contains¶
One of the most important properties of a set may be whether it contains a particular element. This can be easily queried by calling the contains method. It is very simple to use:
if(set.contains(2)) System.out.println("The set contains 2");
else System.out.println("The set does not contain 2");
Of course, this can work not only with numbers, if you put instances of the Animal class in the set, for example, you can use it there as well.
Traversal¶
You have pretty much the same options for traversing elements as you do for lists. Of course, since here the index is not interpreted on the set, index-based traversal is not possible. However, iterator-based or element-by-element traversal can be achieved without major changes:
//traversal - with iterator
Iterator<Integer> it = set.iterator();
while(it.hasNext()) {
System.out.print(it.next() + " ");
}
System.out.println();
//traversal - element by element
for(int number : set) {
System.out.print(number + " ");
}
System.out.println();
The question may then arise as to the order in which we will get back the elements we have entered. This is not important for many problems that perform an action completely independent of the order. HashSet does not guarantee any ordering, but TreeSet does, so its elements must implement some ordering (the wrapper classes of primitive types and String do this). If you store your own objects, you will need to define less-greater-equal operations by implementing the Comparable interface, or if you don't have the ability to modify the class or just want to implement occasional ordering, you can use the Comparator interface, which can be used for all cases of containers that require custom ordering.
Using sets is therefore straightforward, and there are many cases where it is easier to use than lists. For example, the herd we saw earlier can be implemented with sets without any problem, since each animal can only be once in a herd at most. The code for doing this is no more complicated than doing it with lists:
private Set<Animal> members = new HashSet<>();
public void acceptIntoHerd(Animal what) {
tags.add(what);
}
Mappings (Map)¶
The elements of the arrays and lists we've seen so far could all be referenced with ascending indexes starting from 0. However, in many cases it would be useful to be able to assign elements not only to integers, but also to other things, such as words or objects. Mappings, or Map, can be used for this purpose. There are also two implementations of this, the Hash Map, which is based on [hash_table][hash_table] and the Tree Map, which is based on [red_black tree][red_black].
Each map consists of key-value pairs. Both of these can be of any arbitrary reference type. The keys are assigned values, which means that there is always a value associated with a particular key. However, a value can occur for more than one key. Therefore, a key uniquely identifies a pair, while a value does not. This can also be understood in such a way that any type of element can be specified as an index instead of a number.
Their declaration may look like this:
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
public class Maps {
public static void main(String[] args) {
Map<Integer,String> map1 = new HashMap<>();
Map<Integer,String> map2 = new TreeMap<>();
}
}
You will notice that here we have to specify two types separated by commas between the <> signs, rather than just one. The first is the key and the second is the type of the value assigned to it. In the example above, the key is an integer and its value is a text.
Adding a new element pair is done here with the 'put' method.
The code in the example inserts two key-value pairs into the map1 map, assigning the word "Blue" to the number 320 and the word "Green" to 200. The element corresponding to the key can then be queried using the get method, as for lists and sets:
In this case, the text "Blue" is returned. It is important that this is not reversible, you could not say map1.get("Blue"). This is because we could have assigned "Blue" to 200 in the same way. If we tried to put another 320 key element in the map, however, we would overwrite the previous one, so it is always clear.
Deleting elements can be done with the remove method already seen for lists, in the same way as seen, but here again only a key can be specified, the value does not properly identify here either. On deletion, of course, both the key and the value are deleted. However, it is also possible to specify a key-value pair, if you want to delete the pair only for a certain value.
You can observe that the above operation is similar to an indexing operation. It differs in that it does not necessarily start from 0, nor does it only contain indexes in a sequence. However, maps can do much more than this.
Below is an example that counts the words received in the console, how many of each word were received, and stores them in a map.
//counting words received from a console with a map
Map<String, Integer> map1 = new HashMap<>();
for(int i=0; i<args.length; i++) {
if(map1.containsKey(args[i])) { //if we have already seen the word
int units = map1.get(args[i]);
units++;
map1.put(args[i], units); //overwrite the units (number of pieces) so far
}
else { //if we haven't seen the word yet
map1.put(args[i], 1);
}
}
Such maps can be used in practice, for example, in text processing, where we can infer the number of occurrences of words, the basis of many algorithms.
Traversal¶
With maps, as with sets, there is no clear system for the order in which they are written. There is also no way of traversing them index by index (perhaps by creating a map similar to a list, or by maintaining an index heap and traversing it to get the keys in order). Here, too, an iterator can be used for traversal and element-by-element traversal works (in slightly more complex forms):
//map traversal - with iterator
Iterator elements = map1.entrySet().iterator();
while (elements.hasNext()) {
Entry<String, Integer> element = (Entry<String, Integer>) elements.next();
System.out.println(element.getKey() + "\t" + element.getValue());
}
//map traversal - element by element
for(Entry<String, Integer> element : map1.entrySet()) {
System.out.println(element.getKey() + "\t" + element.getValue());
}
In this case, we can traverse the map not by keys or elements, but by specific pairs. Such a pair is called Entry. This must also be given two types, it represents exactly one key-value pair in the map. The map can thus be understood as a set of such entries. Into this we can place the entries of the map by simply treating it as a set of entries with the entrySet method, which returns a set with the contents of the map.
An entry is thus a key-value pair, whose key is obtained by the getKey() method and whose value is obtained by the getValue() method.
For maps, there is also the contains method as seen for sets, but here there are two of them, containsKey and containsValue, which can be used to check the keys and values. They take the corresponding type as a parameter, as appropriate.
So maps also provide simple operation and also support dynamic size. They can be used, for example, for counting objects, mapping two objects to each other, or even storing any value temporarily per object.
Returning to the animal example we have already seen, if there is a herd stored in a set in the form we have seen, then a map can be specified for it, which, for example, keeps count of how many of each species it contains. A method to return this:
public Map<String, Integer> countsSpecies() {
Map<String,Integer> speciesCount = new HashMap<>();
for(Animal animal : members) { //traverse the herd
if(!speciesCount.containsKey(animal.getClass().getName()) { //if no such species is in the map yet
speciesCount.put(animal.getClass().getName(), 1); //insert one
}
else { //if we have already seen such a species
int previousCount = speciesCount.get(animal.getClass().getName()); //get the number assigned so far
previousCount++; //increment by 1
speciesCount.put(animal.getClass().getName(), previousCount); //insert again with the new number, overwriting the old one
}
}
return speciesCount;
}
Comparable and Comparator interfaces¶
As we have seen earlier with arrays, it is possible to specify ordering relations between elements of a type. We can also use the specified ordering relations for sets, possibly the key sets of maps, that do not "order" their elements using hash functions. Examples are TreeSet and TreeMap, but also any collection or mapping that implements the SortedSet and SortedMap interfaces. Very importantly, these sets must never contain the null value.
The use of the Comparable interface may be advisable when one wishes to implement a sorting between objects of a class in general. The wrapper classes of primitive types, or the String class, implement this interface, so if you expect a general ordering for these types (e.g., sort ascending for Integer, alphabetical for String), then this is a given. If we want to achieve this between objects of our own class, we must also implement the Comparable interface.
For example, we sort the objects of the class Animal by their names:
public class Animal implements Comparable<Animal>{
private String name;
public Animal(String name) {
if (name != null)
this.name = name;
else
this.name="";
}
public String getName() {
return name;
}
@Override
public int compareTo(Animal o) {
return this.name.compareTo(o.name);
}
}
Then, if we create a TreeSet where we do not specify which Comparator we want to use to traverse it, the traversal we just defined will be applied. IMPORTANT! The compareTo method must be implemented in such a way that it is interchangeable in terms of the two objects it uses. It must also have a transitive property. The return value of compareTo is 0 if the two objects are considered equal, less than 0 if the this object is considered less than this, greater than 0 if the this object is considered greater than this.
Example usage:
public static void main(String args[]) {
Set<Animal> animals = new TreeSet<>(){{add(new Animal("Leo")); add(new Animal("Chippy")); add(new Animal("Vili"));}};
for(Animal a: animals) {
System.out.println(a.getName());
}
}
The animals are then traversed in the order of their names.
If it is not possible to implement the Comparable interface, or if you just want to implement an ordering that you don't want to implement too many instances of, you can initialize TreeSet (it works similarly to Map) by giving it a Comparator type object in its constructor. For this, the compare method must be implemented, for which the same is true as for compareTo: it must implement an ordering that implements a complete ordering for the given objects and the ordering defined for the elements is interchangeable, transitive.
For example, for the class Animal, you could specify a Comparator that now orders the animals by the length of their names.
class AnimalComparator implements Comparator<Animal>{
@Override
public int compare(Animal o1, Animal o2) {
return o1.getNev().length()-o2.getNev().length();
}
}
We can create our set with such a comparator object by calling the appropriate constructor when creating it:
public static void main(String args[]) {
Set<Animal> animals = new TreeSet<>(new AnimalComparator()){
{
add(new Animal("Leo"));
add(new Animal("Csipi"));
add(new Animal("Calvin"));
add(new Animal("Vili"));}
};
for(substring a: substrings) {
System.out.println(a.getName());
}
}
If you are only going to call one comparator object with this ordering, you can also choose not to create a separate Comparator, but define it as an Anonymous class, but the details of that will be the subject of the next practice:
public static void main(String args[]) {
Set<Animal> animals = new TreeSet<>(
new Comparator<Animal>() {
@Override
public int compare(Animal o1, Animal o2) {
return o1.getName().length()-o2.getName().length();
}
}
){{add(new Animal("Leo")); add(new Animal("Chippy")); add(new Animal("Calvin"));add(new Animal("Vili"));}};
for(Animal a: animals) {
System.out.println(a.getName());
}
}
Tasks¶
- Create a fixed-size stack to store integers (using array) and implement push/pop operations.
- Modify the previous custom linked list implementation so that it can store any type of element, not just
Animal. - Write an executable class that expects "push" or "pop" commands from the console in the Main method. When it receives a pop command, execute it and write the extracted item to the console. For a push statement, an integer must follow, put it in the stack.
- Implement the previous stack task so that it can store any type of element, which should be given to it as a generic type parameter.
- Rewrite the fixed size stack to your own linked list
- Replace your own list implementation with one of the collections.
- Create a map where the keys are strings! In your implementation, make sure that the map is traversed in descending order of key length!