raicesRuffini :: Polinomio Int -> [Int]

    λ> ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
    λ> ejPol1
    3*x^4 + -5*x^2 + 3
    λ> raicesRuffini ejPol1
    []
    λ> ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
    λ> ejPol2
    x^5 + 5*x^2 + 4*x
    λ> raicesRuffini ejPol2
    [0,-1]
    λ> ejPol3 = consPol 4 6 (consPol 1 2 polCero)
    λ> ejPol3
    6*x^4 + 2*x
    λ> raicesRuffini ejPol3
    [0]
    λ> ejPol4 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))
    λ> ejPol4
    x^3 + 2*x^2 + -1*x + -2
    λ> raicesRuffini ejPol4
    [1,-1,-2]

module Pol_Raices_enteras_de_un_polinomio where

import TAD.Polinomio (Polinomio, consPol, polCero, esPolCero)
import Pol_Termino_independiente_de_un_polinomio (terminoIndep)
import Pol_Regla_de_Ruffini (cocienteRuffini)
import Pol_Reconocimiento_de_raices_por_la_regla_de_Ruffini (esRaizRuffini)
import Test.Hspec (Spec, hspec, it, shouldBe)

raicesRuffini :: Polinomio Int -> [Int]
raicesRuffini p
  | esPolCero p = []
  | otherwise   = aux (0 : divisores (terminoIndep p))
  where aux [] = []
        aux (r:rs)
          | esRaizRuffini r p = r : raicesRuffini (cocienteRuffini r p)
          | otherwise         = aux rs

-- (divisores n) es la lista de todos los divisores enteros de n. Por
-- ejemplo,
--    divisores 4     ==  [1,-1,2,-2,4,-4]
--    divisores (-6)  ==  [1,-1,2,-2,3,-3,6,-6]
divisores :: Int -> [Int]
divisores n = concat [[x,-x] | x <- [1..abs n], rem n x == 0]

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

spec :: Spec
spec = do
  it "e1" $
    raicesRuffini ejPol1 `shouldBe` []
  it "e2" $
    raicesRuffini ejPol2 `shouldBe` [0,-1]
  it "e3" $
    raicesRuffini ejPol3 `shouldBe` [0]
  it "e4" $
    raicesRuffini ejPol4 `shouldBe` [1,-1,-2]
  where
    ejPol1 = consPol 4 3 (consPol 2 (-5) (consPol 0 3 polCero))
    ejPol2 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))
    ejPol3 = consPol 4 6 (consPol 1 2 polCero)
    ejPol4 = consPol 3 1 (consPol 2 2 (consPol 1 (-1) (consPol 0 (-2) polCero)))

-- La verificación es
--    λ> verifica
--
--    e1
--    e2
--    e3
--    e4
--
--    Finished in 0.0013 seconds
--    4 examples, 0 failures

from src.Pol_Reconocimiento_de_raices_por_la_regla_de_Ruffini import \
    esRaizRuffini
from src.Pol_Regla_de_Ruffini import cocienteRuffini
from src.Pol_Termino_independiente_de_un_polinomio import terminoIndep
from src.TAD.Polinomio import Polinomio, consPol, esPolCero, polCero


# (divisores n) es la lista de todos los divisores enteros de n. Por
# ejemplo,
#    divisores(4)  == [1, 2, 4, -1, -2, -4]
#    divisores(-6) == [1, 2, 3, 6, -1, -2, -3, -6]
def divisores(n: int) -> list[int]:
    xs = [x for x in range(1, abs(n)+1) if n % x == 0]
    return xs + [-x for x in xs]

def raicesRuffini(p: Polinomio[int]) -> list[int]:
    if esPolCero(p):
        return []
    def aux(rs: list[int]) -> list[int]:
        if not rs:
            return []
        x, *xs = rs
        if esRaizRuffini(x, p):
            return [x] + raicesRuffini(cocienteRuffini(x, p))
        return aux(xs)

    return aux([0] + divisores(terminoIndep(p)))

# Verificación
# ============

def test_raicesRuffini() -> None:
    ejPol1 = consPol(4, 3, consPol(2, -5, consPol(0, 3, polCero())))
    assert raicesRuffini(ejPol1) == []
    ejPol2 = consPol(5, 1, consPol(2, 5, consPol(1, 4, polCero())))
    assert raicesRuffini(ejPol2) == [0, -1]
    ejPol3 = consPol(4, 6, consPol(1, 2, polCero()))
    assert raicesRuffini(ejPol3) == [0]
    ejPol4 = consPol(3, 1, consPol(2, 2, consPol(1, -1, consPol(0, -2, polCero()))))
    assert raicesRuffini(ejPol4) == [1, -1, -2]
    print("Verificado")

# La verificación es
#    >>> test_raicesRuffini()
#    Verificado