IndexedLinkedList.java - A fast list data structure for large data, Take II/V (package private API)

Question

Intro

This post is the continuation of the IndexedLinkedList series. It presents the package private API:

---

Code

public class IndexedLinkedList<E> implements Deque<E>, 
 List<E>, 
 Cloneable, 
 java.io.Serializable {
 /**
 * Implements the batch remove. If {@code complement} is {@code true}, this 
 * operation removes all the elements appearing in {@code c}. Otherwise, it 
 * will retain all the elements present in {@code c}.
 * 
 * @param c the target collection to operate on.
 * @param complement the operation choice flag.
 * @param from the starting, inclusive index of the range to consider.
 * @param end the ending, exclusive index of the range to consider.
 * 
 * @return {@code true} if and only if the list was modified.
 */
 boolean batchRemove(Collection<?> c,
 boolean complement,
 int from, 
 int end) {
 Objects.requireNonNull(c);
 
 if (c.isEmpty()) {
 // Once here, there is nothing to remove. Return false:
 return false;
 }
 
 boolean modified = false;
 
 // The number of nodes to process:
 int numberOfNodesToIterate = end - from;
 int i = 0;
 int nodeIndex = from;
 
 for (Node<E> node = getNode(from); i < numberOfNodesToIterate; ++i) {
 Node<E> nextNode = node.next;
 
 if (c.contains(node.item) == complement) {
 // Once here, we have a match. Remove it and mark 'modified' as
 // 'true':
 modified = true;
 removeObjectImpl(node, nodeIndex);
 } else {
 // Omit the element. We need this in order for 
 // 'removeObjectImpl(node, nodeIndex)' to work properly:
 nodeIndex++;
 }
 
 node = nextNode;
 }
 
 return modified;
 }
 /**
 * Checks that the input {@code expectedModCount} equals the list's 
 * internal, cached modification count.
 * 
 * @param expectedModCount the modification count to check.
 * @throws ConcurrentModificationException if the cached and the input 
 * modification counts differ.
 */
 void checkForComodification(int expectedModCount) {
 if (modCount != expectedModCount) {
 throw new ConcurrentModificationException();
 }
 }
 
 /**
 * Validates the range indices.
 * 
 * @param fromIndex the starting, inclusive index of the range.
 * @param toIndex the ending, exclusive index of the range.
 */
 void checkFromTo(int fromIndex, int toIndex) {
 if (fromIndex < 0) {
 throw new IndexOutOfBoundsException(
 String.format("fromIndex(%d) < 0", fromIndex));
 }
 
 if (toIndex > size) {
 throw new IndexOutOfBoundsException(
 String.format("toIndex(%d) > size(%d)", toIndex, size));
 }
 
 if (fromIndex > toIndex) {
 throw new IllegalArgumentException(
 String.format(
 "fromIndex(%d) > toIndex(%d)",
 fromIndex, 
 toIndex));
 }
 }
 
 /**
 * Checks that the input index is within correct bounds.
 * 
 * @param index the index to check.
 * @param size the size of the list.
 */
 static void checkIndex(int index, int size) {
 
 if (size < 0) {
 throw new IllegalArgumentException(
 String.format("size(%d) < 0", size));
 }
 
 if (index < 0) {
 throw new IndexOutOfBoundsException(
 String.format("index(%d) < 0", index));
 }
 
 if (index >= size) {
 throw new IndexOutOfBoundsException(
 String.format("index(%d) >= size(%d)", index, size));
 }
 }
 
 /**
 * Returns the number of fingers in the finger list. Does not count the 
 * end-of-finger-list sentinel finger. Used in unit tests.
 * 
 * @return the size of the finger list.
 */
 int getFingerListSize() {
 return fingerList.size();
 }
 
 /**
 * Accesses the {@code index}th node sequentially without relying on 
 * fingers. Used in {@link #randomizeFingers()}.
 * 
 * @param index the index of the desired node.
 * 
 * @return the {@code index}th node.
 */
 Node<E> getNodeSequentially(int index) {
 // This is the so called "nearest neighbor optimization":
 if (index < size / 2) {
 // Once here, 'index'th element is closer to the head node. Iterate
 // starting from the head node forward:
 Node<E> node = head;
 for (int i = 0; i < index; i++) {
 node = node.next;
 }
 return node;
 } else {
 // Once here, 'index'th element is closer to the tail node. Iterate
 // starting from the tail node backwards:
 Node<E> node = tail;
 
 for (int i = 0; i < size - 1 - index; i++) {
 node = node.prev;
 }
 
 return node;
 }
 }
 
 /**
 * Loads the two counters representing how much fingers we should push to 
 * left and how much fingers to push to right.
 * 
 * @param fromFingerIndex the lower finger index.
 * @param toFingerIndex the upper, exclusive finger index.
 * @param fromIndex the starting, inclusive element index of the
 * range.
 * @param toIndex the ending, exclusive element index of the range.
 * @param fingersToRemove the number of fingers to remove.
 */
 void loadFingerCoverageCounters(int fromFingerIndex,
 int toFingerIndex,
 int fromIndex,
 int toIndex,
 int fingersToRemove) {
 
 // Compute the number of fingers in the finger list prefix and suffix:
 int fingerPrefixLength = fromFingerIndex;
 int fingerSuffixLength = fingerList.size() - toFingerIndex;
 // Compute the lengths of elements in the acutual list prefix and suffx:
 int listPrefixFreeSpots = fromIndex;
 int listSuffixFreeSpots = size - toIndex;
 // Compute the number of free spots for fingers in both list prefix and
 // suffix:
 int freeFingerPrefixSpots = listPrefixFreeSpots
 - fingerPrefixLength;
 int freeFingerSuffixSpots = listSuffixFreeSpots 
 - fingerSuffixLength;
 // Compute the total number of free spots for fingers:
 int freeSpots = freeFingerPrefixSpots
 + freeFingerSuffixSpots;
 // Compute the ratio between free prefix finger spots and the toal 
 // number of free spots:
 float leftRatio = (float)(freeFingerPrefixSpots) / 
 (float)(freeSpots);
 // Compute the length of the finger list that will be removed:
 int removalRangeLength = toFingerIndex 
 - fromFingerIndex;
 
 // Compute the number of fingers left to distribute to the finger list
 // prefix/suffix:
 int remainingFingers = removalRangeLength
 - fingersToRemove;
 
 // Finally, compute the number of fingers going to prefix/suffix:
 int leftCoveredFingers = (int)(leftRatio * remainingFingers);
 int rightCoveredFingers = remainingFingers - leftCoveredFingers;
 this.numberOfCoveringFingersToPrefix = leftCoveredFingers;
 this.numberOfCoveringFingersToSuffix = rightCoveredFingers;
 }
 
 /**
 * Moves the {@code finger} out of the element with index 
 * {@code finger.index}.
 * 
 * @param finger the finger to move. 
 * @param fingerIndex the index of {@code finger}.
 */
 void moveFingerOutOfRemovalLocation(Finger<E> finger, int fingerIndex) {
 
 if (fingerList.size() == size()) {
 // Here, fingerList.size() is 1 or 2 and the size of the list is the
 // same:
 if (fingerList.size() == 1) {
 // The only finger will be removed in 'remove(int)'. Return:
 return;
 }
 
 if (fingerIndex == 0) {
 // Shift 2nd and the sentinal fingers one position to the
 // left:
 fingerList.setFinger(0, fingerList.getFinger(1));
 fingerList.getFinger(0).index = 0;
 fingerList.setFinger(1, fingerList.getFinger(2));
 fingerList.getFinger(1).index = 1;
 fingerList.setFinger(2, null);
 fingerList.size = 1;
 } else {
 // Here, fingerIndex == 1:
 // Just remove the (last) finger:
 fingerList.removeFinger();
 fingerList.getFinger(1).index = 1;
 } 
 
 return;
 }
 
 // Try push the fingers to the right:
 if (tryPushFingersToRight(fingerIndex)) {
 // Once here, pushing to the right was successful. Return:
 return;
 }
 
 // Could not push the fingers to the right. Try push to the left:
 if (tryPushFingersToLeft(fingerIndex)) {
 // Once here, pushing to the left was successful. Return:
 return;
 }
 
 // Once here, the only free spots are at the very beginning of the
 // finger list:
 for (int i = 0; i <= fingerIndex; ++i) {
 Finger<E> fngr = fingerList.getFinger(i);
 // Move 'fngr' one spot to the left:
 fngr.index--;
 fngr.node = fngr.node.prev;
 }
 
 // Fix the remaining indices:
 fingerList.shiftFingerIndicesToLeft(fingerIndex + 1, 1);
 }
 
 /**
 * Removes the list range {@code [fromIndex, ..., toIndex - 1]}.
 * 
 * @param fromIndex the staring, inclusive range index.
 * @param toIndex the ending, exclusive range index.
 */
 void removeRange(int fromIndex, int toIndex) {
 int removalLength = toIndex - fromIndex;
 
 if (removalLength == 0) {
 // Once here, nothing to remove:
 return;
 }
 
 if (removalLength == 1) {
 // Delegate to the single-element removal method:
 remove(fromIndex);
 return;
 }
 
 if (removalLength == size) {
 // Can simply clear all the contents:
 clear();
 return;
 }
 
 // Compute the bounding finger indices:
 int fromFingerIndex = fingerList.getFingerIndexImpl(fromIndex);
 int toFingerIndex = fingerList.getFingerIndexImpl(toIndex);
 
 // Compute the number of fingers to remove:
 int fingersToRemove = getRecommendedNumberOfFingers() 
 - getRecommendedNumberOfFingers(
 size - removalLength);
 
 // Load the end nodes of the actual range removal area:
 loadRemoveRangeEndNodes(fromIndex, 
 toIndex);
 
 // Do the actual finger list magic:
 removeRangeImpl(fromIndex, 
 toIndex,
 fromFingerIndex, 
 toFingerIndex, 
 fingersToRemove);
 // Unlink the actual nodes:
 unlinkNodeRange(this.removeRangeStartNode,
 this.removeRangeEndNode);
 modCount++;
 
 // Attempt to contract the finger array:
 fingerList.contractFingerArrayIfNeeded(size);
 }
 
 /**
 * Replaces all the elements from range {@code [i, end - 1]}.
 * 
 * @param operator the replacement operator.
 * @param i the starting, inclusive index of the range to replace.
 * @param end the ending, exclusive index of the range to replace.
 */
 void replaceAllRange(UnaryOperator<E> operator, int i, int end) {
 Objects.requireNonNull(operator); 
 int expectedModCount = modCount;
 Node<E> node = getNode(i);
 
 while (modCount == expectedModCount && i < end) {
 node.item = operator.apply(node.item);
 node = node.next;
 i++;
 }
 
 if (modCount != expectedModCount) {
 throw new ConcurrentModificationException();
 }
 }
 
 /**
 * Checks the indices for a list of size {@code size}.
 * 
 * @param fromIndex the starting, inclusive index.
 * @param toIndex the ending, exclusive index.
 * @param size the size of the target list.
 */
 static void subListRangeCheck(int fromIndex, 
 int toIndex, 
 int size) {
 if (fromIndex < 0) {
 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
 }
 if (toIndex > size){
 throw new IndexOutOfBoundsException(
 "toIndex(" + toIndex + ") > size(" + size + ")");
 }
 if (fromIndex > toIndex)
 throw new IllegalArgumentException(
 "fromIndex(" + fromIndex + ") > toIndex(" 
 + toIndex + ")");
 }
}

Critique

Please, tell me anything that comes to mind.