Skip to content

Commit d3ca8d3

Browse files
author
dlsmith
committed
Added ObjectUtil. Implemented IterUtil.conditionalSnapshot and CollectUtil.conditionalSnapshot (with Composeable interface used for support); various CollectUtil methods.
git-svn-id: file:///tmp/test-svn/trunk@4532 fe72c1cf-3628-48e9-8b72-1c46755d3cff
1 parent 811484b commit d3ca8d3

66 files changed

Lines changed: 998 additions & 134 deletions

File tree

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎plt/src/edu/rice/cs/plt/collect/AbstractFunctionalRelation.java‎

Lines changed: 16 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -43,6 +43,7 @@ IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISI
4343
import edu.rice.cs.plt.iter.MappedIterator;
4444
import edu.rice.cs.plt.iter.EmptyIterator;
4545
import edu.rice.cs.plt.iter.MutableSingletonIterator;
46+
import edu.rice.cs.plt.object.ObjectUtil;
4647

4748
/**
4849
* An abstract parent class for implementations of FunctionalRelation. Subclasses must provide
@@ -71,11 +72,17 @@ public abstract class AbstractFunctionalRelation<T1, T2> extends AbstractRelatio
7172
public boolean hasFixedSize() { return functionMap().keySet().hasFixedSize(); }
7273

7374
/** Checks for the given entry in {@code functionMap()}. */
74-
protected boolean containsObjects(Object first, Object second) {
75+
public boolean contains(T1 first, T2 second) {
7576
LambdaMap<T1, T2> map = functionMap();
76-
if (map.containsKey(first)) {
77-
T2 val = map.get(first);
78-
return (second == null) ? (val == null) : second.equals(val);
77+
return map.containsKey(first) && ObjectUtil.equal(map.get(first), second);
78+
}
79+
80+
/** Checks for the given entry in {@code functionMap()}. */
81+
public boolean contains(Object obj) {
82+
if (obj instanceof Pair<?, ?>) {
83+
Pair<?, ?> p = (Pair<?, ?>) obj;
84+
LambdaMap<T1, T2> map = functionMap();
85+
return map.containsKey(p.first()) && ObjectUtil.equal(map.get(p.first()), p.second());
7986
}
8087
else { return false; }
8188
}
@@ -122,7 +129,9 @@ private final class MatchFirstSet extends AbstractPredicateSet<T2> implements Se
122129
public boolean hasFixedSize() { return AbstractFunctionalRelation.this.isStatic(); }
123130
public boolean isStatic() { return AbstractFunctionalRelation.this.isStatic(); }
124131

125-
public boolean contains(Object val) { return containsObjects(_key, val); }
132+
public boolean contains(Object val) {
133+
return AbstractFunctionalRelation.this.contains(Pair.make(_key, val));
134+
}
126135

127136
public Iterator<T2> iterator() {
128137
final LambdaMap<T1, T2> map = functionMap();
@@ -135,13 +144,13 @@ public Iterator<T2> iterator() {
135144
}
136145

137146
@Override public boolean add(T2 val) {
138-
boolean result = !containsObjects(_key, val);
147+
boolean result = !AbstractFunctionalRelation.this.contains(_key, val);
139148
if (result) { functionMap().put(_key, val); }
140149
return result;
141150
}
142151

143152
@Override public boolean remove(Object val) {
144-
boolean result = containsObjects(_key, val);
153+
boolean result = AbstractFunctionalRelation.this.contains(Pair.make(_key, val));
145154
if (result) { functionMap().remove(_key); }
146155
return result;
147156
}

‎plt/src/edu/rice/cs/plt/collect/AbstractInjectiveRelation.java‎

Lines changed: 17 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -43,6 +43,7 @@ IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISI
4343
import edu.rice.cs.plt.iter.MappedIterator;
4444
import edu.rice.cs.plt.iter.EmptyIterator;
4545
import edu.rice.cs.plt.iter.MutableSingletonIterator;
46+
import edu.rice.cs.plt.object.ObjectUtil;
4647

4748
/**
4849
* An abstract parent class for implementations of InjectiveRelation. Subclasses must provide
@@ -70,12 +71,18 @@ public abstract class AbstractInjectiveRelation<T1, T2> extends AbstractRelation
7071
/** Returns {@code injectionMap().keySet().hasFixedSize()}. */
7172
public boolean hasFixedSize() { return injectionMap().keySet().hasFixedSize(); }
7273

73-
/** Checks for the given entry in {@code injectionMap()}. */
74-
protected boolean containsObjects(Object first, Object second) {
74+
/** Checks for the given entry in {@code functionMap()}. */
75+
public boolean contains(T1 first, T2 second) {
7576
LambdaMap<T2, T1> map = injectionMap();
76-
if (map.containsKey(second)) {
77-
T1 val = map.get(second);
78-
return (first == null) ? (val == null) : first.equals(val);
77+
return map.containsKey(second) && ObjectUtil.equal(map.get(second), first);
78+
}
79+
80+
/** Checks for the given entry in {@code functionMap()}. */
81+
public boolean contains(Object obj) {
82+
if (obj instanceof Pair<?, ?>) {
83+
Pair<?, ?> p = (Pair<?, ?>) obj;
84+
LambdaMap<T2, T1> map = injectionMap();
85+
return map.containsKey(p.second()) && ObjectUtil.equal(map.get(p.second()), p.first());
7986
}
8087
else { return false; }
8188
}
@@ -122,7 +129,9 @@ private final class MatchSecondSet extends AbstractPredicateSet<T1> implements S
122129
public boolean hasFixedSize() { return AbstractInjectiveRelation.this.isStatic(); }
123130
public boolean isStatic() { return AbstractInjectiveRelation.this.isStatic(); }
124131

125-
public boolean contains(Object val) { return containsObjects(val, _key); }
132+
public boolean contains(Object val) {
133+
return AbstractInjectiveRelation.this.contains(Pair.make(val, _key));
134+
}
126135

127136
public Iterator<T1> iterator() {
128137
final LambdaMap<T2, T1> map = injectionMap();
@@ -135,13 +144,13 @@ public Iterator<T1> iterator() {
135144
}
136145

137146
@Override public boolean add(T1 val) {
138-
boolean result = !containsObjects(val, _key);
147+
boolean result = !AbstractInjectiveRelation.this.contains(val, _key);
139148
if (result) { injectionMap().put(_key, val); }
140149
return result;
141150
}
142151

143152
@Override public boolean remove(Object val) {
144-
boolean result = containsObjects(val, _key);
153+
boolean result = AbstractInjectiveRelation.this.contains(Pair.make(val, _key));
145154
if (result) { injectionMap().remove(_key); }
146155
return result;
147156
}

‎plt/src/edu/rice/cs/plt/collect/AbstractOneToOneRelation.java‎

Lines changed: 5 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -88,7 +88,9 @@ private final class MatchSecondSet extends AbstractPredicateSet<T1> implements S
8888
public boolean hasFixedSize() { return AbstractOneToOneRelation.this.isStatic(); }
8989
public boolean isStatic() { return AbstractOneToOneRelation.this.isStatic(); }
9090

91-
public boolean contains(Object val) { return containsObjects(val, _key); }
91+
public boolean contains(Object val) {
92+
return AbstractOneToOneRelation.this.contains(Pair.make(val, _key));
93+
}
9294

9395
public Iterator<T1> iterator() {
9496
final LambdaMap<T2, T1> map = injectionMap();
@@ -101,13 +103,13 @@ public Iterator<T1> iterator() {
101103
}
102104

103105
@Override public boolean add(T1 val) {
104-
boolean result = !containsObjects(val, _key);
106+
boolean result = !AbstractOneToOneRelation.this.contains(val, _key);
105107
if (result) { injectionMap().put(_key, val); }
106108
return result;
107109
}
108110

109111
@Override public boolean remove(Object val) {
110-
boolean result = containsObjects(val, _key);
112+
boolean result = AbstractOneToOneRelation.this.contains(Pair.make(val, _key));
111113
if (result) { injectionMap().remove(_key); }
112114
return result;
113115
}

‎plt/src/edu/rice/cs/plt/collect/AbstractRelation.java‎

Lines changed: 8 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -43,11 +43,11 @@ IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISI
4343
/**
4444
* An abstract parent class for implementations of Relation. Subclasses must provide
4545
* the size methods {@link #isInfinite}, {@link #hasFixedSize}, and {@link #isStatic},
46-
* and the query methods {@link #containsObjects}, {@link #iterator},
47-
* {@link #firstSet}, {@link #matchFirst}, {@link #secondSet}, and {@link #matchSecond}.
48-
* To support mutation, they must also override {@link #add(Object, Object)} and
49-
* {@link #remove(Object, Object)}. For best performance, they may also override
50-
* {@link #isEmpty}, {@link #size(int)} and {@link #clear}.
46+
* and the query methods {@link #contains(Object, Object)}, {@link #contains(Object)},
47+
* {@link #iterator}, {@link #firstSet}, {@link #matchFirst}, {@link #secondSet},
48+
* and {@link #matchSecond}. To support mutation, they must also override
49+
* {@link #add(Object, Object)} and {@link #remove(Object, Object)}. For best performance,
50+
* they may also override {@link #isEmpty}, {@link #size(int)} and {@link #clear}.
5151
*/
5252
public abstract class AbstractRelation<T1, T2> extends AbstractPredicateSet<Pair<T1, T2>>
5353
implements Relation<T1, T2> {
@@ -61,7 +61,8 @@ public abstract class AbstractRelation<T1, T2> extends AbstractPredicateSet<Pair
6161
* to have types {@code T1} and {@code T2} because the {@link java.util.Collection#contains}
6262
* method allows arbitrary objects.
6363
*/
64-
protected abstract boolean containsObjects(Object first, Object second);
64+
public abstract boolean contains(T1 first, T2 second);
65+
public abstract boolean contains(Object obj);
6566
public abstract Iterator<Pair<T1, T2>> iterator();
6667
public abstract PredicateSet<T1> firstSet();
6768
public abstract PredicateSet<T2> matchFirst(T1 first);
@@ -70,19 +71,7 @@ public abstract class AbstractRelation<T1, T2> extends AbstractPredicateSet<Pair
7071

7172
public boolean add(T1 first, T2 second) { throw new UnsupportedOperationException(); }
7273
public boolean remove(T1 first, T2 second) { throw new UnsupportedOperationException(); }
73-
74-
/** Invokes {@link #containsObjects} if the argument is a pair. */
75-
public boolean contains(Object o) {
76-
if (o instanceof Pair<?, ?>) {
77-
Pair<?, ?> p = (Pair<?, ?>) o;
78-
return containsObjects(p.first(), p.second());
79-
}
80-
else { return false; }
81-
}
82-
83-
/** Invokes {@link #containsObjects}. */
84-
public boolean contains(T1 first, T2 second) { return containsObjects(first, second); }
85-
74+
8675
/** Invokes {@link #add(Object, Object)}. */
8776
public boolean add(Pair<T1, T2> p) { return add(p.first(), p.second()); }
8877

‎plt/src/edu/rice/cs/plt/collect/CartesianRelation.java‎

Lines changed: 15 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -38,14 +38,16 @@ IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISI
3838
import java.util.Iterator;
3939
import java.io.Serializable;
4040
import edu.rice.cs.plt.tuple.Pair;
41+
import edu.rice.cs.plt.object.Composite;
42+
import edu.rice.cs.plt.object.ObjectUtil;
4143
import edu.rice.cs.plt.iter.CartesianIterator;
4244
import edu.rice.cs.plt.iter.EmptyIterator;
4345

4446
/**
4547
* A Relation representing the cartesian (or cross) product of two sets. Does not support mutation,
4648
* but the contents are updated dynamically as the given sets change.
4749
*/
48-
public class CartesianRelation<T1, T2> extends AbstractRelation<T1, T2> implements Serializable {
50+
public class CartesianRelation<T1, T2> extends AbstractRelation<T1, T2> implements Composite, Serializable {
4951

5052
private final PredicateSet<T1> _firstSet;
5153
private final PredicateSet<T2> _secondSet;
@@ -55,6 +57,9 @@ public CartesianRelation(Set<? extends T1> firsts, Set<? extends T2> seconds) {
5557
_secondSet = new ImmutableSet<T2>(seconds);
5658
}
5759

60+
public int compositeHeight() { return ObjectUtil.compositeHeight(_firstSet, _secondSet) + 1; }
61+
public int compositeSize() { return ObjectUtil.compositeSize(_firstSet, _secondSet) + 1; }
62+
5863
@Override public int size(int bound) {
5964
// copied from CartesianIterable
6065
int size1 = _firstSet.size(bound);
@@ -75,10 +80,18 @@ public CartesianRelation(Set<? extends T1> firsts, Set<? extends T2> seconds) {
7580
public boolean hasFixedSize() { return _firstSet.hasFixedSize() && _secondSet.hasFixedSize(); }
7681
public boolean isStatic() { return _firstSet.isStatic() && _secondSet.isStatic(); }
7782

78-
protected boolean containsObjects(Object first, Object second) {
83+
public boolean contains(T1 first, T2 second) {
7984
return _firstSet.contains(first) && _secondSet.contains(second);
8085
}
8186

87+
public boolean contains(Object o) {
88+
if (o instanceof Pair<?, ?>) {
89+
Pair<?, ?> p = (Pair<?, ?>) o;
90+
return _firstSet.contains(p.first()) && _secondSet.contains(p.second());
91+
}
92+
else { return false; }
93+
}
94+
8295
public Iterator<Pair<T1, T2>> iterator() {
8396
return CartesianIterator.make(_firstSet.iterator(), _secondSet, Pair.<T1, T2>factory());
8497
}

‎plt/src/edu/rice/cs/plt/collect/CollectUtil.java‎

Lines changed: 104 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -42,6 +42,7 @@ IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISI
4242
import edu.rice.cs.plt.tuple.Pair;
4343
import edu.rice.cs.plt.iter.SizedIterable;
4444
import edu.rice.cs.plt.iter.IterUtil;
45+
import edu.rice.cs.plt.object.ObjectUtil;
4546

4647
public final class CollectUtil {
4748

@@ -313,23 +314,31 @@ public static <T> PredicateSet<T> makeSet(Option<? extends T> opt) {
313314
* Create an immutable {@code Relation} based on the given elements. May depend on a valid
314315
* {@code hashCode()} implementation.
315316
*/
316-
public static <T1, T2> Relation<T1, T2> makeRelation(Iterable<? extends Pair<T1, T2>> pairs) {
317+
public static <T1, T2> Relation<T1, T2> makeRelation(Iterable<? extends Pair<? extends T1, ? extends T2>> pairs) {
317318
if (IterUtil.isEmpty(pairs)) {
318319
return EmptyRelation.make();
319320
}
320321
else if (IterUtil.sizeOf(pairs, 2) == 1) {
321-
return new SingletonRelation<T1, T2>(IterUtil.first(pairs));
322+
Pair<? extends T1, ? extends T2> elt = IterUtil.first(pairs);
323+
return new SingletonRelation<T1, T2>(elt.first(), elt.second());
322324
}
323325
else {
324326
Relation<T1, T2> result = IndexedRelation.makeHashBased();
325-
result.addAll(asCollection(pairs));
327+
for (Pair<? extends T1, ? extends T2> elt : pairs) {
328+
result.add(elt.first(), elt.second());
329+
}
326330
return new ImmutableRelation<T1, T2>(result) {
327331
@Override public boolean hasFixedSize() { return true; }
328332
@Override public boolean isStatic() { return true; }
329333
};
330334
}
331335
}
332336

337+
/** Make an {@code ArrayList} with the given elements. */
338+
public static <T> List<T> makeList(Iterable<? extends T> iter) {
339+
return makeArrayList(iter);
340+
}
341+
333342
/** Make an {@code ArrayList} with the given elements. */
334343
public static <T> ArrayList<T> makeArrayList(Iterable<? extends T> iter) {
335344
if (iter instanceof Collection<?>) {
@@ -484,11 +493,63 @@ public static <T1, T2> ImmutableRelation<T1, T2> immutable(Relation<T1, T2> r) {
484493
return new ImmutableRelation<T1, T2>(r);
485494
}
486495

496+
/** Alias for {@link #makeSet}. */
497+
public static <T> PredicateSet<T> snapshot(Set<? extends T> set) {
498+
return makeSet(set);
499+
}
500+
501+
/**
502+
* Produce a snapshot of {@code set} if its composite size is greater than the given threshold.
503+
* @see ObjectUtil#compositeSize
504+
*/
505+
public static <T> Iterable<T> conditionalSnapshot(Set<T> set, int threshold) {
506+
if (ObjectUtil.compositeSize(set) > threshold) { return makeSet(set); }
507+
else { return set; }
508+
}
509+
510+
/** Alias for {@link #makeRelation}. */
511+
public static <T1, T2> Relation<T1, T2> snapshot(Relation<? extends T1, ? extends T2> relation) {
512+
return makeRelation(relation);
513+
}
514+
515+
/**
516+
* Produce a snapshot of {@code set} if its composite size is greater than the given threshold.
517+
* @see ObjectUtil#compositeSize
518+
*/
519+
public static <T1, T2> Relation<T1, T2> conditionalSnapshot(Relation<T1, T2> rel, int threshold) {
520+
if (ObjectUtil.compositeSize(rel) > threshold) { return makeRelation(rel); }
521+
else { return rel; }
522+
}
523+
524+
/** Invoke the {@code HashMap#HashMap(Map)} constructor. */
525+
public static <K, V> LambdaMap<K, V> snapshot(Map<? extends K, ? extends V> map) {
526+
return new DelegatingMap<K, V>(new HashMap<K, V>(map));
527+
}
528+
529+
/**
530+
* Produce a snapshot of {@code set} if its composite size is greater than the given threshold.
531+
* @see ObjectUtil#compositeSize
532+
*/
533+
public static <K, V> Map<K, V> conditionalSnapshot(Map<K, V> map, int threshold) {
534+
if (ObjectUtil.compositeSize(map) > threshold) { return snapshot(map); }
535+
else { return map; }
536+
}
537+
538+
/** Alias for {@link #makeArrayList}. */
539+
public static <T> List<T> snapshot(List<? extends T> list) {
540+
return makeArrayList(list);
541+
}
542+
487543
/** Produce a lazy union of two sets. Size-related operations have poor performance. */
488544
public static <T> PredicateSet<T> union(Set<? extends T> s1, Set<? extends T> s2) {
489545
return new UnionSet<T>(s1, s2);
490546
}
491547

548+
/** Produce a lazy union of a set with an additional singleton element. */
549+
public static <T> PredicateSet<T> union(Set<? extends T> set, T elt) {
550+
return new UnionSet<T>(set, new SingletonSet<T>(elt));
551+
}
552+
492553
/** Produce a lazy intersection of two sets. Size-related operations have poor performance. */
493554
public static <T> PredicateSet<T> intersection(Set<?> s1, Set<? extends T> s2) {
494555
return new IntersectionSet<T>(s1, s2);
@@ -502,6 +563,14 @@ public static <T> PredicateSet<T> complement(Set<? extends T> domain, Set<?> exc
502563
return new ComplementSet<T>(domain, excluded);
503564
}
504565

566+
/**
567+
* Produce the complement of a singleton in a domain set, or, equivalently, a set with
568+
* a certain element removed.
569+
*/
570+
public static <T> PredicateSet<T> complement(Set<? extends T> domain, T excluded) {
571+
return new ComplementSet<T>(domain, new SingletonSet<T>(excluded));
572+
}
573+
505574
/** Lazily filter the given set. Size-related operations have poor performance. */
506575
public static <T> PredicateSet<T> filter(Set<? extends T> set, Predicate<? super T> predicate) {
507576
return new FilteredSet<T>(set, predicate);
@@ -512,6 +581,38 @@ public static <T1, T2> Relation<T1, T2> cross(Set<? extends T1> left, Set<? exte
512581
return new CartesianRelation<T1, T2>(left, right);
513582
}
514583

584+
/** Produce a lazy union of two relations. Size-related operations have poor performance. */
585+
public static <T1, T2> Relation<T1, T2> union(Relation<T1, T2> r1, Relation<T1, T2> r2) {
586+
return new UnionRelation<T1, T2>(r1, r2);
587+
}
588+
589+
/** Produce a lazy union of a relation with an additional singleton entry. */
590+
public static <T1, T2> Relation<T1, T2> union(Relation<T1, T2> rel, T1 first, T2 second) {
591+
return new UnionRelation<T1, T2>(rel, new SingletonRelation<T1, T2>(first, second));
592+
}
593+
594+
/** Produce a lazy intersection of two relations. Size-related operations have poor performance. */
595+
public static <T1, T2> Relation<T1, T2> intersection(Relation<T1, T2> r1, Relation<T1, T2> r2) {
596+
return new IntersectionRelation<T1, T2>(r1, r2);
597+
}
598+
599+
/**
600+
* Produce the complement of a relation in a domain, or, equivalently, the difference of two
601+
* relations. Size-related operations have poor performance.
602+
*/
603+
public static <T1, T2> Relation<T1, T2> complement(Relation<T1, T2> domain,
604+
Relation<? super T1, ? super T2> excluded) {
605+
return new ComplementRelation<T1, T2>(domain, excluded);
606+
}
607+
608+
/**
609+
* Produce the complement of a singleton in a domain relation, or, equivalently, a relation with
610+
* a certain entry removed.
611+
*/
612+
public static <T1, T2> Relation<T1, T2> complement(Relation<T1, T2> domain, T1 first, T2 second) {
613+
return new ComplementRelation<T1, T2>(domain, new SingletonRelation<T1, T2>(first, second));
614+
}
615+
515616
/** Produce a lazy transitive composition of two relations. Size-related operations have poor performance. */
516617
public static <T1, T2, T3> Relation<T1, T3> compose(Relation<T1, T2> left, Relation<T2, T3> right) {
517618
return new ComposedRelation<T1, T2, T3>(left, right);

0 commit comments

Comments
 (0)