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 (18:08) From: Brian Hurt Subject: Re: [Caml-list] Re: Wanted - General Purpose "Glue Logic" Data-Structures
```
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

```