Правильна ли такая реализация итератора?

@EdisonMiranda · Регистрация: 22.05.2014

Студворк — интернет-сервис помощи студентам

Доброе время суток. Есть класс очередь, реализован через массив, добавление идет просто подряд за O(1), удаление за O(N) (идет поиск минимального елемента в массиве)

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
import java.util.*;
 
public class PriorityQueue<K extends Comparable> {
    private int index;
    private Comparable[] elements;
 
    public Object[] getElements() {
        return elements;
    }
 
    public PriorityQueue(int capacity) {
        if (capacity < 0)
            capacity = 10;
        elements = new Comparable[capacity];
    }
 
    public PriorityQueue() {
        this(10);
    }
 
    public boolean isEmpty() {
        return index == 0;
    }
 
    public int size() {
        return index;
    }
 
    private void resize() {
        elements = Arrays.copyOf(elements, elements.length * 2);
    }
 
    public void add(K element) {
        if (index == elements.length)
            resize();
 
        elements[index++] = element;
    }
 
    public Comparable remove() {
        if (isEmpty())
            throw new PriorityQueueIsEmptyException("Queue is empty!");
 
        int priorityIndex = 0;
        for (int i = 1; i < index; i++) {
            if (elements[i].compareTo(elements[priorityIndex]) < 0)
                priorityIndex = i;
        }
        Comparable result = elements[priorityIndex];
        index--;
        elements[priorityIndex] = elements[index];
 
        return result;
    }
 
    public Comparable<K> poll() {
        if (isEmpty())
            return null;
 
        return remove();
    }
 
    public Comparable element() {
        if (isEmpty())
            throw new PriorityQueueIsEmptyException("Queue is empty!");
 
        int priorityIndex = 0;
        for (int i = 1; i < index; i++) {
            if (elements[i].compareTo(elements[priorityIndex]) < 0)
                priorityIndex = i;
        }
 
        return elements[priorityIndex];
    }
 
    public Comparable peek() {
        if (isEmpty())
            return null;
 
        return element();
    }
 
    public Iterator iterator() {
        return new QueueIterator();
    }
 
    public void print() {
        for (int i = 0; i < index; i++) {
            System.out.print(elements[i] + " --> ");
        }
        System.out.println();
    }
 
    private class QueueIterator implements Iterator {
        // список индексов елементов, которые уже брались через итератор методом next()
        // храним, чтобы при поиске очередного минимального елемента не искать его среди 
        // тех что уже были
        private List<Integer> usedIndexes;
        
        private Comparable next;
 
        public QueueIterator() {
            usedIndexes = new ArrayList<Integer>();
        }
 
        private Comparable min(Comparable[] elements, int from, int to, List<Integer> usedIndexes) {
            
            // костыль чтобы задать стартовый минимальный елемент
            // не можем начинать с самого первого так как он мог быть уже минимальным до этого
            int startIndex = from;
            for (int i = from; i <= to; i++) {
                if (!usedIndexes.contains(i)) {
                    startIndex = i;
                    break;
                }
            }
 
            Comparable min = elements[startIndex];
            int minIndex = startIndex;
 
            for (int i = from; i <= to; i++) {
                if (!usedIndexes.contains(i) && elements[i].compareTo(min) < 0) {
                    min = elements[i];
                    minIndex = i;
                }
            }
            usedIndexes.add(minIndex);
            return min;
        }
 
        @Override
        public boolean hasNext() {
            return usedIndexes.size() == index;
        }
 
        @Override
        public Comparable next() {
            if (isEmpty())
                throw new NoSuchElementException();
            next = min(elements, 0, index - 1, usedIndexes);
            return next;
        }
 
        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
}

Java
1
2
3
4
5
6
7
8
9
10
public class PriorityQueueIsEmptyException extends RuntimeException {
 
    PriorityQueueIsEmptyException() {
 
    }
 
    PriorityQueueIsEmptyException(String message) {
        super(message);
    }
}

короче, меня интересует мой итератор. Правильно(ну вроде как да) ли он реализован, можно ли лучше и главное насколько это нормально, что метод next() работает получается за O(N²) (то есть долго)

@EdisonMiranda · 19.08.2014, 01:47 **[ТС]**

еще спрошу:

а если реализовать итератор вообще через клон очереди и в методе next() вызывать метод remove() клона

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
private class QueueIterator implements Iterator {
        private PriorityQueue queue;
 
        public QueueIterator() {
            queue = new PriorityQueue(elements, index);
        }
 
        @Override
        public boolean hasNext() {
            return queue.size() > 0;
        }
 
        @Override
        public Comparable next() {
            if (isEmpty())
                throw new NoSuchElementException();
 
            return queue.remove();
        }
 
        @Override
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
public class PriorityQueue<K extends Comparable> {
    private int index;
    private Comparable[] elements;
 
    /* for second iterator
 
    private PriorityQueue(Comparable[] elements, int index) {
        this.elements = elements;
        this.index = index;
    }*/
 
...
}

то чем это чревато?

Добавлено через 21 минуту

Сообщение от EdisonMiranda

то чем это чревато?

по ходу если сначала взять итератор, а потом поменять очередь(например сделать 1 remove()), то внутренний массив клона будет ссылаться на измененный массив, а индекс будет ссылаться на старый индекс так как индекс примитив а не ссылка и если елементы уже закончаться то next() еще будет фигачить елементы, по этому такой итератор не годиться

Добавлено через 6 минут

Сообщение от EdisonMiranda

@Override
* * * * public boolean hasNext() {
* * * * * * return usedIndexes.size() == index;
* * * * }
@Override
* * * * public Comparable next() {
* * * * * * if (isEmpty())
* * * * * * * * throw new NoSuchElementException();
* * * * * * next = min(elements, 0, index - 1, usedIndexes);
* * * * * * return next;
* * * * }

поменять на

Java
1
2
3
4
5
6
7
8
9
10
11
12
13
@Override
        public boolean hasNext() {
            return usedIndexes.size() < index;
        }
 
        @Override
        public Comparable next() {
            if (usedIndexes.size() == index)
                throw new NoSuchElementException();
 
            next = min(elements, 0, index - 1, usedIndexes);
            return next;
        }

@some_name · 19.08.2014, 02:17

Мысли в слух?

Даже не знаю что вам сказать... Я бы на вашем месте гуглил канонические реализации очереди и от туда уже плясал. Бональное сравнение поможет въехать, что и почему сделано именно так.

@EdisonMiranda · 20.08.2014, 21:21 **[ТС]**

Сообщение от some_name

Мысли в слух?

да, у меня также есть привычка разговаривать сам с собой

Сообщение от some_name

Даже не знаю что вам сказать... Я бы на вашем месте гуглил канонические реализации очереди

мне не нужна каноническая, более того - она не нужна в принципе вообще так уже есть готовые, бери и используй, но я хочу ознакомится поглубже так как неглупые люди говорили мне что нужно начинать с базовой алгоритмики и структур данных

Сообщение от some_name

канонические реализации очереди

- добавление O(1) удаление O(N) (добавление как попало)
- добавление O(N) удаление O(1) (поддерживаем массив отсортированным)
- добавление O(logN) удаление O(logN) (через кучу) -- вот то что я нагуглил

у меня есть конкретная очередь на массиве где добавление идет подряд как попало,
я спрашиваю как для нее делать итератор

Добавлено через 5 минут
some_name, я понимаю, что вам это возможно неинтересно/ненужно, я так же хорошо ознакомлен с анекдотом про неуловимого Джо, но не могли бы вы ответить - как бы ВЫ делали итератор(хватит одного метода next()) для класса, который я написал

@some_name · 20.08.2014, 23:51

Сообщение от EdisonMiranda

ВЫ делали итератор

Впринципе, вы все правильно сделали, только один момент меня смущает:
Этот метод из класса PriorityQueue:

Java
1
2
3
 public Iterator iterator() {
        return new QueueIterator();
    }

нужно заменить на

Java
1
2
3
public Iterator iterator() {
        return new QueueIterator(this);
    }

А в классе QueueIterator добавить констурктор

Java
1
2
3
public QueueIterator(PriorityQueue queue ) {
            this.queue = queue;
        }

Это если бегло. А вообще, при желании можно чего-то другого наворотить, например класс QueueIterator можно сделать inner class. Или реализовать классом PriorityQueue интерфейс Iterator.

Новые блоги и статьи Все статьи Все блоги /
Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .	SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .

@some_name Вежливость-главное оружие 233 / 234 / 86 Регистрация: 19.02.2013 Сообщений: 1,446
	19.08.2014, 02:17
	Мысли в слух? Даже не знаю что вам сказать... Я бы на вашем месте гуглил канонические реализации очереди и от туда уже плясал. Бональное сравнение поможет въехать, что и почему сделано именно так. 1