June 27, 2016

Primitive sets for Android

Udi Cohen

LongArraySet

import android.support.v4.util.LongSparseArray;

/**
 * An implementation of a Set using primitive long data type.
 * It uses {@link android.support.v4.util.LongSparseArray} as a backing map,
 * the same as HashSet uses HashMap internally.
 *
 * Note that this container keeps its mappings in an array data structure,
 * using a binary search to find keys.  The implementation is not intended to be appropriate for
 * data structures that may contain large numbers of items.  It is generally slower than a
 * traditional HashSet, since lookups require a binary search and adds and removes require
 * inserting and deleting entries in the array.  For containers holding up to hundreds of items,
 * the performance difference is not significant, less than 50%.
 *
 * To help with performance, the container includes an optimization when removing
 * keys: instead of compacting its array immediately, it leaves the removed entry marked
 * as deleted.  The entry can then be re-used for the same key, or compacted later in
 * a single garbage collection step of all removed entries.  This garbage collection will
 * need to be performed at any time the array needs to be grown or the the map size or
 * entry values are retrieved.
 */
public class LongArraySet implements Cloneable {

    private LongSparseArray<LongArraySet> backingMap;

    /**
     * Constructs a new empty instance of {@code LongArraySet}.
     */
    public LongArraySet() {
        this(new LongSparseArray<LongArraySet>());
    }

    /**
     * Constructs a new instance of {@code LongArraySet} with a specified capacity.
     *
     * @param capacity the initial capacity of this {@code LongArraySet}.
     */
    private LongArraySet(int capacity) {
        this(new LongSparseArray<LongArraySet>(capacity));
    }

    /**
     * Constructs a new instance of {@code LongArraySet} containing the unique
     * elements in the specified array.
     *
     * @param items the array of elements to add.
     */
    private LongArraySet(long[] items) {
        this(new LongSparseArray<LongArraySet>(items.length));
        for (int i = 0; i < items.length; i++) {
            add(items[i]);
        }
    }

    /**
     * Internal CTor to initialize the internal backing map.
     * @param backingMap
     */
    private LongArraySet(LongSparseArray<LongArraySet> backingMap) {
        this.backingMap = backingMap;
    }

    /**
     * Creates a new {@code LongArraySet} with a specified capacity.
     *
     * @param capacity the initial capacity of this {@code LongArraySet}.
     * @return LongArraySet
     */
    public static LongArraySet newLongArraySetWithCapacity(int capacity) {
        return new LongArraySet(capacity);
    }

    /**
     * Creates a new {@code LongArraySet} containing the unique
     * elements in the specified array.
     *
     * @param elements the array of elements to add.
     * @return LongArraySet
     */
    public static LongArraySet newLongArraySet(long[] elements) {
        return new LongArraySet(elements);
    }

    /**
     * Adds the specified item to this {@code LongArraySet}, if not already present.
     *
     * @param item
     *            the object to add.
     */
    public void add(long item) {
        backingMap.put(item, this);
    }

    /**
     * Removes all elements from this {@code LongArraySet}, leaving it empty.
     *
     * @see #isEmpty
     * @see #size
     */
    public void clear() {
        backingMap.clear();
    }

    /**
     * Searches this {@code LongArraySet} for the specified object.
     *
     * @param item
     *            the object to search for.
     * @return {@code true} if {@code object} is an element of this
     *         {@code LongArraySet}, {@code false} otherwise.
     */
    public boolean contains(long item) {
        return backingMap.indexOfKey(item) >= 0;
    }

    /**
     * Returns true if this {@code LongArraySet} has no elements, false otherwise.
     *
     * @return {@code true} if this {@code LongArraySet} has no elements,
     *         {@code false} otherwise.
     * @see #size
     */
    public boolean isEmpty() {
        return backingMap.size() == 0;
    }

    /**
     * Removes the specified object from this {@code LongArraySet}.
     *
     * @param item
     *            the object to remove.
     */
    public void remove(long item) {
        backingMap.remove(item);
    }

    /**
     * Returns the number of elements in this {@code LongArraySet}.
     *
     * @return the number of elements in this {@code LongArraySet}.
     */
    public int size() {
        return backingMap.size();
    }

    /**
     * Get all the items in this {@code LongArraySet}.
     *
     * @return  {@code long[]} array of all the items in the set.
     *          A new array will be allocated for each request, modifying it won't affect the set.
     */
    public long[] getAllItems() {
        int size = backingMap.size();
        long ret[] = new long[size];

        for (int i = 0; i < size; i++) {
            ret[i] = backingMap.keyAt(i);
        }
        return ret;
    }
}

IntArraySet

import android.support.v4.util.SparseArrayCompat;

/**
 * An implementation of a Set using primitive int data type.
 * It uses {@link android.support.v4.util.SparseArrayCompat} as a backing map,
 * the same as HashSet uses HashMap internally.
 *
 * Note that this container keeps its mappings in an array data structure,
 * using a binary search to find keys.  The implementation is not intended to be appropriate for
 * data structures that may contain large numbers of items.  It is generally slower than a
 * traditional HashSet, since lookups require a binary search and adds and removes require
 * inserting and deleting entries in the array.  For containers holding up to hundreds of items,
 * the performance difference is not significant, less than 50%.
 *
 * To help with performance, the container includes an optimization when removing
 * keys: instead of compacting its array immediately, it leaves the removed entry marked
 * as deleted.  The entry can then be re-used for the same key, or compacted later in
 * a single garbage collection step of all removed entries.  This garbage collection will
 * need to be performed at any time the array needs to be grown or the the map size or
 * entry values are retrieved.
 */
public class IntArraySet implements Cloneable {

    private SparseArrayCompat<IntArraySet> backingMap;

    /**
     * Constructs a new empty instance of {@code IntArraySet}.
     */
    public IntArraySet() {
        this(new SparseArrayCompat<IntArraySet>());
    }

    /**
     * Constructs a new instance of {@code IntArraySet} containing the unique
     * elements in the specified array.
     *
     * @param items the array of elements to add.
     */
    private IntArraySet(int[] items) {
        this(new SparseArrayCompat<IntArraySet>(items.length));
        for (int i = 0; i < items.length; i++) {
            add(items[i]);
        }
    }

    /**
     * Constructs a new instance of {@code IntArraySet} with a specified capacity.
     *
     * @param capacity the initial capacity of this {@code IntArraySet}.
     */
    private IntArraySet(int capacity) {
        this(new SparseArrayCompat<IntArraySet>(capacity));
    }

    /**
     * Internal CTor to initialize the internal backing map.
     * @param backingMap
     */
    private IntArraySet(SparseArrayCompat<IntArraySet> backingMap) {
        this.backingMap = backingMap;
    }

    /**
     * Creates a new {@code IntArraySet} with a specified capacity.
     *
     * @param capacity the initial capacity of this {@code IntArraySet}.
     * @return IntArraySet
     */
    public static IntArraySet newIntArraySetWithCapacity(int capacity) {
        return new IntArraySet(capacity);
    }

    /**
     * Creates a new {@code IntArraySet} containing the unique
     * elements in the specified array.
     *
     * @param elements the array of elements to add.
     * @return IntArraySet
     */
    public static IntArraySet newIntArraySet(int[] elements) {
        return new IntArraySet(elements);
    }

    /**
     * Adds the specified item to this {@code IntArraySet}, if not already present.
     *
     * @param item
     *            the object to add.
     */
    public void add(int item) {
        backingMap.put(item, this);
    }

    /**
     * Removes all elements from this {@code IntArraySet}, leaving it empty.
     *
     * @see #isEmpty
     * @see #size
     */
    public void clear() {
        backingMap.clear();
    }

    /**
     * Searches this {@code IntArraySet} for the specified object.
     *
     * @param item
     *            the object to search for.
     * @return {@code true} if {@code object} is an element of this
     *         {@code IntArraySet}, {@code false} otherwise.
     */
    public boolean contains(int item) {
        return backingMap.indexOfKey(item) >= 0;
    }

    /**
     * Returns true if this {@code IntArraySet} has no elements, false otherwise.
     *
     * @return {@code true} if this {@code IntArraySet} has no elements,
     *         {@code false} otherwise.
     * @see #size
     */
    public boolean isEmpty() {
        return backingMap.size() == 0;
    }

    /**
     * Removes the specified object from this {@code IntArraySet}.
     *
     * @param item
     *            the object to remove.
     */
    public void remove(int item) {
        backingMap.remove(item);
    }

    /**
     * Returns the number of elements in this {@code IntArraySet}.
     *
     * @return the number of elements in this {@code IntArraySet}.
     */
    public int size() {
        return backingMap.size();
    }

    /**
     * Get all the items in this {@code IntArraySet}.
     *
     * @return  {@code int[]} array of all the items in the set.
     *          A new array will be allocated for each request, modifying it won't affect the set.
     */
    public int[] getAllItems() {
        int size = backingMap.size();
        int ret[] = new int[size];

        for (int i = 0; i < size; i++) {
            ret[i] = backingMap.keyAt(i);
        }
        return ret;
    }

    @Override
    @SuppressWarnings("unchecked")
    public IntArraySet clone() {
        IntArraySet clone = null;
        try {
            clone = (IntArraySet) super.clone();
            clone.backingMap = backingMap.clone();
        } catch (CloneNotSupportedException cnse) {
            /* ignore */
        }
        return clone;
    }
}

Copyright 2016-present, Facebook, Inc. All rights reserved. This sample code is licensed under the Creative Commons Attribution license available at https://creativecommons.org/licenses/by/4.0/.

Keep Updated

Stay up-to-date via RSS with the latest open source project releases from Facebook, news from our Engineering teams, and upcoming events.

Subscribe
Facebook © 2017