How to iterate through SparseArray?

Question

Is there a way to iterate over Java SparseArray (for Android) ? I used sparsearray to easily get values by index. I could not find one.

Unbridle

Wow, talk about a completely unloved class, conforms to ZERO collection interfaces... – Photosensitive

yeah, I know :( but is there an analogue for SparseArray ? – Unbridle

You could use a TreeMap<Integer, MyType> which would allow you to iterate in order by key. As stated, SparseArray is designed to be more efficient than a HashMap, but it doesn't allow iteration. – Instrumentality

I just wanted to avoid TreeMap or HashMap because of there heaviness.Anyway, thank you all, for your suggestions. – Unbridle

it's very, very unlikely that the performance of the map impl you choose is going to be the bottleneck in your app. – Socinian

@JeffreyBlattman doesn't mean we should avoid using the right structure when it's clearly appropriate. – Earthly

@Earthly the comment "I just wanted to avoid TreeMap or HashMap because of there heaviness" has no backing. That's my point. – Socinian

@JeffreyBlattman From the class overview, developer.android.com/reference/android/util/SparseArray.html , It is intended to be more memory efficient than using a HashMap to map Integers to Objects... – Earthly

@Earthly say it's TWICE as fast, that probably means a saving of less than 10ms. Is 10ms relevant in the grander scheme of the app? Is it worth using a sub-optimal interface that's harder to understand and maintain? I don't know the answer to those things, but the answer is not "absolutely use sparse array regardless". – Socinian

Answer 1

Seems I found the solution. I hadn't properly noticed the keyAt(index) function.

So I'll go with something like this:

for(int i = 0; i < sparseArray.size(); i++) {
   int key = sparseArray.keyAt(i);
   // get the object by the key.
   Object obj = sparseArray.get(key);
}

Unbridle

Funny that we all missed this, presumably because we were looking for the usual collection interface methods... This is it though. – Scant

the documentation states that "keyAt(int index) Given an index in the range 0...size()-1, returns the key from the indexth key-value mapping that this SparseArray stores." so it works fine for me even for the case described by you. – Unbridle

it's better to precalculate size of array and use constant value in loop. – Engenia

Wouldnt it be easier to use directly valueAt function here? – Serilda

This would work too inside the loop: Object obj = sparseArray.valueAt(i); – Like

This actually work fine. just remember that the "i" is not the real index you've used for inserting items. it's the "key" . – Angular

"int key = 0;" you don't need the "= 0", not even to be safe – Indigenous

Is this susceptible to ConcurrentModificationExceptions? I should probably surround this with a synchronized() block if I expect the sparsearray could potentially be modified during this loop right? – Microfiche

How is that everyone missed something, which is mentioned explicitly in the documentation's overview section? Or am I missing something?SparseArray – Orgiastic

valueAt(i) is faster than get(key), because valueAt(i) and keyAt(i) are both O(1), but get(key) is O(log2 n), so I would certainly always use valueAt. – Prosimian

In a SparseArray with just one item on position 2 (ex: {null, null, Object}), sparseArray.size() == 1 but sparseArray.valueAt(0) is null. However, sparseArray.keyAt(0) returns the first key, which is 2, so it's safer to use sparseArray.valueAt(sparseArray.keyAt(i)) like the accepted answer does. – Naseby

should we but sparseArray.size() in a variable,instead of being in the for loop, to avoid keep reading it. That would be faster – Clotilda

Is it safe to assume that there is no "foreach" usage equivalent for sparsearray? Not that it matters much, as this will work fine, but for curiosity sake I must know! – Thrift

Take sparseArray.size() in one variable so it will not call size() every time. – Topgallant

Have a look at the implementation of size(), it just check for gc and returns the pre-computed mSize variable. No need to over optimize. – Bermudez

@sosite Your edit conflicts with the authors intent. There is already an answer suggesting valueAt. Feel free to upvote it. – Spiv

@Spiv Ok, I just wan't that people who's going here to make a copy + paste use proper implementation (valueAt(i) in place of get(key)). But your rollback to revision 10 is still better that revision 12 by xenteros ;) – Oversight

@Bart Burg If I remove "=0" my Compiler says "error: variable i might not have been initialized" - same like in every other language... – Shig

@TheincredibleJan my comment was to an old version of the answer – Indigenous

@Bart Burg I didn't understand it correct the first time I think. You didn't mean "int i = 0" at the loop... – Shig

@Naseby that's incorrect. First, calling valueAt(i) returns the same as calling get(keyAt(i)). Further, you would really never want to pass the result of a call to keyAt() into a call to valueAt(), which you did in your last code expression. – Poundage

@Thrift that's correct. You of course can't use a literal foreach loop on a SparseArray, because SparseArray doesn't implement the Iterable interface. SparseArray also doesn't seem to have keySet() or entrySet() methods the way standard Maps do. So the only way to iterate is using the keyAt() and valueAt()/get() methods. – Poundage

Answer 2

If you don't care about the keys, then valueAt(int) can be used to while iterating through the sparse array to access the values directly.

for(int i = 0, nsize = sparseArray.size(); i < nsize; i++) {
    Object obj = sparseArray.valueAt(i);
}

Culinary

Using valueAt() is useful (and faster than accepted solution) if your iteration doesn't care about the keys, ie: a loop counting occurrences of a specific value. – Apomixis

Take sparseArray.size() in one variable so it will not call size() every time. – Topgallant

It ist redundant to copy size() to a variable. Easy to check if you just look at the code of the size() method. I can't understand why you didn't before you suggest such things... I remember a time 20 years ago where we had simple linked lists which really had to count their size everytime you asked them for it but I don't believe that such things still exist... – Shig

Is this guaranteed to be in key order? – Gramercy

@Gramercy Seems to be so. https://mcmap.net/q/100877/-sort-sparsearray-in-android – Shig

Answer 3

Ooor you just create your own ListIterator:

public final class SparseArrayIterator<E> implements ListIterator<E> {

private final SparseArray<E> array;
private int cursor;
private boolean cursorNowhere;

/**
 * @param array
 *            to iterate over.
 * @return A ListIterator on the elements of the SparseArray. The elements
 *         are iterated in the same order as they occur in the SparseArray.
 *         {@link #nextIndex()} and {@link #previousIndex()} return a
 *         SparseArray key, not an index! To get the index, call
 *         {@link android.util.SparseArray#indexOfKey(int)}.
 */
public static <E> ListIterator<E> iterate(SparseArray<E> array) {
    return iterateAt(array, -1);
}

/**
 * @param array
 *            to iterate over.
 * @param key
 *            to start the iteration at. {@link android.util.SparseArray#indexOfKey(int)}
 *            < 0 results in the same call as {@link #iterate(android.util.SparseArray)}.
 * @return A ListIterator on the elements of the SparseArray. The elements
 *         are iterated in the same order as they occur in the SparseArray.
 *         {@link #nextIndex()} and {@link #previousIndex()} return a
 *         SparseArray key, not an index! To get the index, call
 *         {@link android.util.SparseArray#indexOfKey(int)}.
 */
public static <E> ListIterator<E> iterateAtKey(SparseArray<E> array, int key) {
    return iterateAt(array, array.indexOfKey(key));
}

/**
 * @param array
 *            to iterate over.
 * @param location
 *            to start the iteration at. Value < 0 results in the same call
 *            as {@link #iterate(android.util.SparseArray)}. Value >
 *            {@link android.util.SparseArray#size()} set to that size.
 * @return A ListIterator on the elements of the SparseArray. The elements
 *         are iterated in the same order as they occur in the SparseArray.
 *         {@link #nextIndex()} and {@link #previousIndex()} return a
 *         SparseArray key, not an index! To get the index, call
 *         {@link android.util.SparseArray#indexOfKey(int)}.
 */
public static <E> ListIterator<E> iterateAt(SparseArray<E> array, int location) {
    return new SparseArrayIterator<E>(array, location);
}

private SparseArrayIterator(SparseArray<E> array, int location) {
    this.array = array;
    if (location < 0) {
        cursor = -1;
        cursorNowhere = true;
    } else if (location < array.size()) {
        cursor = location;
        cursorNowhere = false;
    } else {
        cursor = array.size() - 1;
        cursorNowhere = true;
    }
}

@Override
public boolean hasNext() {
    return cursor < array.size() - 1;
}

@Override
public boolean hasPrevious() {
    return cursorNowhere && cursor >= 0 || cursor > 0;
}

@Override
public int nextIndex() {
    if (hasNext()) {
        return array.keyAt(cursor + 1);
    } else {
        throw new NoSuchElementException();
    }
}

@Override
public int previousIndex() {
    if (hasPrevious()) {
        if (cursorNowhere) {
            return array.keyAt(cursor);
        } else {
            return array.keyAt(cursor - 1);
        }
    } else {
        throw new NoSuchElementException();
    }
}

@Override
public E next() {
    if (hasNext()) {
        if (cursorNowhere) {
            cursorNowhere = false;
        }
        cursor++;
        return array.valueAt(cursor);
    } else {
        throw new NoSuchElementException();
    }
}

@Override
public E previous() {
    if (hasPrevious()) {
        if (cursorNowhere) {
            cursorNowhere = false;
        } else {
            cursor--;
        }
        return array.valueAt(cursor);
    } else {
        throw new NoSuchElementException();
    }
}

@Override
public void add(E object) {
    throw new UnsupportedOperationException();
}

@Override
public void remove() {
    if (!cursorNowhere) {
        array.remove(array.keyAt(cursor));
        cursorNowhere = true;
        cursor--;
    } else {
        throw new IllegalStateException();
    }
}

@Override
public void set(E object) {
    if (!cursorNowhere) {
        array.setValueAt(cursor, object);
    } else {
        throw new IllegalStateException();
    }
}
}

Stockbroker

IMHO it seems a bit over-engineering. It's awesome tho – Underpass

Answer 4

Simple as Pie. Just make sure you fetch array size before actually performing the loop.

for(int i = 0, arraySize= mySparseArray.size(); i < arraySize; i++) {
   Object obj = mySparseArray.get(/* int key = */ mySparseArray.keyAt(i));
}

Hope this helps.

Sierrasiesser

Doesn't make any sense to "fetch" the size before the loop and if you only want the value it doesn't make sense to get the key first. – Shig

I am confused.. "fetching" the size before the loop is an optimization. Getting the key is the only way to get the value: it's a two step operation. Please refer to Javadoc of SparseArray. – Sierrasiesser

Answer 5

For whoever is using Kotlin, honestly the by far easiest way to iterate over a SparseArray is: Use the Kotlin extension from Anko or Android KTX! (credit to Yazazzello for pointing out Android KTX)

Simply call forEach { i, item -> }

Stockbroker

yep, you are actually right. my bad, I looked on the tags and thought that Kotlin should not be here. But now having a second thoughts that this answer is a good reference to Kotlin itself. Although instead of using Anko I'd recommend to use android.github.io/android-ktx/core-ktx (if you could kindly edit your answer and add android-ktx I'll upvote it) – Disaffect

@Disaffect hey I didn't even know about Android KTX, good point! – Stockbroker

Answer 6

For removing all the elements from SparseArray using the above looping leads to Exception.

To avoid this Follow the below code to remove all the elements from SparseArray using normal loops

private void getValues(){      
    for(int i=0; i<sparseArray.size(); i++){
          int key = sparseArray.keyAt(i);
          Log.d("Element at "+key, " is "+sparseArray.get(key));
          sparseArray.remove(key);
          i=-1;
    }
}

Serriform

The i=-1; at the end does nothing. Also there is a method called .clear() which should be favored. – Corruption

Why would you use a for() loop instead of a while()? What you're doing makes no sense for looping – Emphasize

i assume Sackurise wanted to write i-=1; to account for the now missing element. But it's better to revert the loop: for(int i=sparseArray.size()-1; i>=0; i++){...; or while (sparseArray.size()>0) { int key=sparseArray.keyAt(0);... – Dorothy

References like "the above looping" don't make any sense at all. – Shig

I thought the point of an 'iterator' was safe object removal. I haven't seen any examples of the Iterator class with sparseArrays like there is for hashmaps. This comes closest to addressing safe object removal, I hope it works without concurrent modification exceptions. – Spital

@Spital The point of an iterator is to iterate over a list. Object removal ist just one possible use. "this" has nothing to do with an iterator. – Shig

Answer 7

Here is simple Iterator<T> and Iterable<T> implementations for SparseArray<T>:

public class SparseArrayIterator<T> implements Iterator<T> {
    private final SparseArray<T> array;
    private int index;

    public SparseArrayIterator(SparseArray<T> array) {
        this.array = array;
    }

    @Override
    public boolean hasNext() {
        return array.size() > index;
    }

    @Override
    public T next() {
        return array.valueAt(index++);
    }

    @Override
    public void remove() {
        array.removeAt(index);
    }

}

public class SparseArrayIterable<T> implements Iterable<T> {
    private final SparseArray<T> sparseArray;

    public SparseArrayIterable(SparseArray<T> sparseArray) {
        this.sparseArray = sparseArray;
    }

    @Override
    public Iterator<T> iterator() {
        return new SparseArrayIterator<>(sparseArray);
    }
}

If you want to iterate not only a value but also a key:

public class SparseKeyValue<T> {
    private final int key;
    private final T value;

    public SparseKeyValue(int key, T value) {
        this.key = key;
        this.value = value;
    }

    public int getKey() {
        return key;
    }

    public T getValue() {
        return value;
    }
}

public class SparseArrayKeyValueIterator<T> implements Iterator<SparseKeyValue<T>> {
    private final SparseArray<T> array;
    private int index;

    public SparseArrayKeyValueIterator(SparseArray<T> array) {
        this.array = array;
    }

    @Override
    public boolean hasNext() {
        return array.size() > index;
    }

    @Override
    public SparseKeyValue<T> next() {
        SparseKeyValue<T> keyValue = new SparseKeyValue<>(array.keyAt(index), array.valueAt(index));
        index++;
        return keyValue;
    }

    @Override
    public void remove() {
        array.removeAt(index);
    }

}

public class SparseArrayKeyValueIterable<T> implements Iterable<SparseKeyValue<T>> {
    private final SparseArray<T> sparseArray;

    public SparseArrayKeyValueIterable(SparseArray<T> sparseArray) {
        this.sparseArray = sparseArray;
    }

    @Override
    public Iterator<SparseKeyValue<T>> iterator() {
        return new SparseArrayKeyValueIterator<T>(sparseArray);
    }
}

It's useful to create utility methods that return Iterable<T> and Iterable<SparseKeyValue<T>>:

public abstract class SparseArrayUtils {
    public static <T> Iterable<SparseKeyValue<T>> keyValueIterable(SparseArray<T> sparseArray) {
        return new SparseArrayKeyValueIterable<>(sparseArray);
    }

    public static <T> Iterable<T> iterable(SparseArray<T> sparseArray) {
        return new SparseArrayIterable<>(sparseArray);
    }
}

Now you can iterate SparseArray<T>:

SparseArray<String> a = ...;

for (String s: SparseArrayUtils.iterable(a)) {
   // ...
}

for (SparseKeyValue<String> s: SparseArrayUtils.keyValueIterable(a)) {
  // ...
}

Hervey

Answer 8

If you use Kotlin, you can use extension functions as such, for example:

fun <T> LongSparseArray<T>.valuesIterator(): Iterator<T> {
    val nSize = this.size()
    return object : Iterator<T> {
        var i = 0
        override fun hasNext(): Boolean = i < nSize
        override fun next(): T = valueAt(i++)
    }
}

fun <T> LongSparseArray<T>.keysIterator(): Iterator<Long> {
    val nSize = this.size()
    return object : Iterator<Long> {
        var i = 0
        override fun hasNext(): Boolean = i < nSize
        override fun next(): Long = keyAt(i++)
    }
}

fun <T> LongSparseArray<T>.entriesIterator(): Iterator<Pair<Long, T>> {
    val nSize = this.size()
    return object : Iterator<Pair<Long, T>> {
        var i = 0
        override fun hasNext(): Boolean = i < nSize
        override fun next() = Pair(keyAt(i), valueAt(i++))
    }
}

You can also convert to a list, if you wish. Example:

sparseArray.keysIterator().asSequence().toList()

I think it might even be safe to delete items using remove on the LongSparseArray itself (not on the iterator), as it is in ascending order.

---

EDIT: Seems there is even an easier way, by using collection-ktx (example here) . It's implemented in a very similar way to what I wrote, actally.

Gradle requires this:

implementation 'androidx.core:core-ktx:#'
implementation 'androidx.collection:collection-ktx:#'

Here's the usage for LongSparseArray :

    val sparse= LongSparseArray<String>()
    for (key in sparse.keyIterator()) {
    }
    for (value in sparse.valueIterator()) {
    }
    sparse.forEach { key, value -> 
    }

And for those that use Java, you can use LongSparseArrayKt.keyIterator , LongSparseArrayKt.valueIterator and LongSparseArrayKt.forEach , for example. Same for the other cases.

Angular

Answer 9

The answer is no because SparseArray doesn't provide it. As pst put it, this thing doesn't provide any interfaces.

You could loop from 0 - size() and skip values that return null, but that is about it.

As I state in my comment, if you need to iterate use a Map instead of a SparseArray. For example, use a TreeMap which iterates in order by the key.

TreeMap<Integer, MyType>

Instrumentality

Answer 10

The accepted answer has some holes in it. The beauty of the SparseArray is that it allows gaps in the indeces. So, we could have two maps like so, in a SparseArray...

(0,true)
(250,true)

Notice the size here would be 2. If we iterate over size, we will only get values for the values mapped to index 0 and index 1. So the mapping with a key of 250 is not accessed.

for(int i = 0; i < sparseArray.size(); i++) {
   int key = sparseArray.keyAt(i);
   // get the object by the key.
   Object obj = sparseArray.get(key);
}

The best way to do this is to iterate over the size of your data set, then check those indeces with a get() on the array. Here is an example with an adapter where I am allowing batch delete of items.

for (int index = 0; index < mAdapter.getItemCount(); index++) {
     if (toDelete.get(index) == true) {
        long idOfItemToDelete = (allItems.get(index).getId());
        mDbManager.markItemForDeletion(idOfItemToDelete);
        }
    }

I think ideally the SparseArray family would have a getKeys() method, but alas it does not.

Fastness

You're wrong - the keyAt method returns the value of the nth key (in your example keyAt(1) would return 250), not to be confused with get which returns the value of the element referenced by the key. – Service

I'm not sure what the 'this' is in your comment. Are you admitting that your answer is wrong, or are you saying that my comment is wrong? If the latter please check developer.android.com/reference/android/util/… – Service

My answer is wrong, I will not delete it so that others can learn. – Fastness