(**************************************************************************)
(*                                                                        *)
(*  Copyright (C) Jean-Christophe Filliatre                               *)
(*                                                                        *)
(*  This software is free software; you can redistribute it and/or        *)
(*  modify it under the terms of the GNU Library General Public           *)
(*  License version 2.1, with the special exception on linking            *)
(*  described in file LICENSE.                                            *)
(*                                                                        *)
(*  This software is distributed in the hope that it will be useful,      *)
(*  but WITHOUT ANY WARRANTY; without even the implied warranty of        *)
(*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.                  *)
(*                                                                        *)
(**************************************************************************)

(** Vectors (aka resizable arrays, growing arrays, dynamic arrays, etc.)

    This module implements arrays that automatically expand as necessary.
    Its implementation uses a traditional array and replaces it with a
    larger array when needed (and elements are copied from the old array
    to the new one). The current implementation doubles the capacity when
    growing the array (and shrinks it whenever the number of elements
    comes to one fourth of the capacity).

    The unused part of the internal array is filled with a dummy value,
    which is user-provided at creation time (and referred to below
    as ``the dummy value''). Consequently, vectors do not retain pointers
    to values that are not used anymore after a shrinking.

    Vectors provide an efficient implementation of stacks, with a
    better locality of reference than list-based implementations (such
    as standard library {!Stack}). A stack interface is provided,
    similar to that of {!Stack} (though {!Vector.push} have arguments
    in the other way round). Inserting [n] elements with
    {!Vector.push} has overall complexity O(n) i.e. each insertion has
    amortized constant time complexity. *)

type 'a t
  (** The polymorphic type of vectors.
      This is a mutable data type. *)


(** {2 Operations proper to vectors, or with a different type and/or
    semantics than those of module [Array]} *)

val make: int -> dummy:'a -> 'a t
(** [Vector.make n dummy] returns a fresh vector of length [n].
   All the elements of this new vector are initially
   physically equal to [dummy] (in the sense of the [==] predicate).

   Raise [Invalid_argument] if [n < 0] or [n > Sys.max_array_length].
   If the value of [dummy] is a floating-point number, then the maximum
   size is only [Sys.max_array_length / 2].*)

val create: dummy:'a -> 'a t
(** [Vector.create dummy] returns a fresh vector of length [0]. *)

val init: int -> dummy:'a -> (int -> 'a) -> 'a t
(** [Vector.init n f] returns a fresh vector of length [n],
   with element number [i] initialized to the result of [f i].
   In other terms, [Vector.init n f] tabulates the results of [f]
   applied to the integers [0] to [n-1].

   Raise [Invalid_argument] if [n < 0] or [n > Sys.max_array_length].
   If the return type of [f] is [float], then the maximum
   size is only [Sys.max_array_length / 2].*)

val resize: 'a t -> int -> unit
(** [Vector.resize a n] sets the length of vector [a] to [n].

   The elements that are no longer part of the vector, if any, are
   internally replaced by the dummy value of vector [a], so that they
   can be garbage collected when possible.

   Raise [Invalid_argument] if [n < 0] or [n > Sys.max_array_length]. *)


(** {2 Stack interface}

    Contrary to standard library's {Stack}, module {Vector} uses less space
    (between N and 2N words, instead of 3N) and has better data locality. *)

val push: 'a t -> 'a -> unit
(** [Vector.push a x] appends [x] at the end of vector [a], i.e.,
    increases the size of [a] by one and stores [x] at the rightmost
    position.

    Note: the order of the arguments is not that of {!Stack.push}. *)

exception Empty
(** Raised when {!Vector.pop} or {!Vector.top} is applied to an empty vector. *)

val pop: 'a t -> 'a
(** [Vector.pop a] removes and returns the rightmost element in vector [a],
   or raises [Empty] if the stack is empty. *)

val top: 'a t -> 'a
(** [Vector.top a] returns the rightmost element in vector [a],
   or raises [Empty] if the vector is empty. *)

val clear: 'a t -> unit
(** Discard all elements from a vector.
    This is equivalent to setting the size to 0 with [resize]. *)

val is_empty: 'a t -> bool
(** Return [true] if the given vector is empty, [false] otherwise. *)


(** {2 Array interface} *)

val length: 'a t -> int
(** Return the length (number of elements) of the given vector.
    Note: the number of memory words occupiedby the vector can be larger. *)

val get: 'a t -> int -> 'a
(** [Vector.get a n] returns the element number [n] of vector [a].
    The first element has number [0]. The last element has number
    [Vector.length a - 1].

    Raise [Invalid_argument "Vector.get"]
    if [n] is outside the range [0] to [Vector.length a - 1]. *)

val set: 'a t -> int -> 'a -> unit
(** [Vector.set a n x] modifies vector [a] in place, replacing
   element number [n] with [x].

   Raise [Invalid_argument "Vector.set"]
   if [n] is outside the range 0 to [Vector.length a - 1]. *)

val append: 'a t -> 'a t -> unit
(** [Vector.append a1 a2] appends the elements of vector [a2] to the end
    of vector [a1].
    It works correctly even if [a1] and [a2] are the same vector. *)

val sub: 'a t -> int -> int -> 'a t
(** [Vector.sub a start len] returns a fresh vector of length [len], containing
    the elements number [start] to [start + len - 1] of vector [a]. *)

val copy: 'a t -> 'a t
(** [Vector.copy a] returns a copy of [a], that is, a fresh vector containing
    the same elements as [a]. *)

val fill : 'a t -> int -> int -> 'a -> unit
(** [Vector.fill a ofs len x] modifies the vector [a] in place,
    storing [x] in elements number [ofs] to [ofs + len - 1].

    Raise [Invalid_argument "Vector.fill"] if [ofs] and [len] do not
    designate a valid subvector of [a]. *)

val blit : 'a t -> int -> 'a t -> int -> int -> unit
(** [Vector.blit v1 o1 v2 o2 len] copies [len] elements
   from vector [v1], starting at element number [o1], to vector [v2],
   starting at element number [o2]. It works correctly even if
   [v1] and [v2] are the same vector, and the source and
   destination chunks overlap.

   Raise [Invalid_argument "Vector.blit"] if [o1] and [len] do not
   designate a valid subvector of [v1], or if [o2] and [len] do not
   designate a valid subvector of [v2]. *)

val to_list : 'a t -> 'a list
(** [Vector.to_list a] returns the list of all the elements of [a]. *)

val of_list: dummy:'a -> 'a list -> 'a t
(** [Vector.of_list dummy l] returns a fresh vector containing the elements
    of [l]. *)

val to_array: 'a t -> 'a array
(** [Vector.to_array a] returns the array of all the elements of [a]. *)

val of_array: dummy:'a -> 'a array -> 'a t
(** [Vector.of_array dummy a] returns a fresh vector containing the elements
    of [a]. *)

val iter : ('a -> unit) -> 'a t -> unit
(** [Vector.iter f a] applies function [f] in turn to all
   the elements of [a].  It is equivalent to
   [f (get a 0); f (get a 1); ...; f (get a (Vector.length a - 1))]. *)

val map : ('a -> 'b) -> 'a t -> 'b t
(** [Vector.map f a] applies function [f] to all the elements of [a],
   and builds a fresh vector with the results returned by [f].

   Note: the dummy value of the returned vector is obtained by applying
   [f] to the dummy value of [a]. If this is not what you want,
   first create a new vector and then fill it with the value
   [f (get a 0)], [f (get a 1)], etc. *)

val iteri : (int -> 'a -> unit) -> 'a t -> unit
(** Same as {!Vector.iter}, but the
   function is applied to the index of the element as first argument,
   and the element itself as second argument. *)

val mapi : (int -> 'a -> 'b) -> 'a t -> 'b t
(** Same as {!Vector.map}, but the
   function is applied to the index of the element as first argument,
   and the element itself as second argument.

   Note: the dummy value of the returned vector is obtained by applying
   [f 0] to the dummy value of [a].  *)

val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a
(** [Vector.fold_left f x a] computes
   [f (... (f (f x (get a 0)) (get a 1)) ...) (get a (n-1))],
   where [n] is the length of the vector [a]. *)

val fold_right : ('b -> 'a -> 'a) -> 'b t -> 'a -> 'a
(** [Vector.fold_right f a x] computes
   [f (get a 0) (f (get a 1) ( ... (f (get a (n-1)) x) ...))],
   where [n] is the length of the vector [a]. *)


(** {2 Only if you know what you are doing...} *)

val unsafe_get : 'a t -> int -> 'a
val unsafe_set : 'a t -> int -> 'a -> unit


This document was generated using caml2html