Ordered Sets

[kelvSYC]

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?

 

[Knute Johnson]

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?

EnumSet

 

[Patricia Shanahan]

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

 

[kelvSYC]

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

Basically I'm thinking of something that's closer to "List with some
features of Set" rather than "Set with some features of List". Any
good way to implement those?

 

[Patricia Shanahan]

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

What happens if you attempt to insert at index 2 but the element you are
trying to insert is a duplicate of an existing element?

Basically I'm thinking of something that's closer to "List with some
features of Set" rather than "Set with some features of List". Any
good way to implement those?

This is such a specific set of requirements that I think it should not
be regarded as either List or Set, but rather as a Collection with some
specific methods of your own.

To implement it, you might be able to combine a LinkedList and a
HashSet, containing the same elements. Use the HashSet to check for
attempts to insert a duplicate. Use the LinkedList to maintain the order.

Patricia

 

[kelvSYC]

What happens if you attempt to insert at index 2 but the element you are

trying to insert is a duplicate of an existing element?

add() can return false to show that the list was not changed, right?

This is such a specific set of requirements that I think it should not
be regarded as either List or Set, but rather as a Collection with some
specific methods of your own.

To implement it, you might be able to combine a LinkedList and a
HashSet, containing the same elements. Use the HashSet to check for
attempts to insert a duplicate. Use the LinkedList to maintain the order.

Patricia

I might have to do that, and then have methods that convert it to a
List or Set as needed, I guess.

 

[Mike Schilling]

add() can return false to show that the list was not changed, right?

List.add() (unlike Set.add()) is declared void. Lists, unlike Sets,
have no reason to reject an add.

What you need to do is define the behavior of your class precisely,
and only then decide whether it's a List, a Set, or neither.

 

[Mark Space]

What you need to do is define the behavior of your class precisely,
and only then decide whether it's a List, a Set, or neither.

What? Get requirements first? That takes too long, I like to start in
codin' right away...


;-)

 

[Patricia Shanahan]

List.add() (unlike Set.add()) is declared void. Lists, unlike Sets,
have no reason to reject an add.

What you need to do is define the behavior of your class precisely,
and only then decide whether it's a List, a Set, or neither.

Note that even if it is neither a List nor a Set, it can share some of
their characteristics. For example, it does seem to be naturally
Iterable, which makes it easy to scan the elements in forwards order.
Its strangenesses are limited to the add method(s), so maybe it could
have a method that returns an unmodifiable List view. See
Collections.unmodifiableList to see how to do it.

Patricia

 

[Stefan Ram]

Note that even if it is neither a List nor a Set,

An »ordered set« is a pair of a set and an ordering relation
on the elements.

So, a Java description might be like

interface orderedSet<E>
{ public java.util.Set<E> getSet();
public java.util.Comparator<E> getComparator(); }

or even just

java.util.Set<java.lang.Comparable>

. This might or might not be what the OP had in mind.

 

[Patricia Shanahan]

An »ordered set« is a pair of a set and an ordering relation
on the elements.

So, a Java description might be like

interface orderedSet<E>
{ public java.util.Set<E> getSet();
public java.util.Comparator<E> getComparator(); }

or even just

java.util.Set<java.lang.Comparable>

. This might or might not be what the OP had in mind.

That approach was one of my first suggestions, but the OP wants to be
able to insert items at arbitrary positions, not according to Comparable
order, or even a Comparator.

Patricia

 

[Stefan Ram]

That approach was one of my first suggestions,

Sorry, I must have missed that.

but the OP wants to be able to insert items at arbitrary
positions, not according to Comparable order, or even a
Comparator.

Actually, it could be done.

For example, the ordered set might have been: |1, 2|

Now, to insert »4« into the middle, i.e., to get |1, 4, 2|,

- add »4« to the set

- make sure that the ordering relation will evaluate as follows
(1,4)=1
(1,2)=1
(4,2)=1
(x,y)=-(y,x)
(x,x)=0

This includes, possibly changing the Comparator at run-time.

It might not be a good for anything, so it might be idle
to write about this, but it is not impossible either.

 

[Patricia Shanahan]

Sorry, I must have missed that.


Actually, it could be done.

For example, the ordered set might have been: |1, 2|

Now, to insert »4« into the middle, i.e., to get |1, 4, 2|,

- add »4« to the set

- make sure that the ordering relation will evaluate as follows
(1,4)=1
(1,2)=1
(4,2)=1
(x,y)=-(y,x)
(x,x)=0

This includes, possibly changing the Comparator at run-time.

It might not be a good for anything, so it might be idle
to write about this, but it is not impossible either.

I did think of an evil variant using a TreeMap<BigDecimal,Whatever>. An
insert into an empty structure uses key 0. An insert at the start of a
non-empty uses key one less than the current lowest key. Similarly,
insert at the end by using key one greater than the current highest key.
To insert between two items, use the mean of their keys.

Patricia

 

[Mike Schilling]

I did think of an evil variant using a TreeMap<BigDecimal,Whatever>.
An
insert into an empty structure uses key 0. An insert at the start of
a
non-empty uses key one less than the current lowest key. Similarly,
insert at the end by using key one greater than the current highest
key.
To insert between two items, use the mean of their keys.

That doesn't help with duplicate detection, though. You'll still need
a Map or Set with the Whatevers as keys. My best first try uses a
LinkedList and a HashSet, the LL for iteration in both directions and
the HS for duplicate direction. The iterate() method returns
something like a ListIterator but whose add() method returns a
boolean. The requirments aren't complete enough to refine this.

 

[kelvSYC]

An >>ordered set<< is a pair of a set and an ordering relation
on the elements.

Technically that's what an ordered set is, so I do have to apologize
for the misuse of terminology. But yes, I was looking for something
that was "ordered" in the sense of how a List is ordered, and not
"ordered" in the sense of an ordering relation.