# modul Constraint Satisfaction Problem
# mengimplementasikan pemrosesan csp
module CSP

  # mendefinisikan variabel pada csp
  # Variable terdiri dari name dan domain (nilai yang variabel bisa ambil)
  # name => string
  # domain => array (biasanya integer)
  class Variable
    attr_reader :name
    attr_accessor :domain

    def initialize(name, domain)
      @name = name
      @domain = domain
    end

    def <=>(vars)
      self.name <=> vars.name
    end

    def to_s
      @name
    end
  end

  # constraint yang variabel harus penuhi
  # constraint => proc
  # contoh untuk constraint: Proc.new {|var1,var2| var1 > var2}
  # vars => array dari Variables
  class Constraint
    attr_reader :constraint, :vars

    def initialize(constraint, vars)
      @constraint = constraint
      @vars = vars
    end
  end

  # masalah csp
  # hanya terdiri dari Constraints
  # constraints => array dari Constraint
  class Problem
    attr_reader :constraints

    def initialize
      @constraints = Array.new
    end

    def add_constraint(cons)
      @constraints.push(cons)
    end
  end

  # pencari solusi dari csp
  # variables_ordering => array dari Variables
  # constraints => array dari Constraint
  # var_for_cons => hash (key => variable, value => array dari Constraint)
  # value_tracking => hash (key => variable, value => integer biasanya)
  # reducted_domain => hash (key => variable, value => array (biasanya integer))
  class Solver
    attr_reader :variable_ordering, :constraints, :var_for_cons, :value_tracking, :reducted_domain, :forward_checking, :bound, :branch_and_bound, :optimization_func, :bab_type, :fail_first, :new_order

    def initialize(problem)
      @constraints = problem.constraints
      @branch_and_bound = false
    end

    # memberitahu ke pencari solusi, variabel mana yang dikerjakan lebih dulu
    def set_ordering(ordering)
      @variable_ordering = ordering
    end

    # memberitahu pencari solusi bahwa ini masalah csp optimalisasi
    def set_branch_and_bound(bab,type)
      @branch_and_bound = bab
      if type == 'min' then
	@bab_type = 'min'
	@bound = 1/0.0
      elsif type == 'max' then
	@bab_type = 'max'
	@bound = -1/0.0
      else
	raise 'Tipe harus max atau min'
      end
    end

    # memberitahu pencari solusi fungsi optimalisasi yang dipakai
    def set_optimization_function(optimization)
      if @branch_and_bound then
	@optimization_func = optimization
      else
	raise 'Harus menggunakan teknik branch and bound untuk menggunakan metode ini'
      end
    end

    # mencari solusi dari csp
    def solve
      constraints_per_variable
      set_value_tracking
      set_reducted_domain
      iterating(0)
    end

    # apakah Anda ingin menggunakan forward checking?
    # fc => boolean
    def set_forward_checking(fc)
      @forward_checking = fc
    end

    # apakah Anda ingin menggunakan prinsip fail-first
    # ff => boolean
    def set_fail_first(ff)
      @fail_first = ff
    end

    private

    # menelusuri pohon variabel dengan nilai-nilainya dan backtrack jika dipelukan
    def iterating(level)
      # prinsip fail-first
      tmp_order = Array.new
      if @fail_first then
	# masukkan variabel yang memiliki nilai dulu
	level.times {|t|
	  tmp_order.push(@new_order[t])
	}
	@new_order = tmp_order
	# urutkan variabel masa depan dengan ukuran domainnya
	tmp_sort = @reducted_domain.reject {|key,value| @new_order.include?(key) }.sort_by {|key,value|
	             value.length
	           }
        # masukkan variabel masa depan
        tmp_sort.each {|value|
	  @new_order.push(value[0])
	}
      else
	@new_order = @variable_ordering
      end

      @reducted_domain[@new_order[level]].each {|node|

	# @value_tracking itu seperti ini { a => 1, b => 2, c => 5, d => nil }
	# kita ada di level b, dan kita telah melalui level a, tetapi belum level c dan level d 
	# jadi kita memberikan nilai "node" ke b pada @value_tracking tapi kita harus menghapus nilai pada level yang
	# belum sampai seperti c dan d
	path_clear_length = @new_order.length - (level + 1)
	variables_rejected = []
	path_clear_length.times {|time|
	  variables_rejected.push(@new_order[level+time+1])
	  @value_tracking[@new_order[level+time+1]] = nil
	}
	@value_tracking[@new_order[level]] = node

	passed_constraint = true
	# beriterasi ke setiap constraint yang variabel ini punya
	@var_for_cons[@new_order[level]].each {|cons|

	  # kita hanya gunakan constraint yang berkaitan dengan variabel pada level yang sudah kita capai
	  # jika kita ada di level b, dan telah mencapai level a tapi belum mencapai level c, kita tidak gunakan
	  # constraint untuk b dan c
	  if (cons.vars & (@new_order - variables_rejected)) == cons.vars then

	    # ubah variabel ini ke array sehingga kita bisa mengirimnya dengan mudah
	    # untuk constraint ini, iterasi ke setiap variabel, dan berikan variabel nilai (dari @value_tracking)
	    # untuk array temp_param jadi kita bisa mengirimnya ke pemanggilan proc constraint
	    temp_param = []
	    cons.vars.each {|var|
	      temp_param.push( @value_tracking[var] )
	    }
	    
	    # uji apakah pemberian nilai ini konsisten
	    if cons.constraint.call(*temp_param) then
	      passed_constraint = true
	    else
	      passed_constraint = false
	      break
	    end

	  end
	}


	# pemberian nilai pada level ini telah melewati semua constraint yang berkaitan dengannya
	if passed_constraint then

	  # csp optimalisasi
	  if @branch_and_bound then
	    if @bab_type == 'min' then
	      if @optimization_func.call(@value_tracking) < @bound then
		bound_flag = true
	      else
		bound_flag = false
	      end
	    elsif @bab_type == 'max' then
	      if @optimization_func.call(@value_tracking) > @bound then
		bound_flag = true
	      else
		bound_flag = false
	      end
	    end
	  end

	  # semua level sudah dicapai 
	  if @value_tracking.reject {|key, value| value.nil? }.length == @new_order.length then

	    # beri nilai ke bound jika menggunakan branch and bound
	    if @branch_and_bound then
	      if bound_flag then
		@bound = @optimization_func.call(@value_tracking)

		# menyimpan kombinasi nilai yang memenuhi seluruh syarat
		temp_str = []
		@value_tracking.sort {|a,b| a[1] <=> b[1]}.each {|var|
		  temp_str.push( var[0].name + ' => ' + var[1].to_s )
		}
		puts temp_str
	      end
	    else
	      # menyimpan kombinasi nilai yang memenuhi seluruh syarat
	      temp_str = []
	      @value_tracking.sort {|a,b| a[1] <=> b[1]}.each {|var|
		temp_str.push( var[0].name + ' => ' + var[1].to_s )
	      }
	      puts temp_str
	    end

	    print "\n"

	  else
	    if @forward_checking then
	      # menyimpan nilai-nilai variabel masa depan yang dihapus untuk dibangkitkan lagi
	      # keeper_deleted_value adalah hash di mana key dari hash ini adalah Variable 
	      # dan nilai dari hash adalah array nilai
	      keeper_deleted_value = {}

	      # pagar boolean untuk menuju ke level yang lebih dalam
	      goin_deeper = true

	      # iterasi semua variabel masa depan
	      # @value_tracking adalah hash di mana key adalah Variable dan nilai dari hash adalah nilai (biasanya integer)
	      # contohnya => { a => 1, b => 3, c => nil, d => nil } menunjukkan bahwa kita sudah mencapai a & b 
	      # tapi belum c & d
	      @value_tracking.find_all {|key, value| value.nil?}.each {|future_variable|

		# iterasi ini memberi [ Variable, nil ] tapi kita tidak membutuhkan nil-nya
		future_variable = future_variable[0]

		deleted_value = []
		# iterasi ke semua nilai dari domain variabel masa depan
		@reducted_domain[future_variable].each {|value|
		  
		  # iterasi ke semua constraint
		  @constraints.each {|cons|
		    # kita hanya tertarik constraint yang menghubungkan variabel sekarang dan variabel masa depan
		    if (cons.vars & [ future_variable, @new_order[level] ]).sort == [ future_variable, @new_order[level] ].sort then

		      temp_param = []
		      # buatlah lebih mudah untuk menguji constraint
		      cons.vars.each {|var|
			if var == future_variable then
			  temp_param.push(value)
			else
			  temp_param.push(@value_tracking[var])
			end
		      }

		      # uji apakah pemberian nilai untuk variabel masa depan dan variabel sekarang konsisten
		      if not cons.constraint.call(*temp_param) then
			# simpanlah nilai variabel masa depan
			deleted_value.push(value)
		      end

		    end
		  }
		}

		# buang nilai dari domain variabel masa depan yang tidak konsisten
		@reducted_domain[future_variable] -= deleted_value

		# jika domain dari variabel masa depan ini kosong maka diketahui pemberian nilai untuk variabel sekarang
		# tidak konsisten untuk keseluruhan masalah
		if @reducted_domain[future_variable].length == 0 then
		  goin_deeper = false
		end
		    
		# jagalah nilai-nilai yang sudah dihapus untuk dibangkitkan lagi nantinya
		keeper_deleted_value[future_variable] = deleted_value
		
	      }

	    end
	    
	    # masuk lebih dalam lagi ke pohon pencarian
	    if @forward_checking then
	      if @branch_and_bound then
		iterating(level+1) if goin_deeper and bound_flag
	      else
		iterating(level+1) if goin_deeper
	      end
	    else
	      if @branch_and_bound then
		iterating(level+1) if bound_flag
	      else
		iterating(level+1)
	      end
	    end
	    
	    # bangkitkan lagi nilai-nilai dari variabel masa depan
	    if @forward_checking then
	      keeper_deleted_value.each {|var, values|
		@reducted_domain[var] += values
	      }
	    end

	  end

	end
      }
    end

    # buat hash di mana key adalah variabel dan nilai adalah array constraint yang berkaitan dengan variabel itu
    def constraints_per_variable
      @var_for_cons = Hash.new
      @variable_ordering.each {|var|
	@var_for_cons[var] = Array.new 
	@constraints.each {|cons|
	  @var_for_cons[var].push(cons) if cons.vars.include?(var)
	}
      }
    end

    # buat hash di mana key dari hash adalah variabel dan nilai hash adalah nil (nantinya nilai hash akan menjadi
    # nilai dari node sementara
    def set_value_tracking
      @value_tracking = Hash.new
      @variable_ordering.each {|var|
	@value_tracking[var] = nil
      }
    end

    # buat hash di mana key dari hash adalah variabel dan nilai hash adalah domain dari variabel
    # nantinya jika kita menggunakan forward checking, kita perlu membuang nilai dari domain variabel masa depan sementara
    # dan bangkitkan nilainya
    def set_reducted_domain
      @reducted_domain = Hash.new
      @variable_ordering.each {|var|
	@reducted_domain[var] = var.domain
      }
    end
  end

end