jcommons/org.eclipse.statet.jcommons.util/src/org/eclipse/statet/jcommons/collections/CopyOnWriteIdentityListSet.java

/*=============================================================================#
 # Copyright (c) 2014, 2021 Stephan Wahlbrink and others.
 # 
 # This program and the accompanying materials are made available under the
 # terms of the Eclipse Public License 2.0 which is available at
 # https://www.eclipse.org/legal/epl-2.0, or the Apache License, Version 2.0
 # which is available at https://www.apache.org/licenses/LICENSE-2.0.
 # 
 # SPDX-License-Identifier: EPL-2.0 OR Apache-2.0
 # 
 # Contributors:
 #     Stephan Wahlbrink <sw@wahlbrink.eu> - initial API and implementation
 #=============================================================================*/

package org.eclipse.statet.jcommons.collections;

import static org.eclipse.statet.jcommons.lang.NullDefaultLocation.FIELD;
import static org.eclipse.statet.jcommons.lang.NullDefaultLocation.PARAMETER;
import static org.eclipse.statet.jcommons.lang.NullDefaultLocation.RETURN_TYPE;
import static org.eclipse.statet.jcommons.lang.NullDefaultLocation.TYPE_ARGUMENT;
import static org.eclipse.statet.jcommons.lang.NullDefaultLocation.TYPE_BOUND;

import java.util.AbstractSet;
import java.util.Collection;
import java.util.Iterator;
import java.util.Set;
import java.util.Spliterator;

import org.eclipse.statet.internal.jcommons.collections.ArrayUtils;
import org.eclipse.statet.jcommons.lang.NonNullByDefault;
import org.eclipse.statet.jcommons.lang.Nullable;


/**
 * Thread safe set based on immutable identity lists.
 * 
 * @param <E>
 */
@NonNullByDefault({ PARAMETER, RETURN_TYPE, FIELD, TYPE_BOUND, TYPE_ARGUMENT })
public final class CopyOnWriteIdentityListSet<E> extends AbstractSet<E> implements IdentitySet<E> {
	
	
	private static int indexOf(final Object[] array, final int end, final @Nullable Object e) {
		for (int i= 0; i < end; i++) {
			if (e == array[i]) {
				return i;
			}
		}
		return -1;
	}
	
	
	private volatile ImIdentityList<E> list;
	
	
	public CopyOnWriteIdentityListSet() {
		this.list= ImCollections.newIdentityList();
	}
	
	public CopyOnWriteIdentityListSet(final Set<E> initialSet) {
		this.list= ImCollections.toIdentityList(initialSet);
	}
	
	
	@Override
	public synchronized boolean add(final E element) {
		if (!this.list.contains(element)) {
			this.list= ImCollections.addElement(this.list, element);
			return true;
		}
		return false;
	}
	
	@Override
	public synchronized boolean remove(final @Nullable Object element) {
		final ImIdentityList<E> l= ImCollections.removeElement(this.list, element);
		if (l != this.list) {
			this.list= l;
			return true;
		}
		return false;
	}
	
	@Override
	@SuppressWarnings("unchecked")
	public synchronized boolean addAll(final Collection<? extends E> c) {
		if (c.isEmpty() || this.list.containsAll(c)) {
			return false;
		}
		final ImIdentityList<E> l= this.list;
		final Object[] toAdd= c.toArray();
		int end= toAdd.length;
		for (int i= 0; i < end; ) {
			if (l.contains(toAdd[i]) || indexOf(toAdd, i, toAdd[i]) >= 0) {
				System.arraycopy(toAdd, i + 1, toAdd, i, end - i - 1);
				end--;
			}
			else {
				i++;
			}
		}
		if (end > 0) {
			this.list= ImCollections.concatList(l,
					ImCollections.newIdentityList((E[])toAdd, 0, end) );
			return true;
		}
		return false;
	}
	
	@Override
	@SuppressWarnings("unchecked")
	public synchronized boolean retainAll(final Collection<?> c) {
		final Object[] array= this.list.toArray();
		final Object[] toRetain= c.toArray();
		int end= array.length;
		for (int i= 0; i < end; ) {
			if (indexOf(toRetain, toRetain.length, array[i]) >= 0) {
				i++;
			}
			else {
				System.arraycopy(array, i + 1, array, i, end - i - 1);
				end--;
			}
		}
		if (end < array.length) {
			this.list= ImCollections.newIdentityList((E[])array, 0, end);
			return true;
		}
		return false;
	}
	
	@Override
	public synchronized boolean removeAll(final Collection<?> c) {
		if (c.isEmpty()) {
			return false;
		}
		final Iterator<?> iter= c.iterator();
		int idx= -1;
		do {
			if (iter.hasNext()) {
				idx= this.list.indexOf(iter.next());
			}
			else {
				return false;
			}
		} while (idx == -1);
		
		int n = this.list.size() - 1;
		if (n == 0) {
			this.list= ImCollections.emptyIdentityList();
			return true;
		}
		else {
			final E[] a= ArrayUtils.copyRemoveElement(this.list, n, idx);
			while (iter.hasNext()) {
				if ((idx= indexOf(a, n, iter.next())) >= 0) {
					System.arraycopy(a, idx + 1, a, idx, n - idx - 1);
					n--;
				}
			}
			this.list= ImCollections.newIdentityList(a, 0, n);
			return true;
		}
	}
	
	@Override
	public synchronized void clear() {
		if (!this.list.isEmpty()) {
			this.list= ImCollections.newIdentityList();
		}
	}
	
	
	@Override
	public int size() {
		return this.list.size();
	}
	
	@Override
	public boolean isEmpty() {
		return this.list.isEmpty();
	}
	
	@Override
	public boolean contains(final @Nullable Object o) {
		return this.list.contains(o);
	}
	
	@Override
	public boolean containsAll(final Collection<?> c) {
		return this.list.containsAll(c);
	}
	
	
	@Override
	public Iterator<E> iterator() {
		return this.list.iterator();
	}
	
	@Override
	public Spliterator<E> spliterator() {
		return this.list.spliterator();
	}
	
	
	@Override
	public Object[] toArray() {
		return this.list.toArray();
	}
	
	@Override
	public <T> T[] toArray(final T[] a) {
		return this.list.toArray(a);
	}
	
	/**
	 * Returns a current snapshot of the set.
	 * 
	 * @return
	 */
	public ImIdentityList<E> toList() {
		return this.list;
	}
	
	/**
	 * Returns a current snapshot of the list and clears the list.
	 * 
	 * @return
	 */
	public synchronized ImIdentityList<E> clearToList() {
		final ImIdentityList<E> list= this.list;
		if (!list.isEmpty()) {
			this.list= ImCollections.newIdentityList();
		}
		return list;
	}
	
	
	@Override
	public boolean equals(final @Nullable Object obj) {
		if (this == obj) {
			return true;
		}
		if (obj instanceof Set) {
			final Set<?> other= (Set<?>) obj;
			final ImList<E> l= this.list;
			return (l.size() == other.size()
					&& l.containsAll(other) );
		}
		return false;
	}
	
}