 |
 | Home | Contact Us | FAQ | Search & Site Map | Link to Us |
 | Sign In | Join | Other 45 Sites in Network |
Java Forum / General / December 2007Ordered Sets
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? > How would one implement an ordered set in Java? That is, an > collection in which the elements are ordered (the List part) and [quoted text clipped - 3 lines] > Javadoc can tell you, the conflicting semantics would make this > impossible. So what kinds of alternatives is there? EnumSet  SignatureKnute Johnson email s/nospam/knute/ > How would one implement an ordered set in Java? That is, an > collection in which the elements are ordered (the List part) and [quoted text clipped - 3 lines] > 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 > > How would one implement an ordered set in Java? That is, an > > collection in which the elements are ordered (the List part) and [quoted text clipped - 11 lines] > > 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? >>> How would one implement an ordered set in Java? That is, an >>> collection in which the elements are ordered (the List part) and [quoted text clipped - 20 lines] > 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 > 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? > > 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 [quoted text clipped - 9 lines] > > Patricia I might have to do that, and then have methods that convert it to a List or Set as needed, I guess. >> 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? 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. > 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... ;-) >>> What happens if you attempt to insert at index 2 but the element >>> you are [quoted text clipped - 6 lines] > 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 >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. >> Note that even if it is neither a List nor a Set, > [quoted text clipped - 12 lines] > > . 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 >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. >> That approach was one of my first suggestions, > [quoted text clipped - 23 lines] > 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 >>> That approach was one of my first suggestions, >> [quoted text clipped - 34 lines] > 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. > >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. 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. Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
Reply to this Message
|
 Sign In
 Join
 My Latest Posts My Monitored Threads My Blog My Photo Gallery My Profile My Homepage Start New Thread Enable EMail Alerts Rate this Thread
|
©2009 Advenet LLC Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.