Package jpaul.DataStructs

Data structures for program analysis and not only.

See:
Description

Interface Summary

CollectionFactory<E>	CollectionFactory is a collection-specific instance of the factory pattern.
Factory<T>	Factory for the factory pattern.
Relation.EntryVisitor<Key,Value>	Relation.EntryVisitor is a wrapper for a function that is called on a relation entry of the form <key,value>.
WorkSet<T>	WorkSet is an ordered set-like data structure.

Class Summary

BijMap<A,B>	BijMap
CompoundIterable<A,B>	CompoundIterable allows the construction of an Iterable by merging several smaller Iterables.
DisjointSet<E>	DisjointSet is an implementation of disjoint-set forests using the path compression and union-by-rank heuristics to achieve O(m * alpha(m, n)) runtime, where 'm' is the total number of operations, 'n' is the total number of elements in the set, and 'alpha' denotes the *extremely* slowly-growing inverse Ackermann function.
DSUtil	DSUtil contains commonly used data-structure utilities.
MapFactory<K,V>	MapFactory is a map-specific instance of the factory pattern.
MapFacts	MapFacts contains several common map factories.
MapFacts.HashMapFactory<K,V>	Deprecated. As of jpaul 2.2, use MapFacts.hash() instead.
MapFacts.TreeMapFactory<K,V>	Deprecated. As of jpaul 2.2, use MapFacts.tree(Comparator) instead.
MapSetRelation<K,V>	MapSetRelation is an implementation of the Relation interface based on a Map from keys to Sets of values.
MapWithDefault<K,V>	MapWithDefault is a map that returns default values for unassigned keys.
MapWrapper<K,V>	MapWrapper is a map backed by another map.
NoCompTreeMap<K,V>	NoCompTreeMap is tree map that does not require any used-defined Comparator.
Pair<A,B>	Pair is an immutable pair of two values.
Relation<K,V>	Relation is a binary relation, accepting one to many and many to one mappings.
Relation3<Ta,Tb,Tc>	Relation3 models a simple ternary relation.
Relation3MapRelImpl<Ta,Tb,Tc>	Relation3MapRelImpl is a simple implementation of Relation3, backed by a Map from Ta keys to RelationTb,Tc between Tb and Tc.
RelationFactory<K,V>	RelationFactory is a relation-specific instance of the factory pattern.
RelFacts	RelFacts contains common relation factories.
RelFacts.COWRelationFactory<K,V>	Deprecated. As of jpaul 2.2, use RelFacts.cow(RelationFactory) instead.
RelFacts.MapSetRelationFactory<K,V>	Deprecated. As of jpaul 2.2, use RelFacts.mapSet() or RelFacts.mapSet(MapFactory,SetFactory) instead.
ReverseListIterator<E>	ReverseListIterator takes a List and produces a ListIterator that traverses the list in reverse order.
ReverseListView<E>	ReverseViewList is an immutable, reverse view of a List.
SetFactory<T>	SetFactory is a set-instance of the factory pattern.
SetFacts	SetFacts contains common set factories.
SetFacts.COWSetFactory<E>	Deprecated. As of jpaul 2.2, use SetFacts.cow(SetFactory) instead.
SetFacts.HashSetFactory<E>	Deprecated. As of jpaul 2.2, use SetFacts.hash() instead.
SetFacts.TreeSetFactory<E>	Deprecated. As of jpaul 2.2, use SetFacts.tree(Comparator) instead.
VerboseWorkSet<T>	VerboseWorkSet - Debugging wrapper for a WorkSet.
WorkList<T>	WorkList is a WorkSet with FIFO order.
WorkPriorityQueue<T>	WorkPriorityQueue is a WorkSet whose elements are extracted in the increasing order of their priorities.
WorkQueue<T>	WorkQueue
WorkStack<T>	WorkStack is a WorkSet with LIFO order.

Package jpaul.DataStructs Description

Data structures for program analysis and not only. Here is a brief overview:

• WorkSets (e.g., for fixed-point computations): WorkList, WorkSet, and WorkPriorityQueue.
• Classes and interfaces for the Factory Design Pattern: Factory and its (many) children. Using the factory design pattern allows the programmer to switch from one data structure implementation to another with minimal effort. Of special importance are the set and map factories from SetFacts and MapFacts.
• Binary and ternary relations: Relation, Relation3 and their children. These classes eliminate the need to manually handle maps to maps to sets, and provide other goodies too.
• Copy-On-Write data structures: see SetFacts.cow and RelFacts.cow. Represent a middle point between mutation-based java.util data structures and purely functional datastructures (such as those from jutil).
• Lots of useful static methods in DSUtil, many of them familiar to people with a functional programming background: map, filter etc.
• Map with default values for unassigned keys: MapWithDefault. This may be useful if the programmer wants a default value that is not null.
• The ever popular Pair: very often, we need to return more than one thing from a method. Returning an array of Objects loses type safety. Something like Pair<Integer,String> is far more informative.

Author:

Alexandru Salcianu - salcianu@alum.mit.edu