org.eclipse.jgit/src/org/eclipse/jgit/util/RefList.java - jgit - Git at Google

 /*
  * 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&lt;String,Ref&gt; and of a List&lt;Ref&gt;. 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.
 	 *
 	 * @param <T>
 	 *            type of reference being stored.
 	 * @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;
 	}

 	@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);
 	}

 	@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 <T>
 	 *            type of reference being stored.
 	 * @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)];
 		}

 		/**
 		 * Get size
 		 *
 		 * @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
 		 *            reference to add
 		 */
 		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
 		 *            another builder
 		 * @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
 		 *            function used for de-duplication
 		 */
 		@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);
 		}

 		/**
 		 * Get unmodifiable list based on this list
 		 *
 		 * @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();
 		}
 	}
 }
	/*
	* 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.
	*
	* @param <T>
	* type of reference being stored.
	* @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;
	}

	@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);
	}

	@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 <T>
	* type of reference being stored.
	* @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)];
	}

	/**
	* Get size
	*
	* @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
	* reference to add
	*/
	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
	* another builder
	* @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
	* function used for de-duplication
	*/
	@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);
	}

	/**
	* Get unmodifiable list based on this list
	*
	* @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();
	}
	}
	}