jpaul.DataStructs
Class SetFacts

java.lang.Object
  jpaul.DataStructs.SetFacts

public final class SetFacts
extends java.lang.Object

SetFacts contains common set factories. For each kind of set factory, we have a corresponding static method. Note: some old set factories that used to exist as separate classes are now static inner classes of this class. They are provided mostly to simplify porting old code (programmers only have to change a few import statements).

Version:

$Id: SetFacts.java,v 1.11 2006/03/14 02:29:31 salcianu Exp $

Author:

Alexandru Salcianu - salcianu@alum.mit.edu

Nested Class Summary

static class	SetFacts.COWSetFactory<E> Deprecated. As of jpaul 2.2, use cow(SetFactory) instead.
static class	SetFacts.HashSetFactory<E> Deprecated. As of jpaul 2.2, use hash() instead.
static class	SetFacts.TreeSetFactory<E> Deprecated. As of jpaul 2.2, use tree(Comparator) instead.

Method Summary

static <E> SetFactory<E>	cow(SetFactory<E> underSetFact) Returns a set factory that generates "copy-on-write" (COW) sets.
static <E> SetFactory<E>	hash() Returns a set factory that generates LinkedHashSets.
static <E> SetFactory<E>	mapBased(MapFactory<E,java.lang.Object> mapFact) Returns a set factory that generates map-backed sets.
static <E> SetFactory<E>	noCompTree() Returns a set factory that generates sets backed by NoCompTreeMaps.
static <E> SetFactory<E>	tree(java.util.Comparator<E> comp) Returns a set factory that generates TreeSets.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

hash

public static <E> SetFactory<E> hash()

Returns a set factory that generates LinkedHashSets. LinkedHashSets are great for applications that use a few large sets; in addition, they provide predictable iteration order (identical to the insertion order). A LinkedHashSet is only slightly slower than a HashSet (iteration is actually faster: linear in the actual size, independent of the capacity). Therefore, in the interest o simplicity, instead of offering a factory for plain HashSets, and a factory for LinkedHashSets, jpaul offers only the latter.

tree

public static <E> SetFactory<E> tree(java.util.Comparator<E> comp)

Returns a set factory that generates TreeSets. TreeSets are great for applications that use many small sets.

cow

public static <E> SetFactory<E> cow(SetFactory<E> underSetFact)

Returns a set factory that generates "copy-on-write" (COW) sets. A COW set shares its representation (also a set) with other COW sets, until a mutation occurs. At that moment, the COW set makes a private, exclusive copy of its underlying representation, and mutates that copy.

The internal representation of a COW set maintains a "sharing" counter to identify cases when the representation is not shared with anyone (and hence, no cloning is necessary before a mutation).

Cloning a COW set is a constant time operation. COW sets are good when it is hard to determine statically whether a clone of a set will be mutated: they delay the real cloning until the first mutation (if any).

Parameters:

underSetFact - Set factory for generating the sets used in the representation of the COW sets.

mapBased

public static <E> SetFactory<E> mapBased(MapFactory<E,java.lang.Object> mapFact)

Returns a set factory that generates map-backed sets. The elements from the set are the keys of the map; the values they are mapped to do not matter; in practice, the implementation will never use null keys, so virtually any map factory is good as argument.

Parameters:

mapFact - Factory for the maps used in the representation of the generated sets.

noCompTree

public static <E> SetFactory<E> noCompTree()

Returns a set factory that generates sets backed by NoCompTreeMaps. NoCompTreeMap is a binary tree-backed map that does not require a user-defined Comparator between keys. This set factory is good for applications that use many small trees and when a total order Comparator is hard to write.

See Also:

mapBased(jpaul.DataStructs.MapFactory)