[C con Clase] SPREADSHEET en la Memoria

[Steven Davidson]

Hola Diego,

Diego wrote:
> Hola,

[CORTE]

> He estado investigando un programa de codigo abierto llamado
> gnumeric, para linux, y este tiene un Hashtable donde guarda todos
> las celdas, como lo haria un diccionario.  Me han dicho que este
> programa tambien usa regiones y arreglos segmentados para hacer las
> operaciones mas eficientemente, pero no conozco los arreglos
> segmentados ni entiendo como puede funcionar un hash con regiones.
> 

Sospecho que array segmentado es "sparse array" en inglés. Básicamente, 
es un array que no tiene que contener todos los elementos, ya que no 
serán rellenados completamente. Por ejemplo, para implementar la hoja de 
cálculo que quieres hacer, podríamos crear un array bidimensional de 
3000 x 3000; o sea,

Celda tabla[3000][3000];

Sin embargo, lo más seguro es que la mayoría de las celdas estará vacía. 
Por lo tanto, en lugar de crear todas las celdas, simplemente creamos 
las celdas que queremos llenar, suponiendo que las demás están vacías, 
que es el estado por defecto. Esto se puede implementar con listas 
dinámicamente enlazadas.

> Ademas algunos miembros de la comunidad gnumeric me han dicho que
> estan trabajando para usar un quadtree, o un arbol de 4 ramas para
> dividir las celdas en regiones, pero tambien me es confuso.  Por
> favor ayudenme.  No estoy interesado en usar OLE o Active X, ya que
> necesito yo mismo hacer las grillas, y no depender de Excel.
> 

Un árbol cuaternario ciertamente se compone de nodos de 4 ramas. Su uso 
típico es para solucionar los problemas espaciales del tema de gráficos 
para implementar un modelado de la información (vértices, aristas, 
caras, etc.).

La idea básica es que partimos de un área rectangular que contiene todos 
los elementos de la información. Subdividimos este rectángulo en cuatro 
cuadrantes, obviamente rectangulares. Seguimos subdividiendo cada 
cuadrante en otros cuatro cuadrantes hasta que obtenemos rectángulos que 
tienen una cantidad de elementos más manejable. Las hojas del árbol 
contienen la información. Sería algo así,

       raíz(0,0,3000,3000)
       /    /       \   \
      /     |       |    \
nodo11  nodo12  nodo13  nodo14
/ | | \ / | | \ / | | \ / | | \

nodo11 : (0,0,1500,1500)
nodo12 : (1500,0,3000,0)
nodo13 : (1500,0,1500,3000)
nodo14 : (1500,1500,3000,3000)

Cada nodo representa un área rectangular que contiene todos los 
elementos en tal rectángulo. Cada rama representa otro rectángulo menor 
que contiene un subconjunto de los elementos de su nodo pariente.

Puedes observar, que con unos cuantos recorridos del árbol llegamos a la 
información que nos interesa.


Espero que esto aclare algunas dudas.

Steven