From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id KAA10551; Thu, 10 Apr 2003 10:23:49 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id KAA10563 for ; Thu, 10 Apr 2003 10:23:47 +0200 (MET DST) Received: from lri.lri.fr (lri.lri.fr [129.175.15.1]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h3A8Nk929332 for ; Thu, 10 Apr 2003 10:23:46 +0200 (MET DST) Received: from pc8-123 (mail@pc8-123 [129.175.8.123]) by lri.lri.fr (8.11.6p2/jtpda-5.3.2) with ESMTP id h3A8CQr28270 ; Thu, 10 Apr 2003 10:12:26 +0200 (MEST) Received: from filliatr by pc8-123 with local (Exim 3.35 #1 (Debian)) id 193XAY-0000El-00; Thu, 10 Apr 2003 10:12:26 +0200 From: Jean-Christophe Filliatre MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <16021.10090.355061.746312@gargle.gargle.HOWL> Date: Thu, 10 Apr 2003 10:12:26 +0200 To: Brian Hurt Cc: "Yaron M. Minsky" , Caml List Subject: Re: [Caml-list] Re: Wanted - General Purpose "Glue Logic" Data-Structures In-Reply-To: References: <16019.49880.45938.429789@gargle.gargle.HOWL> X-Mailer: VM 7.03 under Emacs 20.7.2 Reply-To: Jean-Christophe.Filliatre@lri.fr (Jean-Christophe Filliatre) X-MailScanner: Found to be clean X-Spam: no; 0.00; filliatre:01 lri:01 caml-list:01 glue:01 deallocate:01 decreased:99 allocating:01 yaron:01 minsky:01 abstractions:01 argues:01 vectors:01 val:01 resizing:01 arrays:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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