Re: [Caml-list] Re: Wanted - General Purpose "Glue Logic" Data-Structures

[Brian Hurt <brian.hurt@qlogic.com>]

This doesn't work, or at least doesn't work well.  What happens when you 
delete the value being used as the null value?  You have to go through and 
reset all the null values to the new null value.  Also, you want to keep 
reallocations to a minimum.  If you hit the point where you keep adding 
and deleting the last element, you have to keep allocating and 
deallocating the array block.

Brian


On Wed, 9 Apr 2003, Jean-Christophe Filliatre wrote:

> 
> Yaron M. Minsky writes:
>  > Resizeable arrays seem like a
>  > pretty essential data structure, and the fact that you can't implement
>  > them nicely without breaking the standard compiler abstractions (due to
>  > the dummy value issue) argues in favor of including it in the
>  > distribution, I would think.
> 
> There is an easy trick for this dummy value issue.
> 
> What you want is an interface looking like:
> 
> ======================================================================
> type 'a t                    (* resizeable vectors *)
> val create : int -> 'a t     (* only initial capacity is given *)
> val add : 'a t -> 'a -> unit 
> ...
> ======================================================================
> 
> The idea is  to initially store the capacity as  a negative size, thus
> remembering that the data array still needs initialization:
> 
> ======================================================================
> type 'a t = { mutable size : int; mutable data : 'a array }
> 
> let create n = 
>   if n <= 0 then invalid_arg "create";
>   { size = -n; data = [||] }
> ======================================================================
> 
> Note that being empty is having a size less or equal than zero:
> 
> ======================================================================
> let is_empty v = v.size <= 0
> ======================================================================
> 
> Then the first time an addition is performed, you allocate the array:
> 
> ======================================================================
> let add v x =
>   if v.size < 0 then begin  (* first addition: we allocate the array *)
>     v.data <- Array.create (- v.size) x; v.size <- 0
>   end;
>   (* code to insert x, resizing data if needed *)
>   ...
> ======================================================================
> 
> Hope this helps,
> 

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners