Java ListSet somewhere?

Question

Looking for a insertion order collection that also allows efficient querying and subset views of positions (like sublist). Seems the most straightforward option for this would be to take the linked list approach of List, embed the nodes as map values and expose part or all of the list interface on the class.

Would someone bitch to Oracle about this? Having NavigableMap/Set added for sorted maps and sets and not having the far more common insertion order equivalent...

edit: please don't suggest LinkedHashSet - it doesn't have any way to query the position or to do a relative subset.

Answer 1

edit2: New final version Here is a version only for sets with slightly adjusted function (divided into two, no longer accepts null as 'beginning of the map') that probably has less bugs

public class LinkedSet<E> implements Set<E> {

private LinkedHashMap<E, Integer> m = new LinkedHashMap<E, Integer>();
private int monoticallyIncreasing;

/**
 * Returns true if the value target was added before (exclusive)
 * limitElem in insertion order.
 *
 * If target or limit are not present on the set this method returns false
 *
 * @param limitElem a E that may be a element of the set or not.
 * @return if target was added before limit (can be reset by removing and
 * re-adding the target, that changes iteration order).
 */
public boolean containsBefore(E target, E limitElem) {
    if (isEmpty()) {
        return false;
    }

    Integer targetN = m.get(target);
    if (targetN == null) {
        return false;
    }

    Integer highN = m.get(limitElem);
    if (highN == null) {
        return false;
    }
    return targetN < highN;
}

/**
 * Returns true if the value target was added after (exclusive)
 * previousElem in insertion order.
 *
 * If target or previous are not present on the set this method returns false
 *
 * @param previousElem a E that may be a element of the set or not.
 * @return if target was added before previous (can be reset by removing and
 * re-adding the target, that changes iteration order).
 */
public boolean containsAfter(E target, E previousElem) {
    if (isEmpty()) {
        return false;
    }

    Integer targetN = m.get(target);
    if (targetN == null) {
        return false;
    }

    Integer low = m.get(previousElem);
    if (low == null) {
        return false;
    }
    return low < targetN;
}

@Override
public boolean add(E e) {
    Integer pos = m.get(e);
    if (pos == null) {
        m.put(e, monoticallyIncreasing++);
        return true;
    }
    return false;
}

@Override
public int size() {
    return m.size();
}

@Override
public boolean isEmpty() {
    return m.isEmpty();
}

@Override
public boolean contains(Object o) {
    return m.containsKey(o);
}

@Override
public Object[] toArray() {
    Object[] result = new Object[size()];
    int i = 0;
    for (E e : this) {
        result[i++] = e;
    }
    return result;
}

@Override
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
    int size = size();
    if (a.length < size) {
        a = (T[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
    }
    int i = 0;
    Object[] result = a;
    for (E e : this) {
        result[i++] = e;
    }
    if (a.length > size) {
        //peculiar toArray contract where it doesn't care about the rest
        a[size] = null;
    }
    return a;
}

@Override
public boolean remove(Object o) {
    return m.remove(o) != null;
}

@Override
public boolean addAll(Collection<? extends E> c) {
    boolean changed = false;
    for (E e : c) {
        changed |= add(e);
    }
    return changed;
}

@Override
public boolean containsAll(Collection<?> c) {
    return m.keySet().containsAll(c);
}

@Override
public boolean retainAll(Collection<?> c) {
    return m.keySet().retainAll(c);
}

@Override
public boolean removeAll(Collection<?> c) {
    return m.keySet().removeAll(c);
}

@Override
public void clear() {
    m.clear();
}

@Override
public Iterator<E> iterator() {
    return m.keySet().iterator();
}
}

Answer 2

you mean like java.util.LinkedHashSet:

Hash table and linked list implementation of the Set interface, with predictable iteration order. This implementation differs from HashSet in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order). Note that insertion order is not affected if an element is re-inserted into the set. (An element e is reinserted into a set s if s.add(e) is invoked when s.contains(e) would return true immediately prior to the invocation.)