spatial partition in O(n) on update and only 2 int arrays extra memory

SpatialPartition.java

import java.util.*;

/**
 * 
 * spatial partitioning based on sebastian Lague's video:
 * https://www.youtube.com/watch?v=rSKMYc1CQHE
 * 
 * but using cycle sort instead of regular sorting algorithm because I can
 * 
 **/
public class SpatialPartition<P> {
	
	@FunctionalInterface
	public static interface hash<P> {
		int GetPositionHash(P p);
		
		public default int getKey(P p, int length) {
			// note(ratchetfreak): put nulls at the end,
			return p == null ? length - 1
					: SpatialPartition.getKey((GetPositionHash(p)), length);
		}
	}
	
	public SpatialPartition(int size, hash<P> hcb) {
		this.hcb = hcb;
		starts = new int[size];
		ends = new int[size];
		parts = new ArrayList<P>(size);
		parts.addAll(Collections.nCopies(size, null));
	}
	
	hash<P> hcb;
	
	int[] starts;
	int[] ends;
	List<P> parts;
	
	public static int getKey(int hash, int length) {
		int result = Integer.remainderUnsigned(hash, length);
		// note(ratchetfreak) negative module is a bitch
		return result;
	}
	
	public List<P> getParts() {
		return parts;
	}
	
	public void setSize(int size) {
		if(parts.size() < size) {
			parts.addAll(Collections.nCopies(size - parts.size(), null));
			Arrays.copyOf(starts, size);
			Arrays.copyOf(ends, size);
		}
		if(parts.size() > size) {
			parts.subList(size, parts.size()).clear();
			Arrays.copyOf(starts, size);
			Arrays.copyOf(ends, size);
			positionsChanged();
		}
		
	}
	
	public static boolean logtimings = true;
	
	public void positionsChanged() {

		hash<P> lhcb = hcb;
		{// accumulate
			Arrays.fill(starts, 0);
			// Arrays.fill(ends, 0);
			
			for(P particle : parts) {
				starts[lhcb.getKey(particle, starts.length)]++;
			}
			
			int sum = 0;
			for(int i = 0; i < starts.length; i++) {
				int el = starts[i];
				starts[i] = sum;
				// ends[i] = sum;
				sum += el;
			}
			
			System.arraycopy(starts, 0, ends, 0, starts.length);
		}
		
		
		{// rearrange
			
			// note(ratchetfreak): variation of cycle sort based on countingsort
			// because we don't care about stability
			// invariant: p = part[i] is sorted <=> starts[key(p)] <= i <
			// ends[key(p)]
			// after every iteration some end gets incremented or curr advances
			// the total amount skipped in the second branch will be equal to
			// the number of times the loop in the third branch is iterated
			// getKey is called exactly once per element after which it gets put
			// in its sorted position
			
			int curr = 0;
			int key = lhcb.getKey(parts.get(curr), starts.length);
			while(curr < parts.size()) {
				int start = starts[key];
				int end = ends[key];
				
				if(curr == end) {
					ends[key]++;
					curr++;
					if(curr >= parts.size())
						break;
					key = lhcb.getKey(parts.get(curr), starts.length);
				} else if(curr >= start && curr < end) {
					curr = end;
					if(curr >= parts.size())
						break;
					key = lhcb.getKey(parts.get(curr), starts.length);
				} else {
					P t = parts.get(curr);
					P element = parts.get(end);
					int elKey = lhcb.getKey(element, parts.size());
					
					// note(ratchetfreak): don't copy elements needlessly
					while(elKey == key) {
						ends[key]++;
						end = ends[key];
						element = parts.get(end);
						elKey = lhcb.getKey(element, parts.size());
					}
					
					parts.set(curr, element);
					parts.set(end, t);
					ends[key]++;
					key = elKey;
				}
			}
			
		}
	}
	
	public Iterator<P> getParticles(int hash) {
		int key = getKey(hash, parts.size());
		return Collections
				.unmodifiableList(parts.subList(starts[key], ends[key]))
				.iterator();
		
	}
	
	public int getFirstNull() {
		int key = parts.size() - 1;
		for(int i = starts[key]; i < parts.size(); i++) {
			if(parts.get(i) == null)
				return i;
		}
		return -1;
	}
	
	public Spliterator<P> getParticlesSpliterIterator(int hash) {
		int key = getKey(hash, parts.size());
		return Collections
				.unmodifiableList(parts.subList(starts[key], ends[key]))
				.spliterator();
		
	}
}