require 'finite-set'
require 'finite-map'
require 'generator'


class Category
  module Morphism
    def isomorphic?
      monomorphic? and epimorphic?
    end
  
    def endomap?
      domain == codomain
    end

    def idempotent?
      endomap? and self * self == self
    end
  
    def involution?
      endomap? and (self * self).identity?
    end

    def identity?
      endomap? and self == type.identity_morphism(domain)
    end

    def sections
      result = Set.new
      id = type.identity_morphism(codomain)
      category.Hom(codomain, domain).each{|s|
        result << s if self * s == id
      }
      result
    end

    def retractions
      result = Set.new
      id = type.identity_morphism(domain)
      category.Hom(codomain, domain).each{|r|
        result << r if r * self == id
      }
      result
    end

    def inverse
      unless isomorphic?
        raise "no inverse"
      else
        sections.pick
      end
    end
  end
end


class <<CategoryOfFiniteSets = Category.new
  def Hom(x,y)
    y ** x
  end

  def Ob
    ::Set
  end

  def Mor
    ::Map
  end
end


class Map
  alias monomorphic? injective?
  alias epimorphic?  surjective?
  include Category::Morphism

  def category
    CategoryOfFiniteSets
  end

  def self.identity_morphism(set)
    result = Map.phi(self)
    set.each{|x| result[x] = x}
    result
  end

  def identity?
    endomap? and all?{|x,y| x == y}
  end

  def each_section
    return self unless surjective?

    s = type.phi(domain)
    
    h = Hash.new
    each{|x,y| (h[y] ||= Array.new) << x}

    g = Generator.new(h)
    func = lambda{
      if g.end?
        yield(s.dup)
      else
        y, ary = g.pop
        ary.each{|x|
          s[y] = x
          func.call
        }
      end
    }
    func.call

    self
  end

  def each_retraction
    return self unless injective?

    r = type.phi(domain)
    each{|x,y| r[y] = x}

    d = domain()
    g = Generator.new(codomain - image)
    func = lambda{
      if g.end?
        yield(r.dup)
      else
        x = g.pop
        d.each{|y|
          r[x] = y
          func.call
        }
      end
    }
    func.call

    self
  end

  def sections
    result = Set.new
    each_section{|s| result << s}
    result
  end

  def retractions
    result = Set.new
    each_retraction{|r| result << r}
    result
  end
end


if __FILE__ == $0
  f = Map[0 => 10, 1 => 11, 2 => 12]
  f.codomain = f.image
  p f.monomorphic?
  p f.epimorphic?
  p f.isomorphic?
  
  f = Map[0 => 0, 1 => 2, 2 => 2]
  f.codomain = Set[0,1,2]
  p f.idempotent?
  
  f = Map[0 => 1, 1 => 0, 2 => 2]
  f.codomain = Set[0,1,2]
  p f.involution?
  
  f = Map[0 => 1, 1 => 2, 2 => 0]
  f.codomain = Set[0,1,2,3,4,5]
  p f.retractions.all?{|r| r * f == Map.identity_morphism(f.domain)}

  f = Map[0 => 1, 1 => 1, 2 => 0]
  f.codomain = Set[0,1]
  p f.sections.all?{|s| f * s == Map.identity_morphism(f.codomain)}
end