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