Rather than taking a Comparator or objects implementing Comparable, the mutable sorted set takes a KeyFunctor object that is used to generate sort keys from the data on the fly.
The existing TreeSet class only sorts objects when they are initially added, and any subsequent mutation of any data members used in the Comparator used to sort the objects will put the Set in an undefined state. (This is what we call a Bad Thing.) MutableSortedSet overcomes this by computing the sort key when the object is added to the set, and then storing the key apart from the object. Thus, the objects in the set will remain sorted based on their state at the time they were added to the set, regardless of any subsequent mutations. Additionally, an item can be re-sorted at any time by calling MutableSortedSet.resort(E), which will remove the object, then re-add it with a re-computed key.
As far as efficiency, MutableSortedSet is actually somewhat faster than TreeSet for some operations, including contains(Object), and has the same time complexity as TreeSet for all other operations.
Public Member Functions | |
MutableSortedSet (KeyFunctor< E > func) | |
Constructs a MutableSortedSet with the given KeyFunctor. | |
synchronized boolean | add (Object o) |
| |
synchronized boolean | addAll (Collection<?extends E > c) |
| |
synchronized void | clear () |
| |
Comparator< E > | comparator () |
Returns the comparator this set will use to compare nodes in the set. | |
boolean | contains (Object o) |
| |
boolean | containsAll (Collection<?> c) |
| |
E | first () |
| |
E | get (E item) |
Gets the given item in this set if it exists. | |
SortedSet< E > | headSet (Object toElement) |
| |
boolean | isEmpty () |
| |
Iterator< E > | iterator () |
| |
E | last () |
| |
synchronized boolean | remove (Object o) |
| |
synchronized boolean | removeAll (Collection<?> c) |
| |
synchronized void | resort (E item) |
Re-sorts the given item into the set, updating its sort key based on its current state. | |
synchronized boolean | retainAll (Collection<?> c) |
| |
int | size () |
| |
SortedSet< E > | subSet (E fromElement, E toElement) |
| |
SortedSet< E > | tailSet (E fromElement) |
| |
synchronized Object[] | toArray () |
| |
Object[] | toArray (Object[] a) |
| |
Package Functions | |
Comparator< SetNode< E > > | internalComparator () |
Returns a comparator over set nodes. | |
Package Attributes | |
TreeSet< SetNode< E > > | nodes |
The sorted treeset containing the set nodes. | |
KeyFunctor< E > | functor |
The functor we use to generate a sort key from each object in the set. | |
Private Attributes | |
HashMap< E, SetNode< E > > | mappings |
The mapping between the items being managed in the list and the nodes containing them. | |
Classes | |
class | SetNode< T > |
Represents an individual node in the sorted set. More... |
edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.MutableSortedSet | ( | KeyFunctor< E > | func | ) |
Constructs a MutableSortedSet with the given KeyFunctor.
func | the functor that will be used to generate keys when objects are added |
synchronized boolean edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.add | ( | Object | o | ) |
synchronized boolean edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.addAll | ( | Collection<?extends E > | c | ) |
synchronized void edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.clear | ( | ) |
Comparator<E> edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.comparator | ( | ) |
Returns the comparator this set will use to compare nodes in the set.
boolean edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.contains | ( | Object | o | ) |
boolean edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.containsAll | ( | Collection<?> | c | ) |
E edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.first | ( | ) |
E edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.get | ( | E | item | ) |
Gets the given item in this set if it exists.
Otherwise, return null.
item | the item to get |
SortedSet<E> edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.headSet | ( | Object | toElement | ) |
boolean edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.isEmpty | ( | ) |
Iterator<E> edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.iterator | ( | ) |
E edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.last | ( | ) |
synchronized boolean edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.remove | ( | Object | o | ) |
synchronized boolean edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.removeAll | ( | Collection<?> | c | ) |
synchronized void edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.resort | ( | E | item | ) |
Re-sorts the given item into the set, updating its sort key based on its current state.
item | the item to re-sort |
synchronized boolean edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.retainAll | ( | Collection<?> | c | ) |
int edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.size | ( | ) |
SortedSet<E> edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.subSet | ( | E | fromElement, | |
E | toElement | |||
) |
SortedSet<E> edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.tailSet | ( | E | fromElement | ) |
synchronized Object [] edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.toArray | ( | ) |
Object [] edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.toArray | ( | Object[] | a | ) |
Comparator<SetNode<E> > edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.internalComparator | ( | ) | [package] |
Returns a comparator over set nodes.
TreeSet<SetNode<E> > edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.nodes [package] |
The sorted treeset containing the set nodes.
KeyFunctor<E> edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.functor [package] |
The functor we use to generate a sort key from each object in the set.
HashMap<E, SetNode<E> > edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.mappings [private] |
The mapping between the items being managed in the list and the nodes containing them.