InfiniteArray.ml 1.92 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13
(******************************************************************************)
(*                                                                            *)
(*                                   Menhir                                   *)
(*                                                                            *)
(*                       François Pottier, Inria Paris                        *)
(*              Yann Régis-Gianas, PPS, Université Paris Diderot              *)
(*                                                                            *)
(*  Copyright Inria. All rights reserved. This file is distributed under the  *)
(*  terms of the GNU Library General Public License version 2, with a         *)
(*  special exception on linking, as described in the file LICENSE.           *)
(*                                                                            *)
(******************************************************************************)

14 15 16 17 18 19 20
(** This module implements infinite arrays, that is, arrays that grow
    transparently upon demand. *)

type 'a t = {
    default: 'a;
    mutable table: 'a array;
    mutable extent: int; (* the index of the greatest [set] ever, plus one *)
21
  }
22 23 24 25 26 27 28 29

let default_size =
  16384 (* must be non-zero *)

let make x = {
  default = x;
  table = Array.make default_size x;
  extent = 0;
30
}
31 32 33 34 35 36 37 38

let rec new_length length i =
  if i < length then
    length
  else
    new_length (2 * length) i

let ensure a i =
39
  assert (0 <= i);
40 41 42 43 44 45 46 47 48 49
  let table = a.table in
  let length = Array.length table in
  if i >= length then begin
    let table' = Array.make (new_length (2 * length) i) a.default in
    Array.blit table 0 table' 0 length;
    a.table <- table'
  end

let get a i =
  ensure a i;
50
  Array.unsafe_get a.table (i)
51 52 53

let set a i x =
  ensure a i;
54
  Array.unsafe_set a.table (i) x;
55 56
  if a.extent <= i then
    a.extent <- i + 1
57 58 59 60 61 62 63

let extent a =
  a.extent

let domain a =
  Array.sub a.table 0 a.extent