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/.

Leave a Reply

Join Our Engineering Community

To help personalize content, tailor and measure ads, and provide a safer experience, we use cookies. By clicking or navigating the site, you agree to allow our collection of information on and off Facebook through cookies. Learn more, including about available controls: Cookies Policy