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 UAA27067; Wed, 9 Apr 2003 20:08:55 +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 UAA27116 for ; Wed, 9 Apr 2003 20:08:52 +0200 (MET DST) Received: from epexch01.qlogic.org ([63.170.40.3]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h39I8o910601 for ; Wed, 9 Apr 2003 20:08:51 +0200 (MET DST) Received: from epmailtmp.qlogic.org ([10.20.33.254]) by epexch01.qlogic.org with Microsoft SMTPSVC(5.0.2195.5329); Wed, 9 Apr 2003 13:09:00 -0500 Received: from [10.20.33.146] ([10.20.33.146]) by epmailtmp.qlogic.org with Microsoft SMTPSVC(5.0.2195.4905); Wed, 9 Apr 2003 13:09:00 -0500 Date: Wed, 9 Apr 2003 13:12:38 -0500 (CDT) From: Brian Hurt X-X-Sender: Reply-To: Brian Hurt To: Jean-Christophe Filliatre cc: "Yaron M. Minsky" , Caml List Subject: Re: [Caml-list] Re: Wanted - General Purpose "Glue Logic" Data-Structures In-Reply-To: <16019.49880.45938.429789@gargle.gargle.HOWL> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-OriginalArrivalTime: 09 Apr 2003 18:09:00.0383 (UTC) FILETIME=[188DF6F0:01C2FEC3] X-Spam: no; 0.00; qlogic:01 caml-list:01 glue:01 allocating:01 filliatre:01 yaron:01 minsky:01 abstractions:01 argues:01 vectors:01 val:01 resizing:01 arrays:01 compiler:01 dummy:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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