Cantor Build Status

Fast implementation of finite and complement sets in Ruby

Constructors

Cantor.empty

Finite set that contains no elements

Cantor.build(enum)

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

Cantor.absolute(enum, universe)

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

Cantor.universal

Infinite set containing every value in the universe

Cantor.complement(enum)

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

Operations

  • 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

Performance

Sets with a finite domain of discourse are represented using a bit string of 2U 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.

Benchmarks

These benchmarks aren't intended to be useful. While they indicate the worst-case performance for Cantor, they probably don't show the worst case for the standard Set library.

Note "Relative" indicates Cantor sets with an infinite domain of discourse. This includes Cantor.build, Cantor.universal, and Cantor.complement. "Absolute" sets are Cantor sets with a finite domain of discourse, built from Cantor.absolute.