package commons

class GeradorDeCombinacao(n:Int, r:Int) {
  private var atual:List[Int] = null
	private var fim = false
  
  def next(): List[Int] = {
   if(fim) return null
   if(atual == null) atual = primeiraCombinacao()
   else {
     var indicePrimeiroElementoSomavel = getIndicePrimeiroElementoSomavel()
     // aqui indicePrimeiroElementoSomavel nunca sera -1 pois fim ja e true
     
     var anterior = atual.toList
     // Prefixo imutável
     atual = anterior.take(indicePrimeiroElementoSomavel)
     // Primeiro elemento somável (direita para esquerda)
     var referencia = anterior(indicePrimeiroElementoSomavel) + 1
     atual = atual + referencia
     // Sufixo a partir do primeiro elemento somável
     (referencia+1 until referencia+r-indicePrimeiroElementoSomavel).foreach { elemento =>
       atual = atual + elemento
     }
   }
   if(getIndicePrimeiroElementoSomavel() == -1) fim = true
   atual
  }
  
  def reset() {
    atual = null
    fim = false
  }
  
  def hasNext(): Boolean = {
    return ! fim
  }
  
  def getIndicePrimeiroElementoSomavel():Int = {
    var i = r-1
    while(i >= 0) {
       var elementoNaProximaCombinacao = atual(i)+1
       var elementoTeraValorValidoParaRElementos = (elementoNaProximaCombinacao <= (n - (r-i)))
       if(elementoTeraValorValidoParaRElementos)
         return i
       i -= 1
     }
     return -1
  }
  
  private def primeiraCombinacao(): List[Int] = {
	  var primeiraCombinacao = List[Int]() 
	  (0 until r).foreach { i => primeiraCombinacao = primeiraCombinacao + i }
    primeiraCombinacao    
  }
  
//object GeradorDeCombinacao {
//	def gera(n:Int, r:Int): List[List[Int]] = {
//	  var lista = List[List[Int]]()
//	  (0 until n).foreach { i:Int =>
//	    var combinacao = List(i)
//	    lista = lista + combinacao
//	  }
//	  lista
//	}
//}
  
//  def getIndicePrimeiroElementoSomavel():Int = {
//    var i = r-1
//    while(i >= 0) {
//       var elemento = this.atual(i)
//       var elementoNaProximaCombinacao = elemento+1
//       var indiceSeraMenorQueN = (elementoNaProximaCombinacao < n)
//       if(indiceSeraMenorQueN) {
//         var elementoTeraValorValidoParaRElementos = (elementoNaProximaCombinacao <= (n - (r-i)))
//         if(elementoTeraValorValidoParaRElementos)
//           return i
//       }
//       i -= 1
//     }
//     return -1
//  }

//  De 5 cartas, escolhe 3
//  Todas as combinacoes
//  (5 3) abcde
//  5!/ 3! (5-3)! = 5*4 / 2 = 10
//  abc abd abe acd ace ade bcd bce bde cde
//  012 013 014 023 024 034 123 124 134 234
  // veja que nao existe:
  
  
  // indiceMenorQueN
	 // 10,6
	 // 0, 1, 2, 3, 8, 9
	 // 0, 1, 2, 3, 8, 10 x: indice igual a n
  
  // elementoTeraValorValidoParaRElementos
	 // 10,6
	 // 0, 1, 2, 3, 9, 10 x: n-1 só podera estar por ultimo, n-2 em penultimo ou ultimo
	 // 0, 1, 7, 8, 9, 10 x: n-4, nao pode ter um 7 na posicao 2 
	 // i=5(r-1 = 6-1), valor max comb(5)= 9 = n-1 = n-(r-5)
	 // i=4, valor max comb(4)= 8 = n-2 = n-(r-4)
	 // i=3, valor max comb(3)= 7 = n-3 = n-(r-3)
	 // i=2, valor max comb(2)= 6 = n-4 = n-(r-2)
	 // i=1, valor max comb(1)= 5 = n-5 = n-(r-1)
	 // i=0, valor max comb(0)= 4 = n-6 = n-(r-0) = n-(r-i)
  // Exemplo:
	// 0, 1, 2, 3, 8, 9
	// n = 10
	// r = 6
	// i = 4
	// elemento = 8
	// futuro = 9
	// 9 <= 10-(6-4) = 8 ? NAO
  
  // i = 3
  // elemento = 3
  // futuro = 4
  // 4 <= 10-(6-3) = 7 ? SIM
  
  // Funciona para 2
//     var ultimoIndice = atual.takeRight(1)(0)
//     if(ultimoIndice+1 == n) {
//       var penultimoIndice = atual.takeRight(2)(0)
//       atual = (atual.take(r-2) + (penultimoIndice+1)) + (penultimoIndice+2)
//     }
//     else {
//       atual = atual.take(r-1) + (ultimoIndice+1)
//     }
  
}
