(*
* Funarr - a functional (applicative) array implementation
* Copyright (C) 2004 Brian Hurt
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version,
* with the special exception on linking described in file LICENSE.
*
* This library 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. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*)
(** A Functional (Applicative) Array
*
* This module implements a functional or applicative array, based upon a
* weight balanced tree. Inserting an element at any location, accessing
* an element at any location, and removing an element at any location
* is an O(log N) operation.
*
* The interface to this module is designed to be similiar to the
* {!Array} standard library, but obviously the differences between being
* imperitive and functional makes it impossible to be a drop-in replacement.
*)
(* The type of a functional array. *)
type 'a t
(** The empty array. *)
val empty : 'a t
(** Return the length (number of elements) of the array. This is an O(1)
operation.
*)
val length : 'a t -> int
(** [Funarr.get a n] returns the element number [n] of array [a].
This is an O(log N) operation.
The first element has number 0.
The last element has number [(Funarr.length a) - 1].
Raise [Invalid_argument "index out of bounds"] if [n] is outside
the range 0 to [(Funarr.length a) - 1].
*)
val get : 'a t -> int -> 'a
(** [Funarr.set a n x] returns a changed version of [a] that has
[x] as the element at index [n] instead. Note that [set] can
not change the length of the funarr! It replaces one element with
another only, use {!insert} instead.
This is an O(log N) operation.
Raise [Invalid_argument "index out of bounds"] if [n] is outside
the range 0 to [(Funarr.length a) - 1].
*)
val set : 'a t -> int -> 'a -> 'a t
(** [Funarr.insert a n x] returns a changed version of [a] that
has [x] inserted at location [n]. All the elements in the range
[n] to [(Funarr.length a) - 1] have their numbers incremented, so
that they are in the range [n+1] to [Funarr.length a] instead.
It is permissible to insert an element at location [Funarr.length a]-
this simply appends the element onto the end of the funarr.
This is an O(log N) operation.
Raise [Invalid_argument "index out of bounds"] if [n] is outside
the range 0 to [Funarr.length a].
*)
val insert : 'a t -> int -> 'a -> 'a t
(** [Funarr.remove a n] creates a modified version of [a] with the
element number [n] removed. The elements [n+1] through
[(Funarr.length a) - 1] have their numbers decremented, so that
they have numbers [n] through [(Funarr.length a) - 2]. The length
of the modified array is one less.
This is an O(log N) operation.
Raise [Invalid_argument "index out of bounds"] if [n] is outside
the range 0 to [(Funarr.length a) - 1].
*)
val remove : 'a t -> int -> 'a t
(** [Funarr.make n x] creates a new array of length [n], with all elements
initialized to the value [x].
Like {!Array.make}, all the elements of this new array are initially
physically equal to [x] (in the sense of the [==] predicate).
Consequently, if [x] is mutable, it is shared among all elements
of the array, and modifying [x] through one of the array entries
will modify all other entries at the same time.
This is an O(N) operation.
Raise [Invalid_argument] if [n < 0].
*)
val make : int -> 'a -> 'a t
(** [Funarr.create n f] returns a new array of length [n], where
element [i] is initialized to [f i].
This is an O(N) operation.
Raise [Invalid_argument] if [n < 0].
*)
val init : int -> (int -> 'a) -> 'a t
(** [Funarr.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 (Array.length a - 1)); ()].
This is an O(N) operation.
*)
val iter : ('a -> unit) -> 'a t -> unit
(** [Funarr.map f a] builds a new array of the same length as as
[a], with element [i] of the new list having the value
[f (get a i)].
This is an O(N) operation.
*)
val map : ('a -> 'b) -> 'a t -> 'b t
(** [Funarr.fold_left f x a] computes
[f (... (f (f x (get a 0)) (get a 1)) ...) (get a ((length a)-1))].
This is an O(N) operation.
*)
val fold_left : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a
(** [Funarr.fold_right f a x] computes
[f (get a 0) (f (get a 1) ( ... (f (get a ((length a) -1)) x) ...))].
This is an O(N) operation.
*)
val fold_right : ('b -> 'a -> 'a) -> 'b t -> 'a -> 'a