1

I am writing an application for Android mobile phones.

I have a java.util.ArrayList that contains objects which require a custom java.util.Comparator to be sorted properly.

I know I can use java.util.Collections.sort() but the amount of data is such that I want to sort my ArrayList in an android.os.AsyncTask.

I do not want to use several AsyncTask objects that would each sort a subset of the data.

Any AsyncTask can be cancelled so I want to regularly call AsyncTask.isCancelled() while I sort. If it returns true, I give up on sorting (and on my whole data set).

I Googled but could not find an AsyncTask-friendly way to sort while regularly checking for cancellation.

I may be able to call isCancelled() in my implementation of java.util.Comparator.compare() and throw my own subclass of java.lang.RuntimeException if it returns true. Then try{java.util.Collections.sort(ArrayList, Comparator);} catch () {} for that specific exception. I don't feel entirely comfortable with that approach.

Alternatively, I can use an intermediary java.util.TreeSet and write 2 loops that each check for cancellation before every iteration. The first loop would add all the items of the ArrayList to the TreeSet (and my Comparator implementation keeps them sorted on insertion). The second loop would add all the object in the TreeSet back into the ArrayList, in the correct order, thanks to the TreeSet natural java.util.Iterator. This approach uses some extra memory but will assuredly work.

The last approach I can think of is to implement myself what I have actually been looking for in Android: A generic java.util.List (preferably quick)sort using a java.util.Comparator and an android.os.AsyncTask that regularly checks for cancellation.

Has anybody found that?
Do you have any other solution to this problem?

EDIT:

Although I haven't given any thought to what the sorting method signature would look like, I would also be perfectly happy with using a android.os.CancellationSignal to decide when to abandon the sorting.

michael aubert
  • 6,836
  • 1
  • 16
  • 32
  • Or you could run a separate thread which checks isCancelled(), what this do is, when isCancelled returns true, just make your sorting class, or method terminate. – jitain sharma Aug 21 '14 at 14:53
  • My vote will be go with throwing RuntimeException from comparator if task is cancelled. It may seem like a minor hack but given the situation is more elegant than having to roll your own sorting code. – RajV Aug 21 '14 at 15:14

1 Answers1

0

I’ll try to describe my thought process here. If anybody had better offers at any point…

Lets re-affirm what we are trying to achieve here. We need a sorting algorithm with the following properties

  1. Runs on a single task

  2. Be in place i.e. not use extra memory

  3. We should be able to cancel the sort at will, i.e. return immediately or very close to it when we decide it's no longer needed.

  4. Be efficient

  5. Would not use exceptions to control a perfectly normal flow of your application. You are right about not feeling comfortable about that one ☺

    There is no native android tool to do that AFAIK

Let's focus for a second on requirement 3.

Here is a quote from asycTask documentation, The section regarding cancelling a task

Blockquote To ensure that a task is cancelled as quickly as possible, you should always check the return value of isCancelled() periodically from doInBackground(Object[]), if possible (inside a loop for instance.) ".

Meaning, an iterative sorting algorithm, where on each iteration you must check for the isCancalled() flag, will fill this requirment. The problem is simple iterative sorting algorithms , such is Insertion sort, often are not very efficient. It shouldn’t matter too much for small inputs, but since you say your typical input is a huge array list, and that triggered our quest anyway, we need to keep things as efficient as possible.

Since you did mention quick sort, I was thinking, it has got everything we need! It’s efficient, it’s in place, it runs on a single task. There is only one shortfall. It is, in it’s classic form, recursive, meaning it won’t return immediately upon cancellation. Luckily a brief Google search yields many results that can help including this one. In Brief, you can find there a variant for quicksort that is iterative. This is done by replacing the recursive callstack by a stack that stores the same indexes that recursive implementation would use to preform "partition" with. Take this Algorithm, add a check if asyncTask.isCancelled() on each iteration, and you got yourself a solution that answers all the requirements.

Community
  • 1
  • 1
Tal Ophir
  • 9
  • 2