menhirlib/infiniteArray.ml

   1 (**************************************************************************)
   2 (*                                                                        *)
   3 (*  Menhir                                                                *)
   4 (*                                                                        *)
   5 (*  François Pottier, INRIA Rocquencourt                                  *)
   6 (*  Yann Régis-Gianas, PPS, Université Paris Diderot                      *)
   7 (*                                                                        *)
   8 (*  Copyright 2005-2008 Institut National de Recherche en Informatique    *)
   9 (*  et en Automatique. All rights reserved. This file is distributed      *)
  10 (*  under the terms of the GNU Library General Public License, with the   *)
  11 (*  special exception on linking described in file LICENSE.               *)
  12 (*                                                                        *)
  13 (**************************************************************************)
  14
  15 (* $Id: infiniteArray.ml,v 1.2 2010/01/28 14:23:47 npalix Exp $ *)
  16
  17 (** This module implements infinite arrays, that is, arrays that grow
  18     transparently upon demand. *)
  19
  20 type 'a t = {
  21     default: 'a;
  22     mutable table: 'a array;
  23     mutable extent: int; (* the index of the greatest [set] ever, plus one *)
  24   }
  25
  26 let default_size =
  27   16384 (* must be non-zero *)
  28
  29 let make x = {
  30   default = x;
  31   table = Array.make default_size x;
  32   extent = 0;
  33 }
  34
  35 let rec new_length length i =
  36   if i < length then
  37     length
  38   else
  39     new_length (2 * length) i
  40
  41 let ensure a i =
  42   let table = a.table in
  43   let length = Array.length table in
  44   if i >= length then begin
  45     let table' = Array.make (new_length (2 * length) i) a.default in
  46     Array.blit table 0 table' 0 length;
  47     a.table <- table'
  48   end
  49
  50 let get a i =
  51   ensure a i;
  52   a.table.(i)
  53
  54 let set a i x =
  55   ensure a i;
  56   a.table.(i) <- x;
  57   a.extent <- max (i + 1) a.extent
  58
  59 let extent a =
  60   a.extent
  61
  62 let domain a =
  63   Array.sub a.table 0 a.extent
  64