I understand that Java does not possess a Sorted List for various conceptual reasons, but consider the case I need to have a collection which is kind of like a Priority Queue but also allows me random access (indexable), in other words, I need a List that follows a particular ordering. I would prefer not to use Collections.sort()
Preferable operation constraints:
retrieve - O(1) (index-based random access)
search - O(log n)
insert - O(log n)
delete - O(log n)
An iterator over the collection should give me all elements in Sorted Order (based on predefined Comparator
supplied during instantiation of the data-structure)
I would prefer to use Java's inbuilt library to accomplish this, but feel free to suggest external libraries as well.
EDIT: TreeSet won't do as index based access is difficult, using wrapper collections is also not my best choice as removal would imply I need to remove from both collections.
EDIT2: I was unable to find an implementation and/or documentation for an indexable skip list
this seems a bit relevant, can anyone help me find it ? Any comments for or against the data structure proposed is also welcome.
EDIT3: Though this may not be the most perfect answer, I want to add this piece of code that I wrote so that anyone who has similar problems for the need of a sorted list can use this if they find it useful.
Do check for errors (if any), and suggest improvements (especially to the sortedSubList
method)
import java.util.ArrayList;
import java.util.Collection;
import java.util.Comparator;
public class SortedList<E> extends ArrayList<E> {
private final Comparator<? super E> comparator;
public SortedList(Comparator<? super E> comparator) {
this.comparator = comparator;
}
public SortedList(int initialCapacity, Comparator<? super E> comparator) {
super(initialCapacity);
this.comparator = comparator;
}
@Override
public boolean add(E e) {
if (comparator == null)
return super.add(e);
if (e == null)
throw new NullPointerException();
int start = 0;
int end = size() - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (comparator.compare(get(mid), e) == 0) {
super.add(mid, e);
return true;
}
if (comparator.compare(get(mid), e) < 0) {
end = mid - 1;
}
else {
start = mid + 1;
}
}
super.add(start, e);
return true;
}
@Override
public boolean contains(Object o) {
if (comparator == null)
return super.contains(o);
if (o == null)
return false;
E other = (E) o;
int start = 0;
int end = size() - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (comparator.compare(get(mid), other) == 0) {
return true;
}
if (comparator.compare(get(mid), other) < 0) {
end = mid - 1;
}
else {
start = mid + 1;
}
}
return false;
}
@Override
public int indexOf(Object o) {
if (comparator == null)
return super.indexOf(o);
if (o == null)
throw new NullPointerException();
E other = (E) o;
int start = 0;
int end = size() - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (comparator.compare(get(mid), other) == 0) {
return mid;
}
if (comparator.compare(get(mid), other) < 0) {
end = mid - 1;
}
else {
start = mid + 1;
}
}
return -(start+1);
}
@Override
public void add(int index, E e) {
throw new UnsupportedOperationException();
}
@Override
public boolean addAll(int index, Collection<? extends E> c) {
throw new UnsupportedOperationException();
}
@Override
public E set(int index, E e) {
throw new UnsupportedOperationException();
}
public SortedList<E> sortedSubList(int fromIndex, int toIndex) {
SortedList<E> sl = new SortedList<>(comparator);
for (int i = fromIndex; i < toIndex; i++)
sl.add(get(i));
return sl;
}
}
Build a custom collection that is backed by an ArrayList and a TreeSet. Delegate the random access to the ArrayList and the search to the TreeSet. Of course this means that every write operation will be very expensive, as it will have to sort the ArrayList every time. But the reads should be very efficient.