Cantor

Fast implementation of finite and complement sets in Ruby

Finite set that contains no elements

Finite set containing each element in enum, whose domain of discourse is unrestricted

Finite set containing each element in enum, whose domain of discourse is universe

Infinite set containing every value in the universe

Set containing every value except those in enum. Finite when enum is infinite. Infinite when enum is finite

• xs.include?(x)
• xs.exclude?(x)
• xs.finite?
• xs.infinite?
• xs.empty?
• xs.size
• xs.replace(ys)
• ~xs
• xs.complement
• xs + xs
• xs | ys
• xs.union(ys)
• xs - ys
• xs.difference(ys)
• xs ^ ys
• xs.symmetric_difference(ys)
• xs & ys
• xs.intersection(ys)
• xs <= ys
• xs.subset?(ys)
• xs < ys
• xs.proper_subset?(ys)
• xs >= ys
• xs.superset?(ys)
• xs > ys
• xs.proper_superset?(ys)
• xs.disjoint?(ys)
• xs == ys

Sets with a finite domain of discourse are represented using a bit string of 2^U bits, where U is the size of the domain. This provides nearly O(1) constant-time implementation using bitwise operations for all of the above set operations.

The bit string is represented as an Integer, but as the domain grows larger than 0.size * 8 - 2 items, the type is automatically expanded to a Bignum. Bitwise operations on Bignums are O(U), which is still be significantly faster than using the default Set library.

Sets with an unrestricted domain of discourse are implemented using a Hash. Unary operations and membership tests are O(1) constant-time. Binary operations on these sets is close to that of the default Set library.