#!/usr/bin/ruby

require 'set'

class Set
#wszystkie podzbiory od najmniejszego do największego (lub o podanej liczbie elementów)
  def all_subsets size=-1
    ar = self.to_a
    subsets = Array.new
    cur = Set.new
    0.upto 2**self.size-1 do |key|
      cur.clear
      0.upto ar.size-1 do |k|
        cur.merge ar[k] unless (2**k & key)==0
      end
      subsets += [Set.new(cur)] if size==-1 || size==cur.size
    end
    subsets.sort { |x, y| x.size <=> y.size }
  end

#zwraca zbior w czytelnej formie
  def inspect
    b = '{'+self.to_a.join(', ')+'}'
  end
end

class RelationalSchema
  attr :attribs, true
  attr :dep, true

#zwraca w schemat w czytelnej formie
  def inspect
    b = "#Schemat relacyjny\n"
    b += sprintf "  Atrybuty: %s\n", self.attribs.inspect
    b += "  Zaleznosci:\n"
    self.dep.each { |l, r| b += sprintf "    %s->%s\n", l.inspect, r.inspect }
    b += "  Klucze kandydujace: "
    self.cand_keys.each { |k| b += k.inspect+" " }
    b += "\n  2PN: "+((self.is2nf?)?'Tak':'Nie')
    b += "\n  3PN: "+((self.is3nf?)?'Tak':'Nie')
    b
  end

#konstruktor (klucze jako tablica, zaleznosci jako tablica, w ktorej kazdy element jest postaci
# a,b->c )
  def initialize attribs=nil, dep=nil
    self.attribs = Set.new(attribs)
    self.dep = Hash.new
    return if dep==nil
    dep.each do |el|
      el = el.split '->'
      self.dep[el[0].split(',').to_set] = el[1].split(',').to_set
    end
  end

#uzupełnienie zbioru atrybutów
  def compl attribs
    comp = Set.new(attribs)
    while true
      added = 0
      self.dep.each do |left, right|
        if (left.subset? comp) and not (right.subset? comp)
	  comp.merge right
          added = 1
	end
      end
      break if added==0
    end
    comp
  end

#klucze kandydujące
  def cand_keys
    keys = Array.new
    self.attribs.all_subsets.each do |subset|
      if self.attribs == (self.compl subset)
        sub = false
	keys.each { |key| sub |= key.subset? subset }
	keys += [Set.new(subset)] unless sub
      end
    end
    keys
  end

#czy jest w 2PN?
  def is2nf?
    return self.uncomplete_func_dep.size == 0
  end

#przekształca relację rel do 2PN
  def to2nf
    s0 = Array.new
    s1 = Array.new
    s0[0] = self.clone
    while s0.size>0
      cur = s0.first
      if cur.is2nf?
        s1 += [s0.shift]
      else
        unc = cur.uncomplete_func_dep[0]
        s0 += s0.shift.decompose unc[0], unc[1]
      end
    end
    s1.to_set
  end

#czy jest w 3PN?
  def is3nf?
    return false unless self.is2nf?
    return self.nonkey_dep.size == 0
  end

#przekształca rel do 3PN
  def to3nf
    s1 = Array.new
    sd = Array.new
    if self.is2nf?
      s1 += [self.clone]
    else
      s1 += self.to2nf.to_a
    end
    while s1.size>0
      cur = s1.first
      if cur.is3nf?
        sd += [s1.shift]
      else
         nonkey = cur.nonkey_dep[0]
         s1 += s1.shift.decompose nonkey[0], nonkey[1]
      end
    end
    sd.to_set
  end

#znajduje niepelne zaleznosci funkcyjne kluczy
  def uncomplete_func_dep
    uncomplete = Array.new
    self.cand_keys.each do |k|
      unless k.size==1
        k.all_subsets.each do |atr|
          if (k != atr) && ((self.compl atr) != atr)
            uncomplete += [[atr, (self.compl atr) - atr]]
	  end
        end
      end
    end
    uncomplete
  end

#znajduje zaleznosci funkcyjne atrybutow niekluczowych
  def nonkey_dep
    nonkey_dep = Array.new
    non_key = Set.new(self.attribs)
    self.cand_keys.each { |key| non_key -= key }
    non_key.all_subsets.each do |atr|
      unless (self.compl atr) == atr
        nonkey_dep += [[atr, (self.compl atr) - atr]]
      end
    end
    nonkey_dep
  end

#rozbija schemat relacji na dwie relacje wzgledem zaleznosci left->right
  def decompose left, right
    r1 = RelationalSchema.new
    all = left+right
    r1.attribs = all
    dep = Hash.new
    self.dep.each { |l,r| dep[all & l] = all & r if (all & l).size>0 && (all & r).size>0 }
    r1.dep = dep.clone

    r2 = self.clone
    r2.attribs -= right
    dep = Hash.new
    r2.dep.each do |l, r|
      l += left if right.subset? l
      l -= right
      r -= right
      dep[l] = r if l.size>0 && r.size>0
    end
    r2.dep = dep
    [r1, r2]
  end
end