--[=[
Módulo para convertir un DAG (GRAFO ACÍCCLICO DIRIGIDO) a HTML
Su uso principal es para mostrar los árboles genealógicos de los idiomas

Módo de uso: se debe llamar a la función dagAHtml, la misma debe recibir el DAG,
el cual consiste en un arreglo secuencial con los nodos. A su vez, cada nodo se representa
con un arreglo en donde el primer índice es un arreglo con los índices de los padres, el segundo
es un string con el texto del nodo y el tercero es un arreglo con los índices de los hijos. Si el
nodo no tiene padre o no tiene hijos, deben especificarse los arreglos vacíos.

Basado en el módulo Dag2Html hecho en OCaml (Campl4) http://cristal.inria.fr/~ddr/dag2html/
Traducido a Lua por Tmagc
--]=]

local insert = table.insert
local concat = table.concat

local mod = math.fmod
local max = math.max
local min = math.min

-- divisor común mayor
local function gcd(a, b)
    if a < b then
      return gcd(b, a)
    elseif b == 0 then
      return a
    else
      return gcd(b, mod(a, b))
    end
  end

local function conjunto_union(s1, s2)
    local s3 = {}
    for el,_ in pairs(s1) do
        s3 = true
    end
    for el,_ in pairs(s2) do
        s3 = true
    end
    return s3
end

local function conjunto_interseccion_vacio(s1, s2)
    for el,_ in pairs(s1) do
        if s2 then
            return false
        end
    end
    return true
end

local function concatenar(destino, origen)
    local off = #destino
    for i,v in ipairs(origen) do
        destino = v
    end
end

local function desplazamiento_a_la_izda(lista, inicio, fin, n)
    for i = inicio, fin, 1 do
        lista = lista
        lista = nil
    end
end

local function desplazamiento_a_la_dcha(lista, inicio, fin, n)
    for i = fin, inicio, -1 do
        lista = lista
        lista = nil
    end
end

-- identificadores para un nodo
local PADRES = 1
local VALOR = 2
local HIJOS = 3

-- identificadores para elementos
local NORMAL = 0
local GHOST = 1
local NADA = -1

-- identificadores HTML
local BARRA = 1
local ESPACIO = 2
local HR_IZDA = 3
local HR_CENTRO = 4
local HR_DCHA = 5
local IZDA = 6
local CENTRO = 7
local DCHA = 8

local TD = {
     = "&#124;",
     = "&nbsp;",
     = "<hr noshade size=1 width=\"50%\" align=left>",
     = "<hr noshade size=1>",
     = "<hr noshade size=1 width=\"50%\" align=right>",
     = "left",
     = "center",
     = "right"
}

local TR_INICIO = "<tr align=left>\n"
local TR_FIN = "</tr>\n"

-- contadores
local span_id_counter
local ghost_id_counter
local function reset_id_cnt()
    span_id_counter = 0
    ghost_id_counter = 0
end
local function new_span_id()
  span_id_counter = span_id_counter + 1
  return span_id_counter
end
local function new_ghost_id()
  ghost_id_counter = ghost_id_counter + 1
  return ghost_id_counter
end

-- constructores
local function elemento(tipo, id)
    if not tipo then
        tipo = NADA
    end
    if not id then
        id = -1
    end
    return {tipo=tipo, id=id}
end

local function dato(tipo, id, span)
    if not tipo then
        tipo = NADA
    end
    if not id then
        id = -1
    end
    if not span then
        span = -1
    end

    return {elem={tipo=tipo, id=id}, span=span}
end

local function copiar_dato(d)
    return {elem={tipo = d.elem.tipo, id = d.elem.id}, span=d.span}
end

local function copiar_fila(a)
    local b = {}
    for i,v in ipairs(a) do
        b = copiar_dato(v)
    end
    return b
end

local function copiar_tabla(t)
    local t1 = {}
    for i,fila in ipairs(t) do
        t1 = copiar_fila(fila)
    end
    return t1
end

-- comparadores
local function elementos_son_iguales(e1, e2)
    return e1.tipo == e2.tipo and e1.id == e2.id
end

local function datos_son_iguales(d1, d2)
    return d1.span == d2.span and elementos_son_iguales(d1.elem, d2.elem)
end

----------------------------------------------------------------------------
-- FUNCIONES PARA CREAR LA TABLA DEL DAG
----------------------------------------------------------------------------

local function ancestors(d)
    local a = {}
    for i,nodo in ipairs(d) do
        if #nodo == 0 then
            insert(a, i)
        end
    end
    return a
end

local function get_children(d, parents)
    local children_ = {}
    local children = {}
    for _,p in ipairs(parents) do
        if p.tipo == NORMAL then
            local e = d.id]
            for _,c in ipairs(e) do
                if not children_ then
                    children_ = true
                    insert(children, c) -- por las dudas preservo el orden de la lista porque así estaba en el original, para mí no hay problema en hacer hashing para eliminar duplicados pero no me la voy a jugar
                end
            end
        end
    end
    return children
end

local function get_block(t, i, j)
    if j > #t then
      return nil, nil, nil
    elseif j == #t then
      local x = t
      return {{x.elem, 1}}, 1, x.span
    else
      local x, y = t, t
      if y.span == x.span then
        local list, mpc, span = get_block(t, i, j + 1)
        assert(list)
        assert(mpc)
        local x1, c1 = list, list
        if elementos_son_iguales(x1, x.elem) then
            list = {x1, c1 + 1}
            mpc = max(mpc, c1 + 1)
        else
            insert(list, {x.elem, 1}) -- insert(list, 1, {x.elem, 1}), creía que la inserción la hacía al revés, pero empíricamente compruebo que no
            mpc = max(mpc, c1)
        end
        return list, mpc, span
      else
        return {{x.elem, 1}}, 1, x.span
      end
    end
end

local function group_by_common_children(d, list)
    local cnt = 1
    local nlcsl = {}
    for _,id in ipairs(list) do
        insert(nlcsl, {{id}, {}})
        for _,c in ipairs(d) do
            nlcsl = true
        end
        cnt = cnt + 1
    end

    local L = #nlcsl
    local i = 1
    while i <= L do
        local nl = nlcsl
        local cs = nlcsl
        for j=i+1,L,1 do
            local nl1 = nlcsl
            local cs1 = nlcsl
            if not conjunto_interseccion_vacio(cs, cs1) then
                concatenar(nl, nl1)
                cs = conjunto_union(cs, cs1)
                desplazamiento_a_la_izda(nlcsl, j+1, L+1, 1)
                L = L - 1
                i = 0 --reinicializo i = 1, pero considero el incremento al final
                break
            end
        end
        i = i + 1
    end

    local lista = {}

    for _,el in ipairs(nlcsl) do
        local span = new_span_id()
        for _,nl in ipairs(el) do
            insert(lista, dato(NORMAL, nl, span))
        end
    end

    return lista
end

local function insert_columns(t, nb, j)
    local t1 = {}
    for i,line in ipairs(t) do
        local line1 = {}
        t1 = line1
        for k,_ in ipairs(line) do
            if k < j then
                line1 = copiar_dato(line)
            elseif k == j then
                for r = 0,nb do
                    line1 = copiar_dato(line)
                end
            else
                line1 = copiar_dato(line)
            end
        end
    end
    return t1
end

local function treat_new_row(d, t)
    local i = #t
    local j = 1
    local children_ = {}
    while true do
        local parents, max_parent_colspan, span = get_block(t, i, j)
        if not parents or not max_parent_colspan then
            break
        end

        local children = get_children(d, parents)
        if #children == 0 then
            children = {dato(NADA, -1, new_span_id())}
        else
            for w,c in ipairs(children) do
                children = dato(NORMAL, c, new_span_id())
            end
        end

        local simple_parents_colspan = 0
        for _,p in ipairs(parents) do
            simple_parents_colspan = simple_parents_colspan + p
        end

        if mod(simple_parents_colspan, #children) == 0 then
            j = j + simple_parents_colspan
            local rep = simple_parents_colspan / #children
            for _,c in ipairs(children) do
                for z=1,rep do
                    insert(children_, c)
                end
            end
        else
            local parent_colspan = max_parent_colspan
            for _,p in ipairs(parents) do
                parent_colspan = (parent_colspan / gcd(parent_colspan, p)) * p
            end

            local parents_ = {}
            local k = j
            for _,p in ipairs(parents) do
                local to_add = parent_colspan / p - 1
                local l = k
                for _=p,1,-1 do
                    t = insert_columns(t, to_add, l)
                    l = l + to_add + 1
                end
                insert(parents_, {p, parent_colspan})
                k = k + parent_colspan
            end

            local parents_colspan = parent_colspan * #parents_
            local children_colspan = #children
            local g = gcd(parents_colspan, children_colspan)

            local rep = children_colspan / g
            for _,p in ipairs(parents_) do
                for _=p,1,-1 do
                    t = insert_columns(t, rep-1, j)
                    j = j + rep
                end
            end

            rep = parents_colspan / g
            for _,c in ipairs(children) do
                for z=1,rep do
                    insert(children_, c)
                end
            end
        end
    end

    for _,x in ipairs(children_) do
        if x.elem.tipo ~= NADA then
            insert(t, children_)
            return t, true
        end
    end

    return t, false
end

local function down_it(t, i, k)
    t = t
    for r = i, #t - 1 do
        t = dato(GHOST, new_ghost_id(), new_span_id())
    end
end

local function equilibrate(t)
    local ilast = #t
    local last = t
    local len = #last
    local j = 1
    while j <= len do
        local reset = false
        local x = last.elem
        if x.tipo == NORMAL then
            for i = 1, ilast-1 do
                for k = 1, len do
                    if t.elem.tipo == NORMAL and elementos_son_iguales(t.elem, x) then
                        down_it(t, i, k)
                        reset = true
                        break
                    end
                end
                if reset then
                    break
                end
            end
        end
        if reset then
            j = 1
        else
            j = j + 1
        end
    end
end

local function  group_elem(t)
    for i = 1, #t - 1 do
        for j = 2, #t do
            local x, y = t.elem, t.elem
            if x.tipo == NORMAL and y.tipo == NORMAL and elementos_son_iguales(x, y) then
                t.span = t.span
            end
        end
    end
end

local function  group_ghost(t)
    for i = 1, #t - 1 do
        for j = 2, #t do
            if t.elem.tipo == GHOST and t.elem.tipo == GHOST and t.span == t.span then
                t = copiar_dato(t)
            end
            if t.elem.tipo == GHOST and t.elem.tipo == GHOST and elementos_son_iguales(t.elem, t.elem) then
                t = copiar_dato(t)
                if i > 1 then
                    t.span = t.span
                end
            end
        end
    end
end

local function  group_children(t)
    for i, line in ipairs(t) do
        for j = 2, #line do
            if line.elem.tipo ~= NADA and elementos_son_iguales(line.elem, line.elem) then
                line.span = line.span
            end
        end
    end
end

local function group_span_by_common_children(d, t)
    local cs = {}
    local i = #t
    local line = t -- tiene sentido que i y line no se modifiquen en el resto de la función ??
    for j = 1, #line do
        if line.elem.tipo == NORMAL then
            local current_cs = {}
            local n = d.elem.id]
            for _,c in ipairs(n) do
                current_cs = true
            end
            if not conjunto_interseccion_vacio(cs, current_cs) then
                line.span = line.span
                cs = conjunto_union(cs, current_cs)
            else
                cs = current_cs
            end
        else
            cs = {}
        end
    end
end

local function find_same_parents(t, i, j1, j2, j3, j4)
    while i > 1 do
        local x1, x2, x3, x4 = t, t, t, t

        if x1.span == x4.span then
            return i, j1, j2, j3, j4
        end

        local j = j1-1
        while true do
            if j <= 0 then
                j1 = 1
                break
            elseif t.span ~= x1.span then
                j1 = j + 1
                break
            end
            j = j - 1
        end

        j = j2+1
        while true do
            if j > #t then
                j2 = j - 1
                break
            elseif t.span ~= x2.span then
                j2 = j - 1
                break
            end
            j = j + 1
        end

        j = j3-1
        while true do
            if j <= 0 then
                j3 = 1
                break
            elseif t.span ~= x3.span then
                j3 = j + 1
                break
            end
            j  = j - 1
        end

        j = j4+1
        while true do
            if j > #t then
                j4 = j - 1
                break
            elseif t.span ~= x4.span then
                j4 = j - 1
                break
            end
            j = j+1
        end

        i = i - 1
    end
    return i, j1, j2, j3, j4
end

local function find_linked_children(t, i, j1, j2, j3, j4)
    while i < #t do
        local x1, x2, x3, x4 = t, t, t, t

        local j = j1-1
        while true do
            if j <= 0 then
                j1 = 1
                break
            elseif t.span ~= x1.span then
                j1 = j + 1
                break
            end
            j = j-1
        end

        j = j2+1
        while true do
            if j > #t then
                j2 = j - 1
                break
            elseif t.span ~= x2.span then
                j2 = j - 1
                break
            end
            j = j+1
        end

        j = j3-1
        while true do
            if j <= 0 then
                j3 = 1
                break
            elseif t.span ~= x3.span then
                j3 = j + 1
                break
            end
            j = j-1
        end

        j = j4+1
        while true do
            if j > #t then
                j4 = j - 1
                break
            elseif t.span ~= x4.span then
                j4 = j - 1
                break
            end
            j = j+1
        end

        i = i + 1
    end
    return j1, j2, j3, j4
end

local function mirror_block(t, i1, i2, j1, j2)
    for i = i1, i2 do
        local line = t
        while j1 < j2 do
            local aux = copiar_dato(line)
            line = line
            line = aux
            j1 = j1 + 1
            j2 = j2 - 1
        end
    end
end

local function exch_blocks(t, i1, i2, j1, j2, j3, j4)
    for i = i1, i2 do
      local line = t
      local saved = copiar_fila(line)
      for j = j1, j2 do
        line = copiar_dato(saved)
      end
      for j = j3, j4 do
        line = copiar_dato(saved)
      end
    end
end

local function find_block_with_parents(t, i, jj1, jj2, jj3, jj4)
    local ii = i
    while true do
        local nii, njj1, njj2, njj3, njj4 = find_same_parents(t, i, jj1, jj2, jj3, jj4)
        if nii == ii and njj1 == jj1 and njj2 == jj2 and njj3 == jj3 and njj4 == jj4 then
            return ii, jj1, jj2, jj3, jj4
        end
        nii = min(ii, nii)
        jj1, jj2, jj3, jj4 = find_linked_children(t, nii, njj1, njj2, njj3, njj4)
        if njj1 == jj1 and njj2 == jj2 and njj3 == jj3 and njj4 == jj4 then
            return nii, jj1, jj2, jj3, jj4
        end
        ii = nii
    end
end

local function push_to_right(t, i, j1, j2)
    local line = t
    local j = j1+1
    while j ~= j2 do
        local jj1
        local x = line.elem
        if x.tipo == NADA then
            jj1 = j-1
        else
            local k = j-2
            while true do
                if k <= 0 then
                    jj1 = 1
                    break
                elseif not elementos_son_iguales(line.elem, x) then
                    jj1 = k + 1
                    break
                end
                k = k-1
            end
        end
        local jj2 = j-1
        local jj3 = j

        local jj4
        x = line.elem
        if x.tipo == NADA then
            jj4 = j
        else
            local k = j+1
            while true do
                if k > #line then
                    jj4 = k-1
                    break
                elseif not elementos_son_iguales(line.elem, x) then
                    jj4 = k-1
                    break
                end
                k = k+1
            end
        end

        local ini_jj1 = jj1
        local ii
        ii, jj1, jj2, jj3, jj4 = find_block_with_parents(t, i, jj1, jj2, jj3, jj4)
        if jj4 < j2 and jj2 < jj3 then
            exch_blocks(t, ii, i, jj1, jj2, jj3, jj4)
            j = jj4 + 1
        elseif jj4 < j2 and jj1 == ini_jj1 and jj2 <= jj4 then
            mirror_block(t, ii, i, jj1, jj4)
            j = jj4 + 1
        else
            break
        end
    end
    return j-1
end

local function push_to_left(t, i, j1, j2)
    local line = t
    local j = j2-1
    while j ~= j1 do
        local jj1
        local x = line.elem
        if x.tipo == NADA then
            jj1 = j
        else
            local k = j-1
            while true do
                if k <= 0 then
                    jj1 = 1
                    break
                elseif not elementos_son_iguales(line.elem, x) then
                    jj1 = k + 1
                    break
                end
                k = k-1
            end
        end

        local jj2 = j
        local jj3 = j+1

        local jj4
        x = line.elem
        if x.tipo == NADA then
            jj4 = j+1
        else
            local k = j+2
            while true do
                if k > #line then
                    jj4 = k-1
                    break
                elseif not elementos_son_iguales(line.elem, x) then
                    jj4 = k-1
                    break
                end
                k = k + 1
            end
        end

        local ini_jj4 = jj4
        local ii
        ii, jj1, jj2, jj3, jj4 = find_block_with_parents(t, i, jj1, jj2, jj3, jj4)
        if jj1 > j1 and jj2 < jj3 then
            exch_blocks(t, ii, i, jj1, jj2, jj3, jj4)
            j = jj1 - 1
        elseif jj1 > j1 and jj4 == ini_jj4 and jj3 <= jj1 then
            mirror_block(t, ii, i, jj1, jj4)
            j = jj1 - 1
        else
            break
        end
    end
    return j+1
end

local function fill_gap(t, i, j1, j2)
    local t1 = copiar_tabla(t)
    assert(t1)
    j2 = push_to_left(t1, i, j1, j2)
    j1 = push_to_right(t1, i, j1, j2)
    if j1 ~= j2 - 1 then
        return nil
    end
    local line = t1
    local x, y = line.span, line.span
    for j=j2,#line,1 do
        if line.span == y or elementos_son_iguales(t1.elem, t1.elem) then
            y = line.span
            line.span = x
            if i > 0 then
                t1.span = t1.span
            end
        else
            y = line.span
        end
    end
    return t1
end

local function treat_gaps(t)
    local i = #t

    local j = 3
    while j <= #t do
        local line = t
        local y = line.elem
        if y.tipo == NORMAL and not elementos_son_iguales(y, line.elem) then
            for k = j-2,1,-1 do
                if elementos_son_iguales(y, line.elem) then
                    local t1 = fill_gap(t, i, k, j)
                    if t1 then
                        t = t1
                        j = 2 -- reinicio j=3 pero le pongo 2 para que me lo incremente
                    end
                    break
                end
            end
        end
        j = j + 1
    end
    return t
end

local function group_span_last_row(t)
    local row = t
    for i=2,#row,1 do
        local x = row.elem
        if x.tipo ~= NADA and elementos_son_iguales(x, row.elem) then
            row.span = row.span
        end
    end
end

local function tablify(d)
    local t = {group_by_common_children(d, ancestors(d))}
    local continuar = false

    while true do
        t, continuar = treat_new_row(d, t)
        if not continuar then
            return t
        end

        equilibrate(t) -- opcional en la versión original
        group_elem(t)
        group_ghost(t)
        group_children(t)
        group_span_by_common_children(d, t)
        t = treat_gaps(t) -- opcional en la versión original
        group_span_last_row(t)
    end
end

local function fall(t)
    for i=2, #t do
        local line = t
        local j = 1
        while j <= #line do
            local x = line.elem
            if x.tipo == GHOST then
                local j2, i1

                local k = j+1
                while true do
                    if k > #line then
                        j2 = k-1
                        break
                    elseif not elementos_son_iguales(x, line.elem) then
                        j2 = k-1
                        break
                    end
                    k = k+1
                end

                k = i-1
                while true do
                    if k < 1 then
                        i1 = k+1
                        break
                    end
                    local row = t
                    if not ((j == 1 or row.span ~= row.span) and (j2 == #row or row.span) ~= row.span) then
                        i1 = k+1
                        break
                    end
                    k = k-1
                end

                if i1 ~= i and i1 ~= 1 and t.elem.tipo ~= NADA then
                    i1 = i
                end

                if i1 < i then
                    for m = 1,i1+1,-1 do
                        for l = j,j2,1 do
                            t.elem = elemento(t.elem.tipo, t.elem.id)
                            if m < i then
                                t.span = t.span
                            end
                        end
                    end
                    for l = j,j2,1 do
                        if i1 == 1 or t.elem.tipo == NADA then
                            t.elem.tipo = NADA
                        else
                            t = (l == j or t.span ~= t.span) and dato(GHOST, new_ghost_id(), new_span_id()) or copiar_dato(t)
                        end
                    end
                end
                j = j2+1

            else
                j = j+1
            end
        end
    end
end

local function fall2_cool_right(t, i1, i2, i3, j1, j2)
    local span = t.span

    for i=i2-1,1,-1 do
        for j=j1,j2-1,1 do
            t = (i-i2+i1 >= 1) and copiar_dato(t) or dato(NADA, -1, new_span_id())
        end
    end

    for i=#t,1,-1 do
        for j=j2,#t,1 do
            t = (i-i2+i1 >= 1) and copiar_dato(t) or dato(NADA, -1, new_span_id())
        end
    end

    local old_span = t.span
    local j = j1
    while j <= #t and t.span == old_span do
        t.span = span
        j = j + 1
    end
end

local function fall2_cool_left(t, i1, i2, i3, j1, j2)
    local span = t.span

    for i=i2-1,1,-1 do
        for j=j1+1,j2,1 do
            t = (i-i2+i1 >= 1) and copiar_dato(t) or dato(NADA, -1, new_span_id())
        end
    end

    for i=#t,1,-1 do
        for j=j1,1,-1 do
            t = (i-i2+i1 >= 1) and copiar_dato(t) or dato(NADA, -1, new_span_id())
        end
    end

    local old_span = t.span
    local j = j2
    while j >= 1 and t.span == old_span do
        t.span = span
        j = j - 1
    end
end

local function do_fall2_right(t, i1, i2, j1, j2)
    local i = #t
    local i3
    local f = false
    while not f do
        if i < 1 then
            i3 = 1
            break
        else
            for j=j2, #t, 1 do
                if t.elem.tipo ~= NADA then
                    i3 = i+1
                    f = true
                    break
                end
            end
        end
        i = i-1
    end

    local new_height = i3+i2-i1
    if new_height > #t then
        for cnt = new_height - #t, 1, -1 do
            local new_line = {}
            for k=1,#t,1 do
                new_line = dato(NADA, -1, new_span_id())
            end
            insert(t, new_line)
        end
    end
    fall2_cool_right(t, i1, i2, i3, j1, j2)
end

local function do_fall2_left(t, i1, i2, j1, j2)
    local i = #t
    local i3
    local f = false
    while not f do
        if i < 1 then
            i3 = 1
            break
        else
            for j=j1, 1, -1 do
                if t.elem.tipo ~= NADA then
                    i3 = i+1
                    f = true
                    break
                end
            end
        end
        i = i-1
    end

    local new_height = i3+i2-i1
    if new_height > #t then
        for cnt = new_height - #t, 1, -1 do
            local new_line = {}
            for k=1,#t,1 do
                new_line = dato(NADA, -1, new_span_id())
            end
            insert(t, new_line)
        end
    end
    fall2_cool_left(t, i1, i2, i3, j1, j2)
end

local function do_shorten_too_long(t, i1, j1, j2)
    for i=i1, #t-1, 1 do
        for j = j1, j2-1, 1 do
            t = copiar_dato(t)
        end
    end
    local l = #t
    for k = j1, j2-1, 1 do
        t = dato(NADA, -1, new_span_id())
    end
end

local function try_fall2_right(t, i, j)
    if t.elem.tipo ~= GHOST then
        return false
    end

    local i1
    local k = i-1
    while true do
        if k < 1 then
            i1 = 1
            break
        elseif t.elem.tipo ~= GHOST then
            i1 = k + 1
            break
        end
        k = k-1
    end

    local separated1 = true
    for w=i1-1,1,-1 do
        if j > 1 and t.span == t.span then
            separated1 = false
            break
        end
    end

    local j2
    local x = t.span
    k = j+1
    while true do
        if k > #t or (t.elem.tipo ~= GHOST or t.span ~= x) then
            j2 = k
            break
        end
        k = k+1
    end

    local separated2 = true
    for z = i+1, #t, 1 do
        if j2 > #t or t.span == t.span then
            separated2 = false
            break
        end
    end

    if not separated1 or not separated2 then
        return false
    end
    do_fall2_right(t, i1, i+1, j, j2)
    return true
end

local function try_fall2_left(t, i, j)
    if t.elem.tipo ~= GHOST then
        return false
    end

    local i1
    local k = i-1
    while true do
        if k < 1 then
            i1 = 1
            break
        elseif t.elem.tipo ~= GHOST then
            i1 = k + 1
            break
        end
        k = k-1
    end

    local separated1 = true
    for w=i1-1,1,-1 do
        if j < #t and t.span == t.span then
            separated1 = false
            break
        end
    end

    local j1
    local x = t.span
    k = j-1
    while true do
        if k < 1 or (t.elem.tipo ~= GHOST or t.span ~= x) then
            j1 = k
            break
        end
        k = k-1
    end

    local separated2 = true
    for z = i+1, #t, 1 do
        if j1 < 1 or t.span == t.span then
            separated2 = false
            break
        end
    end

    if not separated1 or not separated2 then
        return false
    end
    do_fall2_left(t, i1, i+1, j1, j)
    return true
end

local function try_shorten_too_long(t, i, j)
    if t.elem.tipo ~= GHOST then
        return false
    end

    local j2
    local x = t.span
    local k = j+1
    while true do
        if k > #t or t.elem.tipo ~= GHOST or t.span == x then
            j2 = k
            break
        end
        k = k+1
    end

    local i1
    k = i+1
    while true do
        if k > #t or t.elem.tipo ~= NORMAL then
            i1 = k
            break
        end
        k = k+1
    end

    local i2
    k = i1
    while true do
        if k > #t or t.elem.tipo ~= NADA then
            i2 = k
            break
        end
        k = k+1
    end

    local separated_left = true
    for w=i,i2-1,1 do
        if j > 0 and t.span == t.span then
            separated_left = false
            break
        end
    end

    local separated_right = true
    for z=i,i2-1,1 do
        if j2 <= #t and t.span == t.span then
            separated_left = false
            break
        end
    end

    if not separated_left or (not separated_right) or i2 <= #t then
        return false
    end

    do_shorten_too_long(t, i, j, j2)
    return true
end

local function fall2_right(t)
    local i = #t
    while i > 1 do
        for j = #t-1, 1, -1 do
            if try_fall2_right(t, i, j) then
                i = #t + 1 --reinicializo i, pero con #t+1 así se decrementa a #t
                break
            end
        end
        i = i - 1
    end
end

local function fall2_left(t)
    local i = #t
    while i > 1 do
        for j = 2, #t, 1 do
            if try_fall2_left(t, i, j) then
                i = #t + 1 --reinicializo i, pero con #t+1 así se decrementa a #t
                break
            end
        end
        i = i - 1
    end
end

local function shorten_too_long(t)
    local i = #t
    while i > 1 do
        for j = 2, #t, 1 do
            if try_shorten_too_long(t, i, j) then
                i = #t + 1 --reinicializo i, pero con #t+1 así se decrementa a #t
                break
            end
        end
        i = i - 1
    end
end

local function top_adjust(t)
    local di
    local i = 1
    local f = false
    while not f do
        if i > #t then
            di = i
        else
            for j=1, #t, 1 do
                if t.elem.tipo ~= NADA then
                    di = i
                    f = true
                    break
                end
            end
        end
        i = i+1
    end

    if di > 1 then
        desplazamiento_a_la_izda(t, di, #t, di-1)
    end
end

local function bottom_adjust(t)
    local last_i
    local i = #t
    local f = false
    while not f do
        if i < 1 then
            last_i = i
        else
            for j=1, #t, 1 do
                if t.elem.tipo ~= NADA then
                    last_i = i
                    f = true
                    break
                end
            end
        end
        i = i-1
    end

    if last_i < #t then
        for k=last_i+1,#t,1 do
            t = nil
        end
    end
end

local function table_of_dag(d)
    reset_id_cnt()
    local t = tablify(d)
    fall(t)
    fall2_right(t)
    fall2_left(t)
    shorten_too_long(t)
    top_adjust(t) -- borro las líneas de sobre al principio
    bottom_adjust(t) -- borro las líneas de sobre al final
    return t
end

----------------------------------------------------------------------------
-- FUNCIONES PARA CONVERTIR LA TABLA DEL DAG A HTML
----------------------------------------------------------------------------

local function table_to_html(d, t, titulo)
    local ht = {}

    local function td(colspan, align, dat)
        insert(ht, "<td")
        if colspan > 1 then
            insert(ht, " colspan="..tostring(colspan))
        end
        if dat == HR_IZDA then
            insert(ht, " align="..TD)
        elseif align == CENTRO or align == DCHA then
            insert(ht, " align="..TD)
        end
        insert(ht, ">")

        local x = TD
        if x then
            insert(ht, x)
        else
            insert(ht, dat)
        end
        insert(ht, "</td>\n")
    end

    local function line_elem_txt(i)
        insert(ht, TR_INICIO)
        local j = 1
        while j <= #t do
            local next_j = j+1
            while next_j <= #t and datos_son_iguales(t, t) do
                next_j = next_j + 1
            end
            local colspan = 3*(next_j-j)-2
            td(1, IZDA, ESPACIO)
            if t.elem.tipo == NORMAL then
                td(colspan, CENTRO, d.elem.id])
            elseif t.elem.tipo == GHOST then
                td(colspan, CENTRO, BARRA)
            else
                td(colspan, CENTRO, ESPACIO)
            end
            td(1, IZDA, ESPACIO)
            j = next_j
        end
        insert(ht, TR_FIN)
    end

    local function vbars_txt(k, i)
        insert(ht, TR_INICIO)
        local j = 1
        while j <= #t do
            local next_j = j+1
            while next_j <= #t and datos_son_iguales(t, t) do
                next_j = next_j + 1
            end
            local colspan = 3*(next_j-j)-2
            td(1, IZDA, ESPACIO)
            td(colspan, CENTRO, ((k > 1 and t.elem.tipo == NADA) or t.elem.tipo == NADA or t.elem.tipo == NADA) and ESPACIO or BARRA)
            td(1, IZDA, ESPACIO)
            j = next_j
        end
        insert(ht, TR_FIN)
    end

    local function exist_several_branches(i, k)
        for j=1,#t,1 do
            for j2=j+1,#t+1,1 do
                if j2 == #t+1 then
                    return false
                end
                if t.elem.tipo == NADA or t.span ~= t.span then
                    break
                end
                if not elementos_son_iguales(t.elem, t.elem) then
                    return true
                end
            end
        end
        return false
    end

    local function alone_bar_txt(i)
        insert(ht, TR_INICIO)
        local j = 1
        while j <= #t do
            local next_j = j+1
            while next_j <= #t and t.span == t.span do
                next_j = next_j + 1
            end
            local colspan = 3*(next_j-j) - 2

            local align = IZDA
            local dat = ESPACIO
            if t.elem.tipo ~= NADA and t.elem.tipo ~= NADA then
                align = CENTRO
                for j2=j,next_j-1,1 do
                    if t.elem.tipo ~= NADA then
                        dat = BARRA
                        break
                    end
                end
            end
            td(1, IZDA, ESPACIO)
            td(colspan, align, dat)
            td(1, IZDA, ESPACIO)
            j = next_j
        end
        insert(ht, TR_FIN)
    end

    local function hbars_txt(i, k)
        insert(ht, TR_INICIO)
        local j = 1
        while j <= #t do
            local next_j = j+1
            while next_j <= #t and ((t.elem.tipo == NADA and t.elem.tipo == NADA) or t.span == t.span) do
                next_j = next_j + 1
            end

            local l = j
            while l < next_j do
                local next_l = l+1
                if t.elem.tipo ~= NADA then
                    while next_l <= #t and datos_son_iguales(t, t) do
                        next_l = next_l + 1
                    end
                end
                assert(next_l <= next_j)

                local colspan = 3*(next_l-l)-2

                if t.elem.tipo == NADA or t.elem.tipo == NADA then
                    td(colspan+2, IZDA, ESPACIO)
                else
                    local function ph(dat)
                        return t.elem.tipo == NADA and ESPACIO or dat
                    end
                    if l == j and next_l == next_j then
                        td(1, IZDA, ESPACIO)
                        td(colspan, CENTRO, ph(BARRA))
                        td(1, IZDA, ESPACIO)
                    elseif l == j then
                        td(1, IZDA, ESPACIO)
                        td(colspan, DCHA, ph(HR_DCHA))
                        td(1, IZDA, ph(HR_CENTRO))
                    elseif next_l == next_j then
                        td(1, IZDA, ph(HR_CENTRO))
                        td(colspan, IZDA, ph(HR_IZDA))
                        td(1, IZDA, ESPACIO)
                    else
                        td(colspan+2, IZDA, ph(HR_CENTRO))
                    end
                end
                l = next_l
            end
            j = next_j
        end
        insert(ht, TR_FIN)
    end


    insert(ht, "<table border=0 cellspacing=0 cellpadding=0>\n")
    
    if type(titulo) == "string" and titulo ~= "" then
    	insert(ht, "<caption style=\"font-weight: bold\">"..titulo.."</caption>\n")
    	insert(ht, TR_INICIO)
    	td(1, IZDA, ESPACIO)
    	insert(ht, TR_FIN)
    end

    for i=1,#t,1 do
        line_elem_txt(i)
        if i < #t then
            vbars_txt(i+1, i)
            if exist_several_branches(i, i) then
                hbars_txt(i, i)
                alone_bar_txt(i)
            end
            if exist_several_branches(i, i+1) then
                hbars_txt(i, i+1)
                vbars_txt(i+1, i+1)
            end
        end
    end

    insert(ht, "</table>\n")
    return concat(ht)
end

local function print_arr(a)
	local t = {}
	insert(t, "{")
	for i,v in ipairs(a) do
		insert(t, tostring(v)..",")	
	end
	insert(t, "}")
	return concat(t)
end

local function print_dag(d)
	local t = {}
	insert(t, "{")
	for i, n in ipairs(d) do
		insert(t, "{")
		insert(t, print_arr(n)..", ")
		insert(t, "\""..n.."\", ")
		insert(t, print_arr(n).."\n")
		insert(t, "},")
	end
	insert(t, "}")
	error(concat(t))
end

local export = {}

function export.dagAHtml(d, titulo)
    return table_to_html(d, table_of_dag(d), titulo)
end

return export