edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E > Class Reference

Collaboration diagram for edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >:

Collaboration graph
[legend]
List of all members.

Detailed Description

Implements a sorted set that allows sorting on any arbitrary key that can be derived from the data of the objects in the set.

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.

Author:
Brian Ellis


Public Member Functions

 MutableSortedSet (KeyFunctor< E > func)
 Constructs a MutableSortedSet with the given KeyFunctor.
synchronized boolean add (Object o)
 
See also:
java.util.Set.add(java.lang.Object)

synchronized boolean addAll (Collection<?extends E > c)
 
See also:
java.util.Set.addAll(java.util.Collection)

synchronized void clear ()
 
See also:
java.util.Set.clear()

Comparator< E > comparator ()
 Returns the comparator this set will use to compare nodes in the set.
boolean contains (Object o)
 
See also:
java.util.Set.contains(java.lang.Object)

boolean containsAll (Collection<?> c)
 
See also:
java.util.Set.containsAll(java.util.Collection)

first ()
 
See also:
java.util.SortedSet.first()

get (E item)
 Gets the given item in this set if it exists.
SortedSet< E > headSet (Object toElement)
 
See also:
java.util.SortedSet.headSet(java.lang.Object)

boolean isEmpty ()
 
See also:
java.util.Set.isEmpty()

Iterator< E > iterator ()
 
See also:
java.util.Set.iterator()

last ()
 
See also:
java.util.SortedSet.last()

synchronized boolean remove (Object o)
 
See also:
java.util.Set.remove(java.lang.Object)

synchronized boolean removeAll (Collection<?> c)
 
See also:
java.util.Set.removeAll(java.util.Collection)

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)
 
See also:
java.util.Set.retainAll(java.util.Collection)

int size ()
 
See also:
java.util.Set.size()

SortedSet< E > subSet (E fromElement, E toElement)
 
See also:
java.util.SortedSet.subSet(java.lang.Object, java.lang.Object)

SortedSet< E > tailSet (E fromElement)
 
See also:
java.util.SortedSet.tailSet(java.lang.Object)

synchronized Object[] toArray ()
 
See also:
java.util.Set.toArray()

Object[] toArray (Object[] a)
 
See also:
java.util.Set.toArray(T[])


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...


Constructor & Destructor Documentation

edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.MutableSortedSet ( KeyFunctor< E >  func  ) 

Constructs a MutableSortedSet with the given KeyFunctor.

Parameters:
func the functor that will be used to generate keys when objects are added


Member Function Documentation

synchronized boolean edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.add ( Object  o  ) 

See also:
java.util.Set.add(java.lang.Object)

synchronized boolean edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.addAll ( Collection<?extends E >  c  ) 

See also:
java.util.Set.addAll(java.util.Collection)

synchronized void edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.clear (  ) 

See also:
java.util.Set.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.

See also:
SortedSet.comparator()

boolean edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.contains ( Object  o  ) 

See also:
java.util.Set.contains(java.lang.Object)

boolean edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.containsAll ( Collection<?>  c  ) 

See also:
java.util.Set.containsAll(java.util.Collection)

E edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.first (  ) 

See also:
java.util.SortedSet.first()

E edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.get ( item  ) 

Gets the given item in this set if it exists.

Otherwise, return null.

Parameters:
item the item to get
Returns:
the item if it is found, null otherwise

SortedSet<E> edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.headSet ( Object  toElement  ) 

See also:
java.util.SortedSet.headSet(java.lang.Object)

boolean edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.isEmpty (  ) 

See also:
java.util.Set.isEmpty()

Iterator<E> edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.iterator (  ) 

See also:
java.util.Set.iterator()

E edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.last (  ) 

See also:
java.util.SortedSet.last()

synchronized boolean edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.remove ( Object  o  ) 

See also:
java.util.Set.remove(java.lang.Object)

synchronized boolean edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.removeAll ( Collection<?>  c  ) 

See also:
java.util.Set.removeAll(java.util.Collection)

synchronized void edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.resort ( item  ) 

Re-sorts the given item into the set, updating its sort key based on its current state.

Parameters:
item the item to re-sort

synchronized boolean edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.retainAll ( Collection<?>  c  ) 

See also:
java.util.Set.retainAll(java.util.Collection)

int edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.size (  ) 

See also:
java.util.Set.size()

SortedSet<E> edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.subSet ( fromElement,
toElement 
)

See also:
java.util.SortedSet.subSet(java.lang.Object, java.lang.Object)

SortedSet<E> edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.tailSet ( fromElement  ) 

See also:
java.util.SortedSet.tailSet(java.lang.Object)

synchronized Object [] edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.toArray (  ) 

See also:
java.util.Set.toArray()

Object [] edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.toArray ( Object[]  a  ) 

See also:
java.util.Set.toArray(T[])

Comparator<SetNode<E> > edu.cmu.hcii.calo.model.sorting.MutableSortedSet< E >.internalComparator (  )  [package]

Returns a comparator over set nodes.

Returns:
a comparator over set nodes.


Member Data Documentation

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.


The documentation for this class was generated from the following file:
Generated on Mon Aug 13 15:06:18 2007 for CALO by  doxygen 1.5.2