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 RAA13115; Tue, 8 Apr 2003 17:03:48 +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 RAA13107 for ; Tue, 8 Apr 2003 17:03:46 +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 h38F3j923572 for ; Tue, 8 Apr 2003 17:03:45 +0200 (MET DST) Received: from epmailtmp.qlogic.org ([10.20.33.254]) by epexch01.qlogic.org with Microsoft SMTPSVC(5.0.2195.5329); Tue, 8 Apr 2003 10:03:58 -0500 Received: from [10.20.33.146] ([10.20.33.146]) by epmailtmp.qlogic.org with Microsoft SMTPSVC(5.0.2195.4905); Tue, 8 Apr 2003 10:03:57 -0500 Date: Tue, 8 Apr 2003 10:07:16 -0500 (CDT) From: Brian Hurt X-X-Sender: Reply-To: Brian Hurt To: Wheeler Ruml cc: John Gerard Malecki , Subject: Re: [Caml-list] Re: Wanted - General Purpose "Glue Logic" Data-Structures In-Reply-To: <16018.7894.703716.797621@katsura.parc.xerox.com> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-OriginalArrivalTime: 08 Apr 2003 15:03:57.0713 (UTC) FILETIME=[146F3810:01C2FDE0] X-Spam: no; 0.00; qlogic:01 caml-list:01 glue:01 wheeler:01 red-black:01 gc'ed:01 dummy:01 null:01 tree:02 arbitrary:02 objects:02 wrote:03 usefull:03 trick:03 array:04 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Mon, 7 Apr 2003, Wheeler Ruml wrote: > I saw Brian's recommendation of a priority queue, but wanted to > mention that a resizable array would do here as well. Eg, something > like It actually sounds like a simple tree is what he needs. The problem with a resizeable array is that removing anything except the last element is O(n)- remember that you have to copy all the higher elements down. He specified fast deletion of arbitrary elements. > Brian's > queue may well do this underneath, Actually, my PSQueue is built ontop of a red-black tree. And it's mainly usefull when you need both the behaviors of a priority queue and a search tree. Otherwise it is a little heavy/ > but there's no reason to suffer > O(log n) insertion and removal time if you don't really care about the > order. Just add to the end and swap with a random element in constant > time. Or remove from a random place and copy in the last element. > The only tricky thing is to be careful to fill any "empty" cells in > the array with the same dummy value (which needs to be supplied at > creation time) so you don't prevent objects from being GC'ed. This was the problem I ran into trying to do an arbitrary resizeable array- I ended up doing a Some of/None trick to handle empty array elements. Which, of course, added a whole second layer of references. Although requiring the user to supply a null item isn't as bad as I first thought- it's the same thing that Array.make does... Brian ------------------- 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