From: adam Date: Mon, 2 Jan 2006 06:28:08 +0000 (-0500) Subject: refactored Topology to make it a value (immutable) class X-Git-Tag: tag_for_25-Mar~471 X-Git-Url: http://git.megacz.com/?p=sbp.git;a=commitdiff_plain;h=6b53048f4413f3c618acc3581d0b4f60a236a9bc;hp=84a4a8204373b996105e69edf91d2f9fae7b4bcb refactored Topology to make it a value (immutable) class darcs-hash:20060102062808-5007d-b2bc0b6e025f75803c863795a62a65c316c6c155.gz --- diff --git a/src/edu/berkeley/sbp/Atom.java b/src/edu/berkeley/sbp/Atom.java index 524ab3a..3b7ce1f 100644 --- a/src/edu/berkeley/sbp/Atom.java +++ b/src/edu/berkeley/sbp/Atom.java @@ -12,7 +12,7 @@ public abstract class Atom extends Element implements Topology< protected abstract Topology top(); - public Topology toAtom() { return dup(); } + public Topology toAtom() { return this; } /** equality is based on the underlying Topology */ public int hashCode() { return top().hashCode(); } @@ -25,13 +25,9 @@ public abstract class Atom extends Element implements Topology< // Topology Thunks ////////////////////////////////////////////////////////////////////////////// - public void add(Topology t) { top().add(t); } - public void add(T t) { top().add(t); } - public void remove(Topology t) { top().remove(t); } - public void remove(T t) { top().remove(t); } - public Topology dup() { return top().dup(); } + public Topology unwrap() { return top().unwrap(); } + public Topology empty() { return top().empty(); } public boolean contains(T v) { return top().contains(v); } - public Topology fresh() { return top().fresh(); } public Topology intersect(Topology t) { return top().intersect(t); } public Topology minus(Topology t) { return top().minus(t); } public Topology union(Topology t) { return top().union(t); } diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java index e707eac..ab06889 100644 --- a/src/edu/berkeley/sbp/Parser.java +++ b/src/edu/berkeley/sbp/Parser.java @@ -155,7 +155,7 @@ public class Parser { // 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); @@ -164,7 +164,7 @@ public class Parser { // 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()))); } } @@ -235,7 +235,7 @@ public class Parser { Atom a = (Atom)position.element(); HashSet hp = new HashSet(); 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 diff --git a/src/edu/berkeley/sbp/Union.java b/src/edu/berkeley/sbp/Union.java index b000f95..8780d9e 100644 --- a/src/edu/berkeley/sbp/Union.java +++ b/src/edu/berkeley/sbp/Union.java @@ -21,8 +21,8 @@ public class Union extends Element implements Iterable { 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; diff --git a/src/edu/berkeley/sbp/Walk.java b/src/edu/berkeley/sbp/Walk.java index 8b6eae6..4f133a4 100644 --- a/src/edu/berkeley/sbp/Walk.java +++ b/src/edu/berkeley/sbp/Walk.java @@ -52,7 +52,7 @@ abstract class Walk { public HashSet bottom(Element e) { return acc; } public HashSet sequence(Sequence seq) { return bottom(seq); } public HashSet 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); } } @@ -83,7 +83,7 @@ abstract class Walk { public WalkTokenSet(Topology cs) { this.cs = cs; } public WalkTokenSet(Topology cs, Cache c) { super(c); this.cs = cs; } public Topology bottom(Element e) { return cs; } - public Topology walkAtom(Atom r) { cs.add(r.dup()); return cs; } + public Topology walkAtom(Atom r) { cs = cs.union(r); return cs; } } class First extends WalkTokenSet { @@ -127,7 +127,7 @@ abstract class Walk { if (c != null) { Topology cached = (Topology)c.follow.get(e); if (cached != null) { - cs.add(cached); + cs = cs.union(cached); eof |= c.eof.get(e); return cs; } @@ -136,7 +136,7 @@ abstract class Walk { Topology 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) { @@ -146,13 +146,13 @@ abstract class Walk { 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(cs.fresh(), c).walk(pos.element())); + if (matched) cs = cs.union(new First(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; } @@ -166,15 +166,15 @@ abstract class Walk { 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; diff --git a/src/edu/berkeley/sbp/util/DiscreteTopology.java b/src/edu/berkeley/sbp/util/DiscreteTopology.java index f78bdae..0fb75eb 100644 --- a/src/edu/berkeley/sbp/util/DiscreteTopology.java +++ b/src/edu/berkeley/sbp/util/DiscreteTopology.java @@ -9,14 +9,15 @@ import edu.berkeley.sbp.*; /** implementation of Topology for any class via equals()/hashCode() */ public class DiscreteTopology implements Topology { + private static final DiscreteTopology empty = new DiscreteTopology(); + HashSet hs = new HashSet(); public DiscreteTopology() { } public DiscreteTopology(V v) { hs.add(v); } - DiscreteTopology(HashSet hs) { this.hs.addAll(hs); } + DiscreteTopology(HashSet hs) { this.hs.addAll(hs); } - public Topology fresh() { return new DiscreteTopology(); } - public Topology dup() { return new DiscreteTopology(this.hs); } + public Topology empty() { return (Topology)empty; } public HashSet hs() { HashSet ret = new HashSet(); @@ -24,18 +25,15 @@ public class DiscreteTopology implements Topology { return ret; } - public void add(Topology t) { hs.addAll(((DiscreteTopology)t).hs); } - public void remove(Topology t) { hs.removeAll(((DiscreteTopology)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 complement() { /*return dup(hs.complement());*/ throw new Error(); } - public Topology intersect(Topology t) { return new DiscreteTopology(hs().retainAll(((DiscreteTopology)t).hs)); } - public Topology minus(Topology t) { return new DiscreteTopology(hs().removeAll(((DiscreteTopology)t).hs)); } - public Topology union(Topology t) { return new DiscreteTopology(hs().addAll(((DiscreteTopology)t).hs)); } - public boolean disjoint(Topology t) { return ((DiscreteTopology)intersect(t)).size()==0; } - public boolean containsAll(Topology t) { return hs.containsAll(((DiscreteTopology)t).hs); } + public Topology unwrap() { return this; } + public Topology complement() { throw new Error(); } + public Topology intersect(Topology t) { return new DiscreteTopology(hs().retainAll(((DiscreteTopology)t.unwrap()).hs)); } + public Topology minus(Topology t) { return new DiscreteTopology(hs().removeAll(((DiscreteTopology)t.unwrap()).hs)); } + public Topology union(Topology t) { return new DiscreteTopology(hs().addAll(((DiscreteTopology)t.unwrap()).hs)); } + public boolean disjoint(Topology t) { return ((DiscreteTopology)intersect(t).unwrap()).size()==0; } + public boolean containsAll(Topology t) { return hs.containsAll(((DiscreteTopology)t.unwrap()).hs); } public int hashCode() { return hs.hashCode(); } public boolean equals(Object o) { return o!=null && o instanceof DiscreteTopology && ((DiscreteTopology)o).hs.equals(hs); } diff --git a/src/edu/berkeley/sbp/util/IntegerTopology.java b/src/edu/berkeley/sbp/util/IntegerTopology.java index cac19e9..e1bec15 100644 --- a/src/edu/berkeley/sbp/util/IntegerTopology.java +++ b/src/edu/berkeley/sbp/util/IntegerTopology.java @@ -9,7 +9,9 @@ import edu.berkeley.sbp.*; /** implementation of Topology for any class for which there is a mapping to the ints */ public class IntegerTopology implements Topology { 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()); } @@ -20,23 +22,18 @@ public class IntegerTopology implemen public IntegerTopology(Range r) { this(new Range.Set(r)); } public IntegerTopology(Range.Set rs) { this.rs = rs; } - public Topology fresh() { return new IntegerTopology(); } - public Topology dup() { return new IntegerTopology(this.rs); } - public Topology dup(Range.Set rs) { return new IntegerTopology(rs); } + public Topology empty() { return (Topology)empty; } - public void add(Topology t) { rs.add(((IntegerTopology)t).rs); } - public void remove(Topology t) { rs.remove(((IntegerTopology)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 complement() { return dup(rs.complement()); } - public Topology intersect(Topology t) { return dup(rs.intersect(((IntegerTopology)t).rs)); } - public Topology minus(Topology t) { return dup(rs.intersect(((IntegerTopology)t).rs.complement())); } - public Topology union(Topology t) { return dup(rs.union(((IntegerTopology)t).rs)); } - public boolean disjoint(Topology t) { return rs.intersect(((IntegerTopology)t).rs).size()==0; } - public boolean containsAll(Topology t) { return rs.intersect(((IntegerTopology)t).rs).equals(((IntegerTopology)t).rs); } + public Topology complement() { return new IntegerTopology(rs.complement()); } + public Topology intersect(Topology t) { return new IntegerTopology(rs.intersect(((IntegerTopology)t.unwrap()).rs)); } + public Topology minus(Topology t) { return new IntegerTopology(rs.intersect(((IntegerTopology)t.unwrap()).rs.complement())); } + public Topology union(Topology t) { return new IntegerTopology(rs.union(((IntegerTopology)t.unwrap()).rs)); } + public boolean disjoint(Topology t) { return rs.intersect(((IntegerTopology)t.unwrap()).rs).size()==0; } + public boolean containsAll(Topology t) { return rs.containsAll(((IntegerTopology)t.unwrap()).rs); } + public Topology unwrap() { return this; } public int hashCode() { return rs.hashCode(); } public boolean equals(Object o) { return o!=null && o instanceof IntegerTopology && ((IntegerTopology)o).rs.equals(rs); } diff --git a/src/edu/berkeley/sbp/util/Range.java b/src/edu/berkeley/sbp/util/Range.java index 714cd83..9dae4a3 100644 --- a/src/edu/berkeley/sbp/util/Range.java +++ b/src/edu/berkeley/sbp/util/Range.java @@ -553,6 +553,12 @@ public class Range { 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; diff --git a/src/edu/berkeley/sbp/util/TopologicalBag.java b/src/edu/berkeley/sbp/util/TopologicalBag.java index 2a1bb53..8862be6 100644 --- a/src/edu/berkeley/sbp/util/TopologicalBag.java +++ b/src/edu/berkeley/sbp/util/TopologicalBag.java @@ -31,7 +31,7 @@ public class TopologicalBag implements MapBag,V> { public void put(Topology t, V v) { for(Topology 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; } diff --git a/src/edu/berkeley/sbp/util/Topology.java b/src/edu/berkeley/sbp/util/Topology.java index 2756aae..95cdaac 100644 --- a/src/edu/berkeley/sbp/util/Topology.java +++ b/src/edu/berkeley/sbp/util/Topology.java @@ -10,20 +10,17 @@ import java.lang.ref.*; /** values inhabiting a topology over V (roughly, infinite sets of V's equipped with union/intersection/complement) */ public interface Topology { - public void add(Topology t); - public void add(V t); - public void remove(Topology t); - public void remove(V t); - public Topology dup(); + public Topology unwrap(); + public Topology empty(); + public boolean contains(V v); - public Topology fresh(); + public boolean disjoint(Topology t); + public boolean containsAll(Topology t); + public Topology complement(); public Topology intersect(Topology t); public Topology minus(Topology t); public Topology union(Topology t); - public Topology complement(); - public boolean disjoint(Topology t); - public boolean containsAll(Topology t); public abstract int hashCode(); public abstract boolean equals(Object o);