How can I cancel Collections.sort()

Question

In relation to this question, which is discussing the possibilities to monitor the process of Collections.sort(), I would like to know if there is a good way to cancel a call to Collections.sort() using a ProgressMonitor.

One approach to monitor progress is to use a custom Comparator that keeps track of its invocations.

Along this line, would it make sense to let this Comparator check for a cancelled flag and return immediately 0, without doing any actual comparison? This would save the time that is needed to do the acutal comparison, but it would not stop the iteration on the list elements.

public class ProgressMonitoringComparator<T extends Comparable<T>> implements Comparator<T> {

private volatile long invocationCount = 0;
private volatile boolean cancelled = false;
private final long elementCount;
private final ProgressMonitor monitor;

public ProgressMonitoringComparator(long elementCount) {
    this.elementCount = elementCount;
    this.monitor = null;
}

public ProgressMonitoringComparator(ProgressMonitor monitor) {
    this.monitor = monitor;
    this.elementCount = -1;
}

public ProgressMonitoringComparator() {
    this(0);
}

public boolean isCancelled() {

    return cancelled;
}

public void setCancelled(boolean cancelled) {

    this.cancelled = cancelled;
}

public float getProgress() {

    if(elementCount <= 0) {
        return -1;
    }
    long totalInvocationsNeeded = (long)(elementCount * Math.log(elementCount));
    return totalInvocationsNeeded / invocationCount;
}

@Override
public int compare(T o1, T o2) {

    if(cancelled || (monitor != null && monitor.isCancelled())) {
        return 0;
    }
    invocationCount++;
    if(monitor != null) {
        monitor.worked();
    }
    return o1.compareTo(o2);
}

}

A second approach, as suggested by user2717954, could be the following:

public class CancellableComparator<T extends Comparable<T>> implements Comparator<T> {

    private volatile boolean cancelled = false;

    public boolean isCancelled() {

        return cancelled;
    }

    public void setCancelled(boolean cancelled) {

        this.cancelled = cancelled;
    }

    @Override
    public int compare(T o1, T o2) {

        if(cancelled) {
            throw new CancelException();
        }
        return o1.compareTo(o2);
    }
}

Collections.sort() doesnt provide you with any information about it's progress. You can kill the Thread it's running in, but thats hardly a good way to do this. — f1sh, Apr 26 '17 at 09:06
@f1sh That was my first thought but... can you? Java relies on threads complying with interrupts, no? You couldn't force it to finish. And anyway, if you happen to stop it mid-swap or something, you're left with a data structure that may not be complete. — Michael, Apr 26 '17 at 09:08
@Michael you can just call ``Thread.stop()``, but you shouldn't. And of course your data will be in an undefined, unfinished state. What else would you expect when you just cancel an operation that works on the data structure you're passing to it? — f1sh, Apr 26 '17 at 09:11
@f1sh Well if `Collections.sort()` was implemented with occasional checks for interrupts then you might be alright. I'm 99% sure it's not. — Michael, Apr 26 '17 at 09:16
Which gives me the though, perhaps you could check for interrupts in a custom comparator? Sounds incredibly hacky but might be a solution. — Michael, Apr 26 '17 at 09:17

score 2 · Accepted Answer · answered Apr 28 '17 at 10:08

From the comments and similar questions, I came up with the following:

public class ProgressMonitoringComparator<T extends Comparable<T>> implements Comparator<T> {

    private static final boolean DEFAULT_SOFT = false;
    private static final int DEFAULT_ELEMENT_CNT = -1;
    private volatile long invocationCount = 0;
    private volatile boolean cancelled = false;
    private final long elementCount;
    private final ProgressMonitor monitor;
    private final Comparator<T> delegate;
    private final boolean soft;

    public boolean isCancelled() {

        return cancelled;
    }

    public void setCancelled(boolean cancelled) {

        this.cancelled = cancelled;
    }

    public double getProgress() {

        if(elementCount <= 0) {
            return -1;
        }
        long totalInvocationsNeeded = (long)(elementCount * Math.log(elementCount));
        return totalInvocationsNeeded / (double)invocationCount;
    }

    public ProgressMonitoringComparator(ProgressMonitor monitor, Comparator<T> delegate, boolean soft) {
        super();
        this.elementCount = DEFAULT_ELEMENT_CNT;
        this.monitor = monitor;
        this.delegate = delegate;
        this.soft = soft;
    }

    public ProgressMonitoringComparator(ProgressMonitor monitor, Comparator<T> delegate) {
        this(monitor, delegate, DEFAULT_SOFT);
    }

    public ProgressMonitoringComparator(ProgressMonitor monitor, boolean soft) {
        this(monitor, null, soft);
    }

    public ProgressMonitoringComparator(ProgressMonitor monitor) {
        this(monitor, DEFAULT_SOFT);
    }

    public ProgressMonitoringComparator(long elementCount, Comparator<T> delegate, boolean soft) {
        super();
        this.elementCount = elementCount;
        this.monitor = null;
        this.delegate = delegate;
        this.soft = soft;
    }

    public ProgressMonitoringComparator(long elementCount, boolean soft) {
        this(elementCount, null, soft);
    }

    public ProgressMonitoringComparator(long elementCount) {
        this(elementCount, DEFAULT_SOFT);
    }

    @Override
    public int compare(T o1, T o2) {

        if(cancelled || (monitor != null && monitor.isCancelled())) {
            if(soft) {
                return 0;
            }
            throw new CancelException();
        }
        invocationCount++;
        if(monitor != null) {
            monitor.worked();
        }
        if(delegate != null) {
            return delegate.compare(o1, o2);
        }
        return o1.compareTo(o2);
    }
}

How can I cancel Collections.sort()

1 Answers1

Linked