LUA / Queue y doble queue

Bienvenidos sean a este post, hoy hablaremos sobre queues en Lua y una manera facil de implementarlas con insert y remove (de la libreria table), estas funciones insertan y remueven elementos en cualquier posicion de un array y moviendo otros elementos para acomodar la operacion sin embargo estos movimientos pueden ser pesados para grandes estructuras, una implementacion mas eficiente usa dos indices, una para el primer elemento y otra para el ultimo elemento:

function ListaNueva()
	return { primero = 0, ultimo = -1 }
end

Para evitar contaminar el espacio global definiremos todas las operaciones de la lista dentro de una tabla, llamada apropiadamente Lista (estan en lo correcto crearemos un modulo), ademas reescribiremos nuestro ultimo ejemplo de la siguiente forma:

Lista = {}
function Lista.nueva()
	return { primero = 0, ultimo = -1 }
end

Ahora si podemos insertar o remover los elementos en ambos extremos en tiempo constante:

function Lista.empujaPrimero(lista, valor)
	local primero = lista.primero - 1
	lista.primero = primero
	lista[primero] = valor
end

function Lista.empujaUltimo(lista, valor)
	local ultimo = lista.ultimo + 1
	lista.ultimo = ultimo
	lista[ultimo] = valor
end

function Lista.surgePrimero(lista)
	local primero = lista.primero
	if primero > lista.ultimo then error("Lista vacia") end
	local valor = lista[primero]
	lista[primero] = nil
	lista[primero] = primero + 1
	return valor
end

function Lista.surgeUltimo(lista)
	local ultimo = lista.ultimo
	if lista.primero > ultimo then error("Lista vacia") end
	local valor = lista[ultimo]
	lista[ultimo] = nil
	lista.ultimo = ultimo - 1
	return valor
end

Las dos primeras funciones se encargaran de empujar el primer y el ultimo elemento de la queue, en ambos casos recibiran a la lista (el queue a modificar) y el valor a insertar, en el caso de primero crearemos una variable llamada primero donde obtendremos el valor de lista y le restaremos 1, luego lo enviaremos a reemplazar el valor de lista y por ultimo lo usaremos como indice para insertarle el nuevo dato almacenado en valor, en el caso de ultimo lo unico que se modifica es la variable local llamada ultimo y le asignamos el valor de ultimo en la lista pasada como argumento y le sumamos 1, despues es exactamente lo mismo pero con el indice de ultimo, en las siguientes dos funciones ocurre casi lo mismo, porque las funciones son parecidas, para ambos le enviamos la lista, en el caso de primero crearemos una variable llamada primero y le asignaremos el valor de primero en la lista, despues el condicional chequeara si primero es mayor que el de ultimo en la lista en caso de ser cierto nos envia una notificacion de error, en caso de seguir crearemos una variable llamada valor donde le asignaremos el dato almacenado en la lista con el indice primero, luego le asignaremos a este indice el valor de nil, esto es para permitir la coleccion de basura (un tema que hablaremos mas adelante), al valor de primero en lista le sumamos 1 y se lo asignamos, por ultimo retornamos el dato asignado a valor, la otra funcion trabaja exactamente de la misma forma pero con el valor de ultimo, el condicional lo unico que cambia es que primero usa el primero de lista con el valor de ultimo almacenado, despues trabaja de la misma con valor y lo devuelve, si usamos esta estructura en una disciplina de queue estricta llamando empujaUltima y surgePrimero tanto primero y ultimo se incrementaran continuamente sin embargo porque representamos arrays con tablas en Lua puedes indexarlos ya sea desde 1 a 20 o desde 16777216 a 16777236 porque Lua usa doble precision para representar numeros, asi que tu programa puede correr por doscientos años haciendo un millon de ingresos por segundo antes de tener problemas con desbordamiento (overflows).

Nota: Esto ultimo lo dice el creador del lenguaje no este blog. 🙄

En resumen, hoy hemos visto como utilizar queues y doble queues, como se implementan, como son y para que sirven, espero les haya sido util sigueme en Twitter o Facebook para recibir una notificacion cada vez que subo un nuevo post en este blog, nos vemos en el proximo post.