RefList.java
/*
* Copyright (C) 2010, Google Inc. and others
*
* This program and the accompanying materials are made available under the
* terms of the Eclipse Distribution License v. 1.0 which is available at
* https://www.eclipse.org/org/documents/edl-v10.php.
*
* SPDX-License-Identifier: BSD-3-Clause
*/
package org.eclipse.jgit.util;
import java.util.Arrays;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.function.BinaryOperator;
import java.util.stream.Collector;
import org.eclipse.jgit.annotations.Nullable;
import org.eclipse.jgit.lib.Ref;
import org.eclipse.jgit.lib.RefComparator;
/**
* Specialized variant of an ArrayList to support a {@code RefDatabase}.
* <p>
* This list is a hybrid of a Map<String,Ref> and of a List<Ref>. It
* tracks reference instances by name by keeping them sorted and performing
* binary search to locate an entry. Lookup time is O(log N), but addition and
* removal is O(N + log N) due to the list expansion or contraction costs.
* <p>
* This list type is copy-on-write. Mutation methods return a new copy of the
* list, leaving {@code this} unmodified. As a result we cannot easily implement
* the {@link java.util.List} interface contract.
*
* @param <T>
* the type of reference being stored in the collection.
*/
public class RefList<T extends Ref> implements Iterable<Ref> {
private static final RefList<Ref> EMPTY = new RefList<>(new Ref[0], 0);
/**
* Create an empty unmodifiable reference list.
*
* @return an empty unmodifiable reference list.
*/
@SuppressWarnings("unchecked")
public static <T extends Ref> RefList<T> emptyList() {
return (RefList<T>) EMPTY;
}
final Ref[] list;
final int cnt;
RefList(Ref[] list, int cnt) {
this.list = list;
this.cnt = cnt;
}
/**
* Initialize this list to use the same backing array as another list.
*
* @param src
* the source list.
*/
protected RefList(RefList<T> src) {
this.list = src.list;
this.cnt = src.cnt;
}
/** {@inheritDoc} */
@Override
public Iterator<Ref> iterator() {
return new Iterator<>() {
private int idx;
@Override
public boolean hasNext() {
return idx < cnt;
}
@Override
public Ref next() {
if (idx < cnt)
return list[idx++];
throw new NoSuchElementException();
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
};
}
/**
* Cast {@code this} as an immutable, standard {@link java.util.List}.
*
* @return {@code this} as an immutable, standard {@link java.util.List}.
*/
public final List<Ref> asList() {
final List<Ref> r = Arrays.asList(list).subList(0, cnt);
return Collections.unmodifiableList(r);
}
/**
* Get number of items in this list.
*
* @return number of items in this list.
*/
public final int size() {
return cnt;
}
/**
* Get if this list is empty.
*
* @return true if the size of this list is 0.
*/
public final boolean isEmpty() {
return cnt == 0;
}
/**
* Locate an entry by name.
*
* @param name
* the name of the reference to find.
* @return the index the reference is at. If the entry is not present
* returns a negative value. The insertion position for the given
* name can be computed from {@code -(index + 1)}.
*/
public final int find(String name) {
int high = cnt;
if (high == 0)
return -1;
int low = 0;
do {
final int mid = (low + high) >>> 1;
final int cmp = RefComparator.compareTo(list[mid], name);
if (cmp < 0)
low = mid + 1;
else if (cmp == 0)
return mid;
else
high = mid;
} while (low < high);
return -(low + 1);
}
/**
* Determine if a reference is present.
*
* @param name
* name of the reference to find.
* @return true if the reference is present; false if it is not.
*/
public final boolean contains(String name) {
return 0 <= find(name);
}
/**
* Get a reference object by name.
*
* @param name
* the name of the reference.
* @return the reference object; null if it does not exist in this list.
*/
public final T get(String name) {
int idx = find(name);
return 0 <= idx ? get(idx) : null;
}
/**
* Get the reference at a particular index.
*
* @param idx
* the index to obtain. Must be {@code 0 <= idx < size()}.
* @return the reference value, never null.
*/
@SuppressWarnings("unchecked")
public final T get(int idx) {
return (T) list[idx];
}
/**
* Obtain a builder initialized with the first {@code n} elements.
* <p>
* Copies the first {@code n} elements from this list into a new builder,
* which can be used by the caller to add additional elements.
*
* @param n
* the number of elements to copy.
* @return a new builder with the first {@code n} elements already added.
*/
public final Builder<T> copy(int n) {
Builder<T> r = new Builder<>(Math.max(16, n));
r.addAll(list, 0, n);
return r;
}
/**
* Obtain a new copy of the list after changing one element.
* <p>
* This list instance is not affected by the replacement. Because this
* method copies the entire list, it runs in O(N) time.
*
* @param idx
* index of the element to change.
* @param ref
* the new value, must not be null.
* @return copy of this list, after replacing {@code idx} with {@code ref} .
*/
public final RefList<T> set(int idx, T ref) {
Ref[] newList = new Ref[cnt];
System.arraycopy(list, 0, newList, 0, cnt);
newList[idx] = ref;
return new RefList<>(newList, cnt);
}
/**
* Add an item at a specific index.
* <p>
* This list instance is not affected by the addition. Because this method
* copies the entire list, it runs in O(N) time.
*
* @param idx
* position to add the item at. If negative the method assumes it
* was a direct return value from {@link #find(String)} and will
* adjust it to the correct position.
* @param ref
* the new reference to insert.
* @return copy of this list, after making space for and adding {@code ref}.
*/
public final RefList<T> add(int idx, T ref) {
if (idx < 0)
idx = -(idx + 1);
Ref[] newList = new Ref[cnt + 1];
if (0 < idx)
System.arraycopy(list, 0, newList, 0, idx);
newList[idx] = ref;
if (idx < cnt)
System.arraycopy(list, idx, newList, idx + 1, cnt - idx);
return new RefList<>(newList, cnt + 1);
}
/**
* Remove an item at a specific index.
* <p>
* This list instance is not affected by the addition. Because this method
* copies the entire list, it runs in O(N) time.
*
* @param idx
* position to remove the item from.
* @return copy of this list, after making removing the item at {@code idx}.
*/
public final RefList<T> remove(int idx) {
if (cnt == 1)
return emptyList();
Ref[] newList = new Ref[cnt - 1];
if (0 < idx)
System.arraycopy(list, 0, newList, 0, idx);
if (idx + 1 < cnt)
System.arraycopy(list, idx + 1, newList, idx, cnt - (idx + 1));
return new RefList<>(newList, cnt - 1);
}
/**
* Store a reference, adding or replacing as necessary.
* <p>
* This list instance is not affected by the store. The correct position is
* determined, and the item is added if missing, or replaced if existing.
* Because this method copies the entire list, it runs in O(N + log N) time.
*
* @param ref
* the reference to store.
* @return copy of this list, after performing the addition or replacement.
*/
public final RefList<T> put(T ref) {
int idx = find(ref.getName());
if (0 <= idx)
return set(idx, ref);
return add(idx, ref);
}
/** {@inheritDoc} */
@Override
public String toString() {
StringBuilder r = new StringBuilder();
r.append('[');
if (cnt > 0) {
r.append(list[0]);
for (int i = 1; i < cnt; i++) {
r.append(", "); //$NON-NLS-1$
r.append(list[i]);
}
}
r.append(']');
return r.toString();
}
/**
* Create a {@link Collector} for {@link Ref}.
*
* @param mergeFunction
* if specified the result will be sorted and deduped.
* @return {@link Collector} for {@link Ref}
* @since 5.4
*/
public static <T extends Ref> Collector<T, ?, RefList<T>> toRefList(
@Nullable BinaryOperator<T> mergeFunction) {
return Collector.of(
() -> new Builder<>(),
Builder<T>::add, (b1, b2) -> {
Builder<T> b = new Builder<>();
b.addAll(b1);
b.addAll(b2);
return b;
}, (b) -> {
if (mergeFunction != null) {
b.sort();
b.dedupe(mergeFunction);
}
return b.toRefList();
});
}
/**
* Builder to facilitate fast construction of an immutable RefList.
*
* @param <T>
* type of reference being stored.
*/
public static class Builder<T extends Ref> {
private Ref[] list;
private int size;
/** Create an empty list ready for items to be added. */
public Builder() {
this(16);
}
/**
* Create an empty list with at least the specified capacity.
*
* @param capacity
* the new capacity; if zero or negative, behavior is the same as
* {@link #Builder()}.
*/
public Builder(int capacity) {
list = new Ref[Math.max(capacity, 16)];
}
/** @return number of items in this builder's internal collection. */
public int size() {
return size;
}
/**
* Get the reference at a particular index.
*
* @param idx
* the index to obtain. Must be {@code 0 <= idx < size()}.
* @return the reference value, never null.
*/
@SuppressWarnings("unchecked")
public T get(int idx) {
return (T) list[idx];
}
/**
* Remove an item at a specific index.
*
* @param idx
* position to remove the item from.
*/
public void remove(int idx) {
System.arraycopy(list, idx + 1, list, idx, size - (idx + 1));
size--;
}
/**
* Add the reference to the end of the array.
* <p>
* References must be added in sort order, or the array must be sorted
* after additions are complete using {@link #sort()}.
*
* @param ref
*/
public void add(T ref) {
if (list.length == size) {
Ref[] n = new Ref[size * 2];
System.arraycopy(list, 0, n, 0, size);
list = n;
}
list[size++] = ref;
}
/**
* Add all items from another builder.
*
* @param other
* @since 5.4
*/
public void addAll(Builder other) {
addAll(other.list, 0, other.size);
}
/**
* Add all items from a source array.
* <p>
* References must be added in sort order, or the array must be sorted
* after additions are complete using {@link #sort()}.
*
* @param src
* the source array.
* @param off
* position within {@code src} to start copying from.
* @param cnt
* number of items to copy from {@code src}.
*/
public void addAll(Ref[] src, int off, int cnt) {
if (list.length < size + cnt) {
Ref[] n = new Ref[Math.max(size * 2, size + cnt)];
System.arraycopy(list, 0, n, 0, size);
list = n;
}
System.arraycopy(src, off, list, size, cnt);
size += cnt;
}
/**
* Replace a single existing element.
*
* @param idx
* index, must have already been added previously.
* @param ref
* the new reference.
*/
public void set(int idx, T ref) {
list[idx] = ref;
}
/** Sort the list's backing array in-place. */
public void sort() {
Arrays.sort(list, 0, size, RefComparator.INSTANCE);
}
/**
* Dedupe the refs in place. Must be called after {@link #sort}.
*
* @param mergeFunction
*/
@SuppressWarnings("unchecked")
void dedupe(BinaryOperator<T> mergeFunction) {
if (size == 0) {
return;
}
int lastElement = 0;
for (int i = 1; i < size; i++) {
if (RefComparator.INSTANCE.compare(list[lastElement],
list[i]) == 0) {
list[lastElement] = mergeFunction
.apply((T) list[lastElement], (T) list[i]);
} else {
list[lastElement + 1] = list[i];
lastElement++;
}
}
size = lastElement + 1;
Arrays.fill(list, size, list.length, null);
}
/** @return an unmodifiable list using this collection's backing array. */
public RefList<T> toRefList() {
return new RefList<>(list, size);
}
@Override
public String toString() {
return toRefList().toString();
}
}
}