public class ReachabilitySet extends Canonical {
- private HashSet<TokenTupleSet> possibleReachabilities;
-
- public ReachabilitySet() {
- possibleReachabilities = new HashSet<TokenTupleSet>();
- //TokenTupleSet ttsEmpty = new TokenTupleSet().makeCanonical();
- //possibleReachabilities.add( ttsEmpty );
+ private HashSet<TokenTupleSet> possibleReachabilities;
+
+ public ReachabilitySet() {
+ possibleReachabilities = new HashSet<TokenTupleSet>();
+ }
+
+ public ReachabilitySet(TokenTupleSet tts) {
+ this();
+ assert tts != null;
+ possibleReachabilities.add(tts);
+ }
+
+ public ReachabilitySet(TokenTuple tt) {
+ // can't assert before calling this(), it will
+ // do the checking though
+ this( new TokenTupleSet(tt).makeCanonical() );
+ }
+
+ public ReachabilitySet(HashSet<TokenTupleSet> possibleReachabilities) {
+ assert possibleReachabilities != null;
+ this.possibleReachabilities = possibleReachabilities;
+ }
+
+ public ReachabilitySet(ReachabilitySet rs) {
+ assert rs != null;
+ // okay to clone, ReachabilitySet should be canonical
+ possibleReachabilities = (HashSet<TokenTupleSet>)rs.possibleReachabilities.clone();
+ }
+
+
+ public ReachabilitySet makeCanonical() {
+ return (ReachabilitySet) Canonical.makeCanonical(this);
+ }
+
+ public Iterator<TokenTupleSet> iterator() {
+ return possibleReachabilities.iterator();
+ }
+
+
+ public boolean contains(TokenTupleSet tts) {
+ assert tts != null;
+ return possibleReachabilities.contains(tts);
+ }
+
+ public boolean containsTuple(TokenTuple tt) {
+ Iterator itr = iterator();
+ while( itr.hasNext() ) {
+ TokenTupleSet tts = (TokenTupleSet) itr.next();
+ if( tts.containsTuple(tt) ) {
+ return true;
+ }
}
+ return false;
+ }
- public ReachabilitySet( TokenTupleSet tts ) {
- this();
- assert tts != null;
- possibleReachabilities.add( tts );
- }
- public ReachabilitySet( TokenTuple tt ) {
- this( new TokenTupleSet( tt ).makeCanonical() );
- }
+ public ReachabilitySet increaseArity(Integer token) {
+ assert token != null;
- public ReachabilitySet( HashSet<TokenTupleSet> possibleReachabilities ) {
- this.possibleReachabilities = possibleReachabilities;
- }
+ HashSet<TokenTupleSet> possibleReachabilitiesNew = new HashSet<TokenTupleSet>();
- public ReachabilitySet( ReachabilitySet rs ) {
- assert rs != null;
- possibleReachabilities = (HashSet<TokenTupleSet>) rs.possibleReachabilities.clone(); // again, DEEP COPY?!
+ Iterator itr = iterator();
+ while( itr.hasNext() ) {
+ TokenTupleSet tts = (TokenTupleSet) itr.next();
+ possibleReachabilitiesNew.add(tts.increaseArity(token) );
}
- public ReachabilitySet makeCanonical() {
- return (ReachabilitySet) Canonical.makeCanonical( this );
- }
+ return new ReachabilitySet(possibleReachabilitiesNew).makeCanonical();
+ }
- public boolean contains( TokenTupleSet tts ) {
- assert tts != null;
- return possibleReachabilities.contains( tts );
- }
- public ReachabilitySet add( TokenTupleSet tts ) {
- ReachabilitySet rsOut = new ReachabilitySet( tts );
- return this.union( rsOut );
- }
+ public ReachabilitySet union(ReachabilitySet rsIn) {
+ assert rsIn != null;
- public ReachabilitySet increaseArity( Integer token ) {
- assert token != null;
+ ReachabilitySet rsOut = new ReachabilitySet(this);
+ rsOut.possibleReachabilities.addAll(rsIn.possibleReachabilities);
+ return rsOut.makeCanonical();
+ }
- HashSet<TokenTupleSet> possibleReachabilitiesNew = new HashSet<TokenTupleSet>();
+ public ReachabilitySet union(TokenTupleSet ttsIn) {
+ assert ttsIn != null;
- Iterator itr = iterator();
- while( itr.hasNext() ) {
- TokenTupleSet tts = (TokenTupleSet) itr.next();
- possibleReachabilitiesNew.add( tts.increaseArity( token ) );
- }
+ ReachabilitySet rsOut = new ReachabilitySet(this);
+ rsOut.possibleReachabilities.add(ttsIn);
+ return rsOut.makeCanonical();
+ }
- return new ReachabilitySet( possibleReachabilitiesNew ).makeCanonical();
- }
+ public ReachabilitySet intersection(ReachabilitySet rsIn) {
+ assert rsIn != null;
- public Iterator iterator() {
- return possibleReachabilities.iterator();
+ ReachabilitySet rsOut = new ReachabilitySet();
+
+ Iterator i = this.iterator();
+ while( i.hasNext() ) {
+ TokenTupleSet tts = (TokenTupleSet) i.next();
+ if( rsIn.possibleReachabilities.contains(tts) ) {
+ rsOut.possibleReachabilities.add(tts);
+ }
}
- public ReachabilitySet union( ReachabilitySet rsIn ) {
- assert rsIn != null;
+ return rsOut.makeCanonical();
+ }
- ReachabilitySet rsOut = new ReachabilitySet( this );
- rsOut.possibleReachabilities.addAll( rsIn.possibleReachabilities );
- return rsOut.makeCanonical();
- }
- public ReachabilitySet union( TokenTupleSet ttsIn ) {
- assert ttsIn != null;
+ public ReachabilitySet add(TokenTupleSet tts) {
+ assert tts != null;
+ ReachabilitySet rsOut = new ReachabilitySet(tts);
+ return rsOut.union(this);
+ }
- ReachabilitySet rsOut = new ReachabilitySet( this );
- rsOut.possibleReachabilities.add( ttsIn );
- return rsOut.makeCanonical();
- }
- public ReachabilitySet intersection( ReachabilitySet rsIn ) {
- assert rsIn != null;
+ public ChangeTupleSet unionUpArityToChangeSet(ReachabilitySet rsIn) {
+ assert rsIn != null;
- ReachabilitySet rsOut = new ReachabilitySet();
+ ChangeTupleSet ctsOut = new ChangeTupleSet();
- Iterator i = this.iterator();
- while( i.hasNext() ) {
- TokenTupleSet tts = (TokenTupleSet) i.next();
- if( rsIn.possibleReachabilities.contains( tts ) ) {
- rsOut.possibleReachabilities.add( tts );
- }
- }
+ Iterator itrO = this.iterator();
+ while( itrO.hasNext() ) {
+ TokenTupleSet o = (TokenTupleSet) itrO.next();
- return rsOut.makeCanonical();
- }
-
- /*
- public ReachabilitySet unionUpArity( ReachabilitySet rsIn ) {
- assert rsIn != null;
-
- ReachabilitySet rsOut = new ReachabilitySet();
- Iterator itrIn;
- Iterator itrThis;
-
- itrIn = rsIn.iterator();
- while( itrIn.hasNext() ) {
- TokenTupleSet ttsIn = (TokenTupleSet) itrIn.next();
-
- boolean foundEqual = false;
-
- itrThis = this.iterator();
- while( itrThis.hasNext() ) {
- TokenTupleSet ttsThis = (TokenTupleSet) itrThis.next();
-
- if( ttsIn.equalWithoutArity( ttsThis ) ) {
- rsOut.possibleReachabilities.add( ttsIn.unionUpArity( ttsThis ) );
- foundEqual = true;
- continue;
- }
- }
-
- if( !foundEqual ) {
- rsOut.possibleReachabilities.add( ttsIn );
- }
- }
+ Iterator itrR = rsIn.iterator();
+ while( itrR.hasNext() ) {
+ TokenTupleSet r = (TokenTupleSet) itrR.next();
- itrThis = this.iterator();
- while( itrThis.hasNext() ) {
- TokenTupleSet ttsThis = (TokenTupleSet) itrThis.next();
+ TokenTupleSet theUnion = new TokenTupleSet();
- boolean foundEqual = false;
+ Iterator itrRelement = r.iterator();
+ while( itrRelement.hasNext() ) {
+ TokenTuple e = (TokenTuple) itrRelement.next();
- itrIn = rsIn.iterator();
- while( itrIn.hasNext() ) {
- TokenTupleSet ttsIn = (TokenTupleSet) itrIn.next();
+ if( o.containsToken(e.getToken() ) ) {
+ theUnion = theUnion.union(new TokenTupleSet(e.increaseArity() ) ).makeCanonical();
+ } else {
+ theUnion = theUnion.union(new TokenTupleSet(e) ).makeCanonical();
+ }
+ }
- if( ttsThis.equalWithoutArity( ttsIn ) ) {
- foundEqual = true;
- continue;
- }
- }
+ Iterator itrOelement = o.iterator();
+ while( itrOelement.hasNext() ) {
+ TokenTuple e = (TokenTuple) itrOelement.next();
- if( !foundEqual ) {
- rsOut.possibleReachabilities.add( ttsThis );
- }
+ if( !theUnion.containsToken(e.getToken() ) ) {
+ theUnion = theUnion.union(new TokenTupleSet(e) ).makeCanonical();
+ }
}
- return rsOut.makeCanonical();
- }
- */
+ if( !theUnion.isEmpty() ) {
+ ctsOut = ctsOut.union(
+ new ChangeTupleSet(new ChangeTuple(o, theUnion) )
+ );
+ }
+ }
+ }
+
+ return ctsOut.makeCanonical();
+ }
+
+
+ public ReachabilitySet ageTokens(AllocationSite as) {
+ assert as != null;
- public ChangeTupleSet unionUpArityToChangeSet( ReachabilitySet rsIn ) {
- assert rsIn != null;
+ ReachabilitySet rsOut = new ReachabilitySet();
- ChangeTupleSet ctsOut = new ChangeTupleSet();
+ Iterator itrS = this.iterator();
+ while( itrS.hasNext() ) {
+ TokenTupleSet tts = (TokenTupleSet) itrS.next();
+ rsOut.possibleReachabilities.add(tts.ageTokens(as) );
+ }
- Iterator itrO = this.iterator();
- while( itrO.hasNext() ) {
- TokenTupleSet o = (TokenTupleSet) itrO.next();
+ return rsOut.makeCanonical();
+ }
- Iterator itrR = rsIn.iterator();
- while( itrR.hasNext() ) {
- TokenTupleSet r = (TokenTupleSet) itrR.next();
- TokenTupleSet theUnion = new TokenTupleSet();
+ public ReachabilitySet pruneBy(ReachabilitySet rsIn) {
+ assert rsIn != null;
- Iterator itrRelement = r.iterator();
- while( itrRelement.hasNext() ) {
- TokenTuple e = (TokenTuple) itrRelement.next();
+ ReachabilitySet rsOut = new ReachabilitySet();
- if( o.containsToken( e.getToken() ) ) {
- theUnion = theUnion.union( new TokenTupleSet( e.increaseArity() ) ).makeCanonical();
- } else {
- theUnion = theUnion.union( new TokenTupleSet( e ) ).makeCanonical();
- }
- }
+ Iterator itrB = this.iterator();
+ while( itrB.hasNext() ) {
+ TokenTupleSet ttsB = (TokenTupleSet) itrB.next();
- Iterator itrOelement = o.iterator();
- while( itrOelement.hasNext() ) {
- TokenTuple e = (TokenTuple) itrOelement.next();
+ boolean subsetExists = false;
- if( !theUnion.containsToken( e.getToken() ) ) {
- theUnion = theUnion.union( new TokenTupleSet( e ) ).makeCanonical();
- }
- }
+ Iterator itrA = rsIn.iterator();
+ while( itrA.hasNext() && !subsetExists ) {
+ TokenTupleSet ttsA = (TokenTupleSet) itrA.next();
- if( !theUnion.isEmpty() ) {
- ctsOut = ctsOut.union(
- new ChangeTupleSet( new ChangeTuple( o, theUnion ) )
- );
- }
- }
+ if( ttsA.isSubset(ttsB) ) {
+ subsetExists = true;
}
+ }
- return ctsOut.makeCanonical();
+ if( subsetExists ) {
+ rsOut.possibleReachabilities.add(ttsB);
+ }
}
+ return rsOut.makeCanonical();
+ }
- public ReachabilitySet ageTokens( AllocationSite as ) {
- ReachabilitySet rsOut = new ReachabilitySet();
+ public ReachabilitySet exhaustiveArityCombinations() {
+ ReachabilitySet rsOut = new ReachabilitySet();
- Iterator itrS = this.iterator();
- while( itrS.hasNext() ) {
- TokenTupleSet tts = (TokenTupleSet) itrS.next();
- rsOut.possibleReachabilities.add( tts.ageTokens( as ) );
- }
+ int numDimensions = this.possibleReachabilities.size();
- return rsOut.makeCanonical();
- }
+ // add an extra digit to detect termination
+ int[] digits = new int[numDimensions+1];
+
+ int minArity = 0;
+ int maxArity = 2;
+ // start with the minimum possible coordinate
+ for( int i = 0; i < numDimensions+1; ++i ) {
+ digits[i] = minArity;
+ }
- public boolean equals( Object o ) {
- if( !(o instanceof ReachabilitySet) ) {
- return false;
+ // and stop when the highest-ordered axis rolls above the minimum
+ while( digits[numDimensions] == minArity ) {
+
+ // spit out a "coordinate" made from these digits
+ TokenTupleSet ttsCoordinate = new TokenTupleSet();
+ Iterator<TokenTupleSet> ttsItr = this.iterator();
+ for( int i = 0; i < numDimensions; ++i ) {
+ assert ttsItr.hasNext();
+ TokenTupleSet ttsUnit = ttsItr.next();
+ for( int j = 0; j < digits[i]; ++j ) {
+ ttsCoordinate = ttsCoordinate.unionUpArity( ttsUnit );
}
+ }
+ rsOut = rsOut.add( ttsCoordinate.makeCanonical() );
+
+ // increment
+ for( int i = 0; i < numDimensions+1; ++i ) {
+ digits[i]++;
+ if( digits[i] > maxArity ) {
+ // this axis reached its max, so roll it back to min and increment next higher digit
+ digits[i] = minArity;
+
+ } else {
+ // this axis did not reach its max so we just enumerated a new unique coordinate, stop
+ break;
+ }
+ }
+ }
+
+ return rsOut.makeCanonical();
+ }
+
- ReachabilitySet rs = (ReachabilitySet) o;
- return possibleReachabilities.equals( rs.possibleReachabilities );
+ public boolean equals(Object o) {
+ if( o == null ) {
+ return false;
}
- public int hashCode() {
- return possibleReachabilities.hashCode();
+ if( !(o instanceof ReachabilitySet) ) {
+ return false;
}
+ ReachabilitySet rs = (ReachabilitySet) o;
+ return possibleReachabilities.equals(rs.possibleReachabilities);
+ }
- public String toStringEscapeNewline() {
- String s = "[";
+ public int hashCode() {
+ return possibleReachabilities.hashCode();
+ }
- Iterator i = this.iterator();
- while( i.hasNext() ) {
- s += i.next();
- if( i.hasNext() ) {
- s += "\\n";
- }
- }
- s += "]";
- return s;
+ public String toStringEscapeNewline() {
+ String s = "[";
+
+ Iterator i = this.iterator();
+ while( i.hasNext() ) {
+ s += i.next();
+ if( i.hasNext() ) {
+ s += "\\n";
+ }
}
- public String toString() {
- String s = "[";
+ s += "]";
+ return s;
+ }
- Iterator i = this.iterator();
- while( i.hasNext() ) {
- s += i.next();
- if( i.hasNext() ) {
- s += "\n";
- }
- }
+ public String toString() {
+ String s = "[";
- s += "]";
- return s;
+ Iterator i = this.iterator();
+ while( i.hasNext() ) {
+ s += i.next();
+ if( i.hasNext() ) {
+ s += "\n";
+ }
}
+
+ s += "]";
+ return s;
+ }
}
projects / IRC.git / blobdiff