У меня есть структура данных двусвязного списка, в которой выполняются все одноэлементные операции в $ Theta ( sqrt {n}) $ время (см. эта почта а также этот репозиторий).
(См. Это для тестов.)
(См. Это для модульного тестирования.)
Планирую отправить его в один из двух проектов:
- OpenJDK; заменить
java.util.LinkedListс моими реализациями того же интерфейса (ов), - Коллекции Apache Commons 4; для дополнения списков.
Запрос на критику
Прежде чем отправить его в два проекта, мне нужно убедиться, что я использую зрелый код OpenJDK / Apache Commons. Расскажите мне обо всем, что придет в голову: СУХОЙ, ТВЕРДЫЙ и т. Д.
Код
Вот оно:
package com.github.coderodde.util;
import java.util.AbstractSequentialList;
import java.util.Arrays;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.Spliterator;
import java.util.function.Consumer;
/**
*
* @author Rodion Efremov
* @see List
* @see ArrayList
* @see java.util.LinkedList
* @since 17
* @param <E> the type of elements held in this collection
*/
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
/**
* Number of elements in the list.
*/
private int size = 0;
/**
* Pointer to first node.
*/
private transient Node<E> first;
/**
* Pointer to last node.
*/
private transient Node<E> last;
/**
* Stack of fingers.
*/
private transient FingerStack<E> fingerStack = new FingerStack<>();
/**
* Constructs an empty list.
*/
public LinkedList() {
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
/**
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #addLast}.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* Inserts the specified element at the specified position in this list.
* Shifts the element currently at that position (if any) and any
* subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index), index);
}
/**
* Appends all of the elements in the specified collection to the end of
* this list, in the order that they are returned by the specified
* collection's iterator. The behavior of this operation is undefined if
* the specified collection is modified while the operation is in
* progress. (Note that this will occur if the specified collection is
* this list, and it's nonempty.)
*
* @param c collection containing elements to be added to this list
* @return {@code true} if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
/**
* Inserts all of the elements in the specified collection into this
* list, starting at the specified position. Shifts the element
* currently at that position (if any) and any subsequent elements to
* the right (increases their indices). The new elements will appear
* in the list in the order that they are returned by the
* specified collection's iterator.
*
* @param index index at which to insert the first element
* from the specified collection
* @param c collection containing elements to be added to this list
* @return {@code true} if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
if (c.isEmpty())
return false;
if (size == 0)
setAll(c);
else if (index == 0)
prependAll(c);
else if (index == size)
appendAll(c);
else
insertAll(c, node(index), index);
return true;
}
/**
* Inserts the specified element at the beginning of this list.
*
* @param e the element to add
*/
public void addFirst(E e) {
linkFirst(e);
}
/**
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #add}.
*
* @param e the element to add
*/
public void addLast(E e) {
linkLast(e);
}
/**
* Removes all of the elements from this list.
* The list will be empty after this call returns.
*/
public void clear() {
fingerStack.clear();
size = 0;
// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
for (Node<E> node = first; node != null;) {
node.prev = null;
node.item = null;
Node<E> next = node.next;
node.next = null;
node = next;
}
first = last = null;
modCount++;
}
/**
* Returns {@code true} if this list contains the specified element.
* More formally, returns {@code true} if and only if this list contains
* at least one element {@code e} such that
* {@code Objects.equals(o, e)}.
*
* @param o element whose presence in this list is to be tested
* @return {@code true} if this list contains the specified element
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
/**
* @since 1.6
*/
@Override
public Iterator<E> descendingIterator() {
return new DescendingIterator();
}
/**
* Retrieves, but does not remove, the head (first element) of this list.
*
* @return the head of this list
* @throws NoSuchElementException if this list is empty
* @since 1.5
*/
@Override
public E element() {
return getFirst();
}
/**
* Returns {@code true} only if the input object is a {@link List}, has the
* same size, and whose iterator returns the elements in the same order as
* this list.
*
* @param o the query object.
* @return {@code true} only if this list and the input list represent the
* same element sequence.
*/
@Override
public boolean equals(Object o) {
if (o == null)
return false;
if (o == this)
return true;
if (!o.getClass().equals(o.getClass()))
return false;
List<?> otherList = (List<?>) o;
if (size != otherList.size())
return false;
Iterator<?> iterator1 = iterator();
Iterator<?> iterator2 = otherList.iterator();
while (iterator1.hasNext() && iterator2.hasNext()) {
Object object1 = iterator1.next();
Object object2 = iterator2.next();
if (!java.util.Objects.equals(object1, object2))
return false;
}
boolean iterator1HasMore = iterator1.hasNext();
boolean iterator2HasMore = iterator2.hasNext();
if (iterator1HasMore || iterator2HasMore)
throw new IllegalStateException(
iterator1HasMore ?
"This list has more elements to offer" :
"Argument list has more elements to offer");
return true;
}
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
/**
* Returns the first element in this list.
*
* @return the first element in this list
* @throws NoSuchElementException if this list is empty
*/
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
/**
* Returns the last element in this list.
*
* @return the last element in this list
* @throws NoSuchElementException if this list is empty
*/
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
/**
* Returns the smallest index of the input object, or -1, if the object does
* not appear in this list.
*
* @param o the object whose index to return.
* @return the index of {@code o}, or -1, if none is present.
*/
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next, index++) {
if (x.item == null)
return index;
}
} else {
for (Node<E> x = first; x != null; x = x.next, index++) {
if (o.equals(x.item))
return index;
}
}
return -1;
}
/**
* Returns the basic iterator over this list supporting only traversal and
* removal.
*
* @return the basic iterator.
*/
@Override
public Iterator<E> iterator() {
return new BasicIterator();
}
/**
* Returns the index of the last appearance of the input object {@code o}.
*
* @param o the object to search for.
* @return the largest index of {@code o}, or -1 if none is present.
*/
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
/**
* Returns a list-iterator of the elements in this list (in proper
* sequence), starting at the specified position in the list.
* Obeys the general contract of {@code List.listIterator(int)}.<p>
*
* The list-iterator is <i>fail-fast</i>: if the list is structurally
* modified at any time after the Iterator is created, in any way except
* through the list-iterator's own {@code remove} or {@code add}
* methods, the list-iterator will throw a
* {@code ConcurrentModificationException}. Thus, in the face of
* concurrent modification, the iterator fails quickly and cleanly, rather
* than risking arbitrary, non-deterministic behavior at an undetermined
* time in the future.
*
* @param index index of the first element to be returned from the
* list-iterator (by a call to {@code next})
* @return a ListIterator of the elements in this list (in proper
* sequence), starting at the specified position in the list
* @throws IndexOutOfBoundsException {@inheritDoc}
* @see List#listIterator(int)
*/
@Override
public ListIterator<E> listIterator(int index) {
return new EnhancedIterator(index);
}
/**
* Adds the specified element as the tail (last element) of this list.
*
* @param e the element to add
* @return {@code true} (as specified by {@link Queue#offer})
* @since 1.5
*/
@Override
public boolean offer(E e) {
return add(e);
}
/**
* Inserts the specified element at the front of this list.
*
* @param e the element to insert
* @return {@code true} (as specified by {@link Deque#offerFirst})
* @since 1.6
*/
@Override
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
/**
* Inserts the specified element at the end of this list.
*
* @param e the element to insert
* @return {@code true} (as specified by {@link Deque#offerLast})
* @since 1.6
*/
@Override
public boolean offerLast(E e) {
addLast(e);
return true;
}
/**
* Retrieves, but does not remove, the head (first element) of this list.
*
* @return the head of this list, or {@code null} if this list is empty
* @since 1.5
*/
@Override
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
/**
* Retrieves, but does not remove, the first element of this list,
* or returns {@code null} if this list is empty.
*
* @return the first element of this list, or {@code null}
* if this list is empty
* @since 1.6
*/
@Override
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
/**
* Retrieves, but does not remove, the last element of this list,
* or returns {@code null} if this list is empty.
*
* @return the last element of this list, or {@code null}
* if this list is empty
* @since 1.6
*/
@Override
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
/**
* Retrieves and removes the head (first element) of this list.
*
* @return the head of this list, or {@code null} if this list is empty
* @since 1.5
*/
@Override
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst();
}
/**
* Retrieves and removes the first element of this list,
* or returns {@code null} if this list is empty.
*
* @return the first element of this list, or {@code null} if
* this list is empty
* @since 1.6
*/
@Override
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst();
}
/**
* Retrieves and removes the last element of this list,
* or returns {@code null} if this list is empty.
*
* @return the last element of this list, or {@code null} if
* this list is empty
* @since 1.6
*/
@Override
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast();
}
/**
* Pops an element from the stack represented by this list. In other
* words, removes and returns the first element of this list.
*
* <p>This method is equivalent to {@link #removeFirst()}.
*
* @return the element at the front of this list (which is the top
* of the stack represented by this list)
* @throws NoSuchElementException if this list is empty
* @since 1.6
*/
@Override
public E pop() {
return removeFirst();
}
/**
* Pushes an element onto the stack represented by this list. In other
* words, inserts the element at the front of this list.
*
* <p>This method is equivalent to {@link #addFirst}.
*
* @param e the element to push
* @since 1.6
*/
@Override
public void push(E e) {
addFirst(e);
}
/**
* Retrieves and removes the head (first element) of this list.
*
* @return the head of this list
* @throws NoSuchElementException if this list is empty
* @since 1.5
*/
@Override
public E remove() {
return removeFirst();
}
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If this list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* {@code i} such that
* {@code Objects.equals(o, get(i))}
* (if such an element exists). Returns {@code true} if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return {@code true} if this list contained the specified element
*/
public boolean remove(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next, index++) {
if (x.item == null) {
removeNodeFromList(x, index);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next, index++) {
if (o.equals(x.item)) {
removeNodeFromList(x, index);
return true;
}
}
}
return false;
}
/**
* Removes the element residing at the given index.
* The procedure:
* 1. Find the node N to remove
* 2. If N is fingered by F, move F left/right
* 3. unlink(N)
*/
public E remove(int index) {
checkElementIndex(index);
// Loads the removeData!
loadRemoveData(index);
// Make sure that no finger is on our way pointing to the node to remove
if (removedDataFinger.index == index)
moveFingerOutOfRemovalLocation(removedDataFinger);
// Once here, the list is not empty and has at least one finger!
return unlink(removedDataNode, index);
}
/**
* Removes and returns the first element from this list.
*
* @return the first element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst();
}
/**
* Removes the first occurrence of the specified element in this
* list (when traversing the list from head to tail). If the list
* does not contain the element, it is unchanged.
*
* @param o element to be removed from this list, if present
* @return {@code true} if the list contained the specified element
* @since 1.6
*/
@Override
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}
/**
* Removes and returns the last element from this list.
*
* @return the last element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast();
}
/**
* Removes the last occurrence of the specified element in this
* list (when traversing the list from head to tail). If the list
* does not contain the element, it is unchanged.
*
* @param o element to be removed from this list, if present
* @return {@code true} if the list contained the specified element
* @since 1.6
*/
@Override
public boolean removeLastOccurrence(Object o) {
int index = size - 1;
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev, index--) {
if (x.item == null) {
unlink(x, index);
if (mustRemoveFinger())
removeFinger();
shiftIndicesToLeftOnce(index + 1);
return true;
}
}
} else {
for (Node<E> x = last; x != null; x = x.prev, index--) {
if (o.equals(x.item)) {
unlink(x, index);
if (mustRemoveFinger())
removeFinger();
shiftIndicesToLeftOnce(index + 1);
return true;
}
}
}
return false;
}
/**
* Returns the number of elements in this list.
*
* @return the number of elements in this list
*/
public int size() {
return size;
}
/**
* Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
* and <em>fail-fast</em> {@link Spliterator} over the elements in this
* list.
*
* <p>The {@code Spliterator} reports {@link Spliterator#SIZED} and
* {@link Spliterator#ORDERED}. Overriding implementations should document
* the reporting of additional characteristic values.
*
* @implNote
* The {@code Spliterator} additionally reports {@link Spliterator#SUBSIZED}
* and implements {@code trySplit} to permit limited parallelism..
*
* @return a {@code Spliterator} over the elements in this list
* @since 1.8
*/
@Override
public Spliterator<E> spliterator() {
return new LinkedListSpliterator<E>(this, first, size, 0, modCount);
}
@java.io.Serial
private static final long serialVersionUID = -8812077630522402934L;
// Internal implementation methods begin:
private void addFinger(Node<E> node, int index) {
final Finger<E> finger = new Finger<>(node, index);
fingerStack.push(finger);
}
private void addFingersAfterAppendAll(
Node<E> first,
int firstIndex,
int collectionSize) {
final int numberOfNewFingers =
getRecommendedNumberOfFingers() - fingerStack.size();
if (numberOfNewFingers == 0)
return;
final int distanceBetweenFingers = collectionSize / numberOfNewFingers;
final int nodesToSkip = distanceBetweenFingers / 2;
int index = firstIndex + nodesToSkip;
Node<E> node = first;
for (int i = 0; i < nodesToSkip; i++)
node = node.next;
addFinger(node, index);
for (int i = 1; i < numberOfNewFingers; i++) {
index += distanceBetweenFingers;
for (int j = 0; j < distanceBetweenFingers; j++) {
node = node.next;
}
addFinger(node, index);
}
}
private void addFingersAfterInsertAll(Node<E> headNodeOfInsertedRange,
int indexOfInsertedRangeHead,
int collectionSize) {
final int numberOfNewFingers =
getRecommendedNumberOfFingers() - fingerStack.size();
if (numberOfNewFingers == 0)
return;
final int distanceBetweenFingers = collectionSize / numberOfNewFingers;
final int startOffset = distanceBetweenFingers / 2;
int index = indexOfInsertedRangeHead + startOffset;
Node<E> node = headNodeOfInsertedRange;
for (int i = 0; i < startOffset; i++)
node = node.next;
addFinger(node, index);
for (int i = 1; i < numberOfNewFingers; i++) {
index += distanceBetweenFingers;
for (int j = 0; j < distanceBetweenFingers; j++)
node = node.next;
addFinger(node, index);
}
}
private void addFingersAfterPrependAll(Node<E> first, int collectionSize) {
final int numberOfNewFingers =
getRecommendedNumberOfFingers() - fingerStack.size();
if (numberOfNewFingers == 0)
return;
final int distance = collectionSize / numberOfNewFingers;
final int startIndex = distance / 2;
int index = startIndex;
Node<E> node = first;
for (int i = 0; i < startIndex; i++)
node = node.next;
addFinger(node, index);
for (int i = 1; i < numberOfNewFingers; i++) {
index += distance;
for (int j = 0; j < distance; j++)
node = node.next;
addFinger(node, index);
}
}
private void addFingersAfterSetAll() {
final int numberOfNewFingers = getRecommendedNumberOfFingers();
if (numberOfNewFingers == 0)
return;
final int distance = size / numberOfNewFingers;
final int startIndex = distance / 2;
int index = startIndex;
Node<E> node = first;
for (int i = 0; i < startIndex; i++)
node = node.next;
addFinger(node, startIndex);
for (int i = 1; i < numberOfNewFingers; i++) {
index += distance;
for (int j = 0; j < distance; j++)
node = node.next;
addFinger(node, index);
}
}
private void appendAll(Collection<? extends E> c) {
Node<E> prev = last;
final Node<E> oldLast = last;
for (E item : c) {
Node<E> newNode = new Node<>();
newNode.item = item;
newNode.prev = prev;
prev.next = newNode;
prev = newNode;
}
last = prev;
int sz = c.size();
size += sz;
modCount++;
addFingersAfterAppendAll(oldLast.next, size - sz, sz);
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(getOutOfBoundsMessage(index));
}
public void checkInvariant() {
for (int i = 0, sz = fingerStack.size(); i < sz; i++) {
Finger<E> finger = fingerStack.get(i);
Node<E> node = getNodeRaw(finger.index);
if (finger.node != node)
throw new AssertionError(
"checkInvariant() failed at finger index (" +
finger.index + "), expected node = " +
finger.node + ", actual node = " + node);
}
}
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(getOutOfBoundsMessage(index));
}
private Finger<E> getClosestFinger(int index) {
int bestDistance = Integer.MAX_VALUE;
Finger<E> bestFinger = null;
for (int sz = fingerStack.size(), i = 0; i < sz; i++) {
Finger<E> finger = fingerStack.get(i);
int distance = Math.abs(finger.index - index);
if (distance == 0)
return finger;
if (bestDistance > distance) {
bestDistance = distance;
bestFinger = finger;
}
}
return bestFinger;
}
private Node<E> getNodeRaw(int index) {
Node<E> node = first;
for (int i = 0; i < index; i++)
node = node.next;
return node;
}
private String getOutOfBoundsMessage(int index) {
return "Index: " + index + ", Size: " + size;
}
private int getRecommendedNumberOfFingers() {
return (int) Math.ceil(Math.sqrt(size / 2.0));
}
/***************************************************************************
Computes the recommended number of fingers for {@code size} elements.
***************************************************************************/
private static int getRecommendedNumberOfFingers(int size) {
return (int) Math.ceil(Math.sqrt(size / 2.0));
}
/***************************************************************************
Inserts the input collection right before the node 'succ'.
***************************************************************************/
private void insertAll(
Collection<? extends E> c,
Node<E> succ,
int succIndex) {
final Node<E> pred = succ.prev;
Node<E> prev = pred;
for (E item : c) {
final Node<E> newNode = new Node<>();
newNode.item = item;
newNode.prev = prev;
prev.next = newNode;
prev = newNode;
}
prev.next = succ;
succ.prev = prev;
int sz = c.size();
modCount++;
size += sz;
// Shift all the fingers positions past the 'succ' on the right 'sz'
// positions to the right:
shiftIndicesToRight(succIndex, sz);
// 0 1 |10 11 12| 3 4 5 6 7 8 9
// Add fingers:
addFingersAfterInsertAll(pred.next, succIndex, sz);
}
/***************************************************************************
Tells if the argument is the index of an existing element.
***************************************************************************/
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
/***************************************************************************
Tells if the argument is the index of a valid position for an iterator or an
add operation.
***************************************************************************/
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}
/***************************************************************************
Links the input element right before the node 'succ'.
***************************************************************************/
private void linkBefore(E e, Node<E> succ, int index) {
shiftIndicesToRightOnce(index);
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>();
newNode.item = e;
newNode.next = succ;
succ.prev = newNode;
if (pred == null) {
first = newNode;
} else {
pred.next = newNode;
newNode.prev = pred;
}
size++;
modCount++;
if (mustAddFinger())
addFinger(newNode, index);
}
/***************************************************************************
Prepends the input element to the head of this list.
***************************************************************************/
private void linkFirst(E e) {
shiftIndicesToRightOnce(0);
final Node<E> f = first;
final Node<E> newNode = new Node<>();
newNode.item = e;
newNode.next = f;
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
if (mustAddFinger())
addFinger(newNode, 0);
}
/***************************************************************************
Appends the input element to the tail of this list.
***************************************************************************/
private void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>();
newNode.item = e;
newNode.prev = l;
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
if (mustAddFinger())
addFinger(newNode, size - 1);
}
/***************************************************************************
Loads the removal operation related data.
***************************************************************************/
private void loadRemoveData(int index) {
Finger<E> finger = getClosestFinger(index);
Node<E> node = finger.node;
if (index < finger.index) {
final int distance = finger.index - index;
for (int i = 0; i < distance; i++)
node = node.prev;
} else {
final int distance = index - finger.index;
for (int i = 0; i < distance; i++)
node = node.next;
}
removedDataFinger = finger;
removedDataNode = node;
}
/***************************************************************************
Returns a finger that does not point to the element to remove. We need this
in order to make sure that after removal, all the fingers point to valid
nodes.
***************************************************************************/
private void moveFingerOutOfRemovalLocation(Finger<E> finger) {
if (size == 1) {
fingerStack.pop();
return;
}
if (finger.node.prev != null) {
// Move the finger one position to the left:
finger.node = finger.node.prev;
finger.index--;
return;
}
if (finger.node.next != null) {
// Move the finger one position to the right:
finger.node = finger.node.next;
finger.index++;
return;
}
throw new IllegalStateException("Removing from an empty list.");
}
/***************************************************************************
Returns true only if this list requires more fingers.
***************************************************************************/
private boolean mustAddFinger() {
// Here, fingerStack.size() == getRecommendedFingerCount(), or,
// fingerStack.size() == getRecommendedFingerCount() - 1
return fingerStack.size() != getRecommendedNumberOfFingers();
}
/***************************************************************************
Returns true only if this list requires less fingers.
/***************************************************************************
***************************************************************************/
private boolean mustRemoveFinger() {
// Here, fingerStack.size() == getRecommendedFingerCount(), or,
// fingerStack.size() == getRecommendedFingerCount() + 1
return fingerStack.size() != getRecommendedNumberOfFingers();
}
/***************************************************************************
Returns the node at index 'index'. Moves the closest finger to the node.
***************************************************************************/
private Node<E> node(int index) {
Finger<E> finger = getClosestFinger(index);
int distance = finger.index - index;
if (distance > 0)
finger.rewindLeft(distance);
else
finger.rewindRight(-distance);
return finger.node;
}
/***************************************************************************
Prepends the input collection to the head of this list.
***************************************************************************/
private void prependAll(Collection<? extends E> c) {
Iterator<? extends E> iterator = c.iterator();
final Node<E> oldFirst = first;
first = new Node<>();
first.item = iterator.next();
Node<E> prevNode = first;
for (int i = 1, sz = c.size(); i < sz; i++) {
Node<E> newNode = new Node<>();
newNode.item = iterator.next();
newNode.prev = prevNode;
prevNode.next = newNode;
prevNode = newNode;
}
prevNode.next = oldFirst;
oldFirst.prev = prevNode;
int sz = c.size();
modCount++;
size += sz;
// Prior to adding new (possible) fingers, we need to shift all the
// current fingers 'c.size()' nodes to the larger index values:
shiftIndicesToRight(0, sz);
// Now, add the missing fingers:
addFingersAfterPrependAll(first, sz);
}
private void removeFinger() {
fingerStack.pop();
}
private E removeNodeFromList(Node<E> node, int index) {
loadRemoveData(index);
if (removedDataFinger.index == index)
moveFingerOutOfRemovalLocation(removedDataFinger);
return unlink(node, index);
}
/***************************************************************************
Sets the input collection as a list.
***************************************************************************/
private void setAll(Collection<? extends E> c) {
Iterator<? extends E> iterator = c.iterator();
first = new Node<>();
first.item = iterator.next();
Node<E> prevNode = first;
for (int i = 1, sz = c.size(); i < sz; i++) {
Node<E> newNode = new Node<>();
newNode.item = iterator.next();
prevNode.next = newNode;
newNode.prev = prevNode;
prevNode = newNode;
}
last = prevNode;
int sz = c.size();
modCount++;
size += sz;
addFingersAfterSetAll();
}
/***************************************************************************
Subtracts 'steps' positions from each index at least 'startingIndex'.
***************************************************************************/
private void shiftIndicesToLeft(int startingIndex, int steps) {
for (int i = 0, sz = fingerStack.size; i < sz; i++) {
Finger<E> finger = fingerStack.get(i);
if (finger.index >= startingIndex)
finger.index -= steps; // substract from index
}
}
/***************************************************************************
Shifts all the indices at least 'startingIndex' one position towards smaller
index values.
***************************************************************************/
private void shiftIndicesToLeftOnce(int startingIndex) {
shiftIndicesToLeft(startingIndex, 1);
}
/***************************************************************************
For each finger with the index at least 'startIndex', add 'steps' to the
index.
***************************************************************************/
private void shiftIndicesToRight(int startIndex, int steps) {
for (int sz = fingerStack.size(), i = 0; i < sz; i++) {
Finger<E> finger = fingerStack.get(i);
if (finger.index >= startIndex)
finger.index += steps;
}
}
/***************************************************************************
Shifts all the indices at least 'startingIndex' one position towards larger
index values.
***************************************************************************/
private void shiftIndicesToRightOnce(int startingIndex) {
shiftIndicesToRight(startingIndex, 1);
}
/***************************************************************************
Unlinks the input node and adjusts the fingers.
***************************************************************************/
private E unlink(Node<E> x, int index) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
if (mustRemoveFinger())
removeFinger();
shiftIndicesToLeftOnce(index + 1);
return element;
}
/***************************************************************************
Unlinks the head node from this list.
***************************************************************************/
private E unlinkFirst() {
shiftIndicesToLeftOnce(1);
final E element = first.item;
final Node<E> next = first.next;
first.item = null;
first.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
if (mustRemoveFinger())
fingerStack.pop();
return element;
}
/***************************************************************************
Unlinks the tail node from this list.
***************************************************************************/
private E unlinkLast() {
final E element = last.item;
final Node<E> prev = last.prev;
last.item = null;
last.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
if (mustRemoveFinger())
fingerStack.pop();
return element;
}
// Caches the removal data:
private transient Node<E> removedDataNode;
private transient Finger<E> removedDataFinger;
/**
* Reconstitutes this {@code LinkedList} instance from a stream
* (that is, deserializes it).
*/
@java.io.Serial
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// Read in any hidden serialization magic
s.defaultReadObject();
int size = s.readInt();
this.size = size;
this.fingerStack = new FingerStack<>();
switch (size) {
case 0:
return;
case 1:
Node<E> newNode = new Node<>();
newNode.item = (E) s.readObject();
first = last = newNode;
addFinger(newNode, 0);
return;
}
Node<E> rightmostNode = new Node<>();
rightmostNode.item = (E) s.readObject();
first = rightmostNode;
int numberOfRequestedFingers = getRecommendedNumberOfFingers(size);
final int distance = size / numberOfRequestedFingers;
int startOffset = distance / 2;
// Read in all elements in the proper order.
for (int i = 1; i < size; i++) {
E item = (E) s.readObject();
Node<E> node = new Node<>();
node.item = item;
if ((i - startOffset) % distance == 0) {
addFinger(node, i);
}
rightmostNode.next = node;
node.prev = rightmostNode;
rightmostNode = node;
}
last = rightmostNode;
}
/**
* Saves the state of this {@code LinkedList} instance to a stream
* (that is, serializes it).
*
* @serialData The size of the list (the number of elements it
* contains) is emitted (int), followed by all of its
* elements (each an Object) in the proper order.
*/
@java.io.Serial
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// Write out any hidden serialization magic
s.defaultWriteObject();
// Write out size
s.writeInt(size);
// Write out all elements in the proper order.
for (Node<E> x = first; x != null; x = x.next)
s.writeObject(x.item);
}
/***************************************************************************
Implements the doubly-linked list node.
***************************************************************************/
private static class Node<E> {
E item;
Node<E> prev;
Node<E> next;
@Override
public String toString() {
return "[Node; item = " + item + "]";
}
}
/***************************************************************************
Implements the list node finger.
***************************************************************************/
private static final class Finger<E> {
Node<E> node;
int index; // Index at which 'node' is located.
Finger(Node<E> node, int index) {
this.node = node;
this.index = index;
}
@Override
public String toString() {
return "[Finger; index = " + index + ", item = " + node.item + "]";
}
// Moves this finger 'steps' position to the left
void rewindLeft(int steps) {
for (int i = 0; i < steps; i++) {
node = node.prev;
}
index -= steps;
}
// Moves this finger 'steps' position to the right
void rewindRight(int steps) {
for (int i = 0; i < steps; i++) {
node = node.next;
}
index += steps;
}
}
/***************************************************************************
Implements a simple, array-based stack for storing the node fingers.
@param <E> the list element type
***************************************************************************/
private static final class FingerStack<E> {
private static final int INITIAL_CAPACITY = 8;
private Finger<E>[] fingerArray;
private int size = 0;
FingerStack() {
this.fingerArray = new Finger[INITIAL_CAPACITY];
}
void push(Finger<E> finger) {
enlargeFingerArrayIfNeeded();
fingerArray[size++] = finger;
}
void pop() {
fingerArray[--size] = null;
}
int size() {
return size;
}
Finger<E> get(int index) {
return fingerArray[index];
}
// Clears this finger stack:
void clear() {
for (int i = 0; i < size; i++) {
fingerArray[i].node = null; // help GC
fingerArray[i] = null;
}
size = 0;
}
// Makes sure that the next finger fits in this finger stack:
private void enlargeFingerArrayIfNeeded() {
if (size == fingerArray.length) {
final int nextCapacity = 3 * fingerArray.length / 2;
fingerArray = Arrays.copyOf(fingerArray, nextCapacity);
}
}
}
/***************************************************************************
This class implements a basic iterator over this list.
@param E the element type.
***************************************************************************/
private final class BasicIterator implements Iterator<E> {
private Node<E> lastReturned;
private Node<E> next = first;
private int nextIndex;
private int expectedModCount = modCount;
@Override
public boolean hasNext() {
return nextIndex < size;
}
@Override
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
@Override
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
int removalIndex = nextIndex - 1;
//checkInvariant();
loadRemoveData(removalIndex);
if (removedDataFinger.index == removalIndex)
moveFingerOutOfRemovalLocation(removedDataFinger);
unlink(lastReturned, removalIndex);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
@Override
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (modCount == expectedModCount && nextIndex < size) {
action.accept(next.item);
lastReturned = next;
next = next.next;
nextIndex++;
}
checkForComodification();
}
private final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
/***************************************************************************
Implements the list iterator over this list.
***************************************************************************/
private final class EnhancedIterator implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
EnhancedIterator(int index) {
next = (index == size) ? null : node(index);
nextIndex = index;
}
@Override
public boolean hasNext() {
return nextIndex < size;
}
@Override
public E next() {
checkForComdification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
@Override
public boolean hasPrevious() {
return nextIndex > 0;
}
@Override
public E previous() {
checkForComdification();
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}
@Override
public int nextIndex() {
return nextIndex;
}
@Override
public int previousIndex() {
return nextIndex - 1;
}
@Override
public void remove() {
checkForComdification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
int removalIndex = nextIndex - 1;
loadRemoveData(removalIndex);
if (removedDataFinger.index == removalIndex)
moveFingerOutOfRemovalLocation(removedDataFinger);
unlink(lastReturned, removalIndex);
if (next == lastReturned)
next = lastNext;
else
nextIndex = removalIndex;
lastReturned = null;
expectedModCount++;
}
@Override
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComdification();
lastReturned.item = e;
}
@Override
public void add(E e) {
checkForComdification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next, nextIndex);
nextIndex++;
expectedModCount++;
}
@Override
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (modCount == expectedModCount && nextIndex < size) {
action.accept(next.item);
lastReturned = next;
next = next.next;
nextIndex++;
}
checkForComdification();
}
private final void checkForComdification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
private final class DescendingIterator implements Iterator<E> {
private final ListIterator<E> iterator = new EnhancedIterator(size());
@Override
public boolean hasNext() {
return iterator.hasPrevious();
}
@Override
public E next() {
return iterator.previous();
}
@Override
public void remove() {
iterator.remove();
}
}
private static final class LinkedListSpliterator<E>
implements Spliterator<E> {
private static final long MINIMUM_BATCH_SIZE = 1 << 10; // 1024 items
private final LinkedList<E> list;
private LinkedList.Node<E> node;
private long lengthOfSpliterator;
private long numberOfProcessedElements;
private long offsetOfSpliterator;
private final int expectedModCount;
private LinkedListSpliterator(LinkedList<E> list,
Node<E> node,
long lengthOfSpliterator,
long offsetOfSpliterator,
int expectedModCount) {
this.list = list;
this.node = node;
this.lengthOfSpliterator = lengthOfSpliterator;
this.offsetOfSpliterator = offsetOfSpliterator;
this.expectedModCount = expectedModCount;
}
@Override
public boolean tryAdvance(Consumer<? super E> action) {
if (action == null) throw new NullPointerException();
if (numberOfProcessedElements == lengthOfSpliterator)
return false;
numberOfProcessedElements++;
E item = node.item;
action.accept(item);
node = node.next;
if (list.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
@Override
public void forEachRemaining(Consumer<? super E> action) {
if (action == null) throw new NullPointerException();
for (long i = numberOfProcessedElements;
i < lengthOfSpliterator;
i++) {
E item = node.item;
action.accept(item);
node = node.next;
}
numberOfProcessedElements = lengthOfSpliterator;
if (list.modCount != expectedModCount)
throw new ConcurrentModificationException();
}
@Override
public Spliterator<E> trySplit() {
final long sizeLeft = estimateSize();
if (sizeLeft == 0)
return null;
final long thisSpliteratorNewLength = sizeLeft / 2L;
if (thisSpliteratorNewLength < MINIMUM_BATCH_SIZE)
return null;
final long newSpliteratorLength =
sizeLeft - thisSpliteratorNewLength;
final long newSpliteratorOffset = this.offsetOfSpliterator;
this.offsetOfSpliterator += newSpliteratorLength;
this.lengthOfSpliterator -= newSpliteratorLength;
Node<E> newSpliteratorNode = this.node;
this.node = list.node((int) this.offsetOfSpliterator);
return new LinkedListSpliterator<>(
list,
newSpliteratorNode,
newSpliteratorLength, // length
newSpliteratorOffset, // offset
expectedModCount);
}
@Override
public long estimateSize() {
return (long)(lengthOfSpliterator - numberOfProcessedElements);
}
@Override
public long getExactSizeIfKnown() {
return estimateSize();
}
@Override
public int characteristics() {
return Spliterator.ORDERED |
Spliterator.SUBSIZED |
Spliterator.SIZED;
}
@Override
public boolean hasCharacteristics(int characteristics) {
switch (characteristics) {
case Spliterator.ORDERED:
case Spliterator.SIZED:
case Spliterator.SUBSIZED:
return true;
default:
return false;
}
}
}
}