Resurrecting RestrictedSet

While spelunking in Ruby's stdlib I came across the description and partial implementation of an interesting data structure called RestrictedSet. It behaves like a Ruby Set but also requires a block to be given (called a restriction proc) which determines if an object is eligible for membership. If the result of calling the restriction proc with a given object is falsey, the object is rejected (see my implementation: restricted_set).

# Initialize with or without an enumerable object
set = RestrictedSet.new(-2..2) { |o| o > 0 }
set.add(1)
set.add(-1)
set.add(42)
set #=> #<RestrictedSet: {1, 2, 42}>
# Accessing the restriction proc
f = set.restriction_proc
p f.call(-4) #=> false
p f.call(4) #=> true

RestrictedSet also accommodates restrictions which depend on the current set. If the restriction proc has an arity of 2, the current set and the object in question are yielded as the first and second arguments, respectively.

set = RestrictedSet.new do |current_set, _|
  current_set.count + 1 <= 2 # Maximum of 2 objects
end
set << :a << :a << :b << :c
set #=> #<RestrictedSet: {:a, :b}>

Inheriting from RestrictedSet works well for creating reusable types of restricted sets. By overriding the initializer to pass a block to super, the restriction logic can be encapsulated in a class with a descriptive name.

class SymbolSet < RestrictedSet
  def initialize(enum = nil)
    super(enum) { |o| Symbol === o }
  end
end

SymbolSet.new(["alpha", :beta]) #=> #<SymbolSet: {:beta}>

require 'prime'
class PrimeSet < RestrictedSet
  def initialize(enum = nil)
    super enum, &Prime.method(:prime?) # using Method#to_proc
  end
end

(1..100).to_set(PrimeSet) #=> #<PrimeSet: {2, 3, 5, 7, 11, 13, 17, 19, ...}>

class NullSet < RestrictedSet
  def initialize(enum = nil)
    super(enum) { false }
  end
end

NullSet[1, 'a', :b] #=> #<NullSet: {}>

Maybe someone can find a use for RestrictedSet in the real world :smile:. If you know why it was never implemented, please share. As always, pull requests welcome.

Revibalog

Resurrecting RestrictedSet