protected abstract Topology<T> top();
- public Topology toAtom() { return dup(); }
+ public Topology toAtom() { return this; }
/** equality is based on the underlying <tt>Topology</tt> */
public int hashCode() { return top().hashCode(); }
// Topology Thunks //////////////////////////////////////////////////////////////////////////////
- public void add(Topology<T> t) { top().add(t); }
- public void add(T t) { top().add(t); }
- public void remove(Topology<T> t) { top().remove(t); }
- public void remove(T t) { top().remove(t); }
- public Topology<T> dup() { return top().dup(); }
+ public Topology<T> unwrap() { return top().unwrap(); }
+ public Topology<T> empty() { return top().empty(); }
public boolean contains(T v) { return top().contains(v); }
- public Topology<T> fresh() { return top().fresh(); }
public Topology<T> intersect(Topology<T> t) { return top().intersect(t); }
public Topology<T> minus(Topology<T> t) { return top().minus(t); }
public Topology<T> union(Topology<T> t) { return top().union(t); }
// FIXME: how does right-nullability interact with follow restrictions?
// all right-nullable rules get a reduction [Johnstone 2000]
if (p.isRightNullable(cache)) {
- Walk.Follow wf = new Walk.Follow(top.fresh(), p.owner(), all_elements, cache);
+ Walk.Follow wf = new Walk.Follow(top.empty(), p.owner(), all_elements, cache);
Reduction red = new Reduction(p);
state.reductions.put(wf.walk(p.owner()), red);
if (wf.includesEof()) state.eofReductions.add(red, true);
// if the element following this position is an atom, copy the corresponding
// set of rows out of the "master" goto table and into this state's shift table
if (p.element() != null && p.element() instanceof Atom)
- state.shifts.addAll(state.gotoSetTerminals.subset(((Atom)p.element()).dup()));
+ state.shifts.addAll(state.gotoSetTerminals.subset(((Atom)p.element())));
}
}
Atom a = (Atom)position.element();
HashSet<Position> hp = new HashSet<Position>();
reachable(position.next(), hp);
- bag0.addAll(a.dup(), /*clo.walk()*/hp);
+ bag0.addAll(a, /*clo.walk()*/hp);
}
// Step 1b: for each _minimal, contiguous_ set of characters having an identical next-position
Topology ret = null;
for(Sequence s : this) {
Topology a = s.toAtom();
- if (ret==null) ret = a.dup();
- else ret = ret.union(a.dup());
+ if (ret==null) ret = a;
+ else ret = ret.union(a);
}
if (ret==null) throw new RuntimeException("confusion on " + this);
return ret;
public HashSet<Element> bottom(Element e) { return acc; }
public HashSet<Element> sequence(Sequence seq) { return bottom(seq); }
public HashSet<Element> walkAtom(Atom r) {
- c.atoms.put(e, c.atoms.get(e)==null ? r.dup() : c.atoms.get(e).union(r.dup()));
+ c.atoms.put(e, c.atoms.get(e)==null ? r : c.atoms.get(e).union(r));
return super.walkAtom(r);
}
}
public WalkTokenSet(Topology<Tok> cs) { this.cs = cs; }
public WalkTokenSet(Topology<Tok> cs, Cache c) { super(c); this.cs = cs; }
public Topology<Tok> bottom(Element e) { return cs; }
- public Topology<Tok> walkAtom(Atom r) { cs.add(r.dup()); return cs; }
+ public Topology<Tok> walkAtom(Atom r) { cs = cs.union(r); return cs; }
}
class First<Tok extends Token> extends WalkTokenSet<Tok> {
if (c != null) {
Topology<Tok> cached = (Topology<Tok>)c.follow.get(e);
if (cached != null) {
- cs.add(cached);
+ cs = cs.union(cached);
eof |= c.eof.get(e);
return cs;
}
Topology<Tok> cso = cs;
boolean eofo = eof;
eof = false;
- cs = cso.fresh();
+ cs = cso.empty();
if (e instanceof Parser.Table.Top) eof = true;
for(Element x : all) {
Sequence a = (Sequence)x;
Position mp = null;
for(Position pos = a.firstp(); pos != null && !pos.isLast(); pos = pos.next()) {
- if (matched) cs.add(new First<Tok>(cs.fresh(), c).walk(pos.element()));
+ if (matched) cs = cs.union(new First<Tok>(cs.empty(), c).walk(pos.element()));
if (pos.isLast()) { matched = (matched && pos.element().possiblyEpsilon(c)); continue; }
boolean good = false;
if (e instanceof Atom) {
Topology top = c.atoms.get(pos.element());
if (top==null) continue;
- if (!(top.containsAll(((Atom)e).dup()))) continue;
+ if (!(top.containsAll(((Atom)e)))) continue;
} else {
if (c.ys.get(pos.element()).contains(e)) good = true;
}
if (e instanceof Sequence) {
Sequence s = (Sequence)e;
- if (s.noFollow() != null) cs.remove(s.noFollow().dup());
+ if (s.noFollow() != null) cs = cs.minus(s.noFollow());
}
if (c != null && e==me) {
- c.follow.put(e, cs.dup());
+ c.follow.put(e, cs);
c.eof.put(e, eof);
}
- cso.add(cs);
+ cso = cso.union(cs);
cs = cso;
eofo |= eof;
eof = eofo;
/** implementation of <tt>Topology</tt> for any class via equals()/hashCode() */
public class DiscreteTopology<V> implements Topology<V> {
+ private static final DiscreteTopology empty = new DiscreteTopology();
+
HashSet<V> hs = new HashSet<V>();
public DiscreteTopology() { }
public DiscreteTopology(V v) { hs.add(v); }
- DiscreteTopology(HashSet<V> hs) { this.hs.addAll(hs); }
+ DiscreteTopology(HashSet<V> hs) { this.hs.addAll(hs); }
- public Topology<V> fresh() { return new DiscreteTopology<V>(); }
- public Topology<V> dup() { return new DiscreteTopology<V>(this.hs); }
+ public Topology<V> empty() { return (Topology<V>)empty; }
public HashSet<V> hs() {
HashSet<V> ret = new HashSet<V>();
return ret;
}
- public void add(Topology<V> t) { hs.addAll(((DiscreteTopology<V>)t).hs); }
- public void remove(Topology<V> t) { hs.removeAll(((DiscreteTopology<V>)t).hs); }
- public void add(V v) { hs.add(v); }
- public void remove(V v) { hs.remove(v); }
public boolean contains(V v) { return hs.contains(v); }
- public Topology<V> complement() { /*return dup(hs.complement());*/ throw new Error(); }
- public Topology<V> intersect(Topology<V> t) { return new DiscreteTopology(hs().retainAll(((DiscreteTopology<V>)t).hs)); }
- public Topology<V> minus(Topology<V> t) { return new DiscreteTopology(hs().removeAll(((DiscreteTopology<V>)t).hs)); }
- public Topology<V> union(Topology<V> t) { return new DiscreteTopology(hs().addAll(((DiscreteTopology<V>)t).hs)); }
- public boolean disjoint(Topology<V> t) { return ((DiscreteTopology)intersect(t)).size()==0; }
- public boolean containsAll(Topology<V> t) { return hs.containsAll(((DiscreteTopology<V>)t).hs); }
+ public Topology<V> unwrap() { return this; }
+ public Topology<V> complement() { throw new Error(); }
+ public Topology<V> intersect(Topology<V> t) { return new DiscreteTopology(hs().retainAll(((DiscreteTopology<V>)t.unwrap()).hs)); }
+ public Topology<V> minus(Topology<V> t) { return new DiscreteTopology(hs().removeAll(((DiscreteTopology<V>)t.unwrap()).hs)); }
+ public Topology<V> union(Topology<V> t) { return new DiscreteTopology(hs().addAll(((DiscreteTopology<V>)t.unwrap()).hs)); }
+ public boolean disjoint(Topology<V> t) { return ((DiscreteTopology)intersect(t).unwrap()).size()==0; }
+ public boolean containsAll(Topology<V> t) { return hs.containsAll(((DiscreteTopology<V>)t.unwrap()).hs); }
public int hashCode() { return hs.hashCode(); }
public boolean equals(Object o) { return o!=null && o instanceof DiscreteTopology && ((DiscreteTopology<V>)o).hs.equals(hs); }
/** implementation of <tt>Topology</tt> for any class for which there is a mapping to the <tt>int</tt>s */
public class IntegerTopology<V extends IntegerTopology.IntegerMappable> implements Topology<V> {
private final Range.Set rs;
-
+
+ private static final IntegerTopology empty = new IntegerTopology();
+
public Range.Set getRanges() { return new Range.Set(rs); }
public IntegerTopology() { this(new Range.Set()); }
public IntegerTopology(Range r) { this(new Range.Set(r)); }
public IntegerTopology(Range.Set rs) { this.rs = rs; }
- public Topology<V> fresh() { return new IntegerTopology<V>(); }
- public Topology<V> dup() { return new IntegerTopology<V>(this.rs); }
- public Topology<V> dup(Range.Set rs) { return new IntegerTopology<V>(rs); }
+ public Topology<V> empty() { return (Topology<V>)empty; }
- public void add(Topology<V> t) { rs.add(((IntegerTopology<V>)t).rs); }
- public void remove(Topology<V> t) { rs.remove(((IntegerTopology<V>)t).rs); }
- public void add(V v) { rs.add(v.toInt()); }
- public void remove(V v) { rs.remove(v.toInt()); }
public boolean contains(V v) { return rs.contains(v.toInt()); }
- public Topology<V> complement() { return dup(rs.complement()); }
- public Topology<V> intersect(Topology<V> t) { return dup(rs.intersect(((IntegerTopology<V>)t).rs)); }
- public Topology<V> minus(Topology<V> t) { return dup(rs.intersect(((IntegerTopology<V>)t).rs.complement())); }
- public Topology<V> union(Topology<V> t) { return dup(rs.union(((IntegerTopology<V>)t).rs)); }
- public boolean disjoint(Topology<V> t) { return rs.intersect(((IntegerTopology<V>)t).rs).size()==0; }
- public boolean containsAll(Topology<V> t) { return rs.intersect(((IntegerTopology<V>)t).rs).equals(((IntegerTopology<V>)t).rs); }
+ public Topology<V> complement() { return new IntegerTopology<V>(rs.complement()); }
+ public Topology<V> intersect(Topology<V> t) { return new IntegerTopology<V>(rs.intersect(((IntegerTopology<V>)t.unwrap()).rs)); }
+ public Topology<V> minus(Topology<V> t) { return new IntegerTopology<V>(rs.intersect(((IntegerTopology<V>)t.unwrap()).rs.complement())); }
+ public Topology<V> union(Topology<V> t) { return new IntegerTopology<V>(rs.union(((IntegerTopology<V>)t.unwrap()).rs)); }
+ public boolean disjoint(Topology<V> t) { return rs.intersect(((IntegerTopology<V>)t.unwrap()).rs).size()==0; }
+ public boolean containsAll(Topology<V> t) { return rs.containsAll(((IntegerTopology<V>)t.unwrap()).rs); }
+ public Topology<V> unwrap() { return this; }
public int hashCode() { return rs.hashCode(); }
public boolean equals(Object o) { return o!=null && o instanceof IntegerTopology && ((IntegerTopology<V>)o).rs.equals(rs); }
return result;
}
+ public boolean containsAll(Range.Set rs) {
+ for(Range r : rs)
+ if (!contains(r)) return false;
+ return true;
+ }
+
public boolean equals(Object obj) {
if (obj instanceof Range.Set) {
Range.Set rs = (Range.Set) obj;
public void put(Topology<K> t, V v) {
for(Topology<K> ht : h.keySet()) {
if (t.disjoint(ht)) continue;
- if (t.equals(ht)) {
+ if (t.containsAll(ht) && ht.containsAll(t)) {
h.get(ht).add(v);
return;
}
/** values inhabiting a topology over <tt>V</tt> (roughly, infinite sets of <tt>V</tt>'s equipped with union/intersection/complement) */
public interface Topology<V> {
- public void add(Topology<V> t);
- public void add(V t);
- public void remove(Topology<V> t);
- public void remove(V t);
- public Topology<V> dup();
+ public Topology<V> unwrap();
+ public Topology<V> empty();
+
public boolean contains(V v);
- public Topology<V> fresh();
+ public boolean disjoint(Topology<V> t);
+ public boolean containsAll(Topology<V> t);
+ public Topology<V> complement();
public Topology<V> intersect(Topology<V> t);
public Topology<V> minus(Topology<V> t);
public Topology<V> union(Topology<V> t);
- public Topology<V> complement();
- public boolean disjoint(Topology<V> t);
- public boolean containsAll(Topology<V> t);
public abstract int hashCode();
public abstract boolean equals(Object o);