[prev in list] [next in list] [prev in thread] [next in thread] 

List:       koffice-devel
Subject:    Re: KSpread - algorithm for fast and memory-saving storage
From:       Holger =?iso-8859-1?q?Schr=F6der?= <holger-kde () holgis ! net>
Date:       2003-04-24 16:40:18
[Download RAW message or body]

Hi,

On Wednesday 23 April 2003 10:21, Pascal A. Niklaus wrote:
> Hi,
>
> I had a browse through KSpread's source tree and found the notice on the
> discussion on how to store formatting information so that it doesn't
> consume much memory and access is still fast.
>
> After some thinking I came up with an algorithm to store the formatting
> information so that it can be accessed very quickly, but doesn't have to
> be stored in the cell (not even a pointer). The concept is to store
> formatting in a list/array of rectangular regions with a specific
> formatting, and to use a quaternary tree structure to find in which
> region a specific cell lies. Even for large worksheets, the specified
> format can be found with a very small number of integer comparisions,
> (1) because maximum tree height increases only with log(size) and (2)
> because the tree is extremely short for regions without complex formatting.
>
> 1) Store the formatting information as a list or array of rectangular
> regions. This is the only info which needs to be saved to the file.
>
here it is important, that you donīt introduce a new file format, and as it is 
now, iirc, every cell or area of cells saves the name of the style or so, so 
you have to be prepared to transform the styles data from your new internal 
representation to the already defined file format at saving, and to generate 
the internal rep. from the xml data on loading. i donīt know if you already 
did this, so if not, try this to get an idea of the xml file format of 
kspread:

create a kspread document with some different styles for some different cells, 
and save it to a file. then open the file in konqueror, it will be opened by 
kspread automatically, but when you replace file:// by zip:// in the Location 
field, it will be opened in konqueror and you have access to the files 
contained therein. you can also rename the *.ksp file to *.zip, and it will 
work automatically.

now you can open the maindox.xml with an editor and look at it. whatever you 
do has to be backward compatible with this file format. it is a good idea to 
improve the "in-RAM"-representation of the formatting attributes, but on disk 
all files are zipped xml files and when you have the same 
<format.....
	.......
</format>
entry some hundred times, it does not need one hundred times the space of one 
entry, but (wild guess) five times as much.


i really like your idea, but please keep this in mind. when you have still 
some time left, consider looking at the openoffice xml file format and how 
they are handling styles, as kspread could switch to their xml file format, 
if somebody does the work somewhen, and so it would be good, when you already 
have a look at that to not create problems now, which would have to be 
overcome in the future.

hope this helps, Holger
_______________________________________________
koffice-devel mailing list
koffice-devel@mail.kde.org
http://mail.kde.org/mailman/listinfo/koffice-devel

[prev in list] [next in list] [prev in thread] [next in thread]