title: Java partially ordered Collection<E>
body: <p>I am looking for a Java implementation of a data structure which holds a collection of elements for which a <strong>partial ordering</strong> is defined, and which allows one to iterate over those elements in some <strong>topological order</strong> (any of the possible orderings is fine; preferably a stable ordering as the contents of the collection changes).</p>
  
  <p>Ideally it would implement a <code>Collection&lt;E&gt;</code>, <code>Set&lt;E&gt;</code>, or <code>SortedSet&lt;E&gt;</code> interface and support all of the methods on the interface.  In terms of specifying the total ordering, the collection could be instantiated with a <code>Comparator&lt;E&gt;</code>, and the comparator could throw an exception (<code>ClassCastException</code>?) if two elements being compared are not ordered with respect to each other.  As a bonus, it would throw an exception if an element being inserted would produce an ordering anomaly (a cycle in the ordered graph of elements).</p>
  
  <p>So yeah, what I want is a topological sort, but I would like a <em>collection object that maintains that sort order</em> with every insertion/removal, similarly to how SortedSet maintains a collection in sorted order.</p>
  
  <p>Does something like this exist?  In some open source library?</p>
  
  <p><strong>References:</strong></p>
  
  <p><a href="http://en.wikipedia.org/wiki/Partially_ordered_set" rel="noreferrer">http://en.wikipedia.org/wiki/Partially_ordered_set</a></p>
  
  <p><a href="http://en.wikipedia.org/wiki/Topological_sorting" rel="noreferrer">http://en.wikipedia.org/wiki/Topological_sorting</a></p>
  
  <p><strong>Update</strong></p>
  
  <p>I ended up going with a different approach for my problem where I won't need a poset, after realizing the performance implications of my requirements (and various other issues that I couldn't quite resolve, using the poset).  Relying on the comparator to determine the ordering among elements means that for element insertion, I have to consult the comparator against every existing element, costing O(n) per insertion.</p>
  
  <p>If performance were not very important (it is), and if the number of elements was bounded to something reasonable (it isn't), I think I would have taken the approach suggested by Willie, although perhaps with my own graph implementation and topological sort implementation to minimize dependencies.</p>