Эффективный способ создать отсортированную очередь, чей итератор повторяется в начале в Java

Question

Я ищу реализацию или метод создания изменяемого (с частыми обновлениями), отсортированного, очереди или списка, который повторяется в итерации.Примером может быть что-то [1, 3, 4, 9], где next () циклически перебирает элементы и возвращает обратно к 1 после 9. Элементы часто удаляются и добавляются, и их необходимо правильно отсортировать.

Первоначально я планировал использовать LinkedList или PriorityQueue, но проблемы росли.Мне нужно, чтобы очередь сортировалась (желательно при обновлении, а не итерации), следовательно, с использованием PriorityQueue, но мне также нужно, чтобы очередь повторялась при итерации (выполняется вручную, а не с помощью цикла).Я подумал о создании класса, который содержал бы Comparator и упаковывал Iterator, который выглядел примерно так:

public class SortedRepeatingQueue<T> extends LinkedList<T> {
    private final Comparator<T> comparator;
    private Iterator<T> iterator = iterator();

    public SortedRepeatingQueue(Comparator<T> comparator) {
        this.comparator = comparator;
    }

    public T next() {
        Collections.sort(this, comparator);
        if (!iterator.hasNext()) {
            iterator = iterator();
        }
        return iterator.next();
    }
}

Однако это могло бы создать проблемы, если запись была удалена или добавлена ​​во время итерации, как это сделал бы кэшированный Iterator.не будет обновляться, и для его обновления потребуется немало усилий, чтобы мы продолжили работу с тем же индексом.Например, если бы мы перебирали [1,2,3,5], находились в 3, а затем вставляли 4, обновление итератора, чтобы удостовериться, что next () вернул 4 вместо 5, было бы сложно.Другим вариантом было простое расширение List, где next () берет первый элемент, возвращает его, а затем перемещает его назад (например, [1,3,4,5] .next () возвращает 1 и создает [3,4,5,1]).Однако это будет отменено любой сортировкой, сделанной в списке.Я также рассмотрел полностью пользовательскую реализацию, но я не очень доверяю себе, чтобы создать безопасную, полностью работающую реализацию этого, и это заняло бы довольно много времени.

Я ищу любой метод обработкиэто быстро (хотя скорость не является основным приоритетом, так как n никогда не должно быть больше 20-30), потому что я полностью в замешательстве.

Спасибо за любую помощь.

Answer 1

Ну, я укусил пулю и написал свою собственную реализацию

/**
 * Implementation of {@link java.util.Queue} that represents a continuous queue of ordered data.
 * Elements are automatically sorted when added, by a given {@link Comparator}
 * This class is useful for something like a turn based game, in which a group of users take turns to perform
 * an action, and then repeat back to the first user.
 * Because of this, direct iteration or looping over <strong>WILL REPEAT INDEFINITELY</strong>, causing an
 * infinite loop.
 * A more suited example would be something like:
 * <p>
 * var currentPlayingUser;
 * while(game in progress){
 * //wait for the user to take their turn
 * currentPlayingUser = queue.poll();
 * }
 *
 * @param <T> The type of element in the queue
 * @author Alexander Wood http://bristermitten.me
 */
public class SortedRepeatingQueue<T> extends AbstractQueue<T> {

    /**
     * Internal list for this implementation.
     * This list is guaranteed to be sorted at all times
     */
    private final List<T> backingList = new ArrayList<>();
    private Comparator<T> comparator;
    private Itr iterator = iterator();

    public SortedRepeatingQueue(Comparator<T> comparator) {
        this.comparator = comparator;
    }

    /**
     * Return, but do not remove the head element.
     * Due to the cyclic nature, removing the head element would not match the intended functionality.
     * However, this will cycle through the elements. That is, given a SortedRepeatingQueue [1,2,3]
     * poll will return 1, then 2, then 3, then 1, etc
     * <p>
     * This is functionally equivalent to the head element being moved to the tail rather than removed, although
     * is not what happens.
     *
     * @return The "head" element of this SortedRepeatingQueue
     */
    @Override
    public T poll() {
        return iterator.next();
    }

    @Override
    public T peek() {
        return iterator.nextWithoutCycle();
    }

    @Override
    public boolean offer(T t) {
        return add(t);
    }

    public boolean add(T e) {
        backingList.add(e);
        backingList.sort(comparator);
        return true;
    }

    public boolean addAll(Collection<? extends T> c) {
        boolean b = backingList.addAll(c);
        backingList.sort(comparator);
        return b;
    }

    public boolean remove(Object o) {
        return backingList.remove(o);
    }

    public Itr iterator() {
        return new Itr();
    }

    public int size() {
        return backingList.size();
    }

    @Override
    public String toString() {
        return "SortedRepeatingQueue{" +
                "backingList=" + backingList +
                '}';
    }

    private class Itr implements Iterator<T> {
        private int cursor = 0;

        public boolean hasNext() {
            return true;
        }

        public T next() {
            if (cursor == backingList.size()) {
                cursor = 0;
            }
            return backingList.get(cursor++);
        }

        public T nextWithoutCycle() {
            if (cursor == backingList.size()) {
                cursor = 0;
            }
            return backingList.get(cursor);
        }

        public void remove() {
            if (cursor == backingList.size()) {
                cursor = 0;
            }
            backingList.remove(cursor);
        }
    }
}

Он использует итератор на основе курсора и упаковывает отсортированный ArrayList для достижения именно необходимой функциональности. Элементы могут быть вставлены или удалены, итератор будет обновляться соответствующим образом. Прямая итерация в цикле вызовет бесконечный цикл, но это не было целью. Краткий пример использования приведен в Javadocs, и большинство методов должны иметь очевидную или унаследованную функциональность, а также те, которые не документированы.

Надеюсь, это поможет кому-то еще, если у меня возникнет очень специфическая проблема