Programación del Sinclair QL (XXVI): Arboles. Manejo de la memoria y sus pruebas

 

Índice de entradas sobre programación del Sinclair QL

---

El módulo que simula la memoria es reducido, crea unas variables de control, luego una variable de cadena en la que simularé el manejo de la memoria, la inicializa rellenándola con asteriscos, tiene una función para retornar un puntero a un espacio en la "memoria" del tamaño que le pasemos, otra para copiar una cadena a la "memoria" a partir de una posición, y una para presentar la "Memoria" en pantalla.

He rediseñado el sistema ocupando ahora cinco módulos:

• Arbol_Base: Se ocupa de cargar los módulos del programa y presentar un menú de las pruebas. 
• Arbol_Utilidades: Funciones comunes a todos los módulos
• Arbol_Nodos: Funciones de manejo de nodos
• Arbol_Nodos_Test: Para efectuar pruebas del manejo de nodos
• Arbol_Memoria: Funciones de manejo de la memoria
• Arbol_Memoria_Test: Pruebas de manejo de la memoria
  

Veamos las funciones para el manejo de la memoria:

• init_mem: inicializa la memoria con su tamaño mínimo
• init_mem_max(max): inicializa la memoria con un tamaño max, si este es menos del mínimo será el mínimo, definido en 300 bytes. Luego podemos usar las variables globales para ver en minMem el tamaño mínimo, y en maxMem el tamaño definido para la memoria.
• ver_mem: presenta la memoria en pantalla
• MemPos$(i): función auxiliar, la memoria comienza en posición cero, pero las cadenas en la posición 1, lo que hace es retornar el byte en la posición i+1
  
• GetBytes(bytes): Solicita un hueco de bytes tamaño, y retorna el puntero a donde comienza.
• SaveMem(base, ValorCadena$): Guarda una cadena en la memoria, a partir de una posición
• GetMem$(base,lon): Retorna el contenido de la memoria a partir de la posición indicada, en una cadena de longitud indicada.

7000 REMark *************************************************************
7010 REMark * Librería.: Arbol Binario                                  *
7020 REMark * Modulo...: Memoria                                        *
7030 REMark * Contenido: Rutinas de manejo de memoria                   *
7040 REMark * Autor....: javu61, septiembre 2024                        *
7050 REMark *************************************************************
7060 :
7070 REMark --- Inicializa la memoria con su tamaño mínimo por defecto
7080 :
7090 DEFine PROCedure init_mem
7100   init_mem_max(0)
7110 END DEFine
7120 :
7130 REMark --- Inicializa la memoria con el tamaño que le indicamos
7140 :
7150 DEFine PROCedure init_mem_max(max)
7160    LOCal i
7170   :
7180   minMem = 300
7190   maxMem=max
7200   IF (max < minMem) THEN maxMem=minMem
7210   NULL = -1 : REMark Puntero nulo
7220   ptrBase = 0 : REMark Puntero a la base de la memoria
7230   :
7240   REMark --- Crear la memoria e inicializarla
7250   :
7260   DIM Memoria$(maxMem)
7270   PRINT "Inicializando la memoria (";maxMem;" bytes) ";
7280   Memoria$=FILL$("*",maxMem)
7290   :
7300 END DEFine
7310 :
7320 REMark --- Presentar el contenido de la memoria en pantalla
7330 :
7340 DEFine PROCedure ver_mem
7350   LOCal i
7360   :
7370   PRINT " "; : FOR i=0 TO 4 : PRINT i;"/";i+5;" "; : END FOR i
7380   PRINT
7390   PRINT " "; : FOR i=0 TO 4 : PRINT "| "; : END FOR i
7400   PRINT
7410   PRINT " "; : FOR i=0 TO 4 : PRINT "0123456789"; : END FOR i
7420   :
7430   FOR i=0 TO maxMem-1
7440     IF (i=0) OR ((i MOD 50) = 0) THEN
7450       INK 7 : PRINT : PRINT n2c$(i,3);":"; : INK 4
7460     END IF
7470     PRINT MemPos$(i);
7480   END FOR i
7490   INK 7 : PRINT
7500 END DEFine
7510 :
7520 DEFine FuNction MemPos$(i)
7530   RETurn (Memoria$(i+1))
7540 END DEFine
7550 :
7560 REMark --- Solicita un hueco en memoria de x bytes
7570 :
7580 DEFine FuNction GetBytes(bytes)
7590   LOCal base
7600   :
7610   IF (ptrBase + bytes > maxMem) THEN
7620     PRINT "No hay sitio en la memoria"
7630     base = NULL
7640   ELSE
7650     base = ptrBase
7660     ptrBase = ptrBase + bytes
7670   END IF
7680   RETurn base
7690 END DEFine GetBytes
7700 :
7710 REMark --- Guarda una cadena en la memoria
7720 :
7730 DEFine PROCedure Save_Mem(base, ValorCadena$)
7740   LOCal i,p
7750   :
7760   FOR i=1 TO LEN(ValorCadena$)
7770     p=base+i
7780     IF (p < 1) OR (p > maxMem) THEN
7790       PRINT " *** Sobrepasa la memoria "
7800       EXIT i
7810     ELSE
7820       Memoria$(base+i)=ValorCadena$(i)
7830     END IF
7840   END FOR i
7850 END DEFine Save_Mem
7860 :
7870 : REMark --- Recupera una cadena desde la memoria
7880 :
7890 DEFine FuNction GetMem$(base,lon)
7900   LOCal c$,i,p
7910   :
7920   c$=""
7930   FOR i=1 TO lon
7940     p = base + i
7950     IF (p<0 or="" p="">maxMem) THEN
7960       PRINT " +++ Sobrepasa la memoria ";
7970       EXIT i
7980     ELSE
7990       c$=c$ & Memoria$(p)
8000     END IF
8010   END FOR i
8020   RETurn c$
8030 END DEFine GetMem
8040 :

Para ejecutar solo debéis cargar el módulo Arbol_Base y ejecutarlo, se encargará de cargar el resto de módulos y presentar el menú. Los módulos los podéis descargar de este enlace.

En este momento el sistema pasa los test, pero al final del segundo da un error que no tiene nada que ver, y no consigo localizar, a ver si alguno ve donde puede estar el problema.  

Programación del Sinclair QL (XXV): Arboles. Pruebas de los nodos

Índice de entradas sobre programación del Sinclair QL

---

Vamos con el programa para poder probar lo escrito en la entrada anterior. Es muy sencillo, genero en un bucle una cantidad aleatoria de nodos, cada uno con un valor que será una cadena de caracteres aleatorios entre "A" y "Z". Luego pruebo las rutinas de modificar los punteros a los hijos de los nodos, y la de cambiar el contenido del nodo.

Como las rutinas para montar los nodos están en otro fichero, tengo que cargarlo con un MERGE. En las entradas anteriores usaba un módulo base con los MERGE, y si se ejecutaba el módulo más de una vez volvía a ejecutarlos, con la pérdida de tiempo que eso genera.

La solución ha sido añadir un controlador de errores, si detecta que no se ha cargado el módulo hace el MERGE, si ve que se ha cargado no hace nada. De esta forma podemos ejecutarlo varias veces sin pérdidas de tiempo.

• WHEN ERRor: Es la rutina que se encarga de errores, para activarla se mira en la línea 260 el valor de una variable NODOS, si no existe dará un error -17
• Prepara el sistema: Prepara la pantalla y llama a la rutina del módulo de nodos para inicializarlo
• Crea módulos: Crea los nodos con información aleatoria
• Modifica módulo: Modifica un nodo para añadir puntero a los hijos y cambia el contenido.
• RndChr: Retorna un caracter aleatorio entre "A" y "Z"


100 REMark *************************************************************
110 REMark * Pruebas para el Manejo de nodos del arbol binario
120 REMark *************************************************************
130 :
140 REMark --- Control de si se ha incluido o no el módulo de nodos
150 :
160 WHEN ERRor
170   IF ERNUM=-17 THEN
180     PRINT "Cargando rutinas de nodos..."
190     MERGE mdv1_nodos
200     NODOS=1
201     RETRY
210   ELSE
220     PRINT "Se ha producido un error ";ERNUM;" en l“nea ";ERLIN
230     STOP
240   END IF
250 END WHEN
260 IF NODOS=0 THEN REMark --- Si da un error es que no ha cargado ---
270 :
280 REMark --- Preparar el sistema
290 :
300 MODE 0 : PAPER 0 : CLS
310 inicializa
320 :
330 REMark --- Generar nodos aleatorios para probar las rutinas
340 :
350 generar = RND(1 TO 10) : PRINT "Generando "& generar & " nodos"
360 FOR n=1 TO generar
370   c$=""
380   IF RND(1 TO 9) > 2 THEN
390     FOR i=0 TO RND(20)
400       c$ = c$ & RndChr$
410     NEXT i
420   END IF
430   n$ = NuevoNodo$(n,c$)
440   PRINT n$
450 NEXT n
460 :
470 PRINT "Finalizados los ";n;" nodos"
480 PRINT
490 PRINT "Cambiando datos de un nodo"
500 PRINT NuevoHijo$(n$,pIzq,56)
510 PRINT NuevoHijo$(n$,pDer,67)
520 PRINT NuevoValor$(n$,"Pruebas de valores")
530 :
540 REMark --- Retorna un caracter aleatório entre A y Z
550 :
560 DEFine FuNction RndChr$
570   RETurn CHR$(RND(CODE("A") TO CODE("Z")))
580 END DEFine aleatorio
590 :

 

El programa fuente lo podéis bajar de aquí.

En la siguiente entrada se añadirá el módulo memoria, añadiendo y eliminando nodos en la misma, por lo que luego mejoraré este programa para poder hacer pruebas de ambas partes, añadiendo un menú para definir cual se desea probar.

Para completar habría que hacer un proceso para compactar la memoria, pero eso requiere cambiar los punteros de los nodos, para lo que es necesario conocer su estructura interna, cosa que el sistema operativo no puede hacer, es responsabilidad de nuestro programa. En los lenguajes modernos con recolectores de basura, como Java o C# intentan hacer esto, con la ventaja de que no usan punteros a memoria, sino que las referencias son a la tabla de variables, con lo cual al cambiar la tabla ya ha cambiado todos los punteros, lo que es mucho mas sencillo que ir buscando en cada objeto a donde apunta y cambiarlo, pero a cambio usan mas memoria para la tabla de variables.

Programación del Sinclair QL (XXIV): Arboles. Estructura de los nodos en Super Basic

 

Índice de entradas sobre programación del Sinclair QL

---

Hemos visto el tema de las variables y el de los punteros, ahora vamos a hacer algo en Super Basic, pero ya que no es un lenguaje que soporte punteros ni se pueden usar variables compuestas de tipo registro, es un poco más complicado su manejo. Para manejar memoria hay que usar llamadas al Sistema Operativo para reservar memoria y código máquina para manejar los registros y punteros, o en el Toolkit II hay algunas funciones que nos lo facilitan. Como esto se sale de estas entradas que son de programación en SuperBasic, con la idea de que se pueda portar a otros Basic, voy a hacer otra cosas diferente para manejar árboles binarios, aunque no descarto luego hacer algo usando código máquina y llamadas al sistema.

Simularé la memoria usando una cadena de caracteres, usando el hecho de que una cadena tiene n caracteres, y podemos acceder a cualquiera de ellos individualmente, y cada carácter tiene un valor de 8 bits, lo que es muy similar a como se maneja una memoria. Desarrollaré funciones para reservar "memoria" dentro de la cadena, guardar datos en ella, leer cualquier dato usando un puntero a su dirección base, etc.

Nodos

Para crear los nodos del árbol, en entradas anteriores usé varios vectores de enteros, ya que los valores que manejamos lo eran. Ahora usaremos valores de tipo cadena de longitud variable, por lo que ya no nos sirve usar un vector, desperdiciamos demasiada memoria definiendo cadenas de longitud fija que pueden estar casi vacías. En su lugar en C se usaría un registro, que es una variable que se subdivide en varias, comportándose como un todo o como cada variable individual. Veamos como lo definiríamos en C:

struct nombre_registro    //El nombre que deseamos darle
{
     tipodato campo_1;    //Se define como cualquier variable, tipo y nombre
     tipodato campo_2;
     ....
     tipodato campo_N;    //Podemos usar todas las variables necesarias       
};


En el programa usaremos el nombre como el tipo de variable:

nombre_registro Variable_Registro;     //El nombre que deseamos darle a la variable

Y luego llamamos a los valores añadiendo un punto al nombre:

Variable_Registro.campo_n = ....
if (Variable_Registro.campo_n == true) {....


En los árboles binarios, necesitamos estos datos dentro para montar el registro:

• Nodo_Izquierdo: Puntero al sub-nodo izquierdo de este nodo.
• Nodo_Derecho: Puntero al sub-nodo derecho de este nodo.
• Nodo_Padre: Puntero al nodo padre de este nodo.Este dato no es estrictamente necesario, pero simplifica el montaje del árbol.
  
• Contenido del nodo: En nuestro caso es una cadena de caracteres, pero puede ser cualquier tipo, como un entero o un vector, o incluso otra estructura de tipo registro.
• Longitud del contenido: Al ser una cadena de longitud variable, necesitamos sabes su longitud para reservar solo la memoria necesaria.
  

Funciones para montar registros

Para montar un registro usaré una cadena de caracteres dividida en partes, los punteros serán valores numéricos entre 0 y 99, mientras que el contenido lo limitaremos a entre 0 y 99 caracteres. 

Para almacenar los números usaré cadenas de longitud fija, ajustadas a la izquierda con ceros por la derecha, así será sencillo ver su valor, realmente lo que se debe usar son bytes, con 1 byte podemos almacenar un número entero sin signo entre 0 y 255, con 2 bytes alcanzamos entre 0 y 65.535, esto pueden ser fácilmente dos caracteres, pero muchos no sería visibles ni nos informarían de los valores del puntero, por eso prefiero usar números almacenados en la cadena, aunque solo puedo almacenar entre 0 y 99 tengo la ventaja de que los puedo ver de forma sencilla, y este desarrollo intenta ser instructivo más que efectivo.

Nuestro nodos serán una cadena de caracteres con este formato <NN:NN:NN:NN:cadena> en donde:

• Inicio del nodo: Un carácter "<"
  
• Puntero al nodo padre: Dos caracteres numéricos. No es necesario pero simplifica la navegación por el árbol.
• Separador: Un carácter ":"
  
• Puntero al nodo hijo izquierdo: Dos caracteres numéricos.
• Separador: Un carácter ":"
  
• Puntero al nodo hijo derecho: Dos caracteres numéricos.
• Separador: Un carácter ":"
  
• Longitud del contenido: Dos caracteres numéricos.
• Separador: Un carácter ":"
  
• Contenido: Una cadena de entre 0 y 99 caracteres
• Fin del registro: Un carácter ">"

Los caracteres de inicio y fin no son necesarios, así como los separadores tampoco lo son, pero los usaré para poder ver los nodos de manera sencilla, y rellenaré la "memoria" con asteriscos, de forma que se vean los huecos libres, y cuando queramos ver la "memoria" lo podemos hacer simplemente imprimiendo la cadena, y veremos un texto de la forma:

<00:01:23:04:HOLA>******************<19:40:00:05;ADIOS><04:25_09:00:>********....

Así creo que es mas sencillo presentar los valores de forma que se vean correctamente, sin necesidad de grandes procesos.

Empecemos por las funciones que montan los nodos, para lo que defino funciones y procedimientos para manejarlas:

• inicializa: Este procedimiento inicializa las variables que usaremos, en donde:
• mLon: Longitud de las cadenas para guardar los punteros
• mNodos: Máximo número de nodos que manejamos
• nIni, nSep, nFin: inicio, separador y final para montar el nodo
• pPadre, pIzq, pDer, pLon, pVal: Orden de los campos para el nodo
  
• n2c$(n,l): Esta función retorna una cadena cuyo contenido es un valor numérico (n), ajustada a una longitud máxima (l) y rellena con ceros por la izquierda. Si le pasamos por ejemplo (17,3) nos retorna "017"

• MontarNodo$(p,i,d,c$): Función que retorna un nodo montado con los valores para el padre (p), hijo izquierdao (i), hijo derecho (d) y una cadena de caracteres (c$), si le pasamos por ejemplo (2,12,3,"Hola") nos retorna "<02:12:03:04:Hola>"

• NuevoNodo$(p,c$): Función que retorna un nuevo nodo sin hijos, con los valores para el padre (p) y una cadena de caracteres (c$), si le pasamos por ejemplo (2,"Hola") nos retorna "<02:00:00:04:Hola>"
• Posicion(pos): Retorna un número que indica donde comienza en la cadena que representa el nodo uno de los valores del nodo (pos con valores para 0=padre, 1=izquierdo, 2=derecho, 3=longitud del contenido, 4=valor del contenido), si le pasamos por ejemplo (pIzq) nos retorna 5
• NuevoHijo$(nodo$, pos, valor): Retorna una cadena que representa un nodo (nodo$), en la que cambia el puntero para uno de los hijos (pos donde 1=izquierdo o 2=derecho), con su nuevo valor de puntero (valor), si le pasamos por ejemplo ("<02:00:00:04:Hola>", pIzq,2) nos retorna "<02:02:00:04:Hola>"
• NuevoValor$(nodo$, NuevoValor$): Retorna una cadena que representa un nodo (nodo$), en la que cambia el valor del contenido (NuevoValor$), si le pasamos por ejemplo ("<02:02:00:04:Hola>", "Adios") nos retorna "<02:02:00:05:Adios>"

5000 REMark *************************************************************
5010 REMark * Librería.: Arbol Binario                                  *
5020 REMark * Programa.: Nodos                                          *
5030 REMark * Contenido: Rutinas de manejo de los nodos                 *
5040 REMark * Autor....: javu61, octubre 2024                           *
5050 REMark *************************************************************
5060 :
5070 REMark --- Inicializar el sistema
5080 :
5090 DEFine PROCedure inicializa
5100   mLon=2
5110   mNodos = 10^mLon - 1
5120   nIni$="<" : nSep$=":" : nFin$=">"
5130   pPadre=0 : pIzq=1 : pDer = 2 : pLon=3 : pVal=4
5140 END DEFine inicializa
5150 :
5160 REMark --- Numero en cadena ajustado a longitud
5170 :
5180 DEFine FuNction n2c$(n,l)
5190   LOCal c$
5200   c$=n
5210   REPeat bucle_n2c
5220     IF LEN(c$)>=l THEN EXIT bucle_n2c
5230     c$ = "0" & c$
5240   END REPeat bucle_n2c
5250   c$= c$(1 TO l)
5260   RETurn c$
5270 END DEFine n2c$
5280 :
5290 REMark --- Montar un nodo
5300 :
5310 DEFine FuNction MontarNodo$(p,i,d,c$)
5320   LOCal n$
5330   n$ = nIni$
5340   n$ = n$ & n2c$(p,mLon) & nSep$
5350   n$ = n$ & n2c$(i,mLon) & nSep$
5360   n$ = n$ & n2c$(d,mLon) & nSep$
5370   n$ = n$ & n2c$(LEN(c$),mLon) & nSep$ & c$
5380   n$ = n$ & nFin$
5390   RETurn n$
5400 END DEFine MontarNodo
5410 :
5420 REMark --- Montar un nodo nuevo sin hijos
5430 :
5440 DEFine FuNction NuevoNodo$(p,c$)
5450   RETurn MontarNodo$(p, 0, 0, c$)
5460 END DEFine NuevoNodo
5470 :
5480 REMark --- Retorna la posición de un elemento en el nodo
5490 :
5500 DEFine FuNction Posicion(pos)
5510   RETurn LEN(nIni$) + (pos * mLon) + (pos * LEN(nSep$)) + 1
5520 END DEFine Posicion
5530 :
5540 REMark --- Añadir un hijo a un nodo
5550 :
5560 DEFine FuNction NuevoHijo$(nodo$, pos, valor)
5570   LOCal p
5580   p = Posicion(pos)
5590   nodo$(p TO p+mLon-1)= n2c$(valor, mLon)
5600   RETurn nodo$
5610 END DEFine NuevoHijo$
5620 :
5630 REMark --- Cambiar el valor de un nodo
5640 :
5650 DEFine FuNction NuevoValor$(nodo$, NuevoValor$)
5660   LOCal p1,p2
5670   p1 = Posicion(pLon)
5680   p2 = Posicion(pVal)
5690   nodo$ = nodo$(1 TO p1-1)
5700   nodo$ = nodo$& n2c$(LEN(NuevoValor$), mLon) & nSep$
5710   nodo$ = nodo$ & NuevoValor$ & nFin$
5720   RETurn nodo$
5730 END DEFine NuevoValor$

 

En la siguiente entrada añadiré un programa para probar que estas funciones trabajen correctamente, y si queréis descargar este fichero lo tenéis aquí.