class Fa::Automaton

The class representing a finite automaton. It contains a pointer to a +struct fa+ from libfa and provides Ruby wrappers for the various libfa operations.

Attributes

faptr[R]

Public Class Methods

new(faptr) click to toggle source
# File lib/fa.rb, line 19
def initialize(faptr)
  @faptr = faptr
end
release(faptr) click to toggle source
# File lib/fa.rb, line 205
def self.release(faptr)
  FFI::free(faptr)
end

Public Instance Methods

<=(other) click to toggle source

Returns whether other matches all the strings that self matches. other may match more strings than that.

@param [Fa::Automaton] other @return [Boolean]

# File lib/fa.rb, line 160
def <=(other); other.contains(self); end
==(other) click to toggle source

Returns whether self and other match the same set of strings

@param [Fa::Automaton] other @return [Boolean]

# File lib/fa.rb, line 140
def ==(other); equals(other); end
complement() click to toggle source

Produces the complement of self. self will not be modified. The resulting automaton will match all strings that do not match self.

@raise OutOfMemoryError if libfa fails to allocate memory @return [Fa::Automaton] the iterated automaton

# File lib/fa.rb, line 122
def complement
  from_ptr( FFI::complement(faptr) )
end
concat(other) click to toggle source

Concatenates self with other, corresponding to SO. Neither self nor other will be modified.

@param [Fa::Automaton] other @raise OutOfMemoryError if libfa fails to allocate memory @return [Fa::Automaton] the concatenation of self and other

# File lib/fa.rb, line 41
def concat(other)
  from_ptr( FFI::concat(faptr, other.faptr) )
end
contains(other) click to toggle source

Returns whether self matches all the strings that other matches. self may match more strings than that.

@param [Fa::Automaton] other @return [Boolean]

# File lib/fa.rb, line 147
def contains(other)
  # The C function works like fa1 <= fa2, and not how the
  # Ruby nomenclature would suggest it, so swap the arguments
  r = FFI::contains(other.faptr, faptr)
  raise Error if r < 0
  return r == 1
end
empty?() click to toggle source

Returns whether self is the empty automaton, i.e., matches no words at all @return [Boolean]

# File lib/fa.rb, line 178
def empty?; is_basic(:empty); end
epsilon?() click to toggle source

Returns whether self is the epsilon automaton, i.e., matches only the empty string @return [Boolean]

# File lib/fa.rb, line 183
def epsilon?; is_basic(:epsilon); end
equals(other) click to toggle source

Returns whether self and other match the same set of strings

@param [Fa::Automaton] other @return [Boolean]

# File lib/fa.rb, line 130
def equals(other)
  r = FFI::equals(faptr, other.faptr)
  raise Error if r < 0
  return r == 1
end
from_ptr(ptr) click to toggle source
# File lib/fa.rb, line 210
def from_ptr(ptr)
  raise OutOfMemoryError if ptr.null?
  Automaton.new(ptr)
end
intersect(other) click to toggle source

Produces the intersection of self and other. Neither self nor other will be modified. The resulting automaton will match all strings that simultaneously match self and other,

@param [Fa::Automaton] other @raise OutOfMemoryError if libfa fails to allocate memory @return [Fa::Automaton] the iterated automaton

# File lib/fa.rb, line 101
def intersect(other)
  from_ptr( FFI::intersect(faptr, other.faptr) )
end
is_basic(kind) click to toggle source

Returns whether self is the empty, epsilon or total automaton

@param [:empty, :epsilon, :total] kind @return [Boolean]

# File lib/fa.rb, line 166
def is_basic(kind)
  # FFI::is_basic checks if the automaton is structurally the same as
  # +basic+; we just want to check here if they accept the same
  # language. If is_basic fails, we therefore check for equality
  r = FFI::is_basic(faptr, kind)
  return true if r == 1
  return equals(Fa::make_basic(kind))
end
iter(min, max) click to toggle source

Produces an iteration of self, corresponding to +S{min,max}+. self will not be modified.

@param [Int] min the minimum number of matches @param [Int] max the maximum number of matches, use -1 for an

unlimited number of matches

@raise OutOfMemoryError if libfa fails to allocate memory @return [Fa::Automaton] the iterated automaton

# File lib/fa.rb, line 63
def iter(min, max)
  from_ptr( FFI::iter(faptr, min, max) )
end
maybe() click to toggle source

Produces an iteration of zero or one self, corresponding to S?. self will not be modified.

@raise OutOfMemoryError if libfa fails to allocate memory @return [Fa::Automaton] the iterated automaton

# File lib/fa.rb, line 90
def maybe
  iter(0, 1)
end
minimize() click to toggle source

Minimizes this automaton in place. Uses either Hopcroft’s or Brzozowski’s algorithm. Due to a stupid design mistake in libfa, the algorithm is selected through a global variable. It defaults to Hopcroft’s algorithm though.

@return [Fa::Automaton] this automaton

# File lib/fa.rb, line 29
def minimize
  r = FFI::minimize(faptr)
  raise Error if r < 0
  self
end
minus(other) click to toggle source

Produces the difference of self and other. Neither self nor other will be modified. The resulting automaton will match all strings that match self but not other,

@param [Fa::Automaton] other @raise OutOfMemoryError if libfa fails to allocate memory @return [Fa::Automaton] the iterated automaton

# File lib/fa.rb, line 112
def minus(other)
  from_ptr( FFI::minus(faptr, other.faptr) )
end
plus() click to toggle source

Produces an iteration of at least one self, corresponding to S+. self will not be modified.

@raise OutOfMemoryError if libfa fails to allocate memory @return [Fa::Automaton] the iterated automaton

# File lib/fa.rb, line 81
def plus
  iter(1, -1)
end
star() click to toggle source

Produces an iteration of any number of self, corresponding to S*. self will not be modified.

@raise OutOfMemoryError if libfa fails to allocate memory @return [Fa::Automaton] the iterated automaton

# File lib/fa.rb, line 72
def star
  iter(0, -1)
end
to_s() click to toggle source

Return the representation of self as a regular expression. Note that that regular expression can look pretty complicated, even for seemingly simple automata. Sometimes, minimizing the automaton before turning it into a string helps; sometimes it doesn’t.

@return [String] the regular expression for self

# File lib/fa.rb, line 196
def to_s
  rx = ::FFI::MemoryPointer.new :string
  rx_len = ::FFI::MemoryPointer.new :size_t
  r = FFI::as_regexp(faptr, rx, rx_len)
  raise OutOfMemoryError if r < 0
  str_ptr = rx.read_pointer()
  return str_ptr.null? ? nil : str_ptr.read_string()
end
total?() click to toggle source

Returns whether self is the total automaton, i.e., matches all possible words. @return [Boolean]

# File lib/fa.rb, line 188
def total?; is_basic(:total); end
union(other) click to toggle source

Produces the union of self with other, corresponding to +S|O+. Neither self nor other will be modified.

@param [Fa::Automaton] other @raise OutOfMemoryError if libfa fails to allocate memory @return [Fa::Automaton] the union of self and other

# File lib/fa.rb, line 51
def union(other)
  from_ptr( FFI::union(faptr, other.faptr) )
end