module Setfu

Version 3.1.0 and older

Constants

VERSION

Public Class Methods

bset_elements(ary) click to toggle source
# File lib/setfu.rb, line 201
def self.bset_elements(ary)
  ary.count.times do |ii|
    ary[ii] = ary[ii].to_bset
  end
end
find_tuple(ary, tup_size) click to toggle source
# File lib/setfu.rb, line 212
def self.find_tuple(ary, tup_size)  # assumes ary is comprised of sets
  candidates = {}
  entropy = 0
  ary.count.times do |ii|
    entropy = ary[ii].entropy > entropy ? ary[ii].entropy : entropy
    unless ary[ii].setfu_count?
      ary[ii].setfu_count = ary[ii].count  # store this as #count is slow
    end
    next unless ary[ii].setfu_count == tup_size
    tup = ary[ii].to_i  # integer keys are good Hash keys, BitSets are not
    candidates[tup] = 0  # store integer version of set in candidate hash if size matches
    ary.count.times do |jj|
      candidates[tup] +=1 if ary[ii]==ary[jj]  # vote count each match
    end
  end
  valid = []
  error = []
  candidates.each_pair do |key,val|
    bset = BitSet.new
    bset.set_bits!(key)
    bset.entropy=entropy
    if val==tup_size
      bset.setfu_tag
      valid.push bset
    elsif val>tup_size
      error.push bset
    end
  end
  group = []
  ary.count.times do |ii|
    next if ary[ii].setfu_tag?
    next if ary[ii].setfu_count > tup_size
    next if ary[ii] <= valid
    next if ary[ii] <= error
    group.push ary[ii]
  end
  
  if (tup_size >=3) && (group.count >= tup_size)  # stardard match finds smaller things ...
    ptup = []
    group.combination(tup_size) do |combo|
      ta = combo.to_bset
      next unless ta.count == tup_size
      next if ta <= error
      if ta <= ptup  # we have an error! There can only be one tuple
        pp = []
        ptup.count.times do |ii|
          pp.push ptup[ii] unless ta==ptup[ii]
        end
        ptup = pp
        error.push ta
      else
        ptup.push ta
      end
    end    
    valid.concat ptup
  end
  
  # ok everything is in the bin ... what about the shorts of the previous calls?
  # let's just mark what we know for next time ...
  ary.count.times do |ii|
    next if ary[ii].setfu_tag?
    if ary[ii] <= valid
      ary[ii].setfu_tag = :valid
    elsif ary[ii] <= error
      ary[ii].setfu_tag = :error
    end
  end
  
  return [valid,error]
end
reduce(ary) click to toggle source
# File lib/setfu.rb, line 306
def self.reduce(ary)
  elms = ary.count
  # process tupples ... first check for errors
  tups = tuples(ary)
  unless (tups.last.empty?)
    ary.setfu_tag = tups.last  # tag with broken set items
    return -1  # can't reduce a system of errors
  end
  if (tups.first.empty?)
    return 0
  end
  tups = tups[0].reverse  # we only need the good ones.
  reductions = 0
  loop do
    tup = tups.pop    
    elms.times do |idx|
      if (tup ** ary[idx]) && !(ary[idx] <= tup)
        ary[idx] -= tup
        reductions += 1
      end
    end
    break if tups.empty?
  end
  return reductions
end
tuple(ary) click to toggle source

returns the tuple, else nil

# File lib/setfu.rb, line 333
def self.tuple(ary)
  tup = ary.to_bset
  return nil unless tup.size==ary.count
  return tup if ary.size == 1 # trivial case
  if ary.size==2
    return tup if ary.first==ary.last
  end
  ary.count.times do |idx|
    ta = ary - [ary[idx]]
    return nil if tuple?(ta)
  end
  return tup
end
tuple?(ary) click to toggle source

the whole thing must be a tuple else false

# File lib/setfu.rb, line 348
def self.tuple?(ary)  # from documentation
  return false if ary.empty?
  tup = ary.to_bset
  return false unless tup.size==ary.count
  return true if ary.size == 1 # trivial case
  if ary.size==2
    return true if ary.first==ary.last
  end
  ary.count.times do |idx|
    ta = ary - [ary[idx]]
    return false if tuple?(ta)
  end
  return true
end
tuples(ary) click to toggle source
# File lib/setfu.rb, line 283
def self.tuples(ary)  # errors include empty sets
  src = []
  valid = []
  error = []
  ary.each do |bs|
    if bs.empty?
      error.setfu_push_unique bs
    else
      src.push bs  
    end
  end
  src.count.times do |tup_no|
    rslt = find_tuple(src, tup_no)
    valid.concat rslt[0]
    error.concat rslt[1] # was 2 ... but removed short
  end
  src.count.times do |idx|
    next if src[idx] <= valid
    next if src[idx] <= error
  end
  return [valid,error] if true
end
untag_bset_elements(ary) click to toggle source
# File lib/setfu.rb, line 206
def self.untag_bset_elements(ary)
  ary.count.times do |ii|
    ary[ii].remove_instance_variable :@bo_setfu_tag rescue :never_mind
    ary[ii].remove_instance_variable :@bo_setfu_count rescue :never_mind
  end
end