#!/usr/bin/env python3
# -*- coding: utf-8 -*-



from suffixArray import suffixArray


'''
 Implementación de la transformada Burrows-Wheeler mediante vectores de suffijos.

 La transformada BW permuta el orden de los símbolos de la cadena de entrada. 
 Si esta tiene muchas subcadenas recurrentes, la cadena transformada contendrá 
 multiples posiciones en las que un mismo símbolo esté repetido varias veces 
 en una fila
'''
# La entrada son una cadena de bytes y un vector de sufijos
# La salida es una cadena de bytes

# O(n) en el tamaño del vector de sufijos
def encodeBWT(cadena,array):
    BWT = bytes()
    for index in array:
        if (index == 0):
            BWT+=bytes([00])
        else:
            BWT+=bytes([cadena[index-1]])
    return BWT
    




'''
 Calculo de los rangos mediante B-ranking.

 En rangos se devuelve el numero de apariciones de cada elemento
 en la cadena de entrada.

 ejemplo:
 cadena = "abbaaa"

 Entonces rango devolverá: [0,0,1,1,2,3]

 La variable totales devuelve un diccionario que almacena los
 elementos de la cadena de entrada y su numero de apariciones
'''
# La entrada es una cadena de byte
# La salida son una cadena de enteros y un diccionario

# O(n) en la longitud de la cadena
def calcularRangos(cadena):
    totales = dict()
    rangos = []
    for char in cadena:
        # Si el símbolo actual no esta en el diccionario
        if bytes([char]) not in totales:
            # Se añade al diccionario con un total de 0 ocurrencias
            totales[bytes([char])] = 0  # Coste constante

        # Se añade a la lista de rangos el numero de apariciones
        # del símbolo actual (se añade antes de contabilizar
        # el numero de apariciones porque los rangos estan en base 0)
        rangos.append(totales[bytes([char])]) # Coste constante

        # Y acto seguido se actualiza su numero de apariciones
        totales[bytes([char])] += 1 # Coste constante

    # Se devuelve la lista de rangos y el diccionario
    # de los símbolos
    return rangos, totales


'''
 Se encarga de calcular la primera columna de la matriz BWT.

 Para calcular la primera columna, se usa la variable totales,
 que almacena en un diccionario los elementos que aparecen y 
 su numero de apariciones

 La primera fila de la matriz BWT almacena los símbolos en orden 
 alfabetico, por lo que si totales, en un símbolo X almacena que
 hay Y ocurrencias, se sabe que esas Y ocurrencias ocurren una
 detrás de otra

 ejemplo:
 totales={'a': 4, 'b': 2}

 entonces primeraCol devolverá {'a': 0, 'b': 4}

 donde el entero indica el indice de la primera aparicion del símbolo

'''
# La entrada es un diccionario
# La salida es una cadena de bytes

# O(nlogn) en la longitud de la cadena debido al uso de un algoritmo de ordenación
def primeraColumna(totales):
    # Se crea un diccionario vacio
    primeraCol = dict()
    # Y se el offset del indice a 0
    offset = 0
    for char, numApariciones in sorted(totales.items()): # coste nlogn
        # Se almacena en el símbolo char el indice de inicio
        primeraCol[char] = (offset) # Coste constante
        # Y se actualiza el offset sumandole el numero de apariciones de
        # este símbolo.
        offset+=numApariciones
    return primeraCol


'''
 Para calcular la inversa de una bwt, se necesitan la primera y ultima 
 columna de la matriz bwt, la primera columna se calcula en la funcion
 homónima, mientras que la ultima se pasa como parametro.

 El algoritmo LF-mapping obtiene la cadena original mediante los
 siguientes pasos:
    1.  Comenzar en el primer símbolo de la primera columna y 
        concatenar al resultado el símbolo del mismo indice 
        de la última columna
    2.  En base al rango del símbolo recien añadido a la solución
        se obtendrá la proxima fila de la primera columna que hay
        que comprobar.
    3.  Acceder al símbolo de la última columna que se encuentra 
        en la fila calculada en el paso anterior, concatenar este
        símbolo a la cadena de salida, repetir desde el paso 2 
        mientras que el proximo símbolo a concatenar sea distinto
        al símbolo nulo 
'''

# La entrada es una cadena de bytes
# La salida es una cadena de bytes

# O(nlogn) en la longitud de la cadena debido al uso de una funcion de coste O(nlogn)
def decodeBWT(cadena):
    # Calcula la cadena original dada una cadena BWT mediante LF-MAPPING
    rangos, totales = calcularRangos(cadena) # O(n)
    primeraCol = primeraColumna(totales) # O(nlogn)
    fila_i = 0
    t = bytes([00])
    while cadena[fila_i] != 00:
        # paso 1/3
        c = bytes([cadena[fila_i]])
        t = c + t
        # Paso 2
        fila_i = primeraCol[c] + rangos[fila_i]

    return t[:-1]
    
    