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

[Jean-Christophe Filliatre <Jean-Christophe.Filliatre@lri.fr>]

In the solution I proposed, you do not deallocate the array block when
you delete the last element; only the size is decreased.

Actually, I didn't use this  trick to implement resizeable arrays, but
to implement heaps encoded in (resizeable) arrays---available from the
hump; but I think the same idea applies.

-- 
Jean-Christophe

Brian Hurt writes:
 > 
 > 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