Лабораторная работа №13
Коллекции. Интерфейс Collection
Теоретические сведения
Коллекция – это структура данных, предназначенная для хранения и обработки объектов некоторого типа. Простейшей коллекцией является массив. Но у него есть много недостатков: во-первых, размер массива определяется заранее, до его использования, поэтому иногда приходится выделять память «с запасом»; во-вторых, каждый элемент массива жестко закреплён в своей ячейке, поэтому удаление элемента является не очень простой задачей.
В языке Java используются различные структуры под общим названием «коллекции», каждая из которых дает возможность добавлять, извлекать, сортировать входящие в них элементы. Механизм осуществления операций может быть различным в зависимости от вида коллекции. Так, например, стек позволяет добавлять элемент только в конец последовательности и извлекать последний элемент. Очередь, напротив, дает возможность извлекать только первый элемент. В множестве элементы вообще не упорядочены и т.д.
В Java для работы с коллекциями используется библиотека JavaCollectionsFramework.
Интерфейсы коллекций
В библиотеке коллекций Java существует два базовых интерфейса, реализации которых и представляют совокупность всех классов коллекций:
1. Collection – коллекция содержит набор объектов (элементов). Здесь определены основные методы для манипуляции с данными, такие как вставка, удаление, поиск.
2. Map – описывает коллекцию, состоящую из пар "ключ – значение". У каждого ключа только одно значение, что соответствует математическому понятию однозначной функции или отображения. Такую коллекцию часто называют еще словарем (dictionary) или ассоциативным массивом (associativearray).
Методы интерфейса Collection:
| int size(); | Возвращает количество элементов. |
| booleanisEmpty(); | Проверяет, является ли коллекция пустой. |
| boolean contains(o: Object); | Проверяет, содержит ли коллекция объект о. |
| Object[] toArray(); | Возвращает массив, содержащий все элементы коллекции. |
| boolean add(e: E); | Добавляет элемент в коллекцию. |
| boolean remove(o: Object); | Удаляет элемент из коллекции. |
| void clear(); | Удаляет все элементы из коллекции. |
Интерфейс Collection расширяют интерфейсы List, Set, Queue и Deque.
List представляет собой неупорядоченную коллекцию, в которой допустимы дублирующие значения. Элементы такой коллекции пронумерованы, нумерация начинается с нуля, к ним можно обратиться по индексу.
Методы интерфейса List:
| get(int index) | Возвращает элемент по индексу. |
| add(int index, T e) | Вставляет элемент в указанную позицию. |
| indexOf(Object obj) | Возвращает первое вхождение элемента в список. |
| lastIndexOf(Object obj) | Возвращает последнее вхождение элемента в список. |
| set(int index, T e) | Заменяет элемент в позиции index. |
| subList(int from, int to) | Возвращает новый список, представляющий собой часть главного. |
Интерфейс Set описывает множество. Элементы множества не упорядочены, множество не может содержать двух одинаковых элементов. Интерфейс Set унаследован от интерфейса Collection, но никаких новых методов не добавляет. Изменяется только смысл метода add(Objectitem) – он не станет добавлять объект item, если он уже присутствует во множестве.
Интерфейс Queue описывает очередь. Элементы могут добавляться в очередь только с одного конца, а извлекаться с другого (аналогично очереди в магазине). Интерфейс Queue также унаследован от интерфейса Collection. Специфические для очереди методы:
| poll() | возвращает первый элемент и удаляет его из очереди |
| peek() | возвращает первый элемент очереди, не удаляя его |
| offer(Objectobj) | добавляет в конец очереди новый элемент и возвращает true, если вставка удалась |
Интерфейс Deque расширяет описанный выше интерфейс Queue и определяет поведение двунаправленной очереди, которая работает либо как обычная однонаправленная очередь, либо как стек (последний вошел, первый вышел). Методы интерфейса Deque:
| void addFirst(E obj) | Добавляет элемент в начало очереди. |
| void addLast(E obj) | Добавляет элемент obj в конец очереди. |
| E getFirst() | Возвращает без удаления элемент из головы очереди. Если очередь пуста, генерирует исключение NoSuchElementException. |
| E getLast() | Возвращает без удаления последний элемент очереди. Если очередь пуста, генерирует исключение NoSuchElementException. |
| booleanofferFirst(E obj) | Добавляет элемент obj в самое начало очереди. Если элемент удачно добавлен, возвращает true, иначе –false. |
| booleanofferLast(E obj) | Добавляет элемент obj в конец очереди. Если элемент удачно добавлен, возвращает true, иначе –false. |
| E peekFirst() | Возвращает без удаления элемент из начала очереди. Если очередь пуста, возвращает значение null. |
| E peekLast() | Возвращает без удаления последний элемент очереди. Если очередь пуста, возвращает значение null. |
| E pollFirst() | Возвращает с удалением элемент из начала очереди. Если очередь пуста, возвращает значение null. |
| E pollLast() | Возвращает с удалением последний элемент очереди. Если очередь пуста, возвращает значение null. |
| E pop() | Возвращает с удалением элемент из начала очереди. Если очередь пуста, генерирует исключение NoSuchElementException. |
| void push(E element) | Добавляет элемент в самое начало очереди. |
| E removeFirst() | Возвращает с удалением элемент из начала очереди. Если очередь пуста, генерирует исключение NoSuchElementException. |
Классы, реализующие интерфейс List
Класс Vector – реализация динамического массива объектов. Позволяет хранить любые данные, включая null в качестве элемента. Эту коллекцию не рекомендуется использовать, если не требуется достижения потокобезопасности. Потому как в Vector, в отличии от других реализаций List, все операции с данными являются синхронизированными. В качестве альтернативы часто применяется аналог – ArrayList.
Класс ArrayList также представляет собой динамический массив элементов, длина которого автоматически увеличивается при добавлении новых элементов. Время доступа к элементу по индексу минимально (в отличие от LinkedList). Удаление элемента из списка осуществляется сдвигом всех элементов, находящиеся правее, на одну ячейку влево; при этом реальный размер массива меняется. Если при добавлении элемента оказывается, что массив полностью заполнен, будет создан новый массив размером (n * 3) / 2 + 1, в него будут помещены все элементы из старого массива + новый добавляемый элемент.
Класс LinkedList реализует интерфейсы List и Queue. Представляет собой двусвязный список. Это структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и две ссылки на следующий и предыдущий узел списка. Время доступа к произвольному элементу больше, чем у ArrayList (заисключением первого и последнего элемента– ссылки на них хранятся постоянно, доступ к остальным элементам осуществляется последовательным перебором). Скорость операций вставки и удаления элемента выше, чем у ArrayList.
Классы, реализующие интерфейс Set
Следующие три класса реализуют интерфейс Set. Они не могут содержать повторяющихся элементов. Различаются способом упорядочивания элементов.
Класс HashSet хранит элементы, упорядоченные по хэш-ключам.
Класс TreeSet хранит элементы, упорядоченныепо значению.
Класс LinkedHashSet хранит элементы, упорядоченныев порядке их добавления.
Интерфейс Iterator
Для навигации по коллекциям в Java предусмотрено специальное архитектурное решение, получившее свою реализацию в интерфейсе Iterator. Идея заключается в том, что к коллекции «привязывается» объект, единственное назначение которого – выдать все элементы этой коллекции в некотором порядке, не раскрывая ее внутреннюю структуру.
Интерфейс Iterator имеет всего три метода:
| next() | Возвращает очередной элемент коллекции, к которой «привязан» итератор (и делает его текущим). Порядок перебора определяет сам итератор. |
| hasNext() | Возвращает true, если перебор элементов еще не закончен. |
| remove() | Удаляет текущий элемент. |
Интерфейс Collection, помимо рассмотренных ранее методов, имеет метод iterator (), который возвращает итератор для данной коллекции, готовый к ее обходу. С помощью такого итератора можно обработать все элементы любой коллекции следующим простым способом:
Iteratoriter = coll.iterator(); // coll - коллекция
while (iter. hasNext ()) {
// обрабатываем объект, возвращаемый методом iter. next ()
}
Для коллекций, элементы которых проиндексированы, определен более функциональный итератор, позволяющий двигаться как в прямом, так и в обратном направлении, а также добавлять в коллекцию элементы. Такой итератор имеет интерфейс ListIterator, унаследованный от интерфейса Iterator и дополняющий его следующими методами:
| previous() | Возвращает предыдущий элемент (и делает его текущим). |
| hasPrevious() | Возвращает true, если предыдущий элемент существует (т.е. текущий элемент не является первым элементом для данного итератора). |
| add(Objectitem) | Добавляет новый элемент перед текущим элементом. |
| set(Objectitem) | Заменяет текущий элемент. |
| nextIndex() | Возвращает индекс следующего элемента. |
| previousIndex() | Возвращает индекс предыдущего элемента. |
Пример 1
Написать программу, имитирующую процесс появления новых объектов – бабочек одного вида. Новая бабочка появляется каждые 2 секунды с вероятностью 50%. О каждой бабочке хранится информация: вид (махаон), время рождения, имя (махаон1, махаон2 и т.д.). При появлении новой бабочки в окне появляется ее изображение. Размер и координаты изображения – случайные числа.
Время жизни бабочки – случайное число от 20 до 30 секунд. Информация о погибшей бабочке удаляется из списка, ее изображения также удаляется.
Для хранения информации о живых и погибших объектах использовать коллекцию LinkedList. Процесс начинается при запуске программы. При нажатии на кнопку Стоп вдва окна должна выводиться информация о живых и погибших объектах.
import java.awt.Graphics;
import java.awt.Image;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.io.File;
import java.io.IOException;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Random;
import javax.imageio.ImageIO;
import javax.swing.Box;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.JTextArea;
public class Lab14Pr1 {
public static void main(String[] args) {
StartPanelstartPanel = new StartPanel();
GraphicPanelgraphicPanel = new GraphicPanel();
Butterflies butterflies = new Butterflies(startPanel, graphicPanel);
LinkedList<Butterfly> bugs = new LinkedList<Butterfly> ();
LinkedList<Butterfly>diedbugs = new LinkedList<Butterfly> ();
long startTime = System.currentTimeMillis();
long nowTime;
int number = 1;
while (startPanel.stopGeneration()) {
nowTime = System.currentTimeMillis();
if (nowTime-startTime>= 2000) {
float probability = (float)Math.random();
if (probability >= 0.5) {
startTime = nowTime;
Random rand = new Random();
int x = rand.nextInt(200) + 100;
int y = rand.nextInt(200) + 100;
int width = rand.nextInt(11) + 10;
int height = rand.nextInt(11) + 10;
bugs.add(new Butterfly("mahaon", nowTime, "mahaon"+number+"\n", x, y, width, height));
graphicPanel.setBut(bugs);
graphicPanel.repaint();
number++;
}
}
Random randDeath = new Random();
int deathtime = randDeath.nextInt(10000)+20000;
if (bugs.peekFirst()!= null) {
nowTime = System.currentTimeMillis();
if (bugs.peekFirst().birthtime + deathtime <= nowTime) {
diedbugs.add(bugs.peekFirst());
bugs.removeFirst();
graphicPanel.setBut(bugs);
graphicPanel.repaint();
}
}
}
startPanel.information.setText("");
Iterator <Butterfly> it = bugs.iterator();
while (it.hasNext()) {
Butterfly oneBut = it.next();
startPanel.information.append(oneBut.type + " " + oneBut.birthtime + " " + oneBut.name);
}
it = diedbugs.iterator();
while (it.hasNext()) {
Butterfly oneBut = it.next();
startPanel.information1.append(oneBut.name);
}
}
}
class Butterflies extends JFrame {
Butterflies (StartPanelstartPanel, GraphicPanelgraphicPanel) {
super ("Генераторбабочек");
Box box1 = Box.createHorizontalBox();
box1.add(startPanel);
box1.add(graphicPanel);
this.getContentPane().add(box1);
this.setDefaultCloseOperation(EXIT_ON_CLOSE);
this.setVisible(true);
this.setExtendedState(MAXIMIZED_BOTH);
}
}
class StartPanel extends JPanel {
private boolean play;
JTextArea information;
JTextArea information1;
StartPanel () {
this.play = true;
JButton stop = new JButton ("Стоп");
stop.addActionListener(new ActionListener() {
public void actionPerformed(ActionEvent event) {
play = false;
}
});
information = new JTextArea(30, 20);
information.setLineWrap(true);
information.setWrapStyleWord(true);
information.setText("Идет процесс генерации...");
information1 = new JTextArea(30, 20);
information1.setLineWrap(true);
information1.setWrapStyleWord(true);
Box box = Box.createVerticalBox();
box.add(information);
box.add(stop);
box.add(information1);
this.add(box);
}
booleanstopGeneration(){
return this.play;
}
}
class GraphicPanel extends JPanel {
private LinkedList<Butterfly> bugs;
GraphicPanel() {
}
public void paint(Graphics g) {
super.paint(g);
//при инициализации объекта startPanel список bugs еще не существует. Чтобынебылоошибки, используем try
try
{
Iterator <Butterfly>iter= this.bugs.iterator();
try
{
Image img = ImageIO.read(new File("C:/Users/belov/Lab13Pr1/src/but.png"));
while (iter.hasNext()) {
Butterfly oneBut = iter.next();
g.drawImage(img, oneBut.coordX, oneBut.coordY, oneBut.width, oneBut.height, null);
}
}
catch(IOException ex)
{
System.out.println("Файлненайден");
}
}
catch (Exception e)
{
}
}
public void setBut (LinkedList<Butterfly> bugs) {
this.bugs = bugs;
}
}
class Butterfly {
String type;
long birthtime;
String name;
intcoordX;
intcoordY;
int width;
int height;
Butterfly(String type, long birthtime, String name, intcoordX, intcoordY, int width, int height){
this.type = type;
this.birthtime = birthtime;
this.name = name;
this.coordX = coordX;
this.coordY = coordY;
this.width = width;
this.height = height;
}
}
Пример 2
В предыдущий пример добавить меню для сохранения информации в файл и открытия нужного файла при запуске программы.
Задания для самостоятельной работы.
Задание 13.1
Написать программу, имитирующую процесс появления новых объектов двух видов.Для хранения информации об объектах использовать коллекцию согласно варианту. Процесс начинается при запуске программы. При нажатии на кнопку Стоп в окно должна выводиться информация о созданных за время работы объектах и время работы программы.
После нажатия кнопки Стоп должна стать доступной кнопка Поиск объекта, щелчок на которой открывает диалоговое окно для ввода имени объекта. После ввода имени в отдельное окно должна выводиться вся информация об этом объекте.
В окне создать меню для выхода из программы и сохранения данных об объектах в файл.
Вариант 1
Объект – муравей. Бывают 2 видов: рабочий и воин. Рабочие рождаются каждую1 секунду с вероятностью 75%. Воины рождаются каждые 3 секунды с вероятностью 60%.
Коллекция для хранения объектов: Vector
Коллекция для хранения и поиска уникальных идентификаторов: HashSet
Коллекция для хранения объектов по времени рождения: TreeMap
Вариант 2
Объект – пчела. Бывают 2 видов: трутень и рабочий. Трутни рождаются каждые 5 секунд, если их количество менее 30% от общего числа пчел, в противном случае – не рождаются вовсе. Рабочие рождаются каждые 2 секундыс вероятностью 50%.
Коллекция для хранения объектов: ArrayList
Коллекция для хранения и поиска уникальных идентификаторов: HashSet
Коллекция для хранения объектов по времени рождения: TreeMap
Вариант 3
Объект – аквариумная рыбка. Бывают 2 видов: золотая и гуппи. Золотые рыбки рождаются каждые 2 секундыс вероятностью 60%. Гуппи рождаются каждые 1.5 секунды с вероятностью 65%.
Коллекция для хранения объектов: LinkedList
Коллекция для хранения и поиска уникальных идентификаторов: HashSet
Коллекция для хранения объектов по времени рождения: TreeMap
Вариант 4
Объект – кролик. Бывают 2 видов: обыкновенный и альбинос. Обыкновенные кролики рождаются каждую секундус вероятностью 65%. Альбиносы рождаются каждые 2 секунды, при условии, что их количество менее 60% от общего числа кроликов, в противном случае – не рождаются вовсе.
Коллекция для хранения объектов: Vector
Коллекция для хранения и поиска уникальных идентификаторов: TreeSet
Коллекция для хранения объектов по времени рождения: HashMap
Вариант 5
Список объектов продажи на автомобильном рынке состоит из 2-х видов машин: грузовые и легковые. Грузовые машины генерируются каждые 2 секунды с вероятностью 90%. Легковые генерируются каждые 0.5 секунд с вероятностью 50%.
Коллекция для хранения объектов: ArrayList
Коллекция для хранения и поиска уникальных идентификаторов: TreeSet
Коллекция для хранения объектов по времени рождения: HashMap
Вариант 6
Рабочий коллектив компании состоит из разработчиков и менеджеров. Разработчики генерируются каждые 2 секунды с вероятностью 70%. Менеджеры генерируются каждые 3 секундыпри условии, что их количество менее 70% от общего числа разработчиков, в противном случае – не генерируются.
Коллекция для хранения объектов: LinkedList
Коллекция для хранения и поиска уникальных идентификаторов: TreeSet
Коллекция для хранения объектов по времени рождения: HashMap
Вариант 7
Обитатели террариумамогут быть двух видов: лягушки и черепахи. Лягушки генерируются каждую1 секунду с вероятностью 80%. Черепахи генерируются каждые 3 секунды с вероятностью 60%.
Коллекция для хранения объектов: Vector
Коллекция для хранения и поиска уникальных идентификаторов: HashSet
Коллекция для хранения объектов по времени рождения: HashMap
Вариант 8
Список транспортных средств на дороге состоит из двух категорий: автомобили и мотоциклы. Автомобили генерируются каждые 2 секунды с вероятностью 50%. Мотоциклы генерируются каждые 5 секунд с вероятностью 65%.
Коллекция для хранения объектов: ArrayList
Коллекция для хранения и поиска уникальных идентификаторов: HashSet
Коллекция для хранения объектов по времени рождения: HashMap
Вариант 9
Объект обучающийся. Бывает 2 видов: студент (муж. пола) и студентка (жен. пола).Студенты генерируются каждые 2 секунды с вероятностью 50%. Студентки генерируются каждые 2.5 секунды с вероятностью 70%.
Коллекция для хранения объектов: Vector
Коллекция для хранения и поиска уникальных идентификаторов: TreeSet
Коллекция для хранения объектов по времени рождения: TreeMap
Вариант 10
Объекты – сельскохозяйственные животные. Могут быть двух типов: коровы и лошади. Коровы генерируются каждые 1.5 секунды с вероятностью 75%. Лошади генерируются каждые 2 секунды с вероятностью 65%.
Коллекция для хранения объектов: ArrayList
Коллекция для хранения и поиска уникальных идентификаторов: TreeSet
Коллекция для хранения объектов по времени рождения: TreeMap
Задание 13.2
Добавить в окно визуализацию процесса генерации новых объектов. Левая часть окна отводится для вывода текстовой информации, в правой части окна при генерации нового объекта должно появляться графическое изображение, соответствующее объекту. Координаты точки появления объекта получить датчиком случайных чисел. Размер графического изображения объекта – случайное число в интервале от 10 до 20 для объектов первого вида и от 20 до 30 для объектов второго вида. Информация о размере объекта является одним из свойств объекта и должна храниться в коллекции.
В левой части добавить кнопки Пауза и Продолжить, нажатие на которые приостанавливает и возобновляет работу программы.
Задание 13.3
Добавить в программу период жизни объекта. Время жизни определяется случайным числом в интервале от 1 до 5 у объектов первого вида и от 2 до 6 у объектов второго вида. Объекты с истекшим периодом жизни должны удаляться из списка, их графическое изображение также должно быть удалено. Добавить в окно текстовое поле для вывода информации об удаленных объектах. Информацию выводить в виде «Имя объекта – время жизни».
