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 (file)
--- a/src/edu/berkeley/sbp/Atom.java
+++ b/src/edu/berkeley/sbp/Atom.java
@@ -12,7 +12,7 @@ public abstract class Atom<T extends Token> extends Element implements Topology<
 
     protected abstract Topology<T> top();
 
 
     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(); }
 
     /** equality is based on the underlying <tt>Topology</tt> */
     public int hashCode() { return top().hashCode(); }

@@ -25,13 +25,9 @@ public abstract class Atom<T extends Token> extends Element implements Topology<
 
     // Topology Thunks //////////////////////////////////////////////////////////////////////////////
 
 
     // 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 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); }
     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); }

diff --git a/src/edu/berkeley/sbp/Parser.java b/src/edu/berkeley/sbp/Parser.java
index e707eac..ab06889 100644 (file)
--- a/src/edu/berkeley/sbp/Parser.java
+++ b/src/edu/berkeley/sbp/Parser.java
@@ -155,7 +155,7 @@ public class Parser<T extends Token, R> {
                     // FIXME: how does right-nullability interact with follow restrictions?
                     // all right-nullable rules get a reduction [Johnstone 2000]
                     if (p.isRightNullable(cache)) {
                     // 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);
                         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<T extends Token, R> {
                     // 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)
                     // 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<T extends Token, R> {
                     Atom a = (Atom)position.element();
                     HashSet<Position> hp = new HashSet<Position>();
                     reachable(position.next(), hp);
                     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
                 }
 
                 // 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 (file)
--- 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<Sequence> {
         Topology ret = null;
         for(Sequence s : this) {
             Topology a = s.toAtom();
         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;
         }
         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 (file)
--- a/src/edu/berkeley/sbp/Walk.java
+++ b/src/edu/berkeley/sbp/Walk.java
@@ -52,7 +52,7 @@ abstract class Walk<T> {
         public HashSet<Element> bottom(Element e)     { return acc; }
         public HashSet<Element> sequence(Sequence seq) { return bottom(seq); }
         public HashSet<Element> walkAtom(Atom r) {
         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);
         }
     }
             return super.walkAtom(r);
         }
     }

@@ -83,7 +83,7 @@ abstract class Walk<T> {
         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 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> {
     }
 
     class First<Tok extends Token> extends WalkTokenSet<Tok> {

@@ -127,7 +127,7 @@ abstract class Walk<T> {
             if (c != null) {
                 Topology<Tok> cached = (Topology<Tok>)c.follow.get(e);
                 if (cached != null) {
             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;
                 }
                     eof |= c.eof.get(e);
                     return cs;
                 }

@@ -136,7 +136,7 @@ abstract class Walk<T> {
             Topology<Tok> cso = cs;
             boolean eofo = eof;
             eof = false;
             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) {
 
             if (e instanceof Parser.Table.Top) eof = true;
             for(Element x : all) {

@@ -146,13 +146,13 @@ abstract class Walk<T> {
                 Sequence a = (Sequence)x;
                 Position mp = null;
                 for(Position pos = a.firstp(); pos != null && !pos.isLast(); pos = pos.next()) {
                 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 (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;
                     }
                     } else {
                         if (c.ys.get(pos.element()).contains(e)) good = true;
                     }

@@ -166,15 +166,15 @@ abstract class Walk<T> {
 
             if (e instanceof Sequence) {
                 Sequence s = (Sequence)e;
 
             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) {
             }
 
             if (c != null && e==me) {

-                c.follow.put(e, cs.dup());
+                c.follow.put(e, cs);

                 c.eof.put(e, eof);
             }
 
                 c.eof.put(e, eof);
             }
 

-            cso.add(cs);
+            cso = cso.union(cs);

             cs = cso;
             eofo |= eof;
             eof = eofo;
             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 (file)
--- 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 <tt>Topology</tt> for any class via equals()/hashCode() */
 public class DiscreteTopology<V> implements Topology<V> {
 
 /** 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); }
     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>();
 
     public HashSet<V> hs() {
         HashSet<V> ret = new HashSet<V>();

@@ -24,18 +25,15 @@ public class DiscreteTopology<V> implements Topology<V> {
         return ret;
     }
         
         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 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); }
 
     public int     hashCode()                          { return hs.hashCode(); }
     public boolean equals(Object o)                    { return o!=null && o instanceof DiscreteTopology && ((DiscreteTopology<V>)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 (file)
--- 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 <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;
 /** 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 Range.Set getRanges()         { return new Range.Set(rs); }
 
     public IntegerTopology()             { this(new Range.Set()); }

@@ -20,23 +22,18 @@ public class IntegerTopology<V extends IntegerTopology.IntegerMappable> implemen
     public IntegerTopology(Range r)      { this(new Range.Set(r)); }
     public IntegerTopology(Range.Set rs) { this.rs = rs; }
 
     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 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); }
 
     public int     hashCode()                          { return rs.hashCode(); }
     public boolean equals(Object o)                    { return o!=null && o instanceof IntegerTopology && ((IntegerTopology<V>)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 (file)
--- 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;
         }
 
             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 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 (file)
--- a/src/edu/berkeley/sbp/util/TopologicalBag.java
+++ b/src/edu/berkeley/sbp/util/TopologicalBag.java
@@ -31,7 +31,7 @@ public class TopologicalBag<K,V> implements MapBag<Topology<K>,V> {
     public void put(Topology<K> t, V v) {
         for(Topology<K> ht : h.keySet()) {
             if (t.disjoint(ht)) continue;
     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;
             }
                 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 (file)
--- 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 <tt>V</tt> (roughly, infinite sets of <tt>V</tt>'s equipped with union/intersection/complement) */
 public interface Topology<V> {
 
 /** 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 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>       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);
 
     public abstract int     hashCode();
     public abstract boolean equals(Object o);