edu.rice.cs.plt.collect
Class IndexedRelation<T1,T2>

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractSet<T>
          edu.rice.cs.plt.collect.AbstractPredicateSet<Pair<T1,T2>>
              edu.rice.cs.plt.collect.AbstractRelation<T1,T2>
                  edu.rice.cs.plt.collect.IndexedRelation<T1,T2>

All Implemented Interfaces:

PredicateSet<Pair<T1,T2>>, Relation<T1,T2>, SizedIterable<Pair<T1,T2>>, Predicate<java.lang.Object>, Predicate2<T1,T2>, java.io.Serializable, java.lang.Iterable<Pair<T1,T2>>, java.util.Collection<Pair<T1,T2>>, java.util.Set<Pair<T1,T2>>

public class IndexedRelation<T1,T2>
extends AbstractRelation<T1,T2>
implements java.io.Serializable

An implementation of the Relation interface based on indexing maps.

See Also:

Serialized Form

Nested Class Summary

Nested classes/interfaces inherited from class edu.rice.cs.plt.collect.AbstractRelation

AbstractRelation.InverseRelation

Constructor Summary

IndexedRelation()
Index in both directions using HashMaps and HashSets.

IndexedRelation(boolean indexSecond)
Index using HashMaps and HashSets.

IndexedRelation(Thunk<java.util.Map<T1,PredicateSet<T2>>> firstIndexFactory, Thunk<java.util.Set<T2>> firstIndexEntryFactory)
Create an index based on the given factories.

IndexedRelation(Thunk<java.util.Map<T1,PredicateSet<T2>>> firstIndexFactory, Thunk<java.util.Set<T2>> firstIndexEntryFactory, Thunk<java.util.Map<T2,PredicateSet<T1>>> secondIndexFactory, Thunk<java.util.Set<T1>> secondIndexEntryFactory)
Create indices based on the given factories.

Method Summary

boolean	add(T1 first, T2 second) Add Pair.make(first, second) to the set.
void	clear()
boolean	contains(java.lang.Object obj) Test whether the set contains an object.
boolean	contains(T1 first, T2 second) Tests whether the given objects appear as a pair in this relation.
PredicateSet<T1>	firstSet() The set of firsts.
boolean	hasFixedSize() true if this iterable is known to have a fixed size.
boolean	isEmpty() Returns size(1) == 0.
boolean	isInfinite() true if the iterable is known to have infinite size.
boolean	isStatic() true if this iterable is unchanging.
java.util.Iterator<Pair<T1,T2>>	iterator()
static <T1,T2> IndexedRelation<T1,T2>	makeHashBased() Make an IndexedRelation indexed by HashMaps and HashSets.
static <T1,T2> IndexedRelation<T1,T2>	makeLinkedHashBased() Make an IndexedRelation indexed by LinkedHashMaps and LinkedHashSets.
static <T1 extends java.lang.Comparable<? super T1>,T2 extends java.lang.Comparable<? super T2>> IndexedRelation<T1,T2>	makeTreeBased() Make an IndexedRelation indexed by TreeMaps and TreeSets.
PredicateSet<T2>	matchFirst(T1 first) The set of seconds corresponding to a specific first.
PredicateSet<T1>	matchSecond(T2 second) The set of firsts corresponding to a specific second.
boolean	remove(T1 first, T2 second) Remove Pair.make(first, second) from the set.
PredicateSet<T2>	secondSet() The set of seconds.
int	size() Returns size(Integer.MAX_VALUE).
int	size(int bound) Computes the size by traversing the iterator (requires linear time).

Methods inherited from class edu.rice.cs.plt.collect.AbstractRelation

add, containsFirst, containsSecond, excludeFirsts, excludeSeconds, inverse, remove

Methods inherited from class java.util.AbstractSet

equals, hashCode, removeAll

Methods inherited from class java.util.AbstractCollection

addAll, containsAll, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Set

addAll, containsAll, equals, hashCode, removeAll, retainAll, toArray, toArray

Constructor Detail

IndexedRelation

public IndexedRelation()

Index in both directions using HashMaps and HashSets.

IndexedRelation

public IndexedRelation(boolean indexSecond)

Index using HashMaps and HashSets. If indexSecond is false, no second-to-first index is created.

IndexedRelation

public IndexedRelation(Thunk<java.util.Map<T1,PredicateSet<T2>>> firstIndexFactory,
                       Thunk<java.util.Set<T2>> firstIndexEntryFactory,
                       Thunk<java.util.Map<T2,PredicateSet<T1>>> secondIndexFactory,
                       Thunk<java.util.Set<T1>> secondIndexEntryFactory)

Create indices based on the given factories.

Parameters:

firstIndexFactory - Maps firsts to sets of seconds.

firstIndexEntryFactory - Produces sets for the first-to-second index.

secondIndexFactory - Maps seconds to sets of firsts.

secondIndexEntryFactory - Produces sets for the second-to-first index.

IndexedRelation

public IndexedRelation(Thunk<java.util.Map<T1,PredicateSet<T2>>> firstIndexFactory,
                       Thunk<java.util.Set<T2>> firstIndexEntryFactory)

Create an index based on the given factories. No second-to-first index is created. (If only a second-to-first index is wanted, invoke this constructor and then invert the result.)

Parameters:

firstIndexFactory - Maps firsts to sets of seconds.

firstIndexEntryFactory - Produces sets for the first-to-second index.

Method Detail

isEmpty

public boolean isEmpty()

Description copied from class: AbstractPredicateSet

Returns size(1) == 0.

Specified by:

isEmpty in interface SizedIterable<Pair<T1,T2>>

Specified by:

isEmpty in interface java.util.Collection<Pair<T1,T2>>

Specified by:

isEmpty in interface java.util.Set<Pair<T1,T2>>

Overrides:

isEmpty in class AbstractPredicateSet<Pair<T1,T2>>

size

public int size()

Description copied from class: AbstractPredicateSet

Returns size(Integer.MAX_VALUE).

Specified by:

size in interface SizedIterable<Pair<T1,T2>>

Specified by:

size in interface java.util.Collection<Pair<T1,T2>>

Specified by:

size in interface java.util.Set<Pair<T1,T2>>

Overrides:

size in class AbstractPredicateSet<Pair<T1,T2>>

size

public int size(int bound)

Description copied from class: AbstractPredicateSet

Computes the size by traversing the iterator (requires linear time).

Specified by:

size in interface SizedIterable<Pair<T1,T2>>

Overrides:

size in class AbstractPredicateSet<Pair<T1,T2>>

Parameters:

bound - Maximum result. Assumed to be nonnegative.

isInfinite

public boolean isInfinite()

Description copied from interface: SizedIterable

true if the iterable is known to have infinite size. If true, an iterator over the iterable in its current state will never return false from hasNext().

Specified by:

isInfinite in interface SizedIterable<Pair<T1,T2>>

Specified by:

isInfinite in class AbstractRelation<T1,T2>

hasFixedSize

public boolean hasFixedSize()

Description copied from interface: SizedIterable

true if this iterable is known to have a fixed size. This is the case if the iterable is immutable, or if changes can only replace values, not remove or add them. An infinite iterable may be fixed if it is guaranteed to never become finite.

Specified by:

hasFixedSize in interface SizedIterable<Pair<T1,T2>>

Specified by:

hasFixedSize in class AbstractRelation<T1,T2>

isStatic

public boolean isStatic()

Description copied from interface: SizedIterable

true if this iterable is unchanging. This implies that hasFixedSize() is true, and that iterator() will always return the same (either == or equal() and immutable) elements in the same order. ("Immutable" here means that equals() invocations are consistent over time -- if two objects are equal, they will never become inequal, and vice versa.)

Specified by:

isStatic in interface SizedIterable<Pair<T1,T2>>

Specified by:

isStatic in class AbstractRelation<T1,T2>

contains

public boolean contains(T1 first,
                        T2 second)

Description copied from class: AbstractRelation

Tests whether the given objects appear as a pair in this relation. Not guaranteed to have types T1 and T2 because the Collection.contains(java.lang.Object) method allows arbitrary objects.

Specified by:

contains in interface Relation<T1,T2>

Specified by:

contains in interface Predicate2<T1,T2>

Specified by:

contains in class AbstractRelation<T1,T2>

contains

public boolean contains(java.lang.Object obj)

Description copied from class: AbstractPredicateSet

Test whether the set contains an object. Overridden here to force subclasses to provide an implementation. The default implementation (AbstractCollection.contains(java.lang.Object)) is a linear search, which is almost always unreasonable for a set.

Specified by:

contains in interface Relation<T1,T2>

Specified by:

contains in interface Predicate<java.lang.Object>

Specified by:

contains in interface java.util.Collection<Pair<T1,T2>>

Specified by:

contains in interface java.util.Set<Pair<T1,T2>>

Specified by:

contains in class AbstractRelation<T1,T2>

iterator

public java.util.Iterator<Pair<T1,T2>> iterator()

Specified by:

iterator in interface java.lang.Iterable<Pair<T1,T2>>

Specified by:

iterator in interface java.util.Collection<Pair<T1,T2>>

Specified by:

iterator in interface java.util.Set<Pair<T1,T2>>

Specified by:

iterator in class AbstractRelation<T1,T2>

firstSet

public PredicateSet<T1> firstSet()

Description copied from interface: Relation

The set of firsts. Need not allow mutation, but must reflect subsequent changes.

Specified by:

firstSet in interface Relation<T1,T2>

Specified by:

firstSet in class AbstractRelation<T1,T2>

matchFirst

public PredicateSet<T2> matchFirst(T1 first)

Description copied from interface: Relation

The set of seconds corresponding to a specific first. Need not allow mutation, but must reflect subsequent changes.

Specified by:

matchFirst in interface Relation<T1,T2>

Specified by:

matchFirst in class AbstractRelation<T1,T2>

secondSet

public PredicateSet<T2> secondSet()

Description copied from interface: Relation

The set of seconds. Need not allow mutation, but must reflect subsequent changes.

Specified by:

secondSet in interface Relation<T1,T2>

Specified by:

secondSet in class AbstractRelation<T1,T2>

matchSecond

public PredicateSet<T1> matchSecond(T2 second)

Description copied from interface: Relation

The set of firsts corresponding to a specific second. Need not allow mutation, but must reflect subsequent changes.

Specified by:

matchSecond in interface Relation<T1,T2>

Specified by:

matchSecond in class AbstractRelation<T1,T2>

add

public boolean add(T1 first,
                   T2 second)

Description copied from interface: Relation

Add Pair.make(first, second) to the set.

Specified by:

add in interface Relation<T1,T2>

Overrides:

add in class AbstractRelation<T1,T2>

remove

public boolean remove(T1 first,
                      T2 second)

Description copied from interface: Relation

Remove Pair.make(first, second) from the set.

Specified by:

remove in interface Relation<T1,T2>

Overrides:

remove in class AbstractRelation<T1,T2>

clear

public void clear()

Specified by:

clear in interface java.util.Collection<Pair<T1,T2>>

Specified by:

clear in interface java.util.Set<Pair<T1,T2>>

Overrides:

clear in class java.util.AbstractCollection<Pair<T1,T2>>

makeHashBased

public static <T1,T2> IndexedRelation<T1,T2> makeHashBased()

Make an IndexedRelation indexed by HashMaps and HashSets.

makeLinkedHashBased

public static <T1,T2> IndexedRelation<T1,T2> makeLinkedHashBased()

Make an IndexedRelation indexed by LinkedHashMaps and LinkedHashSets.

makeTreeBased

public static <T1 extends java.lang.Comparable<? super T1>,T2 extends java.lang.Comparable<? super T2>> IndexedRelation<T1,T2> makeTreeBased()

Make an IndexedRelation indexed by TreeMaps and TreeSets.