On Dec 18, 10:39 pm, Patricia Shanahan <p...@acm.org> wrote:
kelvSYC wrote:
How would one implement an ordered set in Java? That is, an
collection in which the elements are ordered (the List part) and
unique (the Set part).
It would be easy to, say, implement both List and Set, however, as the
Javadoc can tell you, the conflicting semantics would make this
impossible. So what kinds of alternatives is there?
If you just need order, without needing indexing, you could use TreeSet
or LinkedHashSet. TreeSet orders by Comparable order, or by a specified
Comparator. LinkedHashSet orders by insertion order. In each case, the
class implements Set, but guarantees that its Iterator returns the
elements in the specified order.
Patricia
Comparators are good and all, but those examples severely limit your
ordering options. What I'm looking for is a combination of Set and
List such that:
* the iterator is bidirectional (possibly random-access) and returns
the elements in an arbitrary order (in the sense that I can insert an
element at index 2 and know that it will be the third element returned
by the iterator until I insert something at an earlier index - ie. in
the List sense of "arbitaray order" and not just "ordered by
comparator" or "insertion order")
* each element is guaranteed to be different from all of the others
HashSet, containing the same elements. Use the HashSet to check for
attempts to insert a duplicate. Use the LinkedList to maintain the order.