Re: A suitable container that can sort -- please help!
This won't work. The SortedSet contains instances of "something,"
not pairs of instances. If you need to associate a Point with a double,
one straightforward approach is to make yourself a "holder" class that
contains the Point and its associated double, and to put instances of
the "holder" into the set:
class Holder {
final Point point;
final double value;
Holder(Point point, double value) {
this.point = point.clone();
this.value = value;
}
}
...
set.add(new Holder(somePoint, someDouble));
You can also use a SortedMap, which sorts according to the key, so
someDouble could be your Key and somePoint could be the Value. Then,
Map.Entry is similar to this Holder.
If all you want is the first Point/double pair in sorted order,
keeping the entire collection sorted is a lot of wasted work.
From a coding point of work, using a TreeSet or TreeMap is next to zero
work. From an efficiency point of view this depends on the application.
In general, keeping it sorted is not much work. Inserting into a tree of
size n takes only time log(n) (I'll skip the O() below).
Some
possibilities:
- If you want only the extreme Point/double pair, just dump all
the pairs into any convenient collection without regard to their
order. Then when you want the extreme, just sweep once over the
collection to find the pair with minimum (or maximum) value.
Will be O(n) for inserting and O(n) again for each scan. This is good if
the data structure is never updated (so you only need one scan) or you
update the data structure but perform extremely few scans, namely at
most log(n). Otherwise, the next option is more efficient:
- If you gather all the Point/double pairs and then want to process
them in sorted order, begin by putting them in a List without
regard to order. When you've gathered them all, sort the List
with Collections.sort(), and then traverse the sorted List.
Will be n log(n) for sorting, but again does not allow for updates.
This is at par with the SortedSet solution. Inserting n times, each in
time log(n) will also require time n log(n). However, the SortedSet
allows for updates.
- If Point/double pairs are coming and going all the time and you
need to keep them in sorted order all the time, the extra work
of a SortedSet makes sense.
[...]
This depends on the ratio between the number of insertions, say k, the
number of items in the set at any given time, say n, and the number of
queries, q.
For keeping the sorted set, the time for the whole process would be
k * log(n) + q * log(n)
For the linked list version (assuming that you can remove in constant
time, which is possible, but not well supported by
java.util.LinkedList), you have time
k + q * n.
If k >> q, the second option could be more efficient, but most of the
time, the first one will be better. Also, if you don't know the exact
application, the first is always relatively good, whereas the second can
be extremely bad.
Best,
Simon