

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object jpaul.DataStructs.Relation<K,V>
public abstract class Relation<K,V>
Relation
is a binary relation, accepting one to many
and many to one mappings.
Unless otherwise specified a relation is modifiable and threadUNsafe. Similar to the Collection framework, we provide unmodifiable and threadsafe wrappers:
Nested Class Summary  

static interface 
Relation.EntryVisitor<Key,Value>
Relation.EntryVisitor is a wrapper for a function
that is called on a relation entry of the form
<key,value> . 
Constructor Summary  

Relation()

Method Summary  

protected abstract java.util.Set<V> 
_getValues(K key)
Method used by the internal implementation of the Relation or its subclasses. 

abstract boolean 
add(K key,
V value)
Adds the pair <key, value> to the relation. 

abstract boolean 
addAll(K key,
java.util.Collection<V> values)
Puts key in relation to each element of the
collection values . 

abstract boolean 
addAll2(K key,
java.util.Collection<? extends V> values)
Similar to addAll(K, java.util.Collection except that the type of the
collection values allows more flexibility. 

abstract void 
clear()
Removes all mappings stored in this relation. 

Relation<K,V> 
clone()


boolean 
contains(K key,
V value)
Checks the existence of the relation <key,value> . 

boolean 
containsAll(K key,
java.util.Collection<? extends V> values)
Checks the existence of the relation between key
and every element from values . 

abstract boolean 
containsKey(K key)
Checks the existence of the key key in this relation. 

abstract boolean 
equals(java.lang.Object o)
Checks the equality of two relations 

void 
forAllEntries(Relation.EntryVisitor<K,V> visitor)
Visits all the entries <key,value> of
this relation and calls
visitor.visit on each of them. 

java.util.Set<V> 
getValues(K key)
Returns the image of key through this relation. 

abstract boolean 
isEmpty()
Tests if this relation is empty or not. 

boolean 
isFunction()
Checks whether this relation maps each key to a
single value. 

abstract java.util.Set<K> 
keys()
Returns an IMMUTABLE view of all the keys appearing in this relation. 

abstract boolean 
remove(K key,
V value)
Removes the relation between key and
value . 

abstract boolean 
removeAll(K key,
java.util.Collection<V> values)
Removes the relation between key and
any element from values . 

abstract boolean 
removeKey(K key)
Removes all the relations attached to key . 

abstract boolean 
removeKeys(Predicate<K> predicate)
Removes all the keys that satisfy predicate.check() . 

abstract boolean 
removeValues(Predicate<V> predicate)
Removes all the values that satisfy predicate.check() . 

Relation<V,K> 
revert()
Return a relation that is the reverse of this
relation. 

Relation<V,K> 
revert(Relation<V,K> result)
Revert this relation and store the result into
the relation result . 

int 
size()
Returns the number of <key,value> pairs in this relation. 

static

synchronizedRelation(Relation<K,V> rel)
Returns a synchronized (threadsafe) relation wrapper backed by the given relation rel . 

java.lang.String 
toString()
Prettyprint function for debug. 

abstract boolean 
union(Relation<K,V> rel)
Combines this relation with relation
rel . 

static

unmodifiableRelation(Relation<K,V> rel)
Returns an unmodifiable wrapper backed by the given relation rel . 

abstract java.lang.Iterable<V> 
values()
Returns an IMMUTABLE view of all the values appearing in this relation. 
Methods inherited from class java.lang.Object 

finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait 
Constructor Detail 

public Relation()
Method Detail 

public abstract boolean add(K key, V value)
<key, value>
to the relation.
Returns true
if the new relation is bigger.
public abstract boolean addAll(K key, java.util.Collection<V> values)
key
in relation to each element of the
collection values
. Returns true
if
the relation becomes bigger.
public abstract boolean addAll2(K key, java.util.Collection<? extends V> values)
addAll(K, java.util.Collection)
except that the type of the
collection values
allows more flexibility. Puts
key
in relation to each element from the
collection values
. Returns true
if
the relation becomes bigger.
Only for the very curious users: A
legitimate question is "why two almost identical versions
of addAll
?" The answer has to do with speed
optimizations and historic reasons. In program analysis, it
is frequent to propagate large relations, with only the
mappings for a few keys being changed. Consequently,
jpaul
offers special CopyOnWrite
(COW) sets and other datastructures (see COWSetFactory
). For the rest of this
discussion, let's assume that key
is not in
relation with any value yet. The historically first version,
addAll(K, java.util.Collection
, allows the possible underlying set factory to
"clone" the COW set values
(if
values
is indeed a COW set). "Cloning" a COW
datastructure is very fast, and consumes almost no memory at
all, leading to enormous speedups (e.g., in Alex Salcianu's
pointer analysis prototype). Unfortunately, cloning in the
presence of wildcards would violate type safety: cloning a
Set<? extends V>
does not produce a
Set<V>
. Instead, the usual implementations
of addAll2(K, java.util.Collection)
work by creating a brandnew
Set<V>
and adding the new values to it,
onebyone. Retrospectively, the design could have been
better, but we didn't want to do anything that would break the
performances of the applications that already use
jpaul
.
public abstract void clear()
this
relation.
public abstract boolean remove(K key, V value)
key
and
value
.
true
iff the relation changedpublic abstract boolean removeAll(K key, java.util.Collection<V> values)
key
and
any element from values
.
true
iff the relation changedpublic abstract boolean removeKey(K key)
key
.
true
iff the relation changedpublic abstract boolean removeKeys(Predicate<K> predicate)
predicate.check()
.
true
iff the relation changedpublic abstract boolean removeValues(Predicate<V> predicate)
predicate.check()
.
true
iff the relation changedpublic boolean contains(K key, V value)
<key,value>
.
public boolean containsAll(K key, java.util.Collection<? extends V> values)
key
and every element from values
.
public abstract boolean containsKey(K key)
key
key in this relation.
public abstract boolean isEmpty()
public final java.util.Set<V> getValues(K key)
key
through this relation.
The returned collection IS IMMUTABLE.
Returns Collections.emptySet()
if no value is attached to key
.
protected abstract java.util.Set<V> _getValues(K key)
Relation
or its subclasses. Similar to the
userlevel getValues(K)
but the returned set IS MUTABLE.
Mutating this set affects the set of values that are
associated with a given key; therefore, this method cannot be
used by Relation
clients directly.
public abstract java.util.Set<K> keys()
this
relation. If you want to delete a key, then
use removeKey(K)
.
public abstract java.lang.Iterable<V> values()
this
relation. The view may contain the same
value twice, if it is associated with two distinct keys.
public abstract boolean union(Relation<K,V> rel)
this
relation with relation
rel
. A null
parameter is considered
to be an empty relation.
true
iff this
relation has
changed.public abstract boolean equals(java.lang.Object o)
equals
in class java.lang.Object
public void forAllEntries(Relation.EntryVisitor<K,V> visitor)
<key,value>
of
this
relation and calls
visitor.visit
on each of them. This traversal of
the relation entries can be stopped at any point by throwing
an InterruptTraversalException
from the visitor; the exception
is caught internally by the implementation of this method.
public Relation<V,K> revert()
this
relation. The reverse relation contains a pair <a,b>
iff this
relation contains the pair <b,a>.
Once created, the reverse relation is independent of this
relation: mutation on one of them will not affect the other
one. The reverse relation is represented as a
hashset/hashmapbased MapSetRelation
.
Warning: This default representation may
be very inefficient for small relations. If speed is an
issue, please use revert(Relation)
: it allows you to
create the revert relation, using your favorite Relation
implementation.
public Relation<V,K> revert(Relation<V,K> result)
this
relation and store the result into
the relation result
. <a,b> appears in the
reverse relation iff <b,a> appears in this
relation. Returns the new relation (ie,
result
).
public int size()
this
relation. Linear in the size of the
relation. This may be also implemented in O(1) by
incrementally updating a size
field, but that may
complicate the code in the presence of subclassing, etc. Will
think about it if it becomes a problem.
public boolean isFunction()
this
relation maps each key to a
single value. Mathematically, checks whether this relation is
a (partial) function.
public Relation<K,V> clone()
clone
in class java.lang.Object
public java.lang.String toString()
rel1.equals(rel2) <==> rel1.toString().equals(rel2.toString())
toString
in class java.lang.Object
public static <K,V> Relation<K,V> unmodifiableRelation(Relation<K,V> rel)
rel
. This allows "readonly" access, although
changes in the backing collection show up in this view.
Attempts to modify the relation will fail with UnsupportedOperationException
.
public static <K,V> Relation<K,V> synchronizedRelation(Relation<K,V> rel)
rel
. Each operation
synchronizes on rel
.
For operations that return a collection (e.g., keys()
, values()
), it is strongly recommended to
synchronize the whole block that (1) invokes the
collectionreturning relation operation, and (2) uses that
collection. This is similar to the recommended usage pattern
for the JDK synchronized collections (e.g.,
Collections.synchronizedSet
. Here is an example:
Relation<K,V> syncRel = Relation.synchronizedRelation(someRel); ... synchronized(syncRel) { Iterator<K> it = syncRel.keys().iterator(); while(it.hasNext()) { K key = it.next(); ... } }This pattern prevents nondeterministic, hardtoreproduce behavior due to modifications from other threads on the relation you iterate over.


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 