Created
March 23, 2011 22:32
-
-
Save gerardpaapu/884181 to your computer and use it in GitHub Desktop.
Sets represented as javascript functions, with an Object Oriented(tm) interface
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
var Set = function (test) { | |
this.test = test; | |
}; | |
Set.prototype = { | |
'add': function(s) { | |
return Set.add(this, s); | |
}, | |
'complement': function () { | |
return Set.complement(this); | |
}, | |
'union': function(s) { | |
return Set.union(this, s); | |
}, | |
'remove': function(v) { | |
return Set.remove(this, v); | |
}, | |
'intersection': function(s) { | |
return Set.intersection(this, s); | |
}, | |
'exclusiveDisjunction': function(s) { | |
return Set.exclusiveDisjunction(this, s); | |
}, | |
'subtract': function(s) { | |
return Set.subtract(this, s); | |
}, | |
'contains': function(v) { | |
return Set.contains(this, v); | |
} | |
}; | |
// Set ::== Set.empty() | |
// ::== Set.add(<Set>, v) | |
// ::== Set.remove(<Set>, v) | |
// ::== Set.complement(<Set>, v) | |
// ::== Set.union(<Set>, <Set>) | |
Set.empty = function () { | |
return new Set(function () { return false; }); | |
}; | |
Set.add = function (s, v1) { | |
return new Set(function (v2) { | |
return v2 === v1 || s.test(v2); | |
}); | |
}; | |
Set.complement = function(s) { | |
return new Set(function(v) { | |
return !s.test(v); | |
}); | |
}; | |
Set.union = function(s1, s2) { | |
return new Set(function (v) { | |
return s1(v) || s2(v); | |
}); | |
}; | |
// contains(s, v) -> boolean ; the membership test | |
// contains(empty(), _) -> false ; the empty Set contains no values | |
// contains(add(s, v), v) -> true ; add(s, v) always contains v | |
// contains(complement(s), v) = !contains(s, v) ; | |
// contains(union(s1, s2), v) = contains(s1, v) || contains(s2, v) ; | |
Set.contains = function(s, v) { | |
return s.test(v); | |
}; | |
// contains(Set.remove(s, v), v) -> false ; Set.remove(s, v) never contains v | |
Set.remove = function(s, v) { | |
var s2 = Set.complement(Set.add(v, Set.empty())); | |
return Set.intersection(s, s2); | |
}; | |
// intersection(s1, s2) -> a Set that contains only elements that are members of both s1 and s2 | |
// !intersect = !(s1 & s2) = !a | !a | |
// intersect = !(!a | !a) | |
Set.intersection = function(s1, s2) { | |
return Set.complement( | |
Set.union( | |
Set.complement(s1), | |
Set.complement(s2))); | |
}; | |
// subtract(s1, s2) -> a Set than contains all elements of s1 that are not members of s2 | |
Set.subtract = function (s1, s2) { | |
return Set.intersection(Set.complement(s2), s1); | |
}; | |
// exclusiveDisjunction(s1, s2) -> a Set that contains all members that are in either s1 or s2 but not both | |
Set.exclusiveDisjunction = function (s1, s2) { | |
return Set.intersection( | |
Set.complement(Set.intersection(s1, s2)), | |
Set.union(s1, s2)); | |
}; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment