Source file sigs.ml

(*****************************************************************************)
(*                                                                           *)
(* Open Source License                                                       *)
(* Copyright (c) 2020 Nomadic Labs, <contact@nomadic-labs.com>               *)
(*                                                                           *)
(* Permission is hereby granted, free of charge, to any person obtaining a   *)
(* copy of this software and associated documentation files (the "Software"),*)
(* to deal in the Software without restriction, including without limitation *)
(* the rights to use, copy, modify, merge, publish, distribute, sublicense,  *)
(* and/or sell copies of the Software, and to permit persons to whom the     *)
(* Software is furnished to do so, subject to the following conditions:      *)
(*                                                                           *)
(* The above copyright notice and this permission notice shall be included   *)
(* in all copies or substantial portions of the Software.                    *)
(*                                                                           *)
(* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR*)
(* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,  *)
(* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL   *)
(* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER*)
(* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING   *)
(* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER       *)
(* DEALINGS IN THE SOFTWARE.                                                 *)
(*                                                                           *)
(*****************************************************************************)

(** A mutable structure that holds at most a fixed number of values of a same
    type. Values are automatically removed to make room for new values when
    needs be, and they can also be removed by hand if needed.

    The function [promote] (see below) allows to pull a node to the front of
    the buffer. *)
module type COLLECTION_BARE = sig

  (** The type of bounded-size buffers. *)
  type 'a t

  (** [node]s are boxes that contain data. Boxes are never meant to be returned
      to the end user (they can be unsafe), they are meant to build some
      abstraction on top of the buffer.

      In order to make the module safe and remove all notion of box, use the
      functor [Misc.Unbox]. *)
  type 'a node

  (** [data n] is the value contained in the node [n]. *)
  val data : 'a node -> 'a

  (** [create n] allocates a buffer that can hold up to [n] elements.
      @raise [Invalid_argument] if [n] is 0 or less. *)
  val create : int -> 'a t

  (** [capacity b] is the number of elements that [b] can hold. *)
  val capacity : 'a t -> int

  (** [length b] is the number of elements that are currently in [b]. *)
  val length : 'a t -> int

  (** [add b v] adds the value [v] to the buffer [b]. If the buffer [b] already
      has [capacity b] values, then a value is dropped.

      [adds b v] returns the node containing the value [v]. This node can be
      used to [promote] or [remove] the value [v] from the buffer [b]. *)
  val add : 'a t -> 'a -> 'a node

  (** [add_and_return_erased b v] has the same effect as [add b v] but it
      returns the dropped value when applicable (and [None] otherwise). *)
  val add_and_return_erased : 'a t -> 'a -> ('a node * 'a option)

  (** [add_list b vs] adds each element of the list [vs] in the order they
      appear in the list. It returns a list of nodes, for each of the inserted
      elements.

      If [length vs > capacity b], then each value from [vs] is added, but the
      ones at the front of the list are popped. In this case, [add_list b vs]
      returns a list of [capacity b] nodes only. *)
  val add_list : 'a t -> 'a list -> 'a node list

  (** [clear b] removes all values from the buffer [b]. *)
  val clear : 'a t -> unit

  (** [fold b ~init ~f] folds over the value of the buffer [b], newest to oldest. *)
  val fold : 'a t -> init:'b -> f:('b -> 'a node -> 'b) -> 'b

  (** [fold_oldest_first b ~init ~f] folds over the value of the buffer [b], oldest to newest. *)
  val fold_oldest_first : 'a t -> init:'b -> f:('b -> 'a node -> 'b) -> 'b

  (** [elements b] is a list of nodes from [b]. They appear oldest first, newest
      last. *)
  val elements : 'a t -> 'a node list

  (** [elements_data b] is a list of the data content of the nodes of [b]. It is
      equivalent to [List.map data (elements b)] but with better performance. *)
  val elements_data : 'a t -> 'a list

  (** [oldest_element b] returns the oldest inserted element
      from the buffer [b] if any. *)
  val oldest_element : 'a t -> 'a node option

  (** [newest_element b] returns the oldest inserted element
      from the buffer [b] if any. *)
  val newest_element : 'a t -> 'a node option

  (** [remove b n] removes the node [n] from the buffer [b].

      The behavior of this function is undefined if [n] is not part of [b],
      i.e., if [List.exists ((==) n) (elements b)] is [false].

      It is the responsibility of the user of this library (presumably, another
      library wrapping the primitives of this one) to ensure this is never the
      case. *)
  val remove : 'a t -> 'a node -> unit

  (** [remove_oldest b] removes and returns the oldest inserted element
      from the buffer [b] or [None] if the buffer is empty. *)
  val remove_oldest : 'a t -> 'a node option

  (** [remove_newest b] removes and returns the most recently inserted
      element from the buffer [b] or [None] if the buffer is empty. *)
  val remove_newest : 'a t -> 'a node option

  (** [promote b n] places the node [n] to the front of the buffer [b], making
      the node [n] the newest of the nodes of the buffer [b].

      [promote b n] is similar to [remove b n; ignore (add b @@ data n)] except
      that: it is more efficient, and it keeps the value [data n] in the same
      node it was originally inserted in.

      The behavior of this function is undefined if [n] is not part of [b],
      i.e., if [List.exists ((==) n) (elements b)] is [false]. *)
  val promote : 'a t -> 'a node -> unit

end

module type COLLECTION = sig

  include COLLECTION_BARE

  val promote_read : 'a t -> 'a node -> unit

  val promote_write : 'a t -> 'a node -> unit

end

module type WEIGHTED_COLLECTION_BARE = sig
  include COLLECTION_BARE

  (** [capacity b] is the maximum weight that [b] can hold. *)
  val capacity : 'a t -> int

  (** [weight e] returns the weight of the element [e]. *)
  val weight : 'a node -> int

  (** [total_weight b] is the summed weight of all elements that are
      currently in [b]. *)
  val total_weight : 'a t -> int

  (** [add b (v, w)] adds the value [v] of weight [w] to the buffer
      [b]. If the buffer [b] cannot hold this value, i.e., [w >
      capacity b] then this value is not added. And, if by adding this
      value, the buffer would get too full, older values will be
      dropped until the [v] fits.

      [adds b (v, w)] returns the node containing the value [v]. This
      node can be used to [promote] or [remove] the value [v] from the
      buffer [b]. *)
  val add : 'a t -> 'a * int -> 'a node option

  (** [add_and_return_erased b (v, w)] has the same effect as [add b
      (v,w)] but it also returns the dropped values when applicable
      (and [None] otherwise). Dropped values are ordered from
      the oldest to the most recently inserted. *)
  val add_and_return_erased : 'a t -> 'a * int -> 'a node option * 'a list

  (** [add_list b vs] adds each element (with their weight) of the
      list [vs] in the order they appear in the list. It returns a
      list of nodes, for each of the inserted elements. Elements that
      are too large in [vs] w.r.t to [capacity b] are filtered out.

      If the total weight of [vs] is larger than [capacity b] then a
      first-fit strategy is used and the last elements in [vs] are
      prioritized.

      For instance: [add_list (create 5) [(x, 1); (y, 3); (z, 4)]]
      will successfully return [[x ; z]] which are added in the
      buffer. *)
  val add_list : 'a t -> ('a * int) list -> 'a node list
end

module type WEIGHTED_COLLECTION = sig
  include WEIGHTED_COLLECTION_BARE

  val promote_read : 'a t -> 'a node -> unit

  val promote_write : 'a t -> 'a node -> unit
end

(** A mutable structure that holds at most a fixed number of values of a same
    type. Values are automatically removed to make room for new values when
    needs be, and they can also be removed by hand if needed. *)
module type UNBOXED_COLLECTION = sig

  (** The type of bounded-size buffers. *)
  type 'a t

  (** [create n] allocates a ring buffer that can hold up to [n] values.
      @raise [Invalid_argument] if [n] is 0 or less. *)
  val create : int -> 'a t

  (** [capacity b] is the number of elements that [b] can hold. *)
  val capacity : 'a t -> int

  (** [length b] is the number of elements that are currently in [b]. *)
  val length : 'a t -> int

  (** [add b v] adds the value [v] to the buffer [b]. If the buffer [b] already
      has [capacity b] values, the oldest of its values is dropped. *)
  val add : 'a t -> 'a -> unit

  (** [add_and_return_erased b v] has the same effect as [add b v] but it
      returns the dropped value when applicable. *)
  val add_and_return_erased : 'a t -> 'a -> 'a option

  (** [add_list b vs] adds each element of the list [vs] in the order they
      appear in the list. Note that if [List.length vs > capacity b], then only
      the last [capacity b] elements of the list remain in [b] at the end. *)
  val add_list : 'a t -> 'a list -> unit

  (** [remove_oldest b] removes and returns the oldest inserted element
      from the buffer [b] or [None] if the buffer is empty.

      Note that for some collections, the removed element might still
      be held in memory. It will be removed eventually after other
      elements are added. *)
  val remove_oldest : 'a t -> 'a option

  (** [remove_newest b] removes and returns the most recently inserted
      element from the buffer [b] or [None] if the buffer is empty.

      Note that for some collections, the removed element might still
      be held in memory. It will be removed eventually after other
      elements are added. *)
  val remove_newest : 'a t -> 'a option

  (** [clear b] removes all values from the buffer [b]. *)
  val clear : 'a t -> unit

  (** [fold b ~init ~f] folds over the value of the buffer [b], newest to oldest. *)
  val fold : 'a t -> init:'b -> f:('b -> 'a -> 'b) -> 'b

  (** [fold_oldest_first b ~init ~f] folds over the value of the buffer [b],
      oldest to newest. *)
  val fold_oldest_first : 'a t -> init:'b -> f:('b -> 'a -> 'b) -> 'b

  (** [elements b] is a list that contains the same elements as the buffer [b],
      oldest first, newest last. *)
  val elements : 'a t -> 'a list

  (** [oldest_element b] returns the oldest inserted element
      from the buffer [b] if any. *)
  val oldest_element : 'a t -> 'a option

  (** [newest_element b] returns the oldest inserted element
      from the buffer [b] if any. *)
  val newest_element : 'a t -> 'a option
end

module type UNBOXED_WEIGHTED_COLLECTION = sig
  (** The type of bounded-size buffers. *)
  type 'a t

  (** [create n] allocates a ring buffer that can hold up to [n] values.
      @raise [Invalid_argument] if [n] is 0 or less. *)
  val create : int -> 'a t

  (** [capacity b] is the number of elements that [b] can hold. *)
  val capacity : 'a t -> int

  (** [length b] is the number of elements that are currently in [b]. *)
  val length : 'a t -> int

  (** [total_weight b] is the summed weight of all elements that are
      currently in [b]. *)
  val total_weight : 'a t -> int

  (** [add b (v, w)] adds the value [v] of weight [w] to the buffer
      [b]. If the buffer [b] cannot hold this value, i.e., [w >
      capacity b] then this value is not added. And, if by adding this
      value, the buffer would get too full, older values will be
      dropped until the [v] fits. *)
  val add : 'a t -> 'a * int -> unit

  (** [add_and_return_erased b (v, w)] has the same effect as [add b
      (v,w)] but it also returns the dropped values when applicable
      (and [None] otherwise). Dropped values are ordered from the
      oldest to the most recently inserted *)
  val add_and_return_erased : 'a t -> 'a * int -> 'a list

  (** [add_list b vs] adds each element (with their weight) of the
      list [vs] in the order they appear in the list. It returns a
      list of nodes, for each of the inserted elements. Elements that
      are too large in [vs] w.r.t to [capacity b] are filtered out.

      If the total weight of [vs] is larger than [capacity b] then a
      first-fit strategy is used and the last elements in [vs] are
      prioritized.

      For instance: [add_list (create 5) [(x, 1); (y, 3); (z, 4)]]
      will successfully return [[x ; z]] which are added in the
      buffer. *)
  val add_list : 'a t -> ('a * int) list -> unit

  (** [clear b] removes all values from the buffer [b]. *)
  val clear : 'a t -> unit

  (** [fold b ~init ~f] folds over the value of the buffer [b], newest to oldest. *)
  val fold : 'a t -> init:'b -> f:('b -> 'a -> 'b) -> 'b

  (** [fold_oldest_first b ~init ~f] folds over the value of the buffer [b],
      oldest to newest. *)
  val fold_oldest_first : 'a t -> init:'b -> f:('b -> 'a -> 'b) -> 'b

  (** [elements b] is a list that contains the same elements as the buffer [b],
      oldest first, newest last. *)
  val elements : 'a t -> 'a list

  (** [oldest_element b] returns the oldest inserted element
      from the buffer [b] if any. *)
  val oldest_element : 'a t -> 'a option

  (** [newest_element b] returns the oldest inserted element
      from the buffer [b] if any. *)
  val newest_element : 'a t -> 'a option

  (** [remove_oldest b] removes and returns the oldest inserted element
      from the buffer [b] or [None] if the buffer is empty. *)
  val remove_oldest : 'a t -> 'a option

  (** [remove_newest b] removes and returns the most recently inserted
      element from the buffer [b] or [None] if the buffer is empty. *)
  val remove_newest : 'a t -> 'a option

end