Accueil     À propos     Téléchargement     Ressources     Contactez-nous

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

[Caml-list] Wanted - General Purpose "Glue Logic" Data-Structures
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2003-04-09 (06:53) From: Jean-Christophe Filliatre Subject: Re: [Caml-list] Re: Wanted - General Purpose "Glue Logic" Data-Structures
```
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:

======================================================================
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,
--
Jean-Christophe Filliâtre (http://www.lri.fr/~filliatr)

-------------------
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

```