|Home >> All|
|||Util.Collections.* (49)||||Util.Graphs.* (8)||||Util.IO.* (5)||||Util.Templates.* (4)|
Util: Javadoc index of package Util.
MultiMap: MultiMap maps a key to a collection of values. These collections are created as needed using a CollectionFactory . Any constraints on the collections produced by this factory thus hold for the values that this maps to. Formally, a MultiMap is a Multiple Associative Container . It associates key objects with value objects. The difference between a MultiMap and a standard Map is that MultiMap extends the Map interface to allow for the same key to map to multiple values. Thus, the type signature for a MultiMap is :: Map[keytype -> [valtype] ] Note that an association (known as a (Key, Value) pair ...
BitString: BitString implements a vector of bits much like java.util.BitSet , except that this implementation actually works. Also, BitString has some groovy features which BitSet doesn't; mostly related to efficient iteration over true and false components. Each component of the BitString has a boolean value. The bits of a BitString are indexed by non-negative integers (that means they are zero-based, of course). Individual indexed bits can be examined, set, or cleared. One BitString may be used to modify the contents of another BitString through logical AND, logical inclusive OR, and logical exclusive OR ...
SCComponent: SCComponent models a Strongly connected component \ of a graph. The only way to split a graph into SCComponent s is though buildSSC . That method is quite flexible: all it needs is a root node (or a set of root nodes) and a Navigator : an object implementing the Navigator interface that provides the edges coming into/going out of a given Object . So, it can build strongly connected components even for graphs that are not built up from CFGraphable nodes, a good example being the set of methods where the edges represent the caller-callee relation (in this case, the strongly connected components group ...
InvertibleMap: An InvertibleMap is an extension of the Map interface to allow users to do reverse lookups on the mappings maintained. Since Map s are allowed to map multiple keys to a single value, the inversion of a Map is not necessarily a Map itself; thus we return a MultiMap for the inverted view. The returned MultiMap is not guaranteed to be modfiable, even if this is (ie, changes to the data structure may still have to be made through this rather than directly to the returned MultiMap ).
GenericMultiMap: GenericMultiMap is a default implementation of a MultiMap . FSK: right now the implementation tries to preserve the property that if a key 'k' maps to an empty collection 'c' in some MultiMap 'mm', then users of 'mm' will not be able to see that 'k' is a member of the keySet for 'mm'. However, it does not preserve this property when mm.getValues(k) is used as a means to operate on the state of 'mm', and it is not clear to me whether one can even ensure that the property can be maintained if arbitrary operations on mm.getValues(k) are passed on to 'mm'.
FilterIterator: A FilterIterator filters and maps a source Iterator to generate a new one. Note that this implementation reads one element ahead, so if the Filter changes for an object 'o' between the time that is read (when next() is called, returning the object preceding 'o', and checking that 'o' satisfies the current Filter) and the time when hasNext() is called, 'o' will still be returned, regardless of what Filter.isElement(o) returns. Thus, it is recommended that only Filters which remain consistent throughout the iteration be used.
PairMapEntry: PairMapEntry is the easiest implementation of a Map.Entry ever: a pair! Basically saves coders the drugery of writing an inner class at the expense of an import statement. Note that PairMapEntry s are mutable: setValue(Object) is defined in this class. Using null as a key or value will not cause this class or AbstractMapEntry to fail, but be warned that several Map implementations do not like null s in their internal structures.
MapFactory: MapFactory is a Map generator. Subclasses should implement constructions of specific types of Map s. Note also that the current limitations on parametric types in Java mean that we can't easily type this class as MapFactory<M extends Map<K,V>,K,V> , as MapFactory<HashMap<K,V>,K,V> is not a subtype of MapFactory<Map<K,V>,K,V> , even though HashMap is a subtype of Map .
InvertibleMultiMap: An InvertibleMultiMap is an extension of the MultiMap interface to allow users to do reverse lookups on the mappings maintained. If, for MultiMap m , m.contains(a, b) , then m.invert().contains(b, a) . If the InvertibleMultiMap is mutable, the InvertibleMultiMap returned by its invert() method should also be mutable. Moreover, for any InvertibleMultiMap , this.invert().invert()==this .
CollectionFactory: CollectionFactory is a Collection generator. Subclasses should implement constructions of specific types of Collection s. Note that since some types of Collection s have implicit constraints (such as Set s, which cannot contain more than one of the same element), code which uses the classes produced by CollectionFactory s must take care not to assume more than what is guaranteed by the Collection interface.
BinHeapPriorityQueue: BinHeapPriorityQueue is an implementation of the PriorityQueue interface. It supports O(1) time peekMax and O(lg n) time insert and removeMax operations, assuming that ArrayList is implemented in a reasonable manner. The remove operation is probably slow however. Look into implementing a FibonacciHeap-based representation if speed becomes an issue.
MaxPriorityQueue: MaxPriorityQueue maintains a Collection of Object s, each with an associated priority. Implementations should make the peekMax and removeMax operations efficient. Implementations need not implement the Object-addition operations of the Collection interface, since they do not associate each added Object with a priority.
Navigator: The Navigator interface allows graph algorithms to detect (and use) the arcs from and to a certain node. This allows the use of many graph algorithms (eg construction of strongly connected components) even for very general graphs where the arcs model only a subtle semantic relation (eg caller-callee) that is not directly stored in the structure of the nodes.
AbstractMapEntry: An AbstractMapEntry takes care of most of the grunge work involved in subclassing java.util.Map.Entry . For an immutable entry, you need only implement getKey() and getValue() . For a modifiable entry, you must also implement setValue() ; the default implementation throws an UnsupportedOperationException .
BinaryRelation: BinaryRelation represents a predicate on a 2-tuple. It maps a set of pairs to a boolean. Often BinaryRelation s will be constrained in terms of what types of arguments they accept; take care in documenting what requirements your BinaryRelation needs. Examples of BinaryRelation s include "less than" ( < ) and "equals" ( == ).
CollectionWrapper: CollectionWrapper is a class that acts as a wrapper around another Collection, using it as its backing store. This class isn't meant for direct usage, but rather provides for an easy way for developers to quickly add extra independent behavior to their own specific Collections without having to reimplement all of AbstractCollection's interface
GenericInvertibleMultiMap: GenericInvertibleMultiMap is a default implementation of InvertibleMultiMap . It returns modifiable inverted views of the mappings it maintains. Note that a GenericInvertibleMultiMap can directly replace a GenericInvertibleMap , because MultiMap correctly extends Map .
SCCTopSortedGraph: SCCTopSortedGraph represents a graph of strongly connected components topologically sorted in decreasing order. To obtain such a graph, use the topSort static method. It uses a Depth First Search to do the sortting in linear time (see Section 23.4 in Cormen and co for the exact algorithm).
UnmodifiableListIterator: UnmodifiableListIterator is an abstract superclass to save you the trouble of implementing the remove() method over and over again for those iterators which don't implement it. The name's a bit clunky, but fits with the JDK naming in java.util.Collections and etc.
UnmodifiableIterator: UnmodifiableIterator is an abstract superclass to save you the trouble of implementing the remove() method over and over again for those iterators which don't implement it. The name's a bit clunky, but fits with the JDK naming in java.util.Collections and etc.
Relation: Relation is a mathematical relation, accepting one to many and many to one mappings. It is similar to harpoon.Util.Collections.MultiMap but it is intended to be simpler and better tailored for the implementation of the Pointer Analysis algorithm.
ListFactory: ListFactory is a List generator. Subclasses should implement constructions of specific types of List s. ListFactory also has a set of static helper methods for building List objects.
MultiMapSet: A MultiMapSet is a java.util.Set of Map.Entry s which can also be accessed as a MultiMap . Use the entrySet() method of the MultiMap to get back the MultiMapSet .
HashWorklist: A worklist with a backing hash set to determine if an item is/was already on the list. Careful: Although this implements java.util.Set, it does not obey the hashCode() and equals() contract for Set. It obeys the contract for java.util.List instead.
MapSet: A MapSet is a java.util.Set of Map.Entry s which can also be accessed as a java.util.Map . Use the entrySet() method of the Map to get back the MapSet .