Re: [Ocaml-lib-devel] Xarray : resizeable arrays (first cut)

[Brian H. <bri...@ql...>]

On Sun, 27 Apr 2003, John Max Skaller wrote:

> Brian Hurt wrote:
> 
> > Certainly not difficult.  I just don't 
> > see what you get out of it.  
> 
> 
> Suppose you have a rule: when you're increasing the number
> of elements in the array, you can resize it, but never
> when you're decreasing them. That might be useful,
> but it cannot be implemented unless you know the number
> of elements in the array -- i don't mean slots of store
> but actual occupied slots.
> 
> For example: the number of slots is set to the number
> of elements on expansion. So for example adding 1 element
> at a time to 5 then subtracting, then adding again:
> 
> data slots
> 0     0
> 1     1
> 2     2
> 3     3
> 4     4
> 5     5
> 4     5
> 3     5
> 2     5
> 1     5
> 0     5
> 1     1
> 2     2
> 3     3
> 4     4
> 5     5

Ah!  Only reallocate when you start adding elements back in, but then 
shrink to a correct size.  You'd have to save state that you had shrunk, 
but that's not hard.

OK.  Yes, for that you need to know if you're adding or removing slots.

I was thinking you meant something like:
data	slots
0	0
1	1
2	2
3	3
2	3
1	3
0	0 <- shrink happened
1	1
2	2
...

etc.  You have the shrink happening on the first insert.

And that's actually not *that* strange of a resizing algorithm, especially 
if you know that deletes are "bursty".  It saves copying, and may even 
save short-term memory usage (if the GC wouldn't get around to collecting 
the old array soon enough).

> NOte that one could argue that passing
> in the size of a slot (in bytes) also makes
> sense, since a strategy may be based on tuning
> around memory amounts (Kbytes) due to the finiteness
> of this quantity, rather than the more abstract notion
> of a slot.

Especially in that I (the xarray module) don't know how large an 'a is.  
Most likely it's just a reference off somewhere to some other type.  Which 
is one of the reasons adding a user-defined resizer function is usefull.  
If you do know (or at least can guess) how big of data structures you're 
kicking around, write a specific resizer for it.  Or have a 
parameterizable resizing function, like I did with the step function.

Does anyone mind if I use named parameters for the resizer?  Use the type 
(for example):
resizer: numslots:int -> oldlength:int -> newlength:int -> int
?

Make it more obvious what the various arguments are.

Brian