CircularListCursor - an efficient circular cursor on any list

Question

I have decided to create my own CircularListCursor, because I wanted some abstraction and a ListIterator<E> couldn't give enough in my opinion. I'm also using the javafx.beans.Property class, as I really like how it is being used in JavaFX 8 and figured it would be useful.

The basic properties of a cursor are:

Can go backwards
Can go forward
Can get the item under the cursor

My implementation:

public abstract class CircularListCursor<E> {
    private final static int MIN_RANDOM_ACCESS_SIZE = 20;

    public static <E> CircularListCursor<E> of(final List<E> list) {
        Objects.requireNonNull(list, "list");
        if (list.isEmpty()) {
            throw new IllegalArgumentException("list cannot be empty");
        }
        if (list.size() < MIN_RANDOM_ACCESS_SIZE || list instanceof RandomAccess) {
            return new RandomAccessCicularListCursor<>(list);
        }
        else {
            return new DefaultCircularListCursor<>(list);
        }
    }

    abstract public E getCurrent();

    abstract public int getCurrentIndex();

    abstract public E next();

    abstract public int nextIndex();

    abstract public E previous();

    abstract public int previousIndex();

    abstract public IntegerProperty indexProperty();

    abstract public Property<E> elementProperty();

    private static class RandomAccessCicularListCursor<E> extends CircularListCursor<E> {
        private final List<E> list;
        private final int listSize;
        private final IntegerProperty indexProperty;
        private final Property<E> elementProperty;

        private RandomAccessCicularListCursor(final List<E> list) {
            this.list = list;
            this.listSize = list.size();
            this.indexProperty = new SimpleIntegerProperty(0);
            this.elementProperty = new SimpleObjectProperty<>(getCurrent());
        }

        @Override
        public E getCurrent() {
            return list.get(getCurrentIndex());
        }

        @Override
        public int getCurrentIndex() {
            checkForComodification();
            return indexProperty.get();
        }

        @Override
        public E next() {
            indexProperty.set(nextIndex());
            E element = list.get(indexProperty.get());
            elementProperty.setValue(element);
            return element;
        }

        @Override
        public int nextIndex() {
            checkForComodification();
            int index = indexProperty.get();
            return (++index == list.size() ? 0 : index);
        }

        @Override
        public E previous() {
            indexProperty.set(previousIndex());
            E element = list.get(indexProperty.get());
            elementProperty.setValue(element);
            return element;
        }

        @Override
        public int previousIndex() {
            checkForComodification();
            int index = indexProperty.get();
            return ((--index == -1) ? list.size() - 1 : index);
        }

        private void checkForComodification() {
            if (listSize != list.size()) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        public IntegerProperty indexProperty() {
            return indexProperty;
        }

        @Override
        public Property<E> elementProperty() {
            return elementProperty;
        }
    }

    private static class DefaultCircularListCursor<E> extends CircularListCursor<E> {
        private final List<E> list;
        private final int listSize;
        private final IntegerProperty indexProperty;
        private final Property<E> elementProperty;

        private ListIterator<E> listIterator;
        private E element;

        private DefaultCircularListCursor(final List<E> list) {
            this.list = list;
            this.listSize = list.size();
            this.listIterator = list.listIterator();
            this.element = listIterator.next();
            this.indexProperty = new SimpleIntegerProperty(listIterator.previousIndex());
            listIterator.previous();
            this.elementProperty = new SimpleObjectProperty<>(getCurrent());
        }

        @Override
        public E getCurrent() {
            checkForComodification();
            return element;
        }

        @Override
        public int getCurrentIndex() {
            checkForComodification();
            return indexProperty.get();
        }

        @Override
        public E next() {
            checkForComodification();
            return safeNext();
        }

        private E safeNext() {
            if (listIterator.hasNext()) {
                indexProperty.set(listIterator.nextIndex());
                element = listIterator.next();
                elementProperty.setValue(element);
                return element;
            }
            listIterator = list.listIterator();
            return safeNext();
        }

        @Override
        public int nextIndex() {
            checkForComodification();
            int index = indexProperty.get();
            return (++index == list.size() ? 0 : index);
        }

        @Override
        public E previous() {
            checkForComodification();
            return safePrevious();
        }

        private E safePrevious() {
            if (listIterator.hasPrevious()) {
                indexProperty.set(listIterator.previousIndex());
                element = listIterator.previous();
                elementProperty.setValue(element);
                return element;
            }
            listIterator = list.listIterator(list.size());
            return safePrevious();
        }

        @Override
        public int previousIndex() {
            checkForComodification();
            int index = indexProperty.get();
            return ((--index == -1) ? list.size() - 1 : index);
        }

        private void checkForComodification() {
            if (listSize != list.size()) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        public IntegerProperty indexProperty() {
            return indexProperty;
        }

        @Override
        public Property<E> elementProperty() {
            return elementProperty;
        }
    }
}

I use it for example like this in practice (lots of irrelevant example code stripped down):

public class TemplateInvoiceController implements Initializable {
    ...
    private List<SelectionData> selectionDataList = new LinkedList<>();
    private CircularListCursor<SelectionData> selectionDataCursor;
    ...
    @Override
    public void initialize(final URL url, final ResourceBundle resourceBundle) {
        selectionDataList.add(new SelectionData(invoiceNumberLabel, invoiceNumberImageView));
        selectionDataList.add(new SelectionData(invoiceDateLabel, invoiceDateImageView));
        selectionDataList.add(new SelectionData(priceExclVatLabel, priceExclVatImageView));
        selectionDataList.add(new SelectionData(lowVatLabel, lowVatImageView));
        selectionDataList.add(new SelectionData(highVatLabel, highVatImageView));
        selectionDataList.add(new SelectionData(priceInclVatLabel, priceInclVatImageView));

        selectionDataCursor = CircularListCursor.of(selectionDataList);

        selectionDataCursor.elementProperty().getValue().getLabel().setStyle("-fx-text-fill: red; -fx-font-weight: bold");
        selectionDataCursor.elementProperty().addListener((observableValue, oldValue, newValue) -> {
            oldValue.getLabel().setStyle("-fx-text-fill: black; -fx-font-weight: normal");
            newValue.getLabel().setStyle("-fx-text-fill: red; -fx-font-weight: bold");

            GraphicsContext graphicsContext = selectionCanvas.getGraphicsContext2D();
            graphicsContext.clearRect(0d, 0d, selectionCanvas.getWidth(), selectionCanvas.getHeight());
            graphicsContext.setStroke(Paint.valueOf(Color.RED.toString()));
            graphicsContext.strokeRect(newValue.getStartX(), newValue.getStartY(), newValue.getWidth(), newValue.getHeight());
        });
        ...
    }
    ...
}

Working together with:

public void registerSceneListeners() {
    templateController.getPrimaryStage().getScene().addEventFilter(KeyEvent.KEY_PRESSED, keyEvent -> {
        if (keyEvent.getCode() == KeyCode.TAB) {
            if (keyEvent.isShiftDown()) {
                selectionDataCursor.previous();
            }
            else {
                selectionDataCursor.next();
            }
        }
    });
}

I'd like a full review of my CircularListCursor class.

Community · Accepted Answer · 2020-06-10 13:24:26Z

Empty Lists

    if (list.isEmpty()) {
        throw new IllegalArgumentException("list cannot be empty");
    }

Yuck ... you should be able to handle an empty list more gracefully than that. Creating a special EmptyCircularListCursor instance perhaps.

Random Access

I like that you differentiate between RandomAccess and other lists. This is a good thing.

public indexProperty()

By exposing this, and the indexElement, you are allowing people to completely mess up your data. They can change the indexProperty, and not the elementProperty, and now you have corruption.

Co-Modification

Your checkForCoModification method is not reliable. A list.add(xxx) followed by a list.remove(yyy) will result in a regular Iterator throwing a ConcurrentModificationException, but, your code does not. To implement fail-fast co-modification behaviour, you need access to internals of the List that are not public.

next, current & previous

This is a broken concept.... I don't like it. You have access to three methods that may, or may not, all return the same value.... a single-element list will have all three produce the same results.

I would expect that you have to move the cursor before you can access the content.

Additionally, there is no way to easily loop through this structure.... How would I visit each member exactly once?

while (....????) {
}

Fundamentally, I think, you have solved a problem that does not exist, and your solution does not behave as I would expect. Your use-case could just as easily be solved with a ListIterator

Update:

Since these lists tend to be small, I would simply leverage the existing toArray implementation in the underlying list, and provide a thin wrapper that is not a general concept:

import java.util.Arrays;

public class CircularView<T> {

    private final T[] data;
    private int cursor = 0;
    
    public CircularView(T...data) {
        this.data = Arrays.copyOf(data, data.length);
        this.cursor = 0;
    }
    
    public T current() {
        return cursor >= data.length ? null : data[cursor];
    }

    public void forward() {
        if (data.length > 0) {
            cursor = (cursor + 1) % data.length;
        }
    }

    public void backward() {
        if (data.length > 0) {
           cursor = (cursor + data.length - 1) % data.length;
        }
    }
}

You can then spin around that array in easy ways, and you're good.

Using a proper mathematical modulo you can index into an array as if it's circular: cursor = (step % size + size) % size; — Alex Shroyer
– Alex Shroyer, Commented Aug 12, 2014 at 15:36
@hoosierEE cursor = (step + size) % size; would be better, the first modulo is not necessary. — Simon Forsberg
– Simon Forsberg, Commented Aug 12, 2014 at 16:32
@hoosierEE - the double-% operation is useful if the 'step' is far outside (on the negative end of) the range of negative size to positive size. In this case, cursor will never be less than 0, so (cursor + data.length - 1) % data.length will always be safe. — rolfl
– rolfl, Commented Aug 12, 2014 at 16:38

Stack Exchange Network

CircularListCursor - an efficient circular cursor on any list

1 Answer 1

Empty Lists

Random Access

public indexProperty()

Co-Modification

next, current & previous

Update:

You must log in to answer this question.

Linked

Hot Network Questions

CircularListCursor - an efficient circular cursor on any list

1 Answer 1

Empty Lists

Random Access

public indexProperty()

Co-Modification

next, current & previous

Update:

You must log in to answer this question.

Linked

Related

Hot Network Questions