Lecture
In Listing 5.2, we parsed the line into words. How to save them for further processing?
So far, we have used arrays. They are convenient if you need to quickly process the same type of elements, for example, sum up numbers, find the largest and smallest value, sort the elements. But to find the necessary information in a large amount of information, arrays are inconvenient. For this it is better to use binary search trees.
In addition, arrays always have a constant, predetermined length, it is inconvenient to add elements to arrays. When removing an element from an array, the remaining elements should be renumbered.
When solving problems in which the number of elements is not known in advance, elements should be frequently removed and added, other storage methods should be sought.
In the Java language, from the very first versions there is a class vector , designed to store a variable number of elements of the most general type object .
Vector class
The vector class from the java.uti i package stores elements of type object , which means of any type. The number of elements can be any and not determined in advance. Elements get indices O, 1, 2, .... Each element of the vector can be accessed by index, as well as an element of the array.
In addition to the number of elements, called the size (size) of the vector, there is also a buffer size - the capacity (capacity) of the vector. Usually, the capacitance coincides with the size of the vector, but you can increase it by the method of e nsureCapacity (int minCapacity) or compare it with the size of the vector using the trimToSize () method .
In Java 2, the vector class has been redesigned to include it in the hierarchy of collection classes. Therefore, many actions can be performed by old and new methods. It is recommended to use new methods, since the old ones can be excluded from the following versions of Java.
How to create a vector
There are four constructors in the class:
vector () - creates an empty object of zero length;
Vector (int capacity) - creates an empty object of specified capacity ;
vector (int capacity, int increment) - creates an empty object of the specified capacity and sets the number of increment by which the capacity increases, if necessary;
vector (Collection c) - the vector is created for the specified collection. If capacity is negative, an exception is thrown. After creating the vector, it can be filled with elements.
How to add an element to the vector
The add (Object element) method allows you to add an element to the end of a vector
( the old method does the same addElement (Object element) .
Using the add (int index, Object element) method or the old insertElementAt (Object element, int index) method , you can insert an element at the specified index . The element located on this place and all subsequent elements are shifted, their indices increase by one.
The addAil (Collection coll) method allows you to add all elements of the coll collection to the end of the vector.
Using the addAii (int index, Collection coll) method , it is possible to insert into the index position all elements of the coll collection.
How to replace an item
The set (int index, object element) method replaces the element that was in the vector at the index position with the element element (the same allows the old
method setElementAt (Object element, int index))
How to find out the size of the vector
The number of elements in a vector can always be found out using the size () method. The capacity about method returns the capacity of a vector.
The isEmpty () logical method returns true if there is no element in the vector.
How to access a vector element
You can access the first element of the vector using the firstEiement () method, the last using the lastEiement () method, any element using the get (int index) method or the old elementAt (int index) method .
These methods return an object of class object . Before use it should be brought to the desired type.
You can get all the elements of the vector as an array of object [] type using the toArray ( ) and toAr ray (Object [] a) methods. The second method puts all the elements of the vector in the array a, if there is enough space.
How to find out if there is an element in the vector
The logical method contains (object element) returns true if the element element is in the vector.
The logical method containsAii (Collection с) returns true if the vector contains all the elements of the specified collection.
How to find the item index
Four methods allow finding the position of the specified element:
indexof (Object element) - returns the index of the first occurrence of an element in the vector;
indexOf (Object element, int begin) - searches, starting with the begin index, inclusive;
lastindexOf (object element) - returns the index of the last occurrence of an element in the vector;
lastindexOf (Object element, int start) - conducts a search from the start index inclusive to the beginning of the vector.
If the item is not found, it returns -1.
How to remove items
The remove (Object element) logical method removes the first occurrence of the specified element from the vector. The method returns true if the item is found and deleted.
The remove (int index) method removes an element from the index position and returns it as its result of type object .
Similar actions allow you to perform the old methods of type void :
removeElement (Object element) And removeElementAt (int index) that returns no result.
You can remove a range of elements using the removeRange (int begin, int end) method that does not return a result. Elements are removed from the begin position inclusively to the end position exclusively.
All elements of the coil collection can be removed from this vector by the logical method RemoveAll (Collection coll).
You can delete the last elements simply by cutting the vector with
setSizefint newSize).
Removing all elements except those in the specified coil collection allows the logical method retainAll (Collection coll).
You can delete all elements of the vector using the clear () method or the old method.
removeAHElements () or zero size of vector by method setSize (O).
Listing 6.1 expands Listing 5.2 by processing words extracted from a string using a vector.
Listing 6.1. Work with vector
Vector v = new Vector ();
String s = "The string we want to break into words.";
StringTokenizer st = new StringTokenizer (s, "\ t \ n \ r ,.");
while (st.hasMoreTokens ()) {
// Get the word and put it in the vector
v.add (st.nextToken ()); // Add to the end of the vector
}
System.out.println (v.firstElement ()); // First item
System.out.println (v.lastElement ()); // Last item
v.setSize (4); // Reduce the number of elements
v.add ("collect."); // Add to the end
// shortened vector
v.set (3, "again"); // Put in position 3
for (int i = 0; i <v.sizeO; i ++) // enumerate the entire vector
System.out.print (v.get (i) + "");
System.out.println ();
The vector class is an example of how objects of the object class can be used, which means that any objects can be combined into a collection. This type of collection organizes and even numbers the elements. In the vector there is the first element, there is the last element. Each element is addressed directly by
index. When adding and removing items, the remaining items are automatically renumbered.
The second example of the collection, the stack class, extends the clade vector .
Class stack
The stack class from the java.utii package . stack items
The stack implements the order of working with elements like a rifle magazine — the cartridge that was last to shoot the last — or, like a railway deadlock — will be the first to shoot a carriage that was last driven there. This processing order is called LIFO (Last In - First Out).
Before work, an empty stack is created by the stack () constructor .
Then the elements are put on the stack and removed, and only the “top” element is available, the last one that is put on the stack.
In addition to the methods of the vector class, the stack class contains five methods that allow you to work with the collection as a stack:
push (Object item) —places the item item onto the stack;
pop () - removes the top item from the stack;
peek () - reads the top element without removing it from the stack;
empty () - checks if the stack is empty;
search (object item) - finds the position of the item element on the stack. The top item has position 1, item 2 below it, and so on. If the item is not found, it returns - 1.
Listing 6.2 shows how you can use the stack to check for a pair of characters.
Listing 6.2. Bracket matching
import java.utii. *;
class StackTesti
static boolean checkParity (String expression,
String open, String close) {
Stack stack = new Stack ();
StringTokenizer st = new StringTokenizer (expression,
"\ t \ n \ r + * / - () {}", true);
while (st..hasMoreTokens ()) {
String tmp = st.nextToken ();
if (tmp.equals (open)), stack.push (open);
i f (tmp.equals (close)) stack.pop ();
}
if (stack.isEmpty ()) return true / return fals e;
}
public static void main (String [] args) {
System.out.println (
checkParityC'a - (b - (c - a) / (b + c) - 2), "(", ")));
}
}
As you can see, collections make it much easier to handle datasets.
Another example of a collection of a completely different kind — tables — is provided by the Hashtable class.
Hashtable class
The Hashtable class extends the abstract Dictionary class. Objects of this class store key-value pairs.
Of these pairs, "Last Name IO. - Number" consists, for example, of a telephone directory.
Another example is a questionnaire. It can be represented as a set of pairs "Last Name - Ivanov", "First Name - Peter", "Patronymic Name - Sidorovich", "Year of Birth - 1975", etc.
There are many similar examples.
Each object of the Hashtable class, in addition to size (size) - the number of pairs, has two more characteristics: capacity (capacity) - buffer size, and load factor (load factor) - the percentage of buffer fullness, after reaching which its size increases.
How to create a table
To create objects, the Hashtable class provides four constructors:
Hashtable () - creates an empty object with an initial capacity of 101 elements and a load factor of 0.75;
Hashtable (int capacity) - creates an empty object with an initial capacity of capacity and a workload indicator of 0.75;
Hashtable (int capacity, float loadFactor) - creates an empty Object with an initial capacity of capacity and load factor loadFactor;
Hashtable (Map f) - creates an object of the Hashtable class, containing all the display elements f, with a capacity equal to twice the number of display elements f , but not less than 11, and a workload indicator of 0.75.
How to fill the table
Two methods are used to populate a Hashtable class object:
Object put (Object key, Object value) - adds a pair of " key - value " if the key key was not in the table, and changes the value of the key key if it already exists in the table. Returns the old key value or pull if it was not. If at least one parameter is null , an exception is thrown;
void putAii (Map f) - adds all the elements of the display f . In key objects, the hashCode () and equals () methods must be implemented .
How to get value by key
The get (Object key) method returns the value of the element with the key key as an object of class object . For further work, it should be converted to a specific type.
How to find out the presence of a key or value
The logical method containsKey (object key) returns true if the table contains the key key .
The logical method containsvalue (Object value) or the old method contains (object value) returns true if the table contains keys with value value .
The isEmpty () boolean method returns true if there are no items in the table.
How to get all the elements of the table
The values () method represents all the table's value values as a Collection interface. All modifications in the collection object modify the table, and vice versa.
The keyset () method provides all the key keys of a table as a set interface. All changes to the set object adjust the table, and vice versa.
The entrySet () method represents all the key-value pairs of the table in the form of a Set interface. All modifications to the set object modify the table, and vice versa.
The tostring () method returns a string containing all pairs.
Old methods elements () and keys () return values and keys as an interface. Enumeration .
How to remove items
The remove (Object key) method removes a pair with the key key , returning the value of this key, if it exists, and null if the pair with the key key is not found.
The clear about method deletes all items by clearing the table.
Listing 6.3 shows how the Hashtabie class can be used to create a telephone directory, and in fig. 6.1 - the output of this program.
Listing 6.3. Phonebook
import java.util. *;
class PhoneBook {
public static void main (String [] args) {
Hashtabie yp = new Hashtabie ();
String name = null;
yp.put ("John", "123-45-67");
yp.put ("Lemon", "567-34-12");
yp.put ("Bill", "342-65-87");
yp.put ("Gates", "423-83-49");
yp.put ("Batman", "532-25-08");
try {
name = args [0];
(catch (Exception e) {
System.out.println ("Usage: Java PhoneBook Name");
return;
}
if (yp.containsKey (name))
System.out.println (name + "'s phone =" + yp.get (name));
else
System.out.println ("Sorry, no such name");
)
}
Fig. 6.1. Work with the phone book
Properties class
The ' Properties class extends the Hashtabie class. It is intended mainly for input and output of pairs of system properties and their values. Pairs are stored as strings. There are two constructors in the Properties class:
Properties () - creates an empty object;
Properties (Properties default) - creates an object with specified pairs of default properties.
In addition to the methods inherited from the Hashtabie class, the Properties class has the following methods.
Two methods that return the value of a key-string as a string:
• string getProperty (string key) - returns the value by key ;
• String getProperty (String.key, String defaultValue) - returns the value by the key key ; if there is no such key, the defaultValue is returned.
The setProperty method (String key, String value) adds a new pair if there is no key key , and changes the value if there is a key key .
The load (Inputstream in ) method loads properties from the in stream.
The list (PrintStream out) and list (PrintWriter out) methods output properties to the output out stream.
The store (OutputStream out, String header) method outputs properties to the output out stream with the header header .
Very simple listing 6.4 and fig. 6.2 shows the output of all system properties of Java.
Listing 6.4. Displaying system properties
class Prop {
public static void main (String [] args) {
System.getProperties (). List (System.out);
}
}
Examples of classes Vector, Stack, Hashtabie, Properties show the convenience of collection classes. Therefore, Java 2 has developed a whole hierarchy of collections. It is shown in Fig. 6.3. Italics' written interface names. Dotted lines indicate the classes that implement these interfaces. All collections are broken; into three groups described in the interfaces List, Set and Map.
Fig. 6.2. System properties
Fig. 6.3. Class hierarchy and collection interfaces
An example of the implementation of the List interface is the Vector class, an example of the implementation of the Mar interface is the Hashtabie class.
The List and set collections have a lot in common, so their common methods are combined and made into the Superinterface of the Collection .
Let's see what, according to Java API developers, should be contained in these collections.
Interface collection
The collection interface of the java.util package describes the general properties of the List and set collections. It contains methods for adding and removing elements, checking and transforming elements:
boolean add (Object obj) - adds the obj element to the end of the collection; returns false if there is already such an element in the collection, and the collection does not allow duplicate elements; returns true if the addition was successful;
boolean addAii (Collection coll) - adds all elements of the coll collection to the end of the collection;
void clear ( ) - removes all elements of the collection;
boolean contains (Object obj) - checks for the presence of the obj element in the collection;
boolean containsAii (Collection coll ) - checks for the presence of all elements of the coll collection in this collection;
boolean isEmpty () - checks if the collection is empty;
iterator iterator () - returns the iterator of this collection;
boolean remove (object obj) - removes the specified item from the collection; returns false if the item is not found, true if the deletion was successful;
boolean removeAii (Collection coil) - removes elements of the specified collection lying in this collection;
boolean retainAii (Collection coll ) - removes all elements of this collection, except elements of the coll collection;
int size () - returns the number of elements in the collection;
object [] toArray () - returns all elements of the collection as an array;
Objectn toArray <object [] a) - writes all the elements of the collection into the array a, if there is enough space in it.
Interface List
The List interface from the java.utii package , which extends the collection interface, describes methods for working with ordered collections. Sometimes they are called sequences . Elements of such a collection are numbered, starting from zero, they can be accessed by index. Unlike the Set collection, the elements of the List collection can be repeated.
The vector class is one of the implementations of the List interface.
The List interface adds methods to the methods of the Collection interface using the index element of the element:
void add (int index, object obj) - inserts the element obj at the position index ; old elements, starting from the index position, are shifted, their indices increase by one;
boolean addAll (int index, Collection coll) - inserts all elements of the coil collection;
object get (int index) - returns the element that is in the index position;
int indexOf (Object obj) - returns the index of the first appearance of the obj element in the collection;
int lastindexOf (object obj) - returns the index of the last occurrence of the obj element in the collection;
Listiterator listiterator () - returns the collection iterator;
Listiterator listiterator (int index) - returns the end of the collection iterator from position index ;
object set (int index, object obj) - replaces the element located at index position with the element obj ;
List subListUnt from, int to) - returns part of the collection from the position from inclusive to position to exclusively.
Interface Set
The set interface of the java.utii package , which extends the Collection interface, describes an unordered collection that does not contain duplicate elements. This corresponds to the mathematical concept of a set . Such collections are convenient for checking the presence or absence of a property that defines a set for an element. No new methods have been added to the Set interface, just the add () method will not add another copy of the element if such an element already exists in the set.
This interface is extended by the sortedset interface.
SortedSet interface
Интерфейс sortedset из пакета java.utii, расширяющий интерфейс Set, описывает упорядоченное множество, отсортированное по естественному порядку возрастания его элементов или по порядку, заданному реализацией
интерфейса comparator.
Элементы не нумеруются, но есть понятие первого, последнего, большего и меньшего элемента.
Дополнительные методы интерфейса отражают эти понятия:
comparator comparator () — возвращает способ упорядочения коллекции; object first ()— возвращает первый, меньший элемент коллекции;
SortedSet headset (Object toEiement) — возвращает начальные, меньшие элементы до элемента toEiement исключительно;
object last () — возвращает последний, больший элемент коллекции;
SortedSet subset(Object fromElement, Object toEiement) — Возвращает подмножество коллекции от элемента fromElement включительно до элемента toEiement исключительно;
SortedSet tailSet (Object fromElement) — возвращает последние, большие элементы коллекции от элемента fromElement включительно.
Интерфейс Map
Интерфейс Map из пакета java.utii описывает коллекцию, состоящую из пар "ключ — значение". У каждого ключа только одно значение, что соответствует математическому понятию однозначной функции или отображения (тар).
Такую коллекцию часто называют еще словарем (dictionary) или ассоциативным массивом (associative array).
Обычный массив — простейший пример словаря с заранее заданным числом элементов. Это отображение множества первых неотрицательных целых чисел на множество элементов массива, множество пар "индекс массива ^-элемент массива".
Класс HashTable — одна из реализаций интерфейса мар.
Интерфейс Map содержит методы, работающие с ключами и значениями:
boolean containsKey (Object key) — проверяет наличие ключа key ;
boolean containsValue (Object value) — проверяет наличие значения value ;
Set entryset () — представляет коллекцию в виде множества, каждый элемент которого — пара из данного отображения, с которой можно работать методами вложенного интерфейса Map. Entry;
object get (object key) — возвращает значение, отвечающее ключу key; set keyset () — представляет ключи коллекции в виде множества;
Object put(Object key, Object value) — добавляет пару "key— value",
если такой пары не было, и заменяет значение ключа key, если такой ключ уже есть в коллекции;
void putAii (Map m) — добавляет к коллекции все пары из отображения m;
collection values () — представляет все значения в виде коллекции.
В интерфейс мар вложен интерфейс Map.Entry , содержащий методы работы с отдельной парой.
Вложенный интерфейс Map.Entry
Этот интерфейс описывает методы работы с парами, полученными методом entrySet():
методы g etKey() и getvaiue() позволяют получить ключ и значение пары; метод setvaiue (object value) меняет значение в данной паре.
Интерфейс SortedMap
Интерфейс SortedMap , расширяющий интерфейс Map , описывает упорядоченную по ключам коллекцию мар. Сортировка производится либо в естественном порядке возрастания ключей, либо, в порядке, описываемом в интерфейсе Comparator .
Элементы не нумеруются, но есть понятия большего и меньшего из двух элементов, первого, самого маленького, и последнего, самого большого элемента коллекции. Эти понятия описываются следующими методами:
comparator comparator () — возвращает способ упорядочения коллекции;
object firstKey() — возвращает первый, меньший элемент коллекции;
SortedMap headMap(Object toKey) — возвращает начало коллекции до элемента с ключом toKey исключительно;
object lastKey() — возвращает последний, больший ключ коллекции;
SprtedMap subMap (Object fromKey, Object toKey) — возвращает часть коллекции от элемента с ключом fromKey включительно до элемента с ключом toKey исключительно;
SortedMap taiiMap (object fromKey) — возвращает остаток коллекции от элемента fromKey включительно.
Вы можете создать свои коллекции, реализовав рассмотренные интерфейсы. Это дело трудное, поскольку в интерфейсах много методов. Чтобы облегчить эту задачу, в Java API введены частичные реализации интерфейсов — абстрактные классы-коллекции.
Абстрактные классы-коллекции
Эти классы лежат в пакете java.util,
Абстрактный класс AbstractGollection .реализует интерфейс Collection , но оставляет нереализованными методы iterator (), size ().
Абстрактный класс AbstractList реализует интерфейс List , но оставляет нереализованным метод get(mt) и унаследованный метод size() Этот класс позволяет реализовать коллекцию спрямым доступом к элементам, подобно массиву
Абстрактный 5класе AbsttaatSequantaaiList реализует интерфейс List , но оставляет нереализованным метод listiteratordnt index) и унаследованный метрд size () . Данный класс позволяет реализовать коллекции с последовательным доступом к элементам с помощью итератора Listiterator
Абстрактный класс Abstractset реализует интерфейс Set , но оставляет нереализованными методы, унаследованные от Absjractcollection
Абстрактный класс AbstractMap реализует интерфейс Map , но оставляет нереализованным метод entrySet (),
Наконец, в составе Java API есть полностью реализованные классы-коллекции помимо уже рассмотренных классов Vectdr, Stack, Hashtable и Properties , Это классы ArrayList, LinkedList, HashSet, TreeSet, HashMap, TreeMap, WeakHashMap ,
Для работы с этими классами разработаны интерфейсы iterator ,
Listiterator, Comparator И классы Arrays И Collections.
Перед тем Как рассмотреть использование данных классов, обсудим понятие итератора..
Интерфейс Iterator
В 70—80-х годах прошлого столетия, после того как была осознана важность правильной организации данных в определенную структуру, большое внимание уделялось изучению' и' Построению различных структур данных: связанных списков, очередей, деков, стеков, деревьев, сетей
Вместе c развитием структур данных развивались и алгоритмы работы с ними: сортировка, поиск, обход, хэширование.
Этим вопросам посвящена Обширная литература, посмотрите, например, книгу [11]. '
В 90-х годах было решено заносить данные в определенную коллекцию, скрыв ее внутреннюю структуру, а для работы с данными использовать методы этой коллекции.
В частности, задачу обхода возложили на саму коллекцию. В Java API введен интерфейс iterator , описывающий способ обхода всех элементов коллекции. В каждой коллекции есть метод iterator (), возвращающий реализацию интерфейса iterator для указанной коллекции. Получив эту реализацию, можно обходить коллекцию в некотором порядке, определенном данным итератором, с помощью методов, описанных в интерфейсе iterator и реализованных в этом итераторе. Подобная техника использована в классе
StringTokenizer.
В интерфейсе iterator описаны всего три метода:
логический метод hasNext () возвращает true , если обход еще не завершен;
метод next о делает текущим следующий элемент коллекции и возвращает его в виде объекта класса object ;
метод remove о удаляет текущий элемент коллекции.
Можно представить себе дело так, что итератор — это указатель на элемент коллекции. При создании итератора указатель устанавливается перед первым элементом, метод next () перемещает указатель на первый элемент и показывает его. Следующее применение метода next () перемещает указатель на второй элемент коллекции и показывает его. Последнее применение метода next () выводит указатель за последний элемент коллекции.
Метод remove (), пожалуй, излишен, он уже не относится к задаче обхода коллекции, но позволяет при просмотре коллекции удалять из нее ненужные элементы.
В листинге 6.5 к тексту листинга 6.1 добавлена работа с итератором.
Листинг 6.5. Использование итератора вектора
Vector v = new Vector();
String s = "Строка, которую мы хотим разобрать на слова.";
StringTokenizer st = new StringTokenizer (s, "\ t \ n \ r ,.");
while (st.hasMoreTokens()){
// Получаем слово и заносим в вектор.
v.add(st.nextToken()); // Добавляем в конец вектора }
System.out.print*Ln(v.firstElement(}); // Первый элемент
System.out.println(v.lastElement()); // Последний элемент
v.setSize(4); // Уменьшаем число элементов
v.add ("collect."); // Add to the end of the shortened vector
v.set (3, "again"); // Put in position 3
for (int i = 0; i <v.sizeO; i ++) // enumerate the entire vector
System.out.print (v.get (i) + ".");
System.out.println (};
Iterator it = v.iterator (); // Get the vector iterator
try {
while (it.hasNext ()) // While there are elements in the vector,
System.out.println (it.next ()); // print the current item
} catch (Exception e) {}
Interface listlterator
Интерфейс Listiterator расширяет интерфейс iterator , обеспечивая перемещение по коллекции как в прямом, так и в обратном направлении. Он может быть реализован только в тех коллекциях, в которых есть понятия следующего и предыдущего элемента и где элементы пронумерованы.
В интерфейс Listiterator добавлены следующие методы:
void add (Object element) — добавляет элемент element перед текущим элементом;
boolean hasPrevious () — возвращает true , если в коллекции есть элементы, стоящие перед текущим элементом;
int nextindex() — возвращает индекс текущего элемента; если текущим является последний элемент коллекции, возвращает размер коллекции;
Object previous () - returns the previous element and makes it current;
int previous index () - returns the index of the previous item;
void set (Object element) - replaces the current element with the element element;
executed immediately after next () or previous ().
As you can see, iterators can change the collection in which they work by adding, removing, and replacing items. So that this does not lead to conflicts, an exception is provided that occurs when trying to use iterators in parallel with the native methods of the collection. That is why in Listing 6.5, actions with an iterator are enclosed in a tryUcatch () {} block.
Modify the end of Listing 6.5 using the Listiterator iterator.
// Text Listing 6.1 ...
// ...
Listiterator lit = v.listlterator (); // Get the vector iterator
// The pointer is now before the start of the vector
try {
while (lit.hasNext ()) // While there are elements in the vector
System.out.println (lit.next ()); // Go to the next
// element and output it
// Now pointer past the end of the vector. Let's go to the top
while (lit. hasPrevious ())
System, out. printlnf lit. p'reviblis ()); :
} catch (Exception e) {)
Interestingly, the repeated use of the next () and previous () methods one after another will produce the same current element. : Now let's see what features Java 2 collection classes provide.
Listing Classes
The ArrayList class fully implements the List interface and an iterator of the type iterator . The ArrayList class is very similar to the Vector class, has the same set of methods, and can be used in the same situations.
There are three constructors in the ArrayList class;
ArrayList () - creates an empty object;
ArrayList (Collection coil) - creates an object containing all elements of the coll collection;
ArrayList (int initCapacity ) - creates an empty Capacity Object initCapacity .
The only difference between the ArrayList class and the vector class is that the ArrayList class is out of sync. It means that simultaneous modification of an instance of this class by several subprocesses will lead to unpredictable results.
We will look at these questions in chapter 17.
Bidirectional list
The LinkedList class fully implements the List interface and contains additional methods that turn it into a bidirectional list. It implements iterators of type iterator and bistiterator .
This class can be used for handle items in a stack, deck, or bidirectional list.
There are two constructors in the LinkedList class:.
LinkedList - creates empty object
LinkedList (Collection coil) - creates an object containing all the elements of the coll collection.
Mapping Classes
The class, for example, fully implements the Map interface, as well as an iterator of the type iterator . The HashMap class is very similar to the Hashtabie class and can be used in the same situations. It has the same set of functions and the same constructors:
HashMap () - creates an empty object with a load factor of 0.75;
NashMar (int .capacity) - creates an empty object with an initial capacity of capacity and a workload indicator of 0.75;
HashMap (int capacity, float loadFactor) - creates an empty object With an initial capacity capacity and loadFactor ;
HashMap (Map f) - creates an object of the HashMap class, containing all the display elements f , with a capacity equal to twice the number of display elements f, but not less than 11, and a workload indicator of 0.75.
The WeakHashMap class differs from the HashMap class only in that in its objects unused elements that no one refers to are automatically excluded from the object.
Ordered mappings
The TgeeMar class fully implements the sortedMap interface. It is implemented as a binary search tree, so its elements are stored in an ordered manner. it significantly speeds up the search for the desired item.
The order is set either by the natural following of the elements or by an object that implements the Comparator comparison interface.
There are four constructors in this class:
TgeeMar () - creates an empty object with a natural order of elements;
TreeMar (Comparator с) - creates an empty object, in which the order is given by the object of comparison with ;
ТеееМар (Map f) - creates an object containing all the elements of the map f, with the natural order of its elements;
TeeMar (SortedMap sf) - creates an object containing all the sf display elements in the same order.
Here we need to explain how to set the ordering of the elements of the collection.
Comparison of elements of collections
The Comparator interface describes two comparison methods:
int compare (Object obji, object obj2 ) - returns a negative number if objl is in some sense less than obj2 ; zero if they are considered equal; positive number if objl is greater than obj2 . For readers familiar with set theory, let's say that this comparison method has the properties of identity, antisymmetry and transitivity;
boolean equals (Object obj) - compares the given object with the obj object, returning true if the objects match in any sense specified by this method.
For each collection, you can implement these two methods, specifying a specific way of comparing elements, and define an object of the SortedMap class by the second constructor. Elements of the collection will be automatically sorted in the specified order.
Listing 6.6 shows one of the possible ways to order complex numbers — the complex class objects from Listing 2.4. Here is the ComplexCompare class, which implements the Comparator interface. In Listing 6.7, it is used to store multiple sets of complex numbers.
Listing 6.6. Comparison of complex numbers
import java.util. *;
class ComplexCompare implements Comparator {
public int compare (Object objl, Object obj2) {
Complex zl = (Complex) objl, z2 = (Complex) obj2;
double rel = zl.getReO, iml = zl.getlm ();
double re2 = z2.getRe (), im2 = z2.getlm ();
if (rel! = re2) return (int) (rel - re2);
else if (iml! = im2) return (int) (iml - im2);
else return 0;
}
public boolean equals (Object z) {
return compare (this, z) == 0;
}
}
Classes that create sets
The HashSet class fully implements the set interface and an iterator of the iterator type. The Hashset class is used when you only need to keep one copy of each item.
There are four constructors in the HashSet class:
Hashset () - creates an empty object with a load factor of 0.75;
HashSet (int capacity) - creates an empty object with an initial capacity of capacity and a workload indicator of 0.75;
HashSet (int capacity, float loadFactor) - creates an empty object with the initial capacity of capacity and loadFactor ;
HashSet (Collection coll) - creates an object containing all elements of the coll collection, with a capacity equal to twice the number of elements of the coll collection, but not less than 11, and a workload indicator of 0.75.
Ordered sets
The TreeSet class fully implements the sortedset interface and an iterator of the iterator type. The TreeSet class is implemented as a binary search tree, which means that its elements are stored in an ordered form. This greatly speeds up the search for the desired item.
The order is set either by the natural following of the elements or by an object that implements the Comparator comparison interface.
This class is useful when searching for an element in a set, for example, to check whether an element has a property that defines a set.
There are four constructors in the TreeSet class:
TreeSet () - creates an empty object with a natural order of elements;
TreeSet (Comparator с) - creates an empty object, in which the order is specified by the comparison object;
TreeSet (Collection coll) - creates an object containing all elements of the coll collection, with the natural order of its elements;
TreeSet (SortedMap sf) - creates an object containing all the sf display elements in the same order.
Listing 6.7 shows how to store complex numbers in an ordered manner. The order is specified by the object of the class ComplexCompare , defined in Listing 6.6.
Listing 6.7. Storing complex numbers in an orderly manner
TreeSet ts = new TreeSet (new ComptexCompare ());
ts.add (new Complex (1.2, 3.4));
ts. add (new Complex (-1.25, 33.4 ”;
ts.add (new Complex (1.23, -3.45));
ts.add (new Complex (16.2, 23.4));
Iterator it = ts.iterator ();
while (it.hasNext ()), ((Complex) it.next ()). pr ();
Collection Actions
Collections are designed to store items in a convenient form for further processing. Very often, processing consists in sorting the elements and searching for the desired element. These and other processing methods are collected in Class Collections .
Collections class methods
All methods of the collections class are static, they can be used without creating instances to the Collections class.
As usual in static methods, the collection with which the method works is given by its argument.
Sorting can be done only in an ordered collection that implements the List interface. There are two methods for sorting in the collections class:
static void sort (List coll) - sorts in a natural ascending order the collection coll that implements the List interface;
static void sort (List coll, Comparator c) - sorts collection coll
in the order given by object c. After sorting, you can perform a binary search in the collection:
static int binarySearch (List coll, Object element) - searches for an element element is sorted in a natural ascending order by the collection of coll and returns an element index or a negative number if the element is not found; a negative number indicates the index with which the element element would be inserted into the collection, with the opposite sign;
static int binarySearchfList coll, Object element, Comparator c) - TO same, but the collection is sorted in the order specified by the object with .
Four methods find the largest and smallest elements in the collection being ordered:
static object max (Collection coll) - returns the largest element in the natural order coll;
static Object max (Collection coll, Comparator c) - TO In the same order as specified by object c ;
static object mm (Collection coll) - returns the smallest in its natural order element of the soybean collection;
static Object min (Collection coll, Comparator c) - TO In the same order as specified by object c .
Two methods "mix" the elements of the collection in random order:
static void shuffle (List coll) - random numbers are set by default;
static void shuffle (List coll, Random r) - random numbers are determined by the object r .
The reverse method (List coll) reverses the order of the elements.
The copy (List from, List to) method copies the from collection to the to collection.
The fill method (List coll, object element) replaces all elements of the existing coll collection with the element element .
We will get acquainted with other methods as needed.
Conclusion
So, in this chapter, we found out that the Java language provides many tools for working with large amounts of information. In most cases, it is enough to add three to five operators to the program so that nontrivial information processing can be done.
In the next chapter, we will look at similar tools for working with arrays, dates, for obtaining random numbers and other necessary programming tools.
Comments
To leave a comment
Object oriented programming
Terms: Object oriented programming