#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat Jan  4 18:23:24 2020

@author: victor
"""



def suffixArray(s,naive):
    if naive:
        return suffixArrayNaive(s)
    else:
        return suffixArraySA_IS(s)


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

# O(n²logn) puesto que el coste de comparación de cadenas es O(n) y 
# el coste de la ordenación es O(nlogn)
def suffixArrayNaive(bytestring):
    input=bytestring + bytes([00])
    # Genera un array con pares (sufijo, indice) y lo ordena en función del sufijo
    SA = sorted([ (input[i:], i) for i in range(0, len(input)) ])
    # Se devuelven unicamente los indices del array de pares ya ordenado, puesto que
    # con el array de indices y la cadena de entrada se pueden obtener todos los sufijos
    # ahorrando así espacio en memoria
    return list(map(lambda x:x[1], SA))
        

'''
 Implemetación del algortimo de creacion de vectores de sufijos SA-IS
 basada en la que se puede encontrar en la siguiente página web
 https://zork.net/~st/jottings/sais.html

 O(n)

 Coste temporal explicado en el paper que se puede encontrar en el siguiente
 enlace
 https://code.google.com/archive/p/ge-nong/downloads
'''

def suffixArraySA_IS(bytestring):
    return makeSuffixArrayByInducedSorting(bytestring, 256)

S_TYPE = ord("S")
L_TYPE = ord("L")

# Cálculo del vector de sufijos mediante el algoritmo SA-IS
def makeSuffixArrayByInducedSorting(string, alphabetSize = 256):

    # Se clasifica cada símbolo de la cadena de entrada como
    # S-type o como L-type
    typemap = buildTypeMap(string)

    # Los sufijos se van a clasificar en buckets dependiendo
    # del símbolo por el que empiezan, se va a precalcular
    # el tamaño de los buckets
    bucketSizes = findBucketSizes(string, alphabetSize)

    # Acto seguido se usa bucket-sort para insertar todos los
    # sufijos LMS en su zona correcta del vector de sufijos de
    # forma aproximada
    guessedSuffixArray = guessLMSSort(string, bucketSizes, typemap)

    # Ordenar el resto de sufijos mediante induced sorting
    induceSortL(string, guessedSuffixArray, bucketSizes, typemap)
    induceSortS(string, guessedSuffixArray, bucketSizes, typemap)

    # Se crea una nueva cadena que resume el orden relativo de los sufijos
    # LMS en el vector de sufijos aproximado
    summaryString, summaryAlphabetSize, summarySuffixOffsets = \
        summariseSuffixArray(string, guessedSuffixArray, typemap)

    # Calcular un vector de sufijos ordenado de la cadena anterior
    summarySuffixArray = makeSummarySuffixArray(
        summaryString,
        summaryAlphabetSize,
    )
    
    # Usando el vector de sufijos auxiliar, calcular exactamente
    # donde deben encontrarse los sufijos LMS en el vector a devolver
    result = accurateLMSSort(string, bucketSizes, typemap,
            summarySuffixArray, summarySuffixOffsets)

    # Reordenar los sufijos en su lugar final mediante induced sorting
    induceSortL(string, result, bucketSizes, typemap)
    induceSortS(string, result, bucketSizes, typemap)
    return result
    
    
    
    

# El algoritmo SA-IS divide los sufijos de la cadena en 2 tipos: S-type y L-type.
# Los sufijos de S-type son menores (en cuanto a ordenación) que el sufijo de su derecha
# Los sufijos de L-type son mayores (en cuanto a ordenación) que el sufijo de su derecha

#La clasificacion se realiza desde el final de la cadena hasta el principio.

# Reglas para clasificar los sufijos

# 1.   El sufijo vacio al final de la cadena es S-type por definición, por lo que
#      el penultimo sufijo (contiene unicamente el ultimo símbolo) es siempre L-type
#      (puesto que es mayor alfabeticamente que el vacio)

# 2.   Si el símbolo con offset X es alfabeticamente mayor que el símbolo con offset
#      X + 1, el sufijo con offset X es L-type

# 3.   Si el símbolo con offset X es alfabeticamente el mismo que el símbolo con offset
#      X + 1, y el sufijo con offset X + 1 es L-type, entonces el sufijo con offset X es
#      L-type

# 4.   En cualquier otro caso el sufijo con offset X es S-type.

# Algoritmo que se encarga de clasificar los sufijos en S-type y L-type
# Devuelve un vector de booleanos del mismo tamaño que la cadena, en el que
# vector[i] es cierto si data[i] es S-type y es falso en caso contrario 
def buildTypeMap(data):
    res = bytearray(len(data) + 1)

    # Regla 1
    res[-1] = S_TYPE
    if not len(data):
        return res
    res[-2] = L_TYPE
    # Se calcula el tipo del resto de sufijos
    for i in range(len(data)-2, -1, -1):
        # Regla 2
        if data[i] > data[i+1]:
           res[i] = L_TYPE
        # Regla 3
        elif data[i] == data[i+1] and res[i+1] == L_TYPE:
            res[i] = L_TYPE
        # Regla 4
        else:
            res[i] = S_TYPE
    return res


# Un símbolo de la cadena de entrada es un "S character" si un sufijo S-type
# comienza en la posición del símbolo en concreto (igual para los "L character")
# El símbolo S mas a la izquierda (LMS character o "LeftMostS charcter") es un
# símbolo S que tiene un símbolo L inmediatamente a su izquierda.

# Algoritmo que devuelve cierto si el caracter situado en index es LMS
def isLMSChar(offset, typemap):
    if offset == 0:
        return False
    if typemap[offset] == S_TYPE and typemap[offset - 1] == L_TYPE:
        return True
    return False


# LMS substrings o subcadenas LMS son una porcion de la cadena de entrada que
# comienza en un símbolo LMS y continua hasta (sin incluir) el siguiente símbolo
# LMS.

# Las subcadenas LMS son necesarias puesto que la eficiencia del algoritmo SA-IS
# se debe a la ordenación de estas subcadenas. La manera en la que estas subcadenas
# se comparan es distinta a la manera en la que se comparan cadenas normales, por lo que
# es necesario implementarlo

# Devuelve cierto si las dos subcadenas son iguales
def lmsSubstringsAreEqual(string, typemap, offsetA, offsetB):

    # Si cualquiera de las 2 cadenas de entrada es vacia
    if offsetA == len(string) or offsetB == len(string):
        return False
    i = 0
    while True:
        aIsLMS = isLMSChar(i + offsetA, typemap)
        bIsLMS = isLMSChar(i + offsetB, typemap)
        # Si se encuentra el inicio de la proxima subcadena LMS...
        if (i > 0 and aIsLMS and bIsLMS):
            # ... es porque se han recorrido nuestras subcadenas LMS
            # sin encontrar diferencia
            return True
        # Una subcadena ha acabado antes que la otra
        if aIsLMS != bIsLMS:
           return False
        # Se han encontrado símbolos distintos
        if string[i + offsetA] != string[i + offsetB]:
            return False
        i += 1
        
        
        
        
# Dada una cadena, se cuenta cuantos sufijos de la cadena comienzan
# con cada símbolo del alfabeto, o cuantos sufijos estan el en bucket
# de cada símbolo

# Esto es utilizado luego por el algoritmo de bucket sorting, que se
# encargara de ordenar todos los sufijos.     
def findBucketSizes(string, alphabetSize=256):
    res = [0] * alphabetSize
    for char in string:
        res[char] += 1
    return res

# Sabiendo el tamaño de cada bucket, se puede obtener un vector en el que
# el indice de cada símbolo apunta al inicio de su bucket correspondiente
# en el vector de suffijos
def findBucketHeads(bucketSizes):
    offset = 1
    res = []
    for size in bucketSizes:
        res.append(offset)
        offset += size
    return res

# Del mismo modo, tambien se necesitan los indices al final de cada bucket
def findBucketTails(bucketSizes):
    offset = 1
    res = []
    for size in bucketSizes:
        offset += size
        res.append(offset - 1)
    return res

# Se empieza a ordenar de manera aproximada el vector de sufijos
# mediante el uso de bucket sorting.

# Basicamente se recorrera la cadena de izquierda a derecha y se
# apilaran todos los sufijos LMS al final de su bucket
def guessLMSSort(string, bucketSizes, typemap):
    guessedSuffixArray = [-1] * (len(string) + 1)
    bucketTails = findBucketTails(bucketSizes)
    # Ordenación mediante bucket sort
    for i in range(len(string)):
        if not isLMSChar(i, typemap):
            # No es el comienzo de un sufijo LMS
            continue
        # Indice del bucket correspondiente al sufijo actual
        bucketIndex = string[i]
        # Se añade la posición de inicio al final del bucket
        guessedSuffixArray[bucketTails[bucketIndex]] = i
        # Se reduce en 1 su valor
        bucketTails[bucketIndex] -= 1
    guessedSuffixArray[0] = len(string)
    return guessedSuffixArray


# Funcion que se encarga de extrapolar la posición del resto de sufijos.
# Escanea nuestro vector de sufijos temporal y por cada sufijo inicializado,
# se comprueba el sufijo a su izquierda en la cadena original, si este es
# L-type, se oredenara este tambien.
def induceSortL(string, guessedSuffixArray, bucketSizes, typemap):
    bucketHeads = findBucketHeads(bucketSizes)
    # Para cada elemento del vector de sufijos
    for i in range(len(guessedSuffixArray)):
        if guessedSuffixArray[i] == -1:
            # Elemento no inicializado
            continue
        # Nos interesa el sufijo que comienza a la izquierda del
        # sufijo con indice i
        j = guessedSuffixArray[i] - 1
        if j < 0:
            # El elemento con indice i en el vector de sufijos es
            # el sufijo que comienza al inicio de la cadena con offset
            # 0. Esto implica que no hay sufijos a su izquierda
            continue
        if typemap[j] != L_TYPE:
            # Solo nos interesan los sufijos L-type
            continue
        # Ahora se va a obtener el bucket al que pertenece el sufijo
        # y a realizar su ordenación mediante bucket sorting
        bucketIndex = string[j]
        guessedSuffixArray[bucketHeads[bucketIndex]] = j
        bucketHeads[bucketIndex] += 1
        
# Función espejo de la fuFunciónncion anterior, es decir, en vez de recorrer
# el vector de sufijos de izquieda a derecha lo hace de derecha a izquierda
def induceSortS(string, guessedSuffixArray, bucketSizes, typemap):
    bucketTails = findBucketTails(bucketSizes)
    # Por cada elemento del vector de sufijos
    for i in range(len(guessedSuffixArray)-1, -1, -1):
        j = guessedSuffixArray[i] - 1
        if j < 0:
            # El elemento con indice i en el vector de sufijos
            # es el sufijo que comienza al inicio de la cadena,
            # con offset 0. Esto implica que no hay sufijos a su izquierda
            continue
        if typemap[j] != S_TYPE:
            # Solo nos interesan los sufijos S-type
            continue
        # Ahora se va a calcular el bucket al que pertenece el sufijo
        bucketIndex = string[j]
        guessedSuffixArray[bucketTails[bucketIndex]] = j
        bucketTails[bucketIndex] -= 1

# Crear una nueva cadena que resume el orden relativo de los
# sufijos LMS calculados aproximandamente en el vector de sufijos
def summariseSuffixArray(string, guessedSuffixArray, typemap):
    # Este vector se va a utilizar para almacenar los nombres de las
    # subcadenas LMS en las posiciones en las que aparecen en la
    # cadena original
    lmsNames = [-1] * (len(string) + 1)
    # Monitorizar que nombres se han almacenado
    currentName = 0
    # Posicion respecto de la cadena original del ultimo sufijo LMS
    # que se ha comprobado
    lastLMSSuffixOffset = None
    # Sabemos que la primera subcadena LMS que vamos a ver siempre será
    # aquella que representa el sufijo vacio, y siempre estara en la posicion
    # 0
    lmsNames[guessedSuffixArray[0]] = currentName
    lastLMSSuffixOffset = guessedSuffixArray[0]
    # Para cada sufijo en el vector de sufijos
    for i in range(1, len(guessedSuffixArray)):
        suffixOffset = guessedSuffixArray[i]
        if not isLMSChar(suffixOffset, typemap):
            # Solo nos interesan los sufijos LMS
            continue
        # Si es sufijo LMS y comienza con una subcadena
        # distinta a la del ultimo sufijo que hemos comprobado
        # se cambia su nombre
        if not lmsSubstringsAreEqual(string, typemap,
                lastLMSSuffixOffset, suffixOffset):
            currentName += 1
        lastLMSSuffixOffset = suffixOffset

        # Se almacena el nombre del sufijo LMS actual en nombresLMS
        # en el mismo lugar en el que este sufijo sucede ne la cadena
        # original
        lmsNames[suffixOffset] = currentName
    # nombresLMS almacena los caracteres de la cadena de sufijos en el
    # orden correcto, pero tambien amlacena muchos indices no utilizados
    # que no se van a utilizar, por lo que se van a eliminar. Tambien se
    # va a aprovechar para crear un sumario de offset de sufijos que
    # nos dira que sufijo LMS representa cada cadena del sumario
    summarySuffixOffsets = []
    summaryString = []
    for index, name in enumerate(lmsNames):
        if name == -1:
            continue
        summarySuffixOffsets.append(index)
        summaryString.append(name)
    # El caracter mas pequeño alfabeticamente en la cadena sumario
    # es 0, asi que el numero total de caracteres en este alfabeto
    # es uno mas que el caracter mayor
    summaryAlphabetSize = currentName + 1
    return summaryString, summaryAlphabetSize, summarySuffixOffsets


# Crea un vector de sufijos de la cadena resumen
def makeSummarySuffixArray(summaryString, summaryAlphabetSize):
    if summaryAlphabetSize == len(summaryString):
        # Cada símbolo de esta cadenaSumario aparece una unica vez, por
        # lo que se puede obtener el vector de sufijos con bucket-sort
        summarySuffixArray = [-1] * (len(summaryString) + 1)
        # Se añade el sufijo vacio
        summarySuffixArray[0] = len(summaryString)
        for x in range(len(summaryString)):
            y = summaryString[x]
            summarySuffixArray[y+1] = x
    else:
        # Si la cadena sumario es mas compleja, se usa recursió
        summarySuffixArray = makeSuffixArrayByInducedSorting(
            summaryString,
            summaryAlphabetSize,
        )
    return summarySuffixArray





# Ordena mediante bucket sorting el vector de sufijos final

# Basicamente se recorrera la cadena de izquierda a derecha y se
# apilaran todos los sufijos LMS al final de su bucket
def accurateLMSSort(string, bucketSizes, typemap,
        summarySuffixArray, summarySuffixOffsets):
    suffixOffsets = [-1] * (len(string) + 1)
    bucketTails = findBucketTails(bucketSizes)
    # Ordenación mediante bucket sort
    for i in range(len(summarySuffixArray)-1, 1, -1):
        stringIndex = summarySuffixOffsets[summarySuffixArray[i]]
        # Se obtiene el bucket al que pertenece el sufijo
        bucketIndex = string[stringIndex]
        # Se añade este sufijo al inicio del bucket
        suffixOffsets[bucketTails[bucketIndex]] = stringIndex
        bucketTails[bucketIndex] -= 1
    # Sufijo vacio al inicio del vector
    suffixOffsets[0] = len(string)
    return suffixOffsets


